\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}