Computable structure theory using admissible recursion theory on ω<span class='sub'>1</span> using admissibility

doi:10.1017/CBO9781139028592.005

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

Published online by Cambridge University Press: 05 December 2013

Noam Greenberg and

Julia F. Knight

Edited by

Noam Greenberg,

Denis Hirschfeldt,

Joel David Hamkins and

Russell Miller

Show author details

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

Book contents

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.

Information

Type: Chapter
Information: Effective Mathematics of the Uncountable , pp. 50 - 80
DOI: https://doi.org/10.1017/CBO9781139028592.005 [Opens in a new window]
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.)

Book purchase

Temporarily unavailable

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

Accessibility standard: Unknown

Why this information is here

This section outlines the accessibility features of this content - including support for screen readers, full keyboard navigation and high-contrast display options. This may not be relevant for you.

Accessibility Information

Accessibility compliance for the PDF of this chapter is currently unknown and may be updated in the future.