Invariants, Boolean algebras and ACA₀⁺

Shore, Richard

doi:10.1090/S0002-9947-05-03802-X

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.