# The model-companionship spectrum of set theory, generic absoluteness, and
the Continuum problem

Matteo Viale

###### Abstract.

We show that for $\Pi_{2}$-properties of second or third order arithmetic as
formalized in appropriate natural signatures the apparently weaker notion of
_forcibility_ overlaps with the standard notion of _consistency_ (assuming
large cardinal axioms).

Among such $\Pi_{2}$-properties we mention: the negation of the continuum
hypothesis, Souslin Hypothesis, the negation of Whitehead’s conjecture on free
groups, the non-existence of outer automorphisms for the Calkin algebra, etc…
In particular this gives an a posteriori explanation of the success forcing
(and forcing axioms) met in producing models of such properties.

Our main results relate generic absoluteness theorems for second order
arithmetic, Woodin’s axiom $(*)$ and forcing axioms to Robinson’s notion of
model companionship (as applied to set theory). We also briefly outline in
which ways these results provide an argument to refute CH.

The author acknowledge support from INDAM through GNSAGA and from the project:
_PRIN 2017-2017NWTM8R Mathematical Logic: models, sets, computability. MSC:
_03C10 03E57._ _

## Introduction

### Model completeness, model companionship, and the model companionship
spectrum of a theory

Model companionship and model completeness are model theoretic notions
introduced by Robinson which give a simple first order characterization of the
way algebraically closed fields sits inside the class of rings with no zero-
divisors. We start this paper rushing through the main properties of model
completess and model companionship (we will later on analyze carefully all
these concepts in Section 1). Our aim is to show in a few paragraphs how we
can use these notions to reformulate in a simple model-theoretic terminology
deep generic absoluteness results for second order arithmetic by Woodin and
others, as well as other major results on forcing axioms and Woodin’s Axiom
$(*)$.

The key model-theoretic concept we are interested in is that of existentially
closed model of a first order theory111We adopt the following notational
conventions: $\sqsubseteq$ denotes the substructure relation between
structures; $\mathcal{M}\prec_{n}\mathcal{N}$ indicates that $\mathcal{M}$ is
a $\Sigma_{n}$-elementary substructure of $\mathcal{N}$, we omit the $n$ to
denote full-elementarity; given a first order theory $T$, $T_{\forall}$
denotes the universal sentences which are consequences of $T$, likewise we
interpret $T_{\exists},T_{\forall\exists},\dots$. $T$:

######  Definition 1.

Let $\tau$ be a signature and $T$ be a first order theory. $\mathcal{M}$ is
$T$-existentialy closed ($T$-ec) if for any $\tau$-structure
$\mathcal{N}\sqsupseteq\mathcal{M}$ which is a model of $T$ we have that

$\mathcal{M}\prec_{1}\mathcal{N}.$

A key non-trivial fact is that $\mathcal{M}$ is $T$-ec if and only if it is
$T_{\forall}$-ec.

It doesn’t take long to realize that in signature
$\tau=\left\\{+,\cdot,0,1\right\\}$ the $\tau$-theory $T$ of fields has as its
class of existentially closed models exactly the algebraically closed fields.
Note also that if we let $S$ be the class of rings with no zero-divisors which
are not fields, we still have that the $S$-existentially closed structures are
the algebraically closed fields (even if no field is a model of $S$).

Model completeness and model companionship allow to generalize these features
of the class of rings with no zero divisors to arbitrary first order theories.

######  Definition 2.

Let $\tau$ be a first order signature.

  * •

A $\tau$-theory $T$ is _model complete_ if any model of $T$ is $T$-ec.

  * •

$T$ is the _model companion_ of a $\tau$-theory $S$ if:

    * –

any model of $S$ embeds into a model of $T$ and conversely,

    * –

$T$ is model complete.

In particular in signature $\tau=\left\\{+,\cdot,0,1\right\\}$, the theory of
algebraically closed fields is model complete and is the model companion both
of the theory of fields and of the theory of rings with no zero-divisors which
are not fields.

We will also need here the following equivalent characterization of model
completeness: $T$ is model complete whenever

> _For $\mathcal{M},\mathcal{N}$ models of $T$, $\mathcal{M}\prec\mathcal{N}$
> if and only if $\mathcal{M}\prec_{1}\mathcal{N}$ if and only if
> $\mathcal{M}\sqsubseteq\mathcal{N}$_.

Note also that:

  * •

any theory $T$ admitting quantifier elimination is model complete;

  * •

any model complete theory $T$ is the model companion of itself;

  * •

two $\tau$-theories $T$ and $S$ which have no model in common can have the
same model companion, but the model companion of a theory $T$ if it exists is
unique;

  * •

if $T^{*}$ is the model companion of $T$ it can be the case that no model of
$T$ is a model of $T^{*}$ and conversely;

  * •

there are $\tau$-theories $T$ which do not admit a model companion (for
example this is the case for the theory of groups in signature
$\tau=\left\\{\cdot,1\right\\}$).

Much in the same way as the algebraic closure of a ring $R$ with no zero-
divisors closes off $R$ with respect to solutions to polynomial equations with
coefficients in $R$ and which exist in some superring of $R$ which has no
zero-divisors (and which does not have to be algebraically closed), for a
theory $T$ with model companion $T^{*}$ any model $\mathcal{M}$ of $T$ brings
to a supermodel $\mathcal{N}$ of $T^{*}$ which is obtained by adding (at
least) the solutions to the existential formulae with parameters in
$\mathcal{M}$ which are consistent with the universal fragment of $T$ (in the
case of ring with no zero-divisors the key universal property one has to
maintain is the non-existence of zero-divisors along with the ring axioms).

A key property of model companionship which brought our attention to this
notion is the following (see Section 1 for details):

######  Fact 1.

Let $\tau$ be a first order signature and $T$ be a _complete_ $\tau$-theory
with model companion $T^{*}$. Then $T^{*}$ is axiomatized by
$T^{*}_{\forall\exists}$ and TFAE for a $\Pi_{2}$-sentence $\psi$ for $\tau$:

  * •

$T_{\forall}+\psi$ is consistent.

  * •

$\psi\in T^{*}$.

In case $T$ is a companionable non-complete theory, further weak hypothesis on
$T$ (which are satisfied by set theory) allow to characterize its model
companion $T^{*}$ as the unique theory axiomatized by the $\Pi_{2}$-sentences
which are consistent with the universal fragment of any completion of $T$ (see
Lemma 1.21).

Unlike other notions of complexity (such as stability, NIP, simplicity) model
companionship and model completeness are very sensitive to the signature in
which one formalizes a first order theory $T$.

######  Notation 1.

For a given signature $\tau$, $\tau^{*}$ is the signature extending $\tau$
with new function symbols222As usual we confuse $0$-ary function symbols with
constants. $f_{\phi}$ and new relation symbols $R_{\phi}$ for any
$\tau$-formula $\phi(x_{0},x_{1},\dots,x_{n})$. $T_{\tau}$ is the
$\tau^{*}$-theory with axioms

$\text{{\sf AX}}^{0}_{\phi}:=\forall\vec{x}[\phi(\vec{x})\leftrightarrow
R_{\phi}(\vec{x})]$ $\text{{\sf AX}}^{1}_{\phi}:=\forall
x_{1},\dots,x_{n}[\exists
y\phi(y,x_{1},\dots,x_{n})\rightarrow\phi(f_{\phi}(x_{1},\dots,x_{n}),x_{1},\dots,x_{n})],$

as $\phi$ ranges over the $\tau$-formulae.

It is clear that any $\tau$-structure admits a unique extension to a
$\tau^{*}$-model of $T_{\tau}$ and any $\tau$-theory $T$ is such $T\cup
T_{\tau}$ admits quantifier elimination, hence is model complete and is its
own model companion relative to signature $\tau^{*}$. This holds regardless of
whether the $\tau$-theory $T$ is model complete or admits a model companion in
signature $\tau$ (cfr. $T$ being the theory of groups in signature
$\left\\{\cdot,1\right\\}$). On the other hand $T$ is stable (simple, NIP) if
and only if so is $T_{\tau}$. This is a serious drawback if one wishes to use
model companionship to gauge the complexity of a mathematical theory $T$,
since model companionship of $T$ is very much dependent on the signature in
which we formalize it: $T$ can trivially be model complete if we formalize it
in a rich enough signature.

We now introduce a simple trick to render model companionship a useful
classification tool for mathematical theories regardless of the signature in
which we give their first order axiomatization. Roughly the idea is to
consider all possible signatures in which a theory can be formalized and pay
attention only to those for which the theory admits a model companion.

######  Definition 3.

Let $\tau$ be a signature and $F_{\tau}$ denote the set of $\tau$-formulae.

Given $A\subseteq F_{\tau}\times 2$, let $\tau_{A}$ be the signature
$\tau\cup\left\\{R_{\phi}:(\phi,0)\in
A\right\\}\cup\left\\{f_{\phi}:(\phi,1)\in A\right\\}$. A $\tau$-theory $T$ is
_$(A,\tau)$ -companionable_ if

$T_{A}=T\cup\left\\{\text{{\sf AX}}^{i}_{\phi},:(\phi,i)\in A\right\\}$

admits a model companion for the signature $\tau_{A}$.

Given a $\tau$-theory $T$ its _$\tau$ -companionship spectrum_ is given by
those $A\subseteq F_{\tau}\times\left\\{0,1\right\\}$ such that $T$ is
$(A,\tau)$-companionable.

Note that $F_{\tau}\times\left\\{i\right\\}$ is always in the companionship
spectrum of $T$, but proving that some $\bar{A}\subsetneq F_{\tau}$ is such
that some $A\subseteq\bar{A}\times 2$ is in the companionship spectrum of $T$
is a (possibly highly) non-trivial and informative result on $T$; model-
companionability for $T$ amounts to say that $T$ is
$(\emptyset,\tau)$-companionable. The $\tau$-companionship spectrum of $T$ is
non-informative if $T$ is model complete in signature $\tau$: in this case the
$\tau$-companionship spectrum of $T$ is $\mathcal{P}\left(F_{\tau}\times
2\right)$.

Note also that even if $T$ is $(\emptyset,\tau)$-companionable there could be
many $A\subseteq F_{\tau}\times 2$ such that $T$ is $A$-companionable and many
$B\subseteq F_{\tau}\times 2$ such that $T$ is not $B$-companionable; in
principle nothing prevents the families of such $A$s and $B$s to be both of
size $2^{|F_{\tau}|}$ and to produce a complex ordering of the
$\tau$-companionship spectrum of $T$ with respect to $\subseteq$.

To better grasp the above considerations, let for a $\tau$-theory $T$ $C_{T}$
be the category whose objects are the $\tau$-models of $T$ and whose arrows
are the $\tau$-morphisms. NIP, stability, simplicity are properties which
consider only the objects in this category, model completeness and model
companionship pay also attention to the arrows of this category. We get a much
deeper insight on the properties of $C_{T}$ if we are able to detect for which
$A\subseteq F_{\tau}\times 2$ $T_{A}$ is model companionable: for any
$A\subseteq F_{\tau}\times 2$ in the passage from $C_{T}$ to $C_{T_{A}}$ we
maintain the same class of objects, but the $\tau_{A}$-morphisms (i.e the
arrows of $C_{T_{A}}$) are just the $\tau$-morphisms between models of $T$
which preseve the formulae in $A$, hence we are possibly destroying many
arrows.

Our definition of $\tau$-companionship spectrum of a mathematical theory is
apparently dependent on the signature $\tau$ in which we formalize it. We may
argue that this is not the case, but to uncover why would bring us far afield
and we defer this task to another paper. We will in this paper confine our
attention to use this notion to analyze first order axiomatizations of set
theory enriched with large cardinal axioms. In this case we can certainly say
that proving that some $A\subsetneq F_{\left\\{\in\right\\}}\times 2$ is in
the $\in$-companionship spectrum of set theory is an informative result:
$\left\\{\in\right\\}$ is a minimal signature in which set theory can be
formalized (in the empty signature we certainly cannot formalize it), hence
any $A\subseteq F_{\left\\{\in\right\\}}\times 2$ for which set theory is
$A$-companionable gives non-trivial information on set theory. Moreover we can
easily verify that any reasonable $\in$-axiomatization of set theory is not
model complete for the $\in$-signature, hence the $\in$-companionship spectrum
of set theory is certainly non-trivial.

### Some of our main results

We can now state in an informative way key parts of our main results.

The first non-trivial result states that for any definable cardinal $\kappa$
there is at least one signature admitting a constant for the cardinal $\kappa$
such that set theory is companionable for this signature.

It is convenient from now on to adopt the following short-hand notation for
structures:

######  Notation 2.

Given a signature $\tau$, $\mathcal{M}=(M,\tau^{\mathcal{M}})$ is a shorthand
for the $\tau$-structure $(M,R^{\mathcal{M}}:R\in\tau)$.

######  Theorem 1.

Let $T\supseteq\mathsf{ZFC}$ be a $\in$-theory, and $\kappa$ be a
$T$-definable cardinal (i.e. such that for some $\in$-formula
$\phi_{\kappa}(x)$ $T$ proves $\exists!x[\phi_{\kappa}(x)\wedge x$_is a
cardinal_ $]$).

Then there is at least one $A_{\kappa}\subsetneq F_{\in}$ such that letting
$\bar{A}_{\kappa}=A_{\kappa}\times 2$:

  1. (1)

For all models $(V,\in)$ of $T$
$(H_{\kappa^{+}}^{V},\left\\{\in\right\\}_{\bar{A}_{\kappa}}^{V})\prec_{1}(V,\left\\{\in\right\\}_{\bar{A}_{\kappa}}^{V})$.

  2. (2)

$T$ is $\bar{A}_{\kappa}$-companionable.

  3. (3)

The model companion $T^{*}_{\kappa}$ of $T_{\bar{A}_{\kappa}}$ for signature
$\left\\{\in\right\\}_{\bar{A}_{\kappa}}$ is the
$\left\\{\in\right\\}_{\bar{A}_{\kappa}}$-theory common to
$H_{\kappa^{+}}^{V}$ as $(V,\in)$ ranges over $\in$-models of $T$ and $\kappa$
is the constant of $\left\\{\in\right\\}^{*}$ given by the formula
$\exists!x[\phi_{\kappa}(x)\wedge x$_is a cardinal_ $]$.

  4. (4)

$T^{*}_{\kappa}$ is also axiomatized by the $\Pi_{2}$-sentences for
$\left\\{\in\right\\}_{\bar{A}_{\kappa}}$ which are consistent with
$S_{\forall}$ for any $\left\\{\in\right\\}_{\bar{A}_{\kappa}}$-theory $S$
which is a complete extension of $T_{\bar{A}_{\kappa}}$.

Note that the above theorem allows to put in the companionship spectrum of any
extension of $\mathsf{ZFC}$ at least one $\bar{A}_{\kappa}$ for each definable
cardinal $\kappa$ such as
$\omega,\omega_{1},\dots,\aleph_{\omega},\dots,\aleph_{\omega_{1}},\dots,\kappa,\dots$
for $\kappa$ the least inaccessible, measurable, Woodin, supercompact,
extendible…

In case $\kappa=\omega,\omega_{1}$ we can say much more and prove that for
$\Pi_{2}$-sentences in the appropriate signature forcibility and consistency
overlap (assuming large cardinal axioms).

This gives an a posteriori explanation of the success forcing has met in
proving the consistency of $\Pi_{2}$-properties (according to the right
signature) for second or third order artithmetic: our results show that there
are no other means to prove the consistency of such statements.

######  Theorem 2.

Let $S$ be _any_ extension of

$\mathsf{ZFC}+\text{{suitable} large cardinal axioms}$

in signature $\tau=\left\\{\in\right\\}$. There are $A_{1}\neq A_{2}\subseteq
F_{\left\\{\in\right\\}}$ recursive sets of $\in$-formulae such that (letting
$\bar{A}_{i}=A_{i}\times 2$ for $i=1,2$):

  1. (1)

For all models $(V,\in)$ of $S$
$(H_{\omega_{i}}^{V},\left\\{\in\right\\}_{\bar{A}_{i}}^{V})\prec_{1}(V,\left\\{\in\right\\}_{\bar{A}_{i}}^{V})$
for both $i=1,2$.

  2. (2)

$S$ is $\bar{A}_{i}$-companionable for both $i=1,2$333With very strong large
cardinal axioms for the case for $T_{\bar{A}_{2}}$, and no large cardinal
axioms in the case for $T_{\bar{A}_{1}}$..

  3. (3)

The model companion of $S_{\bar{A}_{1}}$ is the $\tau_{\bar{A}_{1}}$-theory
common to the models $H_{\aleph_{1}}^{V[G]}$ as $(V\in)$ ranges over
$\in$-models of $S$ and $G$ is $V$-generic for some444If one is not at ease
with the (inconsistent) assumption that $V[G]$ exists, this can be
reformulated as: $(V\,in)\models\exists P\,(P\Vdash\psi^{H_{\omega_{1}}})$ and
$(V,\in)\models S$. $P\in V$.

  4. (4)

The model companion of $S_{\bar{A}_{2}}$ is the $\tau_{\bar{A}_{2}}$-theory
common to all $H_{\aleph_{2}}^{V[G]}$ for $V[G]$ a forcing extension of $V$
which models $\text{{\sf MM}}^{++}$ and $(V,\in)$ a $\in$-model of $S$ 555With
very strong large cardinal axioms holding in $V$. $\text{{\sf MM}}^{++}$ is
one of the strongest forcing axioms..

  5. (5)

$(S_{\bar{A}_{1}})_{\forall}$ and $(S_{\bar{A}_{2}})_{\forall}$ are both
invariant across forcing extensions of $V$ for any $\in$-model $(V,\in)$ of
$S$ (assuming the existence of class many Woodin cardinals in $V$).

######  Corollary 1.

Assume $S$ extends $\mathsf{ZFC}$ with the correct large cardinal axioms.

Let $X$ be any among $\bar{A}_{1},\bar{A}_{2}\subseteq
F_{\left\\{\in\right\\}}\times 2$ as in the previous theorem, and:

  * •

$S_{X}$ be the $\tau_{X}$-theory $S\cup\left\\{\text{{\sf
AX}}^{i}_{\phi}:(\phi,i)\in X\right\\}$,

  * •

$S^{*}_{X}$ be the model companion theory of $S_{X}$ given by the previous
theorem.

TFAE for any $\Pi_{2}$-sentence $\psi$ for $\tau_{X}$:

  1. (A)

$\psi\in S^{*}_{X}$;

  2. (B)

$R_{\forall}+\psi$ is consistent for all $\tau_{X}$-theories $R$ which are
complete extensions of $S_{X}$;

  3. (C)

(if $X=\bar{A}_{2}$)

$S_{X}\models\exists P\,\left[\Vdash_{P}\psi^{H_{\omega_{2}}}\right];$

(if $X=\bar{A}_{1}$)

$S_{X}\models\exists P\,\left[\Vdash_{P}\psi^{H_{\omega_{1}}}\right].$

In particular the equivalence of B with C shows that _forcibility_ and
_consistency_ overlap for $\Pi_{2}$-sentences in signature
$\left\\{\in\right\\}_{X}$.

We complete this introduction outlining a bit more the significance of the
above results and trying to get a better insight on what are the signatures
$\left\\{\in\right\\}_{\bar{A}_{1}},\left\\{\in\right\\}_{\bar{A}_{2}},\left\\{\in\right\\}_{\bar{A}_{\kappa}}$
mentioned in the theorems.

### What is the right signature for set theory?

The $\in$-signature is certainly sufficient to give by means of $\mathsf{ZFC}$
a first order axiomatization of set theory (with eventually other extra
hypothesis such as large cardinal axioms), but we can see rightaway that it is
not efficient to formalize many basic set theoretic concepts. Consider for
example the notion of ordered pair: on the board we write $x=\langle
y,z\rangle$ to mean that _$x$ is the ordered pair with first component $y$ and
second component $z$_. In set theory this concept is formalized by means of
Kuratowski’s trick stating that
$x=\left\\{\left\\{y\right\\},\left\\{y,z\right\\}\right\\}$. However the
$\in$-formula formalizing the above is:

$\exists t\exists u\;[\forall w\,(w\in x\leftrightarrow w=t\vee
w=u)\wedge\forall v\,(v\in t\leftrightarrow v=y)\wedge\forall v\,(v\in
u\leftrightarrow v=y\vee v=z)].$

It is clear that the meaning of this $\in$-formula is hardly decodable with a
rapid glance (unlike $x=\langle y,z\rangle$), moreover just from the point of
view of its syntactic complexity it is already $\Sigma_{2}$. On the other hand
we do not regard the notion of ordered pair as a complex or doubtful concept
(as is the case for the notion of uncountability, or many of the properties of
the continuum such as its correct place in the hierarchy of uncountable
cardinals, etc…). Other vary basic notions such as: being a function, a binary
relation, the domain or the range of a function, etc.. are formalized already
by rather complicated $\in$-formulae, both from the point of view of
readability for human beings and from the mere computation of their syntactic
complexity according to the Levy hierarchy.

The standard solution adopted by set theorists (e.g. [13, Chapter IV]) is to
regard as elementary all those properties which can be formalized using
$\in$-formulae all of whose quantifiers are bounded to range over the elements
of some set, i.e. the so called $\Delta_{0}$-formulae (see [13, Chapter IV,
Def. 3.5]). We henceforth adopt this point of view and let $B_{0}\subseteq
F_{\left\\{\in\right\\}}$ be the set of such formulae and denote by
$\tau_{\text{{\sf ST}}}$ what according to our previous terminology should
rather be $\left\\{\in\right\\}_{B_{0}\times 2}$. For the sake of convenience
and also to further outline some very nice syntactic features of
$\mathsf{ZFC}$ as formalized in $\tau_{\text{{\sf ST}}}$, let us bring to
front an explicit axiomatization of $T_{B_{0}}$ (which from now on will be
denoted by $T_{\text{{\sf ST}}}$).

######  Notation 3.

__

  * •

$\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})$, function symbols of arity $k$ for any
$\Delta_{0}$-formula $\theta(y,x_{1},\dots,x_{k})$ 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 z\in y\phi}(y,z,\vec{x})\leftrightarrow\forall
z(z\in y\rightarrow R_{\phi}(y,z,\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})]$
$\forall\vec{x}\left[\exists!y\,R_{\phi}(y,\vec{x})\leftrightarrow
R_{\phi}(f_{\phi}(\vec{x}),\vec{x})\right]$

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 all whose 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}}}$.

Note that $T_{\text{{\sf ST}}}$ is axiomatized by $\Pi_{2}$-sentences of
$\tau_{\text{{\sf ST}}}$.

### Levy absoluteness and model companionship results for set theory

Kunen’s [13, Chapter IV] gives a rather convincing summary of the reasons why
it is convenient to formalize set theory using $\tau_{\text{{\sf ST}}}$ rather
than $\in$. We focus here on the role Levy’s absoluteness plays in the search
of $A\subseteq F_{\left\\{\in\right\\}}\times 2$ for which set theory is
$A$-companionable.

######  Lemma 1.

Let $(V,\in)$ be a model of $\mathsf{ZFC}$ and $\kappa$ be an infinite
cardinal for $V$. Then

$(H_{\kappa^{+}}^{V},\tau_{\text{{\sf
ST}}}^{V},A:A\subseteq\mathcal{P}\left(\kappa\right)^{k},\,k\in\mathbb{N})\prec_{1}(V,\tau_{\text{{\sf
ST}}}^{V},A:A\subseteq\mathcal{P}\left(\kappa\right)^{k},\,k\in\mathbb{N})$

Its proof is a trivial variant of the classical result of Levy (which is the
above theorem stated just for the signature $\tau_{\text{{\sf ST}}}$); it is
given in [22, Lemma 5.3].

The upshot is that for any model $V$ of $\mathsf{ZFC}$ and any signature
$\sigma$ such that

$\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}\subseteq\sigma\subseteq\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}\cup\bigcup_{k\in\mathbb{N}}\mathcal{P}\left(\kappa\right)^{k}$

$H_{\kappa^{+}}$ is $\Sigma_{1}$-elementary in $V$ according to $\sigma$. This
is a first indication that for a $\mathsf{ZFC}$-definable cardinal $\kappa$
(e.g. $\kappa=\omega,\omega_{1},\aleph_{\omega},\dots$, more precisely
$\kappa$ being provably in some $T\supseteq\mathsf{ZFC}$ the unique solution
of an $\in$-formula $\phi_{\kappa}(x)$) if $\sigma_{\kappa}=\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$ and $T_{\kappa}$ is the
$\sigma_{\kappa}$-theory given by $\mathsf{ZFC}+\phi_{\kappa}(\kappa)$, we get
that the $\sigma_{\kappa}$-theory common to all of the $H_{\kappa^{+}}^{V}$ as
$V$ ranges over the model of $\mathsf{ZFC}$ is not that far from being
$\mathsf{ZFC}$-ec, since a model of this theory is always a
$\Sigma_{1}$-substructure of some $\sigma_{\kappa}$-model of $\mathsf{ZFC}$.

A second indication that the $\sigma_{\kappa}$-theory of $H_{\kappa^{+}}$ is
close to be the model companion of the $\sigma_{\kappa}$-theory of $V$ is the
fact that the $\Pi_{2}$-sentence for $\sigma_{\kappa}$

$\forall x\exists f:\kappa\to x\text{ surjective function}$

is realized in $H_{\kappa^{+}}^{V}$ for any model $V$ of $\mathsf{ZFC}$ (note
that by Levy’s absoluteness this sentence is consistent with the universal
fragment of the $\sigma_{\kappa}$-theory of $V$, hence by Fact 1 it belongs to
the model companion of set theory for $\sigma_{\kappa}$ — if such a model
companion exists).

In particular if some $T\supseteq\mathsf{ZFC}$ is $\sigma$-companionable for
some $\sigma$ as above, the model companion of $T$ for $\sigma$ should be the
theory of $H_{\kappa^{+}}^{\mathcal{M}}$ for suitably chosen $\mathcal{M}$
which are models of set theory.

A natural question is:

> _Can we cook up $\sigma\supseteq\tau_{\text{{\sf
> ST}}}\cup\left\\{\kappa\right\\}$ so that the $\sigma$-theory of
> $H_{\kappa^{+}}$ is the model companion of the $\sigma$-theory of $V$?_

Theorem 1 answer affirmatively to this question for many natural choices of
$\sigma$ and for all definable cardinals $\kappa$.

### Why the continuum is the second uncountable cardinal

Theorem 2 refines Thm. 1 for the cases $\kappa=\omega,\omega_{1}$. In these
cases our knowledge of the theory of $H_{\kappa^{+}}$ is much more extensive;
moreover most of mathematics can be formalized in $H_{\omega_{1}}$ (all of
second order arithmetic) or in $H_{\omega_{2}}$ (most of third order
arithmetic).

We now want to outline briefly why Thm. 2 provides an interesting
metamathematical argument in favour of strong forcing axioms and against CH.
The considerations of this brief paragraph will be expanded in more details in
a forthcoming paper and have been elaborated jointly with Giorgio Venturi.
Those who are familiar with forcing axioms know that Martin’s maximum and its
bounded forms have been instrumental to prove the consistency of a solution of
many problems of third order arithmetic which are provably undecidable in
$\mathsf{ZFC}$ (or even in $\mathsf{ZFC}$ supplemented by large cardinal
axioms), a sample of these solutions include: the negation of the continuum
hypothesis [8, 6, 25, 21, 16], the negation of Whitehead conjecture on free
abelian groups [18], the non-existence of outer automorphism of the Calkin
algebra [7], the Suslin hypothesis [11], the existence of a five element basis
for uncountable linear order [17]…All statements of the above list (with the
exception of the non-existence of outer automorphism of the Calkin algebra)
and many others can be formalized as $\Pi_{2}$-sentences in signature
$\tau_{\omega_{1}}=\tau_{\text{{\sf ST}}}\cup\left\\{\omega_{1}\right\\}$
(where $\omega_{1}$ is a new constant symbol which is the unique solution of
some formula in one free variable defining the first uncountable cardinal).
For example $\neg\text{{\sf CH}}$ is formalized by

$\forall f\,\left[(f\text{ is a
function}\wedge\operatorname{dom}(f)=\omega_{1})\rightarrow\exists
r\,(r\subseteq\omega\wedge r\not\in\operatorname{ran}(f))\right].$

In particular there has been empiric evidence that forcing axioms produce
models of set theory which maximize the family of $\Pi_{2}$-sentences which
hold true in $H_{\omega_{2}}$ for the signature $\tau_{\omega_{1}}$. Thm. 2
makes this empiric evidence a true mathematical fact: first of all it is
important to note here that (sticking to the notation of Thm. 2)
$\left\\{\in\right\\}_{\bar{A}_{2}}\supseteq\tau_{\omega_{1}}$. Now let $T$ be
a theory as in the assumption of Thm. 2; take (in signature
$\left\\{\in\right\\}_{\bar{A}_{2}}$) any $\Pi_{2}$-sentence $\psi$ which is
consistent with $S_{\forall}$ whenever $S$ is a complete extension of
$T_{\bar{A}_{2}}$; then by A$\Longleftrightarrow$B of Corollary 1 $\psi$ is in
the model companion of $T_{\bar{A}_{2}}$, and Thm. 4(4) (almost) asserts that
$\psi^{H_{\omega_{2}}}$ is derivable from $\text{{\sf MM}}^{++}$. Note that
$\text{{\sf MM}}^{++}$ is one of the strongest forcing axioms.

Another key observation is that (assuming large cardinals) the signature
$\left\\{\in\right\\}_{\bar{A}_{2}}$ is such that the universal fragment of
set theory as formalized in $\left\\{\in\right\\}_{\bar{A}_{2}}$ is _invariant
through forcing extensions of $V$_. What this means is that one _can and must
use forcing_ to establish whether some $\Pi_{2}$-sentence $\psi$ is in the
model companion of set theory according to
$\left\\{\in\right\\}_{\bar{A}_{2}}$.

This is the major improvement of Thm. 2 with respect to Thm. 1: for most of
the signatures $\tau_{\bar{A}_{\kappa}}$ mentioned in Thm. 1 we cannot just
use forcing to establish whether a $\Pi_{2}$-sentence $\psi$ for this
signature is in the model companion of set theory for
$\tau_{\bar{A}_{\kappa}}$.

Let us develop more on this point because it is in our eyes one of the major
advances given by the results of the present paper. Take
$S\supseteq\mathsf{ZFC}$; for a given $X\subseteq
F_{\left\\{\in\right\\}}\times 2$ for which we can prove that $S_{X}$ has a
model companion in signature $\left\\{\in\right\\}_{X}$ we would like to show
that a certain $\Pi_{2}$-sentence $\psi$ for $\left\\{\in\right\\}_{X}$ is in
the model companion of $S_{X}$.

Let us first suppose that $X$ is some $\bar{A}_{\kappa}$ as in Thm. 1. A first
observation is that (with the exception of the $\Delta_{0}$-formulae) all the
formulae in $A_{\kappa}$ define subsets of
$\mathcal{P}\left(\kappa\right)^{n}$ for some $n$, hence
$(H_{\kappa^{+}}^{V},\left\\{\in\right\\}_{\bar{A}_{\kappa}}^{V})\prec_{1}(V,\left\\{\in\right\\}_{\bar{A}_{\kappa}}^{V})$
for any $(V,\in)$ which models $\mathsf{ZFC}$. This gives that if
$(W,\left\\{\in\right\\}_{\bar{A}_{\kappa}}^{W})$ models $(S_{X})_{\forall}$,
then so does
$(H_{\kappa^{+}}^{W},\left\\{\in\right\\}_{\bar{A}_{\kappa}}^{W})$.

A natural strategy to put $\psi$ in the model companion of $S_{X}$ would then
be to start from some complete $T\supseteq S$ and some $(V,\in)$ model of $T$;
then force over $V$ that in some $V[G]$ $\psi^{H_{\kappa^{+}}^{V[G]}}$ holds
true; if $(T_{\bar{A}_{\kappa}})_{\forall}$ holds in $V[G]$, then $\psi$ would
be in the model companion of $S_{\bar{A}_{\kappa}}$ by Thm. 1(4): Levy’s
absoluteness applied to $(V[G],\tau_{\bar{A}_{\kappa}}^{V[G]})$ would yield
that $H_{\kappa^{+}}^{V[G]}\models\psi+(T_{\bar{A}_{\kappa}})_{\forall}$.

Now starting from any model $V$ of $S$ we may be able to design a forcing in
$V$ such that $\psi^{H_{\kappa^{+}}^{V[G]}}$ holds if $G$ is $V$-generic for
this forcing, but it may be the case that $(S_{\bar{A}_{\kappa}})_{\forall}$
fails in $V[G]$; in which case we cannot use $H_{\kappa^{+}}^{V[G]}$ as a
witness that $\psi$ is in the model companion of $S_{\bar{A}_{\kappa}}$.
Remark 1 shows that $(S_{\bar{A}_{\kappa}})_{\forall}$ is not preserved
through forcing extensions whenever $\kappa>\omega_{1}$.

On the other hand for the signatures $\tau_{X}$ for $X$ being the
$\bar{A}_{1}$ or $\bar{A}_{2}$ mentioned in Thm. 2 the above strategy works:
the universal fragment of $(S_{X})_{\forall}$ is preserved through the forcing
extensions of models of $S$; hence $\psi$ will be in the model companion of
$S_{X}$ if for any model $V$ of $S$ we can design a forcing making true $\psi$
in $H_{\kappa^{+}}^{V[G]}$ (for $\kappa=\omega,\omega_{1}$ according to
whether $\psi$ is a formula for $\tau_{\bar{A}_{1}}$ or for
$\tau_{\bar{A}_{2}}$).

Summing up one _may and should only_ use forcing to establish the consistency
with large cardinals of $\psi^{H_{\omega_{2}}}$ for any $\Pi_{2}$-sentence
formalizable in signatures
$\tau_{\omega_{1}}\subseteq\left\\{\in\right\\}_{\bar{A}_{2}}$: the strategy
we outlined above is efficient (as the many applications of forcing axioms
have already shown) and sufficient to compute all $\Pi_{2}$-sentences which
axiomatize the model companion of $S_{\bar{A}_{2}}$, provided $S$ is any set
theory satisfying sufficiently strong large cardinal axioms (by Corollary 1
all other means to produce the consistenty of $\psi$ with the universal
fragment of $S$ are reducible to forcing).

Our take on the above considerations is that if one embraces the standpoint
that the universe of sets should be as large as possible, model companionship
(in particular Fact 1 – actually its more refined version provided by Lemma
1.21 and used in Thm. 2) gives a simple model theoretic property to
instantiate this slogan: all $\Pi_{2}$-sentences talking about $\omega_{1}$
(i.e. expressible in signature $\tau_{\omega_{1}}$) which are not outward
contradictory with the basic properties of $\omega_{1}$ (i.e. with the
universal theory of some model of $\mathsf{ZFC}+$_large cardinals_ in
signature $\tau_{\omega_{1}}$) should hold true in $H_{\omega_{2}}$. This is
what Thm. 2 says to be the case in models of strong forcing axioms such as
$\text{{\sf MM}}^{++}$.

Note that this is exactly parallel to the way one singles out algebraically
closed fields from rings with no zero-divisors: in this set-up one is
interested to solve polynomial equations while preserving the ring axioms and
not adding zero-divisors; the $\Pi_{2}$-sentences for the signature
$\left\\{+,\cdot,0,1\right\\}$ which are consistent with the ring axioms and
the non existence of zero divisors are exactly the axioms of algebraically
closed fields.

Now coming back to CH we already observed that its negation is a
$\Pi_{2}$-sentence for $\tau_{\omega_{1}}$ (hence also for
$\left\\{\in\right\\}_{\bar{A}_{2}}$), but we can actually get more. Caicedo
and Veličković [6] proved that there is a quantifier free
$\tau_{\omega_{1}}$-formula $\phi(x,y,z)$ such that $(\forall x,y\exists
z\phi(x,y,z))^{H_{\omega_{2}}}$ is forcible (by a proper forcing) over any
model of $\mathsf{ZFC}$; moreover if $V\models\mathsf{ZFC}+(\forall x,y\exists
z\phi(x,y,z))^{H_{\omega_{2}}}$, then $V\models 2^{\omega}=\omega_{2}$. In
particular if we accept as true large cardinal axioms and we require that the
correct axiomatization of set theory maximizes the set of $\Pi_{2}$-sentences
for $\tau_{\omega_{1}}$ which may hold for $H_{\aleph_{2}}$, we are bound to
accept that $2^{\omega}=\omega_{2}$ holds true.

### Structure of the paper

It is now a good place to streamline the remainder of this paper and specify
what the reader need to know in order to grasp each of its parts.

  * •

Section 1 gives a detailed and self-contained account of model companionship;
the unique result which we are not able to trace elsewhere in the literature
is Lemma 1.21, which isolates a key property of (possibly incomplete) first
order theories granting model companionship results; we apply it in later
parts of this paper to various (possibly recursive or incomplete)
axiomatizations of set theory. Since we expect that many of our readers are
not familiar with model companionship, we decided it was worth including here
the key results (with proofs) on this notion. The reader familiar with these
notions can skim through this section or jump it and refer to its relevant
bits when needed elsewhere.

  * •

Section 2 proves Theorem 1.

  * •

Section 3 proves the results needed to establish item 5 of Thm. 2. We first
give a self-contained proof of the form of Woodin’s generic absoluteness
results for second order arithmetic we employ in this paper. This identifies
which subsets of $F_{\left\\{\in\right\\}}$ can play the role of $A_{1}$ for
item 5 of Thm. 2. Then we show that the universal theory of $V$ as formalized
in a signature extending $\tau_{\text{{\sf ST}}}$ with predicates for the non-
stationary ideal and for the universally Baire sets cannot be changed using
set sized forcing if there are class many Woodin cardinals. This identifies
which subsets of $F_{\left\\{\in\right\\}}$ can play the role of $A_{2}$ for
item 5 of Thm. 2.

  * •

Section 4 deals with Theorem 2 for the signature $\tau_{\bar{A}_{1}}$. We
expand slightly the results of [22]: by taking advantage of Lemma 1.21, we are
able here to generalize also to non complete axiomatizations of set theory the
model companionship results given in [22] for complete set theories.

  * •

Section 5 deals with Theorem 2 for the signature $\tau_{\bar{A}_{2}}$.

  * •

We conclude the paper with a final section with some comments and open
questions.

Any reader familiar enough with set theory and model theory to follow this
introduction can easily grasp the content of Sections 1, 2. The same applies
for the results of Section 4 provided one accepts as a black-box Woodin’s
generic absoluteness results for second order arithmetic given in Section 3.
The proofs in Section 3 require familiarity with Woodin’s stationary tower
forcing and (in its second part, cfr. Section 3.4) also with Woodin’s
$\mathbb{P}_{\mathrm{max}}$-technology. Section 5 can be fully appreciated
only by readers familiar with forcing axioms, Woodin’s stationary tower
forcing, Woodin’s $\mathbb{P}_{\mathrm{max}}$-technology.

### Acknowledgements

This paper wouldn’t exist without the brilliant idea by Venturi to relate the
study of the generic multiverse of set theory to Robinson’s model
companionship, or without the major breakthrough of Asperò and Schindler
establishing that Woodin’s axioms $(*)$ follows from $\text{{\sf MM}}^{++}$.
I’m grateful to Boban Velickovic for many useful discussions on the scopes and
limits of the results presented here (the necessity of large cardinal
assumptions in the hypothesis of Thm. 3, and Remark 1 are due to him). I’m
also grateful to Philipp Schlicht who realized Thm. 1 could be easily
established by slightly generalizing the proofs of results occurring in
previous drafts of this paper. I’ve had fruitful discussions on the content of
this paper with many people, let me mention and thank David Asperó, Ilijas
Farah, Juliette Kennedy, Menachem Magidor, Ralf Schindler, Jouko Vaananen,
Andres Villaveces, Hugh Woodin. Clearly none of the persons mentioned here has
any responsibility for any error or orror existing in this paper…. It has been
important to have the opportunity to present these results in several set
theory (or logic) seminars among which those in Toronto, Muenster, Jerusalem,
Paris, Bogotà, Chicago, Helsinki, Torino. This research has been performed
mostly while on sabbatical in the Équipe de Logique Mathématique of the
University of Paris 7 in the academic year 2019-2020; as long as possible it
has been a productive and pleasant experience (until the Covid19 pandemic took
place).

##  1\. Existentially closed structures, model completeness, model
companionship

We present this topic expanding on [20, Sections 3.1-3.2]. We decided to
include detailed proofs since the presentation of [20] is (in some occasions)
rather sketchy, and the focus is not exactly ours.

The first objective is to isolate necessary and sufficient conditions granting
that some $\tau$-structure $\mathcal{M}$ embeds into some model of some
$\tau$-theory $T$.

We expand Notation 3 as follows:

######  Notation 1.1.

We feel free to confuse a $\tau$-structure $\mathcal{M}=(M,\tau^{M})$ with its
domain $M$ and an ordered tuple $\vec{a}\in\mathcal{M}^{<\omega}$ with its set
of elements. Moreover we often write $\mathcal{M}\models\phi(\vec{a})$ rather
than $\mathcal{M}\models\phi(\vec{x})[\vec{x}/\vec{a}]$ when $\mathcal{M}$ is
$\tau$-structure $\vec{a}\in\mathcal{M}^{<\omega}$, $\phi$ is a
$\tau$-formula. We let the atomic diagram of a $\tau$-model
$\mathcal{M}=(M,\tau^{M})$ be the family of quantifier free sentences
$\phi(\vec{a})$ in signature $\tau\cup M$ such that
.$\mathcal{M}\models\phi(\vec{a})$.

######  Definition 1.2.

Given $\tau$-theories $T,S$, a $\tau$-sentence $\psi$ separates $T$ from $S$
if $T\vdash\psi$ and $S\vdash\neg\psi$.

$T$ is $\Pi_{n}$-separated from $S$ if some $\Pi_{n}$-sentence for $\tau$
separates $T$ from $S$.

######  Lemma 1.3.

Assume $S,T$ are $\tau$-theories. TFAE:

  1. (1)

$T$ is not $\Pi_{1}$-separated from $S$ (i.e. no universal sentence $\psi$ is
such that $T\vdash\psi$ and $S\vdash\neg\psi$).

  2. (2)

There is _some_ $\tau$-model $\mathcal{M}$ of $S$ which can be embedded in
some $\tau$-model $\mathcal{N}$ of $T$.

See also [20, Lemma 3.1.1, Lemma 3.1.2, Thm. 3.1.3]

###### Proof.

We assume $T,S$ are closed under logical consequences.

(2) implies (1):

By contraposition we prove $\neg$(1)$\to\neg$(2).

Assume some universal sentence $\psi$ separates $T$ from $S$. Then for any
model of $T$, all its substructures model $\psi$, therefore they cannot be
models of $S$.

(1) implies (2):

By contraposition we prove $\neg$(2)$\to\neg$(1).

Assume that for any model $\mathcal{M}$ of $S$ and $\mathcal{N}$ of $T$
$\mathcal{M}\not\sqsubseteq\mathcal{N}$. We must show that $T$ is
$\Pi_{1}$-separated from $S$.

Given a $\tau$-structure $\mathcal{M}=(M,\tau^{M})$ which models $S$, let
$\Delta_{0}(\mathcal{M})$ be the atomic diagram666We let the atomic diagram of
a $\tau$-model $\mathcal{M}=(M,\tau^{M})$ be the family of quantifier free
formulae in signature $\tau\cup M$ which holds in the natural expansion of
$\mathcal{M}$ to $\tau\cup M$. of $\mathcal{M}$ in the signature $\tau\cup M$.

The theory $T\cup\Delta_{0}(\mathcal{M})$ is inconsistent, otherwise
$\mathcal{M}$ embeds into some model of $T$: let $\bar{\mathcal{Q}}$ be a
$\tau\cup\mathcal{M}$-model of $\Delta_{0}(\mathcal{M})\cup T$ and
$\mathcal{Q}$ be the $\tau$-structure obtained from $\bar{\mathcal{Q}}$
omitting the interpretation of the constants not in $\tau$. Clearly
$\mathcal{Q}$ models $T$. The interpretation of the constants in
$\tau\cup\mathcal{M}$ inside $\bar{\mathcal{Q}}$ defines a $\tau$-substructure
of $\mathcal{Q}$ isomorphic to $\mathcal{M}$.

By compactness (since $\Delta_{0}(\mathcal{M})$ is closed under finite
conjunctions) there is a quantifier free $\tau$-formula
$\psi_{\mathcal{M}}(\vec{x})$ and $\vec{a}\in\mathcal{M}^{<\omega}$ such that
$T+\psi_{\mathcal{M}}(\vec{a})$ is inconsistent. This gives that
$T\vdash\neg\psi_{\mathcal{M}}(\vec{a})$. Since $\vec{a}$ is a family of
constants never occurring in $T$, we get that
$T\vdash\forall\vec{x}\neg\psi_{\mathcal{M}}(\vec{x})$ and
$\mathcal{M}\models\exists\vec{x}\psi_{\mathcal{M}}(\vec{x})$.

The theory

$S\cup\left\\{\neg\exists\vec{x}\psi_{\mathcal{M}}(\vec{x}):\mathcal{M}\models
S\right\\}$

is inconsistent, since $\neg\exists\vec{x}\psi_{\mathcal{M}}(\vec{x})$ fails
in any model $\mathcal{M}$ of $S$.

By compactness there is a finite set of formulae
$\psi_{\mathcal{M}_{1}}\dots\psi_{\mathcal{M}_{k}}$ such that

$S+\bigwedge\left\\{\neg\exists\vec{x}_{i}\psi_{\mathcal{M}_{i}}(\vec{x}_{i}):i=1,\dots,k\right\\}$

is inconsistent. This gives that

$S\vdash\bigvee_{i=1}^{k}\exists\vec{x}_{i}\psi_{\mathcal{M}_{i}}(\vec{x}_{i}).$

The $\tau$-sentence
$\psi:=\bigvee_{i=1}^{k}\exists\vec{x}_{i}\psi_{\mathcal{M}_{i}}(\vec{x}_{i})$
holds in all models of $S$ and its negation

$\bigwedge\left\\{\neg\exists\vec{x}_{i}\psi_{\mathcal{M}_{i}}(\vec{x}_{i}):i=1,\dots,k\right\\}$

is a conjunction of universal sentences (hence —modulo logical equivalence—
universal) derivable from $T$. Hence $\neg\psi$ separates $T$ from $S$.

∎

The following Lemma shows that models of $T_{\forall}$ can always be extended
to superstructures which model $T$.

######  Lemma 1.4.

Let $T$ be a $\tau$-theory and $\mathcal{M}$ be a $\tau$-structure. TFAE:

  1. (1)

$\mathcal{M}$ is a $\tau$-model of $T_{\forall}$.

  2. (2)

There exists $\mathcal{N}\sqsupseteq\mathcal{M}$ which models $T$.

###### Proof.

(2) implies (1) is trivial.

Conversely:

######  Claim 1.

$T$ is not $\Pi_{1}$-separated from $\Delta_{0}(\mathcal{M})$ (in the
signature $\tau\cup\mathcal{M}$).

###### Proof.

If not there are $\vec{a}\in\mathcal{M}^{<\omega}$, and a quantifier free
$\tau$-formula $\phi(\vec{x},\vec{z})$ such that

$T\vdash\forall\vec{z}\phi(\vec{a},\vec{z}),$

while

$\Delta_{0}(\mathcal{M})\vdash\neg\forall\vec{z}\phi(\vec{a},\vec{z}).$

The latter yields that

$\Delta_{0}(\mathcal{M})\vdash\exists\vec{x}\exists\vec{z}\neg\phi(\vec{x},\vec{z}),$

and therefore also that

$\mathcal{M}\models\exists\vec{x}\exists\vec{z}\neg\phi(\vec{x},\vec{z}).$

On the other hand, since the constants $\vec{a}$ do not appear in any of the
sentences in $T$, we also get that

$T\vdash\forall\vec{x}\forall\vec{z}\phi(\vec{x},\vec{z}).$

This is a contradiction since $\mathcal{M}$ models $T_{\forall}$. ∎

By the Claim and Lemma 1.3 some $\tau\cup\mathcal{M}$-model
$\bar{\mathcal{P}}$ of $\Delta_{0}(\mathcal{M})$ embeds into some
$\tau\cup\mathcal{M}$-model $\bar{\mathcal{Q}}$ of $T$. Let $\mathcal{Q}$ be
the $\tau$-structure obtained from $\bar{\mathcal{Q}}$ omitting the
interpretation of the constants not in $\tau$. Then $\mathcal{Q}$ models $T$
and contains a substructure isomorphic to $\mathcal{M}$. ∎

######  Corollary 1.5 (Resurrection Lemma).

Assume $\mathcal{M}\prec_{1}\mathcal{N}$ are $\tau$-structures. Then there is
$\mathcal{Q}\sqsupseteq\mathcal{N}$ which is an elementary extension of
$\mathcal{M}$.

###### Proof.

Let $T$ be the elementary diagram $\Delta_{\omega}(\mathcal{M})$ of
$\mathcal{M}$ in the signature $\tau\cup\mathcal{M}$. It is easy to check that
any model of $T$ when restricted to the signature $\tau$ is an elementay
extension of $\mathcal{M}$. Since $\mathcal{M}\prec_{1}\mathcal{N}$, the
natural extension of $\mathcal{N}$ to a $\tau\cup\mathcal{M}$-structure
realizes the $\Pi_{1}$-fragment of $T$ in the signature $\tau\cup\mathcal{M}$.
Now apply the previous Lemma. ∎

The Resurrection Lemma motivates the resurrection axioms introduced by Hamkins
and Johnstone in [9], and their iterated versions introduced by the author and
Audrito in [5].

###  1.1. Existentially closed structures

The objective is now to isolate the “generic” models of some universal theory
$T$ (i.e. all axioms of $T$ are universal sentences). These are described by
the $T$-existentially closed models.

######  Definition 1.6.

Given a first order signature $\tau$, let $T$ be any consistent $\tau$-theory.
A $\tau$-structure $\mathcal{M}$ is $T$-existentially closed ($T$-ec) if

  1. (1)

$\mathcal{M}$ can be embedded in a model of $T$.

  2. (2)

$\mathcal{M}\prec_{\Sigma_{1}}\mathcal{N}$ for all
$\mathcal{N}\sqsupseteq\mathcal{M}$ which are models of $T$.

In general $T$-ec models need not be models777For example let $T$ be the
theory of commutative rings with no zero divisors which are not fields in the
signature $(+,\cdot,0,1)$. Then the $T$-ec structures are exactly all the
algebraically closed fields, and no $T$-ec model is a model of $T$. By Thm.
2.6 $(H_{\omega_{1}},\sigma_{\omega}^{V})$ is $S$-ec for $S$ the
$\sigma_{\omega}$-theory of $V$, but it is not a model of $S$: the
$\Pi_{2}$-sentence asserting that every set has countable transitive closure
is true in $(H_{\omega_{1}},\sigma_{\omega}^{V})$ but denied by $S$. of $T$,
but only of their universal fragment. A standard diagonalization argument
shows that for any theory $T$ there are $T$-ec models, see Lemma 1.9 below or
[20, Lemma 3.2.11].

A trivial observation which will come handy in the sequel is the following:

######  Fact 1.7.

Assume $\mathcal{M}$ is a $T$-ec model and $S\supseteq T$ is such that some
$\mathcal{N}\sqsupseteq\mathcal{M}$ models $S$. Then $\mathcal{M}$ is $S$-ec.

######  Proposition 1.8.

Assume a $\tau$-structure $\mathcal{M}$ is $T$-ec. Then:

  1. (1)

$\mathcal{M}\models T_{\forall}$.

  2. (2)

$\mathcal{M}$ is also $T_{\forall}$-ec.

  3. (3)

If $\mathcal{N}\prec_{\Sigma_{1}}\mathcal{M}$, then $\mathcal{N}$ is also
$T$-ec.

  4. (4)

Let $\forall\vec{x}\exists\vec{y}\psi(\vec{x},\vec{y},\vec{a})$ be a
$\Pi_{2}$-sentence with $\psi(\vec{x},\vec{y},\vec{z})$ quantifier free
$\tau$-formula and parameters $\vec{a}$ in $\mathcal{M}^{<\omega}$. Assume it
holds in some $\mathcal{N}\sqsupseteq\mathcal{M}$ which models $T_{\forall}$,
then it holds in $\mathcal{M}$.

  5. (5)

Let $S$ be the $\tau$-theory of $\mathcal{M}$. For any $\Pi_{2}$-sentence
$\psi$ in the signature $\tau$ TFAE:

     * •

$\psi$ holds in some model of $S_{\forall}$.

     * •

$\psi$ holds in $\mathcal{M}$.

###### Proof.

__

(1):

There is at least one super-structure of $\mathcal{M}$ which models $T$, and
any $\psi\in T_{\forall}$ holds in this superstructure, hence in
$\mathcal{M}$.

(2):

Assume $\mathcal{M}\sqsubseteq\mathcal{P}$ for some model $\mathcal{P}$ of
$T_{\forall}$. We must argue that $\mathcal{M}\prec_{1}\mathcal{P}$.

By Lemma 1.4, there is $\mathcal{Q}\sqsupseteq\mathcal{P}$ which models $T$.

Since $\mathcal{M}$ and $\mathcal{Q}$ are both models of $T$ and $\mathcal{M}$
is $T$-ec, we get the following diagram:

$\mathcal{M}$$\mathcal{Q}$$\mathcal{P}$$\scriptstyle{\Sigma_{1}}$$\scriptstyle{\sqsubseteq}$$\scriptstyle{\sqsubseteq}$

Then any $\Sigma_{1}$-formula $\psi(\vec{a})$ with
$\vec{a}\in\mathcal{M}^{<\omega}$ realized in $\mathcal{P}$ holds in
$\mathcal{Q}$, and is therefore reflected to $\mathcal{M}$. We are done by
Tarski-Vaught’s criterion.

(3):

Assume $\mathcal{N}\sqsubseteq\mathcal{P}$ for some model of $T_{\forall}$
$\mathcal{P}$. Let $\Delta_{0}(\mathcal{P})$ be the atomic diagram of
$\mathcal{P}$ in the signature $\tau\cup\mathcal{P}\cup\mathcal{M}$ and
$\Delta_{0}(\mathcal{M})$ be the atomic diagram of $\mathcal{M}$ in the same
signature888We are considering $\mathcal{P}\cup\mathcal{M}$ as the union of
the domains of the structure $\mathcal{P},\mathcal{M}$ amalgamated over
$\mathcal{N}$; in particular we add a new constant for each element of
$\mathcal{P}\setminus\mathcal{N}$, a new constant for each element of
$\mathcal{M}\setminus\mathcal{N}$, a new constant for each element of
$\mathcal{N}$..

######  Claim 2.

$T_{\forall}\cup\Delta_{0}(\mathcal{P})\cup\Delta_{0}(\mathcal{M})$ is a
consistent $\tau\cup\mathcal{M}\cup\mathcal{P}$-theory.

###### Proof.

Assume not. Find $\vec{a}\in(\mathcal{P}\setminus\mathcal{N})^{<\omega}$,
$\vec{b}\in(\mathcal{M}\setminus\mathcal{N})^{<\omega}$,
$\vec{c}\in\mathcal{N}^{<\omega}$ and $\tau$-formulae
$\psi_{0}(\vec{x},\vec{z})$, $\psi_{1}(\vec{y},\vec{z})$ such that:

  * •:

$\psi_{0}(\vec{a},\vec{c})\in\Delta_{0}(\mathcal{P})$,

  * •:

$\psi_{1}(\vec{b},\vec{c})\in\Delta_{0}(\mathcal{M})$,

  * •:

$T\cup\left\\{\psi_{0}(\vec{a},\vec{c}),\psi_{1}(\vec{b},\vec{c})\right\\}$ is
inconsistent.

Then

$T\vdash\neg\psi_{0}(\vec{a},\vec{c})\vee\neg\psi_{1}(\vec{b},\vec{c}).$

Since the constants appearing in $\vec{a},\vec{b},\vec{c}$ are never appearing
in sentences of $T$, we get that

$T\vdash\forall\vec{z}\,(\forall\vec{x}\neg\psi_{0}(\vec{x},\vec{z}))\vee(\forall\vec{y}\neg\psi_{1}(\vec{y},\vec{z})).$

Since $\mathcal{P}$ models $T_{\forall}$, and

$\mathcal{P}\models\psi_{0}(\vec{x},\vec{z})[\vec{x}/\vec{a},\vec{z}/\vec{c}],$

we get that

$\mathcal{P}\models\forall\vec{y}\neg\psi_{1}(\vec{y},\vec{c}).$

Therefore

$\mathcal{N}\models\forall\vec{y}\neg\psi_{1}(\vec{y},\vec{c})$

being a substructure of $\mathcal{P}$, and so does $\mathcal{M}$ since
$\mathcal{N}\prec_{1}\mathcal{M}$. This contradicts
$\psi_{1}(\vec{b},\vec{c})\in\Delta_{0}(\mathcal{M})$. ∎

If $\bar{\mathcal{Q}}$ is a model realizing
$T_{\forall}\cup\Delta_{0}(\mathcal{P})\cup\Delta_{0}(\mathcal{M})$, and
$\mathcal{Q}$ is the $\tau$-structure obtained forgetting the constant symbols
not in $\tau$, we get that:

  * •:

$\mathcal{P}$ and $\mathcal{M}$ are both substructures of $\mathcal{Q}$
containing $\mathcal{N}$ as a common substructure;

  * •:

$\mathcal{N}\prec_{1}\mathcal{M}\prec_{1}\mathcal{Q}$, since $\mathcal{Q}$
realizes $T_{\forall}$ and $\mathcal{M}$ is $T_{\forall}$-ec.

We can now conclude that if a $\Sigma_{1}$-formula $\psi(\vec{c})$ for
$\tau\cup\mathcal{N}$ with parameters in $\mathcal{N}$ holds in $\mathcal{P}$,
it holds in $\mathcal{Q}$ as well (since $\mathcal{Q}\sqsupseteq\mathcal{P}$),
and therefore also in $\mathcal{N}$ (since $\mathcal{N}\prec_{1}\mathcal{Q}$).

(4):

Observe that for all $\vec{b}\in\mathcal{M}^{<\omega}$,
$\exists\vec{y}\,\psi(\vec{b},\vec{y},\vec{a})$ holds in $\mathcal{N}$, and
therefore in $\mathcal{M}$, since $\mathcal{M}$ is $T$-ec; hence
$\mathcal{M}\models\forall\vec{x}\exists\vec{y}\psi(\vec{x},\vec{y},\vec{a})$.

(5):

First of all note that $\mathcal{M}$ is $S$-ec since $S\supseteq T$ (by Fact
1.7). By Lemma 1.4 (applied to $S_{\forall}+\psi$ and $\mathcal{M}$) any
$\Pi_{2}$-sentence $\psi$ for $\tau$ which holds in some model of
$S_{\forall}$ holds in some model of $S_{\forall}$ which is a superstructure
of $\mathcal{M}$. Now apply 4.

∎

In particular a structure is $T$-ec if and only if it is $T_{\forall}$-ec, and
a $T$-ec structure realizes all $\Pi_{2}$-sentences which are consistent with
its $\Pi_{1}$-theory.

We now show that any structure $\mathcal{M}$ can always be extended to a
$T$-ec structure for any $T$ which is not separated from the $\Pi_{1}$-theory
of $\mathcal{M}$.

######  Lemma 1.9.

[20, Lemma 3.2.11] Given a first order $\tau$-theory $T$, any model of
$T_{\forall}$ can be extended to a $\tau$-superstructure which is $T$-ec.

###### Proof.

Given a model $\mathcal{M}$ of $T$, we construct an ascending chain of
$T_{\forall}$-models as follows. Enumerate all quantifier free $\tau$-formulae
as $\left\\{\phi_{\alpha}(y,\vec{x}_{\alpha}):\alpha<|\tau|\right\\}$. Let
$\mathcal{M}_{0}=\mathcal{M}$ have size $\kappa\geq|\tau|+\aleph_{0}$. Fix
also some enumeration

$\displaystyle\pi:$ $\displaystyle\kappa\to|\tau|\times\kappa^{2}$
$\displaystyle\alpha\mapsto(\pi_{0}(\alpha),\pi_{1}(\alpha),\pi_{2}(\alpha))$

such that $\pi_{2}(\alpha)\leq\alpha$ for all $\alpha<\kappa$ and for each
$\xi<|\tau|$, and $\eta,\beta<\kappa$ there are unboundedly many
$\alpha<\kappa$ such that $\pi(\alpha)=(\xi,\eta,\beta)$.

Let now $\mathcal{M}_{\eta}$ with enumeration
$\left\\{\vec{m}^{\xi}_{\eta}:\xi<\kappa\right\\}$ of
$\mathcal{M}_{\eta}^{<\omega}$ be given for all $\eta\leq\beta$. If
$\mathcal{M}_{\beta}$ is $T$-ec, stop the construction. Else check whether
$T_{\forall}\cup\Delta_{0}(\mathcal{M}_{\beta})\cup\left\\{\exists
y\phi_{\pi_{0}(\alpha)}(y,\vec{m}^{\pi_{1}(\alpha)}_{\pi_{2}(\alpha)})\right\\}$
is a consistent $\tau\cup\mathcal{M}_{\beta}$-theory; if so let
$\mathcal{M}_{\beta+1}$ have size $\kappa$ and realize this theory. At limit
stages $\gamma$, let $\mathcal{M}_{\gamma}$ be the direct limit of the chain
of $\tau$-structures $\left\\{\mathcal{M}_{\beta}:\beta<\gamma\right\\}$. Then
all $\mathcal{M}_{\xi}$ are models of $T_{\forall}$, and at some stage
$\beta\leq\kappa$ $\mathcal{M}_{\beta}$ is $T_{\forall}$-ec (hence also
$T$-ec), since all existential $\tau$-formulae with parameters in some
$\mathcal{M}_{\eta}$ will be considered along the construction, and realized
along the way if this is possible, and all $\mathcal{M}_{\eta}$ are always
models of $T_{\forall}$ (at limit stages the ascending chain of
$T_{\forall}$-models remains a $T_{\forall}$-model). ∎

Compare the above construction with the standard consistency proofs of bounded
forcing axioms as given for example in [3, Section 2]. In the latter case to
preserve $T_{\forall}$ at limit stages we use iteration theorems999Assume $G$
is $V$-generic for a forcing which is a limit of an iteration of length
$\omega$ of forcings $\left\\{P_{n}:n<\omega\right\\}$. In general
$H_{\omega_{2}}^{V[G]}$ is not given by the union of $H_{\omega_{2}}^{V[G\cap
P_{n}]}$, hence a subtler argument is needed to maintain that
$H_{\omega_{2}}^{V[G]}$ preserves $T_{\forall}$..

###  1.2. The Kaiser hull of a first order theory

The Kaiser Hull of a theory $T$ describes the smallest elementary class
containing all the “generic” structures for $T$. For most theories $T$ the
models of the respective Kaiser hulls realize exactly all $\Pi_{2}$-sentences
which are consistent with the universal fragment of any extension of $T$.

######  Definition 1.10.

[20, Lemma 3.2.12, Lemma 3.2.13] Given a theory $T$ in a signature $\tau$, its
Kaiser hull $\mathrm{KH}(T)$ is given by the $\Pi_{2}$-sentences of $\tau$
which holds in all $T$-ec structures.

######  Definition 1.11.

A $\tau$-theory $T$ is $\Pi_{n}$-complete, if it is consistent and for any
$\Pi_{n}$-sentence either $\phi\in T$ or $\neg\phi\in T$.

By Proposition 1.8.5 we get:

######  Fact 1.12.

Given a $\Pi_{1}$-complete first order $\tau$-theory $T$, its Kaiser Hull is a
$\Pi_{2}$-complete $\tau$-theory defined by the request that for any
$\Pi_{2}$-sentence $\psi$

$\psi\in\mathrm{KH}(T)\quad\text{ if and only if
}\quad\left\\{\psi\right\\}\cup T_{\forall}\text{ is consistent}.$

In particular any model of the Kaiser hull of a $\Pi_{1}$-complete $T$
realizes simultaneously all $\Pi_{2}$-sentences which are individually
consistent with $T_{\forall}$.

For theories $T$ of interests to us their Kaiser hull can be described in the
same terms, but the proof is much more delicate. We start with the following
weaker property which holds for arbitrary theories:

######  Fact 1.13.

Given a $\tau$-theory $T$, its Kaiser hull $\mathrm{KH}(T)$ contains the set
of $\Pi_{2}$-sentences $\psi$ for $\tau$ such that for all complete
$S\supseteq T$, $S_{\forall}\cup\left\\{\psi\right\\}$ is consistent.

###### Proof.

Assume $\psi$ is a $\Pi_{2}$-sentence such that for all complete $S\supseteq
T$, $S_{\forall}\cup\left\\{\psi\right\\}$ is consistent. We must show that
$\psi$ holds in all $T$-ec models.

Fix $\mathcal{M}$ an existentially closed model for $T$ (it exists by Lemma
1.9); we must show that $\mathcal{M}\models\psi$. Let
$\mathcal{N}\sqsupseteq\mathcal{M}$ be a model of $T$ and $S$ be the
$\tau$-theory of $\mathcal{N}$. Then $S$ is a complete theory and
$\mathcal{M}\models S_{\forall}$ since $\mathcal{M}\prec_{1}\mathcal{N}$
(being $T$-ec). Since $S\supseteq T$, $\mathcal{M}$ is also $S$-ec (by Fact
1.7). Since $S_{\forall}\cup\left\\{\psi\right\\}$ is consistent, and
$S_{\forall}$ is $\Pi_{1}$-complete, we obtain that $\mathcal{M}$ models
$\psi$, being an $S_{\forall}$-ec model, and using Fact 1.12. ∎

We will show in Lemma 1.21 that the set of $\Pi_{2}$-sentences described in
the Fact provides an equivalent characterization of the Kaiser hull for many
theories admitting a model companion, among which the axiomatizations of set
theory considered in this paper.

###  1.3. Model completeness

It is possible (depending on the choice of the theory $T$) that there are
models of the Kaiser hull of $T$ which are not $T$-ec. Robinson has come up
with two model theoretic properties (model completeness and model
companionship) which describe the case in which the models of the Kaiser hull
of $T$ are exactly the class of $T$-ec models (even in case $T$ is not a
complete theory).

######  Definition 1.14.

A $\tau$-theory $T$ is _model complete_ if for all $\tau$-models $\mathcal{M}$
and $\mathcal{N}$ of $T$ we have that $\mathcal{M}\sqsubseteq\mathcal{N}$
implies $\mathcal{M}\prec\mathcal{N}$.

Remark that theories admitting quantifier elimination are automatically model
complete. On the other hand model complete theories need not be
complete101010For example the theory of algebraically closed fields is model
complete, but algebraically closed fields of different characteristics are
elementarily inequivalent.. However for theories $T$ which are
$\Pi_{1}$-complete, model completeness entails completeness: any two models of
a $\Pi_{1}$-complete, model complete $T$ share the same $\Pi_{1}$-theory,
therefore if $T_{1}\supseteq T$ and $T_{2}\supseteq T$ with $\mathcal{M}_{i}$
a model of $T_{i}$, we can suppose (by Lemma 1.3) that
$\mathcal{M}_{1}\sqsubseteq\mathcal{M}_{2}$. Since they are both models of
$T$, model completeness entails that $\mathcal{M}_{1}\prec\mathcal{M}_{2}$.

######  Lemma 1.15.

[20, Lemma 3.2.7] (Robinson’s test) Let $T$ be a $\tau$-theory. The following
are equivalent:

  1. (a)

$T$ is model complete.

  2. (b)

Any model of $T$ is $T$-ec.

  3. (c)

Each _existential_ $\tau$-formula $\phi(\vec{x})$ in free variables $\vec{x}$
is $T$-equivalent to a universal $\tau$-formula $\psi(\vec{x})$ in the same
free variables.

  4. (d)

Each $\tau$-formula $\phi(\vec{x})$ in free variables $\vec{x}$ is
$T$-equivalent to a universal $\tau$-formula $\psi(\vec{x})$ in the same free
variables.

Remark that d (or c) shows that being a model complete $\tau$-theory $T$ is
expressible by a $\Delta_{0}(\tau,T)$-property in any model of $\mathsf{ZFC}$,
hence it is absolute with respect to forcing.

###### Proof.

__

a implies b:

Immediate.

b implies c:

Fix an existential formula $\phi(\vec{x})$ in free variables
$x_{1},\dots,x_{n}$. If $\phi(\vec{x})$ is not consistent with $T$ it is
$T$-equivalent to the trivial formula $\forall y(y\neq y)$ in free variables
$\vec{x}$. Hence we may assume that $T\cup\phi(\vec{x})$ is a consistent
theory. Let $\vec{c}=(c_{1},\dots,c_{n})$ be a finite set of new constant
symbols. Then $T\cup\phi(\vec{c})$ is a consistent
$\tau\cup\left\\{c_{1},\dots,c_{n}\right\\}$-theory.

Let $\Gamma$ be the set of universal $\tau$-formulae $\theta(\vec{x})$ such
that

$T\vdash\forall\vec{x}\,(\phi(\vec{x})\rightarrow\theta(\vec{x})).$

Note that $\Gamma$ is closed under finite conjunctions and disjunctions. Let
$\Gamma(\vec{c})=\left\\{\theta(\vec{c}):\,\theta(\vec{x})\in\Gamma\right\\}$.
Note that $T\cup\Gamma(\vec{c})$ is a consistent
$\tau\cup\left\\{c_{1},\dots,c_{n}\right\\}$-theory, since it holds in any
$\tau\cup\left\\{c_{1},\dots,c_{n}\right\\}$-model of $T\cup\phi(\vec{c})$.

It suffices to prove

(1) $T\cup\Gamma(\vec{c})\models\phi(\vec{c});$

if this is the case, by compactness, a finite subset $\Gamma_{0}(\vec{c})$ of
$\Gamma(\vec{c})$ is such that

$T\cup\Gamma_{0}(\vec{c})\models\phi(\vec{c});$

letting
$\bar{\theta}(\vec{x}):=\bigwedge\left\\{\psi(\vec{x}):\psi(\vec{c})\in\Gamma_{0}(\vec{c})\right\\}$,
the latter gives that

$T\models\forall\vec{x}\,(\bar{\theta}(\vec{x})\rightarrow\phi(\vec{x}))$

(since the constants $\vec{c}$ do not appear in $T$).

$\bar{\theta}(\vec{x})\in\Gamma$ is a universal formula witnessing c for
$\phi(\vec{x})$.

So we prove (1):

###### Proof.

Let $\mathcal{M}$ be a $\tau\cup\left\\{c_{1},\dots,c_{n}\right\\}$-model of
$T\cup\Gamma(\vec{c})$. We must show that $\mathcal{M}$ models
$\phi(\vec{c})$.

The key step is to prove the following:

######  Claim 3.

$T\cup\Delta_{0}(\mathcal{M})\cup\left\\{\phi(\vec{c})\right\\}$ is consistent
(where $\Delta_{0}(\mathcal{M})$ is the
$\tau\cup\left\\{c_{1},\dots,c_{n}\right\\}$-atomic diagram of $\mathcal{M}$
in signature $\tau\cup\left\\{c_{1},\dots,c_{n}\right\\}\cup\mathcal{M}$).

Assume the Claim holds and let $\mathcal{N}$ realize the above theory. Then

$\mathcal{M}\sqsubseteq\mathcal{N}\restriction(\tau\cup\left\\{c_{1},\dots,c_{n}\right\\}).$

Hence

$\mathcal{M}\restriction\tau\sqsubseteq\mathcal{N}\restriction\tau.$

By b

$\mathcal{M}\restriction\tau\prec_{1}\mathcal{N}\restriction\tau.$

Now let $b_{1},\dots,b_{n}\in\mathcal{M}$ be the interpretations of
$c_{1},\dots,c_{n}$ in the
$\tau\cup\left\\{c_{1},\dots,c_{n}\right\\}$-structure $\mathcal{M}$. Then

$\mathcal{N}\restriction\tau\models\phi(x_{1},\dots,x_{n})[b_{1},\dots,b_{n}].$

Since $\phi(\vec{x})$ is $\Sigma_{1}$ for $\tau$ and
$b_{1},\dots,b_{n}\in\mathcal{M}$, we get that

$\mathcal{M}\restriction\tau\models\phi(x_{1},\dots,x_{n})[b_{1},\dots,b_{n}],$

hence

$\mathcal{M}\models\phi(c_{1},\dots,c_{n}),$

and we are done.

So we are left with the proof of the Claim.

###### Proof.

Let $\psi(\vec{x},\vec{y})$ be a quantifier free $\tau$-formula such that
$\psi(\vec{c},\vec{a})\in\Delta_{0}(\mathcal{M})$ for some
$\vec{a}\in\mathcal{M}$.

Clearly $\mathcal{M}$ models $\exists\vec{y}\psi(\vec{c},\vec{y})$.

Then the universal formula
$\neg\exists\vec{y}\psi(\vec{c},\vec{y})\not\in\Gamma(\vec{c})$, since
$\mathcal{M}$ models its negation and $\Gamma(\vec{c})$ at the same time.

This gives that

$T\not\vdash\forall\vec{x}\,(\phi(\vec{x})\rightarrow\neg\exists\vec{y}\psi(\vec{x},\vec{y})),$

i.e.

$T\cup\left\\{\exists\vec{x}\,[\phi(\vec{x})\wedge\exists\vec{y}\psi(\vec{x},\vec{y})]\right\\}$

is consistent.

We conclude that

$T\cup\left\\{\phi(\vec{c})\wedge\psi(\vec{c},\vec{a})\right\\}$

is consistent for any tuple $a_{1},\dots,a_{k}\in\mathcal{M}$ and formula
$\psi$ such that $\mathcal{M}$ models $\psi(\vec{c},\vec{a})$ (since
$\vec{c},\vec{a}$ are constants never appearing in the formulae of $T$).

This shows that
$T\cup\Delta_{0}(\mathcal{M})\cup\left\\{\phi(\vec{c})\right\\}$ is
consistent. ∎

(1) is proved. ∎

c implies d:

We prove by induction on $n$ that $\Pi_{n}$-formulae and $\Sigma_{n}$-formulae
are $T$-equivalent to a $\Pi_{1}$-formula.

c gives the base case $n=1$ of the induction for $\Sigma_{1}$-formulae and
(trivially) for $\Pi_{1}$-formulae.

Assuming we have proved the implication for all $\Sigma_{n}$ formulae for some
fixed $n>0$, we obtain it for $\Pi_{n+1}$-formulae
$\forall\vec{x}\psi(\vec{x},\vec{y})$ (with $\psi(\vec{x},\vec{y})$
$\Sigma_{n}$) applying the inductive assumptions to $\psi(\vec{x},\vec{y})$;
next we observe that a $\Sigma_{n+1}$-formula is equivalent to the negation of
a $\Pi_{n+1}$-formula, which is in turn equivalent to the negation of a
universal formula (by what we already argued), which is equivalent to an
existential formula, and thus equivalent to a universal formula (by c).

d implies a:

By d every formula is $T$-equivalent both to a universal formula and to an
existential formula (since its negation is $T$-equivalent to a universal
formula).

This gives that $\mathcal{M}\prec\mathcal{N}$ whenever
$\mathcal{M}\sqsubseteq\mathcal{N}$ are models of $T$, since truth of
universal formulae is inherited by substructures, while truth of existential
formulae pass to superstructures.

∎

We will also need the following:

######  Fact 1.16.

Let $\tau$ be a signature and $T$ a model complete $\tau$-theory. Let
$\sigma\supseteq\tau$ be a signature and $T^{*}\supseteq T$ a $\sigma$-theory
such that every $\sigma$-formula is $T^{*}$-equivalent to a $\tau$-formula.
Then $T^{*}$ is model complete.

###### Proof.

By the model completeness of $T$ and the assumptions on $T^{*}$ we get that
every $\sigma$-formula is equivalent to a $\Pi_{1}$-formula for
$\tau\subseteq\sigma$. We conclude by Robinson’s test. ∎

Later on we will show that in most cases model complete theories maximize the
family of $\Pi_{2}$-sentences compatible with any $\Pi_{1}$-completion of
their universal fragment. This will be part of a broad family of properties
for first order theories which require a new concept in order to be properly
formulated, that of model companionship.

###  1.4. Model companionship

Model completeness comes in pairs with another fundamental concept which
generalizes to arbitrary first order theories the relation existing between
algebraically closed fields and commutative rings without zero-divisors. As a
matter of fact, the case described below occurs when $T^{*}$ is the theory of
algebraically closed fields and $T$ is the theory of commutative rings with no
zero divisors.

######  Definition 1.17.

Given two theories $T$ and $T^{*}$ in the same language $\tau$, $T^{*}$ is the
_model companion_ of $T$ if the following conditions holds:

  1. (1)

Each model of $T$ can be extended to a model of $T^{*}$.

  2. (2)

Each model of $T^{*}$ can be extended to a model of $T$.

  3. (3)

$T^{*}$ is model complete.

Different theories can have the same model companion, for example the theory
of fields and the theory of commutative rings with no zero-divisors which are
not fields both have the theory of algebraically closed fields as their model
companion.

######  Theorem 1.18.

[20, Thm 3.2.14] Let $T$ be a first order theory. If its model companion
$T^{*}$ exists, then

  1. (1)

$T_{\forall}=T^{*}_{\forall}$.

  2. (2)

$T^{*}$ is the theory of the existentially closed models of $T_{\forall}$.

###### Proof.

__

  1. (1)

By Lemma 1.4.

  2. (2)

By Robinson’s test 1.15 $T^{*}$ is the theory realized exactly by the
$T^{*}$-ec models; by Proposition 1.8(2) $\mathcal{M}$ is $T^{*}$-ec if and
only if it is $T^{*}_{\forall}$-ec; by (1) $T^{*}_{\forall}=T_{\forall}$.

∎

An immediate by-product of the above Theorem is that the model companion of a
theory does not necessarily exist, but, if it does, it is unique and is its
Kaiser hull.

######  Theorem 1.19.

[20, Thm. 3.2.9] Assume $T$ has a model companion $T^{*}$. Then $T^{*}$ is
axiomatized by its $\Pi_{2}$-consequences and is the Kaiser hull of
$T_{\forall}$.

Moreover $T^{*}$ is the unique model companion of $T$ and is characterized by
the property of being the unique model complete theory $S$ such that
$S_{\forall}=T_{\forall}$.

###### Proof.

For quantifier free formulae $\psi(\vec{x},\vec{y})$ and
$\phi(\vec{x},\vec{z})$ the assertion

$\forall\vec{x}\,[\exists\vec{y}\psi(\vec{x},\vec{y})\leftrightarrow\forall\vec{z}\phi(\vec{x},\vec{z})]$

is a $\Pi_{2}$-sentence.

Let $T^{**}$ be the theory given by the $\Pi_{2}$-consequences of $T^{*}$.

Since $T^{*}$ is model complete, by Robinson’s test 1.15c, for any
$\Sigma_{1}$-formula $\exists\vec{y}\psi(\vec{x},\vec{y})$ there is a
universal formula $\forall\vec{z}\phi(\vec{x},\vec{z})$ such that

$\forall\vec{x}\,[\exists\vec{y}\psi(\vec{x},\vec{y})\leftrightarrow\forall\vec{z}\phi(\vec{x},\vec{z})]$

is in $T^{**}$.

Again by Robinson’s test 1.15c $T^{**}$ is model complete.

Now assume $S$ is a model complete theory such that $S_{\forall}=T_{\forall}$.
Clearly $T^{*}_{\forall}=T_{\forall}=S_{\forall}$. By Robinson’s test 1.15b
and Proposition 1.8(2), $S_{\forall}$ holds exactly in the $T_{\forall}$-ec
models, but these are exactly the models of $T^{*}$. Hence $T^{*}=S$.

This shows that any model complete theory is axiomatized by its
$\Pi_{2}$-consequences, that the model companion $T^{*}$ of $T$ is unique,
that $T^{*}$ is also the Kaiser hull of $T$ (being axiomatized by the
$\Pi_{2}$-sentences which hold in all $T$-ec-models), and is characterized by
the property of being the unique model complete theory $S$ such that
$T_{\forall}=S_{\forall}$. ∎

Thm. 1.19 provides an equivalent characterization of model companion theories
(which is expressible by a $\Delta_{0}$-property in parameters $T$ and
$T^{*}$, hence absolute for transitive models of $\mathsf{ZFC}$).

Note also that Robinson’s test 1.15d gives an explicit axiomatization of a
model complete theory $T$:

######  Fact 1.20.

Assume $T$ is a model complete $\tau$-theory. Let
$\psi\mapsto\theta_{\psi}^{T}$ be a function assigning to each
$\Sigma_{1}$-formula $\psi(\vec{x})$ for $\tau$ a $\Pi_{1}$-formula
$\theta_{\psi}^{T}(\vec{x})$ which is $T$-equivalent to $\psi(\vec{x})$.

Then $T$ is axiomatized by $T_{\forall}$ and the $\Pi_{2}$-sentences

$\text{{\sf
AX}}_{\psi}^{T}\equiv\forall\vec{x}(\psi(\vec{x})\leftrightarrow\theta_{\psi}^{T}(\vec{x}))$

as $\psi(\vec{x})$ ranges over the $\Sigma_{1}$-formulae for $\tau$.

###### Proof.

First of all

$T^{*}=\left\\{\text{{\sf AX}}_{\psi}^{T}:\psi\text{ a
$\tau$-formula}\right\\}$

is a model complete theory, since $T^{*}$ satisfies Robinson’s test 1.15d. Let
$S=T^{*}+T_{\forall}$. Note that $S$ is also model complete (by Robinson’s
test 1.15d). Moreover $S\subseteq T$ (since $\text{{\sf AX}}_{\psi}^{T}\in T$
for all $\Sigma_{1}$-formulae $\psi$), and $S_{\forall}\supseteq T_{\forall}$
(since $T_{\forall}$ is certainly among the universal consequences of $S$). We
conclude that $S_{\forall}=T_{\forall}$. Therefore $S$ is the model companion
of $T$. $S=T$ by uniqueness of the model companion. ∎

We use the following criteria for model companionship in the proofs of
Theorems 2.6, 4.4, 5.

######  Lemma 1.21.

Let $T,T_{0}$ be $\tau$-theories with $T_{0}$ model complete. Assume that for
every $\Pi_{1}$-sentence $\theta$ for $\tau$ $T+\theta$ is consistent if and
only if so is $T_{0}+\theta$. Then:

  1. (1)

$T^{*}=T_{0}+T_{\forall}$ is the model companion of $T$.

  2. (2)

$T^{*}$ is axiomatized by the the set of $\Pi_{2}$-sentences $\psi$ for $\tau$
such that $S_{\forall}\cup\left\\{\psi\right\\}$ is consistent for all
$\Pi_{1}$-complete $S\supseteq T$.

  3. (3)

$T^{*}$ is axiomatized by the the set of $\Pi_{2}$-sentences $\psi$ for $\tau$
such that for all universal $\tau$-sentences $\theta$
$T_{\forall}+\theta+\psi$ is consistent if and only if so is $T+\theta$.

###### Proof.

By assumption $T_{0}$ is consistent with any finite subset of $T_{\forall}$;
hence, by compactness, $T^{*}=T_{0}+T_{\forall}$ is consistent. By Fact 1.16
$T^{*}$ is model complete.

  1. (1)

We need to show that any model of $T^{*}$ embeds into a model of $T$ and
conversely.

Assume $\mathcal{N}$ models $T^{*}$. Then $\mathcal{N}$ models $T_{\forall}$.
By Lemma 1.4 there exists $\mathcal{M}\sqsupseteq\mathcal{N}$ which models
$T$.

Conversely let $\mathcal{M}$ model $T$ and $S$ be the $\tau$-theory of
$\mathcal{M}$. By assumption (and compactness) there is $\mathcal{N}$ which
models $T_{0}+S_{\forall}$ (but this $\mathcal{N}$ may not be a superstructure
of $\mathcal{M}$). Let $S^{*}$ be the $\tau$-theory of $\mathcal{N}$. Then
$S^{*}_{\forall}=S_{\forall}$, since $S_{\forall}$ and $S^{*}_{\forall}$ are
$\Pi_{1}$-complete theories with $S^{*}_{\forall}\supseteq S_{\forall}$.
Moreover $S^{*}\supseteq T^{*}$, since $S_{\forall}\supseteq T_{\forall}$.

######  Claim 4.

The $\tau\cup\mathcal{M}$-theory $S^{*}\cup\Delta_{0}(\mathcal{M})$ is
consistent.

Assume the Claim holds, then $\mathcal{M}$ is a $\tau$-substructure of a model
of $S^{*}\supseteq T^{*}$ and we are done.

###### Proof.

If not there is $\psi(\vec{a})\in\Delta_{0}(\mathcal{M})$ such that
$S^{*}\cup\left\\{\psi(\vec{a})\right\\}$ is inconsistent. This gives that

$S^{*}\vdash\neg\psi(\vec{a}).$

Since none of the constant in $\vec{a}$ occurs in $\tau$, we get that

$S^{*}\vdash\forall\vec{x}\neg\psi(\vec{x}),$

i.e. $\forall\vec{x}\neg\psi(\vec{x})\in S^{*}_{\forall}=S_{\forall}$. But
$\mathcal{M}$ models $S_{\forall}$ and $\forall\vec{x}\neg\psi(\vec{x})$ fails
in $\mathcal{M}$; a contradiction. ∎

  2. (2)

Assume $\psi\in T^{*}$ and $S$ is a $\Pi_{1}$-complete extension of $T$, we
must show that $S_{\forall}+\psi$ is consistent: by assumption there is
$\mathcal{N}$ which models
$T_{0}+S_{\forall}=T_{0}+T_{\forall}+S_{\forall}=T^{*}+S_{\forall}$, and we
are done. Conversely assume $R_{\forall}+\psi$ is consistent whenever $R$ is a
$\Pi_{1}$-complete extension of $T$. We must show that $\psi\in T^{*}$: pick
$\mathcal{M}$ model of $T^{*}$ and let $S$ be its theory. The assumptions of
the Lemma (and compactness) grant that $T+S_{\forall}$ is consistent. Since
$S$ is complete $S_{\forall}$ is the $\Pi_{1}$-fragment of $T+S_{\forall}$.
Hence $S_{\forall}+\psi$ is consistent, by our assumption on $\psi$. Therefore
$\mathcal{M}\models\psi$ by Proposition 1.8.

  3. (3)

Left to the reader (as the previous item, modulo compactness arguments).

∎

######  Remark 1.22.

We do not know whether the characterization of the model companion of $T$
given in Lemma 1.21(3) can be proved for _all_ theories $T$ admitting a model
companion: following the notation of the Lemma, it is conceivable that some
$\tau$-theory $T$ has a model companion $T^{*}$, but there is some universal
$\tau$-sentence $\theta$ such that for any model $\mathcal{M}$ of $T+\theta$
any superstructure of $\mathcal{M}$ which models $T^{*}$ kills the truth of
$\theta$. In this case some $\Pi_{2}$-sentence in the Kaiser hull of $T$ is
inconsistent with the universal fragment of $T+\theta$.

Note also that if $T^{*}$ is the model companion of $T$ and $\theta$ is a
universal sentence such that $T^{*}+\theta$ is consistent, so is $T+\theta$:
if $\mathcal{M}\models T^{*}+\theta$ there is a superstructure $\mathcal{N}$
of $\mathcal{M}$ which models $T$ (since $T^{*}$ is the model companion of
$T$). Now $\mathcal{M}\prec_{1}\mathcal{N}$, since $\mathcal{M}$ is $T$-ec.
Hence $\mathcal{N}\models\theta$.

###  1.5. Is model companionship a tameness notion?

As we already outlined in the introduction model completeness and model
companionship are “tameness” notion for first order theories which must be
handled with care. We spell out the details in this small section.

######  Proposition 1.23.

Given a signature $\tau$ consider the signature $\tau^{*}$ which adds an
$n$-ary predicate symbol $R_{\phi}$ for any $\tau$-formula
$\phi(x_{1},\dots,x_{n})$ with displayed free variables.

Let $T_{\tau}$ be the following $\tau^{*}$-theory:

  * •

$\forall\vec{x}\,(\phi(\vec{x})\leftrightarrow R_{\phi}(\vec{x}))$ for all
quantifier free $\tau$-formulae $\phi(\vec{x})$,

  * •

$\forall\vec{x}\,[R_{\phi\wedge\psi}(\vec{x})\leftrightarrow(R_{\psi}(\vec{x})\wedge
R_{\phi}(\vec{x}))]$ for all $\tau$-formulae $\phi(\vec{x}),\psi(\vec{x})$,

  * •

$\forall\vec{x}\,[R_{\neg\phi}(\vec{x})\leftrightarrow\neg R_{\phi}(\vec{x})]$
for all $\tau$-formulae $\phi(\vec{x})$,

  * •

$\forall\vec{x}\,[\exists yR_{\phi}(y,\vec{x})\leftrightarrow R_{\exists
y\phi}(\vec{x})]$ for all $\tau$-formulae $\phi(y,\vec{x})$.

Then any $\tau$-structure $\mathcal{N}$ admits a unique extension to a
$\tau^{*}$-structure $\mathcal{N}^{*}$ which models $T_{\tau}$. Moreover every
$\tau^{*}$-formula is $T_{\tau}$-equivalent to an atomic $\tau^{*}$-formula.
In particular for any $\tau$-model $\mathcal{N}$, the algebras of its
$\tau$-definable subsets and of the $\tau^{*}$-definable subsets of
$\mathcal{N}^{*}$ are the same.

Therefore for any consistent $\tau$-theory $T$, $T\cup T_{\tau}$ is consistent
and admits quantifier elemination, hence is model complete.

###### Proof.

By an easy induction one can prove that any $\tau$-formula $\phi(\vec{x})$ is
$T_{\tau}$-equivalent to the atomic $\tau^{*}$-formula $R_{\phi}(\vec{x})$.

Another simple inductive argument brings that any $\tau^{*}$-formula
$\phi(\vec{x})$ is $T_{\tau}$-equivalent to the $\tau$-formula obtained by
replacing all symbols $R_{\psi}(\vec{x})$ occurring in $\phi$ by the
$\tau$-formula $\psi(\vec{x})$. Combining these observations together we get
that any $\tau^{*}$-formula is equivalent to an atomic $\tau^{*}$-formula.

$T_{\tau}$ forces the $\mathcal{M}^{*}$-interpretation of any relation symbol
$R_{\phi}(\vec{x})$ in $\tau^{*}\setminus\tau$ to be the
$\mathcal{M}$-interpretation of the $\tau$-formula $\phi(\vec{x})$ to which it
is $T_{\tau}$-equivalent. ∎

Observe that the expansion of the language from $\tau$ to $\tau^{*}$ behaves
well with respect to several model theoretic notions of tameness distinct from
model completeness: for example $T$ is a _stable_ $\tau$-theory if and only if
so is the $\tau^{*}$-theory $T\cup T_{\tau}$, the same holds for NIP-theories,
or for $o$-minimal theories, or for $\kappa$-categorical theories.

The passage from $\tau$-structures to $\tau^{*}$-structures which model
$T_{\tau}$ can have effects on the embeddability relation; for example assume
$\mathcal{M}\sqsubseteq\mathcal{N}$ is a non-elementary embedding of
$\tau$-structures; then $\mathcal{M}^{*}\not\sqsubseteq\mathcal{N}^{*}$: if
the non-atomic $\tau$-formula $\phi(\vec{a})$ in parameter
$\vec{a}\in\mathcal{M}^{<\omega}$ holds in $\mathcal{M}$ and does not hold in
$\mathcal{N}$, the atomic $\tau^{*}$-formula $R_{\phi}(\vec{a})$ holds in
$\mathcal{M}^{*}$ and does not hold in $\mathcal{N}^{*}$.

However if $T$ is a model complete $\tau$-theory, then for
$\mathcal{M}\sqsubseteq\mathcal{N}$ $\tau$-models of $T$, we get that
$\mathcal{M}\prec\mathcal{N}$; this entails that
$\mathcal{M}^{*}\sqsubseteq\mathcal{N}^{*}$, which (by the quantifier
elimination of $T\cup T_{\tau}$) gives that
$\mathcal{M}^{*}\prec\mathcal{N}^{*}$. In particular for a model complete
$\tau$-theory $T$ and $\mathcal{M},\mathcal{N}$ $\tau$-models of $T$,
$\mathcal{M}\sqsubseteq\mathcal{N}$ if and only if
$\mathcal{M}^{*}\sqsubseteq\mathcal{N}^{*}$.

Let us now investigate the case of model companionship. If $T$ is the model
companion of $S$ with $S\neq T$ in the signature $\tau$, $T\cup T_{\tau}$ and
$S\cup T_{\tau}$ are both model complete theories in the signature $\tau^{*}$.
But $T\cup T_{\tau}$ cannot be the model companion of $S\cup T_{\tau}$, by
uniqueness of the model companion, since each of these theories is the model
companion of itself and they are distinct. Moreover if $T$ and $S$ are also
complete, no $\tau^{*}$-model of $S\cup T_{\tau}$ can embed into a
$\tau^{*}$-model of $T\cup T_{\tau}$: since $T$ is the model companion of $S$
and $S\neq T$, $T_{\forall}=S_{\forall}$ and there is some $\Pi_{2}$-sentence
$\psi$ $\forall x\exists y\phi(x,y)$ with $\phi$-quantifer free in $T\setminus
S$. Therefore $\forall x\,R_{\exists y\phi}(x)\in(T\cup
T_{\tau})_{\forall}\setminus(S\cup T_{\tau})_{\forall}$; we conclude by Lemma
1.3, since $T\cup T_{\tau}$ and $S\cup T_{\tau}$ are complete, hence the above
sentence separates $(T\cup T_{\tau})_{\forall}$ from $(S\cup
T_{\tau})_{\forall}$.

###  1.6. Summing up

The results of this section gives that for any $\tau$-theory $T$:

  * •

The universal fragment of $T$ describes the family of substructures of models
of $T$, and (in most cases, e.g. if $T$ is $\Pi_{1}$-complete) the $T$-ec
models realize all $\Pi_{2}$-sentences which are “absolutely” consistent with
$T_{\forall}$ (i.e. consistent with the universal fragment of any extension of
$T$).

  * •

Model companionship and model completeness describe (almost all) the cases in
which the family of $\Pi_{2}$-sentences which are “absolutely” consistent with
$T$ (as defined in the previous item) describes the elementary class given by
the $T$-ec structures.

  * •

One can always extend $\tau$ to a signature $\tau^{*}$ so that $T$ has a
conservative extension to a $\tau^{*}$-theory $T^{*}$ which is model complete,
but this process may be completely uninformative since it may completely
destroy the substructure relation existing between $\tau$-models of $T$
(unless $T$ is already model complete).

  * •

On the other hand for certain theories $T$ (as the axiomatizations of set
theory considered in the present paper), one can unfold their “tameness” by
carefully extending $\tau$ to a signature $\tau^{*}$ in which only certain
$\tau$-formulae are made equivalent to atomic $\tau^{*}$-formulae. In the new
signature $T$ can be extended to a conservative extension $T^{*}$ which has a
model companion $\bar{T}$, while this process has mild consequences on the
$\tau^{*}$-substructure relation for models of $T^{*}_{\forall}$ (i.e. for the
pairs of interest of $\tau$-models $\mathcal{M}_{0}\sqsubseteq\mathcal{M}_{1}$
of a suitable fragment of $T$, their unique extensions to $\tau^{*}$-models
$\mathcal{M}^{*}_{i}$ are still models of $T^{*}_{\forall}$ and maintain that
$\mathcal{M}^{*}_{0}\sqsubseteq\mathcal{M}^{*}_{1}$ also for $\tau^{*}$). This
gives useful structural information on the web of relations existing between
$\tau^{*}$-models of $T^{*}_{\forall}$ (as outlined by Theorems 2.6, 4.4, 5).

  * •

Our conclusion is that model completeness and model companionship are tameness
properties of elementary classes $\mathcal{E}$ defined by a theory $T$ rather
than of the theory $T$ itself: these model-theoretic notions outline certain
regularity patterns for the substructure relation on models of $\mathcal{E}$,
patterns which may be unfolded only when passing to a signature distinct from
the one in which $\mathcal{E}$ is first axiomatized (much the same way as it
occurs for Birkhoff’s characterization of algebraic varieties in terms of
universal theories).

  * •

The results of the present paper shows that if we consider set theory together
with large cardinal axioms as formalized in the signature
$\sigma_{\omega},\sigma_{\omega,\mathbf{NS}_{\omega_{1}}},\sigma_{\omega_{1}}$,
we obtain (until now unexpected) tameness properties for this first order
theory, properties which couple perfectly with well known (or at least
published) generic absoluteness results. The notion of companionship spectrum
gives a model theoretic criterium for selecting these signatures out of the
continuum many signatures which produce definable extensions of
$\mathsf{ZFC}$. Moreover the common practice of set theory (independently of
our results) motivate the choice of signatures for set theory made in the
present paper (signatures which belong to the companionship spectrum of set
theory), and our results validate it.

##  2\. The theory of $H_{\kappa^{+}}$ is the model companion of set theory

In this section we prove Thm. 1 The following piece of notation will be used
all along this section and supplements Notations 1, 3:

######  Notation 2.1.

__

  * •

$\sigma_{\text{{\sf ST}}}$ is the signature containing a predicate symbol
$S_{\phi}$ of arity $n$ for any $\in$-formula $\phi$ with $n$-many free
variables.

  * •

$\sigma_{\kappa}=\sigma_{\text{{\sf ST}}}\cup\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$ with $\kappa$ a constant symbol.

  * •

$T_{\kappa}$ is the $\sigma_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$-theory given by the axioms

(2) $\forall x_{1}\dots
x_{n}\,[S_{\psi}(x_{1},\dots,x_{n})\leftrightarrow(\bigwedge_{i=1}^{n}x_{i}\subseteq\kappa^{<\omega}\wedge\psi^{\mathcal{P}\left(\kappa^{<\omega}\right)}(x_{1},\dots,x_{n}))]$

as $\psi$ ranges over the $\in$-formulae.

  * •

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

$\mathsf{ZFC}^{-}_{\text{{\sf ST}}}\cup\left\\{\kappa\text{ is an infinite
cardinal}\right\\};$

  * •

$\mathsf{ZFC}^{*-}_{\kappa}$ is the $\sigma_{\kappa}$-theory

$\mathsf{ZFC}^{-}_{\kappa}\cup T_{\kappa};$

  * •

Accordingly we define $\mathsf{ZFC}_{\kappa}$, $\mathsf{ZFC}^{*}_{\kappa}$.

######  Notation 2.2.

Given a $\in$-structure $(M,E)$ and $\tau$ a signature extending
$\tau_{\text{{\sf ST}}}$, from now we let $(M,\tau^{M})$ be the unique
extension of $(M,E)$ defined in accordance with Notation 3 which satisfies
$T_{\tau}$. In particular $(M,\tau^{M})$ is a shorthand for
$(M,S^{M}:S\in\tau)$. If $(N,E)$ is a substructure of $(M,E)$ we also write
$(N,\tau^{M})$ as a shorthand for $(N,S^{M}\restriction N:S\in\tau)$.

###  2.1. By-interpretability of the first order theory of $H_{\kappa^{+}}$
with the first order theory of $\mathcal{P}\left(\kappa\right)$

Let’s compare the first order theory of the structure

$(\mathcal{P}\left(\kappa\right),S_{\phi}^{V}:\phi\text{ an atomic
$\tau_{\text{{\sf ST}}}$-formula})$

with that of the $\tau_{\text{{\sf ST}}}$-theory of $H_{\kappa^{+}}$ in models
of $\mathsf{ZFC}_{\text{{\sf ST}}}$. We will show that they are
$\mathsf{ZFC}_{\tau_{\text{{\sf ST}}}}$-provably by-interpretable with a by-
interpetation translating $H_{\kappa^{+}}$ in a $\Pi_{1}$-definable subset of
$\mathcal{P}\left(\kappa^{2}\right)$ and atomic predicates into
$\Sigma_{1}$-relations over this set. This result is the key to the proof of
Thm. 1 and is just outlining the model theoretic consequences of the well-
known fact that sets can be coded by well-founded extensional graphs.

######  Definition 2.3.

Given $a\in H_{\kappa^{+}}$, $R\in\mathcal{P}\left(\kappa^{2}\right)$ codes
$a$, if $R$ codes a well-founded extensional relation on some
$\alpha\leq\kappa$ with top element $0$ so that the transitive collapse
mapping of $(\alpha,R)$ maps $0$ to $a$.

  * •

$\mathsf{WFE}_{\kappa}$ is the set of $R\in\mathcal{P}\left(\kappa\right)$
which are a well founded extensional relation with domain $\alpha\leq\kappa$
and top element $0$.

  * •

$\text{{\rm Cod}}_{\kappa}:\mathsf{WFE}_{\kappa}\to H_{\kappa^{+}}$ is the map
assigning $a$ to $R$ if and only if $R$ codes $a$.

The following theorem shows that the structure $(H_{\kappa^{+}},\in)$ is
interpreted by means of “imaginaries” in the structure
$(\mathcal{P}\left(\kappa\right),\tau_{\text{{\sf ST}}}^{V})$ by means of:

  * •

a universal $\tau_{\text{{\sf ST}}}\cup\left\\{\kappa\right\\}$-formula (with
quantifiers ranging over subsets of $\kappa^{<\omega}$) defining a set
$\mathsf{WFE}_{\kappa}\subseteq\mathcal{P}\left(\kappa^{2}\right)$.

  * •

an equivalence relation $\cong_{\kappa}$ on $\mathsf{WFE}_{\kappa}$ defined by
an existential $\tau_{\text{{\sf ST}}}\cup\left\\{\kappa\right\\}$-formula
(with quantifiers ranging over subsets of $\kappa^{<\omega}$)

  * •

A binary relation $E_{\kappa}$ on $\mathsf{WFE}_{\kappa}$ invariant under
$\cong_{\kappa}$ representing the $\in$-relation as the extension of an
existential $\tau_{\text{{\sf ST}}}\cup\left\\{\kappa\right\\}$-formula (with
quantifiers ranging over subsets of $\kappa^{<\omega}$)111111See [10, Section
25] for proofs of the case $\kappa=\omega$; in particular the statement and
proof of Lemma 25.25 and the proof of [10, Thm. 13.28] contain all ideas on
which one can elaborate to draw the conclusions of Thm. 2.4..

######  Theorem 2.4.

Assume $\mathsf{ZFC}^{-}_{\kappa}$. The following holds121212Many transitive
supersets of $H_{\kappa^{+}}$ are $\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$-model of $\mathsf{ZFC}^{-}_{\kappa}$ for
$\kappa$ an infinite cardinal (see [13, Section IV.6]). To simplify notation
we assume to have fixed a transitive $\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$-model $\mathcal{N}$ of
$\mathsf{ZFC}^{-}_{\kappa}$ with domain $N\supseteq H_{\kappa^{+}}$. The
reader can easily realize that all these statements holds for an arbitrary
model $\mathcal{N}$ of $\mathsf{ZFC}^{-}_{\kappa}$ replacing $H_{\kappa^{+}}$
with its version according to $\mathcal{N}$.:

  1. (1)

The map $\mathrm{Cod}_{\kappa}$ and $\mathsf{WFE}_{\kappa}$ are defined by
$\mathsf{ZFC}^{-}_{\kappa}$-provably $\Delta_{1}$-properties in parameter
$\kappa$. Moreover $\text{{\rm Cod}}_{\kappa}:\mathsf{WFE}_{\kappa}\to
H_{\kappa^{+}}$ is surjective (provably in $\mathsf{ZFC}^{-}_{\kappa}$), and
$\mathsf{WFE}_{\kappa}$ is defined by a universal $\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$-formula with quantifiers ranging over
subsets of $\kappa^{<\omega}$.

  2. (2)

There are existential $\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$-formulae (with quantifiers ranging over
subsets of $\kappa^{<\omega}$), $\phi_{\in},\phi_{=}$ such that for all
$R,S\in\mathsf{WFE}_{\kappa}$, $\phi_{=}(R,S)$ if and only if $\text{{\rm
Cod}}_{\kappa}(R)=\text{{\rm Cod}}_{\kappa}(S)$ and $\phi_{\in}(R,S)$ if and
only if $\text{{\rm Cod}}_{\kappa}(R)\in\text{{\rm Cod}}_{\kappa}(S)$. In
particular letting

$E_{\kappa}=\left\\{(R,S)\in\mathsf{WFE}_{\kappa}:\phi_{\in}(R,S)\right\\},$
$\cong_{\kappa}=\left\\{(R,S)\in\mathsf{WFE}_{\kappa}:\phi_{=}(R,S)\right\\},$

$\cong_{\kappa}$ is a $\mathsf{ZFC}^{-}_{\kappa}$-provably definable
equivalence relation, $E_{\kappa}$ respects it, and

$(\mathsf{WFE}_{\kappa}/_{\cong_{\kappa}},E_{\kappa}/_{\cong_{\kappa}})$

is isomorphic to $(H_{\kappa^{+}},\in)$ via the map $[R]\mapsto\text{{\rm
Cod}}_{\kappa}(R)$.

###### Proof.

A detailed proof requires a careful examination of the syntactic properties of
$\Delta_{0}$-formulae, in line with the one carried in Kunen’s [13, Chapter
IV]. We outline the main ideas, following Kunen’s book terminology for certain
set theoretic operations on sets, functions and relations (such as
$\operatorname{dom}(f),\operatorname{ran}(f)$, $\text{Ext}(R)$, etc). To
simplify the notation, we prove the results for a transitive model $(N,\in)$
which is then extended to a structure $(N,\tau_{\text{{\sf
ST}}}^{N},\kappa^{N})$ which models $\mathsf{ZFC}^{-}_{\kappa}$, and whose
domain contains $H_{\kappa^{+}}$. The reader can verify by itself that the
argument is modular and works for any other model of
$\mathsf{ZFC}^{-}_{\kappa}$ (transitive or ill-founded, containing the “true”
$H_{\kappa^{+}}$ or not).

  1. (1)

This is proved in details in [13, Chapter IV]. To define
$\mathsf{WFE}_{\kappa}$ by a universal $\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$-property over subsets of $\kappa$ and
$\text{{\rm Cod}}_{\kappa}$ by a $\Delta_{1}$-property for $\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$ over $H_{\kappa^{+}}$, we proceed as
follows:

     * •

_$R$ is an extensional relation with domain contained in $\kappa$ and top
element $0$_ is defined by the $\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$-atomic formula $\psi_{\mathrm{EXT}}(R)$
$\mathsf{ZFC}^{-}_{\kappa}$-provably equivalent to the
$\Delta_{0}(\kappa)$-formula:

$\displaystyle(R\subseteq\kappa^{2})\wedge$
$\displaystyle\wedge(\text{Ext}(R)\in\kappa\vee\text{Ext}(R)=\kappa)\wedge$
$\displaystyle\wedge\forall\alpha,\beta\in\text{Ext}(R)\,[\forall
u\in\text{Ext}(R)\,(u\mathrel{R}\alpha\leftrightarrow
u\mathrel{R}\beta)\rightarrow(\alpha=\beta)]\wedge$
$\displaystyle\wedge\forall\alpha\in\text{Ext}(R)\,\neg(0\mathrel{R}\alpha).$

     * •

$\mathsf{WFE}_{\kappa}$ is defined by the universal $\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$-formula $\phi_{\mathsf{WFE}_{\kappa}}(R)$
(quantifying only over subsets of $\kappa^{<\omega}$)

$\displaystyle\psi_{\mathrm{EXT}}(R)\wedge$ $\displaystyle\wedge[\forall
f\subseteq\kappa^{2}\,(f\text{ is a function }\rightarrow\exists
n\in\omega\,\neg(\langle f(n+1),f(n)\rangle\in R))].$

Its interpretation is the subset of $\mathcal{P}\left(\kappa^{<\omega}\right)$
of the $\sigma_{\kappa}$-symbol $S_{\phi_{\mathsf{WFE}_{\kappa}}}$.

     * •

To define $\text{{\rm Cod}}_{\kappa}$, consider the $\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$-atomic formula $\psi_{\text{{\rm
Cod}}}(G,R)$ provably equivalent to the $\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$-formula:

$\displaystyle\psi_{\mathrm{EXT}}(R)\wedge$ $\displaystyle\wedge(G\text{ is a
function})\wedge$
$\displaystyle\wedge(\operatorname{dom}(G)=\text{Ext}(R))\wedge(\operatorname{ran}(G)\text{
is transitive})\wedge$
$\displaystyle\wedge\forall\alpha,\beta\in\text{Ext}(R)\,[\alpha\mathrel{R}\beta\leftrightarrow
G(\alpha)\in G(\beta)].$

Then $\text{{\rm Cod}}_{\kappa}(R)=a$ can be defined either by the existential
$\tau_{\text{{\sf ST}}}\cup\left\\{\kappa\right\\}$-formula131313Given an $R$
such that $\psi_{\mathrm{EXT}}(R)$ holds, _$R$ is a well founded relation_
holds in a model of $\mathsf{ZFC}^{-}_{\kappa}$ if and only if $\text{{\rm
Cod}}_{\kappa}$ is defined on $R$. In the theory $\mathsf{ZFC}^{-}_{\kappa}$,
$\mathsf{WFE}_{\kappa}$ can be defined using a universal property by a
$\tau_{\text{{\sf ST}}}\cup\left\\{\kappa\right\\}$-formula quantifying only
over subsets of $\kappa$. On the other hand if we allow arbitrary
quantification over elements of $H_{\kappa^{+}}$, we can express the well-
foundedness of $R$ also using the existential formula $\exists
G\,\psi_{\text{{\rm Cod}}_{\kappa}}(G,R)$. This is why $\mathsf{WFE}_{\kappa}$
is defined by a universal $\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$-property in the structure
$(\mathcal{P}\left(\kappa\right),\tau_{\text{{\sf ST}}}^{V},\kappa)$, while
the graph of $\text{{\rm Cod}}_{\kappa}$ can be defined by a
$\Delta_{1}$-property for $\tau_{\text{{\sf ST}}}\cup\left\\{\kappa\right\\}$
in the structure $(H_{\kappa^{+}},\tau_{\text{{\sf ST}}}^{V},\kappa^{V})$.

$\exists G\,(\psi_{\text{{\rm Cod}}}(G,R)\wedge G(0)=a)$

or by the universal $\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$-formula

$\forall G\,(\psi_{\text{{\rm Cod}}}(G,R)\rightarrow G(0)=a).$

  2. (2)

The equality relation in $H_{\kappa^{+}}$ is transferred to the isomorphism
relation between elements of $\mathsf{WFE}_{\kappa}$: if $R,S$ are well-
founded extensional on $\kappa$ with a top-element, the Mostowski collapsing
theorem entails that $\text{{\rm Cod}}_{\kappa}(R)=\text{{\rm
Cod}}_{\kappa}(S)$ if and only if
$(\mathrm{Ext}(R),R)\cong(\mathrm{Ext}(S),S)$. Isomorphism of the two
structures $(\mathrm{Ext}(R),R)\cong(\mathrm{Ext}(S),S)$ is expressed by the
$\Sigma_{1}$-formula for $\tau_{\kappa}$:

$\phi_{=}(R,S)\equiv\exists f\,(f\text{ is a bijection of $\kappa$ onto
$\kappa$ and $\alpha R\beta$ if and only if $f(\alpha)Sf(\beta)$}).$

In particular we get that $S_{\phi_{=}}(R,S)$ holds in $H_{\kappa^{+}}$ for
$R,S\in\mathsf{WFE}_{\kappa}$ if and only if $\text{{\rm
Cod}}_{\kappa}(R)=\text{{\rm Cod}}_{\kappa}(S)$.

Similarly one can express $\text{{\rm Cod}}_{\kappa}(R)\in\text{{\rm
Cod}}_{\kappa}(S)$ by the $\Sigma_{1}$-property $\phi_{\in}$ in
$\tau_{\kappa}$ stating that $(\mathrm{Ext}(R),R)$ is isomorphic to
$(\mathrm{pred}_{S}(\alpha),S)$ for some $\alpha\in\kappa$ with
$\alpha\mathrel{S}0$, where $\mathrm{pred}_{S}(\alpha)$ is given by the
elements of $\mathrm{Ext}(S)$ which are connected by a finite path to
$\alpha$.

Moreover letting $\cong_{\kappa}\subseteq\mathsf{WFE}_{\kappa}^{2}$ denote the
isomorphism relation between elements of $\mathsf{WFE}_{\kappa}$ and
$E_{\kappa}\subseteq\mathsf{WFE}_{\kappa}^{2}$ denote the relation which
translates into the $\in$-relation via $\text{{\rm Cod}}_{\kappa}$, it is
clear that $\cong_{\kappa}$ is a congruence relation over $E_{\kappa}$, i.e.:
if $R_{0}\cong_{\kappa}R_{1}$ and $S_{0}\cong_{\kappa}S_{1}$,
$R_{0}\mathrel{E_{\kappa}}S_{0}$ if and only if
$R_{1}\mathrel{E_{\kappa}}S_{1}$.

This gives that the structure
$(\mathsf{WFE}_{\kappa}/_{\cong_{\kappa}},E_{\kappa}/_{\cong_{\kappa}})$ is
isomorphic to $(H_{\kappa^{+}},\in)$ via the map $[R]\mapsto\text{{\rm
Cod}}_{\kappa}(R)$ (where $\mathsf{WFE}_{\kappa}/_{\cong_{\kappa}}$ is the set
of equivalence classes of $\cong_{\kappa}$ and the quotient relation
$[R]\mathrel{E_{\kappa}/_{\cong_{\kappa}}}[S]$ holds if and only if
$R\mathrel{E_{\kappa}}S$).

This isomorphism is defined via the map $\text{{\rm Cod}}_{\kappa}$, which is
by itself defined by a $\mathsf{ZFC}^{-}_{\kappa}$-provably
$\Delta_{1}$-property for $\tau_{\text{{\sf ST}}}\cup\left\\{\kappa\right\\}$.

The very definition of $\mathsf{WFE}_{\kappa},\cong_{\kappa},E_{\kappa}$ show
that

$\mathsf{WFE}_{\kappa}=S_{\phi_{\mathsf{WFE}_{\kappa}}}^{N},$
$\cong_{\kappa}=S_{\phi_{\mathsf{WFE}_{\kappa}}(x)\wedge\phi_{\mathsf{WFE}_{\kappa}}(y)\wedge\phi_{=}(x,y)}^{N},$
$E_{\kappa}=S_{\phi_{\mathsf{WFE}_{\kappa}}(x)\wedge\phi_{\mathsf{WFE}_{\kappa}}(y)\wedge\phi_{\in}(x,y)}^{N}.$

∎

###  2.2. Model completeness for the theory of $H_{\kappa^{+}}$

######  Theorem 2.5.

Any $\sigma_{\kappa}$-theory $T$ extending

$\mathsf{ZFC}^{*-}_{\kappa}\cup\left\\{\text{all sets have size
$\kappa$}\right\\}$

is model complete.

###### Proof.

To simplify notation, we conform to the assumption of the previous theorem,
i.e. we assume that the model $(N,\in)$ which is uniquely extended to a model
of $\mathsf{ZFC}^{*-}_{\kappa}+$_every set has size $\kappa$_ on which we work
is a transitive superstructure of $H_{\kappa^{+}}$.

The statement _every set has size $\kappa$_ is satisified by a
$\mathsf{ZFC}^{-}_{\kappa}$-model $(N,\tau_{\text{{\sf ST}}}^{V},\kappa)$ with
$N\supseteq H_{\kappa}^{+}$ if and only if $N=H_{\kappa^{+}}$. From now on we
proceed assuming this equality.

By Robinson’s test 1.15 it suffices to show that for all $\in$-formulae
$\phi(\vec{x})$

$\mathsf{ZFC}^{-}_{\kappa}+\text{ every set has size
$\kappa$}\vdash\forall\vec{x}\,(\phi(\vec{x})\leftrightarrow\psi_{\phi}(\vec{x})),$

for some universal $\sigma_{\kappa}$-formula $\psi_{\phi}$.

We will first define a recursive map $\phi\to\theta_{\phi}$ which maps
$\Sigma_{n}$-formulae $\phi$ for $\left\\{\in,\kappa\right\\}$ quantifying
over all elements of $H_{\kappa^{+}}$ to $\Sigma_{n+1}$-formulae
$\theta_{\phi}$ for $\tau_{\text{{\sf ST}}}\cup\left\\{\kappa\right\\}$ whose
quantifier range just over subsets of $\kappa^{<\omega}$.

The proof of the previous theorem gave $\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$-formulae $\theta_{x=y}$, $\theta_{x\in y}$
such that

$S_{\theta_{x=y}}^{H_{\kappa^{+}}}=\cong_{\kappa}=\left\\{(R,S)\in(\mathsf{WFE}_{\kappa})^{2}:\,\text{{\rm
Cod}}_{\kappa}(R)=\text{{\rm Cod}}_{\kappa}(S)\right\\},$ $S_{\theta_{x\in
y}}^{H_{\kappa^{+}}}=E_{\kappa}=\left\\{(R,S)\in(\mathsf{WFE}_{\kappa})^{2}:\,\text{{\rm
Cod}}_{\kappa}(R)\in\text{{\rm Cod}}_{\kappa}(S)\right\\}.$

Specifically (following the notation of that proof)

$\theta_{x=y}=\phi_{\mathsf{WFE}_{\kappa}}(x)\wedge\phi_{\mathsf{WFE}_{\kappa}}(y)\wedge\phi_{=}(x,y),$
$\theta_{x\in
y}=\phi_{\mathsf{WFE}_{\kappa}}(x)\wedge\phi_{\mathsf{WFE}_{\kappa}}(y)\wedge\phi_{\in}(x,y).$

Now for any $\left\\{\in,\kappa\right\\}$-formula $\psi(\vec{x})$, we proceed
to define the $\tau_{\text{{\sf ST}}}\cup\left\\{\kappa\right\\}$-formula
$\theta_{\psi}(\vec{x})$ letting:

  * •

$\theta_{\psi\wedge\psi}(\vec{x})$ be
$\theta_{\psi}(\vec{x})\wedge\theta_{\psi}(\vec{x})$,

  * •

$\theta_{\neg\psi}(\vec{x})$ be $\neg\theta_{\psi}(\vec{x})$,

  * •

$\theta_{\exists y\psi(y,\vec{x})}(\vec{x})$ be $\exists
y\theta_{\psi}(y,\vec{x})\wedge\phi_{\mathsf{WFE}_{\kappa}}(y)$.

An easy induction on the complexity of the $\tau_{\text{{\sf
ST}}}\cup\left\\{\kappa\right\\}$-formulae $\theta_{\phi}(\vec{x})$ gives that
for any $\left\\{\in,\kappa\right\\}$-definable subset $A$ of
$(H_{\kappa^{+}})^{n}$ which is the extension of some
$\left\\{\in,\kappa\right\\}$-formula $\phi(x_{1},\dots,x_{n})$

$\left\\{(R_{1},\dots,R_{n})\in(\mathsf{WFE}_{\kappa})^{n}:\,(\text{{\rm
Cod}}_{\kappa}(R_{1}),\dots,\text{{\rm Cod}}_{\kappa}(R_{n}))\in
A\right\\}=S_{\theta_{\phi}}^{H_{\kappa^{+}}},$

with the further property that
$S_{\theta_{\phi}}^{H_{\kappa^{+}}}\subseteq(\mathsf{WFE}_{\kappa})^{n}$
respects the $\cong_{\kappa}$-relation141414It is also clear from our argument
that the map $\phi\mapsto\theta_{\phi}$ is recursive (and a careful inspection
reveals that it maps a $\Sigma_{n}$-formula to a $\Sigma_{n+1}$-formula)..

Now every $\sigma_{\kappa}$-formula is $\mathsf{ZFC}^{*-}_{\kappa}$-equivalent
to a $\left\\{\in,\kappa\right\\}$-formula151515The map assigning to any
$\sigma_{\kappa}$-formula a $\mathsf{ZFC}^{*-}_{\kappa}$-equivalent
$\left\\{\in,\kappa\right\\}$-formula can also be chosen to be recursive..

Therefore we can extend $\phi\mapsto\theta_{\phi}$ assigning to any
$\sigma_{\kappa}$-formula $\phi(\vec{x})$ the formula $\theta_{\psi}(\vec{x})$
for some $\left\\{\in,\kappa\right\\}$-formula $\psi(\vec{x})$ which is
$\mathsf{ZFC}^{*-}_{\kappa}$-equivalent to $\phi(\vec{x})$.

Then for any $\left\\{\in,\kappa\right\\}$-formula $\phi(x_{1},\dots,x_{n})$
$H_{\kappa^{+}}\models\phi(a_{1},\dots,a_{n})$ if and only if

$(\mathsf{WFE}_{\kappa}/_{\cong_{\kappa}},E_{\kappa}/_{\cong_{\kappa}})\models\phi([R_{1}],\dots,[R_{n}])$

with $\text{{\rm Cod}}_{\kappa}(R_{i})=a_{i}$ for $i=1,\dots,n$ if and only if

$H_{\kappa^{+}}\models\forall
R_{1},\dots,R_{n}\,[(\bigwedge_{i=1}^{n}\text{{\rm
Cod}}_{\kappa}(R_{i})=a_{i})\rightarrow\theta_{\phi}(R_{1},\dots,R_{n})]$

if and only if

$H_{\kappa^{+}}\models\forall
R_{1},\dots,R_{n}\,[(\bigwedge_{i=1}^{n}\text{{\rm
Cod}}_{\kappa}(R_{i})=a_{i})\rightarrow
S_{\theta_{\phi}}(R_{1},\dots,R_{n})].$

Since this argument can be repeated verbatim for any model of
$\mathsf{ZFC}^{*-}_{\kappa}$+_every set has size $\kappa$_, and any
$\sigma_{\kappa}$-formula is $\mathsf{ZFC}^{*-}_{\kappa}$-equivalent to a
$\left\\{\in,\kappa\right\\}$-formula, we have proved the following:

######  Claim 5.

For any $\sigma_{\kappa}$-formula $\phi(x_{1},\dots,x_{n})$,
$\mathsf{ZFC}^{*-}_{\kappa}+$_every set has size $\kappa$_ proves that

$\forall x_{1},\dots,x_{n}\,[\phi(x_{1},\dots,x_{n})\leftrightarrow\forall
y_{1},\dots,y_{n}\,[(\bigwedge_{i=1}^{n}\text{{\rm
Cod}}_{\kappa}(y_{i})=x_{i})\rightarrow
S_{\theta_{\phi}}(y_{1},\dots,y_{n})]].$

But $\text{{\rm Cod}}_{\kappa}(y)=x$ is expressible by an existential
$\tau_{\text{{\sf ST}}}\cup\left\\{\kappa\right\\}$-formula provably in
$\mathsf{ZFC}^{-}_{\kappa}\subseteq\mathsf{ZFC}^{*-}_{\kappa}$, therefore

$\forall y_{1},\dots,y_{n}\,[(\bigwedge_{i=1}^{n}\text{{\rm
Cod}}_{\kappa}(y_{i})=x_{i})\rightarrow S_{\theta_{\phi}}(y_{1},\dots,y_{n})]$

is a universal $\sigma_{\kappa}$-formula, and we are done. ∎

###  2.3. Proof of Thm. 1

Conforming to the notation of Thm. 1, it is clear that $\sigma_{\kappa}$ is a
signature of the form $\left\\{\in\right\\}_{\bar{A}_{\kappa}}$ whenever
$\kappa$ is a $T$-definable cardinal for some $T$ extending $\mathsf{ZFC}$.
Therefore the following result completes the proof of Thm. 1.

######  Theorem 2.6.

Assume $T\supseteq\mathsf{ZFC}^{*}_{\kappa}$ is a $\sigma_{\kappa}$-theory.
Then $T$ has a model companion $T^{*}$. Moreover for any $\Pi_{2}$-sentence
$\psi$ for $\sigma_{\kappa}$, TFAE:

  1. (1)

$\psi\in T^{*}$;

  2. (2)

$T\vdash\psi^{H_{\kappa^{+}}}$;

  3. (3)

For all universal $\sigma_{\kappa}$-sentences $\theta$, $T+\theta$ is
consistent if and only if so is $T_{\forall}+\theta+\psi$.

###### Proof.

By Thm. 2.5, any $\sigma_{\kappa}$-theory extending

$\mathsf{ZFC}^{*-}_{\kappa}+\emph{every set has size $\kappa$}$

is model complete. Therefore so is

$T^{*}=\left\\{\phi:H_{\kappa^{+}}^{\mathcal{M}}\models\phi,\,\mathcal{M}\models
T\right\\},$

since $H_{\kappa^{+}}^{\mathcal{M}}$ models
$\mathsf{ZFC}^{*-}_{\kappa}$+_every set has size $\kappa$_ for any
$\mathcal{M}$ which models $T$.

We must now show that $T^{*}_{\forall}=T_{\forall}$. Assume
$T^{*}\models\theta$ for some universal sentece $\theta$. Then
$H_{\kappa^{+}}^{\mathcal{M}}\models\theta$ for any model $\mathcal{M}$ of
$T$. Since $H_{\kappa^{+}}^{\mathcal{M}}\prec_{1}\mathcal{M}$ for any such
$\mathcal{M}$, we get that any such $\mathcal{M}$ models $\theta$ as well.
Therefore $T^{*}_{\forall}\subseteq T_{\forall}$. Appealing again to Levy
absoluteness, by a similar argument, we get that $T_{\forall}\subseteq
T^{*}_{\forall}$.

We now show that $T^{*}$ is the set of $\Pi_{2}$-sentences $\phi$ such that:

> For all $\Pi_{1}$-sentences $\phi$ for $\tau$, $T+\theta$ is consistent if
> and only if so is $T_{\forall}+\phi+\theta$.

We prove it establishing that $T$ and $T^{*}$ satisfy the assumption of Lemma
1.21 i.e. for any $\Pi_{1}$-sentence $\theta$ for $\sigma_{\kappa}$ $T+\theta$
is consistent if and only if so is $T^{*}+\theta$.

So assume $T+\theta$ is consistent for some $\Pi_{1}$-sentence $\theta$, we
must show that $T^{*}+\theta$ is also consistent, but this is immediate: by
Levy absoluteness if $\mathcal{M}$ models $\theta$, so does
$H_{\kappa^{+}}^{\mathcal{M}}$.

Conversely assume $T+\theta$ is inconsistent for some $\Pi_{1}$-sentence
$\theta$. Then $T\models\neg\theta$. Again by Levy absoluteness if
$\mathcal{M}$ models $T$, $H_{\kappa^{+}}^{\mathcal{M}}\models\neg\theta$.
Hence $\neg\theta\in T^{*}$ by definition, and $\theta$ is inconsistent with
$T^{*}$. ∎

######  Remark 2.7.

Note that the family of models
$\left\\{H_{\kappa^{+}}^{\mathcal{M}}:\,\mathcal{M}\models T\right\\}$ we used
to define $T^{*}$ may not be an elementary class for $\sigma_{\kappa}$.

Thm. 2.6 can be proved for many other signatures other than $\sigma_{\kappa}$.
It suffices that the signature in question adds new predicates just for
definable subsets of $\mathcal{P}\left(\kappa\right)^{n}$, and also that it
adds family of predicates which are closed under definability (i.e.
projections, complementation, finite unions, permutations) and under the map
$\text{{\rm Cod}}_{\kappa}$. Under these assumptions we can still use Lemma 1
and Fact 1.13 to argue for the evident variations of the proof of Thm. 2.6 to
this set up. However linking these model companionship results to generic
absoluteness as we do in Theorem 2 requires much more care in the definition
of the signature. We will pursue this matter in more details in the next
sections.

###  2.4. A weak version of Theorem 2 for third order arithmetic

We can prove a weak version of Thm. 2 for the theory of $H_{\aleph_{2}}$
appealing to the generic absoluteness results of [23, 4, 5] which establish
the invariance of the theory of $H_{\aleph_{2}}$ in models of strong forcing
axioms with respect to stationary set preserving forcings preserving these
axioms.

Let $\mathsf{ZFC}^{*}_{\omega_{1}}\supseteq\mathsf{ZFC}_{\text{{\sf ST}}}$ be
the $\sigma_{\omega_{1}}=\sigma_{\omega}\cup\left\\{\kappa\right\\}$-theory
obtained adding axioms which force in each of its $\sigma_{\omega_{1}}$-models
$\kappa$ to be interpreted by the first uncountable cardinal, and each
predicate symbol $S_{\phi}$ to be interpreted as the subset of
$\mathcal{P}\left(\omega_{1}^{<\omega}\right)^{n}$ defined by
$\phi^{\mathcal{P}\left(\omega_{1}^{<\omega}\right)}(x_{1},\dots,x_{n})$.

######  Theorem 2.8.

Let $T$ be a $\sigma_{\omega_{1}}$-theory extending

$\mathsf{ZFC}^{*}_{\omega_{1}}+\text{{\sf MM}}^{+++}+\emph{there are class
many superhuge cardinals}.$

TFAE for any $\Pi_{2}$-sentence $\psi$ for $\sigma_{\omega_{1}}$:

  1. (1)

$S_{\forall}+\psi$ is consistent for all complete $S$ extending $T$;

  2. (2)

$T$ proves that some stationary set preserving forcing notion $P$ forces
$\psi^{\dot{H}_{\omega_{2}}}+\text{{\sf MM}}^{+++}$;

  3. (3)

$T\vdash\psi^{H_{\omega_{2}}}$.

See Remarks 2.9(2) for some information on $\text{{\sf MM}}^{+++}$, and 2.9(1)
for informations on superhugeness.

The proof of Theorem 2.8 is a trivial variation of the proof of Theorem 2.6:

###### Proof.

[23, Thm. 5.18] gives that 2.8(3) and 2.8(2) are equivalent. Theorem 2.6
establishes the equivalence of 2.8(3) and 2.8(1). ∎

######  Remark 2.9.

__

  1. (1)

$\delta$ is superhuge if it supercompact and this can be witnessed by huge
embeddings. A superhuge cardinal is consistent relative to the existence of a
$2$-huge cardinal.

  2. (2)

For a definition of $\text{{\sf MM}}^{+++}$ see [23, Def. 5.19]. We just note
that $\text{{\sf MM}}^{+++}$ is a natural strengthening of Woodin’s axiom
$(*)$ (by the recent breakthrough of Asperò and Schindler [2]) and of Martin’s
maximum (for example any of the standard iterations to produce a model of
Martin’s maximum produce a model of $\text{{\sf MM}}^{+++}$ if the iteration
has length a superhuge cardinal [23, Thm 5.29]).

  3. (3)

We can prove exactly the same results of Thm. 2.8 replacing (verbatim in its
statement) $\text{{\sf MM}}^{+++}$ by any of the axioms
$\mathsf{RA}_{\omega}(\Gamma)$ introduced in [5] or the axioms
$\mathsf{CFA}(\Gamma)$ and $\mathsf{BCFA}(\Gamma)$ introduced in [4], provided
in item 2.8(2) _stationary set preserving forcing notion $P$_ is replaced by
$P\in\Gamma$.

  4. (4)

We consider Thm. 2.8 weaker than Thm. 2 or Corollary 1, because in Corollary 1
one can choose the theory $T$ to be inconsistent with $\text{{\sf MM}}^{++}$
without hampering its conclusion (for example $T$ could satisfy $\mathsf{CH}$,
a statement denied by $\text{{\sf MM}}^{++}$), and because Corollary 1C holds
for all forcing notions $P$ unlike Thm. 2.8(2). The key point separating these
two results is that the signature $\sigma_{\omega_{1}}$ is too expressive and
renders many statements incompatible with forcing axioms formalizable by
existential (or even atomic) $\sigma_{\omega_{1}}$-sentences (for example such
is the case for $\mathsf{CH}$).

  5. (5)

A key distinction between the signature $\sigma_{\omega_{1}}$ and the
signature $\left\\{\in\right\\}_{\bar{A}_{2}}$ considered in Thm. 2 is that
for any $T\supseteq\mathsf{ZFC}+$_appropriate large cardinals_ $\mathsf{CH}$
cannot be $T$-equivalent to a $\Sigma_{1}$-sentence for
$\left\\{\in\right\\}_{\bar{A}_{2}}$ because CH is a statement which can
change its truth value across forcing extensions, while the universal
$\left\\{\in\right\\}_{\bar{A}_{2}}$-sentences maintain the same truth value
across all forcing extensions of a model of $T$, by Thm. 2(5). On the other
hand CH is $\mathsf{ZFC}_{\omega_{1}}$-equivalent to an atomic
$\sigma_{\omega_{1}}$-sentence. $\neg\mathsf{CH}$ is the simplest example of
the type of $\Pi_{2}$-sentences which exemplifies why Thm. 2.8(2) is much
weaker than Thm. 2, and why Thm. 2 for the signature
$\left\\{\in\right\\}_{\bar{A}_{2}}$ needs a different (and as we will see
much more sophisticated) proof strategy than the one we use here to establish
Theorems 2.6 and 2.8.

##  3\. Generic invariance results for signatures of second and third order
arithmetic

We collect here generic absoluteness results results needed to prove Thm. 2.
We prove all these results working in “standard” models of $\mathsf{ZFC}$,
i.e. we assume the models are well-founded. This is a practice we already
adopted in Section 2. We leave to the reader to remove this unnecessary
assumption.

###  3.1. Universally Baire sets and generic absoluteness for second order
number theory

We recall here the properties of universally Baire sets and the generic
absoluteness results for second order number theory we need to prove Thm. 2.

######  Notation 3.1.

$\mathcal{A}\subseteq\bigcup_{n\in\omega}\mathcal{P}\left(\kappa\right)^{n}$
is projectively closed if it is closed under projections, finite unions,
complementation, and permutations (if $\sigma:n\to n$ is a permutation and
$A\subseteq\mathcal{P}\left(\kappa\right)^{n}$,
$\hat{\sigma}[A]=\left\\{(a_{\sigma(0)},\dots,a_{\sigma(n-1}):\,(a_{0},\dots,a_{n-1})\in
A\right\\}$).

Otherwise said, $\mathcal{A}$ is the class of lightface definable subsets of
some signature on $\mathcal{P}\left(\kappa\right)$.

###  3.2. Universally Baire sets

Assuming large cardinals there is a very large sample of projectively closed
families of subsets of $\mathcal{P}\left(\omega\right)$ which are are
“simple”, hence it is natural to consider elements of these families as atomic
predicates.

The exact definition of what is meant by a “simple” subset of $2^{\omega}$ is
captured by the notion of universally Baire set.

Given a topological space $(X,\tau)$, $A\subseteq X$ is nowhere dense if its
closure has a dense complement, meager if it is the countable union of nowhere
dense sets, with the Baire property if it has meager symmetric difference with
an open set. Recall that $(X,\tau)$ is Polish if $\tau$ is a completely
metrizable, separable topology on $X$.

######  Definition 3.2.

(Feng, Magidor, Woodin) Given a Polish space $(X,\tau)$, $A\subseteq X$ is
_universally Baire_ if for every compact Hausdorff space $(Y,\sigma)$ and
every continuous $f:Y\to X$ we have that $f^{-1}[A]$ has the Baire property in
$Y$.

$\mathsf{UB}$ denotes the family of universally Baire subsets of $X$ for some
Polish space $X$.

We adopt the convention that $\mathsf{UB}$ denotes the class of universally
Baire sets and of all elements of $\bigcup_{n\in\omega+1}(2^{\omega})^{n}$
(since the singleton of such elements are universally Baire sets).

The theorem below outlines three simple examples of projectively closed
families of universally Baire sets containing $2^{\omega}$.

######  Theorem 3.3.

Let $T_{0}$ be the $\tau_{\text{{\sf ST}}}$-theory $\mathsf{ZFC_{\text{{\sf
ST}}}}+$_there are infinitely many Woodin cardinals and a measurable above_
and $T_{1}$ be the $\tau_{\text{{\sf ST}}}$-theory $\mathsf{ZFC_{\text{{\sf
ST}}}}+$_there are class many Woodin cardinals_.

  1. (1)

[15, Thm. 3.1.12, Thm. 3.1.19] Assume $V$ models $T_{0}$. Then every
projective subset of $2^{\omega}$ is universally Baire.

  2. (2)

[15, Thm. 3.3.3, Thm. 3.3.5, Thm. 3.3.6, Thm. 3.3.8, Thm. 3.3.13, Thm. 3.3.14]
Assume $V\models T_{1}$. Then $\mathsf{UB}$ is projectively closed.

To proceed further we now list the standard facts about universally Baire sets
we will need:

  1. (1)

[10, Thm. 32.22] $A\subseteq 2^{\omega}$ is universally Baire if and only if
for each forcing notion $P$ there are trees $T_{A},S_{A}$ on
$\omega\times\delta$ for some $\delta>|P|$ such that $A=p[[T_{A}]]$ (where
$p:(2\times\kappa)^{\omega}\to 2^{\omega}$ denotes the projection on the first
component and $[T]$ denotes the body of the tree $T$), and

$P\Vdash T_{A}\text{ and }S_{A}\text{ project to complements},$

by this meaning that for all $G$ $V$-generic for $P$

$V[G]\models(p[[T_{A}]]\cap p[[S_{A}]]=\emptyset)\wedge(p[[T_{A}]]\cup
p[[S_{A}]]=(2^{\omega})^{V[G]})$

  2. (2)

Any two Polish spaces $X,Y$ of the same cardinality are Borel isomorphic [12,
Thm. 15.6].

  3. (3)

Any Polish space is Borel isomorphic to a Borel subset of $[0;1]^{\omega}$
[12, Thm. 4.14], hence also to a Borel subset of $2^{\omega}$ (by the previous
item).

  4. (4)

Given $\phi:\mathbb{N}\to\mathbb{N}$, $\prod_{n\in\omega}2^{\phi(n)}$ is
Polish (it is actually homemomorphic to the union of $2^{\omega}$ with a
countable Hausdorff space) [12, Thm. 6.4, Thm. 7.4].

Hence it is not restrictive to focus just on universally Baire subsets of
$2^{\omega}$ and of its countable products, which is what we will do in the
sequel.

######  Notation 3.4.

Given $G$ a $V$-generic filter for some forcing $P\in V$, $A\in\text{{\sf
UB}}^{V[G]}$ and $H$ $V[G]$-generic filter for some forcing $Q\in V[G]$,

$A^{V[G][H]}=\left\\{r\in(2^{\omega})^{V[G][H]}:V[G][H]\models r\in
p[[T_{A}]]\right\\},$

where $(T_{A},S_{A})\in V[G]$ is any pair of trees as given in item 1 above
such that $p[[T_{A}]]=A$ holds in $V[G]$, and $(T_{A},S_{A})$ project to
complements in $V[G][H]$.

###  3.3. Generic absoluteness for second order number theory

The following generic absoluteness result is the key to establish Thm. 2(5)
for the signature $A_{1}$.

We decide to include a full proof of Woodin’s generic absoluteness results for
second order number theory we use in this paper. The version we need follows
readily from [15, Thm. 3.1.2] and the assumptions that there exists class many
Woodin limits of Woodin; here we reduce these large cardinal assumptions to
the existence of class many Woodin cardinals, while providing an alternative
approach to the proof of some of these result. The theorem below is an
improvement of [24, Thm. 3.1].

######  Theorem 3.5.

Assume in $V$ there are class many Woodin cardinals. Let $\mathcal{A}\in V$ be
a family of universally Baire sets of $V$ and
$\tau_{\mathcal{A}}=\tau_{\text{{\sf ST}}}\cup\mathcal{A}$. Let $G$ be
$V$-generic for some forcing notion $P\in V$.

Then

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

###### Proof.

We proceed by induction on $n$ to prove the following stronger assertion:

######  Claim 6.

Whenever $G$ is $V$-generic for some forcing notion $P$ in $V$ and $H$ is
$V[G]$-generic for some forcing notion $Q$ in $V[G]$

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

###### Proof.

It is not hard to check that for all $A\in\mathcal{A}$,
$A^{V[G]}=A^{V[G][H]}\cap V[G]$ (choose in $V$ a pair of trees $(T,S)$ such
that $A=p[[T]]$ and the pair $(T,S)$ projects to complements in $V[G][H]$, and
therefore also in $V[G]$). Therefore $(H_{\omega_{1}}^{V[G]},\tau_{\text{{\sf
ST}}}^{V[G]},A^{V[G]}:A\in\mathcal{A})$ is a $\tau_{\mathcal{A}}$-substructure
of $(H_{\omega_{1}}^{V[G][H]},\tau_{\text{{\sf
ST}}}^{V[G][H]},A^{V[G][H]}:A\in\mathcal{A})$.

This proves the base case of the induction.

We prove the successor step.

Assume that for any $G$ $V$-generic for some forcing $P\in V$ and $H$
$V[G]$-generic for some forcing $Q\in V[G]$

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

Fix $\bar{G}$ and $\bar{H}$ as in the assumptions of the Claim as witnessed by
forcings $\bar{P}\in V$ and $\bar{Q}\in V[\bar{G}]$.

We want to show that

$(H_{\omega_{1}}^{V[\bar{G}]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}]},A^{V[\bar{G}]}:A\in\mathcal{A})\prec_{n+1}(H_{\omega_{1}}^{V[\bar{G}][\bar{H}]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}][\bar{H}]},A^{V[\bar{G}][\bar{H}]}:A\in\mathcal{A}).$

Let $\gamma$ be a Woodin cardinal of $V$ such that
$\bar{P}\ast\dot{\bar{Q}}\in V_{\gamma}$ (where $\dot{\bar{Q}}\in V^{P}$ is
chosen so that $\dot{\bar{Q}}_{G}=\bar{Q}$).

Then $\gamma$ is Woodin also in $V[\bar{G}]$. Let $K$ be $V[\bar{G}]$-generic
for161616$\mathcal{T}^{\omega_{1}}_{\gamma}$ denotes here the countable tower
of height $\gamma$ denoted as $\mathbb{Q}_{<\gamma}$ in [15, Section 2.7].
$(\mathcal{T}^{\omega_{1}}_{\gamma})^{V[\bar{G}]}$ with $\bar{H}\in V[K]$, so
that $V[\bar{G}][K]=V[\bar{G}][\bar{H}][\bar{K}]$ for some $\bar{K}\in
V[\bar{G}][K]$.

Hence we have the following diagram:

$(H_{\omega_{1}}^{V[\bar{G}]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}]},A^{V[\bar{G}]}:A\in\mathcal{A})$$(H_{\omega_{1}}^{V[\bar{G}][K]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}][K]},A^{V[\bar{G}][K]}:A\in\mathcal{A})$$(H_{\omega_{1}}^{V[\bar{G}][\bar{H}]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}][\bar{H}]},A^{V[\bar{G}][\bar{H}]}:A\in\mathcal{A})$$\scriptstyle{\Sigma_{\omega}}$$\scriptstyle{\Sigma_{n}}$$\scriptstyle{\Sigma_{n}}$

obtained by inductive hypothesis applied both on $V[\bar{G}]$,
$V[\bar{G}][\bar{H}]$ and on $V[\bar{G}][\bar{H}]$,
$V[\bar{G}][\bar{H}][\bar{K}]$, and using the fact that
$(H_{\omega_{1}}^{V[\bar{G}][K]},\tau_{\text{{\sf
UB}}^{V[\bar{G}]}}^{V[\bar{G}][K]})$ is a fully elementary superstructure of
$(H_{\omega_{1}}^{V[\bar{G}]},\tau_{\text{{\sf
UB}}^{V[\bar{G}]}}^{V[\bar{G}]})$ [15, Thm. 2.7.7, Thm. 2.7.8].

Let $\phi\equiv\exists x\psi(x)$ be any $\Sigma_{n+1}$ formula for
$\tau_{\mathcal{A}}$ with parameters in $H_{\omega_{1}}^{V[\bar{G}]}$. First
suppose that $\phi$ holds in $(H_{\omega_{1}}^{V[\bar{G}]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}]},A^{V[\bar{G}]}:A\in\mathcal{A})$, and fix $\bar{a}\in
V[\bar{G}]$ such that $\psi(\bar{a})$ holds in
$(H_{\omega_{1}}^{V[\bar{G}]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}]},A^{V[\bar{G}]}:A\in\mathcal{A})$. Since

$(H_{\omega_{1}}^{V[\bar{G}]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}]},A^{V[\bar{G}]}:A\in\mathcal{A})\prec_{n}(H_{\omega_{1}}^{V[\bar{G}][\bar{H}]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}][\bar{H}]},A^{V[\bar{G}][\bar{H}]}:A\in\mathcal{A}),$

we conclude that $\psi(\bar{a})$ holds in
$(H_{\omega_{1}}^{V[\bar{G}][\bar{H}]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}][\bar{H}]},A^{V[\bar{G}][\bar{H}]}:A\in\mathcal{A})$, hence
so does $\phi$.

Now suppose that $\phi$ holds in
$(H_{\omega_{1}}^{V[\bar{G}][\bar{H}]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}][\bar{H}]},A^{V[\bar{G}][\bar{H}]}:A\in\mathcal{A})$ as
witnessed by $\bar{a}\in H_{\omega_{1}}^{V[\bar{G}][\bar{H}]}$.

Since

$(H_{\omega_{1}}^{V[\bar{G}][\bar{H}]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}][\bar{H}]},A^{V[\bar{G}][\bar{H}]}:A\in\mathcal{A})\prec_{n}(H_{\omega_{1}}^{V[\bar{G}][K]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}][K]},A^{V[\bar{G}][K]}:A\in\mathcal{A}),$

it follows that $\psi(\bar{a})$ holds in
$(H_{\omega_{1}}^{V[\bar{G}][K]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}][K]},A^{V[\bar{G}][K]}:A\in\mathcal{A})$, hence so does
$\phi$. Since

$(H_{\omega_{1}}^{V[\bar{G}]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}]},A^{V[\bar{G}]}:A\in\mathcal{A})\prec(H_{\omega_{1}}^{V[\bar{G}][K]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}][K]},A^{V[\bar{G}][K]}:A\in\mathcal{A}),$

the formula $\phi$ holds also in
$(H_{\omega_{1}}^{V[\bar{G}]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}]},A^{V[\bar{G}]}:A\in\mathcal{A})$.

Since $\phi$ is arbitrary, this shows that

$(H_{\omega_{1}}^{V[\bar{G}][\bar{H}]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}]},A^{V[\bar{G}]}:A\in\mathcal{A})\prec_{n+1}(H_{\omega_{1}}^{V[\bar{G}][\bar{H}]},\tau_{\text{{\sf
ST}}}^{V[\bar{G}][\bar{H}]},A^{V[\bar{G}][\bar{H}]}:A\in\mathcal{A}),$

concluding the proof of the inductive step for $\bar{G}$ and $\bar{H}$.

Since we have class many Woodin, this argument is modular in $\bar{G},\bar{H}$
as in the assumptions of the inductive step, because we can always find some
Woodin cardinal $\gamma$ of $V$ which remains Woodin in $V[\bar{G}]$ and is of
size larger than the poset in $V[\bar{G}]$ for which $\bar{H}$ is
$V[\bar{G}]$-generic. The proof of the inductive step is completed. ∎

∎

###  3.4. Generic invariance for the universal fragment of the theory of $V$
with predicates for the non-stationary ideal and for universally Baire sets

The results of this section are the key to establish Thm. 2(5) for the
signature $A_{1}$. The proofs require some familiarity with the basics of the
$\mathbb{P}_{\mathrm{max}}$-technology and with Woodin’s stationary tower
forcing.

######  Notation 3.6.

__

  * •

$\tau_{\mathbf{NS}_{\omega_{1}}}$ is the signature $\tau_{\text{{\sf
ST}}}\cup\left\\{\omega_{1}\right\\}\cup\left\\{\mathbf{NS}_{\omega_{1}}\right\\}$
with $\omega_{1}$ a constant symbol, $\mathbf{NS}_{\omega_{1}}$ a unary
predicate symbol.

  * •

$T_{\mathbf{NS}_{\omega_{1}}}$ is the $\tau_{\mathbf{NS}_{\omega_{1}}}$-theory
given by $T_{\text{{\sf ST}}}$ together with the axioms

$\omega_{1}\text{ is the first uncountable cardinal},$ $\forall
x\;[(x\subseteq\omega_{1}\text{ is non-
stationary})\leftrightarrow\mathbf{NS}_{\omega_{1}}(x)].$

  * •

$\mathsf{ZFC}^{-}_{\mathbf{NS}_{\omega_{1}}}$ is the
$\tau_{\mathbf{NS}_{\omega_{1}}}$-theory

$\mathsf{ZFC}^{-}_{\text{{\sf ST}}}+T_{\mathbf{NS}_{\omega_{1}}}.$

  * •

Accordingly we define $\mathsf{ZFC}_{\mathbf{NS}_{\omega_{1}}}$.

The following is the key to establish Thm. 2(5) for the signature $A_{2}$.

######  Theorem 3.

Assume $(V,\in)$ models $\mathsf{ZFC}+$_there are class many Woodin
cardinals_. Then the $\Pi_{1}$-theory of $V$ for the language
$\tau_{\mathbf{NS}_{\omega_{1}}}\cup\text{{\sf UB}}^{V}$ is invariant under
set sized forcings171717Here we consider any $A\subseteq(2^{\omega})^{k}$ in
$\text{{\sf UB}}^{V}$ as a predicate symbol of arity $k$..

Asperó and Veličkovic̀ provided the following basic counterexample to the
conclusion of the theorem if large cardinal assumptions are dropped.

######  Remark 3.7.

Let $\phi(y)$ be the $\Delta_{1}$-property in
$\tau_{\mathbf{NS}_{\omega_{1}}}$

$\exists y(y=\omega_{1}\wedge L_{y+1}\models y=\omega_{1}).$

Then $L$ models this property, while the property fails in any forcing
extension of $L$ which collapses $\omega_{1}^{L}$ to become countable.

In order to prove the Theorem we need to recall some basic terminology and
facts about iterations of countable structures.

####  3.4.1. Generic iterations of countable structures

######  Definition 3.8.

[14, Def. 1.2] Let $M$ be a transitive countable model of $\mathsf{ZFC}$. Let
$\gamma$ be an ordinal less than or equal to $\omega_{1}$. An iteration
$\mathcal{J}$ of $M$ of length $\gamma$ consists of 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:

  * •

$M_{0}=M$,

  * •

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

  * •

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

  * •

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

  * •

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.

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)$ will
denote the domain of $j_{\alpha\beta}$ for any $\alpha\leq\beta\leq\gamma$.

######  Definition 3.9.

Let $A$ be a universally Baire sets of reals. $M$ is $A$-iterable if:

  1. (1)

$M$ is transitive and such that $H_{\omega_{1}}^{M}$ is countable.

  2. (2)

$M\models\mathsf{ZFC}+\mathbf{NS}_{\omega_{1}}$_is precipitous_.

  3. (3)

Any iteration

$\left\\{j_{\alpha\beta}:\alpha\leq\beta\leq\gamma\right\\}$

of $M$ is well founded and such that $A\cap M_{\beta}=j_{\alpha\beta}(A\cap
M_{0})$ for all $\beta\leq\gamma$.

####  3.4.2. Proof of Theorem 3

###### Proof.

Let $\phi$ be a $\Pi_{1}$-sentence for
$\tau_{\mathbf{NS}_{\omega_{1}}}\cup\text{{\sf UB}}^{V}$ which holds in $V$.