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

HTML articles powered by AMS MathViewer

- by Richard A. Shore PDF
- Trans. Amer. Math. Soc.
**358**(2006), 989-1014

## 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

- 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**, DOI 10.1090/conm/065/891245 - Csima, B., Montalban, A. and Shore, R.A., Boolean algebras, Tarski invariants and index sets,
*Notre Dame Journal of Formal Logic*, to appear. - C. C. Chang and H. J. Keisler,
*Model theory*, 2nd ed., Studies in Logic and the Foundations of Mathematics, vol. 73, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. MR**0532927** - 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** - 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** - 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 - Sergeĭ S. Goncharov,
*Schetnye bulevy algebry i razreshimost′*, Sibirskaya Shkola Algebry i Logiki. [Siberian School of Algebra and Logic], Nauchnaya Kniga (NII MIOONGU), Novosibirsk, 1996 (Russian, with Russian summary). MR**1469495** - John Doner and Wilfrid Hodges,
*Alfred Tarski and decidable theories*, J. Symbolic Logic**53**(1988), no. 1, 20–35. MR**929372**, DOI 10.2307/2274425 - 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**309729**, DOI 10.1016/0003-4843(72)90001-0 - Sabine Koppelberg,
*Handbook of Boolean algebras. Vol. 1*, North-Holland Publishing Co., Amsterdam, 1989. Edited by J. Donald Monk and Robert Bonnet. MR**991565** - A. S. Morozov,
*Strong constructivizability of countable saturated Boolean algebras*, Algebra i Logika**21**(1982), no. 2, 193–203 (Russian). MR**700992** - 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 - 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**, DOI 10.1007/978-3-662-02460-7 - Tarski, A., Arithmetical classes and types of Boolean algebras,
*Bulletin of the American Mathematical Society***55**, 63. - Vaught, R. L.,
*Topics in the Theory of Arithmetical Classes and Boolean Algebras*, Ph.D. Thesis, University of California, Berkeley. - White, W. M.,
*Characterizations for Computable Structures*, Ph.D. Thesis, Cornell University.

## Additional Information

**Richard A. Shore**- Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
- MR Author ID: 161135
- Email: shore@math.cornell.edu
- Received by editor(s): March 22, 2004
- Published electronically: April 13, 2005
- Additional Notes: The author was partially supported by NSF Grant DMS-0100035.
- © Copyright 2005 Richard A. Shore
- Journal: Trans. Amer. Math. Soc.
**358**(2006), 989-1014 - MSC (2000): Primary 03B25, 03B30, 03C57, 03D28, 03D35, 03D45, 03F35, 06E05
- DOI: https://doi.org/10.1090/S0002-9947-05-03802-X
- MathSciNet review: 2187642