Wednesday, 30 January 2013

Independence of the continuum hypothesis

Following up from previous posts, let us continue on the theme of independence proofs, i.e. showing that a certain statement is not provable in a given formal system. The most celebrated of these results is of course Cohen's proof that the continuum hypothesis (CH) is not provable in set theory. For that Cohen developed the new method of "forcing". A few years after Cohen's result, Dana Scott come up with a brilliant proof of the independence of the CH that avoids forcing, but uses what are now called boolean valued-models. I want to give a brief sketch of Scott's proof, but one should definitely read the extremely well-writen paper [1] for all the details.

The first nice thing about Scott's paper is that it starts by giving a completely natural formulation of CH. CH is often stated using cardinals as the equation $$2^{\aleph_0} = \aleph_1$$ so it's easy to dismiss it as abstract non-sense. But it can also be rephrase in concrete terms as: Given any set of reals, either the set of integers can be mapped onto the set, or the set can be mapped onto the whole set of reals. So, the question is: Is there a set of reals whose cardinality lies strictly between the cardinalities of natural numbers and the whole set of reals?

Formally this can be written as $$ \forall X ( \exists f^{\mathbb{N} \rightarrow X} (\mbox{Img}(f) = X) \vee \exists g^{X \to \mathbb{R}} (\mbox{Img}(g) = \mathbb{R}) ).  $$ I'm writing \( x^X \) as an abbreviation for \( x \in X \).

Scott then builds a model of set theory (a version slightly different than the usual presentation of the Zermelo-Frankel set theory) in which CH is false.

The first novelty is that the construction of the model is parametrised by a probability space \( (\Omega, \cal{A}, P) \). The real numbers are interpreted as random variables, i.e. in the constructed model the set of real number \( \cal{R} \) consists of all \( \eta \colon \Omega \to \mathbb{R} \) such that $$ \{\omega \in \Omega \; \colon \; \eta(\omega) \leq r \} \in \cal{A} $$ where \( \mathbb{R} \) is the "real" set of real numbers. The whole point is to make the set of reals in the model \( \cal{R} \) much much bigger than the actual set of real numbers \( \mathbb{R} \).

The second novelty is that formulas are no longer either true or false, but they have a real (in the sense of \( \mathbb{R} \)) value between zero and one (saying how true it is, with one meaning "very" true). So, equality between two "real numbers" \( \eta \colon \Omega \to \mathbb{R} \) and \( \zeta \colon \Omega \to \mathbb{R} \) is given as $$ val(\eta = \zeta) =  \{\omega \in \Omega \; \colon \; \eta(\omega) = \zeta(\omega) \} / [P = 0] $$ where one has to quotient out the set of events which have \(P\)-measure zero. This valuation function can be extended to all formulas, and the main result is that if a formula \( A \) is provable in set theory then \( val(A) = 1 \), independent of the probability space we started with.

Hence, in order to show that CH is not provable, it's enough to find some probability space \( (\Omega, \cal{A}, P) \) such that in that space \(val(\)CH\() < 1\). Scott fixes \( I \) an arbitrary set of cardinality greater than \( 2^{\aleph_0} \), and then takes \( \Omega = [0,1]^I \). Because \( I \) is huge, the set of sample points \( \Omega \) will also be huge, which means the set of reals \( \cal{R} \) in the model has an immense cardinality.

So, now we need to build a set \( X \subseteq \cal{R}\) such that neigher \( \exists f^{\mathbb{N} \rightarrow X} (\mbox{Img}(f) = X) \) nor \( \exists g^{X \to \cal{R}} (\mbox{Img}(g) = {\cal R}) \). One can check that the projection \( \xi_i \colon \Omega \to \mathbb{R} \) are indeed random variables, and hence are real numbers in the model (i.e. belong to \(\cal{R}\)). Pick a subset \( J \subset I \) which is uncountable but still of cardinality strictly smaller than \( I \). Our set of reals \( X \subset \cal{R}\) will be (informally) $$ X = \{ \xi_j \; \colon \; j \in J \} $$ which one can show that is not countable but has (inside the model) cardinality smaller than the reals \( \cal{R} \). Neat!

Anyway, I hope Scott will forgive me for such a sketchy account of his paper, but I hope this will serve as an advertisement for the curious ones to go and have a closer look at all the details in [1].

[1] Dana Scott, A proof of the independence of the continuum hypothesis, Mathematical systems theory, 1(2):89-111, 1967.


J said...

There is now a new proof using classical realisability!

Ariel Gabizon said...

Thanks for the effort to make this accessible!
One thing that confuses me - you say that in the model where CH is false the reals have huge cardinality, but don't they have to have cardinality 2^{א_0} for result to be meaningful?