Ranked structures and arithmetic transfinite recursion

Greenberg, Noam; Montalbán, Antonio

doi:10.1090/S0002-9947-07-04285-7

Ranked structures and arithmetic transfinite recursion
HTML articles powered by AMS MathViewer

by Noam Greenberg and Antonio Montalbán PDF

Trans. Amer. Math. Soc. 360 (2008), 1265-1307 Request permission

Abstract:

$\mathsf {ATR}_0$ is the natural subsystem of second-order arithmetic in which one can develop a decent theory of ordinals. We investigate classes of structures which are in a sense the “well-founded part" of a larger, simpler class, for example, superatomic Boolean algebras (within the class of all Boolean algebras). The other classes we study are: well-founded trees, reduced Abelian $p$-groups, and countable, compact topological spaces. Using computable reductions between these classes, we show that Arithmetic Transfinite Recursion is the natural system for working with them: natural statements (such as comparability of structures in the class) are equivalent to $\mathsf {ATR}_0$. The reductions themselves are also objects of interest.

References

C. J. Ash and J. Knight, Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000. MR 1767842
Ewan J. Barker, Back and forth relations for reduced abelian $p$-groups, Ann. Pure Appl. Logic 75 (1995), no. 3, 223–249. MR 1355134, DOI 10.1016/0168-0072(94)00045-5
Jon Barwise and Paul Eklof, Infinitary properties of abelian torsion groups, Ann. Math. Logic 2 (1970/71), no. 1, 25–68. MR 279180, DOI 10.1016/0003-4843(70)90006-9
Wesley Calvert, The isomorphism problem for classes of computable fields, Arch. Math. Logic 43 (2004), no. 3, 327–336. MR 2052886, DOI 10.1007/s00153-004-0219-1
U. Kalvert, D. Kammins, Dz. F. Naĭt, and S. Miller, Comparison of classes of finite structures, Algebra Logika 43 (2004), no. 6, 666–701, 759 (Russian, with Russian summary); English transl., Algebra Logic 43 (2004), no. 6, 374–392. MR 2135387, DOI 10.1023/B:ALLO.0000048827.30718.2c
Riccardo Camerlo and Su Gao, The completeness of the isomorphism relation for countable Boolean algebras, Trans. Amer. Math. Soc. 353 (2001), no. 2, 491–518. MR 1804507, DOI 10.1090/S0002-9947-00-02659-3
Peter Cholak, Alberto Marcone, and Reed Solomon, Reverse mathematics and the equivalence of definitions for well and better quasi-orders, J. Symbolic Logic 69 (2004), no. 3, 683–712. MR 2078917, DOI 10.2178/jsl/1096901762
Harvey M. Friedman and Jeffry L. Hirst, Weak comparability of well orderings and reverse mathematics, Ann. Pure Appl. Logic 47 (1990), no. 1, 11–29. MR 1050559, DOI 10.1016/0168-0072(90)90014-S
Harvey M. Friedman and Jeffry L. Hirst, Reverse mathematics and homeomorphic embeddings, Ann. Pure Appl. Logic 54 (1991), no. 3, 229–253. MR 1133006, DOI 10.1016/0168-0072(91)90048-Q
Harvey Friedman, Metamathematics of comparability, Manuscript dated October 2001.
—, Metamathematics of Ulm theory, Manuscript dated November 2001.
Harvey M. Friedman, Stephen G. Simpson, and Rick L. Smith, Countable algebra and set existence axioms, Ann. Pure Appl. Logic 25 (1983), no. 2, 141–181. MR 725732, DOI 10.1016/0168-0072(83)90012-X
Su Gao, The homeomorphism problem for countable topological spaces, Topology Appl. 139 (2004), no. 1-3, 97–112. MR 2051099, DOI 10.1016/j.topol.2003.09.005
S. S. Goncharov and Dzh. Naĭt, Computable structure and antistructure theorems, Algebra Logika 41 (2002), no. 6, 639–681, 757 (Russian, with Russian summary); English transl., Algebra Logic 41 (2002), no. 6, 351–373. MR 1967769, DOI 10.1023/A:1021758312697
Jeffry L. Hirst, Reverse mathematics and ordinal exponentiation, Ann. Pure Appl. Logic 66 (1994), no. 1, 1–18. MR 1263322, DOI 10.1016/0168-0072(94)90076-0
Jeffry L. Hirst, Reverse mathematics and rank functions for directed graphs, Arch. Math. Logic 39 (2000), no. 8, 569–579. MR 1797809, DOI 10.1007/s001530050165
Jeffry L. Hirst, A survey of the reverse mathematics of ordinal arithmetic, Reverse mathematics 2001, Lect. Notes Log., vol. 21, Assoc. Symbol. Logic, La Jolla, CA, 2005, pp. 222–234. MR 2185437
Greg Hjorth and Alexander S. Kechris, Analytic equivalence relations and Ulm-type classifications, J. Symbolic Logic 60 (1995), no. 4, 1273–1300. MR 1367210, DOI 10.2307/2275888
Greg Hjorth and Alexander S. Kechris, Recent developments in the theory of Borel reducibility, Fund. Math. 170 (2001), no. 1-2, 21–52. Dedicated to the memory of Jerzy Łoś. MR 1881047, DOI 10.4064/fm170-1-2
Irving Kaplansky, Infinite abelian groups, Revised edition, University of Michigan Press, Ann Arbor, Mich., 1969. MR 0233887
Sabine Koppelberg, Handbook of Boolean algebras. Vol. 1, North-Holland Publishing Co., Amsterdam, 1989. Edited by J. Donald Monk and Robert Bonnet. MR 991565
Antonio Montalbán, Beyond the arithmetic, Ph.D. thesis, Cornell University, Ithaca, New York, 2005.
Antonio Montalbán, Up to equimorphism, hyperarithmetic is recursive, J. Symbolic Logic 70 (2005), no. 2, 360–378. MR 2140035, DOI 10.2178/jsl/1120224717
James R. Munkres, Topology, second ed., Prentice-Hall Inc., Englewood Cliffs, N.J., 2000.
Gerald E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970, DOI 10.1007/BFb0086109
V. L. Selivanov, The fine hierarchy and definable index sets, Algebra i Logika 30 (1991), no. 6, 705–725, 771 (Russian, with Russian summary); English transl., Algebra and Logic 30 (1991), no. 6, 463–475 (1992). MR 1213731, DOI 10.1007/BF02018741
John N. Crossley, Jeffrey B. Remmel, Richard A. Shore, and Moss E. Sweedler (eds.), Logical methods, Progress in Computer Science and Applied Logic, vol. 12, Birkhäuser Boston, Inc., Boston, MA, 1993. Papers from the conference in honor of Anil Nerode’s sixtieth birthday held at Cornell University, Ithaca, New York, June 1–3, 1992. MR 1281145, DOI 10.1007/978-1-4612-0325-4
Richard A. Shore, Invariants, Boolean algebras and $\textrm {ACA}^+_0$, Trans. Amer. Math. Soc. 358 (2006), no. 3, 989–1014. MR 2187642, DOI 10.1090/S0002-9947-05-03802-X
Stephen G. Simpson, Subsystems of second order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999. MR 1723993, DOI 10.1007/978-3-642-59971-2
Clifford Spector, Recursive well-orderings, J. Symbolic Logic 20 (1955), 151–163. MR 74347, DOI 10.2307/2266902