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
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