Abstract
In this paper, we give an example of a complete computable infinitary theory T with countable models \({\mathcal{M}}\) and \({\mathcal{N}}\) , where \({\mathcal{N}}\) is a proper computable infinitary extension of \({\mathcal{M}}\) and T has no uncountable model. In fact, \({\mathcal{M}}\) and \({\mathcal{N}}\) are (up to isomorphism) the only models of T. Moreover, for all computable ordinals α, the computable \({\Sigma_\alpha}\) part of T is hyperarithmetical. It follows from a theorem of Gregory (JSL 38:460–470, 1972; Not Am Math Soc 17:967–968, 1970) that if T is a Π 11 set of computable infinitary sentences and T has a pair of models \({\mathcal{M}}\) and \({\mathcal{N}}\) , where \({\mathcal{N}}\) is a proper computable infinitary extension of \({\mathcal{M}}\) , then T would have an uncountable model.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ash, C.J., Knight, J.F.: Computable Structures and the Hyperarithmetical Hierarchy, #144 in Studies in Logic. Elsevier Science, Amsterdam (2000).
Baldwin, J.: Amalgamation, absoluteness, and categoricity. In Proceedings of the 11th Asian Logic Conference 2009, World Scientific, Singapore (2010)
Baldwin, J., Larson, P.: Iterated Elementary Embeddings and the Model Theory of Infinitary Logic (pre-print)
Barwise K.J.: Infinitary logic and admissible sets. J. Symb. Logic 34, 226–252 (1969)
Friedman S.D.: β-recursion theory. Trans. AMS 255, 173–200 (1979)
Friedman S., Koerwien M.: On absoluteness of categoricity in abstract elementary classes. Notre Dame J. Formal Logic 52, 395–402 (2011)
Gregory J.: Elementary extensions and uncountable models for infinitary finite-quantifier language fragments. Not. Am. Math. Soc. 17, 967–968 (1970)
Gregory J.: Uncountable models and infinitary elementary extensions. JSL 38, 460–470 (1972)
Jensen R.B.: The fine structure of the constructible hierarchy. Ann. Math. Logic 4, 229–308 (1972)
Karp, C.: Languages with Expressions of Infinite Length. PhD thesis, University of Southern California (1959)
Knight J.F.: Review: John Gregory, Uncountable models and infinitary elementary extensions. JSL 47, 438–439 (1982)
Knight J.F.: The Kleene-Mostowski Hierarchy and the Davis-Mostowski Hierarchy. In: Ehrenfeucht, A., Marek, V.W., Srebrny, M. (eds) Andrzej Mostowski and foundational studies, IOS Press, Amsterdam (2008)
Keisler H.J.: Model Theory for Infinitary Logic. North-Holland Publishing Company, Amsterdam (1971)
Kreisel, G.: Set-theoretic problems suggested by the notion of potential totality. In: Infinitistic Methods, Pergamon, pp. 103–140 (1961)
Ressayre J.P.: Models with compactness properties relative to an admissible language. Ann. Math. Logic 11, 31–55 (1977)
Ressayre J.-P.: Boolean models and infinitary first order languages. Ann. Math. Logic 6, 41–92 (1973)
Rogers H. Jr.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge (1967)
Sacks G.E., Simpson S.: The α-finite injury method. Ann. Math. Logic 4, 343–367 (1972)
Shore, R.A.: Priority Arguments in Alpha-Recursion Theory, PhD thesis, MIT (1972)
Slaman, T.A.: Aspects of E-Recursion Theory, PhD thesis, Harvard University (1981)
Vanden Boom M.: The effective Borel hierarchy. Fund. Math. 195, 269–289 (2007)
Author information
Authors and Affiliations
Corresponding author
Additional information
The authors are grateful to John Baldwin, Sy Friedman, and Gerald Sacks for their helpful and encouraging comments.
Rights and permissions
About this article
Cite this article
Johnson, J., Knight, J.F., Ocasio, V. et al. An example related to Gregory’s Theorem. Arch. Math. Logic 52, 419–434 (2013). https://doi.org/10.1007/s00153-013-0322-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-013-0322-2