\documentclass{amsart}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{mathabx}
\usepackage{stmaryrd}


\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}



\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exer}{Exercise}
\newtheorem{exam}{Example}


\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{fact}[thm]{Fact}
\newtheorem{hyp}[thm]{Hypothesis}

\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\res}{\restriction}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\cof}{\operatorname{cof}}
\newcommand{\ot}{\text{o.t.}}
\newcommand{\on}{\text{ON}}
\newcommand{\card}{\text{CARD}}
\newcommand{\ac}{\text{AC}}
\newcommand{\zf}{\text{ZF}}
\newcommand{\zfc}{\text{ZFC}}
\newcommand{\sP}{\mathcal{P}}
\newcommand{\sL}{\mathcal{L}}
\newcommand{\ch}{\text{CH}}
\newcommand{\gch}{\text{GCH}}
\newcommand{\vb}{\text{var}}
\newcommand{\pa}{\text{PA}}
\newcommand{\fa}{\text{F}}
\newcommand{\con}{\text{CON}}


\newcommand{\bz}{\boldsymbol{0}}
\newcommand{\lD}{{\Delta}}
\newcommand{\lS}{{\Sigma}}
\newcommand{\lP}{{\Pi}}
%\newcommand{\models}{\vDash}
\newcommand{\proves}{\vdash}
\newcommand{\sg}{\text{sg}}
\newcommand{\seq}{\text{Seq}}
\newcommand{\lh}{\text{lh}}
\newcommand{\pred}{\text{pred}}



\begin{document}




\begin{center}
\bf Absoluteness and Definability
\end{center}
\bigskip

\section{Formulas and Absoluteness}


Recall that if $M$ is a set and $E$ is a binary relation
on $M$, and $\phi(x_1,\dots,x_n)$ is a formula in the language of set theory
and $a_1,\dots,a_n \in M$, then in our discussion of first order logic
we have defined the notion of $(M,E) \models \phi(a_1,\dots,a_n)$. 
Suppose now $M$ is a set or class and $E$ is a set or class
binary relation on $M$.
Given such an $M$ and $E$ we define a formula $\phi^{(M,E)}$, with parameters,
in the language of set theory which expresses the statement that 
$(M,E) \models \phi(a_1,\dots,a_n)$. We call $\phi^{(M,E)}$ the 
{\em relativization} of $\phi$ to $(M,E)$.

\begin{defn}
Let $M,E$ be classes, and $\phi$ a formula in the language of set theory. 
We define $\phi^{(M,E)}$ by induction on $\phi$ through the following
cases. 

\begin{enumerate}
\item
$(x \in y)^{(M,E)}= (x E y)$.
\item
$(x \approx y)^{(M,E)}= (x \approx y)$.
\item
$(\exists x\ \psi)^{(M,E)}= \exists x \in M \ (\psi^{(M,E)})$.
\item
$(\neg  \psi)^{(M,E)}= \neg (\psi^{(M,E)})$.
\end{enumerate}
If $E$ is the $\epsilon$ relation, or if $E$ is understood, we
simply write $\phi^M$. 
\end{defn}


Note that the relativization of $\forall x \psi$ is implicitly
defined to be $\forall x \in M \ \psi^M$. Note that if $M$ and $E$
are sets, then $\phi^{(M,E)}$ will be a formula with parameters; 
it will  have $M$ and $E$ as parameters. If however $M$ and $E$ are 
pure classes (i.e., given by formulas), then $\phi^{(M,E)}$
will also be a formula in the language of set theory (i.e., without
parameters). The following fact is an immediate consequence of the
definitions, it is more or less just expresses the definition of 
$(M,E) \models \phi$.

\begin{fact}
For all sets $M,E$, formulas $\phi(x_1,\dots,x_n)$, and 
$a_1,\dots,a_n \in M$, $\phi^{(M,E)} \leftrightarrow (M,E) \models
\phi(\vec a)$. 
\end{fact}

If $M,E$ are classes, we may take  $\phi^{(M,E)}$ as our definition of
``$(M,E) \models \phi(\vec a)$.''




As we will be changing the universe of sets by enlarging or shrinking it,
the following definition becomes important. 


\begin{defn}
Let $\phi(x_1,\dots,x_n)$ be a formula in the language of set theory. 
Let $M \subseteq N$
be sets or classes. Let $E \subseteq N \times N$ be a set or class, and
let $E' = E \cap (M \times M)$. 
We say $\phi$ is {\em absolute} between $M$ and $N$
if for all $a_1,\dots,a_n \in M$ we have $\phi^{(M,E')}(a_1,\dots,a_n)
\leftrightarrow \phi^{(N,E)}(a_1,\dots,a_n)$.
\end{defn}

A common case is when $E$ is the $\epsilon$ relation on $N$, in which case
$E'$ is also just the $\epsilon$ relation on $M$. In this case we simply say 
$\phi$ is absolute between $M$ and $N$. Intuitively, we are saying that the
truth of the statement $\phi(a_1,\dots,a_n)$ doesn't depend on whether we
evaluate the statement in $M$ or in $N$. 


\begin{exer} \label{exerab1}
Let $N=\omega$ and $M$ be the odd natural numbers. Let $E$ be the $\epsilon$
relation on $N$. Let $\psi$ be the sentence $\exists x\ \forall y\ 
(y \notin x)$, which asserts the existence of an emptyset. 
Does $\psi^N$ hold? Does $\psi^M$ hold? Let $\phi(x)= 
\exists y\ (y \in x)$. Is $\phi$ absolute between $M$ and $N$?
\end{exer}



In order to investigate which formulas are absolute between which 
sets or classes, we first introduce the following hierarchy of formulas
in the language of set theory, similar in spirit to the hierarchy
introduced earlier for formulas in the language of number theory. 

\begin{defn}
A formula in the language of set theory is $\lD_0$ if it is in the smallest 
collection satisfying the following. 
\begin{enumerate}
\item
All atomic formulas $(x_i \in x_j)$, $(x_i \approx x_j)$ are $\lD_0$.
\item
If $\phi, \psi \in \lD_0$, then so are $\neg \phi$, $\phi \wedge \psi$, 
$\phi \vee \psi$. 
\item
If $\phi(x_1,\dots,x_n,y) \in \lD_0$, then so are 
$\psi(x_1,\dots,x_n)=\exists y \in x_i\ 
\phi(x_1,\dots,x_n,y)$ and $\psi(x_1,\dots,x_n)=\forall y \in x_i\ 
\phi(x_1,\dots,x_n,y)$
\end{enumerate}
A formula is said to be $\lS_n$ if it is logically equivalent to a formula 
of the form 
$\exists x_1 \dots \exists x_n\ \phi$ where $\phi \in \lP_{n-1}$, and
said to be $\lP_n$ if it is equivalent to one of the form 
$\forall x_1 \dots \exists x_n\ \phi$ where $\phi \in \lS_{n-1}$. 
\end{defn}


\begin{lem} \label{d0}
Let $(M,E') \subseteq (N,E)$, where $M,N,E$ are sets or classes. 
Assume that whenever $a \in M$, $b \in N$ and $b E a$, then $b \in M$. 
Then any $\lD_0$ formula is absolute between $(M,E')$ and $(N,E)$. 
\end{lem}


\begin{proof} 
By induction on the formula $\phi$. If $\phi$ is atomic, this is almost
trivial since $E'= E \cap (M \times M)$. The inductive step for the
Boolean connectives is trivial. Suppose $\phi(x)=\exists y\in x\ \psi(x,y)$. 
Let $a \in M$. If $\phi^{(M,E')}(a)$ then there is a $b \in M$ with 
$b E' a$ (and hence $b E a$) such that $\psi^{(M,E')}(a,b)$. 
By induction, $\psi^{(N,E)}(a,b)$
and hence $\phi^{(N,E)}(a)$. Suppose now $\phi^{(N,E)}(a)$. 
Then there is a $b \in N$ with $b E a$ such that $\psi^{(N,E)}(a,b)$. 
By hypothesis, $b \in M$, and also $b E' a$. By induction (using $b \in M$)
we also have $\psi^{(M,E')}(a,b)$. Hence we have $\phi^{(M,E')}(a)$. 
\end{proof}


In the case where $E=\in$, then the hypotheses above are satisfied if 
$M$ is transitive. Thus we have:


\begin{cor}
If $M \subseteq N$ are sets or classes and $M$ is transitive,
then any $\lD_0$ is absolute between $M$ and $N$. 
\end{cor}


As exercise~\ref{exerab1} shows, the hypothesis of transitivity is necessary
for the absoluteness of $\lD_0$ formulas. 

The following exercise generalizes lemma~\ref{d0}
a little.

\begin{exer}
Under the hypotheses of lemma~\ref{d0}, show that the set
of formulas which are absolute between $M$ and $N$ are closed
under the Boolean connectives and bounded set quantification,
that is, if $\phi(\vec x,y)$ is absolute then so is 
$\psi(\vec x)=\exists y \in x_i\ \phi(\vec x,y)$.
\end{exer}





The next lemma shows that we have upwards absoluteness for $\lS_1$ formulas,
and downward absoluteness for $\lP_1$ formulas. 


\begin{lem} \label{abud}
Let $(M,E') \subseteq (N,E)$ satisfy the hypothesis of lemma~\ref{d0}.
Then if $\phi(x) \in \lS_1$ and $\phi^{(M,E')}(a)$, then 
$\phi^{(N,E)}(a)$. If $\phi(x) \in \lP_1$ and 
$\phi^{(N,E)}(a)$ then  $\phi^{(M,E')}(a)$.
\end{lem}


\begin{proof}
Suppose for example $\phi(x)=\forall y\ \psi(x,y)$ where $\psi \in 
\lD_0$. Let $a \in M$ and suppose $\phi^{(N,E)}(a)$. Thus for all 
$b \in N$ we have $\psi^{(N,E)}(a,b)$. In particular, for all $b \in M$
we have  $\psi^{(N,E)}(a,b)$. For each $b \in M$ we have 
 $\psi^{(M,E')}(a,b)$ from lemma~\ref{d0}. Hence,  $\phi^{(M,E')}(a)$.
\end{proof}



\begin{cor}
If $M \subseteq N$ are sets or classes and $M$ is transitive, then
$\lS_1$ formulas are upwards absolute between $M$ and $N$, and $\lP_1$
are downwards absolute.
\end{cor}



If $\Gamma$ is a set of sentences in the language of set theory (e.g.,
$\Gamma=\zfc$), we say a formula $\phi$ is $\Gamma$ provably $\lD_1$
if there are $\lS_1$ and $\lP_1$ formulas $\psi_1$, $\psi_2$
respectively such that 
$\Gamma \proves \forall x_1,\dots x_n\ [ \phi(\vec x) \leftrightarrow
\psi_1(\vec x) \leftrightarrow \psi_2(\vec x)]$.


From lemma~\ref{abud} the following is immediate.


\begin{lem} \label{d1}
Suppose $(M,E') \subseteq (N,E)$ satisfy the hypothesis of lemma~\ref{d0},
and $\phi$ is $\Gamma$ provably $\lD_1$. 
Suppose $(M,E') \models \Gamma$ and $(N,E) \models \Gamma$.
Then $\phi$ is absolute between
$(M,E')$ and $(N,E)$. 
\end{lem}



\begin{cor}
Let $M \subseteq N$ be sets or classes with $M$ transitive. 
Suppose $\phi$ is $\Gamma$ provably $\lD_1$ and $M, N \models \Gamma$. 
Then $\phi$ is absolute between $M$ and $N$. 
\end{cor}


\begin{exer}
Let $M=(\omega, \in)$ and $N=(\omega+1, \in)$. Find a $\lS_1$
formula which is not downwards absolute between $M$ and $N$. 
\end{exer}


In the discussion that follows, we will drop the extra generality
of the relation $E$  and assume that the relations are always the 
$\epsilon$ relation on the sets (or classes) $M$ and $N$. 
The results are all valid in the extra generality by the same
proofs [if $M$ is a set, we could also argue that a more 
general $E$ relation
can always be viewed as the ``real'' $\epsilon$ relation, provided
the structures $(M,E')$, $(N,E)$ satisfy whatever axioms
of $\zfc$ we require of the models $(M, \epsilon)$,
$(N,\epsilon)$. If $M$ is a class, however, this runs into a little
problem as we are not necessarily assuming $M$ is a class inside of
the model $(N,E)$.]


Note that for all the absoluteness results
stated above, the hypotheses are all of the form 
$M \subseteq N$ and $M$ is transitive.



We frequently wish to speak of the absoluteness of relations and 
functions as well. If $R$ is a set or class relation, then when
we speak of the absoluteness of $R$ we are really referring 
to the absoluteness of some implicitly understood formula
defining the relation $R$. If $R$ is a class, then $R$ 
is officially a formula by definition. When $R$ is a set relation,
we will still be implicitly referring to an underlying
defining formula. Suppose now $f$ is a set or class function (say
for simplicity a unary function). Again, we will implicitly
have a formula $\phi(x,y)$ in mind which defines the relation 
$f(x)=y$. When we say $f$ is absolute between $M$ and $N$ we
then mean two things: first, the relation $\phi$ is absolute
between $M$ and $N$ and second, both $M$ and $N$ satisfy the
statement $\forall x\ \exists ! y\ \phi(x,y)$. That is, both
$M, N$ satisfy that $\phi$ defines a function in addition to 
$\phi$ being absolute. 



The following lemma simplifies some computations.



\begin{lem}
A composition of absolute relations and functions is absolute. 
That is, if $R(x_1,\dots, x_n)$, $f(x_1,\dots,x_n)$, and
$g_i(y_1,\dots,y_m)$, $1 \leq i \leq n$,  
are absolute between two models, then so are
$R(g_1(\vec y),\dots, g_n(\vec y))$ and 
$f(g_1(\vec y),\dots, g_n(\vec y))$. (Recall that $R$, $f$, and the
$g_i$ are officially regarded as formulas in this context.)
\end{lem}

\begin{proof}
If $M \subseteq N$, and $\vec y \in M$, then $g^M_1(\vec y)=g^N_1(\vec y)=z_1
\in M$, $\dots, 
g^M_n(\vec y)=g^N_n(\vec y)=z_n \in M$. Also, by assumption 
$R^M(z_1,\dots,z_n)$ iff $R^N(z_1,\dots,z_n)$ and the result follows.
\end{proof}


\begin{exer} \label{exerd1}
Suppose $\Gamma$ proves that $g_1,\dots,g_n$ are functions, and
$R$, $f$, and the $g_i$ are $\Gamma$ provably $\lD_1$. Show that 
$R(g_1(\vec y),\dots, g_n(\vec y))$ and 
$f(g_1(\vec y),\dots, g_n(\vec y))$ are also $\Gamma$ provably
$\lD_1$. 
\end{exer}




We now catalog some of the simple set-theoretic relations and
functions which are absolute in view of lemmas~\ref{d0}~\ref{abud}.
It is of some interest to keep track of how much of $\zfc$ we need
to get the absoluteness, so first we consider what we can prove absolute
just in $\zf-$Power$-$Replacement. 


\begin{lem} \label{ablist}
Let $M \subseteq N$ be sets or classes with $M$ transitive, and
assume $M,N$ are models of  $\zf-$Power$-$Replacement. Then the following
are absolute between $M$ and $N$.

\begin{tabular}{lll}
a.) $x \in y$ & b.) $x=y$ & c.) $ x \subseteq y$ \\
d.) $\{ x,y\}$ & e.) $\langle x,y \rangle$ & f.) $x \cup y$ \\
g.) $x \cap y$ & h.) $\cup x$ & i.) $\cap x$ \\ 
j.)  $S(x)=x \cup \{ x\}$ & k.) $x$ is transitive & l.) $x$ is an
ordered pair \\
m.) $R$ is a relation. & n.) $\dom(R)$ & o.) $\ran(R)$ \\
p.) $R$ is a function & q.) $R$ is a one-to-one function & r.) $y=R(x)$\\
s.) $0$ & t.) $1$ & u.) $2$ etc.

\end{tabular}
\end{lem}



\begin{proof}
All of these functions and relations are 
provably $\lD_0$ from 
 $\zf-$Power$-$Replacement, hence are absolute. 
We consider a few examples from the above list. 

Consider (d), the function $(x,y) \to \{ x,y \} $. 
Let $\phi(x,y,z)=[x \in z \wedge y \in z \wedge \forall w \in z \ 
(w\approx x \vee w \approx y)]$. Clearly $\phi \in \lD_0$ and defines
the graph of this function. The pairing axiom, comprehension
 and extensionality axioms
imply that $\phi$ is the graph of a total function. 


For (e), the function $(x,y) \to \langle x, y \rangle$ consider
$\phi(x,y,z)=[\exists u \in z\ \exists v \in z\ 
( \forall w \in z\ (w \approx u \vee w \approx v) 
\wedge $``$u=\{ x\}$''$\wedge $``$v= \{ x,y\}$''$)]$, where
for ``$u=\{ x,y\}$'' we use the $\lD_0$ formula of (d).
So, $\phi$ is $\lD_0$ and again  $\zf-$Power$-$Replacement
proves $\phi$ is the graph of a function. 


For (l), $x$ is an ordered pair, use the formula 
$\phi(x)= [\exists u \in x\  
\exists y \in u \ \exists z \in u \ (x=\langle 
y,z\rangle)]$. For (m) use $\phi(R)= 
[\forall x \in R \ $``$x$ is an ordered pair''$]$.
\end{proof}


\begin{exer}
Show (n), that is, the function $R \to \dom(R)$ is provably
$\lD_0$ from  $\zf-$Power$-$Replacement (you may take the 
function to be $0$ if $R$ is not a relation). 
\end{exer}




For the function $(x,y) \to x \times y$ we can use the formula
$\phi(x,y,z)=[(\forall u \in x\ \forall v \in y\ \exists w \in z\ 
w=\langle x,y \rangle) \wedge (\forall w \in z\ \exists u \in x \ 
\exists v \in y\ w=\langle x,y \rangle)]$. Substituting for 
$w=\langle x,y \rangle$ we see that $\phi \in \lD_0$. However, 
to prove that $\phi$ is the graph of a total function seems
to need either replacement or power set (for power set
use the fact that $x \times y \subseteq \sP \sP (x \cup y)$ and 
comprehension).


The absoluteness results of lemma~\ref{ablist} did not actually
use that $M,N$ satisfy foundation. The next result on the absoluteness
of the ordinals does. 


\begin{lem}
If $M \subseteq N$ are models of  $\zf-$Power$-$Replacement 
and $M$ is transitive, then $\on$ is absolute between $M$ and $N$. 
That is, if $x \in M$ then $(x$ is an ordinal$)^M \leftrightarrow
(x$ is an ordinal$)^N$. 
\end{lem}



\begin{proof}
Let 
\begin{equation*}
\begin{split}
\phi(x) & \leftrightarrow [( x \text{ is linearly ordered by } \epsilon) 
\wedge (x \text{ is transitive })] \\
& \leftrightarrow [ \forall y \in x\ \forall z \in x\ 
(y \in z \vee y \approx z \vee z \in y) \\ & \quad \wedge 
\forall y \in x\ \forall z \in x\ (y \in z \rightarrow 
\neg(y \approx z \vee z \in y) \\ & \quad \wedge
\forall y \in x \ \forall z \in x\ \forall w \in x\ (
y \in z \wedge z \in w \rightarrow y \in w) \wedge \forall y \in x\ 
\forall z \in y\ (z \in x) ]
\end{split}
\end{equation*}
Clearly $\phi$ is $\lD_0$ and so absolute between $M$ and $N$. 
Suppose now $x \in M$ and $(x$ is an ordinal$)^M$. 
Then $\phi^M(x)$ and so $\phi^N(x)$. Since $N$ satisfies foundation, 
the $\epsilon$ relation is also wellfounded on $x$. Thus, 
$(x$ is an ordinal$)^N$. The other direction is similar.
\end{proof}


\begin{exer}
Let $R$ be the relation defined by $R(n,m) \leftrightarrow
(n, m \in \omega) \wedge \langle n,m \rangle +1$ is prime, where 
$\langle n,m \rangle =2^{n+1} 3^{m+1}$ is the standard coding function.
Show that $R$ is absolute between models $M \subseteq N$ 
of $\zf-$Power$-$Replacement, with $M$ transitive. If $R$ provably $\lD_0$?
\end{exer}




The point of the previous proof is that the wellfoundedness
condition in the definition of an ordinal is gotten for 
``free'' as the models satisfy foundation. For general relations, 
note that 
\begin{equation*}
\begin{split}
\phi(A,R) & \leftrightarrow  (R \text{ is a wellfounded relation on } A)
\\ & \leftrightarrow \forall x\ ((x \subseteq A \wedge x \neq \emptyset) 
\rightarrow \exists y \in x\ \forall z \in x \ 
(\neg \langle z, y \rangle \in R))
\end{split}
\end{equation*}
is $\lP_1$. Thus for general $M \subseteq N$ with $M$
transitive we have that wellfoundedness is downwards absolute. In
general, it may fail to be upwards absolute. A very basic and important
result, however, says that if $M,N$ satisfy enough of $\zf$, in
particular enough of replacement, then wellfoundedness
is also upwards absolute between $M$ and $N$. 


\begin{thm} \label{abwf}
Suppose $M \subseteq N$ satisfy $\zf-$Power and $M$
is transitive. Then wellfoundedness is absolute between $M$ and $N$. 
That is, if $(A,R) \in M$, then $(R$ is a wellfounded relation on $A)^M
\leftrightarrow (R$ is a wellfounded relation on $A)^N$. 
\end{thm}


\begin{proof}
Suppose $A$, $R$ are in $M$, and $(R$ is a wellfounded relation on $A)^M$
(we already know wellfoundedness is downwards absolute). 
Since $M$ satisfies $\zf-$Power, the transfinite recursion
theorem holds in $M$, and thus in $M$ there is a ranking 
function $f \colon A \cap M \to \on^M$ which we recall is defined
recursively by
$$
f(x)= \sup \{ f(y) +1 \colon \langle y,x \rangle \in R.
$$
Since $M$ is transitive, $f$ is defined on all of $A$. At any rate,
if 
\begin{equation*}
\begin{split}
\phi(A,R,f)= & (f \text{ is a function }) \wedge 
(\dom(f)=A) \wedge (\forall x \in A\ f(x) \in \on) \\ & \wedge
\forall x \in A\ \forall y \in A\ (
\langle x, y \rangle \in R \rightarrow  f(x) \in f(y))
\end{split}
\end{equation*}
then $\phi$ is provably $\lD_0$ in $\zf-$Power$-$Replacement and
so is absolute between $M$ and $N$. Since $\phi(A,R,f)^M$
for our particular $A$, $R$, and $f$, it follows that 
$\phi(A,R,f)^N$. Thus, $N$ has a ranking function on $(A,R)$
and so  $(R$ is a wellfounded relation on $A)^N$.
\end{proof}

 
Note that the above argument in fact shows that 
$\psi(A,R) \leftrightarrow (R$ is a wellfounded relation on $A)$ 
is provably $\lD_1$ from $\zf-$Power, since in this theory it
is provably equivalent to $\exists f\ \phi(A,R,f)$.

Theorem~\ref{abwf} used the fact that the ranking function,
defined by transfinite recursion, is absolute between transitive
models of $\zf-$Power. Many other functions of interest are also
defined by transfinite recursions, and we would like to know
that they are absolute as well. The next theorem says that this is 
in fact the case, provided that the function giving the 
recursive definition is absolute.



\begin{thm} \label{abtrans}
Let $M \subseteq N$ be sets or classes which satisfy 
$\zf-$Power, with $M$ transitive. 
Let $A,R$ be classes which are absolute between $M$ and $N$ and
$R$ is wellfounded on $A)^N$. 
Assume also that $(R$ is set-like on $A)^M$,
$(R$ is set-like on $A)^N$, and 
for any $x \in A^M$ that $pred(x,R)^N \subseteq M$. 
Finally, assume $F$ is a class function which is absolute between
$M$ and $N$ and $M,N$ both satisfy that $\forall x \in A\ 
\forall y\ \exists ! z\ F(x,y)=z$. 
Then the class function $G$ defined in the proof of the transfinite recursion
theorem is absolute between $M$ and $N$ and in both $M,N$ satisfies 
the recursive definition 
$G(x)=F(x, G \restriction \pred(x,R))$. 
\end{thm}


\begin{proof}
Note that $R$ is wellfounded on $A)^M$ by an easy downwards absoluteness
argument (any non-empty subset of $A^M$ in $M$ is also a non-empty
subset of $A^N$ in $N$). 
Since both $M,N$ satisfy $\zf-$Power, the transfinite recursion theorem
in $M$ and $N$ shows that in both classes $G$ is a function
defined on $A$ and satisfies the recursive definition. 
It remains to show that for any $x \in A^M$ that $G^M(x)=G^N(x)$. 
If not, let $x \in A^M$ be $R^M$ minimal such that $G^M(x) \neq
G^N(x)$. Since $\pred(x,R)^M=\pred(x,R)^N$, by minimality of $x$
we have $G^M \restriction \pred(x,R)^M =
G^N \restriction \pred(x,R)^N$. Since $F$ is absolute between
$M$ and $N$ and both $G^M, G^N$ satisfy the recursive definition,
it now follows that $G^M(x)=G^N(x)$.
\end{proof}



All of the absoluteness theorems for $M \subseteq N$
require that $M$ be transitive. The next result shows that transitivity
is, in some sense, not too restrictive an assumption.


\begin{thm} \label{coll}
Let $E$ be a wellfounded relation on the set $M$, and suppose
$(M,E)$ satisfies the axiom of extensionality ($\forall x, y\ 
(x = y \leftrightarrow \forall z\ (z \in x \leftrightarrow z \in y))$).
Then there is an isomorphism $\pi \colon (M,E) \to (N,\in)$
for some transitive set $N$. 
\end{thm}


\begin{proof}
Define $\pi$ by transfinite recursion by 
$\pi(x)=\{ \pi(y) \colon y \in M \wedge yE x\}$. 
Let $N= \{ \pi(x) \colon x \in m\}$. $N$ is transitive since
if $u \in v \in N$, then $v= \pi(x)=
\{ \pi(y) \colon y \in M \wedge yE x\}$ for some $x \in M$, and hence
$u=\pi(y)$ for some $y \in M$, so $u \in N$. 
If $xEy$ are in $M$, then by definition $\pi(x) \in \pi(y)$,
so $\pi$ preserves the $E$ relation. Finally, $\pi$ is 
one-to-one. To see this, suppose $x \neq y$ are in $M$ and
$\pi(x)=\pi(y)$. We may assume $x,y$ are chosen to minimize
$\max \{ |x|_E,|y|_E\}$.
since $M$ satisfies extensionality, there is a $z \in M$ such that
(without loss of generality) $z \in x$ and $z \notin y$. 
Clearly $\pi(z) \in \pi(x)$. If $\pi(z) \in \pi(y)$, there there 
would be a $w \in y$ such that $\pi(z)=\pi(w)$.  Necessarily 
$w \neq z$. Since $\max \{ |z|_E, |w|_A\} < 
\max \{ |x|_E,|y|_E\}$, we have a contradiction.
\end{proof}


The map $\pi$ in theorem~\ref{coll} is called the {\em Mostowski collapse}. 


\begin{exer}
Show that if $A \subseteq \on$ and $\pi \colon (A, \in ) \to 
(\alpha, \in)$ is the collapse, then $\alpha$ is an ordinal. 
Furthermore, $\alpha= \ot(A,E)$, and for $x \in A$, 
$\pi(x)=$ the rank of $x$ in $A$.
\end{exer}


\begin{exer}
Show that if $(M,\in) \subseteq (N,\in)$ and $M$ is
transitive, then the collapse of $N$ is the identity on
$M$.
\end{exer}




\section{Skolem Functions}


In the previous section we consider absoluteness results 
of a general nature; they held for all $M \subseteq N$
with $M$ transitive. We now consider how to construct 
subsets (or classes) inside a given $M$ which will 
absolute for given formulas. The idea is
simply to close under existential witness functions.



Let $M$ be a set or class, and $\phi=\phi(x_1,\dots,x_n)$
be an existential formula, say $\phi= \exists y \psi(\vec x, y)$. 
A {\em skolem function} $s_\phi$ corresponding to $\phi$ is a set or
class function $s_\phi \colon M^n \to M$ such that for all 
$a_1,\dots,a_n \in M$, if $\exists y \in M\ \psi(\vec x, y)$, then
$\psi(\vec x, s_\phi(\vec x))$. Note that if $M$ is a class, the statement
that $s_\phi$ is a skolem function for $M$ is expressible by 
a legitimate formula of set theory. To deal with some problems 
concerning the axiom of choice, we also consider the notion of a 
weak skolem function. This is a set or class function 
$s_\phi \colon M^n \to \sP(M)$ such that for all 
$a_1,\dots,a_n \in M$, if $\exists y \in M \ \psi(\vec x, y)$, then 
$\exists y \in s_\phi(\vec x)\ \psi(\vec x, y)$. If $A \subseteq 
M$, we say $A$ is closed under the skolem function $s_\phi$ 
(or weak skolem function) if whenever $a_1,\dots, a_n \in A$, then 
$s_\phi(\vec a) \in A)$ (or $\forall y \in s_\phi(\vec a)\ 
(y \in A)$ respectively). With a slight abuse, we consider
skolem function to also be weak skolem functions. 


The next lemma shows that closure under existential witnesses 
is enough to guarantee absoluteness. Note that transitivity
is not being assumed. 


\begin{lem} \label{witness}
Let $M$ be a set or class, and $A \subseteq M$ a set or class. 
Let $\phi(x_1,\dots, x_n)$ be a formula in the language of
set theory (which we assume is written using only existential
quantifiers, i.e., replace $\forall $ by $\neg \exists \neg$). 
Let $\phi_1,\dots,\phi_k$ denote the subformulas of $\phi$
which are existential, say $\phi_i(\vec x, \vec y)=
\exists z\ \psi(\vec x, \vec y, z)$. Assume that for all 
$i$ we have:
$$
(*) \forall \vec a \in A\ [ \exists z \in M\ \psi_i^M(\vec a, z) 
\rightarrow \exists z \in A\ \psi_i^M(\vec a, z)].
$$
Then $\phi$ is absolute between $A$ and $M$. 
\end{lem}


\begin{proof}
We prove by induction on the length of the formula that all 
subformulas of $\phi$ are absolute between $A$ and $M$. 
Let $\alpha(\vec x, \vec y)$ be a subformula of $\phi$. 
If $\alpha= \neg \beta$ or $\alpha= (\beta \vee \gamma)$,
the result follows immediately by induction. So assume 
$\alpha= \phi_i=\exists z\ \psi_i(\vec x, \vec y, z)$ is 
existential. Fix $\vec a \in A$. If $\alpha^M(\vec a)$ then 
$\exists z \in M\ \psi^M_i(\vec a, z)$ and by $(*)$
then $\exists z \in A\ \psi^M_i(\vec a, z)$. By induction
we then have $\exists z \in A\ \psi^A_i(\vec a, z)$, so 
$\alpha^A(\vec a)$. The other direction follows similarly, 
without using $(*)$. 
\end{proof}


\begin{cor}
Let $A \subseteq M$ be sets or classes, and $\phi$ a formula
in the language of set theory. If $A$ is closed under skolem 
functions, or weak skolem functions, $s_{\phi_i}$ corresponding
to the existential subformulas of $\phi$, then $\phi$ is
absolute between $A$ and $M$. 
\end{cor}


It is important to note that for any finite list of formulas
$\phi_1,\dots,\phi_n$, there are only finitely many skolem
functions that $A$ needs to be closed under to guarantee
the absoluteness of the $\phi_i$ between $A$ and $M$. 


The next lemma shows that for any set $M$ and 
existential formula $\phi$, a skolem function $s_\phi$ for $M$
exists assuming $\zfc$, and if $M$ is a class then a weak skolem
function exists (without assuming choice).


\begin{lem}
Assuming $\zfc$, for any set $M$ and existential formula $\phi$,
a skolem function $s_\phi$ for $M$ exists. 
Assuming $\zf$, for any class $M$ and existential formula $\phi$,
a weak skolem function $s_\phi$ for $M$ exists. 
\end{lem}


\begin{proof}
Let $\phi(x_1,\dots,x_n)=\exists y\ \psi(\vec x, y)$
be an existential formula. 
If $M$ is a set, let $\prec$ be a wellorder of $M$. 
Define $s_\phi(\vec a)=$ the $\prec$ least $y \in M$ such that
$\psi(\vec a, y)$ is one exists, otherwise set $s_\phi(\vec a)=
a_0$ for some fixed $a_0 \in M$. By comprehension $s_\phi$
exists as a set. Suppose now $M$ is a class. Let 
$s_\phi(\vec a)=M \cap V_\alpha$, where $\alpha$ is least so that 
$\exists y \in M \cap V_\alpha\ (\phi(\vec a, y))$, if 
$\exists y \in M\ \phi(\vec a, y)$, and otherwise 
set $\phi(\vec a)=a_0$. It is easy to check that
$s_\phi$ is a class.
\end{proof}


As a corollary we obtain the following theorem.

\begin{thm}(\zf)(Reflection Theorem) \label{reflection}
Let $\phi_1,\dots,\phi_n$ be finitely many formulas in the language of
set theory. Then there is an $\alpha \in \on$ such that 
all of the $\phi_i$ are absolute between $V_\alpha$ and $V$.
\end{thm}


\begin{proof}
Let $\psi_1,\dots,\psi_m$ be the existential subformulas
of the $\phi_i$, and let $s_1,\dots,s_m$ be the corresponding 
weak skolem functions for $V$. Starting with $\alpha_0=0$, we define
an increasing sequence of ordinals $\alpha_i$, for $i < \omega$. 
Let 
$$\alpha_{i+1}= \sup \{ s'_i (\vec a) \colon i \leq m \wedge 
\vec a \subset V_{\alpha_i} \} \cup  (\alpha_i+1),
$$
where $s'_i(\vec a)=$least $\beta \in \on$ such that $s_i(\vec \alpha)
\subseteq V_\beta$. Let $\alpha=\sup_i \alpha_i$. Note that the map 
$\alpha_i \to \alpha_{i+1}$ exists by a legitimate application
of replacement, since all of the $s_j$ are classes. 
Clearly $V_\alpha$ is closed under the weak skolem functions, and
so all of the $\phi_j$ are absolute between $V_\alpha$ and $V$.
\end{proof}


As a corollary we get that $\zf$ or stronger theories are not
finitely axiomatizable.


\begin{cor}
Let $T$ be a consistent theory in the language of set theory extending
$\zf$. Then $T$ is not finitely axiomatizable. That is, there does
not exist a finite set $\phi_1,\dots,\phi_n \in T$ such that 
$\{ \phi_1,\dots,\phi_n\} \proves \psi$ for all $\psi \in T$.
\end{cor}


\begin{proof}
Suppose to the contrary that $\{ \phi_1,\dots, \phi_n\}
\proves T$. Since $T \proves \phi_i$ for each $i$, by the reflection
theorem $T \proves \exists \alpha ( \phi_1^{V_\alpha} \wedge \dots
\wedge \phi_n^{V_\alpha})$. Working from $T$, let $\alpha \in \on$
be the least ordinal such that 
$\phi_1^{V_\alpha} \wedge \dots \wedge \phi_n^{V_\alpha}$. 
Now, the reflection theorem for $\phi_1,\dots,\phi_n$ is a theorem
of $\zf$, and as such uses only finitely many of the axioms of 
$\zf$ in its proof. By assumption, for each of these axioms 
$\psi$ we also have $\psi^V_{\alpha}$. But then we may apply the
reflection theorem within $V_\alpha$ to get that 
$\exists \beta < \alpha \ (\phi_1^{V_\beta} \wedge \dots
\wedge \phi_n^{V_\beta})$ (note that $(V_\beta)^{V_\alpha}=V_\beta$
by absoluteness of rank; we assume the $\psi$'s contain enough
formulas so that rank is absolute between $V_\alpha$ and $V$). 
This violates the minimality of $\alpha$.
\end{proof}



In the above theorems we considered a finite list of formulas
$\phi_1,\dots,\phi_n$. One must be a bit careful when considering an
infinite set of formulas (for example, all of $\zfc$).  First, to
even precisely state any results in this case, we must formalize the
syntax so that we can discuss all of the formulas at once. This is not
a problem, we did this when discussing G\"odel's theorem. The exact
formalization of the syntax is not important, let us just assume we
have a bijection $n \to \theta_n$ between $\omega$ and the formulas in
the language of set theory. We assume the bijection is reasonable in
that simple syntactical operations on the formulas correspond to
recursive functions on $\omega$, and the code of any subformula of
$\phi$ is smaller than the code of $\phi$.
The basic problem is that the ``relation'' $(n,x)$ iff 
$\theta_n(x)$ is not a legitimate class. That is, there is no
single formula which defines definability in $V$ for all formulas. 
To see this, suppose there were such a formula $\psi(n,x)$, that is,
for all formulas $\theta=\theta_n$, $\zfc \proves 
\psi(n,x) \leftrightarrow \theta(x)$. As in the proof of
theorem~\ref{reflection}, we construct a sequence $\alpha_i \in \on$
such that 
$$\forall n \in \omega\ \forall \vec x \in V_{\alpha_i}\ 
[\exists y\ \psi(n, \langle \vec x, y \rangle) \rightarrow 
\exists y \in V_{\alpha_{i+1}} \psi(n, \langle \vec x, y \rangle)].
$$
Let again $\alpha=\sup_i \alpha_i$. Then $\chi(\alpha)$, where
$$
\chi(\alpha)= \forall n\ \forall \vec x \in V_\alpha\ 
[\exists y\ \psi(n, \langle \vec x, y \rangle) \rightarrow 
\exists y \in V_{\alpha_{\alpha}} \psi(n, \langle \vec x, y \rangle)].
$$
So, $\zf \proves \exists \alpha\ \chi(\alpha)$. 
Since each existential formula $\phi(\vec x)$ is equivalent
to one of the form 
$\phi(\vec x)= \exists y\ \theta_n(\langle \vec x, y \rangle)$,
if follows from lemma~\ref{witness} that for each formula 
$\theta(\vec x)$ in the language of set theory that 
$\zf \proves \forall \vec a \in V_{\alpha}\ (\theta(\vec x)
\leftrightarrow \theta^{V_\alpha}(\vec x))$. 
Let $\beta$ be the least ordinal ordinal so that $\chi(\beta)$
holds. Let $\psi_1,\dots,\psi_l$ be enough of $\zf$ so that 
$\{\psi_1,\dots,\psi_l\} \proves \exists \alpha \chi(\alpha)$. 
Since $\zf \proves \psi_j^{V_\beta}$ for $j=1,\dots,l$, 
it follows that $\zf \proves (\exists \alpha\ \chi(\alpha))^{V_\beta}$.
So, $\zf \proves \exists \alpha < \beta\ \chi(\alpha)$, a 
contradiction. 


If $M$ is a set, however, it is an important fact that we can 
``define definability'' over the set $M$. More precisely, 
we have the following lemma.


\begin{lem} \label{setdef}
There is a formula $\rho(n,x,M)$ in the language of set theory
such that for all sets $M$ and $n \in \omega$, $\zf \proves 
(\theta_n(\vec x))^M \leftrightarrow \rho(n, \langle \vec x \rangle, M)$.
\end{lem}


Thus, roughly speaking, $\rho(n,x,M)$ asserts that the $n^{\text{th}}$
formula holds in $M$ at $(x_1,\dots,x_m)$, where $x= \langle x_1,
\dots,x_m \rangle$. For $n \in \omega$, let $r(n)$ be such that
all of the variables in $\theta_n$ occur among $x_1,\dots,x_{r(n)}$.
Let $s(n)$ be such that $\theta_n=\theta_n(x_1,\dots,x_{s(n)})$. 


\begin{proof}
Let 
\begin{equation*}
\begin{split}
\rho(n,x,M) & \leftrightarrow 
\exists f\ [ f \text{ is a function } \wedge \dom(f)=n+1 \wedge 
\\ &\forall i \leq n ( (\theta_i=(x_k \in x_l)) \rightarrow 
\forall z \ (z \in f(i) \leftrightarrow z \in M^{r(n)} \wedge z(k) \in z(l)))
\\ & \wedge 
\forall i \leq n ( (\theta_i=(x_k \approx x_l)) \rightarrow 
\forall z \ (z \in f(i) \leftrightarrow z \in M^{r(n)} \wedge z(k) = z(l)))
\\ & \wedge
\forall i, j \leq n ( (\theta_i=(\neg \theta_j)) \rightarrow 
\forall z \ (z \in f(i) \leftrightarrow z \in M^{r(n)} \wedge z \notin f(j)))
\\ & \wedge
\forall i, j,k \leq n ( (\theta_i=(\theta_i \vee \theta_j) \rightarrow 
\forall z \ (z \in f(i) \leftrightarrow z \in f(j) \vee z \in f(j)))
\\ & \wedge 
\forall i, j \leq n ( (\theta_i=(\exists x_k \theta_j)) \rightarrow 
\forall z \ (z \in f(i) \leftrightarrow z \in M^{r(n)} \wedge 
\\ & \quad \quad \exists u \in f(j) \ ( \forall l \neq k\ (z(l)=u(l))))) 
\\ & \exists z \in f(n)\ ( z \restriction s(n)= x) ]
\end{split}
\end{equation*}
The formula $\rho$ is written out in enough detail so that one can see
it is a legitimate formula in the language of set theory. 
In any model of $\zf$ (in fact, $\zf-$Power$-$Replacement), 
one can easily see that for any $n \in \omega$ and any set $M$, there
is a function $f$ as in the formula $\rho$. Also, a straightforward induction
on $m$ shows that for any $m \leq n$ and any function $f$
as in the statement $\rho$, if $m$ codes a formula then 
$f(m)= \{ z \in M^{r(n)} \colon \theta_m(z')\}$ where $z'$ is obtained by
restricting $z$ to the free variables of $\theta_m$. In particular, 
$f(n)= \{ z \in M^{r(n)} \colon \theta_n(z \restriction s(n) )\}$. 
\end{proof}



As a consequence of this, we can define (working in $\zfc$) 
skolem functions for a set $M$ for all existential formulas simultaneously. 


\begin{lem} ($\zfc$)
For all sets $M$ there is a sequence of functions $s_n$, for each 
$n$ such that $\theta_n=\exists y\ \psi_n(\vec x,y)$ is an 
existential formula, such that $s_n$ is a skolem function for $\theta_n$
for $M$.
\end{lem}



\begin{proof}
Let $\rho(n,x,M)$ be the formula of lemma~\ref{setdef}. 
Fix a wellordering $\prec$ of $M$. Define
\begin{equation*}
\begin{split}
(s_n(\vec x)=y) \leftrightarrow & (\theta_n \text{ is of the form } 
\exists y\ \theta_m( \vec x, y) \wedge \rho(m, \langle \vec x, y \rangle,M) 
\wedge \\ & \forall z \prec y\ \neg ( \rho (m, \langle \vec x, z \rangle,M))).
\end{split}
\end{equation*}
\end{proof}


From this, we immediately get the following absoluteness result.


\begin{thm}($\zfc$)
Let $A \subseteq M$ be sets. Then there is a set $B$ with $A \subseteq B 
\subseteq M$ with $|B|=|A|$ and such that all formulas $\phi$
are absolute between $B$ and $M$. That is, $B \prec M$, i.e., $B$ 
is an elementary substructure of $M$. 
\end{thm}

\begin{proof}
Let $s_n$ be skolem functions for $M$. Let $B$ be the closure of $A$
under the $s_n$ (i.e., $B = \bigcup_n B_n$ where $B_0=A$ and 
$B_{n+1}= \bigcup_m S_m [B_n]$). From lemma~\ref{witness}, $B$
is an elementary substructure of $M$.
\end{proof}









\end{document}
