Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Available in electronic format
Available in print format 		Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(e) ISSN 0002-9939(p)

     

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

Author(s): Bakhadyr M. Khoussainov; Michael C. Laskowski; Steffen Lempp; Reed Solomon
Journal: Proc. Amer. Math. Soc. 135 (2007), 3711-3721.
MSC (2000): Primary 03C57; Secondary 03D45
Posted: June 21, 2007
MathSciNet review: 2336588
Retrieve article in: PDF

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.

References:

[BL71]
Baldwin, J.T. and Lachlan, A.H., On strongly minimal sets, J. Symbolic Logic, 36 (1971), 79-96. MR 0286642 (44:3851)

[Bu96]
Buechler, Steven A., Essential Stability Theory, Springer-Verlag, Heidelberg, 1996. MR 1416106 (98j:03050)

[CK90]
Chang, Chen Chung and Keisler, H. Jerome, Model theory. Third edition, Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam, 1990. MR 1059055 (91c:03026)

[Go78]
Goncharov, Sergey S., Constructive models of $ \aleph_1$-categorical theories, Mat. Zametki 23 (1978), 885-888. MR 502056 (80g:03029)

[GK04]
Goncharov, Sergey S. and Khoussainov, Bakhadyr M., Complexity of categorical theories with computable models, Algebra and Logic, 43 (2004), 650-665, 758-759. MR 2135386 (2005m:03066)

[GHLLM03]
Goncharov, Sergey S.; Harizanov, Valentina S.; Laskowski, Michael C.; Lempp, Steffen; and McCoy, Charles F. D., Trivial, strongly minimal theories are model complete after naming constants, Proc. Amer. Math. Soc. 131 (2003), 3901-3912. MR 1999939 (2004g:03054)

[Ha74]
Harrington, Leo, Recursively presented prime models, J. Symbolic Logic 39 (1974), 305-309. MR 0351804 (50:4292)

[HLZ99]
Herwig, Bernhard; Lempp, Steffen; and Ziegler, Martin, Constructive models of uncountably categorical theories, Proc. Amer. Math. Soc. 127 (1999), 3711-3719. MR 1610909 (2000b:03129)

[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]
Khoussainov, Bakhadyr M.; Nies, André O.; and Shore, Richard A., Computable models of theories with few models, Notre Dame J. Formal Logic 38 (1997), 165-178. MR 1489408 (99c:03049)

[Kuta]
Kueker, David W., Weak invariance and model completeness relative to parameters, in preparation.

[Ku80]
Kudaibergenov, Kanat Zh., Constructivizable models of undecidable theories, Sibirsk. Mat. Zh. 21 (5) (1980), 155-158, 192. MR 592228 (82h:03040)

[Ma89]
Marker, David, Non $ \Sigma_n$ axiomatizable almost strongly minimal theories, J. Symbolic Logic 54 (1989), 921-927. MR 1011179 (90g:03037)

[Mo65]
Morley, Michael, Categoricity in power, Trans. Amer. Math. Soc. 114 (1965), 514-538. MR 0175782 (31:58)

[Ni99]
Nies, André, A new spectrum of recursive models, Notre Dame J. Formal Logic 40 (1999), 307-314. MR 1845630 (2002e:03066)

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: 10.1090/S0002-9939-07-08865-X
PII: S 0002-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
Posted: 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 of article: Copyright 2007, American Mathematical Society




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia