Transitive Models - Forcing and the Continuum Hypothesis

2 Transitive Models

Observation: If $M$ is transitive and $M ⊨ “ e is empty”$ , then $e = \emptyset$ . 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 ⊨ w \in e$ , so $M ⊨ “ e is not empty”$ .

Lemma. Assuming that:

$M$ is transitive

Then

M ⊨ Extensionality + Foundation .

Proof. Extensionality: $\forall x \forall y (\forall w (w \in x \leftrightarrow w \in y) \to x = y)$ . Take $x \neq y$ , $x, y \in M$ . Without loss of generality take $z \in x ∖ y$ . Then $z \in x$ and $x \in M$ so $z \in M$ . So $M ⊨ z \in x \land z \notin y$ . So $M ⊨ \neg \forall w (w \in x \leftrightarrow w \in y)$ .

Foundation: $\forall x (x \neq \emptyset \to \exists m (m \in x \land \forall w \neg (w \in m \land w \in x)))$ . Take $x \in M$ . $M ⊨ x \neq \emptyset$ so $x$ is not empty. So find $m \in x$ which is $\in$ -minimal. Then since $x \in M$ as well, we have $m \in M$ . Therefore $x$ has an $\in$ -minimal element in $M$ . □

2.1 Absoluteness for transitive models

Definition (Bounded quantifier). We call a quantifier of the form $\exists x \in y, φ$ or $\forall x \in y, φ$ a bounded quantifier.

(Defined by $\exists x \in y, φ : = \exists x (x \in y \land φ)$ and $\forall x \in y φ : = \forall x (x \in y \to φ)$ ).

Definition (Closed under bounded quantification). A class of formulas $Γ$ is closed under bounded quantification if whenever $φ$ is in $Γ$ , then so are $\exists x \in y, φ$ and $\forall x \in y, φ$ .

Definition (Delta0). $Δ_{0}$ is the smallest class of formulas containing the atomic formulas that is closed under propositional connectives and bounded quantifiers.

Let $T$ be any theory. Then $Δ_{0}^{T}$ is the class of formulas equivalent to a $Δ_{0}$ formula in $T$ .

Theorem. $Δ_{0}$ formulas are absolute for transitive models.

Proof. By induction:

(1) All atomic formulas are absolute by the substructure lemma.
(2) Propositional connectives: exactly the same proof as in the substructure lemma.
(3) Assume that $φ$ is absolute and show that $\exists x \in y, φ$ and $\forall x \in y, φ$ are absolute.
- $\exists x \in y, φ$ : If $\exists x \in y, φ$ is true for some $y \in M$ , then pick a witness $x \in y$ . Since $y \in M$ , we have $x \in M$ . By the induction hypothesis, we have that $M ⊨ φ (x, y)$ . Thus $M ⊨ \exists x (x \in y \land φ (x, y))$ .
  
  If $M ⊨ \exists x (x \in y \land φ (x, y))$ , then $x \in y \land φ (x, y)$ is true.
- $\forall x \in y, φ$ : Similar. □

Corollary. Assuming that:

$T$ is any theory
$M ⊨ T$ is transitive

Then

Δ_{0}^{T}

-formulas are absolute for

M

Definition ( $S i g m a 1$ , $P i 1$ ). A formula is called $Σ_{1}$ if it is of the form $\exists x_{1}, \dots \exists x_{n}, φ$ where $φ$ is $Δ_{0}$ .

It is called $Π_{1}$ if it is of the form $\forall x_{1}, \dots, \forall x_{n}, φ$ where $φ$ is $Δ_{0}$ .

(same for $Σ_{1}^{T}$ , $Π_{1}^{T}$ ).

Proof. Just definition of the semantics of $\exists, \forall$ . □

Example. What is $Δ_{0}$ ?

1. $x \in y$
2. $x = y$
3. $x \subseteq y$ : $⟺ \forall w \in x (w \in y)$
4. $z = {x}$ : $⟺ x \in z \land \forall w \in z (w = x)$
5. $z = {x, y}$
6. $z = (x, y) = {{x}, {x, y}}$
7. $z = \emptyset$ : $⟺ \forall w \in z (w \neq w)$
8. $z = x \cup y$ : $⟺ x \subseteq z \land y \subseteq z \land \forall w \in z (w \in x \lor w \in y)$
9. $z = x \cap y$
10. $z = x ∖ y$
11. $z = x \cup {x}$
12. $z is transitive$
13. $z = ⋃ x$

Definition (Absolute function). Let $M$ a transitive set, and $F : M^{n} \to M$ (note that this means that $M$ is closed under $F$ ). We say $F$ is absolute for $M$ if there is a formula $Φ$ which is absolute for $M$ such that

F (x_{1}, \dots, x_{n}) = z ⟺ Φ (x_{1}, \dots, x_{n}, z) .

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 ⊨ Pairing$ .

Similarly for union.

Lemma. Assuming that:

$φ$ is absolute for $M$
$F, G_{1}, \dots, G_{n}$ are absolute operations on $M$

Then

\begin{array}{l} ψ (x_{1}, \dots, x_{m}) & : = φ (G_{1} (x_{1}, \dots, x_{m}), \dots, G_{n} (x_{1}, \dots, x_{m})) \\ H (x_{1}, \dots, x_{m}) & : = F (G_{1} (x_{1}, \dots, x_{m}), \dots, G_{n} (x_{1}, \dots, x_{m})) \end{array}

are absolute for $M$ .

Proof. Check the definitions! □

Example. More examples:

(14) $z$ is an ordered pair:
$\exists s \in z, \exists d \in z, \exists x \in s, \exists y \in d, (\forall w \in s, (w = x) \land \forall v \in d, (v = x \land v = y) \land \forall w \in z, (w = s \lor w = d)) .$
(15) $z = a \times b$
(16) $z is a relation$
(17) $z = dom x$
(18) $z = range x$
(19) $z is a function$
(20) $z is injective$
(21) $z is surjective$
(22) $z is bijective$

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 ⊨ x is transitive \land (x, \in) is linearly ordered .

characterises ordinals. But this is clearly in $Δ_{0}$ .

So: being an ordinal is absolute for transitive models.

Thus $M \cap Ord = {x \in M : M ⊨ x is an ordinal}$ . This is transitive, thus there is $α \in Ord$ such that $α = M \cap Ord$ .

Also absolute:

“ $x$ is a successor ordinal” ( $\exists y \in T O D O$ )
“ $x$ is a limit ordinal”
“ $x$ is a non-zero limit ordinal”
$x = ω$ TODO

Cardinals

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

x is an ordinal \land \forall f, \forall y \in x, f : y \to x ⟹ f is not a surjection

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

Observe: this is $Π_{1}$ and therefore downwards absolute.

Remark.

(1) We may not want this to be absolute. If it was, we couldn’t change cardinal behaviour.
(2) We can’t obviously bound $\forall f$ , since the natural bound would be
${h : h \to y \to x}$

or
$P (y \times x) .$

These, however, are not (yet??) on our list of absolute concepts.
(3) Not that neither (1) nor (2) is an argument, since there could be an equivalent formula that is $Δ_{0}$ .

2.2 Non-absoluteness

Assume that $M ⊨ ZFC$ is transitive and countable. Then

M \cap Ord = α < ω_{1} .

However, $M ⊨ ZFC$ implies $M ⊨ there are uncountable cardinals$ .

Let $β < α$ be such that $M ⊨ β is the least uncountable cardinal$ .

But $β$ is a countable ordinal, so not a cardinal.

Consequence: All cardinals in $M$ except $ℵ_{0}$ are going to be fake.

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

Note. This also shows that “ $x = P (y)$ ” cannot be absolute:

Take $y$ such that $M ⊨ y = P (ω)$ . Then $y \subseteq P (ω)$ , but is countable since $y \subseteq M$ .

Thus $y \neq P (ω)$ . Therefore “ $x = P (y)$ ” is not absolute.

Recall the general proof strategy mentioned before:

If $M$ is a countable transitive set such that $M ⊨ ZFC$ , then there is a a countable transitive set $N \supseteq M$ such that $N ⊨ ZFC + \neg CH$ .

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

It’s not obvious that $Con (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 $Con (ZFC)$ $⁄ ⟹$ there is a countable transitive model of ZFC.

Why? Note that $Con (ZFC)$ , or $Con (T)$ for any $T$ is $Δ_{0}$ . So, it’s absolute for transitive models.

So if $M$ is a countable transitive model of ZFC, then $Con (ZFC)$ is true, so by absoluteness, $M ⊨ Con (ZFC)$ . So $M ⊨ ZFC + Con (ZFC)$ . This contradicts Gödel’s Incompleteness Theorem.

We can get a proof of

Con (ZFC) ⟹ Con (ZFC + \neg CH)

via a trick ( Example Sheet 1).

Lemma (Cohen Lemma). Assuming that:

$T \subseteq ZFC$

Then there is finite

T^{*} \subseteq ZFC

such that if

M

is a countable transitive model of

T^{*}

, then there is

N \supseteq M

such that

N

is a countable transitive model of

T + \neg CH

This reduces the problem to:

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

Definition (Hierarchy). We call an assignment $α \mapsto Z_{α}$ a hierarchy if

(i) $Z_{α}$ is a transitive set
(ii) $Ord \cap Z_{α} = α$
(iii) $α < β ⟹ Z_{α} \subseteq Z_{β}$
(iv) $λ limit ⟹ Z_{λ} = ⋃_{α < λ} Z_{α}$

If ${Z_{α} : α \in Ord}$ is a hierarchy, we can define $Z : = ⋃_{α \in Ord} Z_{α}$ . This is a proper class as $Ord \subseteq Z$ . We also define $ρ_{Z} (x) : = \min {α : x \in Z_{α}}$ , a notion of $Z$ -rank.

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

Theorem 2.1 (Levy Reflection Theorem). Assuming that:

$Z$ is a hierarchy
$φ$ is a formula

Then there are unboundedly many

𝜃

such that

φ

is absolute between

Z_{𝜃}

and

Z

Proposition 2.2 (Tarski-Vaught Test). Assuming that:

$M$ is a substructure of $N$

Then

M

is an elementary substructure if and only if for any formula

ϕ (v, \bar{w})

and

\bar{a} \in M

, if there is

b \in N

such that

N ⊨ ϕ (b, \bar{a})

, then there is

c \in M

such that

N ⊨ ϕ (c, \bar{a})

TVT $_{Φ}$ :

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

(i) All formulas in $Φ$ are absolute between $M$ and $N$ .
(ii) For all $φ \in Φ$ , the TV-condition holds: if $φ = \exists x ψ$ , then for all $\bar{y} \in M$ if there is $a \in N$ sucht hat $N ⊨ ψ (a, \bar{y})$ , then there is $b \in M$ such that $N ⊨ ψ (b, \bar{y})$ .

Warm-up: let $(M, \in) ⊨ ZFC$ . Find countable $N \subseteq M$ such that $(N, \in) ≺ (M, \in)$ .

Suppose $\bar{p} = (p_{0}, \dots, p_{n}) \in M$ and $M ⊨ \exists y, ψ (y, \bar{p})$ . Let $w (ψ, \bar{p})$ be a witness for this:

M ⊨ ψ (w (ψ, \bar{p}), \bar{p})

(if necessary, use Axiom of Choice).

(if $M ⊨ \neg \exists y, ψ (y, \bar{p})$ , then let $w (ψ, \bar{p}) = \emptyset$ ).

Set:

\begin{array}{l} N_{0} & : = \emptyset \\ N_{i + 1} & : = {w (ψ, \bar{p}) : ψ formula and \bar{p} \in N_{1}^{< ω}} \\ N & : = ⋃_{i \in ω} N_{i} \end{array}

Note:

(1) $N$ is countable.
(2) $M ≺ N$ by Tarski-Vaught Test.

Remark. In general, even if $M$ is transitive, $N$ is not.

For example, if $ω_{1} \in M$ , then

\exists x, (x is the least countable ordinal)

is true in $M$ .

w (ψ, \emptyset) = ω_{1} .

So $ω_{1} \in N$ . But $ω_{1} \subseteq N$ , since $N$ is countable.

Relevant later!

Also see Example Sheet 1.

Proof of Levy Reflection Theorem. Fix $φ$ and let $Φ$ be its collection of subformulas. This is a finite set!

Need to show: $\forall α, \exists 𝜃 > α$ such that $Z_{𝜃} ⊨ φ ⟺ Z ⊨ φ$ .

For each $ψ \in Φ$ and $\bar{p} = (p_{0}, \dots, p_{n})$ , write

\begin{array}{l} o (ψ, \bar{p}) & : = {\begin{matrix} least α such that \exists y \in Z_{α} with Z ⊨ ψ (y, \bar{p}) & if it exists \\ 0 & otherwise \end{matrix} \\ o (\bar{p}) & : = \max_{ψ \in Φ} o (ψ, \bar{p}) \\ 𝜃_{0} & : = α + 1 \\ 𝜃_{i + 1} & : = \sup {o (\bar{p}) : \bar{p} \in Z_{𝜃_{i}}^{< ω}} \\ 𝜃 & : = \sup_{i \in ω} 𝜃_{i} \end{array}

Then Tarski-Vaught Test implies that $Z_{𝜃}$ and $Z$ agree on $φ$ . □

Corollary. If $T \subseteq ZFC$ is finite, then there is $M$ transitive such that $M ⊨ T$ .

Proof. Let $φ : = \land_{ψ \in T} ψ$ . Since $ZFC ⊢ φ$ , we have that $φ$ is true. By Levy Reflection Theorem, we can find $𝜃$ such that $V_{𝜃} ⊨ φ$ . Note $V_{𝜃}$ is transitive. □

Remark about the proof of Levy Reflection Theorem:

Can you do the same if $Φ$ is infinite?

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

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

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

TODO

Theorem (Mostowski’s Collapsing Theorem). Let $r$ be a relation on a set $a$ that is well-founded and extensional. Then there exists a transitive set $b$ , adn a bijection $f : a \to b$ such that $(\forall x, y \in a) (x r y ⟺ f (x) \in f (y))$ . Moreover, $b$ and $f$ are unique.

Proof. See Logic and Set Theory. □

Corollary. For every $T \subseteq ZFC$ finite, there is a countable transitive model of $T$ .

Proof. Without loss of generality that $T$ contains the axiom of extensionality. Form $M ⊨ T$ transitive by Levy Reflection Theorem.

Use warm-up to obtain $N ≺ M$ countable. This is extensional and well-founded, so by Mostowski find $W$ transitive such that

(W, \in) ≅ (N, \in) .

Then $W ⊨ T$ adn $| W | = | |$ , so $W$ is countable. □

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

Absoluteness is preserved under transfinite recursion.

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

\begin{array}{l} R (0, \bar{x}) & : = F (\bar{x}) \\ R (α + 1, \bar{x}) & : = G (α, R (α, \bar{x}), \bar{x}) \\ R (λ, \bar{x}) & : = H (λ, {R (α, \bar{x}) : α < λ}, \bar{x}) & (*) \end{array}

Proof. Attempts: set functions satisfying the ( $*$ ).

L1 All attempts agree on their common domain.
L2 $\forall α, \exists r$ attempt such that $(α, \bar{x}) \in dom (r)$ .

$R (α, \bar{x}) : = y$ if and only if there exists attempt $r$ with $(α, \bar{x}) \in dom (r)$ and $r (α, \bar{x}) = y$ . □

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

Theorem. If $T \supseteq T_{F, G, H}$ and $F, G, H$ are absolute for transitive models of $T$ , then so is $R$ defined by ( $*$ ).

Want $T_{F, G, H} ⊢ L 1 (F, G, H)$ , $T_{F, G, H} ⊢ L 2 (F, G, H)$ and $T_{F, G, H}$ proves existence of $R$ .

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

Proof. Observe that by assumption, being an “attempt” is absolute for transitive models of $T$ .

Let $M ⊨ T$ be transitive.

(1) To show: If $M ⊨ R (α, \bar{x}) = z$ , then $R (α, \bar{x}) = z$ .
If $M ⊨ R (α, \bar{x}) = z$ , then $M ⊨ \exists r, r is an attempt and r (α, \bar{x}) = z$ . Without the $\exists r$ , this would be absolute. So when we include the existential quantifier, we get an upwards absolute sentence.

Thus: there is $r$ such that $r$ is an attempt and $r (α, \bar{x}) = z$ . So $R (α, \bar{x}) = z$ .
(2) Other direction. Assume $r$ is an attempt with $r (α, \bar{x}) = z$ .
Since $T_{F, G, H} ⊢ L 2 (F, G, H)$ , we have
$M ⊨ \exists r^{'}, \underset{absolute}{\underset{⏟}{r^{'} is an attempt and (α, \bar{x}) \in dom r^{'}}} .$

Since it is absolute, $r^{'}$ is a real attempt.

By ???, $r^{'} (α, \bar{x}) = r (α, \bar{x})$ . Hence $M ⊨ R (α, \bar{x}) = z$ . □

Note. This uses the fact that “ $Δ_{1}$ ” concepts are absolute.

Definition (Delta1T property). A property is called $Δ_{1}^{T}$ if it’s both ${Σ_{1}}^{T}$ and ${Π_{1}}^{T}$ .

Observe: $Δ_{0}^{T}$ concepts are absolute (upwards from $Σ_{1}$ and downwards from $Π_{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}{l} T & ⊢ \forall x, \exists z, F (x) = z \\ T & ⊢ \forall x, \forall z, \forall z^{'}, F (x) = z \land F (x) = z^{'} \to z = z^{'} \end{array}

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

\begin{array}{l} \exists y \in F (x) ψ & ⟺ \underset{upwards absolute}{\underset{⏟}{\exists z \underset{absolute}{\underset{⏟}{(z = F (x) \land \exists y \in z ψ)}}}} \\ ⟺ \underset{downwards absolute}{\underset{⏟}{\forall z \underset{absolute}{\underset{⏟}{(z = F (x) \to \exists y \in z ψ)}}}} \end{array}

Applications

(1) Encode formulas as elements of

ω^{< ω}


$\in$	$=$	$($	$)$	$\land$	$\lor$	$\neg$	$\exists$	$\forall$	$v_{0}$	$v_{1}$	$v_{2}$	$\dots$

$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$\dots$

$\forall v_{0} \exists v_{1} \neg v_{0} \in v_{1}$ would be $(8, 9, 7, 10, 6, 8, 0, 10)$ .

$F m l \subseteq ω^{< ω}$ . So, $F m l$ is absolute for some (sufficiently strong) finite fragment of $ZFC$ (see Example Sheet 1).

(2) If $X$ is any set then
$“ X ⊨ φ ”$

(which means “ $(X, \in) ⊨ φ$ ”) 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 $φ \in Fml$ and each $p \in X^{< ω}$ (parameter)

D (φ, p, X) : = {w \in X : X ⊨ φ (p, w)}

the subset of $X$ defined by $φ$ with parameter $p$ .

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

D (X) : = {D (φ, p, X) : φ \in Fml, p \in X^{< ω}} .

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$ ”).

( $α \in D (X) ⟺ \exists φ \in Fml, \exists p \in X^{< ω}, a = D (φ, p, X)$ )

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

\begin{array}{l} L_{0} & : = \emptyset \\ L_{α + 1} & : = D (L_{α}) \\ L_{λ} & = ⋃_{α < λ} L_{α} \end{array}

The constructible hierarchy.

We usually write $L : = ⋂_{α \in Ord} L_{α}$ .

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 ZFC$ where $T$ is strong enough to prove that it exists.

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

⋃_{α \in Ord \cap M} L_{α} \subseteq M .

The main theorem of next lecture will be:

If $L ⊨ ZF$ and $M ⊨ ZF$ transitive, then

⋃_{α \in Ord \cap M} L_{α} ⊨ ZF .

(Minimal $ZF$ -model).

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

Clearly, by induction, $L_{α} \subseteq V_{α}$ , and clearly for $n \in ω$ , $L_{n} = V_{n}$ . So $L_{ω} = V_{ω}$ .

L_{α + 1} : = ⋃_{φ \in Fml} ⋃_{p \in L_{α}^{< ω}} {D (φ, p, L_{α})} .

If $α \geq ω$ , then

| L_{α + 1} | \leq ℵ_{0} \cdot | L_{α}^{< ω} | = ℵ_{0} \cdot | L_{α} | .

Thus $| L_{α} | = | L_{α + 1} |$ .

Therefore $α < ω_{1}$ , $| L_{α} | = ℵ_{0}$ and $| L_{ω_{1}} | = ℵ_{1}$ .

This means: $V_{ω + 1} \neq L_{ω + 1}$ (since the first has size $2^{ℵ_{0}}$ , while the second has size $ℵ_{0}$ ).

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

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

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

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

\forall α \in Ord \cap M, 𝕃_{α} \in M

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

So $⋃_{α \in Ord \cap M} 𝕃_{α} \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 \land \forall w, \neg (w \in m \land w \in x))) .

Infinity:
$\exists i, \exists e, (\forall v, \neg v \in e \land e \in i) \land \forall x, (x \in i \to \exists s, (s \in i \land \forall w, (w \in s \leftrightarrow w \in x \lor w = x))) .$

Functional axioms:

Pairing:

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

Union:
$\forall x, \exists v, \forall w, (w \in v \leftrightarrow \exists z, (z \in x \land w \in z)) .$
Powerset:
$\forall x, \exists p, \forall w, (w \in p \leftrightarrow \forall v, (v \in w \to v \in x)) .$

Separation $φ$ :

\forall \bar{p}, \forall x, \exists s, \forall w, (w \in s \leftrightarrow w \in x \land φ (w, \bar{p})) .

Replacement $φ$ :

$\forall \bar{p}, [\forall x, \forall y, \forall z (φ (x, y, \bar{p}) \land φ (x, z, \bar{p}) \to y = z)] \to \forall x, \exists r, \forall w, (w \in r \leftrightarrow \exists y, (y \in x \land φ (y, w, \bar{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 $ω$ satisfies the condition of the axiom of infinity, so any $M$ transitive with $ω \in M$ will satisfy the axiom of infinity. TODO

Now do pairing and union.

Since the definitions of pairs and unions

\begin{array}{l} z & = {x, y} \\ z & = ⋃ x \end{array}

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

\begin{array}{l} \forall x, y \in 𝕃, & {x, y} \in 𝕃 \\ \forall x \in 𝕃 & ⋃ x \in 𝕃 \end{array}

If $x, y \in 𝕃_{α}$ , $φ (w, x, y) : = w = x \lor w = y$ ,

\begin{array}{l} D (φ, (x, y), L_{α}) & = {w \in L_{α} : L_{α} ⊨ φ (w, x, y)} \\ = {w \in L_{α} : L_{α} ⊨ w = x \land w} T O D O \end{array}

Powerset axiom.

\forall x, \exists p, \underset{*}{\underset{⏟}{\forall w, (w \in p \leftrightarrow w \subseteq x)}}

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

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

In $𝕃_{ω + 2}$ , we find

{a \in 𝕃_{ω + 1} : a \subseteq ω}

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

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

Ω : = {ρ_{𝕃} (a) : a \in P} .

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

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

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

Separation:

\forall \bar{p}, \forall x, \exists s, \forall w, (w \in s \leftrightarrow \underset{φ^{'} (w, x, \bar{p})}{\underset{⏟}{w \in x \land φ (w, \bar{p})}})

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

\begin{array}{l} D (φ^{'}, x, L_{α}) & : = {w \in L_{α} : L_{α} ⊨ φ^{'} (w, x, \bar{p})} \\ = {w \in L_{α} : L_{α} ⊨ w \in x \land φ (w, \bar{p})} \\ \overset{?}{=} {w \in \underset{not a problem}{\underset{⏟}{𝕃}} : \underset{this is a problem}{\underset{⏟}{𝕃}} ⊨ w \in x \land φ (w, \bar{p})} \end{array}

If $φ$ is not absolute between $L_{α}$ and $L$ , this won’t work.

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

Thus: form

\begin{array}{l} D (φ^{'}, x, L_{𝜃}) & = {w \in L_{𝜃} : L_{𝜃} ⊨ w \in x \land φ (w, \bar{p})} \\ \overset{absolute}{=} {w \in L_{𝜃} : L ⊨ w \in x \land φ (w, \bar{p})} \end{array}

Replacement:

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

Corollary 2.3 (Minimality). Assuming that:

$T$ is a transitive model of $ZF$

Then for all

α \in T \cap Ord

𝕃_{α} \subseteq T

. Axiom of TODO.

Remark. Remark on the Axiom of Choice.

Gödel (1938): $Con (ZF) \to Con (ZFC)$ .

Note first that everything we did so far only needed $ZF$ in the universe. We will sketch that $𝕃 ⊨ AC$ . In fact a strong version of $AC$ known as GLOBAL CHOICE: there is an absolutely definable bijective operation between $𝕃$ and $Ord$ .

Sketch: Recursive construction of bijections $π_{α} : 𝕃_{α} \to η_{α}$ for some ordinal $η_{α}$ , and such that for $β < α$ we have $π_{α} |_{𝕃_{β}} = π_{β}$ .

If $λ$ is a limit and $π_{α}$ is defined for $α < λ$ , then let

π_{λ} (x) : = π_{α} (x)

if $x \in 𝕃_{α}$ .

Suppose $α = β + 1$ and $π_{β}$ is given by $π_{β} : 𝕃_{β} \to η_{β}$ .

Consider $Fml \times L_{β}^{< ω}$ . Well-order it in order type $η_{β}^{'}$ via the induced $π_{β}$ well-order. Then if $x \in L_{α}$ , say

π_{α} (x) : = {\begin{matrix} π_{β} (x) & if x \in L_{β} \\ η_{β} ξ & if ξ is the ordinal corresponding to the least (φ, \bar{p}) such that x = D (φ, \bar{p}, T O D O) \end{matrix}

TODO

Cohen:

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

We have seen ( Example Sheet 1) that ( $*$ ) implies $Con (ZFC) ⟹ Con (ZFC + \neg CH)$ .

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

Idea: If $M$ is a countable transitive model of $ZFC$ : $α : = ω_{1}^{M}$ ; $β : = ω_{2}^{M}$ ; $f : β \to P (ω)$ 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 tcl ({f})$ is transitive and countable. Thus LSM gives $N$ transitive countable with $M \cup tcl ({f}) \subseteq N$ . Know $N ⊨ \exists g : β \to P (ω)$ is an injection, but no clue what $ℵ_{1}$ and $ℵ_{2}$ in $N$ are.

How do we control what we add?

[next] [prev] [prev-tail] [front] [up]

2 Transitive Models

2.1 Absoluteness for transitive models

Ordinals

Cardinals

2.2 Non-absoluteness

Typical Applications

Applications

2.3 The constructible hierarchy

Some first idea of what the L-hierarchy is like

Axioms of ZF

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