|
Ranked structures and arithmetic transfinite recursion
Authors:
Noam Greenberg and Antonio Montalbán
Journal:
Trans. Amer. Math. Soc. 360 (2008), 1265-1307
MSC (2000):
Primary 03F35, 03D45; Secondary 03C57, 03B30
Posted:
October 23, 2007
MathSciNet review:
2357696
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
Abstract: 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 -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 . The reductions themselves are also objects of interest.
- [AK00]
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
(2001k:03090)
- [Bar95]
Ewan
J. Barker, Back and forth relations for reduced abelian
𝑝-groups, Ann. Pure Appl. Logic 75 (1995),
no. 3, 223–249. MR 1355134
(96j:03066), http://dx.doi.org/10.1016/0168-0072(94)00045-5
- [BE71]
Jon
Barwise and Paul
Eklof, Infinitary properties of abelian torsion groups, Ann.
Math. Logic 2 (1970/1971), no. 1, 25–68. MR 0279180
(43 #4906)
- [Cal04]
Wesley
Calvert, The isomorphism problem for classes of computable
fields, Arch. Math. Logic 43 (2004), no. 3,
327–336. MR 2052886
(2005b:03103), http://dx.doi.org/10.1007/s00153-004-0219-1
- [CCKM04]
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
(2006e:03049), http://dx.doi.org/10.1023/B:ALLO.0000048827.30718.2c
- [CG01]
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
(2001k:03097), http://dx.doi.org/10.1090/S0002-9947-00-02659-3
- [CMS04]
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
(2005e:03020), http://dx.doi.org/10.2178/jsl/1096901762
- [FH90]
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
(91b:03100), http://dx.doi.org/10.1016/0168-0072(90)90014-S
- [FH91]
Harvey
M. Friedman and Jeffry
L. Hirst, Reverse mathematics and homeomorphic embeddings,
Ann. Pure Appl. Logic 54 (1991), no. 3,
229–253. MR 1133006
(92m:03093), http://dx.doi.org/10.1016/0168-0072(91)90048-Q
- [Fria]
Harvey Friedman, Metamathematics of comparability, Manuscript dated October 2001.
- [Frib]
-, Metamathematics of Ulm theory, Manuscript dated November 2001.
- [FSS83]
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
(85i:03157), http://dx.doi.org/10.1016/0168-0072(83)90012-X
- [Gao04]
Su
Gao, The homeomorphism problem for countable topological
spaces, Topology Appl. 139 (2004), no. 1-3,
97–112. MR
2051099 (2005e:54037), http://dx.doi.org/10.1016/j.topol.2003.09.005
- [GK02]
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
(2004a:03047), http://dx.doi.org/10.1023/A:1021758312697
- [Hir94]
Jeffry
L. Hirst, Reverse mathematics and ordinal exponentiation, Ann.
Pure Appl. Logic 66 (1994), no. 1, 1–18. MR 1263322
(95a:03078), http://dx.doi.org/10.1016/0168-0072(94)90076-0
- [Hir00]
Jeffry
L. Hirst, Reverse mathematics and rank functions for directed
graphs, Arch. Math. Logic 39 (2000), no. 8,
569–579. MR 1797809
(2001k:03134), http://dx.doi.org/10.1007/s001530050165
- [Hir05]
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
(2006f:03024)
- [HK95]
Greg
Hjorth and Alexander
S. Kechris, Analytic equivalence relations and Ulm-type
classifications, J. Symbolic Logic 60 (1995),
no. 4, 1273–1300. MR 1367210
(96m:54068), http://dx.doi.org/10.2307/2275888
- [HK01]
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
(2002k:03076), http://dx.doi.org/10.4064/fm170-1-2
- [Kap69]
Irving
Kaplansky, Infinite abelian groups, Revised edition, The
University of Michigan Press, Ann Arbor, Mich., 1969. MR 0233887
(38 #2208)
- [Kop89]
Sabine
Koppelberg, Handbook of Boolean algebras. Vol. 1,
North-Holland Publishing Co., Amsterdam, 1989. Edited by J. Donald Monk and
Robert Bonnet. MR
991565 (90k:06002)
- [Mon05a]
Antonio Montalbán, Beyond the arithmetic, Ph.D. thesis, Cornell University, Ithaca, New York, 2005.
- [Mon05b]
Antonio
Montalbán, Up to equimorphism, hyperarithmetic is
recursive, J. Symbolic Logic 70 (2005), no. 2,
360–378. MR 2140035
(2006a:03063), http://dx.doi.org/10.2178/jsl/1120224717
- [Mun00]
James R. Munkres, Topology, second ed., Prentice-Hall Inc., Englewood Cliffs, N.J., 2000.
- [Sac90]
Gerald
E. Sacks, Higher recursion theory, Perspectives in
Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970
(92a:03062)
- [Sel91]
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
(95a:03057), http://dx.doi.org/10.1007/BF02018741
- [Sho93]
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
(95a:03002)
- [Sho06]
Richard
A. Shore, Invariants, Boolean algebras and
𝐴𝐶𝐴⁺₀, Trans. Amer. Math. Soc. 358 (2006), no. 3, 989–1014 (electronic). MR 2187642
(2006i:03013), http://dx.doi.org/10.1090/S0002-9947-05-03802-X
- [Sim99]
Stephen
G. Simpson, Subsystems of second order arithmetic,
Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999. MR 1723993
(2001i:03126)
- [Spe55]
Clifford
Spector, Recursive well-orderings, J. Symb. Logic
20 (1955), 151–163. MR 0074347
(17,570b)
- [AK00]
- 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 (2001k:03090)
- [Bar95]
- Ewan J. Barker, Back and forth relations for reduced abelian
-groups, Ann. Pure Appl. Logic 75 (1995), no. 3, 223-249. MR 1355134 (96j:03066)
- [BE71]
- Jon Barwise and Paul Eklof, Infinitary properties of abelian torsion groups, Ann. Math. Logic 2 (1970/1971), no. 1, 25-68. MR 0279180 (43:4906)
- [Cal04]
- Wesley Calvert, The isomorphism problem for classes of computable fields, Arch. Math. Logic 43 (2004), no. 3, 327-336. MR 2052886 (2005b:03103)
- [CCKM04]
- Wesley Calvert, D. Cummins, Julia F. Knight, and Sara Miller, Comparing classes of finite structures, Algebra and Logic 43 (2004), 374-392. MR 2135387 (2006e:03049)
- [CG01]
- 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 (electronic). MR 1804507 (2001k:03097)
- [CMS04]
- 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 (2005e:03020)
- [FH90]
- 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 (91b:03100)
- [FH91]
- -, Reverse mathematics and homeomorphic embeddings, Ann. Pure Appl. Logic 54 (1991), no. 3, 229-253. MR 1133006 (92m:03093)
- [Fria]
- Harvey Friedman, Metamathematics of comparability, Manuscript dated October 2001.
- [Frib]
- -, Metamathematics of Ulm theory, Manuscript dated November 2001.
- [FSS83]
- 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 (85i:03157)
- [Gao04]
- Su Gao, The homeomorphism problem for countable topological spaces, Topology Appl. 139 (2004), no. 1-3, 97-112. MR 2051099 (2005e:54037)
- [GK02]
- Sergei S. Goncharov and Julia Knight, Computable structure and antistructure theorems, Algebra Logika 41 (2002), no. 6, 639-681, 757. MR 1967769 (2004a:03047)
- [Hir94]
- Jeffry L. Hirst, Reverse mathematics and ordinal exponentiation, Ann. Pure Appl. Logic 66 (1994), no. 1, 1-18. MR 1263322 (95a:03078)
- [Hir00]
- -, Reverse mathematics and rank functions for directed graphs, Arch. Math. Logic 39 (2000), no. 8, 569-579. MR 1797809 (2001k:03134)
- [Hir05]
- Jeffry L Hirst, A survey of the reverse mathematics of ordinal arithmetic, Reverse Mathematics 2001, Lecture Notes in Logic, vol. 12, Association of Symbolic Logic, 2005. MR 2185437 (2006f:03024)
- [HK95]
- Greg Hjorth and Alexander S. Kechris, Analytic equivalence relations and Ulm-type classifications, J. Symbolic Logic 60 (1995), no. 4, 1273-1300. MR 1367210 (96m:54068)
- [HK01]
- -, Recent developments in the theory of Borel reducibility, Fund. Math. 170 (2001), no. 1-2, 21-52, Dedicated to the memory of Jerzy Los. MR 1881047 (2002k:03076)
- [Kap69]
- Irving Kaplansky, Infinite abelian groups, Revised edition, The University of Michigan Press, Ann Arbor, Mich., 1969. MR 0233887 (38:2208)
- [Kop89]
- Sabine Koppelberg, Handbook of Boolean algebras. Vol. 1, North-Holland Publishing Co., Amsterdam, 1989, Edited by J. Donald Monk and Robert Bonnet. MR 991565 (90k:06002)
- [Mon05a]
- Antonio Montalbán, Beyond the arithmetic, Ph.D. thesis, Cornell University, Ithaca, New York, 2005.
- [Mon05b]
- Antonio Montalbán, Up to equimorphism, hyperarithmetic is recursive, Journal of Symbolic Logic 70 (2005), no. 2, 360-378. MR 2140035 (2006a:03063)
- [Mun00]
- James R. Munkres, Topology, second ed., Prentice-Hall Inc., Englewood Cliffs, N.J., 2000.
- [Sac90]
- Gerald E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970 (92a:03062)
- [Sel91]
- V. L. Selivanov, The fine hierarchy and definable index sets, Algebra i Logika 30 (1991), no. 6, 705-725, 771. MR 1213731 (95a:03057)
- [Sho93]
- Richard A. Shore, On the strength of Fraïssé's conjecture, Logical methods (Ithaca, NY, 1992), Progr. Comput. Sci. Appl. Logic, vol. 12, Birkhäuser Boston, Boston, MA, 1993, pp. 782-813. MR 1281145 (95a:03002)
- [Sho06]
- -, Invariants, Boolean algebras and
, Trans. Amer. Math. Soc. 358 (2006), 965-987. MR 2187642 (2006i:03013)
- [Sim99]
- Stephen G. Simpson, Subsystems of second order arithmetic, Springer, 1999. MR 1723993 (2001i:03126)
- [Spe55]
- Clifford Spector, Recursive well-orderings, J. Symb. Logic 20 (1955), 151-163. MR 0074347 (17:570b)
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC (2000):
03F35,
03D45,
03C57,
03B30
Retrieve articles in all journals
with MSC (2000):
03F35,
03D45,
03C57,
03B30
Additional Information
Noam Greenberg
Affiliation:
Department of Mathematics, Notre Dame University, Notre Dame, Indiana 46556
Address at time of publication:
School of Mathematics, Statistics and Computer Science, Victoria University, Wellington, New Zealand
Email:
erlkoenig@nd.edu, greenberg@mcs.vuw.ac.nz
Antonio Montalbán
Affiliation:
Department of Mathematics, University of Chicago, Chicago, Illinois 60637
Email:
antonio@math.uchicago.edu
DOI:
http://dx.doi.org/10.1090/S0002-9947-07-04285-7
PII:
S 0002-9947(07)04285-7
Received by editor(s):
August 29, 2005
Posted:
October 23, 2007
Additional Notes:
We would like to thank our advisor Richard A. Shore for introducing us to questions that are discussed in this paper and for many useful conversations. Both authors were partially supported by NSF Grant DMS-0100035. This paper is part of the second author’s doctoral thesis.
Article copyright:
© Copyright 2007 American Mathematical Society
|