2 Transitive Models

Observation: If $M$ is transitive and $M\models \text{“}e\text{ is empty”}$, then $e=\varnothing$. This is because if $w\in e$, then $w\in e$ and $e\in M$ gives us that $w\in M$ by transitivity, so $M\models w\in e$, so $M\models \text{“}e\text{ is not empty”}$.

2.1 Absoluteness for transitive models

(same for ${\mathrm{\Sigma }}_1^T$, ${\mathrm{\Pi }}_1^T$).

Observation: So, if $M$ is closed under pairing ($\forall x,y\in M,\{x,y\}\in M$), then the pairing operation $x,y\mapsto \{x,y\}$ is absolute, and therefore $M\models \text{Pairing}$.

Similarly for union.

Ordinals

“$x$ is an ordinal” means $x$ is transitive and $(x,\in )$ is a well-order.

We know: being well-founded is not expressible in first-order logic (see Example Sheet 1).

Because all transitive models satisfy Foundation, we have that if $M$ is transitive, then

$$M\models x\text{ is transitive}\wedge (x,\in )\text{ is linearly ordered}.$$

characterises ordinals. But this is clearly in ${\mathrm{\Delta }}_0$.

So: being an ordinal is absolute for transitive models.

Thus $M\cap \mathrm{Ord}=\{x\in M:M\models x\text{ is an ordinal}\}$. This is transitive, thus there is $\alpha \in \mathrm{Ord}$ such that $\alpha =M\cap \mathrm{Ord}$.

Also absolute:

• “$x$ is a successor ordinal” ($\exists y\in TODO$)

• “$x$ is a limit ordinal”

• “$x$ is a non-zero limit ordinal”

• $x=\omega$ TODO

Cardinals

“$x$ is a cardinal” if and only if

$$x\text{ is an ordinal}\wedge \forall f,\forall y\in x,f:y\to x⟹f\text{ is not a surjection}$$

Note that $\forall f$ is not bounded (while $\forall y\in x$ is bounded).

Observe: this is ${\mathrm{\Pi }}_1$ and therefore downwards absolute.

2.2 Non-absoluteness

Assume that $M\models \mathsf{\text{ZFC}}$ is transitive and countable. Then

$$M\cap \mathrm{Ord}=\alpha <{\omega }_1.$$

However, $M\models \mathsf{\text{ZFC}}$ implies $M\models \text{there are uncountable cardinals}$.

Let $\beta <\alpha$ be such that $M\models \beta \text{ is the least uncountable cardinal}$.

But $\beta$ is a countable ordinal, so not a cardinal.

Consequence: All cardinals in $M$ except ${\aleph }_0$ are going to be fake.

So “$x$ is a cardinal” can’t be absolute.

Recall the general proof strategy mentioned before:

If $M$ is a countable transitive set such that $M\models \mathsf{\text{ZFC}}$, then there is a a countable transitive set $N\supseteq M$ such that $N\models \mathsf{\text{ZFC}}+\neg \mathsf{\text{CH}}$.

Question: Is this really solving the original problem? i.e. $\mathrm{Con}(\mathsf{\text{ZFC}})⟹\mathrm{Con}(\mathsf{\text{ZFC}}+\neg \mathsf{\text{CH}})$.

It’s not obvious that $\mathrm{Con}(\mathsf{\text{ZFC}})$ implies that there is a countable transitive model (ctm) of ZFC.

Answer: That’s not only not obvious, but fake.

Let’s prove that $\mathrm{Con}(\mathsf{\text{ZFC}})$ $⁄⟹$ there is a countable transitive model of ZFC.

Why? Note that $\mathrm{Con}(\mathsf{\text{ZFC}})$, or $\mathrm{Con}(T)$ for any $T$ is ${\mathrm{\Delta }}_0$. So, it’s absolute for transitive models.

So if $M$ is a countable transitive model of ZFC, then $\mathrm{Con}(\mathsf{\text{ZFC}})$ is true, so by absoluteness, $M\models \mathrm{Con}(\mathsf{\text{ZFC}})$. So $M\models \mathsf{\text{ZFC}}+\mathrm{Con}(\mathsf{\text{ZFC}})$. This contradicts Gödel’s Incompleteness Theorem.

We can get a proof of

$$\mathrm{Con}(\mathsf{\text{ZFC}})⟹\mathrm{Con}(\mathsf{\text{ZFC}}+\neg \mathsf{\text{CH}})$$

via a trick ( Example Sheet 1).

This reduces the problem to:

Find countable transitive models of $T^{\ast }$ for sufficiently large finite $T^{\ast }\subseteq \mathsf{\text{ZFC}}$.

Paradigmatic example: von Neumann hierarchy $V_{\alpha }$, and $V$ is the entire universe.

TVT${}_{\mathrm{\Phi }}$:

Let $M\subseteq N$ and $\mathrm{\Phi }$ be a collection of formulas closed under subformulas. Then the following are equivalent:

• (i) All formulas in $\mathrm{\Phi }$ are absolute between $M$ and $N$.
• (ii) For all $\phi \in \mathrm{\Phi }$, the TV-condition holds: if $\phi =\exists x\psi$, then for all $\overline{y}\in M$ if there is $a\in N$ sucht hat $N\models \psi (a,\overline{y})$, then there is $b\in M$ such that $N\models \psi (b,\overline{y})$.

Warm-up: let $(M,\in )\models \mathsf{\text{ZFC}}$. Find countable $N\subseteq M$ such that $(N,\in )\prec (M,\in )$.

Suppose $\overline{p}=(p_0,\dots ,p_n)\in M$ and $M\models \exists y,\psi (y,\overline{p})$. Let $w(\psi ,\overline{p})$ be a witness for this:

$$M\models \psi (w(\psi ,\overline{p}),\overline{p})$$

(if necessary, use Axiom of Choice).

(if $M\models \neg \exists y,\psi (y,\overline{p})$, then let $w(\psi ,\overline{p})=\varnothing$).

Set:

$$\begin{array}{llll}\hfill N_0& :=\varnothing & \hfill & \\ \hfill N_{i+1}& :=\{w(\psi ,\overline{p}):\psi \text{ formula and }\overline{p}\in N_1^{<\omega }\}& \hfill & \\ \hfill N& :=\bigcup _{i\in \omega }{N}_i& \hfill & \end{array}$$

Note:

• (1) $N$ is countable.
• (2) $M\prec N$ by Tarski-Vaught Test.

Relevant later!

Also see Example Sheet 1.

Remark about the proof of Levy Reflection Theorem:

Can you do the same if $\mathrm{\Phi }$ is infinite?

Of course not: otherwise we colud prove that there exists $𝜃$ such that $V_{𝜃}\models \mathsf{\text{ZFC}}$, and hence get $\mathrm{Con}(\mathsf{\text{ZFC}})$.

The problem is the case distinction in the definition of $o(\psi ,\overline{p})$: it requires to check whether $\exists y,\psi$ is true.

Next goal: Obtain some $M\subseteq V_{𝜃}$ countable such that $M\models \phi$ and $M$ is transitive.

TODO

The next few lectures will be spent proving $\mathrm{Con}(\mathsf{\text{ZFC}}+\mathsf{\text{CH}})$ using Gödel’s constructible universe.

Absoluteness is preserved under transfinite recursion.

Let $F,G,H$ be three operations.

$$\begin{array}{llll}\hfill R(0,\overline{x})& :=F(\overline{x})& \hfill & \\ \hfill R(\alpha +1,\overline{x})& :=G(\alpha ,R(\alpha ,\overline{x}),\overline{x})& \hfill & \\ \hfill R(\lambda ,\overline{x})& :=H(\lambda ,\{R(\alpha ,\overline{x}):\alpha <\lambda \},\overline{x})& \hfill & \text{(}\ast \text{)}\end{array}$$

Note that for $F,G,H$ fixed, there is a finite fragment $T_{F,G,H}\subseteq \mathsf{\text{ZFC}}$ that proves the recursion theorem instance for $F,G,H$.

Want $T_{F,G,H}⊢L1(F,G,H)$, $T_{F,G,H}⊢L2(F,G,H)$ and $T_{F,G,H}$ proves existence of $R$.

Convention: We say “$T$ is sufficiently strong” if $T\subseteq \mathsf{\text{ZFC}}$ is finite and $T$ proves hte existence of all relevant operations such that they are absolute for transitive models of $T$.

Observe: ${\mathrm{\Delta }}_0^T$ concepts are absolute (upwards from ${\mathrm{\Sigma }}_1$ and downwards from ${\mathrm{\Pi }}_1$).

Typical Applications

Bounding a quantifier by operation.

Let $F$ be an operation and $T$ strong enough to prove $F$ is an operation and absolute.

$$\begin{array}{llll}\hfill T& ⊢\forall x,\exists z,F(x)=z& \hfill & \\ \hfill T& ⊢\forall x,\forall z,\forall z^{\prime },F(x)=z\wedge F(x)=z^{\prime }\to z=z^{\prime }& \hfill & \end{array}$$

Then the quantifiers $\exists y\in F(x)$ and $\forall y\in F(x)$ preserve absoluteness.

$$\begin{array}{llll}\hfill \exists y\in F(x)\psi & ⟺\underset{\text{upwards absolute}}{\underbrace{\exists z\underset{\text{absolute}}{\underbrace{(z=F(x)\wedge \exists y\in z\psi )}}}}& \hfill & \\ \hfill & ⟺\underset{\text{downwards absolute}}{\underbrace{\forall z\underset{\text{absolute}}{\underbrace{(z=F(x)\to \exists y\in z\psi )}}}}& \hfill & \end{array}$$

Applications

• (1) Encode formulas as elements of ${\omega }^{<\omega }$.

  $\in$	$=$	$($	$)$	$\wedge$	$\vee$	$\neg$	$\exists$	$\forall$	$v_0$	$v_1$	$v_2$	$\cdots$
  $0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$\cdots$

  $\forall v_0\exists v_1\neg v_0\in v_1$ would be $(8,9,7,10,6,8,0,10)$.

  $Fml\subseteq {\omega }^{<\omega }$. So, $Fml$ is absolute for some (sufficiently strong) finite fragment of $\mathsf{\text{ZFC}}$ (see Example Sheet 1).

• (2) If $X$ is any set then

  $$\text{“}X\models \phi \text{”}$$

  (which means “$(X,\in )\models \phi$”) is defined by the usual (Tarski) recursion and thus also absolute ( Example Sheet 1).

2.3 The constructible hierarchy

Fix a set $X$. Define for each $\phi \in \mathrm{Fml}$ and each $p\in X^{<\omega }$ (parameter)

$$D(\phi ,p,X):=\{w\in X:X\models \phi (p,w)\}$$

the subset of $X$ defined by $\phi$ with parameter $p$.

For a sufficiently strong $T\subseteq \mathsf{\text{ZFC}}$ finite, we have that $T$ proves that $D$ is an absolute operation (see Example Sheet 1).

$$D(X):=\{D(\phi ,p,X):\phi \in \mathrm{Fml},p\in X^{<\omega }\}.$$

This is absolute for a sufficiently strong theory (use Replacement to get $D(X)$).

This $D(X)$ is sometimes (misleadingly) called the “definable power set of $X$” (it is misleading because it is more like a “definable (by $X$) power set of $X$”).

($\alpha \in D(X)⟺\exists \phi \in \mathrm{Fml},\exists p\in X^{<\omega },a=D(\phi ,p,X)$)

Obvious: $D(X)\subseteq P(X)$. Also: If $X$ is transitive, then so is $D(X)$.

$$\begin{array}{llll}\hfill L_0& :=\varnothing & \hfill & \\ \hfill L_{\alpha +1}& :=D(L_{\alpha })& \hfill & \\ \hfill L_{\lambda }& =\bigcup _{\alpha <\lambda }{L}_{\alpha }& \hfill & \end{array}$$ The constructible hierarchy.

We usually write $L:={\bigcap }_{\alpha \in \mathrm{Ord}}{L}_{\alpha }$.

Claim: $L$ is a hierarchy (in the sense of Lecture). See Example Sheet 1.

By closure of absoluteness under transfinite recursion, the $L$-hierarchy is absolute for transitive models of $T\subseteq \mathsf{\text{ZFC}}$ where $T$ is strong enough to prove that it exists.

i.e. if $M\models T$ transitive and $\alpha \in \mathrm{Ord}\cap M$ and $M\models X=L_{\alpha }$, then $X=L_{\alpha }$. So

$$\bigcup _{\alpha \in \mathrm{Ord}\cap M}{L}_{\alpha }\subseteq M.$$

The main theorem of next lecture will be:

If $L\models \mathsf{\text{ZF}}$ and $M\models \mathsf{\text{ZF}}$ transitive, then

$$\bigcup _{\alpha \in \mathrm{Ord}\cap M}{L}_{\alpha }\models \mathsf{\text{ZF}}.$$

(Minimal $\mathsf{\text{ZF}}$-model).

Some first idea of what the $L$-hierarchy is like

Clearly, by induction, $L_{\alpha }\subseteq V_{\alpha }$, and clearly for $n\in \omega$, $L_n=V_n$. So $L_{\omega }=V_{\omega }$.

$$L_{\alpha +1}:=\bigcup _{\phi \in \mathrm{Fml}}\bigcup _{p\in L_{\alpha }^{<\omega }}\{D(\phi ,p,L_{\alpha })\}.$$

If $\alpha \ge \omega$, then

$$|L_{\alpha +1}|\le {\aleph }_0\cdot |L_{\alpha }^{<\omega }|={\aleph }_0\cdot |L_{\alpha }|.$$

Thus $|L_{\alpha }|=|L_{\alpha +1}|$.

Therefore $\alpha <{\omega }_1$, $|L_{\alpha }|={\aleph }_0$ and $|L_{{\omega }_1}|={\aleph }_1$.

This means: $V_{\omega +1}\ne L_{\omega +1}$ (since the first has size $2^{{\aleph }_0}$, while the second has size ${\aleph }_0$).

Note: This does not mean $V\ne L$. ($V=L$ means $\forall x,\exists \alpha ,x\in L_{\alpha }$).

$V=L$ is called the “axiom of constructibility”.

There is a finite fragment $T_{𝕃}$ of $\mathsf{\text{ZF}}$[!] that proves that all of the operations occuring in the definition of $𝕃$, i.e. $\mathrm{Fml},X^{<\omega },\models ,D,D$ are well-defined and absolute.

Thus, if $M$ is a transitive model of $T_{𝕃}$, then

$$\forall \alpha \in \mathrm{Ord}\cap M,{𝕃}_{\alpha }\in M$$

and thus ${𝕃}_{\alpha }\subseteq M$.

So ${\bigcup }_{\alpha \in \mathrm{Ord}\cap M}{𝕃}_{\alpha }\subseteq M$.

Axioms of ZF

Structural axioms:

• Extensionality:

  $$\forall x,\forall y,(\forall w(w\in x\leftrightarrow w\in y)\to x=y).$$

• Foundation:

  $$\forall x(\exists v,(v\in x)\to \exists m,(m\in x\wedge \forall w,\neg (w\in m\wedge w\in x))).$$

• Infinity:

  $$\exists i,\exists e,(\forall v,\neg v\in e\wedge e\in i)\wedge \forall x,(x\in i\to \exists s,(s\in i\wedge \forall w,(w\in s\leftrightarrow w\in x\vee w=x))).$$

Functional axioms:

• Pairing:

  $$\forall x,\forall y,\exists p,\forall w,(w\in p\leftrightarrow w=x\vee w=y).$$

• Union:

  $$\forall x,\exists v,\forall w,(w\in v\leftrightarrow \exists z,(z\in x\wedge w\in z)).$$

• Powerset:

  $$\forall x,\exists p,\forall w,(w\in p\leftrightarrow \forall v,(v\in w\to v\in x)).$$

• Separation $\phi$:

  $$\forall \overline{p},\forall x,\exists s,\forall w,(w\in s\leftrightarrow w\in x\wedge \phi (w,\overline{p})).$$

• Replacement $\phi$:

  $$\forall \overline{p},[\forall x,\forall y,\forall z(\phi (x,y,\overline{p})\wedge \phi (x,z,\overline{p})\to y=z)]\to \forall x,\exists r,\forall w,(w\in r\leftrightarrow \exists y,(y\in x\wedge \phi (y,w,\overline{p}))).$$

Now we check that these hold in $𝕃$.

In Lecture 2, we proved Extensionality and Foundation in all transitive structures, so also in $𝕃$.

Note that $\omega$ satisfies the condition of the axiom of infinity, so any $M$ transitive with $\omega \in M$ will satisfy the axiom of infinity. TODO

Now do pairing and union.

Since the definitions of pairs and unions

$$\begin{array}{llll}\hfill z& =\{x,y\}& \hfill & \\ \hfill z& =\bigcup x& \hfill & \end{array}$$

are absolute for transitive models, it’s enough to show that

$$\begin{array}{llll}\hfill \forall x,y\in 𝕃,& \{x,y\}\in 𝕃& \hfill & \\ \hfill \forall x\in 𝕃& \bigcup x\in 𝕃& \hfill & \end{array}$$

If $x,y\in {𝕃}_{\alpha }$, $\phi (w,x,y):=w=x\vee w=y$,

$$\begin{array}{llll}\hfill D(\phi ,(x,y),L_{\alpha })& =\{w\in L_{\alpha }:L_{\alpha }\models \phi (w,x,y)\}& \hfill & \\ \hfill & =\{w\in L_{\alpha }:L_{\alpha }\models w=x\wedge w\}TODO& \hfill & \end{array}$$

Powerset axiom.

$$\forall x,\exists p,\underset{\ast }{\underbrace{\forall w,(w\in p\leftrightarrow w\subseteq x)}}$$

The problem here is that $\ast$ is not obviously absolute. In particular, $z=P(x)$ is not absolute.

Consider ${𝕃}_{\omega +1}$: we have $\omega \in {𝕃}_{\omega +1}$ and $P\cap {𝕃}_{\omega +1}$ is countable.

In ${𝕃}_{\omega +2}$, we find

$$\{a\in {𝕃}_{\omega +1}:a\subseteq \omega \}$$

which is the best possible answer to the question “what is the power set of $\omega$?” that ${𝕃}_{\omega +1}$ can give, but unlikely to be the correct answer.

Consider instead $P(\omega )\cap 𝕃=:P$ and define

$$\mathrm{\Omega }:=\{{\rho }_{𝕃}(a):a\in P\}.$$

(reminder: ${\rho }_{𝕃}(a)$ is the least $\alpha$ such that $a\in {𝕃}_{\alpha +1}$)

By Replacement, $\mathrm{\Omega }$ is a set of ordinals, so find $\alpha >\mathrm{\Omega }$. Then $P\subseteq {𝕃}_{\alpha }$.

Therefore $P=\{a\in {𝕃}_{\alpha }:a\subseteq \omega \}\in {𝕃}_{\alpha +1}$, so $P\in 𝕃$.

Separation:

$$\forall \overline{p},\forall x,\exists s,\forall w,(w\in s\leftrightarrow \underset{{\phi }^{\prime }(w,x,\overline{p})}{\underbrace{w\in x\wedge \phi (w,\overline{p})}})$$

If $x\in {𝕃}_{\alpha }$, then

$$\begin{array}{llll}\hfill D({\phi }^{\prime },x,L_{\alpha })& :=\{w\in L_{\alpha }:L_{\alpha }\models {\phi }^{\prime }(w,x,\overline{p})\}& \hfill & \\ \hfill & =\{w\in L_{\alpha }:L_{\alpha }\models w\in x\wedge \phi (w,\overline{p})\}& \hfill & \\ \hfill & \stackrel{?}{=}\{w\in \underset{\text{not a problem}}{\underbrace{𝕃}}:\underset{\text{this is a problem}}{\underbrace{𝕃}}\models w\in x\wedge \phi (w,\overline{p})\}& \hfill & \end{array}$$

If $\phi$ is not absolute between $L_{\alpha }$ and $L$, this won’t work.

Levy Reflection Theorem to the rescue: $\forall \phi ,\forall \alpha ,\exists 𝜃>\alpha$ such that $\phi$ is absolute between $L_{𝜃}$ and $L$.

Thus: form

$$\begin{array}{llll}\hfill D({\phi }^{\prime },x,L_{𝜃})& =\{w\in L_{𝜃}:L_{𝜃}\models w\in x\wedge \phi (w,\overline{p})\}& \hfill & \\ \hfill & \stackrel{\text{absolute}}{=}\{w\in L_{𝜃}:L\models w\in x\wedge \phi (w,\overline{p})\}& \hfill & \end{array}$$

Replacement:

This will be on Example Sheet 2. The proof is a combination of the ideas from power set and separation.

TODO

Cohen:

$\forall T\subseteq \mathsf{\text{ZFC}}$ finite, $\exists T^{\ast }\subseteq \mathsf{\text{ZFC}}$ finite such that if $M$ is a countable transitive model of $T^{\ast }$, then there is $N\supseteq M$ countable transitive model of $T+\neg \mathsf{\text{CH}}$. ($\ast$)

We have seen ( Example Sheet 1) that ($\ast$) implies $\mathrm{Con}(\mathsf{\text{ZFC}})⟹\mathrm{Con}(\mathsf{\text{ZFC}}+\neg \mathsf{\text{CH}})$.

Simplified: If $M$ is a countable transitive model of $\mathsf{\text{ZFC}}$, then there is $N\supseteq M$ countable transitive model of $\mathsf{\text{ZFC}}h=\neg \mathsf{\text{CH}}$.

Idea: If $M$ is a countable transitive model of $\mathsf{\text{ZFC}}$: $\alpha :={\omega }_1^M$; $\beta :={\omega }_2^M$; $f:\beta \to P(\omega )$ injection. Force $N$ such that $f\in N$ and $M\subseteq N$.

Observe that there is a countable transitive model $N$ such that $f\in N$ and $M\subseteq N$. $M\cup \mathrm{tcl}(\{f\})$ is transitive and countable. Thus LSM gives $N$ transitive countable with $M\cup \mathrm{tcl}(\{f\})\subseteq N$. Know $N\models \exists g:\beta \to P(\omega )$ is an injection, but no clue what ${\aleph }_1$ and ${\aleph }_2$ in $N$ are.

How do we control what we add?