On the computability-theoretic complexity of trivial, strongly minimal models
HTML articles powered by AMS MathViewer
- by Bakhadyr M. Khoussainov, Michael C. Laskowski, Steffen Lempp and Reed Solomon PDF
- Proc. Amer. Math. Soc. 135 (2007), 3711-3721 Request permission
Abstract:
We show the existence of a trivial, strongly minimal (and thus uncountably categorical) theory for which the prime model is computable and each of the other countable models computes $\boldsymbol {0}''$. This result shows that the result of Goncharov/Harizanov/Laskowski/Lempp/McCoy (2003) is best possible for trivial strongly minimal theories in terms of computable model theory. We conclude with some remarks about axiomatizability.References
- J. T. Baldwin and A. H. Lachlan, On strongly minimal sets, J. Symbolic Logic 36 (1971), 79–96. MR 286642, DOI 10.2307/2271517
- Steven Buechler, Essential stability theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1996. MR 1416106, DOI 10.1007/978-3-642-80177-8
- C. C. Chang and H. J. Keisler, Model theory, 3rd ed., Studies in Logic and the Foundations of Mathematics, vol. 73, North-Holland Publishing Co., Amsterdam, 1990. MR 1059055
- S. S. Gončarov, Constructive models of $\aleph _{1}$-categorical theories, Mat. Zametki 23 (1978), no. 6, 885–888 (Russian). MR 502056
- S. S. Goncharov and B. Khusainov, Complexity of theories of computable categorical models, Algebra Logika 43 (2004), no. 6, 650–665, 758–759 (Russian, with Russian summary); English transl., Algebra Logic 43 (2004), no. 6, 365–373. MR 2135386, DOI 10.1023/B:ALLO.0000048826.92325.02
- Sergey S. Goncharov, Valentina S. Harizanov, Michael C. Laskowski, Steffen Lempp, and Charles F. D. McCoy, Trivial, strongly minimal theories are model complete after naming constants, Proc. Amer. Math. Soc. 131 (2003), no. 12, 3901–3912. MR 1999939, DOI 10.1090/S0002-9939-03-06951-X
- Leo Harrington, Recursively presentable prime models, J. Symbolic Logic 39 (1974), 305–309. MR 351804, DOI 10.2307/2272643
- Bernhard Herwig, Steffen Lempp, and Martin Ziegler, Constructive models of uncountably categorical theories, Proc. Amer. Math. Soc. 127 (1999), no. 12, 3711–3719. MR 1610909, DOI 10.1090/S0002-9939-99-04920-5
- Khisamiev, Nazif G., On strongly constructive models of decidable theories, Izv. Akad. Nauk Kazakh. SSR Ser. Fiz.-Mat. 35 (1) (1974), 83–84.
- Bakhadyr Khoussainov, Andre Nies, and Richard A. Shore, Computable models of theories with few models, Notre Dame J. Formal Logic 38 (1997), no. 2, 165–178. MR 1489408, DOI 10.1305/ndjfl/1039724885
- Kueker, David W., Weak invariance and model completeness relative to parameters, in preparation.
- K. Ž. Kudaĭbergenov, Constructivizable models of undecidable theories, Sibirsk. Mat. Zh. 21 (1980), no. 5, 155–158, 192 (Russian). MR 592228
- David Marker, Non $\Sigma _n$ axiomatizable almost strongly minimal theories, J. Symbolic Logic 54 (1989), no. 3, 921–927. MR 1011179, DOI 10.2307/2274752
- Michael Morley, Categoricity in power, Trans. Amer. Math. Soc. 114 (1965), 514–538. MR 175782, DOI 10.1090/S0002-9947-1965-0175782-0
- André Nies, A new spectrum of recursive models, Notre Dame J. Formal Logic 40 (1999), no. 3, 307–314. MR 1845630, DOI 10.1305/ndjfl/1022615611
Additional Information
- Bakhadyr M. Khoussainov
- Affiliation: Department of Computer Science, University of Auckland, Auckland, New Zealand
- Email: bmk@cs.auckland.ac.nz
- Michael C. Laskowski
- Affiliation: Department of Mathematics, University of Maryland, College Park, Maryland 20742
- Email: mcl@math.umd.edu
- Steffen Lempp
- Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706
- MR Author ID: 247988
- Email: lempp@math.wisc.edu
- Reed Solomon
- Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269
- MR Author ID: 646849
- Email: solomon@math.uconn.edu
- Received by editor(s): December 14, 2005
- Received by editor(s) in revised form: January 19, 2006, and August 4, 2006
- Published electronically: June 21, 2007
- Additional Notes: The first author’s research was partially supported by The Marsden Fund of New Zealand.
The second author’s research was partially supported by NSF grant DMS-0300080.
The third author’s research was partially supported by NSF grant DMS-0140120.
The fourth author’s research was partially supported by NSF grant DMS-0400754. - Communicated by: Julia Knight
- © Copyright 2007 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 135 (2007), 3711-3721
- MSC (2000): Primary 03C57; Secondary 03D45
- DOI: https://doi.org/10.1090/S0002-9939-07-08865-X
- MathSciNet review: 2336588