# Another proof that $\MM^{++}$ implies Woodin’s axiom $(*)$

Matteo Viale

###### Abstract.

Let $\MM^{++}(\kappa)$ state that the forcing axiom $\MM^{++}$ can be
instantiated only for stationary set preserving posets of size at most
$\kappa$. We give a detailed account of Asperò and Schindler’s proof that
$\MM^{++}(\kappa)+$_there are class many Woodin cardinals_ implies Woodin’s
axiom $(*)$ if $\Diamond_{\kappa}$ holds and $\kappa>\aleph_{2}$. Our
presentation takes advantage of the notion of consistency property:
specifically we rephrase Asperò and Schindler’s forcing as a specific
instantiation of the notion of “consistency property” used by Makkai, Keisler,
Mansfield and others in the study of infinitary logics. We also reorganize the
order of presentation of the various parts of the proof. Taken aside these
variations, our account is quite close to [1].

I thank Boban Veličković for suggesting the idea to relate Asperó and
Schindler’s forcing to consistency properties and for giving me key hints for
the proof of Lemma 2.10 and Fact 2.4. I also thank Ilijas Farah and Ben de
Bondt for the many useful comments. I take full responsibility for the errors
or gaps remaining.

I assume throughout this note that the reader is familiar with the key
properties of stationary set preserving forcings, knows the definition of
$\MM^{++}$ and what are its most important applications, and is familiar with
the theory of $\mathbb{P}_{\mathrm{max}}$ (for example as exposed in [3]).

I will try to make this paper as self-contained as possible.

What I will do is follow very closely Asperò and Schindler’s proof, while
reorganizing their presentation relating explicitly their forcing machinery to
the notion of consistency property introduced by Makkai and others to produce
models of theories in infinitary logics.

I give rightaway a fast account of the proof strategy of Asperò and
Schindler’s result, more detais and precise definitions will follow later on.

Following the proof pattern of Asperò and Schindler’s result I set up their
machinery in a slightly different terminology to design for each
$A\in\mathcal{P}\left(\omega_{1}\right)\setminus L(\mathbb{R})$ and $D$ dense
subset of $\mathbb{P}_{\mathrm{max}}$ universally Baire in the codes a
stationary set preserving forcing $P_{D,A}$ which instantiates the
$\Sigma_{1}$-sentence111$\Sigma_{1}$ in a signature admitting predicate
symbols for all the universally Baire sets, for the predicate
$\mathbf{NS}_{\omega_{1}}$ and for all properties defined by a
$\Delta_{0}$-formula. We will be more precise later on.:

> _There is a $\mathbf{NS}$-correct iteration of some $(N,I,a)\in D$ which
> maps $a$ to $A$._

Asperó and Schindler show that everything can be done assuming $V$ models
$\mathbf{NS}_{\omega_{1}}$_is saturated $+$ there are class many Woodin
cardinals_ with $P_{D,A}$ of size $\kappa$ for any $\kappa$ such that:

  * •

$\kappa\geq 2^{(2^{\aleph_{1}})}$;

  * •

$\Diamond_{\kappa}$ holds.

Now if $\MM^{++}(\mathfrak{c})$ holds, $\mathbf{NS}_{\omega_{1}}$ is
saturated, and $2^{\aleph_{1}}=\aleph_{2}$. Moreover $\Diamond_{\kappa}$ can
be established for $\kappa=\aleph_{3}$ by a stationary set preserving forcing
of size $2^{\aleph_{2}}$ which does not add new subets of $\aleph_{2}$.
Putting everything together, we get that $\MM^{++}(2^{\aleph_{2}})+$_there are
class many Woodin cardinals_ implies the following

> _For any $A\in\mathcal{P}\left(\omega_{1}\right)\setminus L(\mathbb{R})$
> such that $L[A]$ computes correctly $\omega_{1}$, and any $D$ dense subset
> of $\mathbb{P}_{\mathrm{max}}$ universally Baire in the codes there is a
> $\mathbf{NS}$-correct iteration of some $(N,I,a)\in D$ which maps $a$ to
> $A$._

This is an even stronger version of $(*)$.

The following is the key consequence of the existence of class many Woodin
cardinals we will need:

> __
>
> $(H_{\omega_{1}}^{V},\in,B)\prec(H_{\omega_{1}}^{V[G]},\in,B^{V[G]})$
>
> _for all $B$ universally Baire set in $V$ and all generic extensions $V[G]$
> of $V$. _

This property holds assuming class many Woodin cardinals.

The presentation is structured as follows:

  * •

Section 1 gives the main definitions and a review of the results in the
literature on which one leverages to establish that $\MM^{++}$ implies $(*)$.
This is just to make this paper completely self-contained. The reader familiar
with $\mathbb{P}_{\mathrm{max}}$, $\MM^{++}$ etc. can skip this part; proper
references to the results presented in this section are in any case given at
the appropriate stages of this paper.

  * •

Section 2 states the main result (which is just rephrasing in our set up
Schindler’s and Asperò’s main theorem) while introducing the key concept of
semantic certificate222Our notion of semantic certificate is slightly
different from the one appearing in [1], but in spirit it has the same
effects.. Roughly a semantic certificate for
$A\in\mathcal{P}\left(\omega_{1}\right)\setminus L(\mathbb{R})$ and $D\in
L(\mathbb{R})$ dense subset of $\mathbb{P}_{\mathrm{max}}$ existing in some
generic extension $V[G]$ of $V$ (possibly collapsing $\omega_{1}^{V}$ to
countable) is a tuple $(\mathcal{J},r,f,T)$ such that $\mathcal{J}$ is an
iteration of length $\omega_{1}^{V}$ of some $P_{\max}$ condition $(N,I,a)\in
D^{V[G]}$ mapping $a$ to $A$ but _with no evident obstruction to the fact that
$\mathcal{J}$ is $\mathbf{NS}$-correct and belongs to a stationary set
preserving extension of $V$_ (the other elements $r,f,T$ play a crucial role
which will be outlined at the proper stage).

The main result states that there is a stationary set preserving forcing
$P_{D,A}$ of size $\kappa$ generically adding a semantic certificate
$(\mathcal{J}_{G},r_{G},f_{G},T_{G})$ for $D,A$ and such that in any generic
extension $V[G]$ of $V$ by $P_{D,A}$, $\mathcal{J}_{G}$ is really a
$\mathbf{NS}$-correct iteration in $V[G]$.

In 2.1 we prove the first approximations to this result, i.e. the existence of
semantic certificates333This corresponds to [1, Lemma 3.2]. Here we also pay
attention to explain how to get the tree $T$ appearing in [1, eqn. (8) pag.
16] and its role in their proof. in generic extensions collapsing
$\omega_{2}^{V}$ to countable (cfr. Lemma 2.10 — corresponding to [1, Lemma
3.2]).

  * •

Section 3 proves the main result:

    * –

In Section 3.1 we introduce the notion of forcing given by consistency
properties and establish some general facts about these types of forcings.
Specifically a consistency property given by a class of structures
$\mathcal{C}$ for a signature $\mathcal{L}$ is the family of finite sets of
atomic (or negated atomic) $\mathcal{L}$-sentences which are realized by some
structure in $\mathcal{C}$. Now this is naturally a forcing notion
$P_{\mathcal{C}}$ ordered by reverse inclusion. When things are properly
organized a generic filter for $P_{\mathcal{C}}$ produces a term model in
$\mathcal{C}$.

    * –

In Section 3.2 we introduce and analyze a specific instance of these forcings:
the forcing $P^{*}_{0}$ (which corresponds to the forcing $\mathbb{P}_{0}$ in
the sequence of forcings
$\left\\{\mathbb{P}_{\alpha}:\alpha\leq\kappa\right\\}$ of [1]) and show that
it gives an elegant way to produce generic term-models whose transitive
collapse are semantic certificates (cfr. Fact 3.21 – corresponding to [1,
Lemma 3.3]). Unfortunately this forcing cannot be provably stationary set
preserving since it has size continuum and Woodin has shown that
$\MM^{++}(\mathfrak{c})$ is consistent with the negation of $(*)$ [7, Thm.
10.90].

    * –

In Section 3.3 we introduce and analyze the forcings
$\left\\{P_{\alpha}:\alpha\in C\cup\left\\{\kappa\right\\}\right\\}$ indexed
by a club subset $C$ of $\kappa$ (corresponding to the sequence of forcings
$\left\\{\mathbb{P}_{\alpha}:\alpha\leq\kappa\right\\}$ of [1]), and we prove
the main Theorem 3.33 (corresponding to [1, Lemma 3.8, Corollary 3.9]) stating
that $P_{\kappa}$ is stationary set preserving and generically adds a
$\mathbf{NS}$-correct iteration witnessing that $G_{A}\cap D$ is non
empty444$G_{A}$ is the $P_{\max}$-filter given by the conditions $(N,I,a)$
which correctly iterate $a$ to $A$, more details later.. The forcings
$P_{\alpha}$ are also consistency properties of the form
$P_{\mathcal{W}_{\alpha}}$, but now $\mathcal{W}_{\alpha}$ is designed so that
$P_{\mathcal{W}_{\alpha}}$ adds generically countable substructures of
$H_{\kappa}^{V}$ which can be used to seal $P_{\alpha}$-names for
clubs555Roughly these countable structures can be used to witness that a given
stationary set of $V$ on $\omega_{1}^{V}$ is met by a given $P_{\alpha}$-name
for a club subset of $\omega_{1}^{V}$.. $\Diamond_{\kappa}$ is then used to
show that this sealing process is completed at stage $\kappa$ as all
$P_{\kappa}$-names for clubs are guessed at some stage $\alpha<\kappa$ and
sealed by the trace on $P_{\alpha}$ of the generic filter for $P_{\kappa}$.
This roughly outlines why $P_{\kappa}$ should be stationary set preserving.

I decided to be overly cautious and to outline where the arguments require the
existence of class many Woodin cardinals, and why they cannot go through with
weaker assumptions. This might be annoying for some readers, I apologize for
that.

Let us remark once more that:

  1. (A)

This work is just a re-elaboration of Asperó and Schindler’s result, the key
ideas are all appearing in [1]. Here we reformulate them in a slightly
different terminology and give an alternative presentation of this proof.

  2. (B)

This work wouldn’t exist without Boban Velickovic’s suggestion to relate
Asperó and Schindler’s work to the notion of _consistency property_ used in
infinitary logic (consistency properties are particularly useful if one wants
to produce models of a certain first order theory omitting certain prescribed
types). This is somewhat implicit in Asperó and Schindler’s work and we make
it explicit here.

It is also convenient before proceeding to introduce the following short-hand
notation to denote $\mathcal{L}$-structures for a first order signature
$\mathcal{L}$:

######  Notation 1.

Given a signature $\tau$, we denote an $\mathcal{L}$-structure
$\mathcal{M}=(M,R^{\mathcal{M}}:R\in\tau)$ by $(M,\tau^{\mathcal{M}})$.

Later on we will need a similar notation for multi-sorted structures (see
Section 3.2).

##  1\. Main result and background material on $\mathbb{P}_{\mathrm{max}}$,
universally baire sets and $\MM^{++}$

Let us first set up the proper language and terminology in order to deal with
the $\mathbb{P}_{\mathrm{max}}$-technology and to state our main result.

$\mathsf{ZFC}^{-}$ denotes $\mathsf{ZFC}$ minus the powerset axiom.

######  Definition 1.1.

A countable transitive set $M$ is an iterable structure if it models
$\mathsf{ZFC}^{-}+$_there exists an uncountable cardinal_ and for some
transitive $N\supseteq M$:

  * •

$N$ models $\mathsf{ZFC}+\mathbf{NS}_{\omega_{1}}$_is precipitous_ ,

  * •

$\omega_{2}^{N}$ is a countable ordinal in $V$,

  * •

$\operatorname{otp}(N\cap\mathrm{Ord})\geq\omega_{1}^{V}$,

  * •

$H_{\omega_{2}}^{N}=H_{\omega_{2}}^{M}$,

  * •

if $A\in N$ is a maximal antichain of
$(\mathcal{P}\left(\omega_{1}\right)/_{\mathbf{NS}})^{M}$, then $A\in M$.

For example if $N$ is transitive, models $\mathsf{ZFC}$, $\omega_{2}^{N}$ is a
countable ordinal, and $\operatorname{otp}(N\cap\mathrm{Ord})\geq\omega_{1}$,
then $M=H_{\omega_{2}}^{N}$ is an iterable structure if $N$ models
$\mathbf{NS}_{\omega_{1}}$_is saturated_ ; while so is $M=H_{\kappa}^{N}$ for
any countable (in $V$) cardinal (of $N$) $\kappa>(2^{\aleph_{2}})^{N}$ in $N$
if $N$ just models $\mathbf{NS}_{\omega_{1}}$_is precipitous_ (see [3, Lemma
1.5] for the ratio of this definition).

######  Definition 1.2.

[3, Def. 1.2] Let $M$ be an iterable structure. Let $\gamma$ be an ordinal
less than or equal to $\omega_{1}$. An iteration $\mathcal{J}$ of $M$ of
length $\gamma$ consists of a family of transitive models $\langle
M_{\alpha}:\,\alpha\leq\gamma\rangle$, sets $\langle
G_{\alpha}:\,\alpha<\gamma\rangle$ and a commuting family of elementary
embeddings

$\langle j_{\alpha\beta}:M_{\alpha}\to
M_{\beta}:\,\alpha\leq\beta\leq\gamma\rangle$

such that:

  1. (1)

$M_{0}=M$,

  2. (2)

each $G_{\alpha}$ is an $M_{\alpha}$-generic filter for
$(\mathcal{P}\left(\omega_{1}\right)/\mathbf{NS}_{\omega_{1}})^{M_{\alpha}}$,

  3. (3)

each $j_{\alpha\alpha}$ is the identity mapping,

  4. (4)

each $j_{\alpha\alpha+1}$ is the ultrapower embedding induced by $G_{\alpha}$,

  5. (5)

for each limit ordinal $\beta\leq\gamma$, $M_{\beta}$ is the direct limit of
the system
$\left\\{M_{\alpha},j_{\alpha\delta}:\,\alpha\leq\delta<\beta\right\\}$, and
for each $\alpha<\beta$, $j_{\alpha\beta}$ is the induced embedding.

An iteration

$\mathcal{J}=\langle j_{\alpha\beta}:M_{\alpha}\to
M_{\beta}:\,\alpha\leq\beta\leq\omega_{1}\rangle$

existing in $V$ is $\mathbf{NS}$-correct if

$M_{\omega_{1}}\cap\mathbf{NS}_{\omega_{1}}^{V}=\mathbf{NS}_{\omega_{1}}^{M_{\omega_{1}}}.$

From now we will just write _correct_ in place of $\mathbf{NS}$-correct.

We adopt the convention to denote an iteration $\mathcal{J}$ just by $\langle
j_{\alpha\beta}:\,\alpha\leq\beta\leq\gamma\rangle$, we also stipulate that if
$X$ denotes the domain of $j_{0\alpha}$, $X_{\alpha}$ or $j_{0\alpha}(X)$
denotes the domain of $j_{\alpha\beta}$ for any $\alpha\leq\beta\leq\gamma$.

######  Fact 1.3.

[3, Lemma 1.5, Lemma 1.6] Assume $(M,\in)$ is iterable. Then for any ordinal
$\gamma\leq\omega_{1}^{V}$ any iteration

$\mathcal{J}=\langle j_{\alpha\beta}:M_{\alpha}\to
M_{\beta}:\,\alpha\leq\beta<\gamma\rangle$

induced by filters $\langle G_{\alpha}:\,\alpha<\gamma\rangle$ is such that
the structure $M_{\gamma}$ obtained in accordance with666I.e.
$(M_{\gamma},E_{\gamma})$ is the direct limit of $\mathcal{J}$ if $\gamma$ is
limit, or the ultrapower of $(M_{\alpha},\in)$ by $G_{\alpha}$ if
$\gamma=\alpha+1$, see [3, Section 1] for details. Def. 1.2 is well-founded
hence isomorphic to its transitive collapse.

A trivial fact is that for an iteration

$\mathcal{J}=\left\\{j_{\alpha\beta}:\,N_{\alpha}\to
N_{\beta}:\,\alpha\leq\beta\leq\gamma\right\\}$

and $\alpha<\beta$, $N_{\alpha}$ and $N_{\beta}$ are both transitive but in
general it holds that $N_{\alpha}\not\subseteq N_{\beta}$.

Notice that $M$ is iterable if and only if it is $\emptyset$-iterable.

######  Definition 1.4.

[3, Def. 2.1] $\mathbb{P}_{\mathrm{max}}$ is the subset of $H_{\omega_{1}}$
given by the pairs $(M,a)$ such that

  * •

$M$ is iterable, countable, and models Martin’s axiom.

  * •

$a\in\mathcal{P}\left(\omega_{1}\right)^{M}\setminus L(\mathbb{R})^{M}$, and
there exists $r\in\mathcal{P}\left(\omega\right)\cap M$ such that
$\omega_{1}^{M}=\omega_{1}^{L[a,r]}$.

$(M,a)\leq(N,b)$ if there exists $\mathcal{J}=\langle
j_{\alpha\beta}:\,\alpha\leq\beta\leq\omega_{1}^{M}\rangle$ in $M$ iteration
of $N$ of length $\omega_{1}^{M}$ such that $j_{0\omega_{1}^{M}}(b)=a$ and
$(M,\in)$ models that $\mathcal{J}$ is correct.

Note that $\mathbb{P}_{\mathrm{max}}$ is a definable class in
$(H_{\omega_{1}},\in)$; in particular it belongs to any transitive model of
$\mathsf{ZFC}^{-}$ containing $\mathcal{P}\left(\omega\right)$.

Our definition of $\mathbb{P}_{\mathrm{max}}$ is slightly different than the
one given in [3], but it defines an equivalent of the poset defined in [3,
Def. 2.1] in view of the following777Much weaker large cardinals assumptions
are needed, we don’t spell the optimal hypothesis.:

######  Fact 1.5.

Let $\mathbb{P}_{\mathrm{max}}^{0}$ be the forcing $\mathbb{P}_{\mathrm{max}}$
as defined in [3, Def. 2.1]. Assume there are class many Woodin cardinals.

Then for every condition $(M,I,a)$ in $\mathbb{P}_{\mathrm{max}}^{0}$ there is
a condition $(N,b)$ in $\mathbb{P}_{\mathrm{max}}$ and an iteration $\langle
j_{\alpha\beta}:\,\alpha\leq\beta\leq\omega_{1}^{N}\rangle\in N$ of $(M,I)$
according to [3, Def. 1.2] such that
$j_{0\omega_{1}^{N}}(I)=\mathbf{NS}_{\omega_{1}}^{N}\cap
j_{0\omega_{1}^{N}}[M]$ and $j_{0}(a)=b$.

Conversely assume $N$ is iterable and $\delta$ is Woodin in $N$. Let $G$ be
$N$-generic for some $P\in N$ forcing $\mathbf{NS}_{\omega_{1}}$ is
precipitous and Martin’s axiom. Then
$(H_{\kappa}^{N[G]},\mathbf{NS}_{\omega_{1}}^{N[G]},a)\in\mathbb{P}_{\mathrm{max}}^{0}$
for all $a\in\mathcal{P}\left(\omega_{1}\right)^{N[G]}\setminus
L(\mathbb{R})^{N[G]}$ such that there exists
$r\in\mathcal{P}\left(\omega\right)\cap N[G]$ with
$\omega_{1}^{M}=\omega_{1}^{L[a,r]}$ with $\kappa=(2^{\aleph_{1}})^{+}$ in
$N[G]$.

###### Proof.

Only the first part is non-trivial. Let $\gamma>\delta$ be two Woodin
cardinals. Let $X\prec V_{\gamma}$ be countable with $\delta,(M,I,a)\in X$.
Let $N_{0}$ be the transitive collapse of $X$, and $N$ be a generic extension
of $N_{0}$ by a forcing collapsing $\delta$ to become $\omega_{2}$ and forcing
$\mathbf{NS}_{\omega_{1}}$ is precipitous and Martin’s axiom. Since $\gamma$
is Woodin, there are class many measurables in $V_{\gamma}$, hence $N_{0}$ is
iterable and so is $N$ (by [3, Thm. 4.10]).

By [3, Lemma 2.8] there is in $N$ the required iteration $\langle
j_{\alpha\beta}:\,\alpha\leq\beta\leq\omega_{1}^{N}\rangle$ of $(M,I)$ and we
can set $b=j_{0\omega_{1}^{N}}(a)$. ∎

In particular (at the prize of assuming the right large cardinal assumptions)
the forcings $\mathbb{P}_{\mathrm{max}}$ and $\mathbb{P}_{\mathrm{max}}^{0}$
are equivalent.

Let from now on UB denote the class of universally Baire sets888See Section
1.3 below for details..

######  Definition 1.6.

$(*)$-$\mathsf{UB}$ holds in $V$ if:

  * •

There are class many Woodin cardinals.

  * •

For any $A\in\mathcal{P}\left(\omega_{1}\right)\setminus L(\text{{\sf UB}})$
such that $\omega_{1}^{L[A]}=\omega_{1}^{V}$:

    * –

the set

$\displaystyle G_{A}=$
$\displaystyle\\{(M_{0},a)\in\mathbb{P}_{\mathrm{max}}:\,\exists\mathcal{J}\text{
correct iteration of }M_{0}\text{ such that }$ $\displaystyle
j_{0\omega_{1}}(a)=A\text{ and }\mathbf{NS}_{\omega_{1}}^{L(\text{{\sf
UB}})[G]}\cap M_{\omega_{1}}=\mathbf{NS}_{\omega_{1}}^{M_{\omega_{1}}}\\}$

is a filter on $\mathbb{P}_{\mathrm{max}}$;

    * –

$G_{A}$ meets all dense subsets of $\mathbb{P}_{\mathrm{max}}$ which are
universally Baire in the codes999$D$ is universally Baire in the codes if
there is a universally Baire set $B$ such that $D=\text{{\rm Cod}}[B]$ (See
Def. 1.12). Note that assuming the existence of class many Woodin cardinals
any set of reals definable in $L(\mathbb{R})$ is universally Baire.;

    * –

$\mathcal{P}\left(\omega_{1}\right)\subseteq L(\mathbb{R})[A]$.

  * •

$\mathbf{NS}_{\omega_{1}}$ is precipitous in $V$.

Note that the above is expressible as a schema of $\Pi_{2}$-sentences in the
signature $\tau_{\mathbf{NS}_{\omega_{1}},\text{{\sf UB}}}$ which admits
predicate symbols for all $\Delta_{0}$-properties, all universally Baire sets,
and the non-stationary ideal $\mathbf{NS}_{\omega_{1}}$, and constant symbols
for $\omega_{1},\omega,\emptyset$ (see Proposition 1.24).

The rest of this paper will give a proof of the following remarkable result:

######  Theorem 1.7 (Asperó, Schindler [1]).

Assume there are class many Woodin cardinals and $\MM^{++}(\kappa)$ holds for
$\kappa=2^{\aleph_{2}}$. Then so does $(*)$-$\mathsf{UB}$.

Our proof is a variation of Asperó and Schindler’s argument which reorganizes
slightly their presentation while following its streamline.

### Strategy of the proof

We will use the following result:

######  Theorem 1.8.

[3, Thm. 5.1, Thm. 6.3, Thm 7.7] Assume in $V$ there are class many Woodin
cardinals. Let $G$ be $L(\mathbb{R})$-generic for $\mathbb{P}_{\mathrm{max}}$.
Then in $L(\mathbb{R})[G]$ it holds that:

  * •

$\psi_{\mathrm{AC}}$ and Martin’s axiom hold and therefore,
$2^{\omega}=2^{\omega_{1}}=\omega_{2}$.

  * •

$\mathbf{NS}_{\omega_{1}}$ is saturated.

  * •

For any $A\in\mathcal{P}\left(\omega_{1}\right)^{L(\mathbb{R})[G]}\setminus
L(\text{{\sf UB}})$

$\displaystyle G_{A}=$
$\displaystyle\\{(M_{0},a)\in\mathbb{P}_{\mathrm{max}}:\,\exists\mathcal{J}\text{
correct iteration of }M_{0}\text{ such that }$ $\displaystyle
j_{0\omega_{1}}(a)=A\text{ and }\mathbf{NS}_{\omega_{1}}^{L(\text{{\sf
UB}})[G]}\cap M_{\omega_{1}}=\mathbf{NS}_{\omega_{1}}^{M_{\omega_{1}}}\\}$

is an $L(\mathbb{R})$-generic filter for $\mathbb{P}_{\mathrm{max}}$ and such
that $L(\mathbb{R})[G_{A}]=L(\mathbb{R})[G]$.

In particular to establish that $(*)\text{-}\mathsf{UB}$ holds in $V$ it
suffices to prove that:

  1. (1)

There are class many Woodin cardinals;

  2. (2)

$\mathbf{NS}_{\omega_{1}}^{V}$ is saturated;

  3. (3)

For some fixed $A$ in $\mathcal{P}\left(\omega_{1}\right)^{V}\setminus
L(\text{{\sf UB}})$, $G_{A}$ is a filter for $\mathbb{P}_{\mathrm{max}}$
meeting all dense subsets of $\mathbb{P}_{\mathrm{max}}$ universally Baire in
the codes, and
$\mathcal{P}\left(\omega_{1}\right)^{V}\subseteq\mathcal{P}\left(\omega_{1}\right)^{L(\mathbb{R})[G_{A}]}$
($G_{A}$ will also be $L(\mathbb{R})$-generic since all sets of reals
definable in $L(\mathbb{R})$ are universally Baire in the codes assuming class
many Woodin cardinals).

Assuming $\MM^{++}(\mathfrak{c})$ and the existence of class many Woodin
cardinals, the first two conditions are automatically met. The proof of [3,
Lemma 7.6] (but not its statement) actually shows that if $V$ models that
$\mathbf{NS}_{\omega_{1}}$ is saturated, then $G_{A}$ (as computed in $V$) is
a filter on $\mathbb{P}_{\mathrm{max}}$ for any
$A\in\mathcal{P}\left(\omega_{1}\right)^{V}\setminus L(\mathbb{R})$ such that
$L[A]$ computes correctly $\omega_{1}$.

Clearly $L(\mathbb{R})[A]=L(\mathbb{R})[G_{A}]$. Also $\MM^{++}(\mathfrak{c})$
entails that $\mathcal{P}\left(\omega_{1}\right)^{V}\subseteq
L(\mathbb{R})[A]$ (since for example it entails $\psi_{\mathrm{AC}}$ [3,
Section 6] or Martin’s axiom). So the unique missing point is to check that
$G_{A}$ is a filter meeting all dense subsets of $\mathbb{P}_{\mathrm{max}}$
universally Baire in the codes assuming $\MM^{++}$.

There is a natural strategy:

######  Strategy 1.9.

Given $D\subseteq\mathbb{P}_{\mathrm{max}}$ dense and universally Baire in the
codes and $A\in\mathcal{P}\left(\omega_{1}\right)^{V}\setminus L(\text{{\sf
UB}})$, find a forcing $P_{D,A}$ such that if $G$ is $V$-generic for $P_{D,A}$
in $V[G]$ there is an iteration

$\mathcal{K}=\langle k_{\alpha\beta}:M_{\alpha}\to
M_{\beta}:\,\alpha\leq\beta\leq\omega_{1}^{V}\rangle$

such that in $V[G]$:

  1. (1)

$(M_{0},A\cap\omega_{1}^{M_{0}})\in D$,

  2. (2)

$k_{0\omega_{1}^{V}}(A\cap\omega_{1}^{M_{0}})=A$,

  3. (3)

$H_{\omega_{2}}^{V}\subseteq M_{\omega_{1}^{V}}$ and
$\mathbf{NS}_{\omega_{1}}^{M_{\omega_{1}^{V}}}\cap
V=\mathbf{NS}_{\omega_{1}}^{V}$,

  4. (4)

$\mathbf{NS}_{\omega_{1}}^{M_{\omega_{1}^{V}}}=\mathbf{NS}_{\omega_{1}}^{V[G]}\cap
M_{\omega_{1}^{V}}$.

Assume the above is possible. Then $P_{D,A}$ is stationary set preserving
since:

$\mathbf{NS}_{\omega_{1}}^{V}=\mathbf{NS}_{\omega_{1}}^{M_{\omega_{1}^{V}}}\cap
V=\mathbf{NS}_{\omega_{1}}^{V[G]}\cap M_{\omega_{1}^{V}}\cap
H_{\omega_{2}}^{V}=\mathbf{NS}_{\omega_{1}}^{V[G]}\cap
H_{\omega_{2}}^{V}=\mathbf{NS}_{\omega_{1}}^{V[G]}\cap V.$

Now the statement

$\exists\mathcal{K}\,[(\mathcal{K}\text{ is a correct
iteration})\wedge((M_{0},a)\in D)\wedge k_{0\omega_{1}}(a)=A]$

is a $\Sigma_{1}$-formula in parameter $A$ in the language $\tau_{\text{{\sf
ST}}}\cup\left\\{B,\omega_{1},\mathbf{NS}_{\omega_{1}}\right\\}$ where
$\tau_{\text{{\sf ST}}}$ is a signature admitting predicate symbols for all
$\Delta_{0}$-functions and relations and $B$ is a universally Baire set coding
$D$ in some absolute manner.

If $P_{D,A}$ has size $\kappa\geq\mathfrak{c}$, and $\MM^{++}(\kappa)$ holds
in $V$ this $\Sigma_{1}$-statement is reflected to $V$.

Let us first address the issues of defining properly:

  * •

What is the meaning of _“ $\tau_{\text{{\sf ST}}}$ is a signature admitting
predicate symbols for all $\Delta_{0}$-functions and relations and $B$ is a
universally Baire set coding $D$ in some absolute manner”_.

  * •

What is the meaning of _“The formula_

$\exists\mathcal{K}\,[(\mathcal{K}\text{ is a correct
iteration})\wedge((M_{0},a)\in D)\wedge k_{0\omega_{1}}(a)=A]$

_is a $\Sigma_{1}$-formula in parameter $A$ in the language $\tau_{\text{{\sf
ST}}}\cup\left\\{B,\omega_{1},\mathbf{NS}_{\omega_{1}}\right\\}$”_.

  * •

Why $\MM^{++}$ holding in $V$ entails that $\Sigma_{1}$-formulae in parameter
$A\in H_{\omega_{2}}$ for the language $\tau_{\text{{\sf
ST}}}\cup\left\\{B,\omega_{1},\mathbf{NS}_{\omega_{1}}\right\\}$ holding in a
generic extension by a stationary set preserving forcing are reflected to $V$.

###  1.1. The signature $\tau_{\text{{\sf ST}}}$

######  Notation 1.10.

__

  * •

$\tau_{\mathsf{ST}}$ is the extension of the first order signature
$\left\\{\in\right\\}$ for set theory which is obtained by adjoining predicate
symbols $R_{\phi}$ of arity $n$ for any $\Delta_{0}$-formula
$\phi(x_{1},\dots,x_{n})$, and constant symbols for $\omega$ and $\emptyset$.

  * •

$\mathsf{ZFC}^{-}$ is the $\in$-theory given by the axioms of $\mathsf{ZFC}$
minus the power-set axiom.

  * •

$T_{\text{{\sf ST}}}$ is the $\tau_{\text{{\sf ST}}}$-theory given by the
axioms

$\forall\vec{x}\,(R_{\forall x\in y\phi}(y,\vec{x})\leftrightarrow\forall
x(x\in y\rightarrow R_{\phi}(y,x,\vec{x}))$
$\forall\vec{x}\,[R_{\phi\wedge\psi}(\vec{x})\leftrightarrow(R_{\phi}(\vec{x})\wedge
R_{\psi}(\vec{x}))]$
$\forall\vec{x}\,[R_{\neg\phi}(\vec{x})\leftrightarrow\neg R_{\phi}(\vec{x})]$

for all $\Delta_{0}$-formulae $\phi(\vec{x})$, together with the
$\Delta_{0}$-sentences

$\forall x\in\emptyset\,\neg(x=x),$ $\omega\text{ is the first infinite
ordinal}$

(the former is an atomic $\tau_{\text{{\sf ST}}}$-sentence, the latter is
expressible as the atomic sentence for $\tau_{\text{{\sf ST}}}$ stating that
$\omega$ is a non-empty limit ordinal and all its elements are successor
ordinals or $0$).

  * •

$\mathsf{ZFC}^{-}_{\text{{\sf ST}}}$ is the $\tau_{\text{{\sf ST}}}$-theory

$\mathsf{ZFC}^{-}\cup T_{\text{{\sf ST}}},$

accordingly we define $\mathsf{ZFC}_{\text{{\sf ST}}}$.

In $\mathsf{ZFC}_{\text{{\sf ST}}}$ many absolute concepts (such as that of
being a function) are now expressed by an atomic formula, while certain more
complicated ones (for example those defined by means of transfinite recursion
over an absolute property, such as _$x$ is the transitive closure of $y$_) can
still be expressed by means of $\mathsf{ZFC}^{-}_{\text{{\sf ST}}}$-provably
$\Delta_{1}$-properties of $\tau_{\text{{\sf ST}}}$ (i.e. properties which are
$\mathsf{ZFC}^{-}_{\text{{\sf ST}}}$-provably equivalent at the same time to a
$\Pi_{1}$-formula and to a $\Sigma_{1}$-formula), hence are still absolute
between any two models (even non-transitive) $\mathcal{M}$, $\mathcal{N}$ of
$\mathsf{ZFC}_{\text{{\sf ST}}}$ of which one is a substructure of the other.
On the other hand many definable properties have truth values which may vary
depending on which model of $\mathsf{ZFC}_{\text{{\sf ST}}}$ we work in (for
example _$\kappa$ is an uncountable cardinal_ is a
$\Pi_{1}\setminus\Sigma_{1}$-property in $\mathsf{ZFC}_{\text{{\sf ST}}}$
whose truth value may depend on the choice of the model of
$\mathsf{ZFC}_{\text{{\sf ST}}}$ to which $\kappa$ belongs).

###  1.2. Absolute codings of subsets of $H_{\omega_{1}}$ and Shoenfield’s
absoluteness

We define second order number theory as the first order theory of the
structure

$(\mathcal{P}(\mathbb{N})\cup\mathbb{N},\in,\subseteq,=,\mathbb{N}).$

$\Pi^{1}_{n}$-sets (respectively $\Sigma^{1}_{n}$, $\Delta^{1}_{n}$) are the
subsets of $\mathcal{P}(\mathbb{N})\equiv 2^{\mathbb{N}}$ defined by a
$\Pi_{n}$-formula (respectively by a $\Sigma_{n}$-formula, at the same time by
a $\Sigma_{n}$-formula and a $\Pi_{n}$-formula in the appropriate language),
if the formula defining a set $A\subseteq(2^{\mathbb{N}})^{n}$ has some
parameter $\vec{r}\in(2^{\mathbb{N}})^{<\omega}$ we accordingly write that $A$
is $\Pi^{1}_{n}(\vec{r})$ (respectively $\Sigma^{1}_{n}(\vec{r})$,
$\Delta^{1}_{n}(\vec{r})$). if the formula defining a set
$A\subseteq(2^{\mathbb{N}})^{n}$ uses an extra-predicate symbol
$B\subseteq(2^{\omega})^{k}$ we write that $A$ is $\Pi^{1}_{n}(B)$
(respectively $\Sigma^{1}_{n}(B)$, $\Delta^{1}_{n}(B)$).

$A\subseteq(2^{\mathbb{N}})^{N}$ is projective if it is defined by some
$\Pi^{1}_{n}$-property for some $n$. Similarly we define the notion of being
projective in $\vec{r}\in(2^{\mathbb{N}})^{<\omega}$ or
$B\subseteq(2^{\omega})^{k}$.

######  Remark 1.11.

$A\subseteq(2^{\mathbb{N}})^{k}$ is projective in some
$\vec{r}\in(2^{\mathbb{N}})^{<\omega}$ if and only if it is obtained by a
Borel subset of $(2^{\mathbb{N}})^{m}$ by successive applications of the
operations of projection on one coordinate and complementation.

######  Definition 1.12.

Given $a\in H_{\omega_{1}}$, $r\in 2^{\mathbb{N}}$ codes $a$, if (modulo a
recursive bijection of $\mathbb{N}$ with $\mathbb{N}^{2}$), $r$ codes a well-
founded extensional relation on $\mathbb{N}$ whose transitive collapse is the
transitive closure of $\\{a\\}$.

  * •

$\mathrm{Cod}:2^{\mathbb{N}}\to H_{\omega_{1}}$ is the map assigning $a$ to
$r$ if and only if $r$ codes $a$ and assigning the emptyset to $r$ otherwise.

  * •

$\mathrm{WFE}$ is the set of $r\in 2^{\mathbb{N}}$ which (modulo a recursive
bijection of $\mathbb{N}$ with $\mathbb{N}^{2}$) are a well founded
extensional relation on $\mathbb{N}$ whose transitive collapse is the
transitive closure of $\\{a\\}$.

The following are well known facts101010See [2, Section 25] and in particular
the statement and proof of Lemma 25.25, which contains all ideas on which one
can elaborate to draw the conclusions below..

######  Remark 1.13.

The map $\mathrm{Cod}$ is defined by a $\mathsf{ZFC}^{-}$-provably
$\Delta_{1}$-property (with no parameters) over $H_{\omega_{1}}$ and is
surjective. Moreover $\mathrm{WFE}$ is a $\Pi^{1}_{1}$-subset of
$2^{\mathbb{N}}$. Therefore if $N$ is a transitive model of $ZFC^{-}$ existing
in some transitive model $W$ of $\mathsf{ZFC}$, $N$ computes correctly
$\mathrm{Cod}$ and $\mathrm{WFE}$, i.e. $\mathrm{Cod}^{N}=\mathrm{Cod}^{W}\cap
N$ and $\mathrm{WFE}^{N}=\mathrm{WFE}^{W}\cap N$.

######  Lemma 1.14.

Assume $B\subseteq 2^{\omega}$. Let $A\subseteq 2^{\mathbb{N}}$ be a
$\Sigma^{1}_{n+1}(B)$ set. Then $A$ is $\Sigma_{n}$-definable in the structure
$(H_{\omega_{1}},\tau_{\text{{\sf ST}}}^{V},B)$ in the language
$\tau_{\text{{\sf ST}}}\cup\left\\{B\right\\}$. Conversely if $A$ is
$\Sigma_{n}$-definable in the structure $(H_{\omega_{1}},\tau_{\text{{\sf
ST}}}^{V},B)$ in the language $\tau_{\text{{\sf ST}}}\cup\left\\{B\right\\}$,
then $\text{{\rm Cod}}^{-1}[A]$ is a $\Sigma^{1}_{n+1}(B)$ set.

######  Definition 1.15.

Let $M,W$ be transitive models of $\mathsf{ZFC}^{-}$. The pair $(M,W)$ is a
_canonical pair_ if $H_{\omega_{1}}^{M}\subseteq H_{\omega_{1}}^{W}$ and
$\operatorname{otp}(M\cap\mathrm{Ord})\geq\omega_{1}^{W}$.

Note that $M$ may not be a subset of $W$ (and this case will occur in our
proofs).

######  Lemma 1.16.

Assume $(M,W)$ is a _canonical pair_. Then

$(H_{\omega_{1}}^{M},\tau_{\text{{\sf
ST}}}^{M})\prec_{1}(H_{\omega_{1}}^{W},\tau_{\text{{\sf ST}}}^{W})$

###### Proof.

Use Shoenfield’s absoluteness Lemma for $\Sigma^{1}_{2}$-properties [2, Thm.
25.20] between the transitive models of $\mathsf{ZFC}^{-}$ $M\subseteq W$ and
the observation that $\Sigma_{1}$-definable subsets of $H_{\omega_{1}}$
corresponds to $\Sigma^{1}_{2}$-properties (see [2, Lemma 25.25]). ∎

###  1.3. Universally Baire sets

######  Definition 1.17.

Let $V$ be a transitive model of $\mathsf{ZFC}$. $B\subseteq 2^{\omega}$ is
universally Baire in $V$ if there are class sized trees $S_{B},T_{B}$ on
$(2\times\mathrm{Ord})^{<\omega}$ such that:

  * •

$S_{B}\cap(2\times\alpha)^{<\omega}$ and $T_{B}\cap(2\times\alpha)^{<\omega}$
are elements of $V$ for any ordinal $\alpha$;

  * •

$B=p[T_{B}]$ (i.e. $r\in B$ if and only if there is
$f\in\mathrm{Ord}^{\omega}$ such that $(r\restriction n,f\restriction n)\in
T_{B}$ for all $n\in\omega$);

  * •

$p[T_{B}]\cap p[S_{B}]=\emptyset$;

  * •

for all $G$ $V$-generic for some forcing notion $P\in V$, $p[T_{B}]^{V[G]}\cup
p[S_{B}]^{V[G]}=(2^{\omega})^{V[G]}$.

Trees $T$ and $S$ satisfying the two latter conditions for all $G$ $V$-generic
for a specific forcing notion $P$ are said to be projecting to complements for
$P$.

######  Notation 1.18.

Given a universally Baire set $B$ and $G$ $V$-generic for some forcing notion
$P$ of $V$, we let $B^{V[G]}=p[T_{B}]^{V[G]}$.

######  Theorem 1.19.

Assume in $V$ there are class many Woodin cardinals. Let $\text{{\sf UB}}^{V}$
be the family of universally Baire sets of $V$ and $\tau_{\text{{\sf
UB}}^{V}}=\tau_{\text{{\sf ST}}}\cup\text{{\sf UB}}^{V}$. Let $G$ be
$V$-generic for some forcing notion $P\in V$ and $H$ be $V[G]$-generic for
some forcing $Q$ in $V[G]$.

Then

$(H_{\omega_{1}}^{V[G]},\tau_{\text{{\sf ST}}}^{V[G]},A^{V[G]}:A\in\text{{\sf
UB}}^{V})\prec(H_{\omega_{1}}^{V[G][H]},\tau_{\text{{\sf
ST}}}^{V[G]},A^{V[G][H]}:A\in\text{{\sf UB}}^{V}).$

For a proof of this theorem see for example [5, Thm. 4.7].

In particular assume $B$ is universally Baire and such that

$(H_{\omega_{1}},\tau_{\text{{\sf ST}}}^{V},B)\models D=\text{{\rm
Cod}}[B]\text{ is a dense subset of }\mathbb{P}_{\mathrm{max}}.$

Then

$(H_{\omega_{1}}^{V[G]},\tau_{\text{{\sf
ST}}}^{V[G]},B^{V[G]})\models\text{{\rm Cod}}[B^{V[G]}]\text{ is a dense
subset of }\mathbb{P}_{\mathrm{max}}$

and $\text{{\rm Cod}}[B^{V[G]}]\cap H_{\omega_{1}}^{V}=D$.

######  Definition 1.20.

$A\subseteq H_{\omega_{1}}$ is _universally Baire in the codes_ if
$A=\text{{\rm Cod}}[B]$ for some universally Baire set $B$.

######  Notation 1.21.

Given $\mathcal{A}$ a family of universally Baire sets of $V$,
$\tau_{\mathcal{A}}=\tau_{\text{{\sf ST}}}\cup\mathcal{A}$ and
$T_{\mathcal{A}}$ is the theory of the $\tau_{\mathcal{A}}$-structure

$(H_{\omega_{1}}^{V},\tau_{\text{{\sf ST}}},A:A\in\mathcal{A}).$

###  1.4. $\MM^{++}$ and the reflection of $\Sigma_{1}$-sentences in
$\tau_{\text{{\sf ST}}}\cup\text{{\sf
UB}}\cup\left\\{\omega_{1},\mathbf{NS}_{\omega_{1}}\right\\}$

We now show that $\MM^{++}$ entails a strong form of BMM which reflects not
only $\Sigma_{1}$-properties, but also $\Sigma_{1}$-properties expressed in
the first order language expanding $\tau_{\text{{\sf ST}}}$ with predicate
symbols for $\mathbf{NS}_{\omega_{1}}$ and universally Baire sets. Let

$\tau_{\mathbf{NS}_{\omega_{1}},\text{{\sf UB}}}=\tau_{\text{{\sf
ST}}}\cup\text{{\sf
UB}}\cup\left\\{\omega_{1},\mathbf{NS}_{\omega_{1}}\right\\}.$

Given a Woodin cardinal $\delta$, $\mathcal{T}_{\delta}$ denotes the full
stationary tower of height $\delta$ (denoted as $\mathbb{P}_{\delta}$ in [4])
and for $K$ $V$-generic for $\mathcal{T}_{\delta}$ $\operatorname{Ult}(V,K)$
denotes the generic ultrapower and $j_{K}:V\to\operatorname{Ult}(V,K)$ the
generic ultrapower umbedding (see [4, Chapter 2] for the key definitions and
results).

By [6, Thm. 2.12] assuming the existence of class many Woodin cardinals
$\MM^{++}(\kappa)$ can be formulated as follows:

######  Definition 1.22.

$\MM^{++}(\kappa)$ holds if for any (some9 Woodin cardinal $\delta>\kappa$ and
for any stationary set preserving forcing $P$ of size $\kappa$, there is a
stationary set $T_{P}\in V_{\delta}$ and a complete embedding
$i:P\to\mathcal{T}_{\delta}\restriction T_{P}$ such that whenever $G$ is
$V$-generic for $P$:

  * •

The quotient forcing $\mathcal{T}_{\delta}\restriction T_{P}/_{i[G]}$ is
stationary set preserving in $V[G]$,

  * •

Letting $H$ be $V[G]$-generic for $\mathcal{T}_{\delta}\restriction
T_{P}/_{i[G]}$ and $K$ be the $V$-generic filter for
$\mathcal{T}_{\delta}\restriction T_{P}$ induced by the forcing isomorphism of
$\mathcal{T}_{\delta}\restriction T_{P}$ with
$P\ast(\mathcal{T}_{\delta}\restriction T_{P}/_{i[\dot{G}]})$, we have that
the critical point of $j_{K}:V\to\operatorname{Ult}(V,K)$ is $\omega_{2}$,
$j_{K}(\omega_{2})<\delta=j_{K}(\delta)$ and
$\operatorname{Ult}(V,K)^{<\delta}\subseteq\operatorname{Ult}(V,K)$ holds in
$V[K]$.

######  Theorem 1.23.

Assume $\MM^{++}(\kappa)$ holds in $V$ and there are class many Woodin
cardinals. Then for any stationary set preserving forcing $P\in V$ of size
$\kappa$ and any $G$ $V$-generic for $P$

$(H_{\omega_{2}}^{V},\tau_{\text{{\sf
ST}}}^{V},\mathbf{NS}_{\omega_{1}}^{V},\text{{\sf
UB}}^{V})\prec_{1}(H_{\omega_{2}}^{V[G]},\tau_{\text{{\sf
ST}}}^{V[G]},\mathbf{NS}_{\omega_{1}}^{V[G]},A^{V[G]}:A\in\text{{\sf
UB}}^{V}).$

We sketch a proof:

###### Proof.

Assume $\phi(x,y)$ is a quantifer free formula in the signature
$\tau_{\mathbf{NS}_{\omega_{1}},\text{{\sf UB}}}$. Let
$B_{1},\dots,B_{k}\in\text{{\sf UB}}^{V}$ be the universally Baire sets
appearing in the formula $\phi(x,y)$. Fix $A\in H_{\omega_{2}}^{V}$, and
assume that $P$ is stationary set preserving of size $\kappa$ and forces
$\exists y\phi(A,y)$.

Let $K$ be $V$-generic for $\mathcal{T}_{\delta}\restriction T_{P}$ and
$G,H\in V[K]$ be such that $G$ is $V$-generic for $P$ and $H$ is
$V[G]$-generic for $\mathcal{T}_{\delta}\restriction T_{P}/_{i[G]}$ and
$V[K]=V[G][H]$.

Now:

  * •

$H_{\omega_{2}}^{V[G][H]}=H_{\omega_{2}}^{\operatorname{Ult}(V,K)}$ and
$j_{K}(\mathbf{NS}_{\omega_{1}}^{V})=\mathbf{NS}_{\omega_{1}}^{\operatorname{Ult}(V,K)}=\mathbf{NS}_{\omega_{1}}^{V[G][H]}$:
since $V[G][H]=V[K]$, $j(\omega_{2})<\delta$ and $V[K]$ models that
$\operatorname{Ult}(V,K)^{<j(\delta)}\subseteq\operatorname{Ult}(V,K)$.

  * •

$j_{K}(B)=B^{V[G][H]}$ for all universally Baire sets $B\in V$: assume
$S_{B},T_{B}\in V$ are trees on $(2\times\mathrm{Ord})^{<\omega}$ projecting
to complements in any forcing extension with $B=p[T_{B}]$. Then
$j_{K}(S_{B}),j_{K}(T_{B})$ in $\operatorname{Ult}(V,K)$ are trees projecting
to complements containing $j_{K}[S_{B}],j_{K}[T_{B}]$; therefore if $p$ is the
projection map of $(2\times\mathrm{Ord})^{\omega}$ on $2^{\omega}$,

$B^{V[K]}=p[T_{B}]=p[j_{K}[T_{B}]]=p[j_{K}(T)]\subseteq j_{K}(B),$
$(2^{\omega}\setminus B)^{V[K]}=p[S_{B}]=p[j_{K}[S_{B}]]\subseteq
p[j_{K}(S_{B})]=(2^{\omega}\setminus B)^{\operatorname{Ult}(V,K)}.$

Hence $B^{V[K]}=j_{K}(B)$.

This gives that the identity map defines an elementary embedding of the
$\tau_{\mathbf{NS}_{\omega_{1}},\text{{\sf UB}}^{V}}$-structure

$(H_{\omega_{2}}^{V},\tau_{\text{{\sf
ST}}}^{V},\mathbf{NS}_{\omega_{1}}^{V},\text{{\sf UB}}^{V})$

into the $\tau_{\mathbf{NS}_{\omega_{1}},\text{{\sf UB}}^{V}}$-structure

$(H_{\omega_{2}}^{V[G][H]},\tau_{\text{{\sf
ST}}}^{V[G][H]},\mathbf{NS}_{\omega_{1}}^{V[G][H]},B^{V[G][H]}:B\in\text{{\sf
UB}}^{V}).$

Since $H$ is $V[G]$-generic for a stationary set preserving forcing in $V[G]$
and $B^{V[G][H]}\cap V[G]=B^{V[G]}$ for all universally Baire sets in $V$, we
get that

$(H_{\omega_{2}}^{V[G]},\tau_{\text{{\sf
ST}}}^{V[G]},\mathbf{NS}_{\omega_{1}}^{V[G]},B^{V[G]}:B\in\text{{\sf
UB}}^{V})$

is a substructure of

$(H_{\omega_{2}}^{V[G][H]},\tau_{\text{{\sf
ST}}}^{V[G][H]},\mathbf{NS}_{\omega_{1}}^{V[G][H]},B^{V[G][H]}:B\in\text{{\sf
UB}}^{V}).$

By choice of $P$

$(H_{\omega_{2}}^{V[G]},\tau_{\text{{\sf
ST}}}^{V[G]},\mathbf{NS}_{\omega_{1}}^{V[G]},B^{V[G]}:B\in\text{{\sf
UB}}^{V})\models\exists y\phi(A,y).$

Therefore since $\Sigma_{1}$-properties are preserved by superstructures

$(H_{\omega_{2}}^{V[G][H]},\tau_{\text{{\sf
ST}}}^{V[G][H]},\mathbf{NS}_{\omega_{1}}^{V[G][H]},B^{V[G][H]}:B\in\text{{\sf
UB}}^{V})\models\exists y\phi(A,y).$

We conclude that

$(H_{\omega_{2}}^{V},\tau_{\text{{\sf
ST}}}^{V},\mathbf{NS}_{\omega_{1}}^{V},\text{{\sf UB}}^{V})\models\exists
y\phi(A,y).$

The proof is completed. ∎

###  1.5. $G_{A}\cap D$ is a $\Sigma_{1}$-property in the signature
$\tau_{\text{{\sf ST}}}\cup\text{{\sf
UB}}\cup\left\\{\omega_{1},\mathbf{NS}_{\omega_{1}}\right\\}$

The statement

$x=\left\\{j_{\alpha\beta}:\,M_{\alpha}\to
M_{\beta}:\,\alpha\leq\beta\leq\omega_{1}\right\\}\text{ is an iteration of
length $\omega_{1}$}$

is an atomic formula in free variable $x$ for the signature $\tau_{\text{{\sf
ST}}}\cup\left\\{\omega_{1}\right\\}$ given by the conjuctions of:

  1. (1)

_$x$ is a function_,

  2. (2)

_$\operatorname{dom}{x}=\omega_{1}$_ ,

  3. (3)

_$\forall\alpha\in\omega_{1}$ $x(\alpha)$ is an ordered pair
$(M_{\alpha},G_{\alpha})$ such that:_

     * •

_$M_{\alpha}$ is a transitive set_,

     * •

_$(M_{\alpha},\in)$ models $\mathsf{ZFC}+\mathbf{NS}_{\omega_{1}}$ is
precipitous_,

     * •

_$G_{\alpha}$ is $M_{\alpha}$-generic for
$\mathcal{P}\left(\omega_{1}\right)^{M_{\alpha}}/_{\mathbf{NS}_{\omega_{1}}^{M_{\alpha}}}$,_

     * •

_$M_{\alpha+1}=\operatorname{Ult}(M_{\alpha},G_{\alpha})$ where
$\operatorname{Ult}(M_{\alpha},G_{\alpha})$ is the generic ultrapower induced
by $G_{\alpha}$ on $M_{\alpha}$_,

     * •

_if $\alpha$ is a limit ordinal, $M_{\alpha}$ is the direct limit of the
iteration $x\restriction\alpha$_.

We leave to the reader to check that the above properties are formalizable by
$\Delta_{0}$-formulae.

$x=\left\\{j_{\alpha\beta}:\,M_{\alpha}\to
M_{\beta}:\,\alpha\leq\beta\leq\omega_{1}\right\\}\text{ is a correct
iteration}$

is the $\tau_{\text{{\sf
ST}}}\cup\left\\{\omega_{1},\mathbf{NS}_{\omega_{1}}\right\\}$-atomic formula
given by the conjuctions of

  * •

_$x$ is an iteration of length $\omega_{1}$_

  * •

$\forall z[z\subseteq\omega_{1}\wedge z\in
M_{\omega_{1}}\rightarrow[(M_{\omega_{1}}\models z\text{ is
stationary})\leftrightarrow\neg\mathbf{NS}_{\omega_{1}}(z))]]$.

Given $A\in\mathcal{P}\left(\omega_{1}\right)\setminus L(\text{{\sf UB}})$ and
$D$ dense subset of $\mathbb{P}_{\mathrm{max}}$ universally Baire in the codes
with $D=\text{{\rm Cod}}[B]$ and $B\in\text{{\sf UB}}$, $G_{A}\cap D$ is non-
empty is given by the $\tau_{\text{{\sf
ST}}}\cup\left\\{A,\omega_{1},\mathbf{NS}_{\omega_{1}},B\right\\}$
$\Sigma_{1}$-formula:

$\exists x\exists r\,[(x\text{ is a correct iteration of length
}\omega_{1})\wedge B(r)\wedge\text{{\rm
Cod}}(r)=(M_{0},A\cap\omega_{1}^{M_{0}})\wedge
j_{0\omega_{1}}(A\cap\omega_{1}^{M_{0}})=A.]$

######  Proposition 1.24.

In any model of $\mathsf{ZFC}+$_there are class many Woodin cardinals
$+\mathbf{NS}_{\omega_{1}}$ is precipitous_ $(*)\text{-}\mathsf{UB}$ is
expressible by an axiom schema of $\Pi_{2}$-sentences for the signature
$\tau_{\mathbf{NS}_{\omega_{1}},\text{{\sf UB}}}$.

This axiom system is given by the $\Pi_{2}$-axioms of
$\mathsf{ZFC}^{-}_{\text{{\sf ST}}}$ enriched with the $\Pi_{1}$-sentence for
$\tau_{\text{{\sf ST}}}\cup\left\\{\omega_{1}\right\\}$

$\forall f\,\left[(f\text{ is a
function})\wedge(\operatorname{dom}(f)=\omega)\right]\rightarrow(\operatorname{ran}(f)\neq\omega_{1}),$

the $\Pi_{2}$-sentence for $\tau_{\text{{\sf
ST}}}\cup\left\\{\omega_{1},\mathbf{NS}_{\omega_{1}}\right\\}$

$\forall S\,\left[\mathbf{NS}_{\omega_{1}}(S)\leftrightarrow\exists
C\,\left[(C\text{ is a club subset of $\omega_{1}$})\wedge(C\cap
S=\emptyset)\right]\right]$

and (for any universally Baire set $B$ such that $\text{{\rm Cod}}[B]=D$ is a
dense subset of $\mathbb{P}_{\mathrm{max}}$) the $\Pi_{2}$-sentences for
$\tau_{\text{{\sf
ST}}}\cup\left\\{\omega_{1},\mathbf{NS}_{\omega_{1}},B\right\\}$

$\displaystyle\forall A$ $\displaystyle[$
$\displaystyle\left[(\omega_{1}\text{ is the first uncountable
cardinal})^{L[A]}\wedge\forall
r\forall\beta\,\left[(r\subseteq\omega\wedge\beta\text{ is an
ordinal})\rightarrow A\notin L_{\beta}[r])\right]\right]$
$\displaystyle\rightarrow$
$\displaystyle\exists(N_{0},a_{0})\,\exists\mathcal{J}\exists
r(B(r)\wedge\text{{\rm Cod}}(r)=(N_{0},a_{0})\wedge\mathcal{J}\text{ is a
correct iteration of $N_{0}$ with $j_{0\omega_{1}}(a_{0})=A$})$
$\displaystyle]$

###### Proof.

The unique thing to check is that _$\mathbf{NS}_{\omega_{1}}$_ is saturated
follows from the above axioms, but this holds by [3, Thm. 5.1]. ∎

##  2\. Main result and semantic certificates

The key concept introduced by Asperò and Schindler is that of a semantic
certificate.

Given a dense set $D$ of $\mathbb{P}_{\mathrm{max}}$ universally Baire in the
codes and $A\in\mathcal{P}\left(\omega_{1}^{V}\right)\setminus
L(\mathbb{R}^{V})$ it is not at all transparent how one can produce (even in
an arbitrary forcing extension $V[G]$ of $V$ possibly not stationary set
preserving) an iteration

$\mathcal{J}=\left\\{j_{\alpha\beta}:N_{\alpha}\to
N_{\beta}:\,\alpha\leq\beta\leq\omega_{1}^{V}\right\\}$

respecting the constraints $(N_{0},A\cap\omega_{1}^{N_{0}})\in D^{V[G]}$ and
$j_{0\omega_{1}^{V}}(A\cap\omega_{1}^{N_{0}})=A$. Semantic certificates (to be
defined below) impose even stronger constraints on $\mathcal{J}$.

######  Convention 2.1.

Throughout the rest of this paper we assume $\mathbf{NS}_{\omega_{1}}$ is
saturated, Martin’s axiom, and $2^{\aleph_{0}}=2^{\aleph_{1}}=\aleph_{2}$
holds in $V$.

Note that all these assumptions hold assuming $\MM^{++}$ and are also a
consequence of $(*)\text{-}\mathsf{UB}$.

To introduce the notion of semantic certificate we must first select the class
of transitive models of $\mathsf{ZFC}$ and the type of iterations of countable
structures we will consider in the remainder of this paper, these are the
canonical pairs introduced in Def. 1.15.

######  Remark 2.2.

We will be interested in the following three combinations of canonical pairs
(cfr. Def. 1.15) $M,W$:

  * •

$W=M[G]$ is a generic extension of $M$.

  * •

$M$ is the standard universe of sets $V$ and $W=\bar{M}$, where
$j:V\to\bar{M}$ is an elementary embedding definable in $V[G]$ with critical
point $\omega_{1}^{V}$ for $V[G]$ a generic extension of $V$.

  * •

$W=V[G][H]$ is a generic extension of $V$ with $G$ $V$-generic for
$\operatorname{Coll}(\omega,\omega_{2}^{V})$, $H$ $V[G]$-generic for
$\operatorname{Coll}(\omega,\eta)$ with $\eta$ large enough,
$\bar{j}:V\to\bar{M}$ an elementary embedding definable in $V[G]$ with
critical point $\omega_{1}^{V}$ and $\omega_{1}^{\bar{M}}=\omega_{1}^{V[G]}$,
and $M=\bar{M}[H]$.

Note that in the second case we can just assume that
$H_{\omega_{1}}^{V}\subseteq\bar{M}$, in general the transitive classes
$\bar{M},V$ definable in $V[G]$ do not have much else in common.

######  Definition 2.3.

Let:

  * •

$V$ be a transitive model of $\mathsf{ZFC}+\mathbf{NS}_{\omega_{1}}$_is
saturated_ ,

  * •

$B$ be a universally Baire set in $V$ and $D$ in $V$ be a dense subset of
$\mathbb{P}_{\mathrm{max}}$ such that $\text{{\rm Cod}}[B]=D$,

  * •

$A\in\mathcal{P}\left(\omega_{1}\right)^{V}\setminus L(\mathbb{R})^{V}$ be
such that $\omega_{1}^{L[A]}=\omega_{1}^{V}$.

$T$ in $V$ is a witnessing tree for $A,D$ if:

  * •

$T$ is a tree on $(2\times\omega_{2}^{V})^{<\omega}$;

  * •

$p[T]\subseteq B^{V[G]}$ holds in all generic extensions $V[G]$ of $V$;

  * •

whenever $G$ is $V$-generic for $\operatorname{Coll}(\omega,\eta)$ for some
$\eta\geq\lambda$, there is $r\in p[T]^{V[G]}$ such that $\text{{\rm
Cod}}(r)=(N_{0},a_{0})$ refines $(H_{\omega_{2}}^{V},A)$ in the
$\mathbb{P}_{\mathrm{max}}$ order of $V[G]$.

The following Fact encapsulates the unique place in the proof of Thm. 1.7
where the assumption that there are class many Woodin cardinals is essentially
used and cannot be significantly reduced.

######  Fact 2.4.

Assume $V$ models $\mathbf{NS}_{\omega_{1}}$_is saturated $+$ there are class
many Woodin cardinals_.

Then there is in $V$ a witnessing tree $T$ on
$(2\times\omega_{2}^{V})^{<\omega}$ for $A,D$ for any $D$ dense subset of
$\mathbb{P}_{\mathrm{max}}$ with $D=\text{{\rm Cod}}[B]$ for some
$B\in\text{{\sf UB}}^{V}$, and
$A\in\mathcal{P}\left(\omega_{1}\right)^{V}\setminus L(\mathbb{R})$ such that
$\omega_{1}^{L[A]}=\omega_{1}^{V}$.

###### Proof.

Let $G$ be $V$-generic for $\operatorname{Coll}(\omega,\omega_{2}^{V})$. Then
$(H_{\omega_{2}}^{V},A)$ is a $\mathbb{P}_{\mathrm{max}}$-condition in $V[G]$
(any iteration of $X$ in $V[G]$ of length at most $\omega_{1}^{V[G]}$ can be
extended to an iteration of $V$, by [3, Lemma 1.5, Lemma 1.6]).

Find $(N,b)\leq(H_{\omega_{2}}^{V},A)$ in $\text{{\rm Cod}}[B^{V[G]}]$ (which
is dense in $\mathbb{P}_{\mathrm{max}}^{V[G]}$ by Thm. 1.19), $r\in B^{V[G]}$
such that $\text{{\rm Cod}}(r)=(N,b)$, $h\in\lambda^{\omega}$ such that
$(r,h)$ is a branch through $T_{B}$ in $V[G]$ (where $T_{B},S_{B}$ are class
sized trees on $(2\times\mathrm{Ord})^{<\omega}$ witnessing the universal
Baireness of $B$ in $V$ according to Def. 1.17).

Let $\dot{r}$ and $\dot{h}$ be
$\operatorname{Coll}(\omega,\omega_{2}^{V})$-names111111To prove the existence
of such names independently of the choice of the $V$-generic filter $G$ one
uses the homogeneity of $\operatorname{Coll}(\omega,\omega_{2}^{V})$. for $r$
and $h$ such that every $p$ in $\operatorname{Coll}(\omega,\omega_{2}^{V})$
forces that $(\dot{r}_{G},\dot{\dot{h}}_{G})$ is a branch through $T_{B}$ such
that $\text{{\rm
Cod}}(\dot{r}_{G})\leq_{\mathbb{P}_{\mathrm{max}}}(H_{\omega_{2}}^{V},A)$
holds in $V[G]$ whenever $G$ is $V$-generic with $p\in G$.

Let for each $n$

$Y_{n}=\left\\{\beta\in\mathrm{Ord}:\exists
p\in\operatorname{Coll}(\omega,\omega_{2}^{V})\,p\Vdash\dot{h}(\check{n})=\check{\beta}\right\\}$

and $Z=\bigcup_{n\in\omega}Y_{n}$. Then $Z\in V$ has size at most
$\omega_{2}^{V}$ and $r$ belongs to the projection of $T^{*}=T_{B}\cap(2\times
Z)^{<\omega}$ in $V[G]$. We copy in $V$ $T^{*}$ to a tree $T$ on
$(2\times\omega_{2}^{V})^{<\omega}$ via an injection $g:Z\to\lambda$ in $V$,
and we let $\dot{f}$ be the $\operatorname{Coll}(\omega,\omega_{2}^{V})$-name
on $T$ obtained as an isomorphic image of $\dot{h}$ via $g$.

We get that:

> _$\dot{r},\dot{f}$ are $\operatorname{Coll}(\omega,\omega_{2}^{V})$-names
> such that whenever $H$ is $V$-generic for
> $\operatorname{Coll}(\omega,\omega_{2}^{V})$, $(\dot{r}_{H},\dot{f}_{H})$ is
> a branch through $T$ such that $\text{{\rm Cod}}(\dot{r}_{H})\in\text{{\rm
> Cod}}[B^{V[H]}]$ is a $\mathbb{P}_{\mathrm{max}}$-condition refining
> $(H_{\omega_{2}}^{V},A)$._

> _The map $g$ grants that $p[T]^{V[K]}\subseteq p[T_{B}]^{V[K]}=B^{V[K]}$
> holds in any forcing extension $V[K]$ of $V$ for any notion of forcing in
> $V$._

Hence $T$ works. ∎

######  Remark 2.5.

We use here in an essential way the existence of class many Woodin cardinals
(specifically Thm. 1.19). We could also replace this assumption with the
existence of a Woodin cardinal $\delta$ which is a limit of Woodin cardinals
(and then use Thm. [4, Thm 3.1.6]). What is crucially needed to prove the Fact
is that the $\Pi_{2}$-sentence for $\tau_{\mathsf{ST}}$

$\forall x\,\left[x\not\in\mathbb{P}_{\mathrm{max}}\vee\exists
y\,(B(y)\wedge\text{{\rm Cod}}(y)\leq_{\mathbb{P}_{\mathrm{max}}}x)\right]$

holding in the structure

$(H_{\omega_{1}}^{V},\tau_{\text{{\sf ST}}},B)$

remains true in the structure

$(H_{\omega_{1}}^{V[G]},\tau_{\text{{\sf ST}}},B^{V[G]}).$

To see that the above is a $\Pi_{2}$-sentence for $\tau_{\mathsf{ST}}$ use [3,
Remark 1.4] and [2, Lemma 25.25].

######  Definition 2.6.

Let $M$ be a transitive model of $\mathsf{ZFC}+\mathbf{NS}_{\omega_{1}}$_is
saturated_ :

  * •

$T$ in $M$ be a tree on $(2\times\omega_{2}^{M})^{<\omega}$;

  * •

$A\in\mathcal{P}\left(\omega_{1}\right)^{M}\setminus L(\mathbb{R})^{M}$ be
such that $\omega_{1}^{L[A]}=\omega_{1}^{M}$.

A tuple $(\mathcal{J},r,f,T)$ existing in some transitive outer model $W$ of
$M$ is a _weak semantic certificate for $A$_ if:

  1. (1)

$(r,f)$ is a branch through $T$.

  2. (2)

$\mathcal{J}=\left\\{j_{\alpha\beta}:\,N_{\alpha}\to
N_{\beta}:\,\alpha\leq\beta\leq\omega_{1}^{M}\right\\}$ is an iteration with
$N_{0}$ iterable in $W$.

  3. (3)

$\text{{\rm Cod}}(r)=(N_{0},A\cap\omega_{1}^{N_{0}})$ holds.

  4. (4)

$j_{0\omega_{1}^{M}}(A\cap\omega_{1}^{N_{0}})=A$.

  5. (5)

$H_{\omega_{2}}^{M}\subseteq N_{\omega_{1}}$.

  6. (6)

$\mathbf{NS}_{\omega_{1}}^{M}=\mathbf{NS}_{\omega_{1}}^{N_{\omega_{1}^{M}}}\cap\mathcal{P}\left(\omega_{1}\right)^{M}$.

Let $D$ in $M$ be a dense subset of $\mathbb{P}_{\mathrm{max}}^{M}$ such that
$D=\text{{\rm Cod}}[B]$ for some fixed $B\in\text{{\sf UB}}^{M}$.

A weak semantic certificate $(\mathcal{J},r,f,T)$ for $A$ existing in $W$ is a
_semantic certificate for $A,D$_ (relative to $M$) if:

  1. (7)

$M$ models that $T$ is a witnessing tree for $A,D$.

  2. (8)

$W$ is some generic extension of $M$.

Condition 5 and 6 are essential in many stages of the proof, for example we
already use them in the proof of Corollary 2.8 right below. Condition 7 hides
all the large cardinal strength needed in our proofs. Condition 8 makes the
property:

> _There exists a semantic certificate for $A,D$_

first order expressible without any reference to $D$ or to the universally
Baire set $B$ which codes $D$: the relevant information on $B$ and $D$ is now
encoded in the witnessing tree $T$ (whose projection may not be defining a
universally Baire set of $M$, but it is still defining a subset of $B^{M[G]}$
in any generic extension of $M$). This is going to be very handy, see Remark
2.9 below.

There is no reason to expect that the statement _there exists a weak semantic
certificate for $A$ in some transitive outer model of $V$_ is first order
expressible in any reasonable way in $V$, since the class of transitive outer
models of $V$ is not first order definable.

The main result of the paper is the following:

######  Theorem 2.7.

Assume $V$ models _$\mathbf{NS}_{\omega_{1}}$ is saturated_ and _there are
class many Woodin cardinals_. Let $\kappa>\omega_{2}$ be a regular cardinal
such that $\Diamond_{\kappa}$ holds.

Let $A\in\mathcal{P}\left(\omega_{1}\right)\setminus L(\mathbb{R})$ and $D$
dense subset of $\mathbb{P}_{\mathrm{max}}$ be such that:

  * •

$D=\text{{\rm Cod}}[B]$ for some universally Baire set $B$,

  * •

$\omega_{1}^{L[A]}=\omega_{1}^{V}$.

Then there is a stationary set preserving forcing $P_{D,A}$ in $V$ of size
$\kappa$ producing in its generic extensions $V[H]$ a semantic certificate
$(\mathcal{J}_{H},r_{H},f_{H},T)$ for $A,D$ such that

$\mathbf{NS}_{\omega_{1}}^{V[H]}\cap
N_{\omega_{1}^{V}}=\mathbf{NS}_{\omega_{1}}^{N_{\omega_{1}}},$

where

$\mathcal{J}_{H}=\left\\{j_{\alpha\beta}:N_{\alpha}\to
N_{\beta}:\alpha\leq\beta\leq\omega_{1}^{V}\right\\}.$

######  Corollary 2.8.

Assume $\MM^{++}+$_there are class many Woodin cardinals_. Then
$(*)\text{-}\mathsf{UB}$ holds.

The corollary is immediate:

###### Proof.

By $\MM^{++}$, _$\mathbf{NS}_{\omega_{1}}$ is saturated_. Find
$\kappa>\omega_{2}$ such that $\Diamond_{\kappa}$ holds in $V$. Fix
$A\in\mathcal{P}\left(\omega_{1}\right)^{V}$ as prescribed by the theorem, and
let $D$ vary among the universally Baire in the codes dense subsets of
$\mathbb{P}_{\mathrm{max}}$. If $H$ is $V$-generic for $P_{D,A}$, then in
$V[H]$ there is

$\mathcal{J}_{H}=\left\\{j_{\alpha\beta}:N_{\alpha}\to
N_{\beta}:\alpha\leq\beta\leq\omega_{1}\right\\}$

iteration such that $(N_{0},A\cap\omega_{1}^{N_{0}})\in D$ and
$j_{0\omega_{1}}(A\cap\omega_{1}^{N_{0}})=A$ (cfr. Condition 4 of Def. 2.6).
Now

$H_{\aleph_{2}}^{V}\subseteq N_{\omega_{1}^{V}},$

and
$\mathbf{NS}_{\omega_{1}}^{V}=\mathbf{NS}_{\omega_{1}}^{N_{\omega_{1}}}\cap
H_{\omega_{2}}$ (by Conditions 5 and 6 of a semantic certificate). Therefore
in $V[H]$ every stationary subset of $\omega_{1}$ in $V$ is stationary in
$N_{\omega_{1}^{V}}$, hence also in $V[H]$ (by Thm. 3.33). We conclude that
$P_{\kappa}$ is stationary set preserving.

Since
$\mathbf{NS}_{\omega_{1}}^{N_{\omega_{1}^{V}}}=\mathbf{NS}_{\omega_{1}}^{V[H]}\cap
N_{\omega_{1}^{V}}$, $\mathcal{J}_{H}$ is a correct iteration in $V[H]$ with

$(N_{0},A\cap\omega_{1}^{N_{0}})=\text{{\rm Cod}}(r_{H}),\qquad r_{H}\in
p[T]\subseteq p[T_{B}]=B^{V[H]}.$

By the results of Section 1.4, the existence of a correct iteration
$\mathcal{J}$ such that $j_{0,\omega_{1}}(A\cap\omega_{1}^{N_{0}})=A$ and
$(N_{0},A\cap\omega_{1}^{N_{0}})=\text{{\rm Cod}}(r)$ with $r\in B^{V[H]}$ can
be reflected to $V$, by $\MM^{++}$. This concludes the proof. ∎

The rest of the paper is dedicated to the proof of Thm. 2.7.

First of all let us outline some key observations on semantic certificates.

######  Remark 2.9.

Assume $(M,W)$ is a canonical pair and $H_{\omega_{2}}^{M}$ is countable in
$W$. The statement

> $(\mathcal{J},r,f,T)$ is a _weak semantic certificate for $A$._

is first order expressible in the structure
$(H_{\omega_{1}}^{W},\tau_{\mathsf{ST}}^{W})$ by the sentence
$\phi(A,T,H_{\omega_{2}}^{M},\omega_{1}^{M})$ in parameters (the countable in
$W$ sets) $A,T,H_{\omega_{2}}^{M},\omega_{1}^{M}$:

(1) $\displaystyle((r,f)\text{ is a branch of }T)\wedge$
$\displaystyle\wedge\mathcal{J}=\left\\{j_{\alpha\beta}:N_{\alpha}\to
N_{\beta}:\alpha\leq\beta\leq\omega_{1}^{M}\right\\}\text{ is an
iteration}\wedge$ $\displaystyle\wedge
j_{0\omega_{1}^{M}}(A\cap\omega_{1}^{N_{0}})=A\wedge$ $\displaystyle\wedge
H_{\omega_{2}}^{M}\subseteq N_{\omega_{1}^{M}}\wedge$
$\displaystyle\wedge\mathbf{NS}_{\omega_{1}}^{M}=\mathbf{NS}_{\omega_{1}}^{N_{\omega_{1}^{M}}}\cap
H_{\omega_{2}}^{M}\wedge$ $\displaystyle\wedge\text{{\rm
Cod}}(r)=(N_{0},A\cap\omega_{1}^{N_{0}})$

The first five properties listed above of $\mathcal{J},r,f,T$ are expressed by
$\Delta_{0}$-formulae in the relevant parameters (for example we already
showed that this is the case for $\mathcal{J}$_is an iteration of length
$\omega_{1}^{M}$_). The last assertion is a provably $\Delta_{1}$-property in
the signature $\tau_{\text{{\sf ST}}}$.

The unique delicate part (hiding significant large cardinal strength) for a
semantic certificate is the request $p[T]\subseteq B^{V[G]}$ holds in all
generic extensions of $V$. This is expressible by the
$\Pi^{1}_{1}(B,T)$-property

$\forall r\in 2^{\omega}\forall f\in\kappa^{\omega}\,\left[(\forall
n\in\omega(r\restriction n,f\restriction n)\in T)\rightarrow B(r)\right].$

In principle $\Pi^{1}_{1}(B,T)$-properties are not universally Baire, even if
$B$ is universally Baire and $T$ is countable.

Now if $W$ is any transitive outer model of $M$, it is not at all clear
whether we can make sense of $B^{W}$ for a universally Baire set $B$ of $M$.
The notion of witnessing tree $T$ show that we do not have to worry about this
issue, and we can just check whether in this outer model weak semantic
certificates $(\mathcal{J},r,f,T)$ for $A$ with certain properties (depending
only on the parameters $A,H_{\omega_{2}}^{M},T$) exist in $W$.

Most of our arguments will run as follows:

  * •

We fix in advance in $V$ a witnessing tree $T$ for $A,D$.

  * •

We define in some generic extension $V[G]$ of $V$ a generic
$\bar{k}:V\to\bar{M}$ with $\omega_{1}^{\bar{M}}=\omega_{1}^{V[G]}$.

  * •

We consider the canonical pair $(\bar{M},V[G])$ and we also produce in $V[G]$
a weak semantic certificate $(\mathcal{J},r,f,\bar{k}(T))$ for $\bar{k}(A)$
with certain extra properties (independent of the universally Baire set $B$)
which can be expressed as
$\Sigma^{1}_{2}(\bar{k}(T),\bar{k}(A),\bar{k}(H_{\omega_{2}}^{V}))$-facts in
$\bar{M}[H]$ whenever $H$ is an $\bar{M}$-generic filter with
$\bar{k}(A),\bar{k}(H_{\omega_{2}}),\bar{k}(T)$ countable in $\bar{M}[H]$.

  * •

Since these properties of $(\mathcal{J},r,f,\bar{k}(T))$ (holding in $V[G]$)
still hold in $H_{\omega_{1}}^{V[H]}$ for any $V$-generic extension $V[H]$ in
which $\bar{k}(A),\bar{k}(H_{\omega_{2}}),\bar{k}(T)$ are countable, we
reflect them to $(H_{\omega_{1}}^{\bar{M}[H]},\tau_{\text{{\sf
ST}}}^{\bar{M}[H]})$ using Shoenfield’s absoluteness between
$(H_{\omega_{1}}^{\bar{M}[H]},\tau_{\text{{\sf ST}}}^{\bar{M}[H]})$ and
$(H_{\omega_{1}}^{V[H]},\tau_{\text{{\sf ST}}}^{V[H]})$.

  * •

Finally (since $\bar{k}(T)$ is in $\bar{M}$ a witnessing tree for
$\bar{k}(A),\bar{k}(D)$), we use elementarity of $\bar{k}$ to reflect these
properties to $V$ in the form:

> _Semantic certificates for $A,D$ with the required properties exist in any
> generic extension of $V$ by $\operatorname{Coll}(\omega,\omega_{2}^{V})$._

The first example of this modular argument is given by Lemma 2.10.

###  2.1. Existence of semantic certificates

The first key result of Asperó and Schindler is that semantic certificates for
$A,D$ exist in some generic extension of $V$ (the proof below produces them in
a generic extension collapsing $\omega_{2}$ to countable).

######  Lemma 2.10.

Assume in $V$ $\mathbf{NS}_{\omega_{1}}$ is saturated and Martin’s axiom, $X$
is a transitive model of $\mathsf{ZFC}^{-}$ and $T$ is a witnessing tree on
$(2\times\omega_{2})^{<\omega}$ for $A,D$ as given by Fact 2.4, with
$A\in\mathcal{P}\left(\omega_{1}\right)\setminus L(\mathbb{R})$ such that
$\omega_{1}^{L[A]}=\omega_{1}^{V}$ and $D=\text{{\rm Cod}}[B]$ dense subset of
$\mathbb{P}_{\mathrm{max}}$ with $B$ universally Baire.

Then for any $G$ $V$-generic for $\operatorname{Coll}(\omega,\omega_{2}^{V})$,
there is in $V[G]$ a semantic certificate $(\mathcal{J},r,f,T)$ for $A,D$.

###### Proof.

Let $G$ be $V$-generic for $\operatorname{Coll}(\omega,\omega_{2}^{V})$. In
$V[G]$ $H_{\omega_{2}}^{V}$ is countable and iterable. This gives that
$(H_{\omega_{2}}^{V},A)$ is a $\mathbb{P}_{\mathrm{max}}^{V[G]}$ condition.

Since $T$ is a witnessing tree for $A,D$, there is $(N,b)=\text{{\rm
Cod}}(\dot{r}_{G})\leq(H_{\omega_{2}}^{V},A)$ with $r=\dot{r}_{G}\in p[T]$.

Since $N$ is countable and iterable in $V[G]$ and
$\gamma=(\omega_{3})^{V}=\omega_{1}^{V[G]}$, we can find in $V[G]$ an
iteration

$\mathcal{J}=\left\\{j_{\alpha\beta}:N_{\alpha}\to
N_{\beta}:\,\alpha\leq\beta\leq\gamma=\omega_{1}^{V[G]}\right\\}$

of $N=N_{0}$ (just apply [3, Lemma 2.8] in $V[G]$ to $N$).

Let
$\mathcal{K}=\left\\{k_{\alpha\beta}:\,\alpha\leq\beta\leq\omega_{1}^{N}\right\\}\in
N$ be the iteration witnessing that $(N,b)\leq(H_{\omega_{2}}^{V},A)$ and

$\bar{\mathcal{K}}=\left\\{\bar{k}_{\alpha\beta}:\,\alpha\leq\beta\leq\gamma\right\\}=j_{0\gamma}(\mathcal{K}).$

Extend in $V[G]$ $\bar{\mathcal{K}}$ to a full iteration of $V$ applying [3,
Lemma 1.5, Lemma 1.6], and let $\bar{M}=\bar{k}(V)$ with $\bar{k}$ the unique
extension of $\bar{k}_{0\gamma}$ to $V$.

Let $H$ be $V$-generic for $\operatorname{Coll}(\omega,\eta)$ with
$\eta=\bar{k}(\omega_{2}^{V})$ and $G\in V[H]$. Now observe that:

  * •

$H$ is $\bar{M}$-generic for $\operatorname{Coll}(\omega,\eta)$, since
$\bar{M}\subseteq V[G]$ and $H$ is also $V[G]$-generic for
$\operatorname{Coll}(\omega,\eta)$.

  * •

$\bar{k}(T)$ is a tree in $(2\times\bar{k}(\omega_{2}^{V}))^{<\omega}$ in
$\bar{M}$ which is countable in $\bar{M}[H]$ and in $V[H]$, and $r\in
p[\bar{k}(T)]^{V[G]}$.

  * •

$\mathcal{J},\bar{k}(H_{\omega_{2}}^{V})$ are in $H_{\omega_{1}}^{V[H]}$, and
$H_{\omega_{1}}^{V[H]}$ models that $\mathcal{J}$ is an iteration such that
$(N_{0},b)=\text{{\rm Cod}}(r)$, $r\in p[\bar{k}(T)]$, and

$j_{0\gamma}(b)=j_{0\gamma}(\bar{k}_{0\omega_{1}^{N}}(A))=\bar{k}(A).$

Consider the $\Sigma_{1}$-sentences in signature $\tau_{\text{{\sf ST}}}$ and
parameters
$\bar{k}(A),\bar{k}(T),\bar{k}(H_{\omega_{2}}^{V}),\omega_{1}^{\bar{M}}$
(which are in $\bar{M}$ and are countable in $\bar{M}[H]$)

> There is a branch $(r,\bar{k}[f])$ of $\bar{k}(T)$ and an iteration
> $\mathcal{J}=\left\\{j_{\alpha\beta}:N_{\alpha}\to
> N_{\beta}:\alpha\leq\beta\leq\omega_{1}^{\bar{M}}\right\\}$ such that:
>
>   * •
>
> $\text{{\rm Cod}}(r)=(N_{0},a_{0})$,
>
>   * •
>
> $j_{0\omega_{1}^{\bar{M}}}(A\cap\omega_{1}^{N_{0}})=\bar{k}(A)$,
>
>   * •
>
> $\bar{k}(H_{\omega_{2}}^{V})\subseteq N_{\omega_{1}^{\bar{M}}}$,
>
>   * •
>
>
> $\mathbf{NS}_{\omega_{1}}^{\bar{k}(H_{\omega_{2}})}=\mathbf{NS}_{\omega_{1}}^{N_{\omega_{1}^{\bar{M}}}}\cap\bar{k}(H_{\omega_{2}}^{V})$.
>
>

This sentence is true in $V[H]\supseteq\bar{M}[H]$ and all its parameters are
in $H_{\omega_{1}}^{\bar{M}[H]}$.

Therefore it holds in $H_{\omega_{1}}^{\bar{M}[H]}$ by Shoenfield’s
absoluteness (cfr. Lemma 1.16).

By homogeneity of $\operatorname{Coll}(\omega,\eta)$ we conclude that
$\bar{M}$ models that: _“in any $\bar{M}$-generic extension for
$\operatorname{Coll}(\omega,\bar{k}(\omega_{2}^{V}))$ there is a weak semantic
certificate for $\bar{k}(A)$ as witnessed by $\bar{k}(T)$”_. By elementarity
of $\bar{k}$ we get that the same holds in $V$ replacing
$\bar{k}(A),\bar{k}(T)$ by $A,T$. ∎

######  Remark 2.11.

Provided one is given in advance the witnessing tree $T$, this Lemma does not
need the existence of class many Woodin cardinals to go through. One just
needs to be able to define in $V[G]$ the iterations $\mathcal{J}$ and
$\mathcal{K}$. This property of $\mathbb{P}_{\mathrm{max}}$-conditions holds
if $V[G]$ satisfies very mild large cardinal properties (see [3, Section 2]).

##  3\. The proof

We will show that STRATEGY 1.9 works. $P_{D,A}$ is construed in what follows
as the top element of an increasing chain of posets

$\left\\{P_{\alpha}:\alpha\in C\right\\}$

each of size $\kappa$, where $\kappa>\omega_{2}$ is regular, $C$ is a club
subset of $\kappa$, and $\Diamond_{\kappa}$ holds.

######  Convention 3.1.

Fix from now on:

  1. (A)

$A\in\mathcal{P}\left(\omega_{1}\right)\setminus L(\mathbb{R})$ such that
$\omega_{1}^{L[A]}=\omega_{1}^{V}$, and $B$ universally Baire set such that
$\text{{\rm Cod}}[B]=D$ is a dense subset of $\mathbb{P}_{\mathrm{max}}$ with
$N$ a model of $\mathsf{ZFC}+$_Martin’s axiom_ for any of its conditions
$(N,b)$.

  2. (B)

$T_{B},S_{B}$ trees on $(2\times\mathrm{Ord})^{<\omega}$ projecting to
complements in every set sized forcing extension of $V$ and such that
$B=p[T_{B}]$.

  3. (C)

$\kappa>\omega_{2}$ a regular cardinal such that $\Diamond_{\kappa}$ holds.

  4. (D)

$T$ a witnessing tree on $(2\times\omega_{2}^{V})^{<\omega}$ for $A,D$
according to Def. 2.3.

We first focus on designing a forcing generically adding a weak semantic
certificate for $A$ as witnessed by $T$ and prove that this forcing notion
accomplishes all requests set forth in STRATEGY 1.9, except possibly that of
being stationary set preserving. To overcome this problem one is then led to
define a transfinite sequence of posets

$\left\\{P_{\alpha}:\alpha\in C\cup\left\\{\kappa\right\\}\right\\}$

with $P_{\min(C)}$ generically adding a weak semantic certificate for $A$ as
witnessed by $T$, and such that for $\alpha<\beta$ $P_{\beta}$ extends
$P_{\alpha}$ adding many “sufficiently $P_{\alpha}$-generic” conditions. One
then ensures using $\Diamond_{\kappa}$ that at many stages $\lambda\in C$ the
$P_{\kappa}$-names for clubs are guessed by $P_{\lambda}$-names for clubs. Now
the sequence $\left\\{P_{\alpha}:\alpha\in C\right\\}$ is designed in order
that at all stages $\lambda<\beta$ there are $P_{\beta}$-conditions which
_“seal”_ the $P_{\lambda}$-name $A_{\lambda}$ for a club given by the Diamond
sequence $\left\\{A_{\alpha}:\alpha<\kappa\right\\}$ at $\lambda$. Here
_sealing_ means that for any fixed stationary set $S$ existing in $V$ one can
admit as $P_{\beta}$-conditions many which will guarantee that any
$P_{\beta}$-generic filter $G$ including them will be such that $G\cap
P_{\alpha}$ is a (possibly not $P_{\alpha}$-generic) filter ensuring that
$(A_{\alpha})_{G\cap P_{\alpha}}\cap S$ is non-empty. In particular the
$P_{\lambda}$ are more and more likely to be stationary set preserving as
$\lambda$ increases; $\Diamond_{\kappa}$ will be used to catch one’s tail and
be able to infer that $P_{\kappa}$ is stationary set preserving because all
potential $P_{\kappa}$-names for clubs have been sealed at some previous
stage.

The forcings $P_{\alpha}$ we borrow from Asperò and Schindler are here defined
as “consistency properties”, a central concept in the analysis of infinitary
logics.

###  3.1. Consistency properties as forcing notions

It will be crucial for our purposes to focus on consistency properties for
multi-sorted signatures for relational languages.

#### Multi-sorted logics

Multi-sorted first order logic extends first order logic by introducing
_sorts_ for elements of its structures, by specifying for each variable and
constant symbol in the language the _sort_ of this symbol, and for any
function and relation symbol a declaration of the _sort_ of its entries (and
of its output for function symbols).

A typical relational signature for multi-sorted logics reads as $\langle
c^{i}_{k}:k\in K_{i},i\in I;\,R_{j}:j\in J\rangle$ where the upper index of
each constant symbol denotes the _sort_ of that symbol, and each relation
symbol $R_{j}$ comes with a arity $n^{j}$ and a map $s^{j}:n_{j}\to I$ which
specifies for each entry of the relation its sort.

Formulae of multi-sorted logic for relational language are built as in usual
first order logic with the further extra-clauses that:

  * •

$(t=s)$ is allowed ony if $t,s$ are terms of the same sort,

  * •

$R_{j}(t_{1},\dots,t_{n})$ is allowed if and only if $t_{k}$ is of sort
$s^{j}(k)$ for all $k$,

  * •

variable symbols are sorted and quantifiers are bounded to range over the
given sort.

A structure

$\mathcal{M}=\langle M_{i}:\,i\in I,R_{j}^{\mathcal{M}}:j\in
J,\,(c^{i}_{k})^{\mathcal{M}}:k\in K_{i},i\in I\rangle$

is a multi sorted structure for the multi-sorted signature $\langle
c^{i}_{k}:k\in K_{i},i\in I;\,R_{j}:j\in J\rangle$ in which each $M_{i}$
denotes the domain of the sort $i\in I$, each $(c^{i}_{k})^{\mathcal{M}}$ is
an element of $M_{i}$, and for all $j\in J$, $a_{1},\dots,a_{n_{j}}$,
$R_{j}^{\mathcal{M}}(a_{1},\dots,a_{n_{j}})$ holds if and only if $a_{k}\in
M_{s_{j}(k)}$ for $k=1,\dots,n_{j}$.

Multi-sorted logic can be easily identified with a fragment of first order
logic by identifying the multi-sorted structure

$\mathcal{M}=\langle M_{i}:\,i\in I,R_{j}^{\mathcal{M}}:j\in
J,\,(c^{i}_{k})^{\mathcal{M}}:k\in K_{i},i\in I\rangle$

for the multi-sorted signature $\langle c^{i}_{k}:k\in K_{i},i\in
I;\,R_{j}:j\in J\rangle$ with the first order structure:

$\mathcal{M}^{*}=\langle\bigcup_{i\in I}M_{i},\,M_{i}:\,i\in
I,R_{j}^{\mathcal{M}}:j\in J,\,(c^{i}_{k})^{\mathcal{M}}:k\in K_{i},i\in
I\rangle$

for the signature $\langle c^{i}_{k}:k\in K_{i},i\in I;\,R_{j}:j\in
J,\,X_{i}:i\in I\rangle$ with each $X_{i}$ a new unary predicate symbol
interpreted by $M_{i}$ in the structure $\mathcal{M}$. But there is an
inherent advantage in multi-sortd logic: for example by forbidding the
formulae $(t=s)$ for $t,s$ of different sorts one may render certain concepts
which are first order definable in

$\mathcal{M}^{*}=\langle\bigcup_{i\in I}M_{i},\,M_{i}:\,i\in
I,R_{j}^{\mathcal{M}}:j\in J,\,(c^{i}_{k})^{\mathcal{M}}:k\in K_{i},i\in
I\rangle$

undefinable in

$\mathcal{M}=\langle M_{i}:\,i\in I,R_{j}^{\mathcal{M}}:j\in
J,\,(c^{i}_{k})^{\mathcal{M}}:k\in K_{i},i\in I\rangle.$

For example this makes the notion of morphism for multi-sorted structure much
easier to handle than for first order structures (a morphism
$k:\mathcal{M}\to\mathcal{N}$ of multi sorted structues is a multi-map mapping
the domain of the sort $i$ in $\mathcal{M}$ into the domain of the sort $i$ in
$\mathcal{N}$ and respecting the interpretation of atomic formulae).

We will crucially use this fact in the key part of the proof of Lemma 3.40
(cfr. Claim 2). For the moment to appreciate the extra-flexibility given by
multi-sorted logic we present the following trivial example for the multi-
sorted signature $\left\\{0,1;A_{0},A_{1}\right\\}$ with $0,1$ sorts and the
$A_{i}$s unary predicates with sort $i$. Consider the two
$\left\\{0,1;A_{0},A_{1}\right\\}$-structures

$\mathcal{M}_{0}=(\mathbb{N},\mathbb{N};\mathbb{N},\mathbb{N})$
$\mathcal{M}_{1}=(X,\mathbb{N}\setminus X;X,\mathbb{N}\setminus X)$

where $X$ is an infinite coinfinite subset of $\mathbb{N}$. It is clear that
these structures are isomorphic as multi-sorted structures
$\left\\{0,1;A_{0},A_{1}\right\\}$ On the other hand (following the
identification suggested above of a multi-sorted structure $\mathcal{M}$ with
a first order structure $\mathcal{M}^{*}$) we get that

$\mathcal{M}_{0}^{*}=(\mathbb{N},\mathbb{N},\mathbb{N})$
$\mathcal{M}_{1}^{*}=(\mathbb{N},X,\mathbb{N}\setminus X)$

It is immediate to check that these two structures are not even elementarily
equivalent.

The point being that in multi-sorted logic we do not have to worry abot the
intersection of domains of differents sorts $i,j$ in a multi-sorted structure
$\mathcal{M}$, these two domains may be (partly) overlapping, but multi-sorted
logic is not able to detect this overlap.

We will use the extra-flexibility to produce a certain embedding
$k:\mathcal{M}\to\mathcal{N}$ of multi-sorted structures both having
interpretation of the sorts given by partially overlapping domains. The
collation of the maps of $i$ defined on the domains of the various sorts for
$\mathcal{M}$ may not even be a function: there could be overlap of the domain
$M_{i}$ of sort $i$ with $M_{j}$ of sort $j$ and for $a\in M_{i}\cap M_{j}$;
the multimap $k$, may assign a value using its $i$-th component different from
the value assigned by its $k$-th component.

######  Notation 3.2.

Let $\mathcal{L}=\mathcal{S}\cup\mathcal{R}\cup\mathcal{K}$ be a multi-sorted
relational signature with $\mathcal{S}$ its set of sorts, $\mathcal{R}$ its
set of relation symbols and $\mathcal{K}$ its set of constant symbols.

We denote an $\mathcal{L}$-structure

$\mathcal{M}=(M_{s}:s\in
S,R^{\mathcal{M}}:R\in\mathcal{R},c^{\mathcal{M}}:c\in\mathcal{K})$

by
$(\mathcal{S}^{\mathcal{M}},\mathcal{R}^{\mathcal{M}},\mathcal{K}^{\mathcal{M}})$.

######  Definition 3.3.

Given a signature $\mathcal{L}=\mathcal{S}\cup\mathcal{R}\cup\mathcal{K}$ the
$\mathfrak{L}_{\infty,\omega}$-logic for $\mathcal{L}$ is the smallest family
of formulae containing the $\mathcal{L}$-atomic formulae and closed under
quantifications, negation, infinitary disjunctions and conjunctions, i.e.:

  * •

If $\phi$ is an atomic $\mathcal{L}$-formula, it is also an
$\mathfrak{L}_{\infty,\omega}$-formula for $\mathcal{L}$.

  * •

If $\left\\{\phi_{i}(\vec{x}_{ij}):i<\gamma,j<\eta\right\\}$ is a set of
$\mathfrak{L}_{\infty,\omega}$-formulae for $\mathcal{L}$ with each
$\phi_{i}(\vec{x}_{ij})$ in displayed free variables
$\left\\{x_{ij}:j<\omega\right\\}$,

$\bigwedge_{i<\gamma}\phi_{i}(\vec{x}_{ij}),$
$\bigvee_{i<\gamma}\phi_{i}(x_{0},\dots,x_{n})$

are $\mathfrak{L}_{\infty,\omega}$-formulae for $\mathcal{L}$ in displayed
free variables $\left\\{x_{ij}:i<\gamma,j<\eta\right\\}$.

  * •

If $\phi(y,\vec{x})$ is an $\mathfrak{L}_{\infty,\omega}$-formula for
$\mathcal{L}$, so are $\exists y\phi(y,\vec{x})$ and $\forall
y\phi(y,\vec{x})$.

  * •

If $\phi$ is an $\mathfrak{L}_{\infty,\omega}$-formula for $\mathcal{L}$, so
is $\neg\phi$.

The semantics is defined on $\mathcal{L}$-structures
$\mathcal{M}=(M_{s}:s\in\mathcal{S},R^{\mathcal{M}}:R\in\mathcal{R},c^{\mathcal{M}}:c\in\mathcal{K})$
and assignments of the free variables to $M=\bigcup_{s\in\mathcal{S}}$ by the
obvious rules:

  * •

$\mathcal{M}\models R_{j}(\vec{x})[\vec{x}/\vec{a}]$

if and only if

$R_{j}^{\mathcal{M}}(\vec{a})\text{ holds}.$

  * •

$\mathcal{M}\models\neg\phi(\vec{x})[\vec{x}/\vec{a}]$

if and only if

$\mathcal{M}\not\models\phi(\vec{x})[\vec{x}/\vec{a}].$

  * •

$\mathcal{M}\models\bigvee_{i<\gamma}\phi_{i}(\vec{x}_{i})[\vec{x}_{i}/\vec{a}_{i}:i<\gamma]$

if and only if for some $i<\gamma$

$\mathcal{M}\models\phi_{i}(\vec{x}_{i})[\vec{x}_{i}/\vec{a}_{i}].$

  * •

$\mathcal{M}\models\bigwedge_{i<\gamma}\phi_{i}(\vec{x}_{i})[\vec{x}_{i}/\vec{a}_{i}:i<\gamma]$

if and only if for all $i<\gamma$

$\mathcal{M}\models\phi_{i}(\vec{x}_{i})[\vec{x}_{i}/\vec{a}_{i}].$

  * •

$\mathcal{M}\models\forall x\phi(x,\vec{y})[\vec{y}/\vec{b}]$

with $x$ of sort $s$ if and only if for all $a\in M_{s}$

$\mathcal{M}\models\phi(x,\vec{y})[x/a,\vec{y}/\vec{b}].$

  * •

$\mathcal{M}\models\exists x\phi(x,\vec{y})[\vec{y}/\vec{b}]$

with $x$ of sort $s$ if and only if for some $a\in M_{s}$

$\mathcal{M}\models\phi(x,\vec{y})[x/a,\vec{y}/\vec{b}].$

######  Notation 3.4.

A $\mathfrak{L}_{\infty,\omega}$-formula $\psi(\vec{x})$ is of
$\bigwedge\bigvee$-type if it is logically equivalent to a formula

$\bigwedge_{i\in I}\bigvee_{j\in J_{i}}\phi_{ij}(\vec{x})$

with each $\phi_{ij}$ an atomic or negated atomic formula.

######  Definition 3.5.

A $\mathfrak{L}_{\infty,\omega}$-theory $\Sigma$ for the signature
$\mathcal{L}=(\mathcal{S},\mathcal{R},\mathcal{K})$ (with
$\mathcal{K}=\left\\{c^{s}_{j}:j\in K_{s},\,s\in\mathcal{S}\right\\}$) is
_standard_ if it contains:

$\mathcal{L}$-equality axioms:

__

  1. (1):

$(c=c)$,

  2. (2):

$(c=d)\rightarrow(d=c)$,

  3. (3):

$\left[(c=d)\wedge(d=e)\right]\rightarrow(c=e)$,

  4. (4):

$\left[R(c_{1},\dots,c_{n})\wedge\bigwedge_{j=1}^{n}(d_{j}=c_{j})\right]\rightarrow
R(d_{1},\dots,d_{n})$.

for all constant symbols $c,d,e,c_{1},\dots,c_{n},c_{1},\dots,c_{n}$ of
$\mathcal{L}$ and all permitted formulae of type $(c=d)$,
$R(c_{1},\dots,c_{n})$ of the multi-sorted signature $\mathcal{L}$.

$\mathcal{L}$-quantifier elimination axioms:

$(\bigvee_{j\in K_{s}}\psi(c^{s}_{j}))\leftrightarrow\exists x\psi(x),$

for all $\mathfrak{L}_{\infty,\omega}$-formulae $\psi(x)$ in displayed free
variable $x$ of sort $s\in\mathcal{S}$;

$\forall x\bigvee_{j\in K_{s}}\,(x=c^{s}_{j})$

for all free variables $x$ of sort $s$ and for all sorts $s\in\mathcal{S}$.

$\Sigma$ is of _$\bigwedge\bigvee$ -type_ if it is standard and all other
axioms of $\Sigma$ are sentences of $\bigwedge\bigvee$-type.

######  Remark 3.6.

For a standard $\mathfrak{L}_{\infty,\omega}$-theory, the quantifier
elimination axioms give that any $\Pi_{2}$-sentence $\forall x\exists
y\psi(x,y)$ with $\psi(x,y)$ quantifier free is equivalent to a
$\bigwedge\bigvee$-type sentence. By passing to infinitary logic we will be
able to express the $\Pi_{2}$-fragment of an ordinary multi-sorted
$\mathcal{L}$-theory $T$ with the Henkin property (i.e. for any
$\mathcal{L}$-formula $\psi(x)$ there is some constant symbol
$c\in\mathcal{L}$ with $(\exists x\,\psi(x))\rightarrow\psi(c)\in T$) using
quantifier free sentences of $\bigwedge\bigvee$-type on the
$\mathfrak{L}_{\infty,\omega}$-theory extending $T$ with the equality and
quantifier elimination axioms.

#### Consistency properties

We will be interested in studying certain forcing notions whose properties are
best described by means of standard theories.

######  Definition 3.7.

Let $\mathcal{L}=\mathcal{S}\cup\mathcal{R}\cup\mathcal{K}$ be a multi-sorted
signature.

  * •

A $\nu:\mathcal{L}\to M\cup\bigcup_{n<\omega}\mathcal{P}\left(M^{n}\right)$
existing in some generic extension of $V$ is a generic
$\mathcal{L}$-assignment if
$\mathcal{M}=(\mathcal{S}^{\mathcal{M}},\mathcal{R}^{\mathcal{M}},\mathcal{K}^{\mathcal{M}})$
is an $\mathcal{L}$-structure with
$\mathcal{S}^{\mathcal{M}}=\left\\{M_{s}:s\in\mathcal{S}\right\\}$,
$M=\bigcup\mathcal{S}^{\mathcal{M}}$, and:

    * –

$\nu\restriction\mathcal{K}$ maps correctly and surjectively the constants of
sort $s$ to $M_{s}$,

    * –

$\nu\restriction\mathcal{R}$ maps correctly the relation symbols $R_{j}$ of
$\mathcal{R}$ of arity $n_{j}$ and type $s_{j}$ to subsets of
$M_{s_{j}(0)}\times\dots\times M_{s_{j}(n_{j}-1)}$.

  * •

Given a generic assignment $\nu$, $\Sigma_{\nu}$ is the family of
$\mathfrak{L}_{\infty,\omega}$-sentences for $\mathcal{L}$ realized in the
structure $\mathcal{M}$.

######  Warning 3.8.

In certain circumstances occurring below, when the interpretation of a certain
relation symbol $R$ in $\mathcal{R}$ is clear, we consider as an
$\mathcal{L}$-structure also one where the interpretation of $R$ is not
explicitly given (because the information conveyed on the intepretations of
the other symbols suffices to determine the natural interpretation of $R$).

The same occurs for generic assignments $\nu$, we will consider just the
assignment restricted to the constants (and eventually to some predicates),
the assignment $\nu$ on other predicates will be clear from the context.

This is a standard practice (consider for example the omission of the
interpretation for the relation symbol $=$ in the usal notation for first
order structures).

The following definition encapsulates the key provisions of a _consistency
property_ generated by a class of structures according to [KEIINFLOG], and
gives a powerful tool to produce “generic” models omitting a prescribed family
of types.

######  Definition 3.9.

Given a family of generic assignments $\mathcal{A}$ for a signature
$\mathcal{L}=\mathcal{S}\cup\mathcal{R}\cup\mathcal{K}$:

  * •

The forcing $P_{\mathcal{A}}$ consists of all those finite sets of atomic or
negated atomic $\mathcal{L}$-sentences which are contained in some
$\Sigma_{\nu}$ with $\nu\in\mathcal{A}$.

  * •

The order on $P_{\mathcal{A}}$ is given by reverse inclusion.

  * •

A set of $\mathcal{L}$-sentences $\Sigma$ is $\mathcal{A}$-consistent if $p\in
P_{\mathcal{A}}$ for every finite subset $p$ of $\Sigma$.

  * •

Given a maximally $\mathcal{A}$-consistent set of sentences $\Sigma$, the term
model $\mathcal{M}_{\Sigma}$ for $\mathcal{L}$ is defined as follows:

    * –

$[c]_{\Sigma}=\left\\{d\in\mathcal{K}:(c=d)\in\Sigma\right\\}$;

    * –

$s^{\Sigma}=\left\\{[c]_{\Sigma}:c\text{ of sort }s\right\\}$;

    * –

$R^{\Sigma}([c_{1}]_{\Sigma},\dots,[c_{n}]_{\Sigma})$ if and only if
$R(c_{1},\dots,c_{n})\in\Sigma$.

The canonical assignment $\nu_{\Sigma}$ maps $c$ to $[c]_{\Sigma}$, $R$ to
$R^{\Sigma}$.

Note that a filter $H$ on $P_{\mathcal{A}}$ is maximal if and only if
$\Sigma_{H}=\cup H$ is maximally $\mathcal{A}$-consistent. It is also clear
that $\mathcal{A}$-consistent sets are finitely satisfiable, hence consistent
in the ordinary sense.

######  Lemma 3.10.

Given a family of generic assignments $\mathcal{A}$ for a signature
$\mathcal{L}=\mathcal{S}\cup\mathcal{R}\cup\mathcal{K}$, the following holds
for the forcing $P_{\mathcal{A}}$:

  1. (1)

$\mathcal{M}_{\Sigma}$ is a well defined $\mathcal{L}$-structure for all
maximally $\mathcal{A}$-consistent $\Sigma$.

  2. (2)

Assume $H$ is $V$-generic for $P_{\mathcal{A}}$, $\Sigma_{H}=\cup H$.

Then for any $\mathcal{L}$-sentence

$\bigwedge_{i\in I}\bigvee_{j\in J_{i}}\psi_{ij}$

of type $\bigwedge\bigvee$, TFAE:

    1. (A)

$\mathcal{M}_{\Sigma_{H}}\models\bigwedge_{i\in I}\bigvee_{j\in
J_{i}}\psi_{ij}$.

    2. (B)

For all $i\in I$ and some $p\in H$, $D_{i}$ is dense below $p$, where

$D_{i}=\left\\{q\in P_{\mathcal{A}}:\psi_{ij}\in q\text{ for some $j\in
J_{i}$}\right\\}.$

######  Notation 3.11.

Given a maximal filter $H$ on $P_{\mathcal{A}}$ denote
$\mathcal{M}_{\Sigma_{H}}$ by $\mathcal{M}_{H}$, $[c]_{\Sigma_{H}}$ by
$[c]_{H}$, $R^{\Sigma_{H}}$ by $R^{H}$, $s^{\Sigma_{H}}$ by $s^{H}$,
$\nu_{\Sigma_{H}}$ by $\nu_{H}$.

$\mathcal{M}_{\dot{H}}$, $\nu_{\dot{H}}$, $R^{\dot{H}}$, $s^{\dot{H}}$,
$[-]_{\dot{H}}$ denote the canonical $P_{\mathcal{A}}$-names for the
corresponding objects determined by the $V$-generic filter $H$ for
$P_{\mathcal{A}}$.

###### Proof.

__

  1. (1)

It is clear that $[-]_{\Sigma}$ is an equivalence relation, and also that
$R^{\Sigma}$ is independent of the representative chosen in $[-]_{\Sigma}$. We
spell out some details:

$\left[-\right]_{\Sigma}$ is an equivalence relation:

Assume $(c=d),(d=e)\in\Sigma_{H}$. The sets
$\left\\{(c=d),(d=e),\neg(c=e)\right\\}$, $\left\\{(c=d),\neg(d=c)\right\\}$,
$\left\\{\neg(c=c)\right\\}$ are not even consistent, therefore any maximally
$\mathcal{A}$-consistent set (henceforth consistent) containing $(c=d),(d=e)$
must also contain $(c=e)$, $(d=c)$, $(c=c)$.

$R^{\Sigma}$ is well defined:

Assume $[c_{i}]_{\Sigma}=[d_{i}]_{\Sigma}$ for $i=1,\dots,n$ then:

> $R^{\Sigma}([c_{1}]_{\Sigma},\dots,[c_{n}]_{\Sigma})$
>
> if and only if
>
> $R(c_{1},\dots,c_{n})\in\Sigma$
>
> if and only if (since
> $\left\\{(c_{1}=d_{1}),\dots,(c_{n}=d_{n}),R(c_{1},\dots,c_{n}),\neg
> R(d_{1},\dots,d_{n})\right\\}$ is not even consistent)
>
> $R(d_{1},\dots,d_{n})\in\Sigma.$

  2. (2)

Assume $H$ is $V$-generic for $P_{\mathcal{A}}$.

One direction is clear: if for some $p\in H$ $D_{i}$ is predense below $p$ for
all $i\in I$, then $H\cap D_{i}\neq\emptyset$ for all $i\in I$, hence for all
$i$ there is $j$ such that $\psi_{ij}\in\Sigma_{H}$. This immediately yields
that

$\mathcal{M}_{H}\models\bigwedge_{i\in I}\bigvee_{j\in J_{i}}\psi_{ij}.$

For the converse assume

$\mathcal{M}_{H}\models\bigwedge_{i\in I}\bigvee_{j\in J_{i}}\psi_{ij}.$

Then some $p\in H$ is such that

$p\Vdash_{P_{\mathcal{A}}}\ulcorner\mathcal{M}_{\dot{H}}\models\bigwedge_{i\in
I}\bigvee_{j\in J_{i}}\psi_{ij}\urcorner.$

By definition (since $Z=\left\\{(i,j):i\in I,j\in J\right\\}$ is in $V$ and so
is $\bigwedge_{i\in I}\bigvee_{j\in J_{i}}\psi_{ij}$)

$p\Vdash_{P_{\mathcal{A}}}\forall\tau\in\check{I}\exists\sigma\in\check{J}_{i}\ulcorner\mathcal{M}_{\dot{H}}\models\psi_{\tau\sigma}\urcorner.$

By definition of the forcing relation (using the fact that $\check{Z}_{H}=Z$
for all $V$-generic filters $H$, and the forcing clauses for existential
formulae), this holds if and only if

$D^{*}_{i}=\left\\{q\in P:\exists
j\,(q\Vdash\ulcorner\mathcal{M}_{\dot{H}}\models\psi_{\check{i}\check{j}}\urcorner)\right\\}$

is open dense below $p$ for all $i\in I$.

Now if
$q\Vdash\ulcorner\mathcal{M}_{\dot{H}}\models\psi_{\check{i}\check{j}}\urcorner$
and $H$ is $V$-generic for $P_{\mathcal{A}}$ with $q\in H$, we get that
$\psi_{ij}\in\Sigma_{H}$, therefore $q\cup\left\\{\psi_{ij}\right\\}\in H$.

Hence we conclude that

$D_{i}=\left\\{q\in P:\exists j\,(\psi_{ij}\in q)\right\\}$

is dense below $p$ for all $i\in I$.

∎

######  Remark 3.12.

Note that the Lemma holds in this generality just for sentences of
$\bigwedge\bigvee$-type. For example consider a sentence

$\bigvee_{j\in J}\bigwedge_{i\in I_{j}}\psi_{ij}$

Running the proof as before for this sentence we get to the conclusion that

$\mathcal{M}_{H}\models\bigvee_{j\in J}\bigwedge_{i\in I_{j}}\psi_{ij}$

if and only if for some $j\in J$ and some $q\in H$

$q\Vdash\ulcorner\mathcal{M}_{\dot{H}}\models\bigwedge_{i\in
I_{j}}\psi_{ij}\urcorner.$

Now this is in general false because typically a condition $q\in
P_{\mathcal{A}}$ can decide only finitely many atomic $\mathcal{L}$-sentences
(the unique effective method to check whether $q$ forces the truth in
$\mathcal{M}_{\dot{H}}$ of an atomic $\mathcal{L}$-sentence is to check that
it belongs to $q$). On the other hand the above conditions require $q$ to
decide the infinitely many atomic $\mathcal{L}$-sentences $\psi_{ij}$ for all
$i\in I_{j}$.

######  Definition 3.13.

Given a family of generic assignments $\mathcal{A}$, we let
$\Sigma_{\mathcal{A}}$ denote the family of $\mathcal{L}$-sentences $\psi$ in
$V$ of type $\bigwedge\bigvee$ such that

$\emptyset\Vdash_{P_{\mathcal{A}}}\ulcorner\mathcal{M}_{\dot{H}}\models\psi\urcorner.$

The following observation is very useful:

######  Fact 3.14.

Assume $p\in P_{\mathcal{A}}$ and $\psi:=\bigwedge_{i\in I}\bigvee_{j\in
J_{i}}\psi_{ij}$ is a sentence of $\bigwedge\bigvee$-type such that any
$\mathcal{A}$-assignment $\nu$ with $p\subseteq\Sigma_{\nu}$ has $\psi$ in
$\Sigma_{\nu}$. Then $\mathcal{M}_{H}\models\psi$ for any $H$ $V$-generic for
$p$.

In particular if a family of $\mathcal{L}$-assignments $\mathcal{A}$ is
axiomatized by a standard $\mathcal{L}$-theory $\Sigma$,
$\mathcal{M}_{H}\models\Sigma$ for any $H$ $V$-generic for $\Sigma$.

###### Proof.

The sets

$D_{i}=\left\\{q\in P:\exists j\,(\psi_{ij}\in q)\right\\}$

required to check $\mathcal{M}_{H}\models\psi$ are dense below $p$. ∎

###  3.2. The forcing $P^{*}_{0}$

First of all it is convenient to isolate the smallest transitive fragment
$X_{(\mathcal{J},r,f,T)}$ of $V[G]$ having as elements all the objects
required to define a semantic certificate $(\mathcal{J},r,f,T)$ existing in
$V[G]$ and computing correctly all the properties of this semantic certificate
we are interested in. Now $P^{*}_{0}$ will be obtained by gluing together
finite pieces of information describing in an appropriate multi-sorted
signature the properties of the structures $(X_{(\mathcal{J},r,f,T)},\in)$. In
fact $P^{*}_{0}$ will be $P_{\mathcal{A}}$ for a given family $\mathcal{A}$ of
generic assignment $\nu:\mathcal{L}^{0}\to X_{(\mathcal{J},r,f,T)}$ satisfying
certain natural prescriptions. $\mathcal{L}^{0}$ will contain the sorts,
predicates and constants needed to encode what could be true or false in a
generic structure $(X_{(\mathcal{J},r,f,T)},\in)$. A generic filter for
$P^{*}_{0}$ will add a term model for $\mathcal{L}^{0}$. By the result of the
previous section it is to be expected that if things are organized properly
the term model defined by the generic filter for $P^{*}_{0}$ will be
isomorphic to the multi-sorted presentation in signature $\mathcal{L}^{0}$ of
a semantic certificate (to get this we just have to ensure that the
$\mathcal{L}^{0}$-theory associated to semantic certificates is of
$\bigwedge\bigvee$-type and then apply Fact 3.14, with some extra care to
grant well-foundedness of the generic term model). If $P^{*}_{0}$ were
stationary set preserving, one would be (almost) done. However this basic set-
up is not yet sufficient to argue that $P^{*}_{0}$ is stationary set
preserving, just to infer that generic filters for $P^{*}_{0}$ add semantic
certificates $(\mathcal{J},r,f,T)$ for $A,D$. For the moment however let us
analyze in detail the forcing $P^{*}_{0}$ to get accustomed with the more
intricate arguments of the next section where the chain of forcings
$\left\\{P_{\alpha}:\alpha\in C\cup\left\\{\kappa\right\\}\right\\}$ will be
introduced, with each one adding a semantic certificate, and with $P_{\kappa}$
being also stationary set preserving.

######  Definition 3.15.

Given a semantic certificate $(\mathcal{J},r,f,T)$ for $A,D$ existing in some
$V[K]$, let

$\mathcal{J}=\left\\{j_{\alpha\beta}:N_{\alpha}\to
N_{\beta}:\alpha\leq\beta\leq\omega_{1}^{V}\right\\}.$

$X_{(\mathcal{J},r,f,T)}$ is the set

$(\bigcup_{i\leq\omega_{1}^{V}}N_{\alpha})\cup\left\\{N_{\alpha}:\alpha\leq\omega_{1}^{V}\right\\}\cup\left\\{j_{\alpha\beta}:\alpha\leq\beta\leq\omega_{1}^{V}\right\\}\cup\left\\{G_{\alpha}:\alpha<\omega_{1}\right\\}\cup\left\\{r,f\right\\}.$

$\mathcal{X}_{(\mathcal{J},r,f,T)}$ is the multi sorted structure of sorts
$N_{\alpha}:\alpha\leq\omega_{1}^{V},\left\\{r,f\right\\}$ and binary
relations $\in\restriction N_{\alpha}$ of type $(N_{\alpha},N_{\alpha})$,
unary relations $G_{\alpha}$ of type $N_{\alpha}$, binary relations
$j_{\alpha\beta}$ of type $(N_{\alpha},N_{\beta})$, unary relation $T$ of
type121212Denoting the extension of $T$, which is a subset of
$N_{\omega_{1}}$. $N_{\omega_{1}}$, binary relation
$\sqsubseteq^{2}\restriction T$ of type131313 $(s,t)\sqsubseteq^{2}(u,v)$ if
and only if $(s,t),(u,v)\in T$, $s\sqsubseteq u$, $t\sqsubseteq v$.
$(N_{\omega_{1}},N_{\omega_{1}})$, ternary relation $\text{br}_{T}$ of
type141414With $\text{br}_{T}(x,y,z)$ holding just if $x=(s,t)\in T$,$y=r$,
$z=f$ and $s\sqsubseteq r$, $t\sqsubseteq f$.
$(N_{\omega_{1}},\left\\{r,f\right\\},\left\\{r,f\right\\})$, ternary relation
$\text{{\rm Cod}}^{*}$ of type151515Recall $\text{{\rm
Cod}}(r)=(N_{0},A\cap\omega_{1}^{N_{0}})$; $\text{{\rm Cod}}^{*}(x,y,z)$ holds
if and only if $x\in N_{0}$ $y=A\cap\omega_{1}^{N_{0}}$, $z=r$.
$(N_{0},N_{0},\left\\{r,f\right\\})$, satisfaction predicates161616To be
represented by the pairs
$\langle\ulcorner\psi\urcorner,(a_{1},\dots,a_{m})\rangle$ with
$\psi(x_{1},\dots,x_{m})$ an $\in$-formula in displayed free variables and
$(a_{1},\dots,a_{m})\in N_{\alpha}^{m}$ such that
$(N_{\alpha},\in)\models\psi(x_{1},\dots,x_{m})[x_{1}/a_{1},\dots,x_{m}/a_{m}].$
$\operatorname{Sat}_{N_{\alpha}}$ of type
$(\dot{N}_{\alpha},\dot{N}_{\alpha})$ for $\alpha\leq\omega_{1}$,

$\langle
N_{\alpha}:\alpha\leq\omega_{1}^{V},\,\left\\{r,f\right\\};\,\in\restriction
N_{\alpha},\operatorname{Sat}_{N_{\alpha}}:\alpha\leq\omega_{1}^{V},\,G_{\alpha}:\alpha<\omega_{1}^{V},\,j_{\alpha\beta}:\alpha\leq\beta\leq\omega_{1}^{V},\sqsubseteq^{2}\restriction
T,\,\text{br}_{T},\,\text{{\rm Cod}}^{*}\rangle.$

######  Remark 3.16.

__

  * •

The list

$\left\\{N_{\alpha}:\alpha\leq\omega_{1}\right\\}\cup\left\\{j_{\alpha\beta}:\alpha\leq\beta\leq\omega_{1}^{V}\right\\}\cup\left\\{G_{\alpha},:\alpha<\omega_{1}\right\\}\cup\left\\{r,f\right\\}$

gives the $\in$-maximal element of $(X_{(\mathcal{J},r,f,T)},\in)$ and the
list is not redundant, i.e any element in the above list does not belong to
any of the others, and any $\in$-maximal element of the graph of the
$\in$-relation over $(X_{(\mathcal{J},r,f,T)},\in)$ is in the above list.

  * •

In essence $X_{(\mathcal{J},r,f,T)}$ is a set containing all the elements and
predicates of the multisorted structure $\mathcal{X}_{(\mathcal{J},r,f,T)}$
except a few objects which can be easily reconstructed from the remaining ones
(e.g. the sort $\left\\{r,f\right\\}$, the predicates
$\operatorname{Sat}_{N_{\alpha}}$, $\text{br}_{T}$, $\text{{\rm Cod}}^{*}$).

  * •

$H_{\omega_{2}}^{V},T$ are both subsets of $N_{\omega_{1}^{V}}$ (by Condition
5 for the weak semantic certificate for $A$ as witnessed by $T$).

  * •

Note that $X_{(\mathcal{J},r,f,T)}$ is not transitive: if $\langle
a,b\rangle=\left\\{\left\\{a\right\\},\left\\{a,b\right\\}\right\\}\in
j_{\alpha\beta}$, $\left\\{a\right\\}\in N_{\alpha}$, but
$\left\\{a,b\right\\}\in N_{\alpha}\cup N_{\beta}$ may not be neither in
$N_{\alpha}$, nor in $N_{\beta}$. However with the exception of the elements
in the graph of $j_{\alpha\beta}$, all other elements of
$X_{(\mathcal{J},r,f,T)}$ are contained in some $N_{\alpha}$.

  * •

$X_{(\mathcal{J},r,f,T)}$ has size bounded by $|\omega_{2}|^{V[K]}$.

The key point is that (as we will see) the
$\mathfrak{L}_{\infty,\omega}$-theory of the structures
$\mathcal{X}_{(\mathcal{J},r,f,T)}$ completely describes the notion of
semantic certificate up to type isomorphism.

Given a semantic certificate $(\mathcal{J},r,f,T)$ for $A,D$ as witnessed by
$T$ with

$\mathcal{J}=\left\\{j_{\alpha\beta}:N_{\alpha}\to
N_{\beta}:\,\alpha\leq\beta\leq\omega_{1}^{V}\right\\},$

$\mathcal{L}^{0}$ is in $V$ the multi-sorted signature with sorts, constants,
and predicate symbols to be interpreted by the relevant objects (or subsets —
see Warning 3.8) of $X_{(\mathcal{J},r,f,T)}$ which define the associated
multi-sorted structure $\mathcal{X}_{(\mathcal{J},r,f,T)}$.

######  Definition 3.17.

$\mathcal{L}^{0}$ consists of the following sorts, constants, and predicate
symbols:

Sorts:

__

  1. (a):

$\dot{N}_{i}$ to denote the extension of $N_{i}$ for each
$i\leq\omega_{1}^{V}$,

  2. (b):

$\dot{\left\\{r,f\right\\}}$ to denote the set given by the elements of the
selected branch $(r,f)$ of $T$.

Constants:

__

  1. (c):

$\check{x}$ of sort $\dot{N}_{\omega_{1}^{V}}$ for $x\in H_{\omega_{2}}$ to
denote the elements of $H_{\omega_{2}}$.

  2. (d):

symbols $\left\\{\dot{c}_{n,i}:n\in\omega\right\\}$ of sort $\dot{N}_{i}$ for
$i<\omega_{1}^{V}$ needed to denote the elements of $N_{i}$ (but only for
$i<\omega_{1}^{V}$);

  3. (e):

symbols $\left\\{\dot{c}_{j,\omega_{1}^{V}}:j<\omega_{1}^{V}\right\\}$ of sort
$\dot{N}_{\omega_{1}^{V}}$;

  4. (f):

symbols $\dot{r},\dot{f}$ of sort $\dot{\left\\{r,f\right\\}}$ to be
interpreted in some $V[G]$ by the selected branch $(r,f)$ through $T$ such
that $\text{{\rm Cod}}(r)=(N_{0},a_{0})$.

Predicates:

__

  1. (g):

A unary predicate symbol symbol $\dot{T}$ of type $\dot{N}_{\omega_{1}}$ to
denote the extension of the ($2$-dimensional) witnessing tree $T\subseteq
N_{\omega_{1}}$;

  2. (h):

Unary predicate symbols $\left\\{\dot{G}_{j}:j<\omega_{1}\right\\}$ (each of
type $\dot{N}_{j}$ for $j<\omega_{1}^{V}$) to denote the $N_{\alpha}$-generic
filters such that $N_{\alpha+1}$ is the ultrapower of $N_{\alpha}$ by
$G_{\alpha}$;

  3. (i):

Binary predicate symbols $\dot{j}_{\alpha\beta}$ of type
$(\dot{N}_{\alpha},\dot{N}_{\beta})$ to denote $j_{\alpha\beta}$ for
$\alpha\leq\beta\leq\omega_{1}^{V}$;

  4. (j):

A ternary predicate symbol $\text{br}_{T}$ of type
$(\dot{N}_{\omega_{1}},\dot{\left\\{r,f\right\\}},\dot{\left\\{r,f\right\\}})$
to denote the initial segment relation between elements of $T$ and the branch
$(r,f)$;

  5. (k):

For each $\alpha\leq\omega_{1}^{V}$ a binary predicate $\in_{N_{\alpha}}$ of
type $(\dot{N}_{\alpha},\dot{N}_{\alpha})$ to denote the $\in$-relation
restricted to $N_{\alpha}$;

  6. (l):

For each $\alpha\leq\omega_{1}^{V}$ a satisfaction predicate

$\operatorname{Sat}_{N_{\alpha}}(\ulcorner\psi(x_{1},\dots,x_{m})\urcorner)$

of type171717It is clear that the interpretation of this predicate symbol will
subsume the interpretation of $\in_{N_{\alpha}}$ by conisdering the formula
$\operatorname{Sat}_{N_{\alpha}}(\ulcorner x\in y\urcorner)$. However it is
convenient (just for notational simplicity) to have a special symbol to denote
$\in\restriction N_{\alpha}$. $(\dot{N}_{\alpha},\dot{N}_{\alpha})$ to be
represented by the pairs
$\langle\ulcorner\psi\urcorner,(a_{1},\dots,a_{m})\rangle$ with
$\psi(x_{1},\dots,x_{m})$ an $\in$-formula in displayed free variables and
$(a_{1},\dots,a_{m})\in N_{\alpha}^{m}$ such that

$(N_{\alpha},\in)\models\psi(x_{1},\dots,x_{m})[x_{1}/a_{1},\dots,x_{m}/a_{m}];$

  7. (m):

A ternary predicate symbol $\text{{\rm Cod}}^{*}$ of type
$(\dot{N}_{0},\dot{N}_{0},\dot{\left\\{r,f\right\\}})$ to encode the fact that
$\text{{\rm Cod}}(r)=(N_{0},a)$ by holding just of the triples $x,y,z$ with
$y=A\cap\omega_{1}^{N_{0}}$ and $z=r$.

Note that $\mathcal{L}^{0}\in V$ has size $\omega_{2}$ in $V$.

######  Definition 3.18.

Let $(\mathcal{J},r,f,T)$ be a weak semantic certificate for $A,D$ with

$\mathcal{J}=\left\\{j_{\alpha\beta}:N_{\alpha}\to
N_{\beta}:\,\alpha\leq\beta\leq\omega_{1}^{V}\right\\}.$

A map $\nu$ with domain $\mathcal{L}^{0}$ is an _admissible interpretation_
for $(\mathcal{J},r,f,T)$ if it respects the following constraints on the
interpretations of constants and predicates:

Sorts:

__

  1. (a):

$\nu(\dot{N}_{i})=N_{i}$ for each $i\leq\omega_{1}^{V}$.

  2. (b):

$\nu(\dot{\left\\{r,f\right\\}})=\left\\{r,f\right\\}$.

Constant symbols:

__

  1. (c):

$\nu(\check{x})=x$ for every $x\in H_{\omega_{2}}$.

  2. (d):

$\nu[\left\\{\dot{c}_{n,\alpha}:n\in\omega\right\\}]=N_{\alpha}$ and
$\nu(c_{0,\alpha})=A\cap\omega_{1}^{N_{\alpha}}$ for all
$\alpha<\omega_{1}^{V}$.

  3. (e):

$\nu[\left\\{\dot{c}_{j,\omega_{1}^{V}}:j\in\omega_{1}^{V}\right\\}]=N_{\omega_{1}^{V}}$
and $\nu(c_{0,\omega_{1}^{V}})=A$.

  4. (f):

$\nu(\dot{r})=r\in p[T]$, $\nu(\dot{f})=f$ with $(r,f)$ a branch of $T$ and
$\text{{\rm Cod}}(r)=(N_{0},A\cap\omega_{1}^{N_{0}})$.

Predicates:

__

  1. (g):

$\nu(\dot{T})=T$.

  2. (h):

$\nu(\dot{G}_{\alpha})=G_{\alpha}$ for $\alpha<\omega_{1}^{V}$.

  3. (i):

$\nu(\dot{j}_{\alpha\beta})=j_{\alpha\beta}$ for all
$\alpha\leq\beta\leq\omega_{1}^{V}$.

  4. (j):

$\nu(\text{br}_{T})=\left\\{\langle(s,t),r,f\rangle:\,s\sqsubseteq
r,t\sqsubseteq f\right\\}$.

  5. (k):

$\nu(\operatorname{Sat}_{N_{\alpha}})$ as prescribed by l of Def. 3.17.

  6. (l):

$\nu(\text{{\rm Cod}}^{*})=\left\\{\langle
x,A\cap\omega_{1}^{N_{0}},r\rangle:\,x\in N_{0}\right\\}$.

######  Warning 3.19.

A key point is that once we fixed the structure
$\mathcal{X}_{(\mathcal{J},r,f,T)}$ which is the target of $\nu$, we have a
certain freedom in changing the value of the assignments on constant symbols
(for example for all those of the form $\dot{c}_{n,\alpha}$ for $n>0$ and
$\alpha\leq\omega_{1}^{V}$), while maintaining that the (so modified
assignment) is still admissible; but we have no freedom in changing the
interpretation of the predicate symbols. In particular many of the constant
symbols could also be considered sorted variables.

  * •

Given an admissible assignment $\nu$, $\Sigma_{\nu}$ is the set of
$\mathfrak{L}_{\infty,\omega}$-sentences for $\mathcal{L}^{0}$ realized in the
structure $\mathcal{X}_{(\mathcal{J},r,f,T)}$ by the assignment $\nu$.

  * •

A set $\Sigma$ of $\mathfrak{L}_{\infty,\omega}$-sentences for
$\mathcal{L}^{0}$ is _generically consistent_ if in some generic extension
$V[G]$ of $V$ there is a semantic certificate $(\mathcal{J},r,f,T)$ for $A,D$,
and an admissible assignment $\nu:\mathcal{L}^{0}\to X_{(\mathcal{J},r,f,T)}$
such that $\Sigma\subseteq\Sigma_{\nu}$.

The first key observation is that the $\mathcal{L}^{0}$-isomorphism types of a
semantic certificate define an elementary class for
$\mathfrak{L}_{\infty,\omega}$ which is axiomatized by a _standard theory_
(cfr. Def. 3.5).

To accomodate our $\mathfrak{L}_{\infty,\omega}$-axiomatization of the notion
of semantic certificate it is convenient to detail more the nature of the map
$\text{{\rm Cod}}:2^{\omega}\to H_{\omega_{1}}$.

######  Convention 3.20.

We assume the following properties of Cod in case $\text{{\rm
Cod}}(r)=(N,a)\in\mathbb{P}_{\mathrm{max}}$:

  * •

$r$ is identified (modulo a recursive bijection $n\mapsto\langle
k_{n},j_{n}\rangle$ of $\omega$ with $\omega^{2}$) with a well-founded
extensional relation $E_{r}$ with domain $\omega$;

  * •

the Mostowski collapsing map $\pi$ of the structure $(\omega,E_{r})$ has as
range $\operatorname{trcl}{\left\\{\langle N,a\rangle\right\\}}$ and maps $0$
to $N$, $1$ to $\left\\{N\right\\}$, $2$ to $\left\\{N,a\right\\}$, $3$ to
$\langle N,a\rangle$, $4$ to $\left\\{\langle N,a\rangle\right\\}$, $5$ to
$a$.

######  Fact 3.21.

Let $\Sigma^{0}$ be the $\mathcal{L}^{0}$ theory for
$\mathfrak{L}_{\infty,\omega}$ given by the $\mathcal{L}^{0}$-equality axioms
and the $\mathcal{L}^{0}$-quantifier elimination axioms (cfr. Def. 3.5), and
the following list of axioms:

  1. (I)

Axioms to characterize the extensions of $\dot{T}$ and of $H_{\omega_{2}}^{V}$
inside $\dot{N}_{\omega_{1}}$:

    1. (a)

For all $x,y\in H_{\omega_{2}}$

$(\check{x}\in\check{y})\text{ if $x\in y$,}$
$(\check{x}\not\in\check{y})\text{ if $x\not\in y$.}$

    2. (b)

The infinitary conjunction of infinitary disjunctions

$\bigwedge_{x\in
H_{\omega_{2}}}(\bigvee_{j<\omega_{1}^{V}}\check{x}=\dot{c}_{j,\omega_{1}}).$

    3. (c)

For all constant symbols $c$ of sort $\dot{N}_{\omega_{1}^{V}}$

$\dot{T}(c)\leftrightarrow\bigvee_{(s,t)\in T}(c=\check{\langle s,t\rangle})$

  2. (II)

The following axioms to describe the properties of an iteration $\mathcal{J}$:

    1. (a)

For all $\alpha\leq\beta\leq\omega_{1}^{V}$

$\bigwedge_{n<\omega}\bigvee_{j<\omega_{1}^{V}}[\dot{j}_{\alpha\omega_{1}^{V}}(\dot{c}_{n,\alpha})=\dot{c}_{j,\omega_{1}^{V}}],$
$\bigwedge_{n<\omega}\bigvee_{m<\omega}(\dot{j}_{0}(\dot{c}_{n,\alpha})=\dot{c}_{m,\beta}).$

    2. (b)

For all $\alpha<\beta\leq\omega_{1}^{V}$ and constant symbols
$\dot{c}_{n,\alpha},\dot{c}_{m,\beta}$ for $n,m<\omega$

$\left[\dot{G}_{\alpha}(\dot{c}_{n,\alpha})\wedge\dot{j}_{\alpha\beta}(\dot{c}_{n,\alpha})=\dot{c}_{m,\beta})\right]\leftrightarrow\left[\operatorname{Sat}_{N_{\beta}}(\ulcorner\omega_{1}\in\dot{c}_{m,\beta}\urcorner)\wedge\operatorname{Sat}_{N_{\alpha}}(\ulcorner\dot{c}_{n,\alpha}\subseteq\omega_{1}\urcorner)\right].$

    3. (c)

For all $\alpha<\beta\leq\omega_{1}^{V}$ and constant symbols
$\dot{c}_{m,\beta}$ for181818This sentence states that
$j_{\alpha\beta}[N_{\alpha}]=\left\\{j_{\alpha\beta}(f)(\omega_{1}^{N_{\alpha}}):f\in
N_{\alpha},\operatorname{dom}{f}=\omega_{1}^{N_{\alpha}}\right\\}$. $m<\omega$

$\bigvee_{n,k<\omega}\left[(\dot{c}_{k,\beta}=\dot{j}_{\alpha\beta}(c_{n,\alpha}))\wedge\operatorname{Sat}_{N_{\beta}}(\ulcorner\dot{c}_{k,\beta}(\omega_{1})=c_{m,\beta}\urcorner)\right].$

    4. (d)

For all $\alpha<\omega_{1}^{V}$

$\bigwedge_{n<\omega}\operatorname{Sat}_{N_{\alpha}}(\ulcorner\dot{c}_{n,\alpha}\text{
is a dense subset of
}\mathcal{P}\left(\omega_{1}\right)/_{\mathbf{NS}_{\omega_{1}}}\urcorner)\rightarrow\bigvee_{m<\omega}\,(\dot{G}_{\alpha}(\dot{c}_{m,\alpha})\wedge\dot{c}_{m,\alpha}\in\dot{c}_{n,\alpha}).$

  3. (III)

The following sentences describing the properties an iteration $\mathcal{J}$,
a real $r$ and an $f:\omega\to\kappa$ must satisfy to grant that
$(\mathcal{J},r,f,T)$ is a semantic certificate:

    1. (a)

The sentence

$\bigwedge_{n<\omega}\bigvee_{(s,t)\in
T\cap(2\times\omega_{2}^{V})^{n}}\text{br}_{T}(\langle
s,t\rangle,\dot{r},\dot{f})$ $\bigwedge_{(s,t),(u,v)\in
T}\left[\text{br}_{T}(\check{\langle
s,t\rangle},\dot{r},\dot{f})\wedge\text{br}_{T}(\check{\langle
u,v\rangle},\dot{r},\dot{f})\right]\rightarrow(\check{\langle
s,t\rangle}\sqsubseteq^{2}\check{\langle u,v\rangle}\vee\check{\langle
u,v\rangle}\sqsubseteq^{2}\check{\langle s,t\rangle})$

    2. (b)

The axioms191919These axioms formalize that $\text{{\rm
Cod}}(r)=(N_{0},a_{0})$ by imposing that $(N_{0},\in)$ is isomorphic to
$E_{r}\restriction[5;\infty)$ in accordance with notation 3.20, and that
$c_{0,0}$ is assigned to $A\cap\omega_{1}^{N_{0}}$.

$\bigwedge_{n<\omega}\text{{\rm Cod}}^{*}(c_{n,0},c_{0,0},\dot{r}),$
$\bigwedge_{n\in\omega,k_{n},j_{n}\geq 5,\langle s,t\rangle\in
T}(\text{br}_{T}(\check{\langle
s,t\rangle},\dot{r},\dot{f})\wedge\check{s(n)}=\check{1})\rightarrow\operatorname{Sat}_{N_{0}}(\ulcorner
c_{k_{n}-5,0}\in c_{j_{n}-5,0}\urcorner),$
$\bigwedge_{n\in\omega,k_{n},j_{n}\geq 5,\langle s,t\rangle\in
T}(\text{br}_{T}(\check{\langle
s,t\rangle},\dot{r},\dot{f})\wedge\check{s(n)}=\check{0})\rightarrow\operatorname{Sat}_{N_{0}}(\ulcorner
c_{k_{n}-5,0}\not\in c_{j_{n}-5,0}\urcorner).$

    3. (c)

The sentence

$\dot{j}_{0\omega_{1}^{V}}(\check{c}_{0,0})=A.$

    4. (d)

For202020This axioms grants that $(H_{\omega_{2}},\in)$ sits inside
$(N_{\omega_{1}}^{V},\in)$ as a transitive subclass. all constant symbols $c$
of sort $\dot{N}_{\omega_{1}}$ and $y\in H_{\omega_{2}}$

$c\in\check{y}\leftrightarrow\bigvee_{x\in y}\check{x}=c.$

    5. (e)

The infinitary conjunction

$\bigwedge_{S\in(\mathcal{P}\left(\omega_{1}\right)\setminus\mathbf{NS}_{\omega_{1}})^{V}}\operatorname{Sat}_{N_{\omega_{1}^{V}}}(\ulcorner\dot{S}\text{
is stationary}\urcorner).$

Then:

  1. (1)

$\Sigma^{0}$ is standard (cfr. Def. 3.5).

  2. (2)

$\Sigma^{0}$ is realized by any admissible assignement $\nu$.

  3. (3)

Whenever
$\mathcal{N}=\langle(\mathcal{S}^{0})^{\mathcal{N}},(\mathcal{R}^{0})^{\mathcal{N}},(\mathcal{K}^{0})^{\mathcal{N}}\rangle$
is a $\mathcal{L}^{0}$-model of $\Sigma^{0}$ existing in some transitive model
$W$, we have that:

     * •

The domain of each sort of $(\mathcal{S}^{0})^{\mathcal{N}}$ has as extension
the interpretations of the constant symbols of $\mathcal{K}^{0}$ of that sort.

     * •

The sort $\dot{N}_{\alpha}$ of $\mathcal{N}$ is well founded and extensional
for all $\alpha\leq\omega_{1}^{V}$.

     * •

The transitive collapse of the sorts $\dot{N}_{\alpha}$ of $\mathcal{N}$
define a semantic certificate $(\mathcal{J},r,f,T)$ for $A,D$ existing in $W$
with $r(n)=i$ and $f(n)=j$ if and only if for some $(s,t)\in T$ with $s(n)=i$
and $f(n)=j$, $\text{br}_{T}(\check{\langle s,t\rangle},r,f)$.

###### Proof.

The proof that $\Sigma^{0}$ is standard and that
$\Sigma^{0}\subseteq\Sigma_{\nu}$ for any admissible assignment $\nu$ is left
to the reader. It consists in the tyresome checking that all the above
sentences are of $\bigwedge\bigvee$-type and are in $\Sigma_{\nu}$ for any
admissible assignment $\nu$.

Let $W$ be a transitive model of $\mathsf{ZFC}$ and $\mathcal{N}$ be in $W$ a
structure satisfying $\Sigma^{0}$. The axiom for quantifier elimination grants
that $\mathcal{N}$ has as domain of its sorts exactly the interpretation of
the constant symbols of $\mathcal{L}^{0}$ of that sort. The axioms of Type I
grant that

$(\left\\{\check{x}^{\mathcal{N}}:x\in
H_{\omega_{2}}\right\\},\in_{N_{\omega_{1}^{V}}}^{\mathcal{N}})$

is isomorphic to $(H_{\omega_{2}},\in)$ and also that

$(\left\\{c^{\mathcal{N}}:\mathcal{N}\models\dot{T}(c)\right\\},(\sqsubseteq^{2})^{\mathcal{N}})$

is isomorphic to

$(T,\sqsubseteq^{2}).$

These axioms combined with axioms IIIa grant that:

  * •

The unique infinite sequence $(r,f)\in V[G]$ given by $r(n)=i$ and
$f(n)=\alpha$ if

$\mathcal{N}\models\dot{r}(\dot{n})=\dot{i}\wedge\dot{f}(\dot{n})=\check{\alpha}$

is a branch through $T$. Therefore in $V[G]$ $\text{{\rm
Cod}}(r)=(N_{0},a_{0})$ with $a_{0}=A\cap\omega_{1}^{N_{0}}$.

  * •

The structure

$(\left\\{c_{n,0}^{\mathcal{N}}:n\in\omega\right\\},\in_{\mathcal{N}^{0}}^{\mathcal{N}})$

is well-founded and its transitive collapse is exactly $N_{0}$ by Axioms IIIb.

Now the axioms of type II grant that an iteration $\mathcal{J}$ of $N_{0}$ can
be defined so to extend the partial $\in$-isomorphism $\Theta$ so far defined
between the multi-sorted structures $(H_{\omega_{2}}^{V},N_{0};\in\restriction
H_{\omega_{2}},\in\restriction N_{0})$ and

$(\left\\{\check{x}:x\in
H_{\omega_{2}}^{V}\right\\},\left\\{\dot{e}_{n,0}:n\in\omega\right\\},\in_{N_{\omega_{1}^{V}}},\in_{N_{0}})$

to a full isomorphism $\Theta:\mathcal{X}_{(\mathcal{J},r,f,T)}\to\mathcal{N}$
with

$\mathcal{J}=\left\\{j_{\alpha\beta}:N_{\alpha}\to
N_{\beta}:\,\alpha\leq\beta<\omega_{1}^{V}\right\\}$

the unique iteration of $N_{0}$ of length $\omega_{1}^{V}$ such that
$j_{0\omega_{1}}(A\cap\omega_{1}^{N_{0}})=A$.

Specifically these axioms impose inductively the following for all
$\alpha<\omega_{1}^{V}$:

  * •

$(\left\\{c_{j,\alpha}^{\mathcal{N}}:j\in\omega\right\\},\in_{N_{\alpha}}^{\mathcal{M}})$
is isomorphic to $(N_{\alpha},\in)$,

  * •

The Mostowski collapsing map of
$\left\\{c_{j,\alpha}^{\mathcal{N}}:j\in\omega\right\\}$ onto $N_{\alpha}$,
maps $\left\\{c^{\mathcal{N}}:\mathcal{N}\models\dot{G}_{\alpha}(c)\right\\}$
onto some $G_{\alpha}$ which is $N_{\alpha}$-generic for
$(\mathcal{P}\left(\omega_{1}\right)/_{\mathbf{NS}_{\omega_{1}}})^{N_{\alpha}}$.

This occurs because of Axioms IIb, IIc holding in $\mathcal{M}$. Using the
fact that there is at most one iteration in $V[G]$ satisfying the constraints
given by these axioms and using [3, Lemma 2.7] we conclude that $\Theta$
extends to a full isomorphism of the $\mathcal{L}^{0}$-structure

(2)
$(N_{i}:i\leq\omega_{1}^{V},\,\left\\{r,f\right\\};\,\,\in_{N_{i}}:i\leq\omega_{1},\,G_{i}:i<\omega_{1}^{V},\,j_{\alpha\beta}:\alpha\leq\beta\leq\omega_{1}^{V},\,\operatorname{Sat}_{N_{\alpha}}:\alpha\leq\omega_{1}^{V})$

with
$\langle(\mathcal{S})^{\mathcal{N}},(\mathcal{R}\setminus\left\\{\dot{T},\text{{\rm
Cod}}^{*},\text{br}_{T}\right\\})^{\mathcal{N}}\rangle$. Now the structure
given by (2) uniquely determines the iteration

$\mathcal{J}=\left\\{j_{\alpha\beta}:N_{\alpha}\to
N_{\beta}:\,\alpha\leq\beta\leq\omega_{1}^{V}\right\\}.$

Finally use the type III axioms to get that

  * •

$A\cap\omega_{1}^{N_{0}}\in N_{0}$ and
$j_{0\omega_{1}}(A\cap\omega_{1}^{N_{0}})=A$ (by Axioms IIIb and IIIc),

  * •

$H_{\omega_{2}}^{V}\subseteq N_{\omega_{1}^{V}}$ (by Axiom IIId),

  * •

$\mathbf{NS}_{\omega_{1}}^{V}=\mathbf{NS}_{\omega_{1}}^{N_{\omega_{1}^{V}}}\cap
V$ (by Axiom IIIe).

This shows that $(\mathcal{J},r,f,T)$ is a semantic certificate for $A,D$ as
witnessd by $T$ in $V[G]$. ∎

######  Remark 3.22.

In this proof we use crucially the fact that a semantic certificate existing
in $V[G]$ is witnessed by a branch through $T$. Notice that in principle
$\dot{\in}_{N_{\omega_{1}}}^{\mathcal{N}}$ could be such that
$\dot{B}^{\mathcal{N}}$ (whatever definition one may try to give to
$\dot{B}^{\mathcal{N}}$) and $B^{V[G]}$ may not have much in common. However
this is not the case for the properties which can be described by
$\mathcal{L}^{0}$-sentences in parameter $\dot{T}$. This is one of the reasons
to define the tree $T$.

Note also that we forgot to add the extensionality axiom for the
interpretation of the $\in$-relation in the above list; so either one adds it,
or one oberves that for the models of $\Sigma^{0}$ the domain is exactly given
by the interpretation of the constants, hence extensionality comes for free
since the axioms grants that extensionality holds for the image under the
transitive collapse of the $\in_{N_{\alpha}}^{\mathcal{N}}$-relation and this
map is injective.

######  Definition 3.23.

Let $\mathcal{A}$ be the family of admissible assignments according to Def.
3.17. $P^{*}_{0}$ is $P_{\mathcal{A}}$.

The key consequence of Fact 3.21, Lemma 3.10, and Fact 3.14 is the following:

######  Lemma 3.24.

Given $H$ $V$-generic for $P^{*}_{0}$, $\mathcal{M}_{H}$ models $\Sigma^{0}$.

Therefore $\mathcal{M}_{H}$ is well founded and its unique isomorphism with
$\mathcal{X}_{(\mathcal{J}_{H},r_{H},f_{H},T)}$ gives a uniquely defined
semantic certificate $(\mathcal{J}_{H},r_{H},f_{H},T)$ for $A,D$.

Moreover the map $\nu_{H}:c\mapsto\pi_{\alpha,H}([c]_{H})$ (where
$\pi_{\alpha,H}:\dot{N}_{\alpha}^{\mathcal{M}_{H}}\to
X_{(\mathcal{J}_{H},r_{H},F_{H},T)}$ is the Mostowski collapse of
$\in_{N_{\alpha}}^{H}$) is an admissible interpretation on the constants of
$\mathcal{L}^{0}$ and can be naturally extended to a full interpretation of
$\mathcal{L}^{0}$ by mapping
$\nu_{H}(X)=\nu_{H}\left[X^{\mathcal{M}_{H}}\right]$ for $X$ predicate symbol
of $\mathcal{L}^{0}$.

###### Proof.

By Lemma 3.10 and Fact 3.14, $\mathcal{M}_{H}$ realizes all sentences of type
$\bigwedge\bigvee$ holding in $\Sigma_{\nu}$ for all admissible $\nu$.
$\Sigma^{0}$ is a subset of this family of sentences by Fact 3.21. Hence
$\mathcal{M}_{H}$ models $\Sigma^{0}$.

The remaining items of the Lemma are almost self-evident. ∎

By Lemma 2.10 $P^{*}_{0}$ is non-empty; the problem is to check whether it is
also stationary set preserving. This natural question has a negative answer
since $P^{*}_{0}$ has size $\aleph_{2}$ and Woodin has shown that
$\MM^{++}(2^{\aleph_{0}})$ is consistent with the negation of $(*)$ (cfr. [7,
Thm. 10.90]). To sidestep this difficulty, Asperò and Schindler are led to the
definition of the sequence of forcings
$\left\\{P_{\alpha}:\alpha\leq\kappa\right\\}$, and we also follow their
proof-pattern.

###  3.3. The forcing $P_{\kappa}$

We fix (or already have fixed) in $V$:

######  Notation 3.25.

__

  * •

$\kappa>\omega_{2}$ regular and such that $\Diamond_{\kappa}$ holds.

  * •

$T$ tree on $(2\times\omega_{2}^{V})^{<\omega}$, such that there are semantic
certificates $(\mathcal{J},r,f,T)$ for $A,D$ in any generic extension $V[G]$
of $V$ by $\operatorname{Coll}(\omega,\omega_{2})$.

  * •

$C\subseteq\kappa$ club and
$\left\\{Q_{\alpha},A_{\alpha}:\alpha\in\kappa\right\\}$ a $\Diamond_{\kappa}$
sequence such that:

    1. (1)

For all $\eta\in C$

$(Q_{\eta},\in,T,R\cap Q_{\eta})\prec(H_{\kappa},\in,T,R),$

where $R$ is a fixed well ordering of $H_{\kappa}$ in type $\kappa$.

    2. (2)

For all $\eta$ limit point of $C$

$Q_{\eta}=\bigcup_{\alpha\in C\cap\eta}Q_{\alpha}.$

    3. (3)

For any $Y\subseteq H_{\kappa}$ there are stationarily many $\eta<\kappa$ such
that $Y\cap Q_{\eta}=A_{\eta}$.

The forcings $\left\\{P_{\alpha}:\alpha\in
C\cup\left\\{\kappa\right\\}\right\\}$ are obtained from $P^{*}_{0}$ adding
new constant and predicate symbols so to have a stronger control on the type
of structures generated by their $V$-generic filters. The key idea is to
incorporate inside the extended language the names of the countable elementary
substructures of $V$ which can be used to seal a $P_{\kappa}$-name for a club.
Specifically we will add to $\mathcal{L}^{0}$ a sort $\dot{Q}$ to denote (a
subset of) $H_{\kappa}$ and unary predicates
$\left\\{\dot{X}_{i}:i<\omega_{1}^{V}\right\\}$ in this new sort which will be
used to ensure the following:

(3)

> Whenever $H$ is $V$-generic for the forcing $P_{\kappa}$, for “almost”
> all212121More precisely for any $S^{*}\subseteq\kappa$ stationary subset of
> $\kappa$ in $V$ and any $S\subseteq\omega_{1}^{V}$ stationary subset of
> $\omega_{1}^{V}$ in $V$, one can find $\eta\in S^{*}$ and
> $\alpha<\omega_{1}^{V}$ as prescribed. $\eta\in C$ and
> $\alpha<\omega_{1}^{V}$:
>
>   * •
>
> $X_{\alpha}=(\dot{X}_{\alpha})_{H}\prec(Q_{\eta},\in,P_{\eta},A_{\eta})$;
>
>   * •
>
> $H\cap P_{\eta}$ is $X_{\alpha}$-generic222222It meets inside $X_{\alpha}$
> all dense sets of $P_{\eta}$ definable in $X_{\alpha}$. for $P_{\eta}$;
>
>   * •
>
> $X_{\alpha}\cap\omega_{1}^{V}=\alpha$.
>
>

We will also ensure that the layering of the posets $P_{\eta}$ is continuous
at limit stages, and that the $P_{\eta}$ are contained in $Q_{\eta}$ for all
$\eta\in C$, so to get that

(4) $(Q_{\eta},\in,P_{\eta},A_{\eta})\prec(H_{\kappa},\in,P_{\kappa},X),$

holds in $V$ for stationarily many $\eta$ and any $X\subseteq H_{\kappa}$.

Now assume $S$ is a stationary subset of $\omega_{1}$ in $V$ and $\dot{C}$ is
a $P_{\kappa}$-name for a club. Let $H$ be $V$-generic for $P_{\kappa}$; By 3
and 4, we can find $\eta\in C$ and $\alpha<\omega_{1}^{V}$ so that
$\dot{C}\cap Q_{\eta}=A_{\eta}$ is a $P_{\eta}$-name for a club and

$X_{\alpha}=(\dot{X}_{\alpha})_{H}\prec(Q_{\eta},\in,P_{\eta},A_{\eta})\prec(H_{\kappa},\in,P_{\kappa},\dot{C}),$

$\alpha=X_{\alpha}\cap\omega_{1}^{V}\in S$, $H\cap P_{\eta}$ is
$X_{\alpha}$-generic for $P_{\eta}$. Then we should expect that $\dot{C}_{H}$
will have $\alpha\in S$ as a limit point (note that $(\dot{X}_{\alpha})_{H}$
will be countable in $V[H]$ and will not exist in $V$). This will grant that
$S\cap\dot{C}_{H}$ is non-empty. By repeating this argument for all stationary
subsets of $\omega_{1}^{V}$ in $V$ and all $P_{\kappa}$-names for a club
subset of $\omega_{1}^{V}$, we will get that $P_{\kappa}$ is stationary set
preserving. On the other hand the forcing $P_{\kappa}$ will also add a
semantic certificate for $A,D$ as witnessed by $T$. This allows to infer,
combining the information so far given, that $\MM^{++}$ instantiated for
$P_{\kappa}$ can be used to assert that $G_{A}\cap D$ is non-empty.

We are now going to describe close approximations to the generic objects added
by the various $P_{\eta}$; then we will define the signature which
characterizes these generic objects as models of a standard theory of
$\bigwedge\bigvee$-type for $\mathcal{L}^{1}_{\eta}$. The forcings $P_{\eta}$
will be of the form $P_{\mathcal{W}_{\eta}}$ for suitably chosen families of
generic assignments $\mathcal{W}_{\eta}$.

We assume and recall the following facts, notations and conventions:

######  Notation 3.26.

Given a weak semantic certificate $(\mathcal{J},r,f,T)$ for $A,D$, we let
$X_{(\mathcal{J},r,f,T)}$ be the set:

$(\bigcup_{i\leq\omega_{1}^{V}}N_{\alpha})\cup\left\\{N_{\alpha}:\alpha\leq\omega_{1}^{V}\right\\}\cup\left\\{j_{\alpha\beta}:\alpha\leq\beta\leq\omega_{1}^{V}\right\\}\cup\left\\{G_{\alpha}:\alpha<\omega_{1}\right\\}\cup\left\\{r,f\right\\},$

$\mathcal{X}_{(\mathcal{J},r,f,T)}$ be the structure:

$\langle
N_{\alpha}:\alpha\leq\omega_{1}^{V},\,\left\\{r,f\right\\};\,\in\restriction
N_{\alpha},\operatorname{Sat}_{N_{\alpha}}:\alpha\leq\omega_{1}^{V},\,G_{\alpha}:\alpha<\omega_{1}^{V},\,j_{\alpha\beta}:\alpha\leq\beta\leq\omega_{1}^{V},\,\sqsubseteq^{2}\restriction
T,\,\text{br}_{T},\,\text{{\rm Cod}}^{*}\rangle.$

Recall that we have fixed in $V$ the diamond sequence
$\left\\{Q_{\lambda}:\lambda\in C\right\\}$ and the witnessing tree $T$.

######  Definition 3.27.

For $\lambda\in C\cup\left\\{\kappa\right\\}$ a tuple

$(\mathcal{J},r,f,F,K)$

existing in some transitive $\mathsf{ZFC}$-model $W\supseteq Q_{\lambda}$ is a
_weak $\lambda$-precertificate_ (relative to $V$) if

  * •

$(\mathcal{J},r,f,T)$ is a weak semantic certificate for $A$ (relative to $V$)
existing in $W$ as witnessed by $T$ as in Def. 2.6.

  * •

$K\subseteq\omega_{1}^{V}$.

  * •

$F$ a function with domain $\omega_{1}^{V}$ defined by

$\displaystyle F:\,$ $\displaystyle\omega_{1}^{V}\to
C\cap\lambda\times\mathcal{P}\left(Q_{\lambda}\right)^{W}\times Q_{\lambda}$
$\displaystyle\alpha\mapsto\langle\lambda_{\alpha},X_{\alpha},Z_{\alpha}\rangle$

with $\langle\lambda_{\alpha},X_{\alpha},Z_{\alpha}\rangle=\langle
F_{0}(\alpha),F_{1}(\alpha),F_{2}(\alpha)\rangle$ and:

    * –

$F\restriction(\omega_{1}^{V}\setminus K)$ constantly with value $\langle
0,1,0\rangle$.

    * –

$F_{0}\restriction K$ and $F_{1}\restriction K$ being $\subseteq$-increasing,

    * –

for all $\alpha\in K$, $F_{2}(\alpha)=Z_{\alpha}\subseteq Q_{F_{0}(\alpha)}$
is in $Q_{\lambda}$ and $F_{1}(\alpha)=X_{\alpha}$ is the domain of an
elementary substructure of

$(Q_{F_{0}(\alpha)},\in,F_{2}(\alpha),A_{F_{0}(\alpha)})$

with232323$X_{\alpha}$ will not be in $V$, and will be countable in $V[G]$. In
the right set up (i.e. when the posets $\left\\{P_{\beta}:\beta\in
C\cap\lambda_{\alpha}\right\\}$ have been defined), $Z_{\alpha}$ will be
assigned to the poset $P_{\lambda_{\alpha}}$. The very definition of
$P_{\lambda_{\alpha}}$ is done by a recursion based on the notion of
$\lambda$-precertificate and using the sequence $\left\\{P_{\beta}:\beta\in
C\cap\lambda_{\alpha}\right\\}$, in particular we cannot for the moment assign
$Z_{\alpha}$ to its canonical intended meaning. Hence we let $Z_{\alpha}$
range over all possible elements of $Q_{\lambda}$.
$\alpha=X_{\alpha}\cap\omega_{1}^{V}$.

  * •

$(\mathcal{J},r,f,F,K)$ is a _$\lambda$ -precertificate for $A,Q_{\lambda}$_
(relative to $V$) if it exists in a generic extension of $V$.

We denote by $X^{\lambda}_{(\mathcal{J},r,f,F,K)}$ the set

$X_{(\mathcal{J},r,f,T)}\cup\left\\{K,F_{0},Q_{\lambda}\right\\}\cup\left\\{F_{1}(\alpha),F_{2}(\alpha):\alpha\in
K\right\\}.$

and by $\mathcal{X}^{\lambda}_{(\mathcal{J},r,f,F,K)}$ the multi-sorted
structure obtained extending $\mathcal{X}_{(\mathcal{J},r,f,T)}$ with the sort
$Q_{\lambda}$, the constants
$\left\\{Z_{\alpha}:\alpha<\omega_{1}^{V}\right\\}$ of sort $Q_{\lambda}$, the
binary predicates $F_{0},\in\restriction{Q_{\lambda}}$ both of type
$(Q_{\lambda},Q_{\lambda})$, the unary predicates $K$,
$\left\\{X_{\alpha}:\alpha<\omega_{1}^{V}\right\\}$ each of type
$Q_{\lambda}$.

$X^{\lambda}_{(\mathcal{J},r,f,F,K)}$ is the smallest set existing in $W$ and
containing all the information needed to reconstruct the weak semantic
certificate $(\mathcal{J},r,f,T_{\lambda})$ for $A,D$, the function $F$, the
selected set $K$. $\mathcal{X}^{\lambda}_{(\mathcal{J},r,f,F,K)}$ is the
multi-sorted structure which will encode this information using multi-sorted
logic.

######  Remark 3.28.

Note that letting

$\mathcal{J}=\left\\{j_{\alpha\beta}:N_{\alpha}\to
N_{\beta}:\alpha\leq\beta\leq\omega_{1}^{V}\right\\},$

and $(G_{i}:i<\omega_{1}^{V})$ list the $N_{i}$-generic ultrafilters
associated to $\mathcal{J}$,

  * •

The top elements in the $\in$-graph of $X^{\lambda}_{(\mathcal{J},r,f,F,K)}$
are exactly the elements of the following set:

$\left\\{r,f,K,F_{0}\right\\}\cup\left\\{X_{\alpha}:\alpha<\omega_{1}^{V}\right\\}\cup\left\\{N_{i}:i\leq\omega_{1}^{V}\right\\}\cup\mathcal{J}\cup\left\\{G_{\alpha}:\alpha<\omega_{1}\right\\}.$

  * •

$X^{\lambda}_{(\mathcal{J},r,f,F,K)}$ is not transitive for the same reason
for which transitivity fails for $X_{(\mathcal{J},r,f,T_{\lambda})}$, but the
new sorts, constants, and predicates denote elements or subsets of
$Q_{\lambda}$, hence they will not have an $\in$-ill-founded extension in
models of $\Sigma^{0}$ extended with axioms granting that the sort
$Q_{\lambda}$ gets interpreted by an isomorphic copy itself.

Note also that the extra requirement imposed on a weak
$\lambda$-precertificate are expressible by $\Delta_{0}$-properties in
parameters $C\cap\lambda,\lambda,\omega_{1}^{V},\Diamond_{\kappa}\cap
Q_{\lambda},F_{0},K,\left\\{X_{\alpha},Z_{\alpha}:\alpha<\omega_{1}^{V}\right\\}$,
i.e.:

  1. (i)

$K\subseteq\omega_{1}^{V}$,

  2. (ii)

$\displaystyle(F_{0}\text{ is a
function})\wedge(\operatorname{dom}(F_{0})=\omega_{1}^{V})\wedge(\operatorname{ran}{F}_{0}\subseteq
C\cap\lambda\cup\left\\{0\right\\})\wedge$
$\displaystyle\wedge\forall\alpha\in\beta\in\omega_{1}^{V}\,\left[(\alpha\in
K\wedge\beta\in K)\rightarrow(X_{\alpha}\subseteq X_{\beta}\wedge
F_{0}(\alpha)\in F_{0}(\beta))\right]$

  3. (iii)

$\forall\alpha\in\omega_{1}^{V}\setminus
K\,\left[(X_{\alpha}=Z_{\alpha}=1)\wedge(F_{0}(\alpha)=0)\right]$,

  4. (iv)

$\forall\alpha\in K\,\left[(X_{\alpha}\subseteq
Q_{F_{0}(\alpha)})\wedge(X_{\alpha}\cap\omega_{1}^{V}=\alpha)\wedge(Z_{\alpha}\subseteq
Q_{F_{0}(\alpha)})\wedge(Z_{\alpha}\in Q_{\lambda})\right],$

  5. (v)

$\displaystyle\forall\,\alpha\in K\,\forall n,m\in\omega\,\forall\vec{x}\in
X_{\alpha}^{<\omega}$
$\displaystyle\left[\ulcorner(X_{\alpha},\in,\,Z_{\alpha}\cap
X_{\alpha},\,A_{F_{0}(\alpha)\cap
X_{\alpha}})\models\phi_{n}(\vec{x})\urcorner\leftrightarrow\ulcorner(Q_{F_{0}(\alpha)},\in,Z_{\alpha},A_{F_{0}(\alpha)})\models\phi_{n}(\vec{x})\urcorner\right]$
.

Combining these observations with those in Remark 2.9, we get that all the
conditions needed to check whether $(\mathcal{J},r,f,F,K)$ is a weak
$\lambda$-precertificate are expressible by provably $\Delta_{1}$-properties
in $(H_{\omega_{1}}^{W},\tau_{\text{{\sf ST}}}^{W})$ for every $W$ transitive
model of $\mathsf{ZFC}$ in which all the relevant parameters are countable.

######  Definition 3.29.

Let $\mathcal{L}^{1}$ be the extension of $\mathcal{L}^{0}$ (given in Def.
3.17) adding the following sort, constants and predicates:

Sort:

__

  1. (n):

A sort $\dot{Q}$ to denote the element of $Q_{\lambda}$ for some $\lambda\in
C\cup\left\\{\kappa\right\\}$.

Constants:

__

  1. (o):

symbols $\check{\check{x}}$ of sort $\dot{Q}$ for each $x\in H_{\kappa}$ to be
interpreted by $x$.

  2. (p):

symbols $\dot{e}_{n,\alpha}$ of sort $\dot{Q}$ for each
$n<\omega,\alpha<\omega_{1}^{V}$ to be interpreted as the elements of the
various $X_{\alpha}$.

  3. (q):

symbols $\dot{Z}_{\alpha}$ of sort $\dot{Q}$ for each $\alpha<\omega_{1}^{V}$
to be interpreted as the sets $F_{2}(\alpha)$.

Predicates:

__

  1. (r):

a binary predicate symbol $\in_{\dot{Q}}$ of type $(\dot{Q},\dot{Q})$ to be
interpreted by the $\in$-relation restricted to the interpretation of $Q$,

  2. (s):

a unary predicate symbol $\dot{K}$ of type $\dot{Q}$ to be interpreted by the
selected subset of $\omega_{1}^{V}$,

  3. (t):

a binary predicate symbol $\dot{F}_{0}$ of type $(\dot{Q},\dot{Q})$ to be
interpreted by the selected map $\alpha\mapsto\lambda_{\alpha}$ from
$\omega_{1}^{V}$ to $C$,

  4. (u):

unary predicate symbols $\dot{X}_{\alpha}$ of type $\dot{Q}$ for each
$\alpha<\omega_{1}$ to be interpreted by the sets $F_{1}(\alpha)$,

  5. (v):

Let $\left\\{\in,U_{0},U_{1}\right\\}$ be the signature with $U_{0},U_{1}$
unary predicate symbols; we introduce the satisfaction predicates
$\operatorname{Sat}_{i,\alpha}(\ulcorner\psi(x_{1},\dots,x_{m})\urcorner)$ of
type $(\dot{Q},\dot{Q})$ with $i=0,1$ and $\alpha<\omega_{1}^{V}$ to be
represented by the pairs
$\langle\ulcorner\psi\urcorner,(a_{1},\dots,a_{m})\rangle$ with
$\psi(x_{1},\dots,x_{m})$ an $\left\\{\in,U_{0},U_{1}\right\\}$-formula in
displayed free variables and $(a_{1},\dots,a_{m})\in H_{\kappa}^{m}$ such that
for all $\alpha<\omega_{1}^{V}$:

    1. (i):

$\operatorname{Sat}_{0,\alpha}(\ulcorner\psi(a_{1},\dots,a_{m})\urcorner)$
holds if and only if $\alpha\in K$, $a_{1},\dots,a_{m}\in X_{\alpha}$ and

$(X_{\alpha},\in,Z_{\alpha}\cap X_{\alpha},A_{F_{0}(\alpha)}\cap
X_{\alpha})\models\psi(x_{1},\dots,x_{m})[x_{1}/a_{1},\dots,x_{m}/a_{m}].$

    2. (ii):

$\operatorname{Sat}_{1,\alpha}(\ulcorner\psi(a_{1},\dots,a_{m})\urcorner)$
holds if and only if $\alpha\in K$, $F_{0}(\alpha)=\eta$,
$a_{1},\dots,a_{m}\in Q_{\eta}$, and

$(Q_{\eta},\in,Z_{\alpha},A_{\eta})\models\psi(x_{1},\dots,x_{m})[x_{1}/a_{1},\dots,x_{m}/a_{m}].$

For $\lambda\in C\cup\left\\{\kappa\right\\}$ $\mathcal{L}^{1}_{\lambda}$
restricts $\mathcal{L}^{1}$ omitting the constant symbols $\check{\check{x}}$
for any $x\not\in Q_{\lambda}$, so that $\mathcal{L}^{1}_{\kappa}$ is
$\mathcal{L}^{1}$.

$\mathcal{R}^{1}_{\lambda}$ denotes the relations symbols of
$\mathcal{L}^{1}_{\lambda}$ and $\mathcal{K}^{1}_{\lambda}$ its constant
symbols.

$\Delta_{\lambda}$ the family of atomic sentences of