Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Invariants, Boolean algebras and ACA$_{0}^{+}$

Author: Richard A. Shore
Journal: Trans. Amer. Math. Soc. 358 (2006), 989-1014
MSC (2000): Primary 03B25, 03B30, 03C57, 03D28, 03D35, 03D45, 03F35, 06E05
Published electronically: April 13, 2005
MathSciNet review: 2187642
Full-text PDF

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$_{0}$. 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$_{0}^{+}$. This system corresponds to the assertion that $X^{(\omega)}$(the arithmetic jump of $X$) exists for every set $X$. 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 $0^{(\omega)}$.

References [Enhancements On Off] (What's this?)

  • [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${nd}$ 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

Received by editor(s): March 22, 2004
Published electronically: April 13, 2005
Additional Notes: The author was partially supported by NSF Grant DMS-0100035.
Article copyright: © Copyright 2005 Richard A. Shore

American Mathematical Society