Type structure complexity and decidability
HTML articles powered by AMS MathViewer
- by T. S. Millar PDF
- Trans. Amer. Math. Soc. 271 (1982), 73-81 Request permission
Abstract:
We prove that for every countable homogeneous model $\mathcal {A}$ such that the set of recursive types of $\operatorname {Th} (\mathcal {A})$ is $\sum _2^0$, $\mathcal {A}$ is decidable iff the set of types realized in $\mathcal {A}$ is a $\sum _2^0$ set of recursive types. As a corollary to a lemma, we show that if a complete theory $T$ has a recursively saturated model that is decidable in the degree of $T$, then $T$ has a prime model.References
- Leo Harrington, Recursively presentable prime models, J. Symbolic Logic 39 (1974), 305–309. MR 351804, DOI 10.2307/2272643
- Terrence S. Millar, Foundations of recursive model theory, Ann. Math. Logic 13 (1978), no. 1, 45–72. MR 482430, DOI 10.1016/0003-4843(78)90030-X
- C. C. Chang and H. J. Keisler, Model theory, Studies in Logic and the Foundations of Mathematics, Vol. 73, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. MR 0409165
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- Terrence Millar, Homogeneous models and decidability, Pacific J. Math. 91 (1980), no. 2, 407–418. MR 615688
Additional Information
- © Copyright 1982 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 271 (1982), 73-81
- MSC: Primary 03C15; Secondary 03B25, 03D35
- DOI: https://doi.org/10.1090/S0002-9947-1982-0648078-8
- MathSciNet review: 648078