Franklin's Notes


Forcing not-CH

In this note, I'll outline a proof of the fact that the Continuum Hypothesis is not necessarily true given the axioms of ZFC , or in other words, $\neg\mathrm{CH}$ is consistent with ZFC. This proof follows the methods of Nik Weaver used in Forcing for Mathematicians. Here's a list of prerequisites for this proof:

First, we prove a lemma from infinitary combinatorics, which Weaver refers to as the "$\Delta$ System Lemma".

Lemma 1. Let $X$ be an uncountable family of finite sets. Then there is an uncountable subset $Y\subset X$ and a set $R$ such that $A\cap B=R$ for any distinct $A,B\in Y$.

Proof. Let $X_k$ denote the set of elements of $X$ with cardinality $k$ (since they are all finite). Since $X$ is uncountable, some $X_k$ must be uncountable. Let's fix a value $k$ for which this is true. The set $\varnothing$ is trivially contained in uncountably many of the elements of $X_k$ (since it is contained in all of them), and no set of size $k+1$ or greater is contained in all (in fact, any) of the elements of $X_k$, so we may let $R$ be a set of the largest possible size that is contained in uncountably many elements of $X_k$, so that adding any new element to $R$ will cause it to only be contained in at most countably many elements of $X_k$.

We may now use the Axiom of Choice (in fact, a technique of dependent choice ) to choose elements of the set $Y\subset X_k$, one by one via transfinite induction. We may use the Axiom of Choice to construct a function $f:Z\to X_k$, where $Z\subset 2^{X_k}$ is the set of at most countable subsets of $X_k$ such that the intersection between any two is $R$, such that $f$ maps each countable subset of $X_k$ to an element $x\in X_k$ which is not contained in any of the sets in its preimage, and which has intersection $R$ with each of them. (The existence of at least one such $x$ follows from a cardinality pigeonhole argument and the maximality of $R$.)

Now comes the transfinite induction. First, choose an arbitrary element $x_0\in X_k$ such that $R\subset x_0$. Then define the rest of the sequence $(x_\alpha){\alpha < \omega_1}$ by transfinite induction, letting so that, from the aforementioned property of $f$, each $x\alpha$ has intersection $R$ with the previous members of the sequence, and the sequence has uncountable cardinality $\omega_1$, as desired. $\blacksquare$

Now we use this to force a model of ZFC to fail to satisfy $\mathrm{CH}$.

Theorem 1. Let $P$ be the set of finite partial functions from $\mathbb N\times \aleph_\xi^\mathrm{M}$ into ${0,1}$ with $\xi\ne 1$, and let $G$ be a generic ideal of $P$. Then $\mathrm{CH}$ fails in $\mathrm{M}[G]$, and in fact $\mathrm{M}\vDash 2^\mathbb{N}\ge \aleph_\xi$.

Proof. First we show that $P$ satisfies the countable chain condition , or equivalently that in any uncountable subset $S\subset P$, some two elements are comparable. If $S$ is uncountable, then the set $X$ of domains of functions in $S$ must also be uncountable, since only countably many functions into ${0,1}$ can be defined given countably many finite domains. Since the above lemma is provable in ZFC, it holds in $\mathrm{M}$, meaning that we may apply it to $X$, yielding an uncountably infinite subset $Y\subset X$ and a finite set $R\subset \mathbb N\times\aleph_\xi^\mathrm{M}$ such that $A\cap B = R$ for all distinct $A,B\in Y$. For each $A\in Y$, select a function in $S$ whose domain is $A$, and put these functions in the infinite set $T\subset S$. Since $R$ is finite, and there therefore are only finitely many functions from $R$ to ${0,1}$, but there are infinitely many functions in $T$, we have that some two functions $f,g\in T$ take the same values on $R$ and are therefore compatible. Thus, we have demonstrated the existence of compatible functions $f,g\in S$ in any uncountable subset of $P$, so we have that $P$ is ccc.

From Proposition 2 proven here , which states that generic extensions using ccc forcing notions preserve cardinals, we have that $\aleph_\xi^{\mathrm{M}[G]}=\aleph_\xi^{\mathrm{M}}$. The union $\tilde{f}$ of all functions in $G$ is a partial function from $\mathbb N\times\aleph_\xi^\mathrm{M}$ into ${0,1}$, and it belongs to $\mathrm{M}[G]$ since $G\in\mathrm{M}[G]$. Additionally, since $G$ is generic and the set of all partial functions of $P$ with domain containing a given subset of $\mathbb N\times\aleph_\xi^\mathrm{M}$ is dense in $P$, we have that $G$ contains functions with arbitrarily large domain, meaning that the domain of $\tilde{f}$ includes all of $\mathbb N\times\aleph_\xi^\mathrm{M}$.

Now, from within the model, for each ordinal $\alpha < \aleph_\xi^{\mathrm{M}[G]}=\aleph_\xi^\mathrm{M}$, define the set i.e. the "extra" subsets of $\mathbb N$ encoded by the function $\tilde{f}$. The genericity of $G$ again implies that the sets $A_\alpha$ are distinct: for the set of functions $f\in P$ for which $f(n,\alpha)\ne f(n,\beta)$ for some $n\in\mathbb N$ is dense in $P$, for any given $\alpha,\beta<\aleph_\xi^\mathrm{M}$. In $\mathrm{M}[G]$, the sets $A_\alpha$ may be constructed from $\tilde{f}$, meaning that there exist $\aleph_\xi$ distinct subsets of $\mathbb N$ in $\mathrm{M}[G]$. Hence, $\mathrm{CH}$ fails in $\mathrm{M}[G]$, and $2^\mathbb{N}\ge \aleph_\xi$ in this model as claimed. $\blacksquare$

model-theory

set-theory

nonstandard-model

forcing

back to home page