Parameter-free schemes in second-order arithmetic

Abstract: Second-order arithmetic has two types of objects: numbers and set of numbers, which we think of as the reals. Which sets (reals) have to exist in a model of second-order arithmetic is determined by the various set-existence axioms. These usually come in the form of schemes, of which the most common are the comprehension scheme, the choice scheme, and the collection scheme. The \emph{comprehension scheme} $\Sigma^1_n$-${\rm CA}$ asserts for a $\Sigma^1_n$-formula $\varphi(n,A)$, with a set parameter $A$, that the collection it determines is a set. The \emph{choice scheme} $\Sigma^1_n$-${\rm AC}$ asserts for a $\Sigma^1_n$-formula $\varphi(n,X,A)$ that if for every number $n$ there is a set $X$ such that $\varphi(n,X,A)$ holds, then there is a single set $Y$ such that its slice $Y_n$ is a witness for $n$. The \emph{collection scheme} $\Sigma^1_n$-${\rm Coll}$ asserts more generally that among the slices of $Y$, there is a witness for every $n$. The full comprehension scheme for all second-order assertions is denoted by ${\rm Z}_2$, the full choice scheme by ${\rm AC}$, and the full collection scheme by ${\rm Coll}$. Although the theories ${\rm Z}_2$+${\rm AC}$ and ${\rm Z}_2$ are equiconsistent, Feferman and L\' evy showed that ${\rm AC}$ is independent of ${\rm Z}_2$. It is also not difficult to see that ${\rm Coll}$ implies ${\rm Z}_2$ over $\Sigma^1_0$-${\rm CA}$, and hence that ${\rm Coll}$ implies ${\rm AC}$ over $\Sigma^1_0$-${\rm CA}$.

In this talk, I will explore how significant the inclusion of set parameters is in the second-order set-existence schemes. Let ${\rm Z}_2^{-p}$, ${\rm AC}^{-p}$, and ${\rm Coll}^{-p}$ denote the respective parameter-free schemes. H. Friedman showed that the theories ${\rm Z}_2$ and ${\rm Z}_2^{-p}$ are equiconsistent and recently Kanovei and Lyubetsky showed that the theory ${\rm Z}_2^{-p}$ can have extremely badly behaved models in which the sets aren't even closed under complement. They also constructed a more ``nice" model of ${\rm Z}_2^{-p}$ in which $\Sigma^1_2$-${\rm CA}$ holds, but $\Sigma^1_4$-${\rm CA}$ fails. They asked whether one can construct a model of ${\rm Z}_2^{-p}$ in which $\Sigma^1_2$-${\rm CA}$ holds, but there is an optimal failure of $\Sigma^1_3$-${\rm CA}$. I will answer their question by constructing such a model. I will also construct a model of ${\rm Z}_2^{-p}+{\rm Coll}^{-p}$ in which $\Sigma^1_2$-${\rm CA}$ holds, but ${\rm AC}^{-p}$ fails, thus showing that ${\rm Coll}^{-p}$ does not imply ${\rm AC}^{-p}$ even over $\Sigma^1_2$-${\rm CA}$.

logic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic