Independence & Forcing

Proof. Suppose first that both $T+\phi$ and $T+\neg \phi$ have models. If $T⊢\phi$ then $\phi$ is true in every model of $T$, by soundness; but the model of $T+\neg \phi$ is a model of $T$ in which $\phi$ fails, a contradiction. So $T⊬\phi$, and the symmetric argument with the model of $T+\phi$ gives $T⊬\neg \phi$. Hence $\phi$ is independent.

Conversely, suppose $\phi$ is independent of $T$. If $T+\phi$ had no model then, by Gödel's completeness theorem in its contrapositive form — a theory with no model is inconsistent — the theory $T+\phi$ would be inconsistent, so $T+\phi ⊢\perp$, and by the deduction theorem $T⊢\neg \phi$, contradicting independence. So $T+\phi$ has a model, and likewise $T+\neg \phi$.∎

Proof. Assume $\mathrm{Con}(\mathrm{ZFC})$. By the theorem Gödel, 1938: the consistency of CH, the theory $\mathrm{ZFC}+\mathrm{CH}$ is consistent, hence has a model by completeness. By the theorem Cohen, 1963: the consistency of the negation of CH, the theory $\mathrm{ZFC}+\neg \mathrm{CH}$ is consistent, hence also has a model. Two models of ZFC disagree about CH, so by the theorem Independence is a statement about models, CH is independent of ZFC.∎

Proof. ZFC is recursively axiomatised — its axioms are the finitely many individual axioms together with two decidable schemes — and it interprets arithmetic, since the finite von Neumann ordinals with their induced operations form a model of Peano arithmetic inside ZFC. So ZFC meets the hypotheses of the theorem Gödel's second incompleteness theorem, and if it is consistent then it does not prove $\mathrm{Con}(\mathrm{ZFC})$.∎

Proof. Reason inside ZFC. Suppose ZFC proved the sentence "there exists a set $\mathcal{M}$ and a relation $E$ on it with $(\mathcal{M},E)\models \mathrm{ZFC}$ ". The completeness theorem is provable in ZFC, and one of its consequences — soundness in the arithmetised form — gives that the existence of a model of a theory implies the consistency of that theory. Hence ZFC would prove $\mathrm{Con}(\mathrm{ZFC})$, contradicting the corollary ZFC cannot prove its own consistency.∎

Proof. Independence of CH implies in particular that $\mathrm{ZFC}⊬\mathrm{CH}\wedge \neg \mathrm{CH}$, that is, it implies $\mathrm{Con}(\mathrm{ZFC})$. So if ZFC proved the independence of CH outright, ZFC would prove $\mathrm{Con}(\mathrm{ZFC})$, which the corollary ZFC cannot prove its own consistency forbids (assuming ZFC consistent). The positive half is the corollary CH is independent of ZFC, whose proof assumed exactly $\mathrm{Con}(\mathrm{ZFC})$ and used nothing else beyond ZFC.∎

Proof. We prove by induction on $\alpha$ that $L_{\alpha }$ is transitive and that $L_{\alpha }\subseteq L_{\alpha +1}$; the general monotonicity then follows by a second induction on $\beta$.

Base. $L_0=\varnothing$ is transitive vacuously.

Successor. Assume $L_{\alpha }$ is transitive. First, $L_{\alpha }\subseteq L_{\alpha +1}$: given $x\in L_{\alpha }$, transitivity gives $x\subseteq L_{\alpha }$, and $x=\{z\in L_{\alpha }:z\in x\}$ is defined over $L_{\alpha }$ by the formula $z\in a$ with the parameter $a=x\in L_{\alpha }$. So $x\in \mathrm{Def}(L_{\alpha })=L_{\alpha +1}$. Next, $L_{\alpha +1}$ is transitive: any $Y\in L_{\alpha +1}$ satisfies $Y\subseteq L_{\alpha }$ by definition of $\mathrm{Def}$, and $L_{\alpha }\subseteq L_{\alpha +1}$ as just shown, so $Y\subseteq L_{\alpha +1}$.

Limit. If $\lambda$ is a limit and each $L_{\alpha }$ for $\alpha <\lambda$ is transitive, then $L_{\lambda }={\bigcup }_{\alpha <\lambda }{L}_{\alpha }$ is a union of transitive sets, hence transitive; and $L_{\lambda }\subseteq L_{\lambda +1}$ by the successor argument applied to $L_{\lambda }$.

For monotonicity, fix $\alpha$ and induct on $\beta \ge \alpha$: the case $\beta =\alpha$ is trivial, the successor step is $L_{\beta }\subseteq L_{\beta +1}$, and at a limit $\lambda >\alpha$ we have $L_{\alpha }\subseteq L_{\lambda }$ directly from the definition of the union.∎

Proof. Transitivity: if $x\in L$ then $x\in L_{\alpha }$ for some $\alpha$, and $L_{\alpha }$ is transitive by the proposition The hierarchy is increasing and each level is transitive, so $x\subseteq L_{\alpha }\subseteq L$.

For the ordinals, induct on $\alpha$. Suppose $\beta \in L_{\beta +1}$ for all $\beta <\alpha$. Since the hierarchy is increasing, $\beta \in L_{\alpha }$ for every $\beta <\alpha$, so $\alpha \subseteq L_{\alpha }$. Now being an ordinal — being transitive and linearly ordered by $\in$ — is expressible by a formula whose quantifiers can be restricted to any transitive set, and $L_{\alpha }$ is transitive, so

exhibits $\alpha$ as a member of $\mathrm{Def}(L_{\alpha })=L_{\alpha +1}$, using the parameter $\alpha$ once it is known that $\alpha \subseteq L_{\alpha }$; alternatively, and without parameters, $\alpha =\{z\in L_{\alpha }:z\text{ is an ordinal}\}$, because an easy induction shows the ordinals in $L_{\alpha }$ are exactly those below $\alpha$.∎

Proof. Induct on $n$. Both are empty at $n=0$. Suppose $L_n=V_n$; this set is finite, since $|V_{n+1}|=2^{|V_n|}$ starting from $|V_0|=0$. Every subset $Y$ of a finite transitive set $X$ is definable over $X$: writing $Y=\{a_1,\dots ,a_k\}$, the formula $z=a_1\vee \cdots \vee z=a_k$ with parameters $a_1,\dots ,a_k\in X$ defines it, and $Y=\varnothing$ is defined by $z\ne z$. Hence $\mathrm{Def}(X)=\mathcal{P}(X)$ for finite $X$, giving $L_{n+1}=\mathcal{P}(L_n)=\mathcal{P}(V_n)=V_{n+1}$. Taking unions at $\omega$ gives $L_{\omega }=V_{\omega }$.∎

Proof. The function $\alpha \mapsto L_{\alpha }$ is defined by transfinite recursion from the operation $X\mapsto \mathrm{Def}(X)$. Two things must be checked, and both are checks on complexity rather than on set theory.

First, $\mathrm{Def}$ is absolute between transitive models of ZF. Satisfaction for a set structure, $(X,\in )\models \phi [\bar{a}]$, is defined by recursion on the finite formula $\phi$ coded as a hereditarily finite object; the recursion only ever quantifies over subsets of $X$ and over elements of $V_{\omega }$, and its defining formula can be written in ${\Delta }_0$ form relative to parameters. Hence any transitive model of ZF computes the satisfaction relation of $(X,\in )$ correctly, and therefore computes $\mathrm{Def}(X)$ correctly. Note carefully that this is not the same as absoluteness of $\mathcal{P}(X)$, which fails badly; $\mathrm{Def}(X)$ is a set of subsets each of which is described by a formula, and describing is absolute while collecting all subsets is not.

Second, transfinite recursion is absolute when the underlying operation is and the model contains all ordinals. By induction on $\alpha$: if $M$ computes $L_{\beta }$ correctly for all $\beta <\alpha$, then at a successor it applies the absolute operation $\mathrm{Def}$ to a correct input, and at a limit it takes a union, which is absolute. Since $M$ has all ordinals, no stage is missed.

Applying this with $M=L$ — which is transitive by the corollary $L$ is a transitive class containing every ordinal, contains all ordinals, and satisfies ZF — gives $(L_{\alpha }{)}^L=L_{\alpha }$ for all $\alpha$, hence $L^L={\bigcup }_{\alpha }(L_{\alpha }{)}^L=L$. So every set of $L$ is constructible from the point of view of $L$, that is, $L\models V=L$.∎

Proof. We construct ${<}_L$ by recursion on levels, well-ordering each $L_{\alpha }$ and arranging that each ordering extends the previous ones.

Fix a recursive enumeration ${\phi }_0,{\phi }_1,{\phi }_2,\dots$ of all first-order formulas in the language of set theory, in order of their Gödel numbers. Suppose ${<}_{\alpha }$ is a well-ordering of $L_{\alpha }$. Every element of $L_{\alpha +1}$ arises as

for at least one pair consisting of an index $i$ and a finite tuple $\bar{a}$ from $L_{\alpha }$. Assign to $Y$ the ${<}_{\alpha }$ -least such description, where descriptions are compared first by the index $i$, then — among equal indices — by the tuple $\bar{a}$ in the lexicographic order induced by ${<}_{\alpha }$ on tuples of a fixed finite length, shorter tuples preceding longer ones. This is a well-ordering of the set of descriptions, being a finite lexicographic product of well-orderings, so a least description exists.

Now define ${<}_{\alpha +1}$ on $L_{\alpha +1}$ by: elements of $L_{\alpha }$ come first, ordered by ${<}_{\alpha }$; then the elements of $L_{\alpha +1}\setminus L_{\alpha }$, ordered by their least descriptions. Each piece is a well-ordering and the second is placed entirely after the first, so the sum is a well-ordering, and it extends ${<}_{\alpha }$ by construction.

At a limit $\lambda$ set ${<}_{\lambda }={\bigcup }_{\alpha <\lambda }{<}_{\alpha }$. This is a linear order since the ${<}_{\alpha }$ form a chain under extension. It is a well-ordering: a nonempty $S\subseteq L_{\lambda }$ meets some $L_{\alpha }$ with $\alpha <\lambda$, and the ${<}_{\alpha }$ -least element of $S\cap L_{\alpha }$ is ${<}_{\lambda }$ -least in $S$, because every element of $S$ outside $L_{\alpha }$ was placed after all of $L_{\alpha }$.

Finally put $x{<}_{L}y$ if and only if $x$ appears before $y$ in ${<}_{\alpha }$ for the least $\alpha$ with $x,y\in L_{\alpha }$. The whole recursion is given by a single formula, so ${<}_L$ is definable without parameters, and by the theorem $V=L$ holds inside $L$ it is computed the same way inside $L$.

For AC: given a set $x\in L$ of nonempty sets, the function sending each $u\in x$ to its ${<}_L$ -least element is definable from $x$ and ${<}_L$, and $L$ satisfies enough of ZF to form it as a set. It is a choice function on $x$. Hence $L\models \mathrm{AC}$.∎

Proof. By induction. At $\alpha =\omega$: $L_{\omega }=V_{\omega }$ by the proposition Finite levels agree with the cumulative hierarchy, which is countably infinite, and $|\omega |={\aleph }_0$.

Successor step. Suppose $|L_{\alpha }|=|\alpha |$ with $\alpha$ infinite. Each element of $L_{\alpha +1}$ is determined by a formula together with a finite tuple from $L_{\alpha }$. There are countably many formulas and $|L_{\alpha }{|}^{<\omega }=|\alpha |$ finite tuples, using the standard fact that ${\kappa }^{<\omega }=\kappa$ for infinite $\kappa$. So $|L_{\alpha +1}|\le {\aleph }_0\cdot |\alpha |=|\alpha |=|\alpha +1|$. The reverse inequality holds because $L_{\alpha }\subseteq L_{\alpha +1}$.

Limit step. For limit $\lambda$, $|L_{\lambda }|\le {\sum }_{\alpha <\lambda }|L_{\alpha }|={\sum }_{\alpha <\lambda }|\alpha |\le |\lambda |\cdot |\lambda |=|\lambda |$, and again $\lambda \subseteq L_{\lambda }$ gives the reverse.∎

Proof. Argue contrapositively and syntactically, which is what keeps the argument finitary. Suppose $T$ is inconsistent, so there is a finite derivation of $\perp$ from finitely many axioms ${\tau }_1,\dots ,{\tau }_k$ of $T$. By hypothesis ZF proves ${\tau }_i^M$ for each $i$, where ${\phi }^M$ denotes the relativisation of $\phi$ to $M$. Relativisation commutes with the rules of first-order logic: if $\psi$ follows from ${\psi }_1,\dots ,{\psi }_m$ by a rule, then ${\psi }^M$ follows from ${\psi }_1^M,\dots ,{\psi }_m^M$ by the same rule, provided $M$ is nonempty — which it is, since it contains the ordinals. Translating the derivation of $\perp$ term by term therefore yields a derivation of ${\perp }^M$, which is $\perp$, from ${\tau }_1^M,\dots ,{\tau }_k^M$. Since ZF proves each of those, ZF proves $\perp$. Hence ZF is inconsistent. Contraposing gives the statement, and every step was a finite manipulation of finite derivations, so the whole argument formalises in primitive recursive arithmetic.∎

Proof. $L$ is a definable transitive class containing all ordinals, by the corollary $L$ is a transitive class containing every ordinal. ZF proves that $L$ satisfies every axiom of ZF — this is the eight-axiom verification quoted in the outline of the theorem Gödel, 1938: the consistency of CH — and ZF proves $L\models \mathrm{AC}$ by the theorem $L$ satisfies the axiom of choice, and $L\models V=L$ by the theorem $V=L$ holds inside $L$. Now apply the theorem The inner model method with $T=\mathrm{ZFC}$ and with $T=\mathrm{ZF}+V=L$.∎

Proof. A condition with domain inside an $n$ -element set is determined by choosing its domain — a subset of size $k$, in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways — and then a value in $\{0,1\}$ at each of the $k$ points, in $2^k$ ways. Summing over $k$ and applying the binomial theorem to $(1+2{)}^n$ gives $3^n$. Equivalently, and more directly: each of the $n$ points is independently assigned one of three states — undefined, $0$, or $1$ — giving $3^n$ conditions.∎

Proof. The first sentence is the definition of genericity applied to $D$. For the second, suppose $D_{\Phi }\in M$ is dense and every $p\in D_{\Phi }$ guarantees $\Phi$ of the object built from any filter containing $p$. By genericity there is $p\in G\cap D_{\Phi }$, and since $p\in G$ the object built from $G$ satisfies $\Phi$.∎

Proof. Suppose toward a contradiction that $G\in M$. Then the set

is a member of $M$, since $M$ satisfies enough of ZF to form the difference of two of its sets. We claim $D$ is dense. Let $p\in \mathbb{P}$ be arbitrary. By hypothesis $p$ has two extensions $q_0\perp q_1$. If both were in $G$, then, $G$ being downward directed, some $r\in G$ would extend both, making $q_0$ and $q_1$ compatible — contradiction. So at least one $q_i\notin G$, and that $q_i$ is an extension of $p$ lying in $D$. Hence $D$ is dense and belongs to $M$.

Genericity now gives $G\cap D\ne \varnothing$. But $D$ was defined as the complement of $G$, so $G\cap D=\varnothing$. This contradiction shows $G\notin M$.∎

Proof. Build a decreasing chain of conditions. Put $p_0=p$. Given $p_n$, use density of $D_n$ to choose $p_{n+1}\le p_n$ with $p_{n+1}\in D_n$. This is a recursion of length $\omega$ with a choice at each step, so it requires only countable choice, available in ZFC.

Let $G=\{q\in \mathbb{P}:q\ge p_n\text{ for some }n\}$, the upward closure of the chain. Then:

Nonempty and contains $p$: $p=p_0\ge p_0$.

Upward closed: if $q\in G$, say $q\ge p_n$, and $q\le r$, then $r\ge p_n$, so $r\in G$.

Downward directed: if $q\ge p_m$ and $q^{\prime }\ge p_n$ with, say, $m\le n$, then $p_n\le p_m\le q$ and $p_n\le q^{\prime }$, and $p_n\in G$; so $p_n$ is a common extension inside $G$.

Meets each $D_n$: $p_{n+1}\in D_n$ and $p_{n+1}\in G$.

For the final claim, let $M$ be countable and transitive. Then $M$ has only countably many elements, so it contains only countably many dense subsets of $\mathbb{P}$; enumerate them as $\{D_n:n<\omega \}$ — this enumeration lives outside $M$, which is precisely why $M$ cannot carry out the construction itself — and apply the first part.∎

Proof. For $M\subseteq M[G]$, define the check name $\check{x}$ by recursion: $\check{x}=\{(\check{y},1):y\in x\}$. Then $\check{x}\in M$, and since $1\in G$ for every filter, an induction on rank gives $(\check{x}{)}_G=\{(\check{y}{)}_G:y\in x\}=x$. So every $x\in M$ is the evaluation of a name in $M$.

For $G\in M[G]$, take $\Gamma =\{(\check{p},p):p\in \mathbb{P}\}$, a name in $M$. Its evaluation is ${\Gamma }_G=\{(\check{p}{)}_G:p\in G\}=\{p:p\in G\}=G$.

For ordinals, $M\subseteq M[G]$ gives one inclusion. Conversely, an easy induction shows $\mathrm{rank}({\tau }_G)\le \mathrm{rank}(\tau )$, so every element of $M[G]$ has rank below the height of $M$; since both classes are transitive and contain exactly the ordinals of that height, their ordinals agree.∎

Proof. Monotonicity: any generic $G$ containing $q$ contains $p$, since filters are upward closed and $q\le p$; so the defining condition for $p⊩\phi$ applies to $G$ and gives $M[G]\models \phi$.

For the second claim, suppose no $q\le p$ forces $\neg \phi$. Let $G$ be generic with $p\in G$. If $M[G]\models \phi$, the truth part of the theorem The forcing theorem gives some $r\in G$ with $r⊩\phi$, and since $G$ is directed there is $q\in G$ with $q\le p$ and $q\le r$; monotonicity gives $q⊩\phi$, as required. If instead $M[G]\models \neg \phi$, the same argument produces $q\le p$ forcing $\neg \phi$, contrary to assumption. Density follows because $p$ was arbitrary.∎

Proof. Let $p\in \mathrm{Fn}(\omega ,2)$ be arbitrary and fix $n$. Two cases.

If $n\in \mathrm{dom}(p)$, then $p$ itself lies in $D_n$ and $p\le p$, so $p$ has an extension in $D_n$.

If $n\notin \mathrm{dom}(p)$, define $q=p\cup \{(n,0)\}$. Since $\mathrm{dom}(p)$ is finite, so is $\mathrm{dom}(q)=\mathrm{dom}(p)\cup \{n\}$, and $q$ is a function because the new point $n$ was not previously in the domain. Hence $q\in \mathrm{Fn}(\omega ,2)$, and $q\supseteq p$ means $q\le p$. Also $n\in \mathrm{dom}(q)$, so $q\in D_n$.

In both cases $p$ has an extension in $D_n$, which is density. Finally $D_n$ is definable from $\mathrm{Fn}(\omega ,2)$ and $n$ by a formula with bounded quantifiers, so separation inside $M$ produces it as an element of $M$.∎

Proof. $g$ is a function: any two conditions in $G$ are compatible, being members of a downward directed filter, and compatible finite partial functions agree on their common domain, so the union of $G$ has no conflicting pairs. $g$ is total: fix $n$. The set $D_n$ is dense and lies in $M$ by the theorem The domain-filling sets are dense, so genericity gives $p\in G\cap D_n$, and then $n\in \mathrm{dom}(p)\subseteq \mathrm{dom}(g)$. Values lie in $\{0,1\}$ because every condition takes values there.∎

Proof. Fix $f:\omega \to 2$ with $f\in M$, and set

$E_f$ is an element of $M$, being definable from $f$ and the poset.

$E_f$ is dense. Let $p$ be any condition. Since $\mathrm{dom}(p)$ is finite and $\omega$ is not, choose $n\notin \mathrm{dom}(p)$ and put $q=p\cup \{(n,1-f(n))\}$. Then $q$ is a condition, $q\le p$, and $q(n)=1-f(n)\ne f(n)$, so $q\in E_f$.

By genericity pick $p\in G\cap E_f$, witnessed at some $n\in \mathrm{dom}(p)$. Since $p\subseteq g$ we get $g(n)=p(n)\ne f(n)$, so $g\ne f$.

As $f\in M$ was arbitrary, $g$ is not a ground-model real. It does lie in $M[G]$, since $g=\bigcup {\Gamma }_G$ for the canonical name $\Gamma$ of the corollary The extension contains what it should, and $M[G]$ is a model of ZFC closed under unions.∎

Proof. $(1)\Rightarrow (2)$: By AC, $|\mathbb{R}|={\aleph }_{\alpha }$ for some $\alpha \ge 1$, since $\mathbb{R}$ is uncountable by Cantor's theorem. If $\alpha \ge 2$ then ${\aleph }_1<|\mathbb{R}|$, and a subset of $\mathbb{R}$ of size exactly ${\aleph }_1$ exists (take the image of an injection from ${\omega }_1$, available since ${\aleph }_1\le |\mathbb{R}|$); that subset is uncountable and not of size $|\mathbb{R}|$, contradicting (1). So $\alpha =1$.

$(2)\Rightarrow (3)$: If $|\mathbb{R}|={\aleph }_1$, transport the canonical well-ordering of ${\omega }_1$ along a bijection. Every proper initial segment of ${\omega }_1$ is a countable ordinal, hence countable.

$(3)\Rightarrow (1)$: Let $\prec$ be such a well-ordering, of order type $\gamma$. Every proper initial segment being countable means $\gamma \le {\omega }_1$, and $\gamma$ is uncountable since $\mathbb{R}$ is, so $\gamma ={\omega }_1$ and $|\mathbb{R}|={\aleph }_1$. Now let $A\subseteq \mathbb{R}$ be infinite. Under the bijection with ${\omega }_1$, either $A$ is bounded in ${\omega }_1$, hence contained in a countable initial segment and therefore countable, or it is unbounded, in which case it has size ${\aleph }_1=|\mathbb{R}|$.∎