Parameter-free schemes in second-order arithmetic

PDF   Bibtex

V. Gitman, “Parameter-free schemes in second-order arithmetic,” Manuscript.

The strength of a second-order arithmetic theory depends mostly on the amount of comprehension that the theory admits. A comprehension scheme specifies which formulas give collections that turn out to be sets in the model. At the lower extreme, the second-order theory ${\rm ACA}_0$ includes comprehension for all first-order formulas and at the higher extreme, full second-order arithmetic ${\rm Z}_2$ includes comprehension for all (second-order) formulas. In between, we have $\Sigma^1_n$-comprehension schemes for second-order formulas of complexity $\Sigma^1_n$ ($n$ alternations of set quantifiers followed by a first-order formula). A precise formulation of these comprehension schemes should mention that the specified formulas are allowed to use set parameters from the model. But how significant really are parameters in comprehension? What if we formulate the comprehension schemes without parameters, do we get equivalent theories, perhaps, equiconsistent theories?

Let ${\rm Z}_2^{-p}$ be the version of full second-order arithmetic ${\rm Z}_2$, where we do not allow parameters in the comprehension scheme. Friedman showed in [1] (Lemma 3.1.7) that given a model of ${\rm Z}_2^{-p}$, we can appropriately restrict its sets to get a model of ${\rm Z}_2$. Thus, the theories ${\rm Z}_2$ and ${\rm Z}_2^{-p}$ are equiconsistent. In a recent work [2], Lyubetsky and Kanovei separated the theories ${\rm Z}_2$ and ${\rm Z}_2^{-p}$ by constructing models of ${\rm Z}_2^{-p}$ with various failures of comprehension with parameters. They constructed a model of ${\rm Z}_2^{-p}$ in which the sets were not even closed under complement, showing that comprehension without parameters does not even give comprehension with parameters for $\Sigma^0_0$-assertions. They next considered whether it was possible to have a model of ${\rm Z}_2^{-p}$ with enough comprehension with parameters to carry out most standard constructions, but still have comprehension with parameters fail somewhere above. They argued that a reasonable amount of comprehension with parameters for general mathematical purposes is the $\Sigma^1_2$-comprehension scheme and constructed a model of ${\rm Z}_2^{-p}$ with the $\Sigma^1_2$-comprehension scheme and a failure of $\Sigma^1_4$-comprehension. The model was constructed in a forcing extension by a (non-linear) tree iteration of Sacks forcing. Lyubetsky and Kanovei asked whether the result can be improved to obtain the optimal failure of $\Sigma^1_3$-comprehension [2] (Problem 8.2).

In this article, I answer their question positively by constructing a model with the required properties, similarly to how the model of [2] was constructed, in a forcing extension by a tree iteration of Jensen's forcing. Jensen's forcing is a subposet of Sacks forcing constructed in $L$ using the $\diamondsuit$-principle. Jensen's forcing has the ccc and adds a unique generic real whose singleton is $\Pi^1_2$-definable. A similar forcing can be constructed in any universe in which the $\diamondsuit$-principle holds, not just in $L$, and we retain its properties except for, possibly, $\Pi^1_2$-definability of the generic singleton. Jensen originally introduced the forcing because it gives a forcing extension of $L$ in which there is a $\Pi^1_2$-definable non-constructible singleton real [3].

Theorem: It is consistent that there is a model of ${\rm Z}_2^{-p}$ together with $\Sigma^1_2$-comprehension and a failure of $\Sigma^1_3$-comprehension.

If the first-order part of a second-order arithmetic model satisfies ${\rm PA}$, then via Gödel's pairing function, we can view any set in the model as a collection of $n$-tuples, for some $n\lt\omega$, of elements of the model. Among these collections are orderings of the first-order domain of the model, which the model believes are well-orders. In a model of ${\rm Z}_2$, these well-orders are comparable in that given any two of them, there is a set coding an isomorphism of one of them with an initial segment of the other. Using coding, a model of ${\rm Z}_2$ can construct an initial segment of the $L$-hierarchy along any of its well-orders, and these initial segments are similarly coherent (for details of the construction, see [4] (Chapter VII)). We will call a real of a model of ${\rm Z}_2$ constructible if it appears in an initial segment of the $L$-hierarchy of the model. Similarly, in a model of ${\rm Z}_2^{-p}$, we can show that any two definable without parameters well-orders are comparable and we can construct an initial segment of the $L$-hierarchy along any such well-order so that the resulting structures are coherent. We will call a real of a model of ${\rm Z}_2^{-p}$ constructible if it appears in an initial segment of the $L$-hierarchy constructed along a definable without parameters well-order.

The theory ${\rm Z}_2$ can be further strengthened by adding the choice scheme ${\rm AC}$, which is a set choice principle asserting for every second-order formula $\varphi(n,X,A)$ (with set parameter $A$) that if for every $n$, there is a set $X$ such that $\varphi(n,X,A)$ holds, then there is a single set $Y$ whose $n$-th slice $Y_n$ is a witness for $n$. It is not difficult to see that the scheme ${\rm AC}$ actually implies ${\rm Z}_2$ over ${\rm ACA}_0$. The collection of the constructible reals of a model of ${\rm Z}_2$ satisfies ${\rm Z}_2+{\rm AC}$ (see [4], Section VII.6), giving that the two theories are equiconsistent. Friedman's sub-collection of a model of ${\rm Z}_2^{-p}$, which he showed satisfies ${\rm Z}_2$, was precisely the constructible reals of the model, as defined above, coming from the initial segments of the $L$-hierarchy constructed along definable without parameters well-orders. His argument additionally showed that the collection of the constructible reals satisfies ${\rm AC}$. Thus, the theories ${\rm Z}_2^{-p}$ and ${\rm Z}_2+{\rm AC}$ are equiconsistent.

Let ${\rm AC}^{-p}$ denote the parameter-free choice scheme. Because standard arguments that the choice scheme ${\rm AC}$ implies comprehension over ${\rm ACA}_0$ require parameters, it is probably not the case that ${\rm AC}^{-p}$ implies ${\rm Z}_2^{-p}$ over ${\rm ACA}_0$. The reals of the Feferman-Lévy model of ${\rm ZF}$ (a symmetric submodel of a forcing extension), in which $\omega_1^L$ is countable for every $n\lt\omega$ and $\omega_\omega^L$ is the first uncountable cardinal [5], is a model of ${\rm Z}_2$ in which ${\rm AC}^{-p}$ fails. In this model (the code of) $L_{\omega_n^L}$ exists for every $n\lt\omega$, but (the code of) $L_{\omega_\omega^L}$ does not exist, because $\omega_\omega^L$ is uncountable in the Feferman-Lévy model, and therefore cannot be coded by a real. Guzicki constructed a model of ${\rm ZF}$ (again a symmetric submodel of a forcing extension) whose reals are a model satisfying ${\rm Z}_2+{\rm AC}^{-p}$ in which ${\rm AC}$ fails [6], separating the two principles. Recently Lyubetsky and Kanovei showed how to obtain these results involving ${\rm AC}^{-p}$ starting with a model of ${\rm Z}_2$ instead of ${\rm ZFC}$ [7].

Vladimir Kanovei suggested that I should try to construct a model of ${\rm Z}_2^{-p}+{\rm AC}^{-p}$ together with $\Sigma^1_2$-comprehension in which there is a failure of $\Sigma^1_3$-comprehension. However, the best I was able to get is the following theorem.

Theorem: It is consistent that there is a model of ${\rm Z}_2^{-p}+{\rm AC}^{-p}$ together with $\Sigma^1_2$-comprehension in which there is a failure of $\Sigma^1_4$-comprehension.

A set existence principle closely related to the choice scheme is the collection scheme ${\rm Coll}$, which asserts for every second-order formula $\varphi(n,X,A)$ (with set parameter $A$) that if for every $n$, there is a set $X$ such that $\varphi(n,X,A)$ holds, then there is a set $Y$ whose slices are a collecting set for the witnesses $X$. A slice of $Y$ may not be one of the witnesses and a witness for $n$ may be on some slice $m\neq n$. It is easy to see that over ${\rm Z}_2$, ${\rm Coll}$ is equivalent to ${\rm AC}$. Over ${\rm ACA}_0$, ${\rm Coll}$ implies ${\rm Z}_2$, and hence, over ${\rm ACA}_0$, ${\rm Coll}$ is equivalent to ${\rm AC}$. Let ${\rm Coll}^{-p}$ be the parameter-free collection scheme.

Theorem: It is consistent that there is a model of ${\rm Z}_2^{-p}+{\rm Coll}^{-p}$ together with $\Sigma^1_2$-comprehension in which there is a failure of $\Sigma^1_4$-comprehension and a failure of ${\rm AC}^{-p}$.

Thus, we get:

Theorem: The schemes ${\rm Coll}^{-p}$ and ${\rm AC}^{-p}$ are not equivalent over $\rm Z_2^{-p}$.

References

  1. H. Friedman, “On the necessary use of abstract set theory,” Adv. in Math., vol. 41, no. 3, pp. 209–280, 1981. Available at: https://doi.org/10.1016/0001-8708(81)90021-9
  2. V. Kanovei and V. Lyubetsky, “The parameterfree Comprehension does not imply the full Comprehension in the 2nd order Peano arithmetic,” Manuscript.
  3. R. Jensen, “Definable sets of minimal degree,” in Mathematical logic and foundations of set theory (Proc. Internat. Colloq., Jerusalem, 1968), North-Holland, Amsterdam, 1970, pp. 122–128.
  4. S. G. Simpson, Subsystems of second order arithmetic, Second. Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009, p. xvi+444.
  5. A. Lévy, “Definability in axiomatic set theory. II,” in Mathematical Logic and Foundations of Set Theory (Proc. Internat. Colloq., Jerusalem, 1968), North-Holland, Amsterdam, 1970, pp. 129–145.
  6. W. Guzicki, “On weaker forms of choice in second order arithmetic,” Fund. Math., vol. 93, no. 2, pp. 131–144, 1976.
  7. V. Kanovei and V. Lyubetsky, “On the Significance of Parameters in the Choice and Collection Schemata in the 2nd Order Peano Arithmetic,” Mathematics, vol. 11, no. 3, p. 726, 2023.