|
Invariants, Boolean algebras and ACA
Author:
Richard A. Shore
Journal:
Trans. Amer. Math. Soc. 358 (2006), 989-1014
MSC (2000):
Primary 03B25, 03B30, 03C57, 03D28, 03D35, 03D45, 03F35, 06E05
Posted:
April 13, 2005
MathSciNet review:
2187642
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
Abstract: The sentences asserting the existence of invariants for mathematical structures are usually third order ones. We develop a general approach to analyzing the strength of such statements in second order arithmetic in the spirit of reverse mathematics. We discuss a number of simple examples that are equivalent to ACA . Our major results are that the existence of elementary equivalence invariants for Boolean algebras and isomorphism invariants for dense Boolean algebras are both of the same strength as ACA . This system corresponds to the assertion that (the arithmetic jump of ) exists for every set . These are essentially the first theorems known to be of this proof theoretic strength. The proof begins with an analogous result about these invariants on recursive (dense) Boolean algebras coding .
- [1987]
Andreas
R. Blass, Jeffry
L. Hirst, and Stephen
G. Simpson, Logical analysis of some theorems of combinatorics and
topological dynamics, Logic and combinatorics (Arcata, Calif., 1985)
Contemp. Math., vol. 65, Amer. Math. Soc., Providence, RI, 1987,
pp. 125–156. MR 891245
(88d:03113), http://dx.doi.org/10.1090/conm/065/891245
- [2005]
Csima, B., Montalban, A. and Shore, R.A., Boolean algebras, Tarski invariants and index sets, Notre Dame Journal of Formal Logic, to appear.
- [1977]
C.
C. Chang and H.
J. Keisler, Model theory, 2nd ed., North-Holland Publishing
Co., Amsterdam, 1977. Studies in Logic and the Foundations of Mathematics,
73. MR
0532927 (58 #27177)
- [1964]
Ju.
L. Eršov, Decidability of the elementary theory of
relatively complemented lattices and of the theory of filters, Algebra
i Logika Sem. 3 (1964), no. 3, 17–38 (Russian).
MR
0180490 (31 #4725)
- [1998]
Yu.
L. Ershov, S.
S. Goncharov, A.
Nerode, J.
B. Remmel, and V.
W. Marek (eds.), Handbook of recursive mathematics. Vol. 1,
Studies in Logic and the Foundations of Mathematics, vol. 138,
North-Holland, Amsterdam, 1998. Recursive model theory. MR 1673617
(99k:03003)
Yu.
L. Ershov, S.
S. Goncharov, A.
Nerode, J.
B. Remmel, and V.
W. Marek (eds.), Handbook of recursive mathematics. Vol. 2,
Studies in Logic and the Foundations of Mathematics, vol. 139,
North-Holland, Amsterdam, 1998. Recursive algebra, analysis and
combinatorics. MR 1673582
(99k:03004)
- [1983]
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
- [1997]
Sergei
S. Goncharov, Countable Boolean algebras and decidability,
Siberian School of Algebra and Logic, Consultants Bureau, New York, 1997.
MR
1444819 (98h:03044b)
- [1988]
John
Doner and Wilfrid
Hodges, Alfred Tarski and decidable theories, J. Symbolic
Logic 53 (1988), no. 1, 20–35. MR 929372
(89j:01048), http://dx.doi.org/10.2307/2274425
- [1972]
R.
Björn Jensen, The fine structure of the constructible
hierarchy, Ann. Math. Logic 4 (1972), 229–308;
erratum, ibid. 4 (1972), 443. With a section by Jack Silver. MR 0309729
(46 #8834)
- [1989]
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)
J.
Donald Monk and Robert
Bonnet (eds.), Handbook of Boolean algebras. Vol. 2,
North-Holland Publishing Co., Amsterdam, 1989. MR 991595
(90k:06003)
J.
Donald Monk and Robert
Bonnet (eds.), Handbook of Boolean algebras. Vol. 3,
North-Holland Publishing Co., Amsterdam, 1989. MR 991607
(90k:06004)
- [1982]
A.
S. Morozov, Strong constructivizability of countable saturated
Boolean algebras, Algebra i Logika 21 (1982),
no. 2, 193–203 (Russian). MR 700992
(85b:03052)
- [1999]
Stephen
G. Simpson, Subsystems of second order arithmetic,
Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999. MR 1723993
(2001i:03126)
- [1987]
Robert
I. Soare, Recursively enumerable sets and degrees,
Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study
of computable functions and computably generated sets. MR 882921
(88m:03003)
- [1949]
Tarski, A., Arithmetical classes and types of Boolean algebras, Bulletin of the American Mathematical Society 55, 63.
- [1954]
Vaught, R. L., Topics in the Theory of Arithmetical Classes and Boolean Algebras, Ph.D. Thesis, University of California, Berkeley.
- [2000]
White, W. M., Characterizations for Computable Structures, Ph.D. Thesis, Cornell University.
- [1987]
- Blass, A. R., Hirst, J. L. and Simpson, S. G., Logical analysis of some theorems of combinatorics and topological dynamics, in Logic and Combinatorics, S. G. Simpson, ed., Contemporary Mathematics, American Mathematical Society, Providence, 125-156. MR 0891245 (88d:03113)
- [2005]
- Csima, B., Montalban, A. and Shore, R.A., Boolean algebras, Tarski invariants and index sets, Notre Dame Journal of Formal Logic, to appear.
- [1977]
- Chang, C. C. and Keisler, H. J., Model Theory 2
ed., North Holland, Amsterdam. MR 0532927 (58:27177)
- [1964]
- Ershov, Yu. L., Decidability of the elementary theory of distributive lattices with relative complements and the theory of filters, Algebra i Logika 3, 17-38. MR 0180490 (31:4725)
- [1998]
- Ershov, Yu. L., Goncharov, S. S., Nerode, A. and Remmel, J. B., eds., Handbook of Recursive Mathematics, Studies in Logic and the Foundations of Mathematics, vols. 138-139, Elsevier, Amsterdam, vols. 1-2. MR 1673617 (99k:03003); MR 1673582 (99k:03004)
- [1983]
- Friedman, H., Simpson, S. G. and Smith, R., Countable algebra and set existence axioms, Annals of Pure and Applied Logic 25, 141-181. MR 0725732 (85i:03157)
- [1997]
- Goncharov, S. S., Countable Boolean Algebras and Decidability, Consultants Bureau, New York. MR 1444819 (98h:03044b)
- [1988]
- Doner, J. and Hodges, W., Alfred Tarski and decidable theories, The Journal of Symbolic Logic 53, 20-35. MR 0929372 (89j:01048)
- [1972]
- Jensen, R. B., The fine structure of the constructible hierarchy, Annals of Mathematical Logic 4, 229-308. MR 0309729 (46:8834)
- [1989]
- Monk, J. D., ed., Handbook of Boolean Algebras, North Holland, Amsterdam, vols. 1-3. MR 0991565 (90k:06002); MR 0991595 (90k:06003); MR 0991607 (90k:06004)
- [1982]
- Morozov, A. S., Strong constructivizability of countable saturated Boolean algebras, Algebra i Logika 21, 193-203; English version in Algebra and Logic 21, 130-137. MR 0700992 (85b:03052)
- [1999]
- Simpson, S. G., Subsystems of Second Order Arithmetic, Springer, Berlin. MR 1723993 (2001i:03126)
- [1987]
- Soare, R. I., Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin. MR 0882921 (88m:03003)
- [1949]
- Tarski, A., Arithmetical classes and types of Boolean algebras, Bulletin of the American Mathematical Society 55, 63.
- [1954]
- Vaught, R. L., Topics in the Theory of Arithmetical Classes and Boolean Algebras, Ph.D. Thesis, University of California, Berkeley.
- [2000]
- White, W. M., Characterizations for Computable Structures, Ph.D. Thesis, Cornell University.
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC (2000):
03B25,
03B30,
03C57,
03D28,
03D35,
03D45,
03F35,
06E05
Retrieve articles in all journals
with MSC (2000):
03B25,
03B30,
03C57,
03D28,
03D35,
03D45,
03F35,
06E05
Additional Information
Richard A. Shore
Affiliation:
Department of Mathematics, Cornell University, Ithaca, New York 14853
Email:
shore@math.cornell.edu
DOI:
http://dx.doi.org/10.1090/S0002-9947-05-03802-X
PII:
S 0002-9947(05)03802-X
Received by editor(s):
March 22, 2004
Posted:
April 13, 2005
Additional Notes:
The author was partially supported by NSF Grant DMS-0100035.
Article copyright:
© Copyright 2005 Richard A. Shore
|