Parameter-free schemes in second-order arithmetic

Victoria Gitman (CUNY Graduate Center)

Thu Feb 6, 19:00-20:00 (5 weeks ago)

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} Σn1\Sigma^1_n-CA{\rm CA} asserts for a Σn1\Sigma^1_n-formula φ(n,A)\varphi(n,A), with a set parameter AA, that the collection it determines is a set. The \emph{choice scheme} Σn1\Sigma^1_n-AC{\rm AC} asserts for a Σn1\Sigma^1_n-formula φ(n,X,A)\varphi(n,X,A) that if for every number nn there is a set XX such that φ(n,X,A)\varphi(n,X,A) holds, then there is a single set YY such that its slice YnY_n is a witness for nn. The \emph{collection scheme} Σn1\Sigma^1_n-Coll{\rm Coll} asserts more generally that among the slices of YY, there is a witness for every nn. The full comprehension scheme for all second-order assertions is denoted by Z2{\rm Z}_2, the full choice scheme by AC{\rm AC}, and the full collection scheme by Coll{\rm Coll}. Although the theories Z2{\rm Z}_2+AC{\rm AC} and Z2{\rm Z}_2 are equiconsistent, Feferman and L\' evy showed that AC{\rm AC} is independent of Z2{\rm Z}_2. It is also not difficult to see that Coll{\rm Coll} implies Z2{\rm Z}_2 over Σ01\Sigma^1_0-CA{\rm CA}, and hence that Coll{\rm Coll} implies AC{\rm AC} over Σ01\Sigma^1_0-CA{\rm CA}.

In this talk, I will explore how significant the inclusion of set parameters is in the second-order set-existence schemes. Let Z2p{\rm Z}_2^{-p}, ACp{\rm AC}^{-p}, and Collp{\rm Coll}^{-p} denote the respective parameter-free schemes. H. Friedman showed that the theories Z2{\rm Z}_2 and Z2p{\rm Z}_2^{-p} are equiconsistent and recently Kanovei and Lyubetsky showed that the theory Z2p{\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 Z2p{\rm Z}_2^{-p} in which Σ21\Sigma^1_2-CA{\rm CA} holds, but Σ41\Sigma^1_4-CA{\rm CA} fails. They asked whether one can construct a model of Z2p{\rm Z}_2^{-p} in which Σ21\Sigma^1_2-CA{\rm CA} holds, but there is an optimal failure of Σ31\Sigma^1_3-CA{\rm CA}. I will answer their question by constructing such a model. I will also construct a model of Z2p+Collp{\rm Z}_2^{-p}+{\rm Coll}^{-p} in which Σ21\Sigma^1_2-CA{\rm CA} holds, but ACp{\rm AC}^{-p} fails, thus showing that Collp{\rm Coll}^{-p} does not imply ACp{\rm AC}^{-p} even over Σ21\Sigma^1_2-CA{\rm CA}.

logic

Audience: researchers in the topic


Online logic seminar

Series comments: Description: Seminar on all areas of logic

Organizer: Wesley Calvert*
*contact for this listing

Export talk to
This website uses cookies to improve your experience.