language hipsters also have never used C#, if they had they

AC is not refutable in ZF - Part 4
Wed, 12 Oct 2011 21:39:00 GMT

So, finally, this is part 4 of my series about the irrefutability of the AC from ZF. We are almost there!

Theorem 1: Let ZF-Formulae $\phi_0(\vec{x}),\ldots,\phi_n(\vec{x})$ be given. Then $\forall_\alpha\exists_{\beta\ge\alpha}\forall_{\vec{x}\in V_\beta} \bigwedge\limits_{i=0}^n (\phi_i(\vec{x})\leftrightarrow\phi_i^{V_\beta}(\vec{x}))$ . We then say that $V_\beta$ reflects the $\phi_i$ .
Proof: Let $\alpha$ be given. Without loss of generality we may assume that the $\phi_i$ can be written without universal quantifiers, as we can replace every universal quantifier by a negated existential quantifier of the negated quantfied formula.
Recursively define a sequence $\left<\beta_n \mid n<\omega\right>$ where $\beta_0=\alpha$ and $\beta_{n+1}$ is the smallest ordinal $\gamma>\beta_n$ , such that if $\exists_y\theta(\vec{z},y)$ is a subformula of one of the $\phi_i$ , we have $\forall_{\vec{z}\in V_{\beta_n}}((\exists_y\theta(\vec{z},y))\rightarrow\exists_{y\in V_\gamma}\theta(\vec{z},y))$ . Let $\beta$ be the supremum of the $\beta_i$ . It is sufficient to show that for all subformulae $\psi(\vec{z})$ of any $\phi_i$ we have $\forall_{\vec{z}\in V_\beta}(\psi(\vec{z})\leftrightarrow\psi^{V_\beta}(\vec{z}))$ , which goes by structural induction. If $\psi$ is of the form $x\in y$ this is trivial. The step over $\rightarrow,\wedge,\bot$ is clear. We can assume that every occurence of $\forall$ is in the scope of an occurence of $\exists$ , and therefore, instead of having an induction step for $\forall$ , we have an induction step for $\exists$ : $\psi=\exists_y\theta(\vec{z},y)$ , and let $\vec{z}\in V_\beta$ . By induction hypothesis, $\psi^{V_\beta}(\vec{z})\rightarrow\psi(\vec{z})$ . For the other direction, let $\exists_y\theta(\vec{z},y)$ , then $\exists_y\in V_{\beta_{n+1}}\theta(\vec{z},y)$ . By induction hypothesis, we have $\exists_{y\in V_\beta}\theta^{V_\beta}(\vec{z},y)$ .

□

We can do everything we did in Part 1 as well directly in ZF. Alphabets become sets, and formulae become finite sequences. Especially, there is a set of all formulae, which is countable. Notice that there is no need to fix a special "encoding" for formulae, it is clear that one exists, and it is clear that all such encodings have to be equivalent. For a ZF-formula $\phi$ , let $\lceil\phi\rceil$ be its embedding into ZF, that is, $\lceil\phi\rceil$ is a set.

For every set $u$ we can define an interpretation, interpreting $\in$ by $\{\left<x,y\right>\in u\times u \mid x\in y\}$ . We write $u\models \phi$ if this interpretation (for all valuations) models $\lceil\phi\rceil$ , notice that in this case, $\models$ is a relation inside ZF. Trivially, we have $\forall_{\vec{a}\in u}((u\models\phi(\vec{a})) \Leftrightarrow\phi^u(\vec{a}))$ .

Definition: Now we can define the class of $OD$ of ordinal definable sets:

$OD:=\{x \mid \exists_{\alpha\in On}\exists_{\vec{p}\in\alpha}\exists_{\lceil\phi\rceil} x=\{y\in V_\alpha \mid V_\alpha\models \phi(y,\vec{p})\}\}$

where we write $\exists_{\lceil\phi\rceil}$ to denote that there must exist an encoded ZF-formula.

This class is interesting, as it messes around with the intuition about two meta-layers. However, it is not yet our goal.

Definition: The transitive closure $TC(x)$ of a set $x$ is the smallest $y\supseteq x$ such that every element of $y$ is also subset of $y$ .

Definition: The class $HOD$ of hereditary ordinal definable sets is defined by

$HOD:=\{x \mid TC(\{x\})\subseteq OD\}$

Since $x\in TC(\{x\})$ , trivially $HOD\subseteq OD$ .

Lemma 1: $x\in HOD \Leftrightarrow x\in OD\wedge x\subseteq HOD$ .
Proof: "=>": From $x\in HOD$ directly follows $TC(\{x\}\subseteq OD$ , therefore, $x\in OD$ . For $y\in x$ we have $TC(\{y\})\subseteq TC(\{x\})\subseteq OD\subseteq HOD$ , that is, $y\in HOD$ , therefore, $x\subseteq HOD$ .
"<=": For $x\in OD$ and $TC(\{x\})\subseteq HOD$ we have $TC(\{x\})=\{x\}\cup\bigcup_{y\in x} TC(\{y\})\subseteq OD$ . Therefore, $x\in HOD$ .

□

Lemma 2: For every ZF-formula $\phi(x,\vec{y})$ we have $\forall_{\vec{\gamma}\in On}(\{x \mid \phi(x,\vec{\gamma})\}\in V\rightarrow\{x \mid \phi(x,\vec{\gamma})\}\in OD$ .
Proof: Let $\{x \mid \phi(x,\vec{\gamma)}\in V$ , $\alpha$ such that $\{x \mid \phi(x,\vec{\gamma)}\in V_\alpha$ , and $\vec{\gamma}<\alpha$ . By Theorem 1 there is a $\beta\ge\alpha$ such that $V_\beta$ reflects $\phi$ , therefore $\{x \mid \phi(x,\vec{\gamma})\} = \{x\in V_\beta \mid \phi^{V_\beta}(x,\vec{\gamma})\} = \{x\in V_\beta \mid V_\beta\models\phi(x,\vec{\gamma})\}\in OD$ .

□

Theorem 2: $HOD$ is an inner model.
Proof: Due to Part 3, it is sufficient to show (I1), (I2) and (I3). By Lemma 1, (I1) holds.
Let $x\subseteq HOD$ , and $\alpha$ such that $x\subseteq V_\alpha$ . Then trivially, $x\subseteq V_\alpha\cap HOD$ . But by Lemma 2 we have $V_\alpha\cap HOD=\{x \mid x\in V_\alpha\wedge x\in HOD\}\in OD$ . Trivially, we also have $V_\alpha\cap HOD\subseteq HOD$ , so by Lemma 1, $V_\alpha\cap HOD\in HOD$ . Thus, (I2) holds.
For (I3), let $\phi(x,\vec{z})$ be a $\Sigma_0$ -formula, choose arbitrary $\vec{z},u\in HOD$ , and let $a=\{x\in u \mid \phi(x,\vec{z})\}$ . Then $a\subseteq u\subseteq HOD$ by (I1), so by Lemma 1, it is sufficient to show that $a\in OD$ . As $HOD\subseteq OD$ we have $\vec{z},u\in OD$ , therefore there are $\vec{\lceil\phi\rceil},\lceil\psi\rceil$ and $\vec{\alpha},\gamma\in On$ and for $i=1,\ldots,n$ there are $p_i\in \alpha_i^{<\omega}$ , $q\in\gamma^{<\omega}$ sucht hat $z_i = \{y\in V_{\alpha_i} \mid V_{\alpha_i}\models\phi_i(y,p_i)\}$ and $u=\{y\in V_\gamma \mid V_\gamma\models\psi(y,q)\}$ . Let $\alpha=\max\{\vec{alpha},\gamma\}$ , and $\chi(x,y)=\lceil y=V_x\rceil$ . By Theorem 1 we get a $\beta>\alpha$ such that $V_\beta$ reflects $\chi$ . Therefore

$a=\{x\in V_\beta \mid V_\beta\models \exists_{\vec{w}}\exists_w(\chi(\gamma, w)\wedge$
$(\bigwedge\limits_{i=1}^n\chi(\alpha_i,w_i))\wedge$
$\exists_{\vec{v}}\forall_y (\psi^w(x,q)\wedge\phi(x,\wedge{v})\wedge\bigwedge\limits_{i=1}^n (y\in v_i\leftrightarrow\phi_i^{w_i}(y,p_i))))\}$

which is in $OD$ . Therefore, $a\in HOD$ .

□

Lemma 3: There exists a surjective functor $F:On\rightarrow OD$ .
Proof: In Part 2 we proved that there is a bijection $G:On\rightarrow\omega\times On^{<\omega}$ , so it is sufficient to give a surjective functor $F:\omega\times On^{<\omega}\rightarrow OD$ . Now let $\left<\phi_n \mid n<\omega\right>$ be an enumeration of all ZF-formulae. Define

$F(n,p) = \left\{\begin{array}{rl} \{x\in V_{p(m)} \mid V_{p(m)}\models\phi_n(x,p \mid _m)\} & \mbox{ for } \operatorname{dom}(p)=m+1 \\ \emptyset & \mbox{ otherwise}\end{array}\right.$

Then $F$ is surjective.

□

Lemma 4: There exists a surjective functor $H:On\rightarrow HOD$
Proof: Since $HOD\subseteq OD$ , use $H=F \mid _{HOD}$ .

□

Theorem: (AC) holds in $HOD$
Proof: By Lemma 4, we have our surjective $H:On\rightarrow HOD$ . For $\alpha\in On$ , define $g_\alpha= H \mid _\alpha$ . By Lemma 2 we know that for every $\alpha$ , $g_\alpha\in OD$ , and since $g_\alpha\subseteq HOD$ , we have $g_\alpha\in HOD$ . Let $u\in HOD$ be arbitrary but fixed. Then there exists an $\alpha$ such that $u\subseteq \operatorname{ran}(g_\alpha)$ . Now define a well-ordering $r\subseteq u\times u$ by

$\{\left<x;y\right> \mid \min\{\gamma \mid x=g_\alpha(\gamma)\}<\min\{\gamma \mid y=g_\alpha(\gamma)\}$

$r$ is a well-ordering, and $r\in HOD$ . Thus, in $HOD$ , the well-ordering theorem holds, therefore, AC holds in $HOD$ .

□

AC is not refutable in ZF - Part 4Wed, 12 Oct 2011 21:39:00 GMT

AC is not refutable in ZF - Part 4
Wed, 12 Oct 2011 21:39:00 GMT