|
Invariants, Boolean algebras and ACA
Author(s):
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
Retrieve article in:
PDF DVI PostScript
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 .
References:
-
- [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:
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.
Copyright of article:
Copyright
2005,
Richard A. Shore
|