# On the categoricity of complete second order theories††thanks: The first and
second author would like to thank the Academy of Finland, grant no: 322795.
This project has received funding from the European Research Council (ERC)
under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No 101020762).

Tapio Saarinen
University of Helsinki  Jouko Väänänen
University of Helsinki and
University of Amsterdam  Hugh Woodin
Harvard University

###### Abstract

We show, assuming PD, that every complete finitely axiomatized second order
theory with a countable model is categorical, but that there is, assuming
again PD, a complete recursively axiomatized second order theory with a
countable model which is non-categorical. We show that the existence of even
very large (e.g. supercompact) cardinals does not imply the categoricity of
all finite complete second order theories. More exactly, we show that a non-
categorical complete finitely axiomatized second order theory can always be
obtained by (set) forcing. We also show that the categoricity of all finite
complete second order theories with a model of a certain singular cardinality
$\kappa$ of uncountable cofinality can be forced over any model of set theory.
Previously, Solovay had proved, assuming $V=L$, that every complete finitely
axiomatized second order theory (with or without a countable model) is
categorical, and that in a generic extension of $L$ there is a complete
finitely axiomatized second order theory with a countable model which is non-
categorical.

##  1 Introduction

A second order theory $T$ is _complete_ if it decides, in the semantical
sense, every second order sentence $\phi$ in its own vocabulary i.e. if for
every such $\phi$ either $T\models\phi$ or $T\models\neg\phi$, or
equivalently, all models of $T$ are second order equivalent. The question we
investigate in this paper is whether every complete second order theory is
_categorical_ in the sense that all of its models are isomorphic. Already in
1928 Fraenkel [8] mentions this question as a question ‘calling for
clarification’. Carnap [6] claimed a positive answer, but his proof had an
error (see [5]).

For mere cardinality reasons there are always complete non-categorical second
order theories. One needs only consider models of the empty vocabulary. Since
there are only continuum many different second order theories, there must be
two such models of different cardinality with the same (_a fortiori_ complete)
second order theory.

Categoricity of complete second order theories would follow if all second
order equivalent models were isomorphic, which is not the case again for
cardinality reasons. However, if $V=L$, then _countable_ second order
equivalent models are isomorphic [1] and, moreover, every complete finitely
axiomatized second order theory is categorical [26]. But if a Cohen real is
added to a model of $V=L$, then there are countable non-isomorphic second
order equivalent models [1], and if $\aleph_{1}$ Cohen-reals are added to a
model of $V=L$, there is a complete finitely axiomatized second order theory
(with a countable model) which is non-categorical [26].

Fraïssé [9, 10] conjectured that countable second order equivalent ordinals
are equal. Marek [18, 19] showed that Fraïssé’s conjecture is true under the
assumption $V=L$, and false in a forcing extension obtained by collapsing an
inaccessible cardinal to $\omega_{1}$.

The ambitious goal in the area of this paper is to decide in a definitive way
the status of categoricity of complete second order theories. Since we are
dealing with a question that cannot be decided in ZFC alone, it is natural to
make an assumption such as PD, a consequence of the existence of large
cardinals (e.g. infinitely many Woodin cardinals). We offer a partial solution
to the full question by solving the case of second order theories with
countable models. We have also partial results about theories with uncountable
models. In particular, we show that a non-categorical complete finitely
axiomatized second order theory can always be obtained by (set) forcing. This
shows that large cardinal assumptions cannot imply, as $V=L$ does, the
categoricity of all complete finitely axiomatized second order theories.

_Notation:_ We recall the usual definition of the beth hierarchy:
$\beth_{0}=\omega$, $\beth_{\alpha+1}=2^{\beth_{\alpha}}$, and
$\beth_{\nu}=\sup_{\alpha<\nu}\beth_{\alpha}$ for limit $\nu$. An ordinal
$\alpha$ is called a _beth fixed point_ if $\alpha=\beth_{\alpha}$. If $\mu$
is a cardinal, we use $\mbox{Fn}(I,J,\mu)$ to denote the poset of partial
functions $I\to J$ of cardinality $<\mu$, ordered by $p\leq q\iff q\subseteq
p$. The trivial poset $\mbox{Fn}(\emptyset,\emptyset,1)$ is denoted
$(\\{0\\},=)$.

We denote the second order theory of a structure $M$ by
$\operatorname{Th}_{2}(M)$. A second order theory $T$ is complete if
$\operatorname{Th}_{2}(M)=\operatorname{Th}_{2}(N)$ for all $M,N\models T$,
and $T$ is categorical if $M\cong N$ for all $M,N\models T$. For second order
sentences $\phi,\psi$ we write $\phi\models\psi$ to mean $M\models\phi$
implies $M\models\psi$ for all $M$, and similarly $T\models T^{\prime}$ for
second order theories $T,T^{\prime}$, and we say $T$ axiomatizes $T^{\prime}$.
If $T$ is a finite (resp. recursive) set of sentences and $T\models
T^{\prime}$, we say $T^{\prime}$ is finitely (resp. recursively)
axiomatizable.

A cardinal $\lambda$ is second order characterizable if there is a second
order sentence $\phi$ in the empty vocabulary such that $N\models\phi$ if and
only if $\lvert N\rvert=\lambda$.

##  2 The case of $L[U]$

It is already known that if $V=L$, then every complete finitely axiomatized
second order theory is categorical [26]. We now show that this also holds if
$V=L[U]$, and we show there are complete recursively axiomatized second order
theories that are non-categorical (with very large models).

Assuming $V=L[U]$, we write $\kappa$ for the sole measurable cardinal, $U$ for
the unique normal measure on $\kappa$ and $<_{L[U]}$ for the canonical well-
order. By a $L[U]$-premouse we mean a structure $(L_{\alpha}[W],\in,W)$ where
$W$ is an $L_{\alpha}[W]$-ultrafilter on some $\gamma<\alpha$. Recall that a
premouse $(L_{\alpha}[W],\in,W)$ is iterable (under taking iterated
ultrapowers), i.e. that every iterate is well-founded, if and only if every
iterate in an iteration of any countable length is well-founded. Observe that
every iterate in an iteration of countable length has the same cardinality as
the original premouse, so the iterability of a premouse is expressible in
second order logic. See for example [12, chapter 20] for more details.

######  Theorem 1.

Assume $V=L[U]$. Every complete finitely axiomatized second order theory is
categorical.

###### Proof.

Suppose $\phi$ is a complete second order sentence in a vocabulary with a
single binary relation symbol $R$ (for simplicity). Note first that $\phi$ has
models in only one cardinality. If not, let $N$ be a model of $\phi$ of least
cardinality, and $M$ another model with $\lvert M\rvert>\lvert N\rvert$. Let
$\theta$ be the sentence

$\exists P\exists
R^{\prime}(\theta^{\prime}(P)\land\phi^{\prime}(P,R^{\prime}))$

where

  * •

$P$ is a unary predicate, not occurring in $\phi$, and $R^{\prime}$ is a
binary relation symbol not occurring in $\phi$.

  * •

$\phi^{\prime}(P,R^{\prime})$ is a modification of the sentence $\phi$, where
the first order quantifiers $\exists x\dots$ are relativised to $P$ as
$\exists x(P(x)\land{\dots})$, and each occurrence of $R$ is replaced by
$R^{\prime}$.

  * •

$\theta^{\prime}(P)$ says that the cardinality of $P$ is smaller than the
ambient domain of the model (for example, that there is no injective function
with range contained in $P$).

As $\phi$ is complete and $M\models\theta$ (by taking $(P,R^{\prime})$
isomorphic to $N$), also $N\models\theta$, so there is a model of $\phi$ of
cardinality smaller than that of $N$, which is a contradiction. Thus all
models of $\phi$ have the same cardinality.

Now let $M_{0}$ be the $<_{L[U]}$-least model of $\phi$. Suppose first that
$\lvert M_{0}\rvert>\kappa$: in this case we can mimic the categoricity
argument for $L$ as follows. Let $\theta$ be the sentence

$\exists E\exists u\exists m\exists P\exists
R^{\prime}(\theta^{\prime}(E,u)\land\phi^{\prime}(P,R^{\prime})\land\theta_{least}(E,u,m)\land\theta_{isom}(E,m,P,R^{\prime}))$

where

  * •

$E,R^{\prime}$ are binary predicate symbols, $P$ a unary predicate symbol and
$u,m$ are first order variables, none occurring in $\phi$ (the intuition is
that $E$ is $\in$, $u$ is a normal ultrafilter, $m$ is a structure in the
vocabulary of $\phi$, $P$ is the domain of $m$ and $R$ is the single binary
relation of $m$).

  * •

$\theta^{\prime}(E,u)$ states $E$ is well-founded and extensional (so that $E$
has a transitive collapse, and the domain of the model equipped with $E$ can
be thought of as a transitive set), and its collapse is a level of $L[u]$
having a normal measure $u$ as an element.

  * •

$\phi^{\prime}(P,R^{\prime})$ is (as before) a modification of the sentence
$\phi$ where each first order quantifier $\exists x\dots$ is relativised to
$P$ as $\exists x(P(x)\land\dots)$, and each occurrence of $R$ is replaced by
$R^{\prime}$.

  * •

$\theta_{least}(E,u,m)$ says $m<_{L[u]}m^{\prime}$ for any other
$m^{\prime}=(Q,S)$ also satisfying $\phi^{\prime}(Q,S)$ (using the formula
defining the canonical well-order of $L[u]$ with $u$ as a parameter).

  * •

$\theta_{isom}(E,m,P,R^{\prime})$ states that $m=(P,R^{\prime})$, and that
$(P,R^{\prime})$ is isomorphic to the ambient model (so there is an injection
$F$ with range $P$ such that $R(x,y)\leftrightarrow R^{\prime}(F(x),F(y))$ for
all $x,y$).

If $M\models\theta$ with witnesses $E$, $u$ and $m=(P,R^{\prime})$, and
$\pi\colon(M,E)\to(N,\in)$ is the transitive collapse, then $\pi(u)=U$ is the
unique normal measure $U$ on $\kappa$, $N=L_{\alpha}[U]$ for some $\alpha$ and
$\pi(m)$ is the $<_{L[U]}$-least model $M_{0}$ of $\phi$, so $M$ is isomorphic
to $M_{0}$.

Conversely, let $\alpha$ be least such that $M_{0}\in L_{\alpha}[U]$. Then
$\kappa<\alpha<\lvert M_{0}\rvert^{+}$ and $U\in L_{\alpha}[U]$, so we may
pick a bijection $\pi\colon M_{0}\to L_{\alpha}[U]$ and let $E$, $u$ and
$m=(P,R^{\prime})$ be the preimages of $\in$, $U$ and $M_{0}$ under $\pi$ to
witness $M_{0}\models\theta$.

Thus the above sentence $\theta$ is such that $M\models\theta$ if and only if
$M$ is isomorphic to the $<_{L[U]}$-least model of $\phi$. Now if
$M\models\phi$, also $M\models\theta$ by completeness of $\phi$, so $M$ is
isomorphic to $M_{0}$ and $\phi$ is categorical.

Suppose now that $\lvert M_{0}\rvert=\lambda<\kappa$. In this case we cannot
find a binary relation $E$ on $M_{0}$ and $u\in M_{0}$ such that $u$ is a
normal measure in the transitive collapse of $(M_{0},E)$, so we modify the
previously produced sentence $\theta$. This argument relies on a
straightforward modification of the $\Delta^{1}_{3}$ well-order of reals in
$L[U]$. We make the further assumption that the domain of $M_{0}$ is a
cardinal (and that $M_{0}$ is the $<_{L[U]}$-least among such models), and let
$\theta$ be the sentence

$\exists E\exists W\exists m\exists P\exists
R^{\prime}(\theta^{\prime}(E,W)\land\phi^{\prime}(E,P,R^{\prime})\land\theta_{least}(E,W,m)\land\theta_{isom}(E,m,P,R^{\prime}))$

where

  * •

$E,R^{\prime}$ are binary and $W,P$ unary predicate symbols, and $m$ a first
order variable, none occurring in $\phi$.

  * •

$\theta^{\prime}(E,W)$ states $E$ is well-founded and extensional, whose
transitive collapse is an iterable $L[U]$-premouse $(L_{\alpha}[W],\in,W)$ for
some $\alpha$, where $W$ is a $L[W]$-ultrafilter on some $\gamma$, where
$\gamma$ is an ordinal greater than the cardinality of the ambient model.

  * •

$\phi^{\prime}(E,P,R^{\prime})$ is the sentence $\phi^{\prime}(P,R^{\prime})$
from before, with the additional stipulation that the extent of the predicate
$P$ is a cardinal.

  * •

$\theta_{least}(E,W,m)$ says $m<_{L[W]}m^{\prime}$ for any other
$m^{\prime}=(Q,S)$ also satisfying $\phi^{\prime}(E,Q,S)$ (using the formula
defining the canonical well-order of $L[W]$ with $W$ as a predicate).

  * •

$\theta_{isom}(E,m,P,R^{\prime})$ remains unchanged from earlier.

We claim that $\theta$ is a sentence such that $M\models\theta$ if and only if
$M$ is isomorphic to the $<_{L[U]}$-least model of $\phi$ (among models whose
domain is a cardinal). So suppose $M\models\theta$ with witnesses $E,W$ and
$m=(P,R^{\prime})$, and let $\pi\colon(M,E,W)\to(N,\in,W^{\prime})$ be the
transitive collapse. Then $W^{\prime}=\pi^{\prime\prime}(W)$ is a
$N$-ultrafilter on some $\gamma>\lambda$ and $N=L_{\alpha}[W^{\prime}]$ for
some $\alpha>\gamma$, and $\pi(m)$ is the $<_{L[W^{\prime}]}$-least model of
$\phi$ in $L_{\alpha}[W^{\prime}]$, to which $M$ is isomorphic.

To see why $\pi(m)$ is $M_{0}$, let $j\colon L[U]\to L[F]$ and $k\colon
L_{\alpha}[W^{\prime}]\to L_{\delta}[F]$ be long enough iterations of $L[U]$
and $L_{\alpha}[W]$ respectively such that they become comparable. Then
$\operatorname{crit}(j)=\kappa>\lambda$ and
$\operatorname{crit}(k)=\gamma>\lambda$, so $j(M_{0})=M_{0}$ and
$k(\pi(m))=\pi(m)$. By elementarity, both $M_{0}$ and $\pi(m)$ are now the
$<_{L[F]}$-least model of $\phi$ among models whose domain is a cardinal, so
$\pi(m)=M_{0}$ and $M$ is isomorphic to $M_{0}$.

Conversely, to see $M_{0}\models\theta$ amounts to finding an appropriate
premouse $(L_{\alpha}[W],\in,W)$. Let $\delta$ be a large enough cardinal such
that $M_{0},U\in L_{\delta}[U]$, and that $(L_{\delta}[U],\in,U)$ is an
iterable premouse. Then let $N$ be the Skolem hull of $\lambda\cup\\{M_{0}\\}$
in $L_{\delta}[U]$ of cardinality $\lambda$, and let $\pi\colon(N,\in,U\cap
N)\to(L_{\alpha}[W],\in,W)$ be the transitive collapse. Now
$(L_{\alpha}[W],\in,W)$ is also an iterable premouse with $\lvert
L_{\alpha}[W]\rvert=\lambda$, $W$ is a $L_{\alpha}[W]$-ultrafilter on some
$\gamma=\pi(\kappa)>\lambda$, and $\pi(M_{0})=M_{0}$, so by elementarity
$M_{0}$ is the $<_{L[W]}$-least model of $\phi$ as required. So $\theta$ is a
sentence such that $M\models\theta$ if and only if $M$ is isomorphic to
$M_{0}$, implying as before that $\phi$ is categorical.

Finally, observe that the case $\lvert M_{0}\rvert=\kappa$ is impossible,
since the measurable cardinal $\kappa$ is $\Pi^{2}_{1}$-indescribable [11].
Thus $\phi$ is categorical. ∎

It turns out that finite axiomatizability is key for the preceding theorem.
For every second order characterizable cardinal $\lambda>\kappa$, we produce a
non-categorical recursively axiomatizable theory whose models have cardinality
$\lambda$.

######  Theorem 2.

Assume $V=L[U]$. Suppose $\kappa$ is measurable and $\lambda$ is second order
characterizable with $\lambda>\kappa$. Then there is a recursively
axiomatizable theory $T$ with $\kappa$ many non-isomorphic models of
cardinality $\lambda$.

###### Proof.

For $\alpha<\kappa$ let $M_{\alpha}=(\lambda+\alpha,<)$, so in a structure of
cardinality $\lambda$, $M_{\alpha}$ is straightforwardly definable from
$\alpha$ (as $\lambda$ is second order characterizable). These models have the
property that $M_{\alpha}\cong M_{\beta}$ implies $M_{\alpha}=M_{\beta}$.

For a second order sentence $\phi$ in vocabulary $(<)$, let

$S_{\phi}=\\{\alpha<\kappa:M_{\alpha}\models\phi\\},$

and let $T_{0}$ be the set of sentences $\phi$ such that $S_{\phi}\in U$. As
$U$ is an ultrafilter, $T_{0}$ is a complete theory (so for any $\phi$,
exactly one of $\phi\in T_{0}$ or $\lnot\phi\in T_{0}$ hold), and by the
$\sigma$-completeness of $U$ the intersection $X=\bigcap\\{S_{\phi}:\phi\in
T_{0}\\}\in U$ is nonempty. The set $X$ is such that for any $\alpha,\beta\in
X$, the structures $M_{\alpha}$, $M_{\beta}$ have the same second order theory
$T_{0}$, so it remains to see that the theory $T_{0}$ is recursively
axiomatizable.

For a second order sentence $\phi$ in vocabulary $(<)$, let $E$ be a binary
relation symbol and $u$ a first order variable, neither occurring in $\phi$,
and let $\phi^{+}$ be the second order sentence

$\exists E\exists u(\theta^{\prime}(E,u)\land(\exists x\in u)(\forall\alpha\in
x)"M_{\alpha}\models\phi")$

where $\theta^{\prime}(E,u)$ says $E$ is well-founded and extensional, and its
transitive collapse is a level of $L[u]$ containing $\lambda$ and having a
normal measure $u$ as an element. Note that $\phi^{+}$ is a sentence in the
empty vocabulary. Intuitively, $\phi^{+}$ states that $M_{\alpha}\models\phi$
for a $U$-big set of ordinals $\alpha<\kappa$, so for any structure $N$ with
$\lvert N\rvert=\lambda$ we have the equivalences

$\displaystyle N\models\phi^{+}$
$\displaystyle\iff\\{\alpha<\kappa:M_{\alpha}\models\phi\\}=S_{\phi}\in U$
$\displaystyle\iff M_{\alpha}\models\phi\text{ for some }\alpha\in X$
$\displaystyle\iff\phi\in T_{0}.$

The import of the vocabulary of $\phi^{+}$ being empty is that for a structure
$N$, the truth of $N\models\phi^{+}$ depends only on $\lvert N\rvert$, so we
get that for all structures $N$ with $\lvert N\rvert=\lambda$,

$N\models\phi^{+}\iff M_{\alpha}\models\phi^{+}\text{ for some }\alpha\in
X\iff\phi^{+}\in T_{0}$

so also $\phi\leftrightarrow\phi^{+}\in T_{0}$ for all second order sentences
$\phi$ in vocabulary $(<)$.

Now define the recursive set of sentences

$T=\\{\phi\leftrightarrow\phi^{+}:\phi\text{ is a second order sentence in
vocabulary }(<)\\}.$

Observe that any model $N$ of the theory $T$ has cardinality $\lambda$, since
taking $\theta_{\lambda}$ to be the second order characterization of
$\lambda$, we have $M_{\alpha}\models\theta_{\lambda}$ for all
$\alpha<\kappa$, so $N\models\theta_{\lambda}^{+}$ and thus
$N\models\theta_{\lambda}$ since
$\theta_{\lambda}^{+}\leftrightarrow\theta_{\lambda}\in T$.

To see $T$ axiomatizes $T_{0}$, suppose $N\models T$ so $\lvert
N\rvert=\lambda$, and that $\phi$ is a second order sentence in the vocabulary
$(<)$, so either $\phi\in T_{0}$ or $\lnot\phi\in T_{0}$. In the former case
we have $S_{\phi}\in U$ so $N\models\phi^{+}$, so $N\models\phi$, and in the
latter case we have $S_{\lnot\phi}\in U$ so $N\models\lnot\phi$. Thus
$\operatorname{Th}_{2}(N)=T_{0}$, so $T$ recursively axiomatizes $T_{0}$ as
desired. ∎

In conclusion, all complete finitely axiomatizable theories are categorical in
$L[U]$ as in $L$, and in $L[U]$ there are complete recursively axiomatizable
second order theories that are non-categorical (whereas this is still unknown
in $L$).

##  3 Countable models

We already remarked earlier that if $V=L$, then every complete finitely
axiomatized second order theory is categorical [26]. We now show that for
theories with a countable model this is a consequence of PD, and therefore a
consequence of large cardinals:

######  Theorem 3.

Assume PD. Every complete finitely axiomatized second order theory with a
countable model is categorical.

###### Proof.

Suppose $\phi$ is a complete second order sentence with a countable model.
Then by completeness all models of $\phi$ are countable. Suppose $\phi$ is on
the level $\Sigma^{1}_{n}$ of second order logic and its vocabulary is, for
simplicity, just one binary predicate symbol $P$. Let $R$ be the
$\Sigma^{1}_{n}$ (lightface) set of real numbers coding models of $\phi$. By
PD and its consequence, the Projective Uniformization Theorem [22, Theorem
6C5], there is a $\Sigma^{1}_{n+1}$ (even $\Sigma^{1}_{n}$ if $n$ is even)
element $r$ in $R$. Suppose $r$ codes the model $M$ of $\phi$. We show that
every model of $\phi$ is isomorphic to $M$. Suppose $N$ is a model of $\phi$.
Let $\theta$ be the following second order sentence:

$\begin{array}[]{l}\exists Q_{+}\exists
Q_{\times}(\theta_{1}(Q_{+},Q_{\times})\wedge\exists
A(\theta_{2}(Q_{+},Q_{\times},A)\wedge\\\ \exists
B(\theta_{3}(Q_{+},Q_{\times},A,B)\wedge\exists
F\theta_{4}(F,B)))),\end{array}$

where

  * •

$\theta_{1}(Q_{+},Q_{\times})$ is the standard second order characterization
of $({\mathbb{N}},+,\times)$.

  * •

$\theta_{2}(Q_{+},Q_{\times},A)$ says that the set $A$ satisfies the
$\Sigma^{1}_{n+1}$ definition of $r$ in terms of $Q_{+}$ and $Q_{\times}$.

  * •

$\theta_{3}(Q_{+},Q_{\times},A,B)$ says in a domain $N$ that $(N,B)$ is the
binary structure coded by $A$ in terms of $Q_{+}$ and $Q_{\times}$.

  * •

$\theta_{4}(F,B)$ is the second order sentence which says that $F$ is a
bijection and

$\forall x\forall y(P(x,y)\leftrightarrow B(F(x),F(y))).$

Thus, $\theta$ essentially says “I am isomorphic to the model coded by $r$.”
Trivially, $M\models\theta$. Recall that $M\models\phi$. Since $\phi$ is
complete, $\phi\models\theta$. Therefore our assumption $N\models\phi$ implies
$N\models\theta$ and therefore $N\cong M$. ∎

We make a few remarks about the proof. First, if $n=2$, then we can use the
Novikov-Kondo-Addison Uniformisation Theorem and PD is not needed. Thus we
obtain:

######  Corollary 4.

A complete $\Sigma^{1}_{2}$-sentence of second order logic with a countable
model is always categorical.

In fact, the categorical finite second order axiomatizations of structures
such as $({\mathbb{N}},+,\times)$, $({\mathbb{R}},+,\times,0,1)$ and
$({\mathbb{C}},+,\times,0,1)$ (any many other classical structures) are all on
the $\Pi^{1}_{1}$-level of second order logic.

Second, the above proof gives also the following more general result: Assume
$Det(\mathbf{\Delta}^{1}_{2n})$. Suppose $T$ is a recursively axiomatized
theory on the $\Sigma^{1}_{2n+2}$-level of second order logic, which is
complete for sentences on this level of second order logic. Then $T$ is
categorical.

An essential ingredient of the proof of Theorem 3 was the assumption that the
complete second order theory is finitely axiomatized. The following theorem
shows that “finitely” cannot be replaced by “recursively”.

######  Theorem 5.

Assume PD. There is a recursively axiomatized complete second order theory
with $2^{\omega}$ non-isomorphic countable models.

###### Proof.

For any $x\subseteq\omega$ let

$M_{x}=(V_{\omega}\cup\\{y\subseteq\omega:y\equiv_{T}x\\},\in),$

where $y\equiv_{T}x$ means the Turing-equivalence of $y$ and $x$. We denote
the second order theory of $M_{x}$ by $\operatorname{Th}_{2}(M_{x})$. By
construction, $x\equiv_{T}y$ implies
$\operatorname{Th}_{2}(M_{x})=\operatorname{Th}_{2}(M_{y})$. On the other
hand, if $x\not\equiv_{T}y$, then clearly $M_{x}\ncong M_{y}$. If $\phi$ is a
second order sentence, then ‘$M_{x}\models\phi$’ is a projective property of
$x$, closed under $\equiv_{T}$, and hence by Turing Determinacy for projective
sets [20] has a constant truth value on a cone of reals $x$. By intersecting
the cones we get a cone $C$ of reals $x$ on which
$\operatorname{Th}_{2}(M_{x})$ is constant. For any second order $\phi$ let
$\phi^{+}$ be the second order sentence

$``M_{y}\models\phi\mbox{ for a cone of $y$}"$

and $\hat{\phi}$ the sentence $\phi\leftrightarrow\phi^{+}$. Let us consider
the recursive second order theory $T$ consisting of $\hat{\phi}$, when $\phi$
ranges over second order sentences in the vocabulary of the structures
$M_{x}$. We may immediately conclude that $T$ is complete, for if a second
order sentence $\phi$ is given, then by the choice of $C$ either
$M_{x}\models\phi$ for $x\in C$ or $M_{x}\models\neg\phi$ for $x\in C$. In the
first case $\hat{\phi}\models\phi$ and in the second case
$\hat{\phi}\models\neg\phi$. Therefore, $T\models\phi$ or $T\models\neg\phi$.
There are a continuum of non Turing equivalent reals in the cone $C$. Hence
there are a continuum of non-isomorphic $M_{x}$ with $x\in C$. ∎

##  4 Models of cardinality $\aleph_{1}$

Next, we show that the $(*)$ axiom (see Definition 4.33 in [28]) has
categoricity consequences for theories with a model of cardinality
$\aleph_{1}$. Thus these consequences can also be derived from forcing axioms,
namely MM++ which implies the $(*)$ axiom (as shown in [4]). The following
theorem answers a question of Boban Veličković.

######  Theorem 6.

Assume $(*)$. Then there is a complete finitely axiomatizable second order
theory with $\omega_{2}\,(=2^{\omega_{1}})$ non-isomorphic models of
cardinality $\aleph_{1}$.

###### Proof.

The pertinent consequence of $(*)$ is the quasihomogeneity of the
nonstationary ideal on $\omega_{1}$ (see Section 5.8 in [28], particularly
Definition 5.100). We take “NS${}_{\omega_{1}}$ is quasihomogeneous” to be the
following statement: if $X\subseteq\operatorname{\mathcal{P}}(\omega_{1})$ is
ordinal definable from parameters in
${\mathbb{R}}\cup\\{$NS${}_{\omega_{1}}\\}$, and $X$ is closed under equality
modulo NS${}_{\omega_{1}}$, and $X$ contains one bistationary subset of
$\omega_{1}$, then $X$ contains every bistationary subset of $\omega_{1}$.

We focus on the $\omega_{1}$-like dense linear orders
$\Phi(S)=\eta+\sum_{\alpha<\omega_{1}}\eta_{\alpha}$, where

$\eta_{\alpha}=\begin{cases}\eta,&\alpha\notin S\\\ 1+\eta,&\alpha\in
S,\end{cases}$

$\eta$ is the order type of the rationals, and $S\subseteq\omega_{1}$ is
bistationary. These models have the property that
$\Phi(S)\cong\Phi(S^{\prime})$ if and only if $S\triangle S^{\prime}\in
NS_{\omega_{1}}$. For a second order sentence $\phi$ in vocabulary $(<)$, the
set

$X_{\phi}=\\{S\subseteq\omega_{1}:S\text{ bistationary},\Phi(S)\models\phi\\}$

is ordinal definable, and closed under equality modulo NS${}_{\omega_{1}}$, so
the quasihomogeneity of NS${}_{\omega_{1}}$ implies that $X_{\phi}$ contains
either every bistationary subset of $\omega_{1}$, or none of them.

This shows the models $\Phi(S)$ for bistationary $S\subseteq\omega_{1}$ all
have the same complete second order theory, which is thus non-categorical.
This theory is axiomatized by the second order sentence in vocabulary $(<)$
expressing “I am isomorphic to $\Phi(S)$ for some bistationary
$S\subseteq\omega_{1}$”, so it is finitely axiomatizable, as required. ∎

Some categoricity consequences of $(*)$ can already be derived from AD, the
axiom of determinacy. As the axiom $(*)$ states that
$L[\operatorname{\mathcal{P}}(\omega_{1})]$ is a homogeneous forcing extension
of a model of AD by a forcing that does not add reals, the categoricity
consequences of AD for theories with a model of cardinality $\leq\aleph_{1}$
also follow from $(*)$. (Of course, the existence of recursively axiomatized
non-categorical theories under $(*)$ is overshadowed by the existence of even
finitely axiomatized such theories.)

######  Theorem 7.

Assume AD. Then there is a complete recursively axiomatized second order
theory with at least $2^{\aleph_{0}}$ many models of cardinality $\aleph_{1}$.

###### Proof.

By Martin, AD implies $\omega_{1}\to(\omega_{1})^{\omega}$, and moreover the
homogeneous set given by $\omega_{1}\to(\omega_{1})^{\omega}$ can be taken to
be a club (see [14]). We may then intersect $\omega$ many homogeneous clubs
for $\omega$ many colorings to obtain
$\omega_{1}\to(\omega_{1})^{\omega}_{2^{\omega}}$, and the homogeneous subset
can still be taken to be a club.

We focus on models of the form $M_{X}=(\omega_{1},<,X)$ for
$X\in[\omega_{1}]^{\omega}$. The second order theory
$\operatorname{Th}_{2}(M_{X})$ in the vocabulary $(<,X)$ can be encoded by a
real $f(X)\in 2^{\omega}$ consisting of the Gödel numbers of the sentences
true in $M_{X}$. This gives a coloring $f\colon[\omega_{1}]^{\omega}\to
2^{\omega}$, so we find a homogeneous club subset $H_{0}\subseteq\omega_{1}$
such that $f(X)$ does not depend on $X\in[H_{0}]^{\omega}$. Hence the models
$M_{X}$ with $X\in[H_{0}]^{\omega}$ all have the same complete second order
theory $T_{0}$, which is thus non-categorical.

The theory $T_{0}$ is axiomatized by

$T=\\{\phi\leftrightarrow\phi^{+}:\phi\text{ is a second order sentence}\\}$

where for a given second order sentence $\phi$ in vocabulary $(<,X)$, the
sentence $\phi^{+}$ expresses “there exists a club $C\subseteq\omega_{1}$ such
that $M_{X}\models\phi$ for all $X\in[C]^{\omega}$”.

For a given second order sentence $\phi$, if $M_{X}\models\phi$ for each
$X\in[H_{0}]^{\omega}$, then $H_{0}$ serves to witness that $\phi^{+}$ holds,
so $T\models\phi$. Conversely, if $\phi^{+}$ holds, there is a club $C$ such
that $M_{X}\models\phi$ for every $X\in[C]^{\omega}$, and taking $X\in[C\cap
H_{0}]^{\omega}$ we see also that $M_{X}\models\phi$ for all
$X\in[H_{0}]^{\omega}$. Thus $T\models\phi$ for exactly those $\phi$ such that
$M_{X}\models\phi$ for all $X\in[H_{0}]^{\omega}$, so we see that $T$ is a
recursive axiomatization of the theory $T_{0}$ as desired. ∎

The same can be analogously derived from the $(*)$ axiom, as follows:

######  Corollary 8.

Assume $(*)$. Then there is a complete recursively axiomatized second order
theory with $\omega_{2}$ many models of cardinality $\aleph_{1}$.

###### Proof.

Recall $(*)$ states that
$L[\operatorname{\mathcal{P}}(\omega_{1})]=L({\mathbb{R}})^{{{\mathbb{P}}_{\text{max}}}}$
and AD holds in $L({\mathbb{R}})$. As ${{\mathbb{P}}_{\text{max}}}$ is
homogeneous and does not add reals under AD (see Lemmas 4.40 and 4.43 in
[28]), $\omega_{1}=\omega_{1}^{L({\mathbb{R}})}$ and
$[\omega_{1}]^{\omega}=([\omega_{1}]^{\omega})^{L({\mathbb{R}})}$.

We again look at models $M_{X}=(\omega_{1},<,X)$ for
$X\in[\omega_{1}]^{\omega}$, and working in $L({\mathbb{R}})$, define a
coloring $f\colon[\omega_{1}]^{\omega}\to 2^{\omega}$ by

$f(X)=r\quad\iff\quad
L({\mathbb{R}})\models{{\mathbb{P}}_{\text{max}}}\Vdash"\check{r}\text{ codes
}\operatorname{Th}_{2}(M_{\check{X}})".$

That $f$ is a well-defined total function relies on the homogeneity of
${{\mathbb{P}}_{\text{max}}}$. By ADL(R) we find a club $H_{0}\in
L({\mathbb{R}})$, $H_{0}\subseteq\omega_{1}$ homogeneous for $f$. Stepping out
of $L({\mathbb{R}})$, we see that the models $M_{X}$, $X\in[H_{0}]^{\omega}$
all have the same complete second order theory $T_{0}$ (in
$L({\mathbb{R}})^{{\mathbb{P}}_{\text{max}}}=L[\operatorname{\mathcal{P}}(\omega_{1})]$
and in $V$ both).

Working now in $V$, we again define

$T=\\{\phi\leftrightarrow\phi^{+}:\phi\text{ is a second order sentence}\\}$

where for a given second order sentence $\phi$, the sentence $\phi^{+}$
expresses “there exists a club $C\subseteq\omega_{1}$ such that
$M_{X}\models\phi$ for all $X\in[C]^{\omega}$”. The proof concludes
analogously to the preceding theorem.

We note that $(*)$ calculates $\lvert\omega_{1}^{\omega}\rvert$ to be
$\omega_{2}$, so $T_{0}$ has $\omega_{2}$ many non-isomorphic models as
claimed. ∎

Of course, we may also use the fact that the club filter on $\omega_{1}$ is an
ultrafilter under AD to get another complete recursively axiomatized non-
categorical second order theory, the difference being that this theory has
$\omega_{1}$ many models instead. The proof, analogous to the proof of Theorem
2, is omitted:

######  Theorem 9.

Assume AD. Then there is a complete recursively axiomatized second order
theory with $\omega_{1}$ many models of cardinality $\aleph_{1}$. ∎

This proof is also easily modified to assume $(*)$ instead:

######  Corollary 10.

Assume $(*)$. Then there is a complete recursively axiomatized second order
theory with $\omega_{1}$ many models of cardinality $\aleph_{1}$. ∎

Thus, under $(*)$, a complete non-categorical theory with a model of
cardinality $\aleph_{1}$ may have either $\omega_{1}$ or $\omega_{2}$ many
non-isomorphic models.

##  5 Forcing non-categoricity

We shall show (Theorem 14) that we can force, over any model of set theory, a
finite complete non-categorical second order theory with a model of
cardinality $\aleph_{1}$. This shows that large cardinals cannot imply the
categoricity of finite complete second order theories in general and, in
particular, in the case that the theory has a model of cardinality
$\aleph_{1}$. This is in contrast to finite complete second order theories
with a countable model where PD implies categoricity (Theorem 3).

Here is an outline of the proof. We start with a preparatory countably closed
forcing ${\mathbb{P}}$ obtaining a generic extension $V[G]$. Then we add
$\aleph_{1}$ Cohen-reals obtaining a further generic extension $V[G][H]$. In
this model we consider for every $x\subseteq\omega$ the model

$M_{x}=(HC^{V[x]},HC^{V},\in).$ (1)

We show that if $x$ is Cohen-generic over $V[G]$, then the complete second
order theory of $M_{x}$ is finitely axiomatizable (in second order logic), and
if $x$ and $y$ are mutually Cohen-generic over $V[G]$, then $M_{x}$ and
$M_{y}$ are second order equivalent but non-isomorphic.

We begin by recalling the following _fast club_ forcing
${\mathbb{P}}_{\mbox{\scriptsize fast}}$, due to R. Jensen: Conditions are
pairs $p=(c_{p},E_{p})$ where $c_{p}$ is a countable closed subset of
$\omega_{1}$ and $C_{p}$ is club in $\omega_{1}$. We define
$(c_{p},E_{p})\leq(c_{q},E_{q})$ if $c_{q}$ is an initial segment of $c_{p}$,
$E_{q}\subseteq E_{p}$, and $c_{p}\setminus c_{q}\subseteq E_{q}$. This
forcing is countably closed. If we assume CH, this forcing has the
$\aleph_{2}$-c.c. It is called fast club forcing because of the following
property: Suppose $G$ is ${\mathbb{P}}_{{\mbox{\scriptsize fast}}}$-generic.
If $C_{G}$ is the union of the sets $c_{p}$ such that $p\in G$, then the
following holds: If $D$ is any club in $V$, then there is $\alpha$ such that
$C_{G}\setminus\alpha\subseteq D$. The set $C_{G}$ is called a _fast club_
(over $V$).

Let ${\mathbb{Q}}$ be the poset $\mbox{Fn}(\omega_{1}\times\omega,2,\omega)$
for adding $\aleph_{1}$ Cohen reals. We use fast club forcing to build a
preparatory iterated forcing in such a way that after forcing with
${\mathbb{Q}}$ the ground model reals are second order definable from any set
$A\subseteq\omega_{1}$ with a certain second order property. The following
lemma is crucial in the iteration:

######  Lemma 11.

Suppose $G\times H$ is ${\mathbb{P}}_{\mbox{\scriptsize
fast}}\times{\mathbb{Q}}$-generic over $V$. Suppose $A\subseteq\omega_{1}$ is
in $V[H]$ and $D\subseteq C_{G}$ is a club in $V[G\times H]$ such that
$V[G\times H]$ satisfies $\forall\alpha<\omega_{1}(D\cap\alpha\in L[A])$. Then
${\mathcal{P}}(\omega)^{V}\subseteq L[A]$.

###### Proof.

We modify a construction from the proof of [30, Lemma 4.33] to our context.
Let us call a pair $(A,B)$ of sets of ordinals an _interlace_ , if $A\cap
B=\emptyset$, above every element of $A$ there is an element of $B$, and vice
versa. Suppose we have disjoint sets $X,Y,Z\subseteq\omega_{1}$ such that
$(X\cup Y,Z)$ is an interlace. Let $z\sim z^{\prime}$ in $Z$ if
$(z,z^{\prime})\cap(X\cup Y)=\emptyset$. Let $[z_{n}]$, $n<\omega$, be the
first $\omega$ $\sim$-equivalence classes in $Z$ in increasing order. The
triple $(X,Y,Z)$ is said to _code_ the set $a\subseteq\omega$ if for all
$n<\omega$:

$n\in a\iff\min\\{\alpha\in X\cup Y:[z_{n}]<\alpha<[z_{n+1}]\\}\in X.$

It suffices to prove that for every $a\subseteq\omega$ in $V$ there is a
triple $(X,Y,Z)\in L[A]$ such that $(X\cup Y,Z)$ is an interlace, and
$(X,Y,Z)$ codes $a$. To this end, suppose $a\in{\mathcal{P}}(\omega)^{V}$.

Suppose $\dot{A}$ is a ${\mathbb{Q}}$-name for $A$ in $V$, $\tau\in V$ is a
${\mathbb{P}}_{\mbox{\scriptsize fast}}$-name for a ${\mathbb{Q}}$-name
$\dot{D}$ for $D$, and $\dot{F}$ a ${\mathbb{Q}}$-name for a function
$\omega_{1}\to\omega_{1}$ which lists the elements of $\dot{D}$ in increasing
order. W.l.o.g. $\tau$ is a ${\mathbb{P}}_{\mbox{\scriptsize fast}}$-name
$\langle\dot{f}_{\alpha}:\alpha<\omega_{1}\rangle$ for a sequence of countable
partial functions defined on $\omega_{1}$ such that
$\\{\dot{f}_{\alpha}(\gamma):\gamma\in\mbox{dom}(f_{\alpha})\\}$ is a maximal
antichain in ${\mathbb{Q}}$ and $\dot{f}_{\alpha}(\gamma)$ forces
$\dot{F}(\alpha)=\gamma$. Suppose (w.l.o.g.) the weakest condition in
${\mathbb{P}}_{\mbox{\scriptsize fast}}\times{\mathbb{Q}}$ forces what is
assumed about $\dot{A}$, $\dot{F}$, $\tau$ and $\dot{D}$. Since
${\mathbb{P}}_{\mbox{\scriptsize
fast}}\Vdash``{\mathbb{Q}}\Vdash\dot{D}\subseteq C_{\dot{G}}"$, we have
$\Vdash\mbox{dom}(\dot{f}_{\alpha})\subseteq C_{\dot{G}}$. More generally, if
$p\in{\mathbb{P}}_{\mbox{\scriptsize fast}}$ decides the countable set
$\mbox{dom}(\dot{f}_{\alpha})$, then

$p\Vdash\mbox{dom}(\dot{f}_{\alpha})\subseteq c_{p}\setminus\alpha.$ (2)

If $\delta<\omega_{2}$, let $W_{\delta}$ be the set of conditions
$p\in{\mathbb{P}}_{\mbox{\scriptsize fast}}$ such that $p$ decides
$\mbox{dom}(\dot{f}_{\delta})$. It is easy to see that $W_{\delta}$ is dense.

We construct descending $\omega$-sequences $(p_{n}),(q_{n})$ and $(r_{n})$ in
${\mathbb{P}}_{\mbox{\scriptsize fast}}$ as follows. We let
$p_{0}=q_{0}=r_{0}$ be the weakest condition in
${\mathbb{P}}_{\mbox{\scriptsize fast}}$. Suppose $p_{n},q_{n}$ and $r_{n}$
have been defined already. Let $\delta_{n}=\max(c_{r_{n}}\cup{\\{0\\}})$. Now
there are two cases:

  1. 1.

Case $n\in a$:

    1. (a)

Let $p_{n+1}\leq p_{n}$ such that $\min(c_{p_{n+1}}\setminus
c_{p_{n}})>\delta_{n}$ and $p_{n+1}\in W_{\delta_{n}}$.

    2. (b)

Let $q_{n+1}\leq q_{n}$ such that $\min(c_{q_{n+1}}\setminus
c_{q_{n}})>\max(c_{p_{n+1}})$ and $q_{n+1}\in W_{\delta_{n}}$.

    3. (c)

Let $r_{n+1}\leq r_{n}$ such that $\min(c_{r_{n+1}}\setminus
c_{r_{n}})>\max(c_{q_{n+1}})$ and $q_{n+1}\in W_{\delta_{n}}$.

  2. 2.

Case $n\notin a$:

    1. (a)

Let $q_{n+1}\leq q_{n}$ such that $\min(c_{q_{n+1}}\setminus
c_{q_{n}})>\delta_{n}$ and $q_{n+1}\in W_{\delta_{n}}$.

    2. (b)

Let $p_{n+1}\leq p_{n}$ such that $\min(c_{p_{n+1}}\setminus
c_{p_{n}})>\max(c_{q_{n+1}})$ and $p_{n+1}\in W_{\delta_{n}}$.

    3. (c)

Let $r_{n+1}\leq r_{n}$ such that $\min(c_{r_{n+1}}\setminus
c_{r_{n}})>\max(c_{p_{n+1}})$ and $r_{n+1}\in W_{\delta_{n}}$.

Note that if $\delta_{n}<\alpha<\min(c_{p_{n+1}}\setminus c_{p_{n}})$, then
$p_{n+1}\Vdash\alpha\notin C_{\dot{G}}$, whence
$p_{n+1}\Vdash\alpha\notin\tau$. Respectively, if
$\delta_{n}<\alpha<\min(c_{q_{n+1}}\setminus c_{q_{n}})$, then
$q_{n+1}\Vdash\alpha\notin C_{\dot{G}}$, whence
$q_{n+1}\Vdash\alpha\notin\tau$, and if
$\delta_{n}<\alpha<\min(c_{r_{n+1}}\setminus c_{r_{n}})$, then
$r_{n+1}\Vdash\alpha\notin C_{\dot{G}}$, whence
$r_{n+1}\Vdash\alpha\notin\tau$.

Similarly, if $\max(c_{p_{n+1}})<\alpha<\delta_{n+1}$, then
$p_{n+2}\Vdash\alpha\notin C_{\dot{G}}$, whence
$p_{n+2}\Vdash\alpha\notin\tau$. Respectively, if
$\max(c_{q_{n+1}})<\alpha<\delta_{n+1}$, then $q_{n+2}\Vdash\alpha\notin
C_{\dot{G}}$, whence $q_{n+2}\Vdash\alpha\notin\tau$.

Finally, if $\alpha\in I=[\min(c_{p_{n+1}}),\max(c_{p_{n+1}})]$, then
$p_{n+1}$ may leave the sentence $\alpha\in\tau$ undecided, but still
$p_{n+1}\Vdash I\cap\tau\neq\emptyset$, since $p_{n+1}$ decides
$\mbox{dom}(\dot{f_{\delta_{n}}})$ and we have (2). Respectively, $q_{n+1}$
forces $[\min(c_{q_{n+1}}),\max(c_{q_{n+1}})]\cap\tau\neq\emptyset$, and
$r_{n+1}$ forces $[\min(c_{r_{n+1}}),\max(c_{r_{n+1}})]\cap\tau\neq\emptyset$.

Let
$p_{\omega}=\inf_{n}p_{n},q_{\omega}=\inf_{n}q_{n},r_{\omega}=\inf_{n}r_{n}$,
and let $\delta=\sup\\{\delta_{n}:n<\omega\\}$. Let
$G_{0}\subseteq{\mathbb{P}}_{\mbox{\scriptsize fast}}$ be generic over $V[H]$
such that $p_{\omega}\in G_{0}$,
$G_{1}\subseteq{\mathbb{P}}_{\mbox{\scriptsize fast}}$ generic over $V[H]$
such that $q_{\omega}\in G_{1}$, and
$G_{2}\subseteq{\mathbb{P}}_{\mbox{\scriptsize fast}}$ generic over $V[H]$
such that $r_{\omega}\in G_{2}$. Lastly, let

$X=\tau_{G_{0}\times H}\cap\delta,\ Y=\tau_{G_{1}\times H}\cap\delta,\
Z=\tau_{G_{2}\times H}\cap\delta.$

As $\Vdash_{{\mathbb{P}}_{\mbox{\scriptsize
fast}}\times{\mathbb{Q}}}\tau\cap\delta\in L[\dot{A}]$ and
$\dot{A}_{G_{0}\times H}=\dot{A}_{H}$, we have $V[G_{0}\times H]\models X\in
L[A]$. By absoluteness, $V[H]\models X\in L[A]$. Similarly, $V[H]\models
Y,Z\in L[A]$.

Now by construction, $(X\cup Y,Z)$ is an interlace and $(X,Y,Z)$ codes $a$.
Hence $a\in L[A]$.

∎

We need another auxiliary lemma for the iteration:

######  Lemma 12.

Assume $G$ is ${\mathbb{P}}_{\mbox{\scriptsize fast}}$-generic over $V$,
${\mathbb{R}}\in V[G]$ is a $\sigma$-closed forcing, $K$ is
${\mathbb{R}}$-generic over $V[G]$, $H$ is ${\mathbb{Q}}$-generic over
$V[G][K]$, $A\subseteq\omega_{1}$ is in $V[H]$, and in $V[G][K][H]$, there is
a club $D\subseteq C_{G}$ such that $D\cap\alpha\in L[A]$ for all
$\alpha<\omega_{1}$. Then such a club $D$ must already exist in $V[G][H]$.

###### Proof.

Suppose $\dot{A}\in V$ is a ${\mathbb{Q}}$-name for $A$ and $\dot{D}\in V[G]$
is an ${\mathbb{R}}$-name for a ${\mathbb{Q}}$-name for $D$. Suppose
$\dot{F}\in V[G]$ is an ${\mathbb{R}}$-name for a ${\mathbb{Q}}$-name for a
function $\omega_{1}\to\omega_{1}$ listing the elements of $\dot{D}$ in
increasing order. W.l.o.g. $\dot{D}$ is a ${\mathbb{R}}$-name
$\langle\dot{f}_{\alpha}:\alpha<\omega_{1}\rangle$ for a sequence of countable
partial functions defined on $\omega_{1}$ such that
$\\{\dot{f}_{\alpha}(\gamma):\gamma\in\mbox{dom}(f_{\alpha})\\}$ is a maximal
antichain in ${\mathbb{Q}}$ and $\dot{f}_{\alpha}(\gamma)$ forces
$\dot{F}(\alpha)=\gamma$. Suppose (w.l.o.g.) the weakest condition in
${\mathbb{R}}\times{\mathbb{Q}}$ forces what is assumed about $\dot{A}$,
$\dot{F}$, and $\dot{D}$. Since $\Vdash\dot{D}\subseteq C_{\dot{G}}$, we have
$\Vdash\mbox{dom}(\dot{f}_{\alpha})\subseteq C_{\dot{G}}$.

We shall define a descending sequence $(r_{\alpha})_{\alpha<\omega_{1}}$ in
$K$. For a start, $r_{0}\in K$ can be arbitrary. Suppose $r_{\alpha}\in K$ has
been defined already. Let $r_{\alpha+1}\leq r_{\alpha}$ such that
$r_{\alpha+1}\in K$ and $r_{\alpha+1}$ decides $\mbox{dom}(\dot{f}_{\beta})$
and $\dot{f}_{\alpha}(\gamma)$ for $\beta\leq\alpha$ and
$\gamma\in\mbox{dom}(\dot{f}_{\alpha})$. Let $g_{\alpha}\in V[G]$ such that
$r_{\alpha+1}\Vdash\dot{f}_{\alpha}=g_{\alpha}$. Let $\dot{S}$ be a
${\mathbb{Q}}$-name in $V$ for a function $\omega_{1}\to\omega_{1}$ such that
$g_{\alpha}(\gamma)\Vdash\dot{S}(\alpha)=\gamma$. Let $\dot{E}\in V$ be a
${\mathbb{Q}}$-name such that
$\Vdash\dot{E}=\\{\dot{S}(\alpha):\alpha<\omega_{1}\\}$. Now

$V[K][H]\models\dot{E}_{H}=\dot{D}_{K\times H}\ \wedge\
\dot{E}_{H}\cap\delta\in L[A],$

whence $V[H]\models\dot{E}_{H}\cap\delta\in L[A]$ follows by absoluteness. ∎

Now we can construct the iteration in such a way that after forcing with the
iteration and then with ${\mathbb{Q}}$ the ground model reals, which are the
same as the reals after the iteration, are second order definable from any set
$A\subseteq\omega_{1}$ with a certain second order property.

######  Lemma 13.

We assume CH. Suppose ${\mathbb{P}}$ is the countable support iteration of
fast club forcing of length $\omega_{2}$. Let $G$ be ${\mathbb{P}}$-generic
over $V$. Suppose $H$ is ${\mathbb{Q}}$-generic over $V[G]$. Suppose in
$V[G][H]$ there is a set $A\subseteq\omega_{1}$ such that for every club $C$,
there is a club $D\subseteq C$ such that $D\cap\alpha\in L[A]$ for all
$\alpha<\omega_{1}$. Then $P(\omega)^{V}\subseteq L[A]$.

###### Proof.

Let ${\mathbb{P}}=\langle{\mathbb{P}}_{\alpha}:\alpha<\omega_{2}\rangle$ be
the countable support iteration of
$\langle\dot{Q}_{\alpha}:\alpha<\omega_{2}\rangle$, where
${\mathbb{P}}_{\alpha}\Vdash``\dot{Q}_{\alpha}\mbox{ is the fast club}$
forcing ${\mathbb{P}}_{{\mbox{\scriptsize fast}}}$”. Let
$G_{\alpha}=G\cap{\mathbb{P}}_{\alpha}$. Let $\dot{A}\in V[G]$ be an $H$-name
for $A$. Choose $\beta$ large enough such that $\dot{A}\in V[\langle
G_{\alpha}:\alpha<\beta\rangle].$ Now $G_{\beta}$ is
${\mathbb{P}}_{\mbox{\scriptsize fast}}$-generic over $V[\langle
G_{\alpha}:\alpha<\beta\rangle]$. But, $V[G]$ is a generic extension of
$V[\langle G_{\alpha}:\alpha<\beta\rangle][G_{\beta}]$ by countably closed
forcing and by assumption, in $V[G][H]$, there is a club $D\subseteq
C_{G_{\beta}}$ such that $D\cap\eta\in L[A]$ for all $\eta<\omega_{1}$. We
apply Lemma 12 in $V[\langle G_{\alpha}:\alpha<\beta\rangle]$ and conclude
that there is a club $D\subseteq C_{G_{\beta}}$ in $V[\langle
G_{\alpha}:\alpha<\beta\rangle][G_{\beta}][H]$ such that $D\cap\alpha\in L[A]$
for all $\alpha<\omega_{1}$. By Lemma 11, $P(\omega)^{V}\subseteq L[A]$. ∎

######  Theorem 14.

There is a set of forcing conditions that forces the existence of a complete
non-categorical finite second order theory with a model of cardinality
$\aleph_{1}$.

###### Proof.

Assume w.l.o.g., CH. As said above, we start with some preparatory countably
closed forcing ${\mathbb{P}}$ obtaining a generic extension $V[G]$. Then we
add $\aleph_{1}$ Cohen-reals obtaining a further generic extension $V[G][H]$.
In this model we consider for every $x\subseteq\omega$ the model $M_{x}$ as
defined in (1). Clearly, the cardinality of $M_{x}$ is $\aleph_{1}$. We shall
now show that if $x$ is Cohen-generic over $V[G]$, e.g. one of the
$\aleph_{1}$ many coded by $H$, then the complete second order theory of
$M_{x}$ is finitely axiomatizable (in second order logic). To end the proof of
the theorem, we show that if $x$ and $y$ are mutually Cohen-generic over
$V[G]$, then $M_{x}$ and $M_{y}$ are second order equivalent but non-
isomorphic.

In order to use second order logic over $\omega_{1}$ to talk about $HC^{V}$
and Cohen-genericity over $V$ we need to be able to decide, by the means
offered by second order logic, which reals in $V[G][H]$ are in $V$ (or,
equivalently, in $V[G]$) and which are not. This is precisely the purpose of
the preparatory forcing ${\mathbb{P}}$.

We denote the starting ground model by $V$ and assume, w.l.o.g., that $V$
satisfies CH. We let the preparatory forcing
${\mathbb{P}}=\langle{\mathbb{P}}_{\alpha}:\alpha<\omega_{2}\rangle$ be the
countable support iteration of
$\langle\dot{Q}_{\alpha}:\alpha<\omega_{2}\rangle$, where
${\mathbb{P}}_{\alpha}\Vdash``\dot{Q}_{\alpha}\mbox{ is the fast club}$
forcing ${\mathbb{P}}_{{\mbox{\scriptsize fast}}}$”. Let $G$ be
${\mathbb{P}}$-generic over $V$ and $G_{\alpha}=G\cap{\mathbb{P}}_{\alpha}$.
In $V[G]$ we force with ${\mathbb{Q}}$ a generic $H$. Note that
$\aleph_{1}^{V[G][H]}=\aleph_{1}^{V}$ and
${\mathcal{P}}(\omega)^{V[G]}={\mathcal{P}}(\omega)^{V}$. Working in
$V[G][H]$, let the second order sentence $\phi(R,E)$, where $R$ is unary and
$E$ is binary, say in a model $M$:

  1. (1)

$E^{M}$ is a well-founded relation satisfying $ZFC^{-}$ $+$ “every set is
countable”. This should be also true when relativized to $R^{M}$.

  2. (2)

$|M|=\aleph_{1}$.

  3. (3)

If $P^{\prime}\in R^{M}$ denotes (in $M$) the set $\mbox{Fn}(\omega,2,\omega)$
of conditions for adding one Cohen real, then there is $K\subseteq P^{\prime}$
such that $K$ is $P^{\prime}$-generic over $R^{M}$ and $M\models``V=R[K]"$.

  4. (4)

If $a\subseteq\omega$ and the transitive collapse of $M$ is $N$, then the
following conditions are equivalent:

    1. (a)

$a\in R^{N}$.

    2. (b)

If $A\subseteq\omega_{1}$ and for every club $C\subseteq\omega_{1}$ there is a
club $D\subseteq C$ such that $D\cap\alpha\in L[A]$ for every
$\alpha<\omega_{1},$ then $a\in L[A]$.

Note that we can express $``D\cap\alpha\in L[A]"$, or equivalently
$``\exists\beta(|\beta|=\aleph_{1}\wedge D\cap\alpha\in L_{\beta}[A]"$, in
second order logic on $M$ since second order logic gives us access to all
structures of cardinality $|M|$ (=$\aleph_{1}$).

Claim: The following conditions are equivalent in $V[G][H]$:

  1. (i)

$M\models\phi(R,E)$.

  2. (ii)

$M\cong M_{x}$ for some real $x$ which is Cohen generic over $V$.

###### Proof.

(i) implies (ii): Suppose $M\models\phi(R,E)$. Let $(N,U,\in)$ be the
transitive collapse of $(M,R^{M},E^{M})$. By (3), there is $r$ which is Cohen-
generic over $U$ and $N=HC^{U[r]}$. We show that $U=HC^{V}$. Suppose
$a\in{\mathcal{P}}(\omega)^{V}$. We use condition (4) to demonstrate that
$a\in U$. To this end, let $A$ be as in (4b). By Lemma 13, $a\in L[A]$. Thus
(4) implies $a\in U$. On the other hand, suppose
$a\in({\mathcal{P}}(\omega))^{U}$. We again use (4) to show that
$a\in{\mathcal{P}}(\omega)^{V}$. Let $A\subseteq\omega_{1}$ code
$([\omega_{1}]^{\omega})^{V}$. If $C$ is any club in $V[G][H]$, then, since
$H$ is obtained by means of a CCC forcing, there is a club $D\subseteq C$ in
$V[G]$. Now $D\cap\alpha\in V$, whence $D\cap\alpha\in L[A]$, for all
$\alpha<\omega_{1}$. It follows that $a\in L[A]$. Since $A\in V$, we may
conclude $a\in{\mathcal{P}}(\omega)^{V}$. Hence, $U=HC^{V}$ and $r$ is Cohen-
generic over $V$. We have proved (ii).

(ii) implies (i): Suppose $(N,R^{N},E^{N})=(HC^{V[r]},HC^{V},\in)$, where $r$
is $\mbox{Fn}(\omega,2,\omega)$-generic over $V$. We show that
$(N,R^{N},E^{N})\models\phi(R,E)$. Conditions (1) and (2) are trivially
satisfied. Condition (3) holds by construction. To prove that condition (4)
holds, suppose $a\subseteq\omega$ and let $A$ be as in (4). By Lemma 13, $a\in
L[A]$. Condition (4) and thereby the Claim is proved. ∎

We continue the proof of Theorem 14. The sentence $\phi(R,E)$ is non-
categorical in $V[G][H]$ because if we take two mutually generic (over $V[G]$)
Cohen reals $r_{0}$ and $r_{1}$, then $M_{r_{0}}$ and $M_{r_{1}}$ are non-
isomorphic models of $\phi(R,E)$. To prove that $\phi(R,E)$ is complete,
suppose $(M,R^{M},E^{M})$ and $(N,R^{N},E^{N})$ are two models of $\phi(R,E)$.
W.l.o.g., they are of the form $(M,R^{M},\in)$ and $(N,R^{N},\in)$, where $M$
and $N$ are transitive sets. By construction, they are of the form $M_{r_{0}}$
and $M_{r_{1}}$ where both $r_{0}$ and $r_{1}$ are Cohen generic over
$HC^{V}$, hence over $HC^{V[G]}$. They are subsumed by the generic $H$. By
homogeneity of Cohen forcing $\mbox{Fn}(\omega,2,\omega)$ the models are
second order equivalent. ∎

In fact the forcing gives something stronger. If $\kappa$ is a cardinal that
is second order characterizable in the forcing extension, we may replace the
model $M_{x}=(HC^{V[x]},HC^{V},\in)$, where $x\subseteq\omega$ is Cohen over
$V$, with the model $(\kappa\cup HC^{V[x]},HC^{V},\in)$, and the proof of
Theorem 14 goes through mutatis mutandis:

######  Corollary 15.

There is a set of forcing conditions that forces the following: if $\kappa$ is
any second order characterizable cardinal, there is a complete non-categorical
finitely axiomatizable second order theory with a model of cardinality
$\kappa$. ∎

Since the non-isomorphic models above derive from mutually generic Cohen
reals, it follows that the non-categorical theories in question have (at most)
continuum many non-isomorphic models. We lastly mention how to get non-
categorical theories with more models than this.

It is straightforward to see that in theorem 14 and the constructions
preceding it, the cardinal $\aleph_{1}$ may be replaced with any cardinal
$\mu^{+}$ with $\mu$ regular. That is, the $\omega_{2}$-length countable
support iteration of fast club forcing at $\omega_{1}$ is replaced by a
$\mu^{++}$-length $\leq\mu$-sized support iteration of fast club forcing at
$\mu^{+}$, and the forcing to add $\aleph_{1}$ many Cohen subsets of $\omega$
is replaced by adding $\mu^{+}$ many Cohen subsets of $\mu$. The model $M_{x}$
is then taken to be of the form $(H(\mu)^{V[x]},H(\mu)^{V},\in)$ where $x$ is
a Cohen subset of $\mu$ generic over $V$.

From this variation, we then get the following corollary.

######  Corollary 16.

Suppose $\mu$ is a regular cardinal. There is then a set of forcing conditions
that forces the following: if $\mu$ is second order characterizable, and if
$\kappa\geq\mu$ is any second order characterizable cardinal, there is a
complete non-categorical finite second order theory $T$ with a model of
cardinality $\kappa$. Also, the theory $T$ has between $\mu^{+}$ and $2^{\mu}$
many models up to isomorphism.

Note that the concern of the second order characterizability of $\mu$ and
$\kappa$ in the forcing extension are irrelevant for cardinals with simple
definitions such as $\aleph_{n}$, $n<\omega$ or $\aleph_{\omega_{1}+1}$, for
example.

In conclusion we cannot hope to prove the categoricity of finite complete
second order theories from large cardinals even if we restrict to theories
which have a model of regular uncountable cardinality.

##  6 Forcing categoricity

In [2] (for $\kappa>\omega_{1}$) and [3] (for $\kappa=\omega_{1}$), Aspero and
Friedman proved the following:

######  Theorem 17.

Suppose $\kappa$ is the successor of a regular cardinal, and uncountable. Then
there is a poset ${\mathbb{P}}$ such that in a generic extension by
${\mathbb{P}}$, there is a lightface first order definable well-order of
$H(\kappa^{+})$.

Since we can translate a first order lightface definable well-order of
$H(\kappa^{+})$ into a well-order of $\operatorname{\mathcal{P}}(\kappa)$ that
is second order definable over any structure of cardinality $\kappa$, we
obtain the following corollary.

######  Theorem 18.

Suppose $\kappa$ is the successor of a regular cardinal, uncountable, and that
$\kappa$ is second order characterizable. Then there is a poset ${\mathbb{P}}$
that forces the following: every finitely axiomatizable second order theory
with a model of cardinality $\kappa$ is categorical. ∎

We are thus left to consider the case of theories with models of limit
cardinality, whether regular or singular.

The following theorem shows that the categoricity of complete second order
theories with a model of singular cardinality is (relatively) consistent with
large cardinals. We are indebted to Boban Veličković for suggesting how to
improve an earlier weaker version of this result.

######  Theorem 19.

Suppose $\kappa$ is a singular strong limit with uncountable cofinality
$\lambda$. Then there is a forcing notion ${\mathbb{P}}$ of cardinality
$\kappa$ such that

  1. 1.

${\mathbb{P}}$ preserves $\kappa$ singular strong limit of uncountable
cofinality $\lambda$.

  2. 2.

${\mathbb{P}}$ forces the statement: Every finitely axiomatizable complete
second order theory with a model of cardinality $\kappa$ is categorical.

###### Proof.

W.l.o.g. we assume GCH up to $\kappa$. We first force a second order definable
well-order of the bounded subsets of $\kappa$ with a reverse Easton type
iteration of length $\kappa$ described in [21, Theorem 20].

Let $e:\kappa\to\kappa$ be the function which lists the set $B$ of beth fixed
points $>\lambda$ in increasing order, and let
$S=\langle\kappa_{\xi}:\xi<\lambda\rangle\subseteq B$ be an increasing cofinal
sequence in $\kappa$ such that $\kappa_{0}>\lambda$. Let
$\pi:\kappa\times\kappa\to\kappa$ be the Gödel pairing function. Let $W$ be a
well-order of $V_{\kappa}$. Suppose $A\subseteq\mu$, where $\mu\in B$. We
write $A\sim V_{\mu}$ if

$(V_{\mu},\in)\cong(\mu,\\{(\alpha,\beta):\pi(\alpha,\beta)\in A\\}).$

Let the poset $E(\mu,A)$ be the iteration (product) of the posets
${\mathbb{R}}_{\alpha}$, $\alpha<\mu$, where

${\mathbb{R}}_{\alpha}=\left\\{\begin{array}[]{ll}\mbox{Fn}(\aleph_{\mu+\alpha+3}\times\aleph_{\mu+\alpha+1},2,\aleph_{\mu+\alpha+1}),&\mbox{
if $\alpha=\omega\cdot\beta$ and $\beta\in A$}\\\
\mbox{Fn}(\aleph_{\mu+\alpha+4}\times\aleph_{\mu+\alpha+2},2,\aleph_{\mu+\alpha+2}),&\mbox{
if $\alpha=\omega\cdot\kappa_{\xi}+1$, $\xi<\lambda$}\\\ (\\{0\\},=)&\mbox{
otherwise}\end{array}\right.$

with Easton support i.e. $E(\mu,A)$ consists of functions
$p\in\prod_{\alpha<\mu}{\mathbb{R}}_{\alpha}$ such that, denoting the support
$\\{\alpha:f(\alpha)\neq\emptyset\\}$ of $f$ by $\mbox{supp}(p)$,
$|\mbox{supp}(p)\cap\gamma|<\gamma$ for all regular $\gamma$.

We now define an iteration $\langle{\mathbb{P}}_{\alpha}:\alpha<\kappa\rangle$
with the property that ${\mathbb{P}}_{\alpha}$ does not change beth fixed
points $\beta=\beth_{\beta}$ for any $\beta$. We let
${\mathbb{P}}=\langle{\mathbb{P}}_{\alpha}:\alpha<\kappa\rangle$ be the
following iteration: If $\alpha$ is a limit ordinal, we use direct limits for
regular $\alpha$ and inverse limits for singular $\alpha$. Suppose then
$\alpha=\beta+1$. Let $\dot{A}$ be the $W$-first ${\mathbb{P}}_{\beta}$-name
$\dot{A}$ in $V_{\kappa}$ such that ${\mathbb{P}}_{\beta}\Vdash\dot{A}\sim
V_{\check{e}(\check{\beta})}$. Then
${\mathbb{P}}_{\alpha}={\mathbb{P}}_{\beta}\star
E(\check{e}(\check{\beta}),\dot{A})$. Let $G$ be ${\mathbb{P}}$-generic over
$V$ and $G_{\alpha}=G\cap{\mathbb{P}}_{\alpha}$.

In the forcing extension $V[G]$, for every $\mu\in B$ there is a set
$A\subseteq\mu$ which codes, via the canonical bijection
$\pi:\kappa\times\kappa\to\kappa$, a bijection
$f_{A}\colon\mu\to(V_{\mu})^{V[G]}$. The set $A$ itself satisfies

$V[G]\models
A=\\{\alpha<\mu:2^{\aleph_{\mu+\omega\cdot\alpha+1}}=\aleph_{\mu+\omega\cdot\alpha+3}\\}$

and from $A$ we can read off $f_{A}$ and a well-order $<_{\mu}^{*}$ of
$(V_{\mu})^{V[G]}$:

$V[G]\models f_{A}(\alpha)<_{\mu}^{*}f_{A}(\beta)\iff\alpha<\beta<\mu.$

Now working in $V[G]$, fix a collection
$\mathcal{F}\subseteq\operatorname{\mathcal{P}}(\kappa)$, and we set out to
define a well-order not on the whole of $\mathcal{F}$ but a certain subset of
it. Define a relation $R$ on $\mathcal{F}$ by

$XRY\iff X\cap\kappa_{\xi}<^{*}_{\kappa_{\xi}}Y\cap\kappa_{\xi}\text{ for all
but boundedly many }\xi<\lambda.$

As $\lambda$ is uncountable, $R$ is well-founded, so the set

$\mathcal{W}=\\{X\in\mathcal{F}:X\text{ is minimal in }R\\}$

is nonempty, and if $X,Y\in\mathcal{W}$ with $X\neq Y$, then both
$X\cap\kappa_{\xi}<^{*}_{\kappa_{\xi}}Y\cap\kappa_{\xi}$ and
$Y\cap\kappa_{\xi}<^{*}_{\kappa_{\xi}}X\cap\kappa_{\xi}$ occur for unboundedly
many $\xi<\lambda$.

To see that $\lvert\mathcal{W}\rvert<\kappa$, suppose to the contrary that
$\lvert\mathcal{W}\rvert\geq\kappa$ and define a coloring
$c\colon[\mathcal{W}]^{2}\to\lambda$ by $c(\\{X,Y\\})=\pi(\xi_{1},\xi_{2})$
where $\xi_{1}$ is the least $\xi<\lambda$ such that
$X\cap\kappa_{\xi}<^{*}_{\kappa_{\xi}}Y\cap\kappa_{\xi}$, and $\xi_{2}$ is the
least $\xi<\lambda$ such that
$Y\cap\kappa_{\xi}<^{*}_{\kappa_{\xi}}X\cap\kappa_{\xi}$. Since
$\lvert\mathcal{W}\rvert\geq\kappa>(2^{\lambda})^{+}$, by the Erdös-Rado
theorem there is a set $H\subseteq\mathcal{W}$ homogeneous for $c$ of color
$\pi(\xi_{1},\xi_{2})$ and cardinality $\lambda^{+}$. But this is a
contradiction, since ordering $H$ in $<^{*}_{\kappa_{\xi_{1}}}$-increasing
order yields an infinite decreasing sequence in the well-order
$<^{*}_{\kappa_{\xi_{2}}}$, so $\lvert\mathcal{W}\rvert<\kappa$.

Now for each $X\in\mathcal{W}$, define $f_{Y}\colon\lambda\to\kappa$ such that
$f_{X}(\xi)$ is the index of $X\cap\kappa_{\xi}$ in the well-order
$<^{*}_{\kappa_{\xi}}$. Then the set
$\bigcup\\{\operatorname{ran}(f_{X}):X\in\mathcal{W}\\}$ has some cardinality
$\gamma<\kappa$, and we can let
$h\colon\bigcup\\{\operatorname{ran}(f_{X}):X\in\mathcal{W}\\}\to\gamma$ be
the transitive collapse map.

Then for $X\in\mathcal{W}$, the function $h\circ f_{X}\colon\lambda\to\gamma$
can be encoded as a subset of a large enough $\mu\in B$, and obviously $h\circ
f_{X}\neq h\circ f_{Y}$ if $X\neq Y$, so we can well-order $\mathcal{W}$ by

$X\lhd Y\iff h\circ f_{X}<^{*}_{\mu}h\circ f_{Y}$

and all this is second order definable in $V[G]$ in a structure of size
$\kappa$, if the collection $\mathcal{F}$ is. This allows us to pick a
distinguished element of $\mathcal{F}$ as the $\lhd$-least $R$-minimal
element.

Suppose now that $\phi$ is a complete second order sentence with a model $M$
of cardinality $\kappa$, and let $\mathcal{F}$ consist of the set of
$X\subseteq\kappa$ encoding a model of $\phi$. Note that over a model of
cardinality $\kappa$ we can write a formula $\phi_{R}(X,Y)$ expressing $XRY$
for $X,Y\in\mathcal{F}$, a formula $\phi_{\mathcal{W}}(X)$ expressing
$X\in\mathcal{W}$, and a formula $\phi_{\lhd}(X,Y)$ expressing $X\lhd Y$ if
$X$ and $Y$ are $R$-minimal.

Let $M\models\Phi$ now say that $X\subseteq M$ encodes a model isomorphic to
$M$ (and thus satisfies $\phi$), and for any $Y\subseteq M$ that also encodes
a model of $\phi$, $\lnot\phi_{R}(Y,X)$, and moreover if for all $Z\subseteq
M$ that encode a model of $\phi$ also $\lnot\phi_{R}(Z,Y)$, then $X=Y$ or
$\phi_{\lhd}(X,Y)$. That is, $X\in\mathcal{W}$ and if also $Y\in\mathcal{W}$
then $X=Y$ or $X\lhd Y$, which uniquely specifies $X$. As the model of $\phi$
with the least code in this sense satisfies $\Phi$ and $\phi$ is complete,
$\phi$ implies $\Phi$ and thus that all models of $\phi$ are isomorphic, so
$\phi$ is categorical. ∎

The method of the preceding proof does not extend to the cases of the limit
cardinal $\kappa$ being regular, or of countable cofinality, so these cases
are left open.

In conclusion, no known large cardinal axiom (e.g. the existence of huge
cardinals) can decide whether all complete second order theories with a model
of singular cardinality are categorical. In particular, such axioms cannot
imply that all finite complete second order theories are categorical.

##  7 Theories with only countably many models

Since under PD we have non-categorical complete recursively axiomatized second
order theories, we may ask how badly categoricity can fail in those cases?
Echoing Vaught’s Conjecture, we may ask whether the number of countable non-
isomorphic models of a complete recursively axiomatized second order theory is
always countable or $2^{\omega}$. Leaving this question unresolved, we have
the following result which demonstrates the ability of categorical theories to
‘capture’ (in the sense of [23]) the models of non-categorical theories.

######  Theorem 20.

Assume $AD^{L({\mathbb{R}})}$. If $T$ is a recursively axiomatized complete
second order theory with only countably many non-isomorphic countable models,
then there is a recursively axiomatized categorical second order theory $S$
the unique model of which interprets all the countable models of $T$.

###### Proof.

Let $T$ be a recursively axiomatized second order theory with only countably
many non-isomorphic countable models. Let $A$ be the $\Pi^{1}_{\omega}$ (i.e.
an intersection of a recursively coded family of sets each of which is
$\Pi^{1}_{n}$ for some $n$) set of reals that code a model of $T$. Since $A$
is a countable union of equivalence classes of the
$\Sigma^{1}_{1}$-equivalence relation of isomorphism, we may conclude that $A$
is $\mathbf{\Sigma}^{1}_{1}$.

We wish to show that $A$ is $\Pi^{1}_{2}(r_{0})$ in a parameter $r_{0}$ which
is a $\Pi^{1}_{\omega}$ singleton. For this, we mimic a proof of Louveau
(Theorem 1 in [17]) to show:

######  Theorem 21.

Assume $AD^{L({\mathbb{R}})}$. Every $\mathbf{\Sigma}^{1}_{1}$ set which is
$\Pi^{1}_{\omega}$ is $\Pi^{1}_{2}(r_{0})$ for some real $r_{0}$ such that
$\\{r_{0}\\}$ is a $\Delta^{1}_{\omega+1}$-singleton.

###### Proof.

Let $A$ be a $\mathbf{\Sigma}^{1}_{1}$ set that is also $\Pi^{1}_{\omega}$,
say $A=\bigcap_{n}A_{n}$ with each $A_{n}$ being $\Pi^{1}_{n}$. Let also
$U\subseteq(\omega^{\omega})^{2}$ be a universal $\Sigma^{1}_{1}$ set.

We define for each $n$ a game $G_{n}$ on $\omega$ where players I and II take
turns to play the digits of reals $\alpha$ and $\gamma$ respectively (there is
no need to let II pass turns here). Then II wins a play of $G_{n}$ if
$\alpha\in A\implies\gamma\in U$ and $\alpha\notin A_{n}\implies\gamma\notin
U$.

$\begin{array}[]{c|ccccc}\text{I}&n_{0}&&n_{1}&&\cdots\\\
\hline\cr\text{II}&&m_{0}&&m_{1}&\cdots\end{array}\quad\begin{matrix}\alpha\\\
\gamma\end{matrix}$

As in Louveau’s proof, II has a winning strategy as follows: since $A$ is
$\mathbf{\Sigma}^{1}_{1}$, we have $A(x)\iff U(y,x)$ for some $y$, so II wins
by playing the digits of $\langle y,\alpha\rangle$ (as I is playing the digits
of $\alpha$). The complexity of the winning set for II in $G_{n}$ is
$\Sigma^{1}_{\omega}$, so by Moschovakis’s strategic basis theorem ([22],
Theorem 6E.2), II has a winning strategy $\sigma_{n}$ that is a
$\Delta^{1}_{\omega+1}$-singleton. Note that the pointclass
$\Sigma^{1}_{\omega}$, i.e. the collection of countable unions of recursively
coded families of projective sets, is both adequate and scaled (see Remark 2.2
in [24], essentially Theorem 2.1 in [27]).

Then the set $B_{n}=\\{y\mid(y*\sigma_{n})_{\text{II}}\in U\\}$ is a
$\Sigma^{1}_{1}(\sigma_{n})$ set with $A\subseteq B_{n}\subseteq A_{n}$ (where
$(y*\sigma_{n})_{\text{II}}$ denotes the real $\gamma$ the strategy
$\sigma_{n}$ produces as I plays $\alpha=y$), so altogether
$A=\bigcap_{n}B_{n}$ is a $\Pi^{1}_{2}(s_{0})$ set where
$s_{0}=\langle\sigma_{n}\mid n<\omega\rangle$ is a
$\Delta^{1}_{\omega+1}$-singleton. ∎

We may reduce the complexity of the parameter down to being a
$\Pi^{1}_{\omega}$ singleton by the following theorem of Rudominer:

######  Theorem 22 (Rudominer [24]).

Assume $AD^{L({\mathbb{R}})}$. Then every real $s_{0}$ which is a
$\Sigma^{1}_{\omega+1}$ singleton, is recursive in a real $r_{0}$ which is a
$\Pi^{1}_{\omega}$ singleton. ∎

Therefore the set $A$ is a $\Pi^{1}_{2}(r_{0})$ set where $r_{0}$ is a
$\Pi^{1}_{\omega}$ singleton. Let $\eta(r,s)$ be a second order $\Pi^{1}_{2}$
formula which defines the predicate $s\in A$ on
$({\mathbb{N}},+,\times,r_{0})$. Let $\theta_{1}(Q_{+},Q_{\times})$ be the
standard second order characterization of $({\mathbb{N}},+,\times)$, as above
in the proof of Theorem 3. Let $\psi_{n}(Q_{+},Q_{\times},s)$, $n<\omega$, be
second order formulas such that if $X_{n}$ is the set of reals $s$ satisfying
$\psi_{n}(Q_{+},Q_{\times},s)$ in $({\mathbb{N}},+,\times)$, then
$\\{r_{0}\\}=\bigcap_{n}X_{n}$. Let $P$ be a new unary predicate symbol and

$S=\\{\theta_{1}(Q_{+},Q_{\times})\\}\cup\\{\psi_{n}(Q_{+},Q_{\times},P):n<\omega\\}.$

Suppose $M$ is a model of $S$. W.l.o.g. the arithmetic part of $M$ consists of
the standard $+$ and $\times$ on ${\mathbb{N}}$. Let $s$ be the interpretation
of $P$ in $M$. Then $s=r_{0}$. Thus $S$ is categorical. The theory $S$ is
recursive because the proofs of Theorems 21 and 22 are sufficiently uniform.
In conclusion, $M$ is categorically characterized by the recursive second
order theory $S$.

Now the countable models of $T$ are interpretable in $S$ in the following
sense: a real $s$ codes a model of $T$ if and only if $M\models\eta(r_{0},s)$.
We also get a translation of sentences: if $\phi$ is a second-order sentence
in the vocabulary of $T$, letting $\hat{\phi}$ be the sentence $\exists
X(\eta(r_{0},X)\land X\models\phi)$, we have that $\phi\in T$ if and only if
$\hat{\phi}\in S$. ∎

##  8 Definable models of categorical theories

Suppose we are given a categorical second order theory $T$. Naturally, we
assume that $T$ has a model, otherwise categoricity is vacuous. But what can
be said about the models of $T$ apart from their isomorphism with each other?
In particular, can we always find a model which is definable in some
reasonable sense, e.g. hereditarily ordinal definable? To emphasize this
point, consider the second order sentence which characterizes the structure
$({\mathbb{N}},+,\cdot,0^{\sharp})$. This categorical sentence has no models
in $L$. We ask, can we have a categorical sentence with no models in
$\mathop{\mbox{HOD}}$? Since it could be that $V=\mathop{\mbox{HOD}}$, we are
looking at this question under assumptions stronger than ZFC.

The following result of Kaplan and Shelah is useful for us:

######  Theorem 23 ([13]).

If ${\mathbb{P}}$ forces the collapse of $|\omega_{2}|$ to $\omega$, then
there is a ${\mathbb{P}}$-term $\tau$ for a countable model such that

  1. 1.

If $G_{1}\times G_{2}$ is generic for ${\mathbb{P}}\times{\mathbb{P}}$ then

$V[G_{1}][G_{2}]\models M_{1}\cong M_{2},$

where $M_{1}$ is the interpretation $\tau^{G_{1}}$ of $\tau$ by $G_{1}$ and
$M_{2}$ is $\tau^{G_{2}}$.

  2. 2.

${\mathbb{P}}\Vdash``\tau$ is not isomorphic to $\check{M}$”, for any $M$ in
$V$.

We make some observations about the proof. It involves a construction of
Laskowski and Shelah:

######  Theorem 24 ([16]).

There is a countable consistent first order theory $T$, with a predicate $V$
in its vocabulary, having the following property. For any model $M\models T$
and any $A\subseteq V^{M}$, isolated types are dense over $A$ but the theory
$T(A)=\operatorname{Th}(M,a)_{a\in A}$ has an atomic model if and only if
$\lvert A\rvert<\omega_{2}$.

The theory $T$ is as follows. Let $L$ be a countable vocabulary consisting of
two unary predicates $U,V$, one unary function symbol $p$, as well as binary
relations $R_{n}$ and binary functions $f_{n}$ for $n<\omega$ (the functions
will not be total, but instead have domain $U$). Let $K$ be the collection of
all finite $L$-structures satisfying a certain finite list of first order
axioms (see [16]). Let $\mathcal{B}$ be the Fraïsse limit of $K$ and let
$T=\operatorname{Th}(\mathcal{B})$. The theory $T$ is well defined since
$\mathcal{B}$ is unique up to isomorphism.

We then form an uncountable model of the theory $T$ as follows. For an ordinal
$\alpha$ let $L_{\alpha}$ be the vocabulary $L$ together with $\alpha$ many
new constant symbols $c_{\beta}$, $\beta<\alpha$. Using a standard Henkin
construction, we form a term model for the theory $T$ together with the
additional axioms stating that the new constant symbols name distinct
elements. We let $T(A_{\alpha})$ be the theory of this term model in the
vocabulary $L_{\alpha}$. (Although the Henkin construction involves forming
the completion of a theory, we can make the choice of which completion to use
definable by referring to the well-ordering of the sentences.)

We can also observe that for a countable ordinal $\alpha$, the class of
countable atomic models of $T(A_{\alpha})$ is definable from $T(A_{\alpha})$,
which itself is definable from $\alpha$, and the definitions can be carried
out in $H(\omega_{1})$. Using these two observations, the following obtains:

######  Theorem 25 (ZF).

Assume $\omega_{2}^{\scriptsize\mathop{\mbox{HOD}}}$ is countable. Then there
is a countable model M such that

  1. 1.

The isomorphism class of M is ordinal definable.

  2. 2.

There is no model in $\mathop{\mbox{HOD}}$ which is isomorphic to M.

Moreover, if the property of a linear order of being of order-type
$\omega_{2}^{\scriptsize\mathop{\mbox{HOD}}}$ is second order definable in the
countably infinite structure of the empty vocabulary, then the second order
theory of $M$ is finitely axiomatizable.

###### Proof.

Let $\alpha=\omega_{2}^{\text{HOD}}$. Let $T(A_{\alpha})$ be the theory
constructed above. Finally, let $M$ be a countable atomic model of
$T(A_{\alpha})$. Since $\mathop{\mbox{HOD}}$ satisfies $\lvert
T(A_{\alpha})\rvert=\omega_{2}$, the theory $T(A_{\alpha})$ has no atomic
model in $\mathop{\mbox{HOD}}$, but as being an atomic model is absolute, this
shows that there is no model in $\mathop{\mbox{HOD}}$ isomorphic to $M$.

The isomorphism class of $M$ is ordinal definable as the class of countable
atomic models of $T(A_{\alpha})$, which is definable from $\alpha$.
Additionally, if $\alpha$ is second order definable in the countably infinite
structure of the empty vocabulary, we can define the theories $T$ and
$T(A_{\alpha})$ in second order logic expressing “I am isomorphic to a
countable atomic model of $T(A_{\alpha})$” with a single second order
sentence. This finitely axiomatizes the second order theory of $M$. ∎

Of course, the assumption that $\omega_{2}^{\scriptsize\mathop{\mbox{HOD}}}$
is second order definable in the countably infinite structure of the empty
vocabulary is somewhat ad hoc. However, it holds, for example, in $L[G]$,
where $G$ is $P$-generic over $L$ for
$P=\operatorname{Coll}(\omega,<\omega_{3})^{L}$. This is because the poset $P$
is weakly homogeneous, so
$\mathop{\mbox{HOD}}^{L[G]}=\mathop{\mbox{HOD}}^{L}(P)=L$, whence
$\omega_{2}^{\scriptsize\mathop{\mbox{HOD}}}=\omega_{2}^{L}$ is countable and
second order definable in any countable model in $L[G]$.

We also obtain the following variation:

######  Corollary 26.

Assume $ZFC+AD^{L({\mathbb{R}})}+``\mathop{\mbox{HOD}}\hskip 2.0pt\cap\hskip
2.0pt{\mathbb{R}}=\mathop{\mbox{HOD}}^{L({\mathbb{R}})}\cap\hskip
2.0pt{\mathbb{R}}"$ and that $\omega_{2}^{\scriptsize\mathop{\mbox{HOD}}}$ is
definable in
$\mathop{\mbox{HOD}}^{L({\mathbb{R}})}\restriction\Theta^{L({\mathbb{R}})}$
and countable. Let $M$ be the countable model of Theorem 25. Let
$N=(\Theta^{L({\mathbb{R}})},<,M)$ (w.l.o.g. the domain of $M$ is $\omega$).
Then the second order theory of $N$ is finitely axiomatizable and categorical
but has no model which belongs to $\mathop{\mbox{HOD}}$.

###### Proof.

We can use [7, Theorem 3.10, Chapter 23]) to define
$\mathop{\mbox{HOD}}^{L({\mathbb{R}})}\restriction\Theta^{L({\mathbb{R}})}$
and $L_{\Theta^{L({\mathbb{R}})}}({\mathbb{R}})$ from
$\Theta^{L({\mathbb{R}})}$ in second order logic, which then allows us to
define $\omega_{2}^{\scriptsize\mathop{\mbox{HOD}}}$ and $M$ as in Theorem 25.
∎

The assumptions of Corollary 26 follow, for example, from
$ZFC+AD^{L({\mathbb{R}})}+V=L({\mathbb{R}})[G]$, where $G$ is
${{\mathbb{P}}_{\text{max}}}$-generic, as then
$\mathop{\mbox{HOD}}^{L({\mathbb{R}})}=\mathop{\mbox{HOD}}^{L({\mathbb{R}})[G]}$
and $\omega_{2}^{\scriptsize\mathop{\mbox{HOD}}}$ is countable.

##  9 Open questions

The following question was raised by Solovay [26]:

######  Open Problem 1.

Assuming $V=L$, is every recursively axiomatized complete second order theory
categorical?

Our results do not solve this one way or another, and it remains an
interesting open question. In $L[U]$ there are recursively axiomatized
complete non-categorical second order theories, but we do not know if such
theories necessarily have only large models:

######  Open Problem 2.

Suppose $V=L[U]$, $\kappa$ is the sole measurable cardinal of $L[U]$, and $T$
is a complete recursively axiomatized second order theory that has a model of
cardinality $\lambda<\kappa$ such that $\lambda$ is second order
characterizable. Is $T$ categorical?

There are many other open questions related to finite or recursively
axiomatized complete second order theories with uncountable models. We showed
that we can force categoricity for successor cardinals of regular cardinals,
and some singular limit cardinals, but the following two cases were left open:

######  Open Problem 3.

Can we always force the categoricity of all finite complete second order
theories with a model of cardinality $\kappa$, where $\kappa$ is either a
regular (non-measurable) limit cardinal, or singular of cofinality $\omega$?

An $I_{0}$-_cardinal_ is a cardinal $\lambda$ such that there is $j\colon
L(V_{\lambda+1})\to L(V_{\lambda+1})$ with critical point below $\lambda$.
Note that then $\lambda$ is singular of cofinality $\omega$, $\lambda^{+}$ is
measurable in $L(V_{\lambda+1})$ ([29]), and the Axiom of Choice fails in
$L(V_{\lambda+1})$ ([15]). This is in sharp contrast to the result of Shelah
that if $\lambda$ is a singular strong limit cardinal of uncountable
cofinality, then $L({\mathcal{P}}(\lambda))$ satisfies the Axiom of Choice
([25]). Since Axiom of Choice fails in $L(V_{\lambda+1})$, there can be no
well-order of ${\mathcal{P}}(\lambda)$ which is second order definable on
$\lambda$. This raises the following question:

######  Open Problem 4.

Is every finite complete second order theory with a model of cardinality of an
$I_{0}$-cardinal categorical (or, at least categorical among all models of
that cardinality)?

## References

  * [1] Miklós Ajtai.  Isomorphism and higher order equivalence.  Annals of Mathematical Logic, 1979.
  * [2] David Asperó and Sy-David Friedman.  Large cardinals and locally defined well-orders of the universe.  Ann. Pure Appl. Logic, 157(1):1–15, 2009.
  * [3] David Asperó and Sy-David Friedman.  Definable well-orders of $H(\omega_{2})$ and GCH.  J. Symbolic Logic, 77(4):1101–1121, 2012.
  * [4] David Asperó and Ralf Schindler.  Martin’s Maximum++ implies Woodin’s axiom $(*)$.  Ann. of Math. (2), 193(3):793–835, 2021.
  * [5] Steve Awodey and Erich H. Reck.  Completeness and categoricity. I. Nineteenth-century axiomatics to twentieth-century metalogic.  Hist. Philos. Logic, 23(1):1–30, 2002.
  * [6] Rudolf Carnap.  Untersuchungen zur allgemeinen Axiomatik.  Wissenschaftliche Buchgesellschaft, Darmstadt, 2000.  Edited and with a foreword by Thomas Bonk and Jesus Mosterin.
  * [7] M. Foreman and A. Kanamori.  Handbook of Set Theory.  Springer Netherlands, 2009.
  * [8] Abraham Fraenkel.  Einleitung in die Mengenlehre. 3. Aufl., volume 9.  Springer, Berlin, 1928.
  * [9] Roland Fraïssé.  Sur les types de polyrelations et sur une hypothèse d’origine logistique.  C. R. Acad. Sci. Paris, 230:1557–1559, 1950.
  * [10] Roland Fraïssé.  Sur la signification d’une hypothèse de la théorie des relations, du point de vue du calcul logique.  C. R. Acad. Sci. Paris, 232:1793–1795, 1951.
  * [11] William P Hanf and Dana Scott.  Classifying inaccessible cardinals.  Notices of the American mathematical Society, 8:445, 1961.
  * [12] Akihiro Kanamori.  The higher infinite : large cardinals in set theory from their beginnings.  Springer monographs in mathematics. Springer, Berlin ;, 2nd ed. edition, 2003.
  * [13] Itay Kaplan and Saharon Shelah.  Forcing a countable structure to belong to the ground model.  MLQ Math. Log. Q., 62(6):530–546, 2016.
  * [14] Eugene M. Kleinberg.  Infinitary combinatorics and the axiom of determinateness, volume Vol. 612 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin-New York, 1977.
  * [15] Kenneth Kunen.  Elementary embeddings and infinitary combinatorics.  J. Symbolic Logic, 36:407–413, 1971.
  * [16] M. C. Laskowski and S. Shelah.  On the existence of atomic models.  J. Symbolic Logic, 58(4):1189–1194, 1993.
  * [17] Alain Louveau.  Borel sets and the analytical hierarchy.  In Proceedings of the Herbrand symposium (Marseilles, 1981), volume 107 of Stud. Logic Found. Math., pages 209–215. North-Holland, Amsterdam, 1982.
  * [18] Wiktor Marek.  Consistance d’une hypothèse de Fraïssé sur la définissabilité dans un langage du second ordre.  C. R. Acad. Sci. Paris Sér. A-B, 276:A1147–A1150, 1973.
  * [19] Wiktor Marek.  Sur la consistance d’une hypothèse de Fraïssé sur la définissabilité dans un langage du second ordre.  C. R. Acad. Sci. Paris Sér. A-B, 276:A1169–A1172, 1973.
  * [20] Donald A. Martin.  The axiom of determinateness and reduction principles in the analytical hierarchy.  Bull. Amer. Math. Soc., 74:687–689, 1968.
  * [21] Telis K. Menas.  Consistency results concerning supercompactness.  Trans. Amer. Math. Soc., 223:61–91, 1976.
  * [22] Yiannis N. Moschovakis.  Descriptive set theory, volume 155 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, RI, second edition, 2009.
  * [23] Michael O. Rabin.  A simple method for undecidability proofs and some applications.  In Logic, Methodology and Philos. Sci. (Proc. 1964 Internat. Congr.), pages 58–68. North-Holland, Amsterdam, 1965.
  * [24] Mitch Rudominer.  The mouse set theorem just past projective.  Journal of Mathematical Logic, 0(0):2450014, 0.
  * [25] Saharon Shelah.  Set theory without choice: not everything on cofinality is possible.  Arch. Math. Logic, 36(2):81–125, 1997.
  * [26] Robert Solovay.  FOM posting, 2006.  http://cs.nyu.edu/pipermail/fom/2006-May/010561.html.
  * [27] John R. Steel.  Scales in $L({\bf R})$.  In Cabal seminar 79–81, volume 1019 of Lecture Notes in Math., pages 107–156. Springer, Berlin, 1983.
  * [28] W. Hugh Woodin.  The axiom of determinacy, forcing axioms, and the nonstationary ideal, volume 1 of De Gruyter Series in Logic and its Applications.  Walter de Gruyter GmbH & Co. KG, Berlin, revised edition, 2010.
  * [29] W. Hugh Woodin.  Suitable extender models II: beyond $\omega$-huge.  J. Math. Log., 11(2):115–436, 2011.
  * [30] W. Hugh Woodin.  In search of Ultimate-$L$: the 19th Midrasha Mathematicae Lectures.  Bull. Symb. Log., 23(1):1–109, 2017.