Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-02-11T13:18:22.900Z Has data issue: false hasContentIssue false

Computable structure theory using admissible recursion theory on ω1 using admissibility

Published online by Cambridge University Press:  05 December 2013

By
Noam Greenberg  and
Julia F. Knight
Edited by
Noam Greenberg ,
Denis Hirschfeldt ,
Joel David Hamkins  and
Russell Miller
Noam Greenberg
Affiliation:
Victoria University of Wellington
Denis Hirschfeldt
Affiliation:
University of Chicago
Joel David Hamkins
Affiliation:
College of Staten Island
Russell Miller
Affiliation:
Queens College, City University of New York
Get access

Summary

Abstract We use the theory of recursion on admissible ordinals to develop an analogue of classical computable model theory and effective algebra for structures of size ℵ1, which, under our assumptions, is equal to the continuum. We discuss both general concepts, such as computable categoricity, and particular classes of examples, such as fields and linear orderings.

§1. Introduction. Our aim is to develop computable structure theory for uncountable structures. In this paper we focus on structures of size ℵ1. The fundamental decision to be made, when trying to formulate such a theory, is the choice of computability tools that we intend to use. To discover which structures are computable, we need to first describe which subsets of the domain are computable, and which functions are computable. In this paper, we use admissible recursion theory (also known as α-recursion theory) over the domain ω1. We believe that this choice yields an interesting computable structure theory. It also illuminates the concepts and techniques of classical computable structure theory by observing similarities and differences between the countable and uncountable settings. In particular, it seems that as is the case for degree theory and for the study of the lattice of c.e. sets, the difference between true finiteness and its analogue in the generalised case, namely countability in our case, is fundamental to some constructions and reveals a deep gap between classical computability and attempts to generalise it to the realm of the uncountable.

Type
Chapter
Information
Effective Mathematics of the Uncountable , pp. 50 - 80
Publisher: Cambridge University Press
Print publication year: 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Chris J., Ash, Carl G., Jockusch Jr., and Julia F., Knight. Jumps of orderings. Trans. Amer. Math. Soc., 319(2): 573–599, 1990.Google Scholar
[2] Chris J., Ash and Julia F., Knight. Computable Structures and the Hyperarithmetical Hierarchy, volume 144 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, 2000.
[3] Shreeram, Abhyankar. On the compositum of algebraically closed subfields. Proc. Amer. Math. Soc., 7: 905–907, 1956.Google Scholar
[4] Chris J., Ash, Julia F., Knight, Mark, Manasse, and Theodore A., Slaman. Generic copies of countable structures. Ann. Pure Appl. Logic, 42(3): 195–205, 1989.Google Scholar
[5] J., Carson, Julia F., Knight, Karen, Lange, Charles, McCoy, and John, Wallbaum. The arithmetical hierarchy in the setting of ω. In preparation.
[6] John, Chisholm. Effective model theory vs. recursive model theory. J. Symbolic Logic, 55(3): 1168–1191, 1990.Google Scholar
[7] Rod, Downey, Denis R., Hirschfeldt, Asher M., Kach, Steffen, Lempp, Joseph R., Mileti, and Antonio, Montalbán. Subspaces of computable vector spaces. J. Algebra, 314(2): 888–894, 2007.Google Scholar
[8] Rod, Downey and Carl G., Jockusch Jr.Every low Boolean algebra is isomorphic to a recursive one. Proc. Amer. Math. Soc., 122(3): 871–880, 1994.Google Scholar
[9] Rod, Downey and Julia F., Knight. Orderings with ath jump degree 0(α). Proc. Amer. Math. Soc., 114(2): 545–552, 1992.Google Scholar
[10] Harvey, Friedman and Lee, Stanley. A Borel reducibility theory for classes of countable structures. J. Symbolic Logic, 54(3): 894–914, 1989.Google Scholar
[11] Sy D., Friedman. Uncountable admissibles I: forcing. Trans. Amer. Math. Soc., 270(1): 61–73, 1982.Google Scholar
[12] A., Fröhlich and J.C., Shepherdson. Effective procedures in field theory. Philos. Trans. Roy. Soc. London. Ser. A., 248: 407–432, 1956.Google Scholar
[13] Sergei S., Gončarov. The number of nonautoequivalent constructivizations. Algebra i Logika, 16(3): 257–282, 377, 1977.Google Scholar
[14] Sergei S., Gončarov and V.D., Dzgoev. Autostability of models. Algebra i Logika, 19(1): 45–58, 132, 1980.Google Scholar
[15] Noam, Greenberg and Julia F., Knight. Relative computable categoricity and Scott families in uncountable computable model theory. In preparation.
[16] Noam, Greenberg, Asher M., Kach, Steffen, Lempp, and Dan, Turetsky. Computable properties of uncountable linear orderings. In preparation.
[17] Carl G., Jockusch Jr. and Robert I., Soare. Degrees of orderings not isomorphic to recursive linear orderings. Ann. Pure Appl. Logic, 52(1-2): 39–64, 1991. International Symposium on Mathematical Logic and its Applications (Nagoya, 1988).Google Scholar
[18] Jesse, Johnson. Computable Model Theory for Uncountable Structures. PhD dissertation, University of Notre Dame, 2013.
[19] Julia F., Knight. Degrees coded in jumps of orderings. J. Symbolic Logic, 51(4): 1034–1042, 1986.Google Scholar
[20] Julia F., Knight and Michael, Stob. Computable Boolean algebras. J. Symbolic Logic, 65(4): 1605–1623, 2000.Google Scholar
[21] Peter, Koepke and Benjamin, Seyfferth. Ordinal machines and admissible recursion theory. Ann. Pure Appl. Logic, 160(3): 310–318, 2009.Google Scholar
[22] Mark, Manasse. Techniques and Counterexamples in Almost Categorical Recursive Model Theory. PhD thesis, University of Wisconsin – Madison, 1982.
[23] George, Metakides and Anil, Nerode. Recursively enumerable vector spaces. Ann. Math. Logic, 11(2): 147–171, 1977.Google Scholar
[24] Terrence S., Millar. Foundations of recursive model theory. Ann. Math. Logic, 13(1): 45–72, 1978.Google Scholar
[25] Russell G., Miller. The -spectrum of a linear order. J. Symbolic Logic, 66(2): 470–486, 2001.Google Scholar
[26] Russell G., Miller. Computable fields and Galois theory. Notices Amer. Math. Soc., 55(7): 798–807, 2008.Google Scholar
[27] Michael, Morley. Decidable models. Israel J. Math., 25(3-4): 233–240, 1976.Google Scholar
[28] A.T., Nurtazin. Strong and weak constructivizations, and enumerable families. Algebra i Logika, 13: 311–323, 364, 1974.Google Scholar
[29] Jeffrey B., Remmel. Recursively categorical linear orderings. Proc. Amer. Math. Soc., 83(2): 387–391, 1981.Google Scholar
[30] Linda Jean, Richter. Degrees of structures. J. Symbolic Logic, 46(4): 723–731, 1981.Google Scholar
[31] Gerald E., Sacks. Higher Recursion Theory. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1990.
[32] Richard A., Shore, α-recursion theory. In Handbook of Mathematical Logic, Part C, pages 525–815. Studies in Logic and the Foundations of Math., Vol. 90. North-Holland, Amsterdam, 1977.
[33] John J., Thurber. Every low2 Boolean algebra has a recursive copy. Proc. Amer. Math. Soc., 123(12): 3859–3866, 1995.Google Scholar
[34] Bartel L., van der Waerden. Eine Bemerkung über die Unzerlegbarkeit von Polynomen. Math. Ann., 102(1): 738–739, 1930.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×