1 Introduction
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
$\mathrm {ACA}_0$
includes comprehension for all first-order formulas and at the higher extreme, full second-order arithmetic
$\mathrm {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
$\mathrm {Z}_2^{-p}$
be the version of full second-order arithmetic
$\mathrm {Z}_2$
, where we do not allow parameters in the comprehension scheme. Friedman showed in [Reference Friedman3, Lemma 3.1.7] that given a model of
$\mathrm {Z}_2^{-p}$
, we can appropriately restrict its sets to get a model of
$\mathrm {Z}_2$
. Thus, the theories
$\mathrm {Z}_2$
and
$\mathrm {Z}_2^{-p}$
are equiconsistent. In a recent work [Reference Kanovei and Lyubetsky8], Lyubetsky and Kanovei separated the theories
$\mathrm {Z}_2$
and
$\mathrm {Z}_2^{-p}$
by constructing models of
$\mathrm {Z}_2^{-p}$
with various failures of comprehension with parameters. They constructed a model of
$\mathrm {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
$\mathrm {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
$\mathrm {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 [Reference Kanovei and Lyubetsky8, Problem 8.2].
In this article, we answer their question positively by constructing a model with the required properties, similarly to how the model of [Reference Kanovei and Lyubetsky8] 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.Footnote
1
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 [Reference Jensen5].
Theorem 1.1. It is consistent that there is a model of
$\mathrm {Z}_2^{-p}$
together with
$\Sigma ^1_2$
-comprehension and a failure of
$\Sigma ^1_3$
-comprehension.
Theorem 1.1 is proved in Section 3.
If the first-order part of a second-order arithmetic model satisfies
$\mathrm {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<\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
$\mathrm {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
$\mathrm {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 [Reference Simpson10], Chapter VII). We will call a real of a model of
$\mathrm {Z}_2$
constructible if it appears in an initial segment of the L-hierarchy of the model. Similarly, in a model of
$\mathrm {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
$\mathrm {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
$\mathrm {Z}_2$
can be further strengthened by adding the choice scheme
$\mathrm {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
$\mathrm {AC}$
actually implies
$\mathrm {Z}_2$
over
$\mathrm {ACA}_0$
. The collection of the constructible reals of a model of
$\mathrm {Z}_2$
satisfies
$\mathrm {Z}_2+\mathrm {AC}$
(see [Reference Simpson10, Section VII.6]), giving that the two theories are equiconsistent. Friedman’s sub-collection of a model of
$\mathrm {Z}_2^{-p}$
, which he showed satisfies
$\mathrm {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
$\mathrm {AC}$
. Thus, the theories
$\mathrm {Z}_2^{-p}$
and
$\mathrm {Z}_2+\mathrm {AC}$
are equiconsistent.
Let
$\mathrm {AC}^{-p}$
denote the parameter-free choice scheme. Because standard arguments that the choice scheme
$\mathrm {AC}$
implies comprehension over
$\mathrm {ACA}_0$
require parameters, it is probably not the case that
$\mathrm {AC}^{-p}$
implies
$\mathrm {Z}_2^{-p}$
over
$\mathrm {ACA}_0$
. The reals of the Feferman–Lévy model of
$\mathrm {ZF}$
(a symmetric submodel of a forcing extension), in which
$\omega _1^L$
is countable for every
$n<\omega $
and
$\omega _\omega ^L$
is the first uncountable cardinal [Reference Lévy9], is a model of
$\mathrm {Z}_2$
in which
$\mathrm {AC}^{-p}$
fails. In this model (the code of)
$L_{\omega _n^L}$
exists for every
$n<\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
$\mathrm {ZF}$
(again a symmetric submodel of a forcing extension) whose reals are a model satisfying
$\mathrm {Z}_2+\mathrm {AC}^{-p}$
in which
$\mathrm {AC}$
fails [Reference Guzicki4], separating the two principles.Footnote
2
Vladimir Kanovei suggested to try to construct a model of
$\mathrm {Z}_2^{-p}+\mathrm {AC}^{-p}$
together with
$\Sigma ^1_2$
-comprehension in which there is a failure of
$\Sigma ^1_3$
-comprehension. However, the best we were able to get is the following theorem.
Theorem 1.2. It is consistent that there is a model of
$\mathrm {Z}_2^{-p}+\mathrm {AC}^{-p}$
together with
$\Sigma ^1_2$
-comprehension in which there is a failure of
$\Sigma ^1_4$
-comprehension.
Theorem 1.3 is proved in Section 5.
A set existence principle closely related to the choice scheme is the collection scheme
$\mathrm {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
$\mathrm {Z}_2$
,
$\mathrm {Coll}$
is equivalent to
$\mathrm {AC}$
. Over
$\mathrm {ACA}_0$
,
$\mathrm {Coll}$
implies
$\mathrm {Z}_2$
, and hence, over
$\mathrm {ACA}_0$
,
$\mathrm {Coll}$
is equivalent to
$\mathrm {AC}$
. Let
$\mathrm {Coll}^{-p}$
be the parameter-free collection scheme. I separate the schemes
$\mathrm {Coll}^{-p}$
and
$\mathrm {AC}^{-p}$
over
$\mathrm {Z}_2^{-p}$
.
Theorem 1.3. It is consistent that there is a model of
$\mathrm {Z}_2^{-p}+\mathrm {Coll}^{-p}$
together with
$\Sigma ^1_2$
-comprehension in which there is a failure of
$\Sigma ^1_4$
-comprehension and a failure of
$\mathrm {AC}^{-p}$
.
Theorem 1.3 is proved in Section 5. Thus, we get
Theorem 1.4. The schemes
$\mathrm {Coll}^{-p}$
and
$\mathrm {AC}^{-p}$
are not equivalent over
${\mathrm {Z}}_2^{-p}$
.
2 Preliminaries
2.1 Second-order arithmetic
Second-order arithmetic has two types of objects: numbers and sets of numbers, which we think of as the reals of the model. It is formalized in a two-sorted logic, which has two separate sorts of variables and corresponding quantifiers. By convention, we use lower-case variables for numbers and upper-case variables for sets. The language of second-order arithmetic consists of the language of
$\mathrm {PA}$
together with a membership relation
$\in $
used to determine which numbers belong to which sets. A model of second-order arithmetic is a structure
$\mathcal M=\langle M,+,\times ,<,0,1,\in ,\mathcal S\rangle $
, where M is the universe of numbers and
$\mathcal S$
is the universe of sets. We associate each set A with a subset of M consisting of those
$a\in M$
such that
$a\in A$
. This interpretation is formalized by the extensionality axiom for sets. The second-order arithmetic theories we consider include the
$\mathrm {PA}$
axioms for the first-order part together with the extensionality axiom for sets and a single induction axiom
$$ \begin{align*}\forall X\, ((0\in X\wedge \forall n\, (n\in X\rightarrow n+1\in X))\rightarrow \forall n\, n\in X)\end{align*} $$
asserting that induction holds for every set. The theories then differ by which sets are posited to exist. The most common set existence axioms are the comprehension schemes. The
$\Sigma ^1_n$
-comprehension scheme,
$\Sigma ^1_n$
-
$\mathrm {CA}$
, asserts that every
$\Sigma ^1_n$
-formula with parameters defines a set. Formally,
$\Sigma ^1_n$
-
$\mathrm {CA}$
asserts for every
$\Sigma ^1_n$
-formula
$\varphi (n,A)$
, with set parameter A, that there is a set
$X\in \mathcal S$
such that
$X=\{n\mid \varphi (n,A)\}$
.Footnote
3
One of the strongest second-order arithmetic theories is full second-order arithmetic
$\mathrm {Z}_2$
, which includes the comprehension scheme asserting that every second-order formula with parameters defines a set, namely
$\Sigma ^1_n$
-
$\mathrm {CA}$
for every
$n<\omega $
. If we exclude parameters from the comprehension scheme, we get the theory
$\mathrm {Z}_2^{-p}$
, which is the focus of this article.
Other common set existence principles are the set choice principles. The choice scheme
$\mathrm {AC}$
asserts for every second-order formula
$\varphi (n,X,A )$
that if
$\forall n\exists X\,\varphi (n,X)$
holds, then there is a set Y such that
$\forall n\,\varphi (n,Y_n,A)$
holds, where
$$ \begin{align*}Y_n=\{m\mid \langle m,n \rangle\in Y\}\end{align*} $$
is the n-th slice of Y. We will denote by
$\mathrm {AC}^{-p}$
the parameter-free choice scheme. Closely related to the choice scheme is the collection scheme, which asserts for every second-order formula
$\varphi (n,X,A )$
that if
$\forall n\exists X\,\varphi (n,X)$
holds, then there is a set Y such that
$\forall n\exists m\,\varphi (n,Y_m,A)$
holds. We will denote by
$\mathrm {Coll}^{-p}$
the parameter-free collection scheme.
2.2 Tree iterations of Jensen’s forcing
Recall that a perfect tree is a subtree of
$2^{{<}\omega }$
in which every node has a splitting node above it. Also recall that given a tree T and a node
$s\in T$
, we denote by
$T_s$
the subtree of T consisting of all nodes compatible with s. If T and S are perfect trees whose intersection includes a perfect tree, then there is a maximal such perfect tree, which we call the meet of T and S and denote by
$T\wedge S$
. A perfect poset
$\mathbb {P}$
is a collection of perfect trees ordered by the subtree relation satisfying the following closure properties:
-
(1)
$(2^{{<}\omega })_s\in \mathbb {P}$
for every
$s\in 2^{{<}\omega }$
, -
(2) if
$T,S\in \mathbb {P}$
, then
$T\wedge S\in \mathbb {P}$
, -
(3) finite unions of trees in
$\mathbb {P}$
are in
$\mathbb {P}$
.
Perfect posets are subposets of Sacks forcing and they share many of the properties of Sacks forcing such as that the generic filter is determined by a single generic real that is precisely the intersection of all the trees in the generic filter. While Sacks forcing is the largest perfect poset, the smallest perfect poset, which I will denote by
$\mathbb {P}_{\text {min}}$
, is the closure under finite unions of the collection of all trees
$(2^{{<}\omega })_s$
for some
$s\in 2^{{<}\omega }$
(it is easy to see that this collection is closed under meets).
Given a perfect poset
$\mathbb {P}$
, let
$\mathbb {Q}(\mathbb {P})$
be the poset whose elements are pairs
$(T,n)$
, where
$T\in \mathbb {P}$
and
$n<\omega $
, ordered so that
$(S,m)\leq (T,n)$
whenever S is a subtree of T such that S and T agree up to level n and
$m\geq n$
. Forcing with
$\mathbb {Q}(\mathbb {P})$
adds a generic perfect tree. Let
$\mathbb {Q}(\mathbb {P})^{{<}\omega }$
be the finite-support
$\omega $
-length product of the
$\mathbb {Q}(\mathbb {P})$
and let
$G\subseteq \mathbb {Q}(\mathbb {P})^{{<}\omega }$
be V-generic. In the forcing extension
$V[G]$
, let
$\{\mathscr T_n\mid n<\omega \}$
be the
$\omega $
-many generic perfect trees added by G. Finally, let
$\mathbb {P}^*$
be the closure of
$\mathbb {P}$
and
$\{\mathscr T_n\mid n<\omega \}$
under finite meets and unions. In
$V[G]$
, the perfect poset
$\mathbb {P}^*$
has the following two key properties:
-
(1)
$\{\mathscr T_n\mid n<\omega \}$
is a maximal antichain, -
(2) every maximal antichain of
$\mathbb {P}$
from V remains maximal in
$\mathbb {P}^*$
(see [Reference Friedman, Gitman and Kanovei2] for details). Let us now work in the constructible universe L. Let
$\vec D=\langle D_\xi \mid \xi <\omega _1\rangle $
be the canonical
$\diamondsuit $
-sequence obtained by letting
$D_{\alpha +1}$
be the least counterexample if one exists. Let us call a countable level
$L_\alpha $
of L suitable if
$$ \begin{align*}L_\alpha\models\mathrm{ZFC}^-+P(\omega)\text{ exists}.\end{align*} $$
For example, the collapse of any countable elementary substructure of
$L_{\omega _2}$
is suitable. Observe also that, by canonicity of the
$\diamondsuit $
-sequence
$\vec D$
, if
$L_\alpha $
is suitable and
$\delta =(\omega _1)^{L_\alpha }$
, then
$\vec D\upharpoonright \delta \in L_\alpha $
. We will use suitable models
$L_\alpha $
handed to us by
$\vec D$
to construct Jensen’s forcing
$\mathbb J$
in
$\omega _1$
-many steps as a continuous chain of length
$\omega _1$
of countable perfect posets. Let
$\mathbb {P}_0=\mathbb {P}_{\text {min}}$
. At limit ordinals, we will take unions. So suppose we have constructed a countable perfect poset
$\mathbb {P}_\xi $
. We let
$\mathbb {P}_{\xi +1}=\mathbb {P}_\xi $
unless the following happens. Suppose that
$D_\xi $
codes a suitable model
$L_{\alpha _\xi }$
such that
$\mathbb {P}_\xi \in L_{\alpha _\xi }$
and
$(\omega _1)^{L_{\alpha _\xi }}=\xi $
. Then we let
$G_\xi $
be the L-least
$L_{\alpha _\xi }$
-generic filter for
$\mathbb {Q}(\mathbb {P}_\xi )^{{<}\omega }$
and let
$\mathbb {P}_{\xi +1}=\mathbb {P}_\xi ^*$
as constructed in
$L_{\alpha _\xi }[G_\xi ]$
. Notice that by our observations above, we seal maximal antichains ensuring that the resulting union poset will have the ccc. We let
$\mathbb J=\bigcup _{\xi <\omega _1}\mathbb {P}_\xi $
. Jensen showed that the poset
$\mathbb J$
has the ccc and adds a unique generic real, whose singleton is
$\Pi ^1_2$
-definable [Reference Jensen5]. Products and iterations of Jensen’s forcing also turned out to have “unique generics” properties.
Lyubetsky and Kanovei showed that in a forcing extension by a finite-support
$\alpha $
-length product of Jensen’s forcing the only L-generic reals for
$\mathbb J$
are those explicitly added by the (
$\alpha $
-many) slices of the generic filter [Reference Kanovei and Lyubetsky6].
As mentioned in footnote 1, a forcing with the same properties as
$\mathbb J$
, minus the low complexity of the generic singleton, can be constructed in any model of the
$\diamondsuit $
-principle. In particular, since ccc posets of size
$\omega _1$
preserve the
$\diamondsuit $
-principle, any forcing extension of L by
$\mathbb J$
continues to satisfy the
$\diamondsuit $
-principle, and we can construct a Jensen-like poset again in it. In this way, we can make sense of iterating Jensen’s forcing and define finite n-length iterations
$\mathbb J_n$
of
$\mathbb J$
. The iterations
$\mathbb J_n$
are constructed, analogously to Jensen’s forcing, as a chain of length
$\omega _1$
of iterations
$\mathbb {P}_n^{\xi }=\mathbb {Q}_0^\xi * \dot {\mathbb {Q}}_1^\xi *\cdots *\dot {\mathbb {Q}}_{n-1}^\xi $
for
$\xi <\omega _1$
, where
$\mathbb {P}_0^\xi $
is a countable perfect poset, and for
$i<n-1$
,
$$ \begin{align*}\mathop{1\hskip-2.5pt \mathrm{l}}_{\mathbb{P}_n^\xi\upharpoonright i}\Vdash \dot{\mathbb{Q}}_{i}^{\xi}\text{ is a countable perfect poset}. \end{align*} $$
We start with
$\mathbb {P}^0_n$
in which
$\mathbb {Q}^0_0=\mathbb {P}_{\text {min}}$
and for
$i<n-1$
,
$\dot {\mathbb {Q}}^0_i=\check {\mathbb {P}}_{\text {min}}$
. At stages
$\xi +1$
at which the canonical
$\diamondsuit $
-sequence
$\vec D$
codes a suitable model
$L_{\alpha _\xi }$
, we construct
$\mathbb {P}_n^{\xi +1}$
in a generic extension of
$L_{\alpha _\xi }$
(by a poset generalizing
$\mathbb {Q}(\mathbb {P})^{{<}\omega }$
which adds
$\omega $
-many generic perfect trees to every iterate in
$\mathbb {P}_n^\xi $
). As in the case of the construction of Jensen’s forcing
$\mathbb J$
, every maximal antichain of
$\mathbb {P}_n^\xi $
remains maximal in
$\mathbb J_n$
(see [Reference Friedman, Gitman and Kanovei2] for details). Abraham showed that the finite iterations
$\mathbb J_n$
have the ccc and add a unique n-length generic sequence of reals [Reference Abraham1, Lemmas 2.3 and 2.4].
In [Reference Friedman, Gitman and Kanovei2], together with Friedman and Kanovei, we studied the properties of the (non-linear) tree iterations of
$\mathbb J$
. Suppose that
$\mathcal T$
is a tree of height at most
$\omega $
. We will call the following poset
$\mathbb {P}(\mathbb J,\mathcal T)$
, the tree iteration of
$\mathbb J$
along
$\mathcal T$
. Elements of
$\mathbb {P}(\mathbb J,\mathcal T)$
are functions p from a finite subtree
$D_p$
of
$\mathcal T$
into
$\bigcup _{n<\omega }\mathbb J_n$
such that for every node
$s\in D_p$
,
$p(s)\in \mathbb J_{\text {len}(s)}$
and whenever
$s\subseteq t$
in
$D_p$
, then
$p(s)=p(t)\upharpoonright \text {len}(s)$
. In other words, a condition is a tree isomorphic to a finite subtree of
$\mathcal T$
whose level n nodes are elements of the n-length iteration
$\mathbb J_n$
and the assignment is coherent in the sense that conditions on the lower nodes are restrictions of the conditions on the higher nodes. The elements are ordered so that
$q\leq p$
if
$D_p\subseteq D_q$
and for every node
$s\in D_p$
,
$q(s)\leq p(s)$
. A generic filter G for
$\mathbb {P}(\mathbb J,\mathcal T)$
adds a tree
$\mathcal T^G$
isomorphic to
$\mathcal T$
whose nodes on level n are mutually generic sequences for
$\mathbb J_n$
.
Theorem 2.1 [Reference Friedman, Gitman and Kanovei2].
Suppose that
$\mathcal T=\omega ^{{<}\omega }$
or
$\mathcal T=\omega _1^{{<}\omega }$
. Then the tree iteration
$\mathbb {P}(\mathbb J,\mathcal T)$
has the ccc.
The tree iterations of
$\mathbb J$
also have a “uniqueness of generics” property generalizing Lyubetsky and Kanovei’s result for finite-support products of
$\mathbb J$
.
Theorem 2.2 [Reference Friedman, Gitman and Kanovei2].
Suppose that
$\mathcal T=\omega ^{{<}\omega }$
or
$\mathcal T=\omega _1^{{<}\omega }$
and
$G\subseteq \mathbb {P}(\mathbb J,\mathcal T)$
is L-generic. In
$L[G]$
:
-
(1) The only L-generic sequences of reals for
$\mathbb J_n$
are those coming from the nodes of
$\mathcal T^G$
on level n. -
(2) The collection of all L-generic n-length sequences of reals for
$\mathbb J_n$
is
$\Pi ^1_2$
-definable.
The following two easy propositions will be useful in later arguments. Given a condition
$p\in \mathbb {P}(\mathbb J,\mathcal T)$
and a subtree T of
$\mathcal T$
, let
$p\upharpoonright T$
be the restriction of p to the domain
$D_p\cap T$
.
Proposition 2.3. Suppose that T is a subtree of
$\mathcal T$
,
$a\in \mathbb {P}(\mathbb J, T)$
,
$p\in \mathbb {P}(\mathbb J,\mathcal T)$
, and a is compatible with
$p\upharpoonright T$
in
$\mathbb {P}(\mathbb J,T)$
, then a is compatible with p in
$\mathbb {P}(\mathbb J,\mathcal T)$
.
Proof. Let
$q\in \mathbb {P}(\mathbb J,T)$
be such that
$q\leq a,p\upharpoonright T$
. Define a condition
$q'$
with domain
$D_{q'}=D_q\cup D_p$
as follows. If
$s\in T$
, then
$q'(s)=q(s)$
. If
$s\in D_{q'}\setminus T$
, then let i be largest such that
$s\upharpoonright i\in D_p$
and let
$q'(s)$
be
$q(s\upharpoonright i)$
concatenated with the tail of
$p(s)$
from i. It is easy to see that
$q'\leq p,a$
in
$\mathbb {P}(\mathbb J,\mathcal T)$
.
Suppose that
$G\subseteq \mathbb {P}(\mathbb J,\mathcal T)$
is L-generic. Given a subtree T of
$\mathcal T$
, let
$G_T$
consist of all conditions
$p\in G$
with domain
$D_p\subseteq T$
.
Proposition 2.4. Suppose that T is a subtree of
$\mathcal T$
. Then
$G_T$
is L-generic for
$\mathbb {P}(\mathbb J,T)$
.
Proof. Suppose that
$p\in G_T$
and
$q\geq p$
in
$\mathbb {P}(\mathbb J,T)$
. Then
$q\geq p$
in
$\mathbb {P}(\mathbb J,\mathcal T)$
. So
$q\in G$
, and hence
$q\in G_T$
. Next, suppose that
$p,q\in G_T$
. Since
$p,q\in G$
, there is
$r\in G$
such that
$r\leq p,q$
, and hence
$r\upharpoonright T\leq p,q$
. Observe that
$r\upharpoonright T$
is compatible with every condition in G because r is compatible with every condition in G. Thus,
$r\upharpoonright T\in G$
, and hence
$r\upharpoonright T\in G_T$
. Finally, suppose that
$\mathcal A$
is a maximal antichain of
$\mathbb {P}(\mathbb J,T)$
. Let’s argue that
$\mathcal A$
is also a maximal antichain of
$\mathbb {P}(\mathbb J,\mathcal T)$
. Let
$p\in \mathbb {P}(\mathbb J,\mathcal T)$
. Then there is
$a\in \mathcal A$
that is compatible with
$p\upharpoonright T$
in
$\mathbb {P}(\mathbb J,T)$
, but then a is also compatible with p in
$\mathbb {P}(\mathbb J,\mathcal T)$
by Proposition 2.3. Thus, there is
$p\in G\cap \mathcal A$
. This completes the argument that
$G_T$
is L-generic for
$\mathbb {P}(\mathbb J,T)$
.
2.3 Automorphisms of forcing notions
Suppose that
$\mathbb {P}$
is a partial order,
$\pi $
is an automorphism of
$\mathbb {P}$
, and
$G\subseteq \mathbb {P}$
is V-generic. We can apply
$\pi $
recursively to any
$\mathbb {P}$
-name
$\sigma $
to obtain the
$\mathbb {P}$
-name
$\pi (\sigma )$
defined by
$\langle \tau ,p\rangle \in \sigma $
if and only if
$\langle \pi (\tau ),\pi (p)\rangle \in \pi (\sigma )$
. Standard arguments then show that for a condition
$p\in \mathbb {P}$
,
$p\Vdash \varphi (\sigma )$
if and only if
$\pi (p)\Vdash \varphi (\pi (\sigma ))$
. It is also easy to see that 
is V-generic. We will use the following standard proposition later, and we include the proof here for completeness.
Proposition 2.5. Suppose that
$\sigma $
is a
$\mathbb {P}$
-name. Then 
.
Proof. We can assume recursively that we already showed the conclusion for all
$\mathbb {P}$
-names
$\tau $
of rank less than
$\sigma $
. Suppose that 
. Then there is a
$\mathbb {P}$
-name
$\dot b$
such that 
,
$\langle \dot b,p\rangle \in \sigma $
, and 
. Let
$\pi ^{-1}(\bar p)=p$
. Then
$\langle \pi (\dot b),\bar p\rangle \in \pi (\sigma )$
and
$\bar p\in G$
. Thus,
$\pi (\dot b)_G\in \pi (\sigma )_G$
, and by our recursive assumption, since
$\dot b$
has rank less than
$\sigma $
, 
, and so,
$b\in \pi (\sigma )_G$
. Reversing the steps of this argument shows that if
$b\in \pi (\sigma )_G$
, then 
, verifying the equality.
3 A model of
$\mathrm {Z}_2^{-p}+\Sigma ^1_2$
-
$\mathrm {CA}$
+
$\neg \Sigma ^1_3$
-
$\mathrm {CA.}$
In this section, we construct a model of
$\mathrm {Z}_2^{-p}+\Sigma ^1_2$
-
$\mathrm {CA}$
in which
$\Sigma ^1_3$
-
$\mathrm {CA}$
fails.
Let
$G\subseteq \mathbb {P}(\mathbb J,\omega ^{{<}\omega })$
be L-generic. We work in
$L[G]$
. Let
$\dot \varphi $
be the canonical name for the isomorphism between
$\omega ^{{<}\omega }$
and the tree, added by G, whose nodes on level n are mutually generic n-length sequences of reals for
$\mathbb J_n$
.
Observe that any automorphism
$\pi $
of the tree
$\omega ^{{<}\omega }$
gives rise to the obvious corresponding automorphism
$\pi ^*$
of the poset
$\mathbb {P}(\mathbb J,\omega ^{{<}\omega })$
.
Theorem 3.1. Suppose that T is a finite subtree of
$\omega ^{{<}\omega }$
. Then the only L-generic sequences for
$\mathbb J_n$
in
$L[G_T]$
are the sequences
$\dot \varphi _G(s)$
for
$s\in T$
.
Proof. Let
$r\in L[G_T]$
be an n-length sequence of reals L-generic for
$\mathbb J_n$
. Then by Theorem 2.2 (1),
$r=\dot \varphi _G(s)$
for some node s on level n of
$\omega ^{{<}\omega }$
. Suppose towards a contradiction that
$s\notin T$
. Let
$i\geq 1$
be least such that
$s\upharpoonright i\notin T$
. Let
$\dot r$
be a
$\mathbb {P}(\mathbb J,T)$
-name for r. Let
$p\in G$
be such that
$p\Vdash \dot r=\dot \varphi (\check s)$
. Fix any condition
$q\leq p$
. Let
$t\in \omega ^{{<}\omega }$
be a node on the same level as s such that
$t\upharpoonright i-1=s\upharpoonright i-1$
and
$t\notin D_q\cup T\cup \{s\}$
. Many such nodes t must exist since
$D_q$
and T are both finite. Let
$\pi $
be an automorphism of
$\omega ^{{<}\omega }$
which maps
$(\omega ^{{<}\omega })_s$
onto
$(\omega ^{{<}\omega })_t$
, while fixing everything outside these subtrees. In particular,
$\pi $
fixes T and
$\pi (s)=t$
. Let 
and let
$\bar q$
be the condition defined so that for
$a\in D_q$
,
$\bar q(a)=\bar q(\pi (a))=q(a)$
. In other words, conditions on nodes in
$D_q\cap (\omega ^{{<}\omega })_s$
are copied over to
$(\omega ^{{<}\omega })_t$
. This means, in particular, that
$\pi ^*(\bar q)=\bar q$
. We have just argued that such conditions
$\bar q$
are dense below p, and so some such
$\bar q\in G$
. Let 
, which is also L-generic for
$\mathbb {P}(\mathbb J,\omega ^{{<}\omega })$
, and note that
$\pi ^*(\bar q)=\bar q\in H$
. Observe that
$\dot r_H=\dot r_G=r$
since the name
$\dot r$
only mentioned conditions with domain contained in T, and
$\pi $
fixes T. Since
$p\geq \bar q$
,
$p\in H$
. So it must be the case that
$r=\dot \varphi _H(s)$
. But this is impossible because
$\dot \varphi _H(s)=\dot \varphi _G(t)$
and, by genericity,
$\dot \varphi _G(s)\neq \dot \varphi _G(t)$
.
It is not clear how to make the argument above work for infinite subtrees
$T\in L$
, and I suspect that the result will turn out to be false for these.
We now follow the ideas in [Reference Kanovei and Lyubetsky8] to define the following subtree
$\mathcal T$
of
$\omega ^{{<}\omega }$
in
$L[G]$
. For
$1\leq m<\omega $
, let
$\vec 0_m$
denote the m-length sequence of zeroes. We have for every
$n<\omega $
and
$1\leq m<\omega $
:
-
(1)
$\langle n\rangle \in \mathcal T$
, -
(2)
, -
(3)
if and only if
$\dot \varphi _G(\langle n,1 \rangle )(1)(m)=1$
.
,
if and only if 
Condition (1) puts all level 1 nodes of
$\omega ^{{<}\omega }$
into
$\mathcal T$
. Condition (2) puts all left-most branches of
$\omega ^{{<}\omega }$
above level 1 nodes into
$\mathcal T$
. Condition (3) says that a node on level
$m+1$
of the left-most branch above
$\langle n\rangle $
splits in
$\mathcal T$
if and only if the mth bit of the second real in the pair of reals
$\dot \varphi _G(\langle n,1\rangle )$
is 1. Condition (3) is coding the reals
$\dot \varphi _G(\langle n,1\rangle )(1)$
into the tree
$\mathcal T$
. Let
$\dot {\mathcal T}$
be the canonical
$\mathbb {P}(\mathbb J,\omega ^{{<}\omega })$
-name for
$\mathcal T$
.
Let
$$ \begin{align*}\mathcal S=\{A\in P^{L[G_T]}(\omega)\mid T\subseteq \mathcal T\text{ is a finite tree}\}\end{align*} $$
be the union of the powersets of
$\omega $
from all submodels
$L[G_T]$
with T a finite subtree of
$\mathcal T$
, and let
$$ \begin{align*}\mathcal M=\langle \omega,+,\times,<,0,1\in,\mathcal S \rangle\end{align*} $$
be a model of second-order arithmetic in
$L[G]$
. We will argue that the model
$\mathcal M$
has all the required properties.
Proposition 3.2.
$\mathcal S=\{A\in P^{L[\{\dot \varphi _G(s)\mid s\in X\}]}(\omega )\mid X\subseteq \mathcal T\text { is finite}\}.$
Proof. Suppose that
$A\in P^{L[\{\dot \varphi _G(s)\mid s\in X\}]}(\omega )$
for some finite
$X\subseteq \mathcal T$
. Let
$X\subseteq T$
, where T is a finite subtree of
$\mathcal T$
. Then
$A\in L[\{\dot \varphi _G(s)\mid s\in X\}]\subseteq L[G_T]$
. Next, suppose that
$A\in L[G_T]$
for some finite subtree T of
$\mathcal T$
. The generic
$G_T$
is clearly inter-definable with the collection
$\{\dot \varphi _G(s)\mid s\in T\}$
, which means that
$A\in L[G_T]=L[\{\dot \varphi _G(s)\mid s\in T\}]$
.
In other words,
$\mathcal S$
depends only on the collection
$\bar {\mathcal T}=\{\dot \varphi _G(s)\mid s\in \mathcal T\}$
. Let
$\dot {\mathcal S}$
be the canonical
$\mathbb {P}(\mathbb J,\omega ^{{<}\omega })$
-name for
$\mathcal S$
. Since, via coding, we can view L-generic sequences for
$\mathbb J_n$
as subsets of
$\omega $
, we can talk about these sequences internally to the model
$\mathcal M$
. In particular, clearly
$\bar {\mathcal T}\subseteq \mathcal S$
.
Lemma 3.3. For every n-length sequence of reals
$r\in \mathcal S$
, we have that r is L-generic for
$\mathbb J_n$
if and only if
$r\in \bar { \mathcal T}$
. Hence
$\dot \varphi _G(\langle 0,1\rangle )\notin \mathcal S$
.
Proof. Suppose that
$r\in \mathcal S$
is an n-length sequence L-generic for
$\mathbb J_n$
. Then
$r\in L[G_T]$
for some finite tree
$T\subseteq \mathcal T$
. But then, by Theorem 3.1,
$r=\dot \varphi _G(s)$
for some
$s\in T$
. Since
$\langle 0,1\rangle \notin \mathcal T$
, it follows that
$\dot \varphi _G(\langle 0,1\rangle )\notin \mathcal S$
.
Observe that any permutation
$f\in L$
of
$\omega $
gives rise to the automorphism
$\pi _f$
of the tree
$\omega ^{{<}\omega }$
which correspondingly permutes the trees
$(\omega ^{{<}\omega })_{\langle n\rangle }$
for
$n<\omega $
. More precisely
$\pi _f(\langle n_0,n_1,\ldots , n_{\text {len}(s)-1}\rangle )=\langle f(n_0),n_1,\ldots , n_{\text {len}(s)-1}\rangle )$
. Given any two conditions
$p,q\in \mathbb {P}(\mathbb J,\omega ^{{<}\omega })$
, there is a permutation
$f\in L$
of
$\omega $
such that p and
$\pi _f^*(q)$
are compatible, namely, let f be any permutation such that for every
$\langle n\rangle \in D_p\cap D_q$
,
$f(n)=m$
for some m such that
$\langle m\rangle \notin D_p$
. We will argue that the collection
$\bar {\mathcal T}$
is not affected by applying automorphisms
$\pi ^*_f$
to the generic filter G, and hence neither is the collection
$\mathcal S$
.
Lemma 3.4. For any permutation
$f\in L$
of
$\omega $
, if 
, then 
, and hence
$\mathcal S=\dot {\mathcal S}_H$
.
Proof. Suppose that
$s=\langle n\rangle $
for some
$n<\omega $
and let
$r=\dot \varphi _G(s)$
. Then
$r=\dot \varphi _H(\langle f(n)\rangle )$
by the definition of
$\pi _f$
, and hence 
. Next, suppose that 
for some
$n<\omega $
and
$1\leq m<\omega $
, and
$r=\dot \varphi _G(s)$
. Then 
by the definition of
$\pi _f$
, and hence 
. Finally, suppose that 
for some
$n<\omega $
and
$1\leq m<\omega $
, and
$r=\dot \varphi _G(s)$
. Then
$\dot \varphi _G(\langle n,1 \rangle )(1)(m)=1$
by the definition of
$\mathcal T$
, and hence
$\dot \varphi _H(\langle f(n),1\rangle )(1)(m)=1$
by the definition of
$\pi _f$
. Thus, 
by the definition of
$\dot {\mathcal T}$
. Since
$f^{-1}$
is also a permutation of
$\omega $
, the same argument shows that 
. Since
$\mathcal S$
depends only on 
, it follows immediately that
$\mathcal S=\dot {\mathcal S}_H$
.
Corollary 3.5. For any permutation
$f\in L$
of
$\omega $
,
$\mathop {1\hskip -2.5pt \mathrm {l}}_{\mathbb {P}(\mathbb J,\omega ^{{<}\omega })}\dot {\mathcal S}=\pi _f^*(\dot {\mathcal S})$
.
Proof. We need to show that for any L-generic filter
$\bar G$
for
$\mathbb {P}(\mathbb J,\omega ^{{<}\omega })$
,
$\dot {\mathcal S}_{\bar G}=\pi ^*_f(\dot {\mathcal S})_{\bar G}$
. By Lemma 3.4, we know that 
. Since, clearly,
$\pi _{f^{-1}}=\pi ^{-1}_f$
, we have 
. By Proposition 2.5, we have 
.
Lemma 3.6. The model
$\mathcal M=\langle \omega ,+,\times ,<,0,1,\mathcal S\rangle \models \mathrm {Z}_2^{-p}$
.
Proof. Suppose that
$\psi (x)$
is a second-order arithmetic formula. We need to argue that
$$ \begin{align*}A=\{n\in\omega\mid \mathcal M\models\psi(x)\}\in \mathcal S.\end{align*} $$
Indeed, we will argue that
$A\in L$
by showing that if
$\mathcal M\models \psi (n)$
for some
$n<\omega $
, then
$$ \begin{align*}\mathop {1\hskip -2.5pt \mathrm {l}}\nolimits_{\mathbb {P}(\mathbb J,\omega ^{{<}\omega })}\Vdash \langle \omega ,+,\times ,<,0,1,\dot {\mathcal S}\rangle \models \psi (n).\end{align*} $$
Suppose toward a contradiction that
$p,q\in \mathbb {P}(\mathbb J,\omega ^{{<}\omega })$
and
$n<\omega $
such that
$$ \begin{align*}p\Vdash \langle \omega,+,\times,<,0,1,\dot{\mathcal S}\rangle\models\psi(n)\end{align*} $$
and
$$ \begin{align*}q\Vdash \langle \omega,+,\times,<,0,1,\dot{\mathcal S}\rangle\not\models\psi(n).\end{align*} $$
Let
$f\in L$
be a permutation of
$\omega $
such that p and
$\pi ^*_f(q)$
are compatible. We have
$$ \begin{align*}\pi^*_f(q)\Vdash \langle \omega,+,\times,<,0,1,\pi^*_f(\dot{\mathcal S})\rangle\not\models\psi(n).\end{align*} $$
But since by Corollary 3.5,
$\mathop {1\hskip -2.5pt \mathrm {l}}_{\mathbb {P}(\mathbb J,\omega ^{{<}\omega })}\Vdash \dot {\mathcal S}=\pi ^*_f(\dot {\mathcal S})$
,
$$ \begin{align*}\pi^*_f(q)\Vdash \langle \omega,+,\times,<,0,1,\dot{\mathcal S}\rangle\not\models\psi(n).\end{align*} $$
Let
$r\leq p, \pi ^*_f(q)$
. Then
$$ \begin{align*}r\Vdash \langle \omega,+,\times,<,0,1,\dot{\mathcal S}\rangle\models\psi(n)\end{align*} $$
and
$$ \begin{align*}r\Vdash \langle \omega,+,\times,<,0,1,\dot{\mathcal S}\rangle\not\models\psi(n),\end{align*} $$
which is the desired contradiction.
Lemma 3.7. The collection
$\bar {\mathcal T}=\{\dot \varphi _G(s)\mid s\in \mathcal T\}$
is definable in
$\mathcal M$
by a
$\Pi ^1_2$
-formula.
Proof. By Lemma 3.3, for every n-length sequence
$r\in \mathcal S$
,
$r\in \bar {\mathcal T}$
if and only if r is an n-length sequence of reals L-generic for some
$\mathbb J_n$
. Thus, it suffices to argue that
$\mathcal M$
can recognize in a
$\Pi ^1_2$
-way whether an n-length sequence of reals is L-generic for
$\mathbb J_n$
. Recall, from Section 2.2, that the iteration
$\mathbb J_n$
is constructed as the union of the
$\omega _1$
-length chain of iterations
$\mathbb {P}_n^\xi $
for
$\xi <\omega _1$
, and every maximal antichain of
$\mathbb {P}_n^\xi $
remains maximal in
$\mathbb J_n$
(for the precise result, see Lemma 6.11 (4) in [Reference Friedman, Gitman and Kanovei2]). Thus, any n-length L-generic sequence of reals for
$\mathbb J_n$
is also
$L_{\alpha _\xi }$
-generic for
$\mathbb {P}_n^\xi $
, where
$\xi +1$
is a non-trivial stage in the construction of
$\mathbb J_n$
. Since each iteration
$\mathbb J_n$
has the ccc, the converse holds as well: if an n-length sequence of reals is
$L_{\alpha _\xi }$
-generic for
$\mathbb {P}_n^\xi $
for all non-trivial stages
$\xi +1$
in the construction of
$\mathbb J_n$
, then it is fully L-generic for
$\mathbb J_n$
. Next, observe that whether an n-length sequence of reals r is
$L_{\alpha _\xi }$
-generic for
$\mathbb {P}_n^\xi $
can be verified in any
$L_\alpha [r]\models \mathrm {ZFC}^-$
with
$\alpha>\xi $
. Notice also that any
$L_\alpha \models \mathrm {ZFC}^-$
can verify whether
$\xi +1<\alpha $
is a non-trivial stage in the construction of
$\mathbb J_n$
. Putting it all together, we get that an n-length sequence r of reals is L-generic for
$\mathbb J_n$
if and only if for every
$\alpha <\omega _1$
such that
$L_\alpha [r]\models \mathrm {ZFC}^-$
, if
$\xi <\alpha $
is such that
$\xi +1$
is a non-trivial stage in the construction of
$\mathbb J_n$
, then
$L_\alpha [r]$
satisfies that r is
$L_{\alpha _\xi }$
-generic for
$\mathbb {P}_n^\xi $
. Because
$\mathcal S$
is the union powersets of
$\omega $
for models of the form
$L[A]$
, given any
$r\in \mathcal S$
,
$\mathcal S$
has (a code for)
$L_\alpha [r]$
for any countable
$\alpha $
and
$r\in \mathcal S$
. Thus, an n-length sequence
$r\in \mathcal S$
of reals is L-generic for
$\mathbb J_n$
if and only if
$\mathcal M$
satisfies that for every class X, Y, Z, if X is a well-order and Y codes
$L_X[r]$
and Z is a truth predicate for
$L_X[r]$
and
$L_X[r]\models \mathrm {ZFC}^-$
(according to Z), then r is
$L_{\alpha _\xi }$
-generic for
$\mathbb {P}_n^\xi $
for every non-trivial successor stage
$\xi +1$
in
$L_X$
. The formula is
$\Pi ^1_2$
because being a well-order is
$\Pi ^1_1$
.
Lemma 3.8.
$\dot \varphi _G(\langle 0,1\rangle )$
is definable in
$\mathcal M$
from the parameter
$\dot \varphi _G(\langle 0\rangle )$
by a
$\Sigma ^1_3$
-formula. Thus,
$\Sigma ^1_3$
-
$\mathrm {CA}$
fails in
$\mathcal M$
.
Proof. We have that
$m\in \dot \varphi _G(\langle 0,1\rangle )(1)$
if and only if there are two L-generic
$m+1$
-length sequences of reals generic for
$\mathbb J_{m+1}$
whose first coordinate is
$\dot \varphi _G(\langle 0\rangle )$
. By Lemma 3.7, this is a
$\Sigma ^1_3$
-formula with parameter
$\dot \varphi _G(\langle 0\rangle )$
. Since
$\dot \varphi _G(\langle 0,1\rangle )\notin \mathcal S$
,
$\Sigma ^1_3$
-
$\mathrm {CA}$
fails in
$\mathcal M$
.
Lemma 3.9.
$\Sigma ^1_2$
-
$\mathrm {CA}$
holds in
$\mathcal M$
.
Proof. Since
$\mathcal S$
is clearly closed under complement, it suffices to show that
$\Pi ^1_2$
-
$\mathrm {CA}$
holds in
$\mathcal M$
. Let
$A\in \mathcal S$
and fix a formula
$\psi (x,A):=\forall X\exists Y\,\varphi (x,X,Y,A)$
, where
$\varphi $
is a first-order formula. We will argue that
$$ \begin{align*}\{n\in\omega\mid L[A]\models\psi(n,A)\}=\{n\in\omega\mid \mathcal M\models\psi(n,A)\}.\end{align*} $$
This suffices since if
$A\in \mathcal S$
, then
$A\in L[G_T]$
for some finite subtree T of
$\mathcal T$
, and hence the set
$\{n\in \omega \mid L[A]\models \psi (n,A)\}$
is in
$L[G_T]$
as well.
Suppose
$L[A]\models \psi (n,A)$
for some
$n<\omega $
. Let
$C\in \mathcal S$
. By Shoenfield’s absoluteness,
$$ \begin{align*}L[A,C]\models\psi(n,A).\end{align*} $$
Thus, there is
$B\in L[A,C]$
such that
$$ \begin{align*}L[A,C]\models\varphi(n,C,B,A).\end{align*} $$
Since
$A,C\in \mathcal S$
,
$P^{L[A,C]}(\omega )\subseteq \mathcal S$
, and so
$B\in \mathcal S$
. Thus,
$\mathcal M\models \varphi (n,C,B,A)$
. Since
$C\in \mathcal S$
was arbitrary,
$\mathcal M\models \psi (n,A)$
. Next, suppose that
$\mathcal M\models \psi (n,A)$
. Fix
$C\in L[A]$
. Then
$\mathcal M\models \exists Y\,\varphi (n,C,Y,A)$
. Fix
$B\in \mathcal S$
such that
$\mathcal M\models \varphi (n,C,B,A)$
. Then
$L[A,C,B]\models \varphi (n,C,B,A)$
, and so
$L[A,C,B]\models \exists Y\,\varphi (n,C,Y,A)$
. But then by Shoenfield’s absoluteness,
$L[A]\models \exists Y\,\varphi (n,C,Y,A)$
. Since
$C\in L[A]$
was arbitrary,
$L[A]\models \psi (n,A)$
.
This finishes the argument that
$\mathcal M\models \mathrm {Z}_2^{-p}+\Sigma ^1_2$
-
$\mathrm {CA}$
+
$\neg \Sigma ^1_3$
-
$\mathrm {CA}$
. Finally, let’s observe that the parameter-free collection scheme fails in
$\mathcal M$
.
Proposition 3.10.
$\mathrm {Coll}^{-p}$
fails in
$\mathcal M$
.
Proof. The model
$\mathcal M$
satisfies that for every n, there is an n-length L-generic sequence of reals for
$\mathbb J_n$
. But there cannot be a single set
$X\in \mathcal S$
collecting on its slices n-length L-generic sequences of reals for
$\mathbb J_n$
for every
$n<\omega $
because X has to come from some
$L[G_T]$
, where T is a finite tree. Since T is finite, by the uniqueness Theorem 3.1, there is some
$n<\omega $
such that
$L[G_T]$
cannot have an L-generic sequence of reals for
$\mathbb J_n$
.
4 A model of
$\mathrm {Z}_2^{-p}+\mathrm {Coll}^{-p}+\Sigma ^1_2$
-
$\mathrm {CA}+\neg \Sigma ^1_4$
-
$\mathrm {CA}+\neg \mathrm {AC}^{-p}$
In this section, we construct a model of
$\mathrm {Z}_2^{-p}+\mathrm {Coll}^{-p}+\Sigma ^1_2$
-
$\mathrm {CA}$
in which
$\Sigma ^1_4$
-
$\mathrm {CA}$
fails and
$\mathrm {AC}^{-p}$
fails. We do this by using a more complicated version of the construction in Section 3 working in a forcing extension of L by
$\mathbb {P}(\mathbb J,\omega _1^{{<}\omega })$
instead of
$\mathbb {P}(\mathbb J,\omega ^{{<}\omega })$
.
Let
$G\subseteq \mathbb {P}(\mathbb J,\omega _1^{{<}\omega })$
be L-generic. We work in
$L[G]$
. Let
$\dot \varphi $
be the canonical name for the isomorphism between
$\omega _1^{{<}\omega }$
and the tree, added by G, whose nodes on level n are mutually generic sequences of reals for
$\mathbb J_n$
.
We start with the following generalization of Theorem 3.1.
Theorem 4.1. Suppose that
$T\in L$
that is a countable subtree of
$\omega _1^{{<}\omega }$
. Then the only L-generic sequences for
$\mathbb J_n$
in
$L[G_T]$
are the sequences
$\dot \varphi _G(s)$
for
$s\in T$
.
The proof is analogous to the proof of Theorem 3.1, using that
$\omega _1^{{<}\omega }$
is uncountable and the tree T is countable to have enough room to find the required node t for the automorphism.
We define the following subtree
$\mathcal T$
of
$\omega _1^{{<}\omega }$
in
$L[G]$
. We have for every
$\xi <\omega _1$
,
$1\leq m<\omega $
,
$n<\omega $
:
-
(1)
$\langle \xi \rangle \in \mathcal T$
, -
(2)
, -
(3)
-
(4)
for all
$\eta <\omega _1$
if and only if
$\dot \varphi _G(\langle \xi ,1 \rangle )(1)(m)=1$
.
,
for all 
Conditions (3) and (4) say that whether a node 
of a left-most branch above a level 1 node splits into
$\omega $
-many or
$\omega _1$
-many nodes depends on whether
$\dot \varphi _G(\langle \xi ,1\rangle )(1)(m)=1$
.
Let
$$ \begin{align*}\mathcal S=\{A\in P^{L[G_T]}(\omega)\mid T\subseteq \mathcal T\text{ is a countable tree and } T\in L\}\end{align*} $$
be the union of the powersets of
$\omega $
from all submodels
$L[G_T]$
with T a countable subtree of
$\mathcal T$
from L, and let
$$ \begin{align*}\mathcal M=\langle \omega,+,\times,<,0,1\in,\mathcal S \rangle.\end{align*} $$
We will argue that the model
$\mathcal M$
has all the required properties. As before, let
$\bar {\mathcal {T}}=\{\dot\varphi_G(s)\mid s\in \mathcal {T}\}$
and let
$\dot{\mathcal {S}}$
be the canonical
$\mathbb{P}(\mathbb{J},\omega_1^{{<}\omega})$
-name for
$\mathcal {S}$
. Using Theorem 4.1, we show
Lemma 4.2. For every n-length sequence of reals
$r\in \mathcal S$
, we have that r is L-generic for
$\mathbb J_n$
if and only if
$r\in \bar { \mathcal T}$
. Hence
$\dot \varphi _G(\langle 0,1\rangle )\notin \mathcal S$
.
Observe that any permutation
$f\in L$
of
$\omega _1$
gives rise to the automorphism
$\pi _f$
of the tree
$\omega _1^{{<}\omega }$
which correspondingly permutes the trees
$(\omega _1^{{<}\omega })_{\langle \xi \rangle }$
for
$\xi <\omega _1$
. More precisely
$\pi _f(\langle \xi _0,\xi _1,\ldots , \xi _{\text {len}(s)-1}\rangle )=\langle f(\xi _0),\xi _1,\ldots , \xi _{\text {len}(s)-1}\rangle )$
. As before, given any two conditions
$p,q\in \mathbb {P}(\mathbb J,\omega _1^{{<}\omega })$
, there is a permutation
$f\in L$
of
$\omega _1$
such that p and
$\pi _f^*(q)$
are compatible. We will argue that the collection
$\mathcal S$
is not affected by applying automorphisms
$\pi ^*_f$
to the generic filter G.
Lemma 4.3. For any permutation
$f\in L$
of
$\omega _1$
, we have 
. Thus,
$\mathop {1\hskip -2.5pt \mathrm {l}}_{\mathbb {P}(\mathbb J,\omega _1^{{<}\omega })}\Vdash \dot {\mathcal S}=\pi _f^*(\dot {\mathcal S})$
.
Proof. Let 
. Suppose that
$T\in L$
is a countable subtree of
$\mathcal T$
. Let 
. Let’s argue that
$T'\subseteq \dot {\mathcal T}_H$
. It suffices to focus on nodes 
, where
$\eta \notin \omega $
. So suppose
$s\in T$
. It follows that
$\dot \varphi _G(\langle \xi ,1\rangle )(1)(m)=1$
, and so
$\dot \varphi _H(\langle f(\xi ),1\rangle )(m)=1$
, which means that 
. Since
$f^{-1}$
is also a permutation of
$\omega _1$
, we have that if
$T'\in L$
is a countable subtree of
$\dot {\mathcal T}_H$
, then 
is a subtree of
$\mathcal T$
. Next, observe that given such trees T and
$T'$
, we have that
$L[G_T]=L[H_{T'}]$
because the trees T and
$T'$
are isomorphic by
$\pi _f$
, making the posets
$\mathbb {P}(\mathbb J,T)$
and
$\mathbb {P}(\mathbb J,T')$
isomorphic by
$\pi ^*_f$
, and the isomorphism takes
$G_T$
to
$H_{T'}$
. It follows that 
.
Analogs of Lemma 3.6 and Lemma 3.9 in Section 3 give that
$\mathcal M$
satisfies
$\mathrm {Z}^{-p}_2+\Sigma ^1_2$
-
$\mathrm {CA}$
.
Lemma 4.4.
$\dot \varphi _G(\langle 0,1\rangle )$
is definable in
$\mathcal M$
from the parameter
$\dot \varphi _G(\langle 0\rangle )$
by a
$\Pi ^1_4$
-formula. Thus,
$\Sigma ^1_4$
-
$\mathrm {CA}$
fails in
$\mathcal M$
.
Proof. Recall that for
$m<\omega $
,
$\dot \varphi _G(\langle 0,1\rangle )(1)(m)=1$
if and only if
$\mathcal T$
splits
$\omega _1$
-many times above the node 
. In this case,
$\mathcal S$
does not have a maximal set of L-generic sequences for
$\mathbb J_{m+1}$
whose first coordinate is
$\dot \varphi _G(\langle 0\rangle )$
. More formally, there is no set
$A\in \mathcal S$
such that each slice
$A_n$
is an L-generic
$m+1$
-length sequence for
$\mathbb J_{m+1}$
whose first coordinate is
$\dot \varphi _G(\langle 0\rangle )$
and whenever R is an L-generic
$m+1$
-length sequence for
$\mathbb J_{m+1}$
whose first coordinate is
$\dot \varphi _G(\langle 0\rangle )$
, then
$R=A_n$
for some
$n<\omega $
. The assertion that each slice
$A_n$
is an L-generic
$m+1$
-length sequence for
$\mathbb J_{m+1}$
whose first coordinate is
$\dot \varphi _G(\langle 0\rangle )$
is
$\Pi ^1_2$
and the assertion that every L-generic
$m+1$
-length sequence R for
$\mathbb J_{m+1}$
, whose first coordinate is
$\dot \varphi _G(\langle 0\rangle )$
, is
$A_n$
for some
$n<\omega $
is
$\Pi ^1_3$
. Thus, the assertion that A is maximal as above is
$\Pi ^1_3$
, and therefore, the assertion that there is no such A is
$\Pi _4^1$
.
Next, we verify that
$\mathcal M\models \mathrm {Coll}^{-p}$
.
We will call a countable subtree
$T\in L$
of
$\mathcal T$
full if whenever it contains a node
$\langle \xi \rangle $
, then it contains all nodes 
for
$1\leq m<\omega $
and all nodes 
for
$n<\omega $
and
$1\leq m<\omega $
. We will call a countable tree
$T\in L$
undecided if the only nodes in T are of the form
$\langle \xi \rangle $
for some
$\xi <\omega _1$
or 
for some
$m<\omega $
or 
for some
$n<\omega $
and
$1\leq m<\omega $
. Observe that every undecided tree T is automatically contained in
$\mathcal T$
. As the name suggests, we cannot tell from an undecided tree whether
$\dot \varphi _G(\langle \xi ,1\rangle )(1)(m)=1$
for any
$\xi <\omega _1$
and
$m<\omega $
.
Lemma 4.5. Suppose that
$T\in L$
is a full countable subtree of
$\mathcal T$
,
$\varphi (x,X)$
is a second-order formula, and there is
$A\in L[G_T]$
such that
$\mathcal M\models \varphi (n,A)$
. Then there is a full undecided countable tree
$\bar T\in L$
and
$\bar A\in L[G_{\bar T}]$
such that
$\mathcal M\models \varphi (n,\bar A)$
.
Proof. Let
$p\in G$
be such that
$$ \begin{align*}p\Vdash \exists X\in L[\dot G_T]\,\langle\omega,+,\times,<,0,1,\dot{\mathcal S}\rangle\models\varphi(n,X).\end{align*} $$
Let’s argue that there can only be finitely many
$\xi <\omega _1$
such that 
for some
$\eta \notin \omega $
. Since
$T\subseteq \mathcal T$
, there is some condition
$q\in G$
such that
$q\Vdash T\subseteq \dot {\mathcal T}$
. Thus, for every node 
with
$\eta \notin \omega $
,
$$ \begin{align*}q\Vdash\dot\varphi_G(\langle \xi,1\rangle)(1)(m)=1.\end{align*} $$
But this is clearly only possible for
$\xi $
such that
$\langle \xi \rangle \in D_q$
, and
$D_q$
is finite. So let
$\{\xi _0,\ldots ,\xi _{n-1}\}$
be a finite set such that if 
with
$\eta \notin \omega $
, then
$\xi =\xi _i$
for some
$i<n$
. By strengthening the condition p, we can assume that
-
(1)
$\{\langle \xi _i\rangle \mid i<n\}$
are exactly the level 1 nodes in
$D_p$
, -
(2) for
$i<n$
,
$\langle \xi _i,1\rangle \in D_p$
, -
(3) for every
with
$\eta \notin \omega $
,
$p(\langle \xi _i\rangle )\Vdash p(\langle \xi _i,1\rangle )(1)(m)=1.$
with 
Fix some
$\vec \eta =\{\eta _i\mid i<n\}$
such that for
$i<n$
,
$\langle \eta _i\rangle \notin T\cup \{\langle \xi _i\rangle \mid i<n\}$
, which is possible since T is countable. Let
$f:\omega _1\to \omega _1$
such that
$f(\xi _i)=\eta _i$
,
$f(\eta _i)=\xi _i$
for
$i<n$
and
$f(\xi )=\xi $
otherwise. For each
$i<n$
and
$1\leq m<\omega $
, let
$f_{i,m}:\omega _1\to \omega _1$
be a bijection which maps the set
onto
$\omega $
. Let
$\pi _{\vec \eta }$
be the following automorphism of
$\omega _1^{{<}\omega }$
. If
$t=\langle \alpha _0,\alpha _1\ldots ,\alpha _n\rangle $
does not end-extend a node 
with
$\alpha =\xi _i$
or
$\alpha =\eta _i$
for some
$i<n$
, then
$\pi _{\vec \eta }(t)=\langle f(\alpha _0),\alpha _1,\ldots ,\alpha _n\rangle $
. Suppose 
, where
$\alpha =\xi _i$
or
$\alpha =\eta _i$
. If
$\alpha =\xi _i$
, then 
and if
$\alpha =\eta _i$
, then 
. To summarize,
$\pi _{\vec \eta }$
switches the tree
$(\omega _1^{{<}\omega })_{\xi _i}$
with the tree
$(\omega _1^{{<}\omega })_{\eta _i}$
for
$i<n$
, keeping everything the same other than mapping nodes of the form 
to nodes of the form 
such that if
$s\in T$
, then
$\bar \eta <\omega $
. This ensures that the image of T under
$\pi _{\vec \eta }$
is an undecided tree.
By density, we can find such a set of nodes
$\vec \eta $
and a condition
$q\in G$
with 
such that for nodes
$s\in D_p$
,
$q(s)=p(s)$
and
$q(\pi _{\vec \eta }(s))=p(s)$
. In particular,
$q\leq p$
. By the definition of
$\pi _{\vec \eta }$
, this means that
$\pi ^*_{\vec \eta }(q)=q$
. Let 
. It is easy to see that if
$S\in L$
is a subtree of
$\mathcal T$
, then 
is a subtree of
$\dot {\mathcal T}_H$
. So let’s argue that if
$S'\in L$
is a subtree of
$\dot {\mathcal T}_H$
, then 
is a subtree of
$\mathcal T$
. The main concern is to show that if
$\dot \varphi _H(\langle \eta _i,1\rangle )(m)(1)=0$
, then for every 
with
$n<\omega $
, 
with
$k<\omega $
. But this is true because, according to
$\pi _{\vec \eta }$
, the only situation in which k might end up outside of
$\omega $
is when
$\pi ^{-1}_{\vec \eta }(t)\in T$
, and in this case, by our assumption on p,
$q(\langle \eta _i\rangle )=p(\langle \xi _i\rangle )\Vdash p(\langle \xi _i,1\rangle )(1)(m)=1$
, and
$p(\langle \xi _i,1\rangle )=q(\langle \eta _i,1\rangle )$
, which means that
$\dot \varphi _H(\langle \eta _i,1\rangle )(1)(m)=1$
.
Thus, by our usual arguments, the automorphism
$\pi ^*_{\vec \eta }$
does not affect
$\mathcal S$
. Next, observe that 
is a full undecided subtree of
$\dot {\mathcal T}_H$
. Since
$q\leq p$
,
$$ \begin{align*}q\Vdash \exists X\in L[\dot G_T]\,\langle\omega,+,\times,<,0,1,\dot{\mathcal S}\rangle\models\varphi(n,X).\end{align*} $$
Since
$q=\pi ^*_{\vec \eta }(q)\in H$
and
$\pi ^*_{\vec \eta }$
does not affect
$\mathcal S$
, there is
$A\in L[H_T]$
such that
$\mathcal M\models \varphi (n,A)$
. But now since T is isomorphic to
$T'$
via
$\pi _{\vec \eta }$
, the posets
$\mathbb {P}(\mathbb J,T)$
and
$\mathbb {P}(\mathbb J,T')$
are isomorphic via
$\pi ^*_{\vec \eta }$
, which means that
$L[H_T]=L[G_{T'}]$
. Since
$T'$
is undecided, we have proved what we promised.
Lemma 4.6.
$\mathcal M\models {\mathrm {Coll}}^{-p}$
.
Proof. Suppose that
$\mathcal M\models \forall n\exists X\,\varphi (n,X)$
for some second-order arithmetic formula
$\varphi (n,X)$
. Given
$n<\omega $
, by Lemma 4.5, there is a full undecided countable subtree
$T_n\in L$
and
$X\in L[G_{T_n}]$
such that
$\mathcal M\models \varphi (n,X)$
. By extending
$T_n$
to a larger tree, if necessary, we can assume that
$\{\xi <\omega _1\mid \langle \xi \rangle \in T_n\}$
is an ordinal
$\alpha _n$
. Let
$\alpha =\bigcup _{n<\omega }\alpha _n$
and let T be the full undecided tree whose level 1 nodes are precisely
$\langle \xi \rangle $
for
$\xi <\alpha $
. Then each
$T_n$
is contained in T. Thus, for every
$n<\omega $
, there is some
$X\in L[G_T]$
such that
$\mathcal M\models \varphi (n,X)$
.
Since
$\mathbb {P}(\mathbb J,\omega _1^{{<}\omega })$
has the ccc by Theorem 2.1, all
$\mathbb {P}(\mathbb J,\omega _1^{{<}\omega })$
-nice names for reals are in
$L_{\omega _1}$
. Thus, there is a countable ordinal
$\beta $
such that
$L_\beta $
already has, for every
$n<\omega $
, a
$\mathbb {P}(\mathbb J,T)$
-name
$\dot X_n$
such that
$\mathcal M\models \varphi (n,(\dot X_n)_G)$
. It follows that
$\{\dot X_{G_T}\mid \dot X\in L_\beta \text { is a } \mathbb {P}(\mathbb J,T)\text {-name}\}$
is a countable set of reals in
$L[G_T]$
having a witness to
$\mathcal M\models \varphi (n,X)$
for every
$n<\omega $
, and this set is in
$\mathcal S$
.
This finishes the argument that
$\mathcal M\models \mathrm {Z}_2^{-p}+\mathrm {Coll}^{-p}+\Sigma ^1_2$
-
$\mathrm {CA}$
+
$\neg \Sigma ^1_4$
-
$\mathrm {CA}$
.
Finally, let’s observe that
$\mathrm {AC}^{-p}$
fails in
$\mathcal M$
.
Lemma 4.7.
$\mathrm {AC}^{-p}$
fails in
$\mathcal M.$
Proof. The model
$\mathcal M$
satisfies that for every
$n<\omega $
, there is an L-generic real Y for
$\mathbb J$
and
$s\in 2^n$
such that for
$m<n$
,
$s(m)=1$
if and only if for every set coding
$\omega $
-many
$m+1$
-length L-generic sequences for
$\mathbb J_{m+1}$
with Y as the first coordinate, there is another
$m+1$
-length L-generic sequence for
$\mathbb J_{m+1}$
not in the set. In other words,
$Y=\dot \varphi _G(\langle \xi \rangle )$
for some
$\xi <\omega _1$
and
$s= \dot \varphi _G(\langle \xi ,1\rangle )\upharpoonright n$
.
Suppose that
$\mathcal M\models \mathrm {AC}^{-p}$
. Then
$\mathcal S$
has a set A such that
$A_n$
codes
$Y_n$
and
$s_n$
witnessing the statement above. Let
$T\in L$
be a countable subtree of
$\mathcal T$
such that
$A\in L[G_T]$
. First, let’s observe that there cannot be cofinally many
$n<\omega $
such that
$A_n$
codes the same real Y because if this was the case and
$Y=\dot \varphi _G(\langle \xi \rangle )$
, then using
$\Sigma ^1_2$
-
$\mathrm {CA}$
, we could argue that
$\dot \varphi _G(\langle \xi ,1\rangle )\in \mathcal S$
. Thus, there are countably many different reals Y coded on the slices of A. Next, we fix a condition p and a
$\mathbb {P}(\mathbb J,T)$
-name
$\dot A$
such that p forces that for all
$n<\omega $
,
$\dot A_n$
codes, for some
$\xi <\omega _1$
,
$\dot \varphi (\langle \xi \rangle )$
and
$\dot \varphi (\langle \xi ,1\rangle )\upharpoonright n$
. Choose some
$Y_n=\dot \varphi _G(\langle \alpha \rangle )$
with
$\langle \alpha \rangle \notin D_p$
, which is possible since there are infinitely many different Y and p is finite. Next choose some
$1\leq \eta <\omega _1$
such that
$\dot \varphi _G(\langle \alpha ,\eta \rangle )\upharpoonright n\neq \dot \varphi _G(\langle \alpha ,1\rangle )\upharpoonright n$
, which must exist by density. Let
$\pi $
be an automorphism of
$\omega _1^{{<}\omega }$
which switches the trees
$(\omega _1^{{<}\omega })_{\langle \alpha ,1\rangle }$
and
$(\omega _1^{{<}\omega })_{\langle \alpha ,\eta \rangle }$
, while preserving everything else, and note that
$\pi $
fixes T and p by our choice of
$\alpha $
and
$\eta $
. Let 
, and note that
$\pi ^*(p)=p\in H$
. Also,
$\pi ^*(p)=p$
forces that for all
$n<\omega $
,
$\pi ^*(\dot A)_n=\dot A_n$
codes, for some
$\xi <\omega _1$
,
$\dot \varphi (\langle \xi \rangle )$
and
$\dot \varphi (\langle \xi ,1\rangle )\upharpoonright n$
. Now we have that
$\dot A_G=\dot A_H$
, but
$\dot \varphi _H(\langle \alpha ,1\rangle )=\dot \varphi _G(\langle \alpha ,\eta \rangle )$
, and, by construction,
$\dot \varphi _G(\langle \alpha ,1\rangle )\upharpoonright n\neq \dot \varphi _G(\langle \alpha ,\eta \rangle )\upharpoonright n$
. Thus, we have reached a contradiction, showing that such a set A cannot exist.
Corollary 4.8. The schemes
$\mathrm {AC}^{-p}$
and
$\mathrm {Coll}^{-p}$
are not equivalent over
${\mathrm {Z}}_2^{-p}$
or even over
${\mathrm {Z}}_2^{-p}+\Sigma ^1_2$
-
$\mathrm {CA}$
.
5 A model of
$\mathrm {Z}_2^{-p}+\mathrm {AC}^{-p}+\Sigma ^1_2$
-
$\mathrm {CA}+\neg \Sigma ^1_4$
-
$\mathrm {CA.}$
In this section, we construct a model of
$\mathrm {Z}_2^{-p}+\mathrm {AC}^{-p}+\Sigma ^1_2$
-
$\mathrm {CA}$
in which
$\Sigma ^1_4$
-
$\mathrm {CA}$
fails. We will again be working in a forcing extension of L by
$\mathbb {P}(\mathbb J,\omega _1^{{<}\omega })$
, but we are going to change the tree
$\mathcal T$
to code in a different set to witness the failure of comprehension with parameters in our model.
Let
$G\subseteq \mathbb {P}(\mathbb J,\omega _1^{{<}\omega })$
be L-generic. We work in
$L[G]$
. Let
$\dot \varphi $
be the canonical name for the isomorphism between
$\omega _1^{{<}\omega }$
and the tree, added by G, whose nodes on level n are mutually generic sequences of reals for
$\mathbb J_n$
.
In this construction, we are going to define a tree
$\mathcal T$
similarly to how we defined it in the previous sections, but instead of coding, for every
$\xi <\omega _1$
, the sets
$\dot \varphi _G(\langle \xi ,1\rangle )(1)$
into
$\mathcal T$
, we are going to code in, for every
$\xi <\omega _1$
, the finite fragments
$\dot \varphi _G(\langle \xi ,n\rangle )(1)\upharpoonright n$
for
$n<\omega $
. Let
$p_n$
, for
$n<\omega $
, denote the n-th prime. For
$n<\omega $
, we will code the n-length fragment
$\dot \varphi _G(\langle \xi ,n\rangle )(1)\upharpoonright n$
so that
$\dot \varphi _G(\langle \xi ,n\rangle )(1)(m)=1$
if and only if the node 
splits
$\omega _1$
-many times in
$\mathcal T$
.
We define the following subtree
$\mathcal T$
of
$\omega _1^{{<}\omega }$
in
$L[G]$
. We have for every
$\xi <\omega _1$
,
$1\leq m<\omega $
,
$n<\omega $
:
-
(1)
$\langle \xi \rangle \in \mathcal T$
, -
(2)
, -
(3)
-
(4)
for all
$\eta <\omega _1$
if and only if
$\dot \varphi _G(\langle \xi ,n \rangle )(1)(m)=1$
and
$m<n$
.
,
for all 
Let
$$ \begin{align*}\mathcal S=\{A\in P^{L[G_T]}(\omega)\mid T\subseteq \mathcal T\text{ is a countable tree and } T\in L\},\end{align*} $$
and let
$$ \begin{align*}\mathcal M=\langle \omega,+,\times,<,0,1\in,\mathcal S \rangle.\end{align*} $$
We will argue that the model
$\mathcal M$
has all the required properties.
As before, let
$\dot {\mathcal S}$
be the canonical
$\mathbb {P}(\mathbb J,\omega _1^{{<}\omega })$
-name for
$\mathcal S$
. An analogous proof to the proof of Lemma 4.3 gives
Lemma 5.1. For any permutation
$f\in L$
of
$\omega _1$
, we have 
. Thus,
$\mathop {1\hskip -2.5pt \mathrm {l}}_{\mathbb {P}(\mathbb J,\omega _1^{{<}\omega })}\Vdash \dot {\mathcal S}=\pi _f^*(\dot {\mathcal S})$
.
Analogs of Lemma 3.6 and Lemma 3.9 in Section 3 give that
$\mathcal M$
satisfies
$\mathrm {Z}^{-p}_2+\Sigma ^1_2$
-
$\mathrm {CA}$
.
Let
$$ \begin{align*}C=\{\langle n,i\rangle\mid i<n, \dot\varphi_G(\langle 0,n\rangle)(m)=i\}.\end{align*} $$
It is easy to see using the proof of Lemma 4.4 that C is
$\Pi ^1_4$
-definable in
$\mathcal M$
from the parameter
$\dot \varphi _G(\langle 0\rangle )$
.
Lemma 5.2. The set
$C\notin \mathcal S$
.
Proof. Suppose towards a contradiction that
$C\in \mathcal S$
, and fix a countable subtree
$T\in L$
of
$\mathcal T$
such that
$C\in L[G_T]$
. Let
$\dot C$
be a
$\mathbb {P}(\mathbb J,T)$
-name such that
$\dot C_G=C$
and fix a condition
$$ \begin{align*}p\Vdash \dot C=\{\langle n,i\rangle\mid i<n, \dot\varphi(\langle 0,n\rangle)(m)=i\}.\end{align*} $$
Fix some
$1\leq k<\omega $
such that
$\langle 0,k\rangle \notin D_p$
, which is possible since
$D_p$
is finite. Fix some
$1\leq \eta <\omega _1$
such that
$\dot \varphi _G(\langle 0,\eta \rangle )\upharpoonright k\neq \dot \varphi _G(\langle 0,k\rangle )\upharpoonright k$
, which must exist by density. Let
$\pi $
be an automorphism of the tree
$\omega _1^{{<}\omega }$
which switches the trees
$(\omega _1^{{<}\omega })_{\langle 0,k\rangle }$
and
$(\omega _1^{{<}\omega })_{\langle 0,\eta \rangle }$
and fixes everything else. Observe that
$\pi $
fixes every node in the tree T. By construction,
$\pi ^*(p)=p$
, and since
$\pi $
fixes the tree T,
$\pi ^*(\dot C)=\dot C$
. Let 
. Since
$\pi ^*(p)=p$
,
$p\in H$
. Thus,
$$ \begin{align*}C=\dot C_G=\dot C_H=\{\langle n,i\rangle\mid i<n,\dot\varphi_H(\langle 0,n\rangle)(m)=i\}\end{align*} $$
because of the statement forced by p. But, we have
$$ \begin{align*}C_k=(\dot C_G)_k=\dot\varphi_G(\langle 0,k\rangle)\upharpoonright k,\end{align*} $$
while
$$ \begin{align*}(\dot C_H)_k=\dot\varphi_H(\langle 0,k\rangle)\upharpoonright k=\dot\varphi_G(\langle 0,\eta\rangle)\upharpoonright k,\end{align*} $$
which is impossible by our choice of
$\eta $
. Thus, we have reached the desired contradiction showing that
$C\notin \mathcal S$
.
Combining our observation about the complexity of the definition of the set C in the model
$\mathcal M$
with the fact that
$C\not \in \mathcal S$
, we obtain the following lemma.
Lemma 5.3. The set C is definable in
$\mathcal M$
from the parameter
$\dot \varphi _G(\langle 0\rangle )$
by a
$\Pi ^1_4$
-formula. Thus,
$\Sigma ^1_4$
-
$\mathrm {CA}$
fails in
$\mathcal M$
.
It remains to verify that
$\mathrm {AC}^{-p}$
holds in
$\mathcal M$
.
We will use the definitions of a full and undecided tree from Section 4 verbatim. An analogous proof to that of Lemma 4.5 gives
Lemma 5.4. Suppose that
$T\in L$
is a full countable subtree of
$\mathcal T$
,
$\varphi (x,X)$
is a second-order formula, and there is
$A\in L[G_T]$
such that
$\mathcal M\models \varphi (n,A)$
. Then there is a full undecided countable tree
$\bar T\in L$
and
$\bar A\in L[G_{\bar T}]$
such that
$\mathcal M\models \varphi (n,\bar A)$
.
Lemma 5.5. Suppose that
$T\in L$
is a full undecided countable subtree of
$\mathcal T$
and
$p,q\in \mathbb {P}(\mathbb J,\omega _1^{{<}\omega })$
are such that
$q\leq p\upharpoonright T$
. Then there is an automorphism
$\pi $
of
$\omega _1^{{<}\omega }$
fixing all nodes in T such that p is compatible with
$\pi ^*(q)$
and 
. Thus,
$\mathop {1\hskip -2.5pt \mathrm {l}}_{\mathbb {P}(\mathbb J,\omega _1^{{<}\omega })}\Vdash \dot {\mathcal S}=\pi ^*(\dot {\mathcal S})$
.
Proof. We define the automorphism
$\pi $
as follows. Suppose that
$s\in D_p\cap D_q$
and
$s\notin T$
. We first handle nodes of the form
$s=\langle \xi \rangle $
. In this case,
$\pi $
switches the tree
$(\omega _1^{{<}\omega })_{\langle \xi \rangle }$
with a tree
$(\omega _1^{{<}\omega })_{\langle \eta \rangle }$
for some
$\eta <\omega _1$
such that
$\langle \eta \rangle \notin T\cup D_p\cup D_q$
. Next, we handle nodes of the form
$s=\langle \xi ,n\rangle $
, for some
$n<\omega $
, which weren’t handled in the previous case (this must have been because
$\langle \xi \rangle \in T$
). In this case,
$\pi $
switches the tree
$(\omega _1^{{<}\omega })_{s}$
with a tree
$(\omega _1^{{<}\omega })_{t}$
, where
$t=\langle \xi ,\beta \rangle \notin T\cup D_p\cup D_q$
,
$\beta \geq \omega $
and
$$ \begin{align*}\dot\varphi_G(\langle \xi,n\rangle)(1)\upharpoonright n=\dot \varphi_G(\langle \xi,\beta\rangle)\upharpoonright n.\end{align*} $$
Note that such a node t must exist by density. Finally, if a node
$s=\langle \alpha _0,\ldots ,\alpha _n\rangle $
was not handled by one of the above cases, then
$\pi $
switches the tree
$(\omega _1^{{<}\omega })_{s}$
with a tree
$(\omega _1^{{<}\omega })_{t}$
, where
$t=\langle \alpha _0,\ldots ,\beta \rangle \notin T\cup D_p\cup D_q$
was not yet placed in the image of
$\pi $
by the above cases. All other nodes are fixed by
$\pi $
. In particular, all nodes in T are fixed by
$\pi $
.
Suppose that 
. Then it should be clear that
$T\in L$
is a countable subtree of
$\mathcal T$
if and only if 
is a countable subtree of
$\dot {\mathcal T}_H$
, which implies that 
.
Lemma 5.6.
$\mathcal M\models \mathrm {AC}^{-p}$
.
Proof. Suppose that
$\mathcal M\models \forall n\exists X\,\varphi (n,X)$
for some second-order arithmetic formula
$\varphi (n,X)$
. Given
$n<\omega $
, by Lemma 5.4, there is a full undecided countable subtree
$T_n\in L$
and
$X\in L[G_{T_n}]$
such that
$\mathcal M\models \varphi (n,X)$
. By extending
$T_n$
to a larger tree, if necessary, we can assume that
$\{\xi <\omega _1\mid \langle \xi \rangle \in T_n\}$
is an ordinal
$\alpha _n$
. Let
$\alpha =\bigcup _{n<\omega }\alpha _n$
and let T be the full undecided tree whose level 1 nodes are precisely
$\langle \xi \rangle $
for
$\xi <\alpha $
. Then each
$T_n$
is contained in T. Thus, for every
$n<\omega $
, there is some
$X\in L[G_T]$
such that
$\mathcal M\models \varphi (n,X)$
.
Fix a condition
$$ \begin{align*}p\Vdash \psi(\dot G_T,\dot{\mathcal S}):=\forall n\exists X\in L[\dot G_T]\,\langle \omega,+,\times,<,0,1,\dot{\mathcal S}\rangle\models\varphi(n,X).\end{align*} $$
Let’s argue that this statement is already forced by
$p\upharpoonright T$
. Suppose towards a contradiction that this is not the case. Then there is a condition
$q\leq p\upharpoonright T$
such that
$q\Vdash \neg \psi (\dot G_T,\dot {\mathcal S})$
. By Lemma 5.5, there is an automorphism
$\pi $
of
$\omega _1^{{<}\omega }$
fixing all nodes in T such that p is compatible with
$\pi ^*(q)$
and
$\mathop {1\hskip -2.5pt \mathrm {l}}_{\mathbb {P}(\mathbb J,\omega _1^{{<}\omega })}\Vdash \dot {\mathcal S}=\pi ^*(\dot {\mathcal S})$
. Observe that the condition
$\pi ^*(q)\Vdash \psi (\dot G_T,\dot {\mathcal S})$
because
$\pi ^*$
fixes
$\dot G_T$
and
$\mathop {1\hskip -2.5pt \mathrm {l}}_{\mathbb {P}(\mathbb J,\omega _1^{{<}\omega })}\Vdash \dot {\mathcal S}=\pi _f^*(\dot {\mathcal S})$
. Thus, we have reached the desired contradiction showing that
$p\upharpoonright T\Vdash \psi (\dot G_T,\dot {\mathcal S})$
. We can now assume without loss of generality that
$D_p\subseteq T$
.
Fix
$n<\omega $
. We will construct a mixed
$\mathbb {P}(\mathbb J,T)$
-name
$\dot X_n$
such that
$$ \begin{align*}p\Vdash \langle \omega,+,\times,<,0,1,\dot{\mathcal S}\rangle\models\varphi(n,\dot X_n).\end{align*} $$
For every
$r\leq p$
, there is a condition
$q\leq r$
and a
$\mathbb {P}(\mathbb J,T)$
-name
$\dot X^{q}_n$
such that
$$ \begin{align*}q\Vdash \langle \omega,+,\times,<,0,1,\dot{\mathcal S}\rangle\models\varphi(n,\dot X^q_n).\end{align*} $$
An analogous automorphism argument to above shows that actually
$$ \begin{align*}q\upharpoonright T\Vdash \langle \omega,+,\times,<,0,1,\dot{\mathcal S}\rangle\models\varphi(n,\dot X^q_n),\end{align*} $$
and so we can assume without loss of generality that
$D_q\subseteq T$
. Thus, we can construct a maximal antichain
$\mathcal A_n$
of such conditions q with
$D_q\subseteq T$
below p. By Proposition 2.3, it easy to see that
$\mathcal A_n$
is a maximal antichain of
$\mathbb {P}(\mathbb J,\omega _1^{{<}\omega })$
below p.
Let
$$ \begin{align*}\dot X_n=\bigcup_{q\in \mathcal A_n}\{(\tau,r)\mid r\leq q,D_r\subseteq T,r\Vdash \tau\in \dot X_n^{q}, \tau\in\text{dom}(\dot X_n^{q})\}.\end{align*} $$
Clearly,
$\dot X_n$
is a
$\mathbb {P}(\mathbb J,T)$
-name. Since
$\mathcal A_n$
is an antichain, if
$(\tau ,r)\in \dot X_n$
, then there is a unique
$q\in \mathcal A_n$
such that
$r\leq q$
. Fix an L-generic filter
$\bar G$
for
$\mathbb {P}(\mathbb J,\omega _1^{{<}\omega })$
with
$p\in \bar G$
. Let
$q\in \bar G\cap \mathcal A_n$
. We will argue that
$(\dot X_n)_{\bar G}=(\dot X^{q}_n)_{\bar G}$
. Suppose that
$a\in (\dot X_n)_{\bar G}$
. Then
$( \tau ,r)\in \dot X_n$
such that
$\tau _{\bar G}=a$
and
$r\in \bar G$
. It follows that r is compatible with q, which, since
$\mathcal A_n$
is an antichain, means that
$r\leq q$
. By definition of
$\dot X_n$
,
$r\Vdash \tau \in \dot X^{q}_n$
, which implies that
$a\in (\dot X^{q}_n)_{\bar G}$
. Next, suppose that
$a\in (\dot X^{q}_n)_{\bar G}$
. Then
$(\tau ,r)\in \dot X^{q}_n$
such that
$a=\tau _{\bar G}$
and
$r\in G$
. Let
$r'\in \bar G$
such that
$r'\leq r,q$
. Observe that
$r'\upharpoonright T\leq r,q$
and
$r'\upharpoonright T\in \bar G$
because it is above
$r'$
. Thus, we can assume without loss of generality that
$D_{r'}\subseteq T$
. Also, since
$r'\leq r$
,
$r'\Vdash \tau \in \dot X^{q}_n$
. Thus,
$(\tau ,r')\in \dot X_n$
, and so
$a\in (\dot X_n)_{\bar G}$
. Since
$\mathcal A_n$
was a maximal antichain below p, it follows that
$$ \begin{align*}p\Vdash \langle \omega,+,\times,<,0,1,\dot{\mathcal S}\rangle\models\varphi(n,\dot X_n).\end{align*} $$
Now, let
$\dot Y$
be a
$\mathbb {P}(\mathbb J,T)$
-name for the set whose n-th slice is
$\dot X_n$
. Then clearly,
$$ \begin{align*}p\Vdash\forall n<\omega\, \langle \omega,+,\times,<,0,1,\dot{\mathcal S}\rangle\models\varphi(n,\dot Y_n),\end{align*} $$
and
$\dot Y_G\in L[G_T]$
. Hence
$\dot Y_G\in \mathcal S$
.
6 Questions
In Sections 3 and 4, we obtained models
$\mathrm {Z}_2^{-p}+\Sigma ^1_2$
-
$\mathrm {CA}$
with a failure of
$\Sigma ^1_4$
-
$\mathrm {CA}$
in which
$\mathrm {Coll}^{-p}$
and
$\mathrm {AC}^{-p}$
holds respectively. Is it possible to obtain such models with an optimal failure of
$\Sigma ^1_3$
-
$\mathrm { CA}$
?
Question 6.1. Can we obtain a model of
$\mathrm {Z}_2^{-p}+\mathrm {Coll}^{-p}+\Sigma ^1_2$
-
$\mathrm {CA}$
in which, optimally,
$\Sigma ^1_3$
-
$\mathrm {CA}$
fails?
Question 6.2. Can we obtain a model of
$\mathrm {Z}_2^{-p}+\mathrm {AC}^{-p}+\Sigma ^1_2$
-
$\mathrm {CA}$
in which, optimally,
$\Sigma ^1_3$
-
$\mathrm {CA}$
fails?
Since standard arguments showing that
$\mathrm {AC}$
implies
$\mathrm {Z}_2$
over
$\mathrm {ACA}_0$
rely on parameters, it is most likely not the case that
$\mathrm {AC}^{-p}$
implies
$\mathrm {Z}_2^{-p}$
over
$\mathrm {ACA}_0$
.
Question 6.3. Can we obtain a model
$\mathrm {ACA}_0+\mathrm {AC}^{-p}$
in which
$\mathrm {Z}_2^{-p}$
fails?
This is not directly relevant to the results in this article, but for the complete understanding of forcing extensions by
$\mathbb {P}(\mathbb J,\omega ^{{<}\omega })$
, it is interesting to know whether the uniqueness result of Theorem 3.1 holds for countable trees and an analogous question applies to the forcing
$\mathbb {P}(\mathbb J,\omega _1^{{<}\omega })$
.
Question 6.4. Suppose that
$G\subseteq \mathbb {P}(\mathbb J,\omega ^{{<}\omega })$
is L-generic and that
$T\in L$
is a countable subtree of
$\omega ^{{<}\omega }$
. Is it true that the only L-generic sequences for
$\mathbb J_n$
in
$L[G_T]$
are the sequences
$\dot \varphi _G(s)$
for
$s\in T$
? What about an analogous question for uncountable subtrees and forcing extensions by
$\mathbb {P}(\mathbb J,\omega _1^{{<}\omega })$
?
