A decidable Ehrenfeucht theory with exactly two hyperarithmetic models

DOI10.1016/0168-0072(91)90053-OMaRDI QIDQ810001zbMATH OpenFDO

Authors Robert C. Reed

Publication date 1991

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(91)90053-O

zbMATH Keywords

countable modelsdecidable modelsEhrenfeucht theoryhyperarithmetic setpersistently Ehrenfeuchttheory of trees

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Model theory of denumerable and separable structures (03C15) Trees (05C05)

Review text

T is an Ehrenfeucht theory if it has finitely many countable models up to isomorphism and is not \(\omega\)-categorical. T is persistently Ehrenfeucht if for every n-type \(\Gamma\) (x) of T, the theory \(\Gamma\) (c) in the language of T with a new constant c added is Ehrenfeucht. This lengthy paper is devoted to a proof of the following theorem. For each \(n<\omega\) there is a complete, decidable, persistently Ehrenfeucht theory T having exactly five non-isomorphic countable models: three decidable models and two models decidable exactly in the hyperarithmetic set H(n). By a theorem of Millar this is the best that can be achieved if a decidable Ehrenfeucht theory has a countable model which is not \(0\)- decidable. The T exhibited is a theory of trees which is inspired by earlier examples of Millar and Peretyat'kin.

Recommendations

• scientific article; zbMATH DE number 3914293
• A new spectrum of computable models
• Finite extensions and the number of countable models
• Model complete theories of trees
• Spectra of computable models for Ehrenfeucht theories

Cites work

• Foundations of recursive model theory
• scientific article; zbMATH DE number 3914293 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Model theory
• On complete theories with a finite number of denumerable models
• Persistently Finite Theories with Hyperarithmetic Models

Cited in

(10)

• The complexity of countable categoricity in finite languages
• scientific article; zbMATH DE number 4164815 (Why is no real title available?)
• Complexity of Ehrenfeucht models
• scientific article; zbMATH DE number 3914293 (Why is no real title available?)
• Recursive categoricity and persistence
• Finite extensions and the number of countable models
• Autostability of prime models under strong constructivizations
• Model completions and omitting types
• Arithmetical decidability of homogeneous and almost prime countable models of Ehrenfeucht theories with arithmetical types
• Decidable models of Ehrenfeucht theories

This page was built for publication: A decidable Ehrenfeucht theory with exactly two hyperarithmetic models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q810001)