On the computability-theoretic complexity of trivial, strongly minimal models

Khoussainov, Bakhadyr; Laskowski, Michael; Lempp, Steffen; Solomon, Reed

doi:10.1090/S0002-9939-07-08865-X

On the computability-theoretic complexity of trivial, strongly minimal models

Authors: Bakhadyr M. Khoussainov, Michael C. Laskowski, Steffen Lempp and Reed Solomon
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
Published electronically: June 21, 2007
MathSciNet review: 2336588
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

[BL71] J. T. Baldwin and A. H. Lachlan, On strongly minimal sets, J. Symbolic Logic 36 (1971), 79–96. MR 286642, https://doi.org/10.2307/2271517
[Bu96] Steven Buechler, Essential stability theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1996. MR 1416106
[CK90] 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
[Go78] S. S. Gončarov, Constructive models of ℵ₁-categorical theories, Mat. Zametki 23 (1978), no. 6, 885–888 (Russian). MR 502056
[GK04] 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, https://doi.org/10.1023/B:ALLO.0000048826.92325.02
[GHLLM03] 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, https://doi.org/10.1090/S0002-9939-03-06951-X
[Ha74] Leo Harrington, Recursively presentable prime models, J. Symbolic Logic 39 (1974), 305–309. MR 351804, https://doi.org/10.2307/2272643
[HLZ99] 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, https://doi.org/10.1090/S0002-9939-99-04920-5
[Kh74] Khisamiev, Nazif G., On strongly constructive models of decidable theories, Izv. Akad. Nauk Kazakh. SSR Ser. Fiz.-Mat. 35 (1) (1974), 83-84.
[KNS97] 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, https://doi.org/10.1305/ndjfl/1039724885
[Kuta] Kueker, David W., Weak invariance and model completeness relative to parameters, in preparation.
[Ku80] K. Ž. Kudaĭbergenov, Constructivizable models of undecidable theories, Sibirsk. Mat. Zh. 21 (1980), no. 5, 155–158, 192 (Russian). MR 592228
[Ma89] David Marker, Non Σ_{𝑛} axiomatizable almost strongly minimal theories, J. Symbolic Logic 54 (1989), no. 3, 921–927. MR 1011179, https://doi.org/10.2307/2274752
[Mo65] Michael Morley, Categoricity in power, Trans. Amer. Math. Soc. 114 (1965), 514–538. MR 175782, https://doi.org/10.1090/S0002-9947-1965-0175782-0
[Ni99] André Nies, A new spectrum of recursive models, Notre Dame J. Formal Logic 40 (1999), no. 3, 307–314. MR 1845630, https://doi.org/10.1305/ndjfl/1022615611

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03C57, 03D45

Retrieve articles in all journals with MSC (2000): 03C57, 03D45

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
Email: lempp@math.wisc.edu

Reed Solomon
Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269
Email: solomon@math.uconn.edu

DOI: https://doi.org/10.1090/S0002-9939-07-08865-X
Keywords: Computable model, uncountably categorical, strongly minimal, trivial geometry, axiomatizability
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
Article copyright: © Copyright 2007 American Mathematical Society