Misunderstanding the Continuum Hypothesis


(sometimes)

A few days ago I read this article and realized I'd misunderstood the Continuum Hypothesis.  The Continuum Hypothesis is a statement in the language of set theory that says something like this:

There's no set whose cardinality is between that of the real numbers $\mathbb{R}$ and the integers $\mathbb{Z}$.

Set Theory

Set theory is an axiomatic theory designed to give a rigorous foundation to our intuitive beliefs about sets.  The axioms of set theory take for granted just two things: 

  1. That there is a collection - also known as a class - of objects, which are known as sets
  2. That there is a binary relation between sets, represented by the symbol $\in$, and where $x \in A$ is read as "x is an element of A".

Those two assumptions in themselves do not create any sort of parallel between the objects discussed and the naive concept of the "set".  That's the purpose of the axioms.  There's about 10 of these - known as the Zermelo-Fraenkel axioms - and rather than list them all I'll just show one to give the flavour:
$$
\forall A,B : A = B \iff (\forall x: x \in A \iff x \in B)
$$
This says that two sets are the same when they have the same elements.  Likewise, the other axioms are "reasonable" if you want to use the axioms to infer things about naive sets.  The axioms allow us to crank the handle of logic and "prove" things.  When you prove something in set theory, you are proving something that applies whenever you have a collection of objects and a relation that satisfies the axioms.

Cardinality

Given the axioms it is possible to define additional concepts like ordered pairs and functions.  These things are in fact just sets, but ones which can be interpreted in special ways.  The relation "a one-to-one function exists between $A$ and $B$" is an equivalence relation, and can be used to divide the class of sets into equivalence classes.  We say that $A$ and $B$ have the same cardinality if they inhabit the same equivalence class.  We can say that the cardinality of $A$ is less than the cardinality of $B$ if the two sets have different cardinalities, and there's an onto function from $B$ to $A$.

The Continuum Hypothesis

Within set theory is is possible to construct first the integers and then the real numbers, and set theory provides us with the language for talking about the sizes of these sets.  Cantor proved that the cardinality of the reals is greater than that of the integers.  (Another way to say this is that the reals are not countable.)  Which begs the question: are the reals the smallest set that's larger than the integers?  Or, to put it another way: is there a set with cardinality between that of the integers and that of the reals?  The Continuum Hypothesis is the statement that there is no such set, and that the reals have the next largest cardinality after the integers.

At university I learned what I considered to be a very strange fact: that the Continuum Hypothesis was neither provable, nor disprovable.  That's doesn't mean that no-one's proved or disproved it yet, or that it's just very hard: it means someone, somehow, proved that you can't get to it or it's negation starting with the axioms of set theory and using just the rules of logic.

Now the integers are unique, by which we mean that if you have a set with an ordering and some operations, and they satisfy the axioms for the integers, then it's essentially the same as any other combination that does.  There's a mapping between the sets which preserves the ordering and all the operations - which suggests that all you've really got are different labels for the same old integers.  The same goes for the reals - they're unique too!  But if the reals actually exist at all, surely there either is or is not a subset with a cardinality in between it and the integers.  I.e. the Continuum Hypothesis is either true, absolutely, or false, absolutely.  But if the Continuum Hypothesis can't be proven or disproven then you can add either CH or ¬CH to the original axioms and carry on forever without ever reaching a contradiction as a result.

Over the years this has led me to a lot of metaphysical confusion: Perhaps the reals can't actually exist and all of real-analysis is just a game played with pencil and paper?  Perhaps the reals can exist, but CH is a Gödel Sentence, and as such we can never know whether it is true or false.  Then I read that article and realised it's much simpler than I'd thought!

How to interpret the Continuum Hypothesis

The article titled "The Deepest Uncertainty" pointed out two things I knew, and two things I didn't.  What I knew was that Kurt Gödel showed the Continuum Hypothesis could not be disproven, and about 20 years later Paul Cohen showed that it couldn't be proven either.  However, what I didn't know was how they did it, and it turns out they both did it by constructing models.  These are collections of objects, together with an $\in$ relation, which obey the axioms of set theory.  In Gödel's case the model was a collection of sets in which there did not exist a set with cardinality between that of the reals and that of the integers; in Cohen's it was a model in which there did exist a set with a cardinality between the two.

Suddenly the Continuum Hypothesis seemed a lot less strange.  Yes, the integers are unique, and so are the reals.  But there's no reason to think that the collection of objects which satisfy the axioms of set theory are unique.  And in fact Gödel and Cohen have shown that they are not.  This is not unusual in mathematics.  For example, a group is a collection of objects together with a binary operation that satisfies a few axioms, and both $(\mathbb{Z},+)$ and $(\mathbb{R}-\{0\},\times)$ are groups, but there's no isomorphism between them - they're not the same!

Realising this allows us to interpret the Continuum Hypothesis correctly.  The reason you cannot prove it or disprove it from the axioms is that the axioms do not constrain the models enough - it's true in some models and not true in others.  In the models where it is true all we are saying is that in that collection of objects  there are some subsets of $\mathbb{R}$ missing.

Perhaps "is the Continuum Hypothesis true?" is the wrong question, and the right question is "in which models is the Continuum Hypothesis true?"  It's a bit like in group theory we could ask whether "$\forall x,n \ ( x^n =1 \iff x = 1 \lor n = 0)$" is true,  and the answer would be "it depends on the group".

The Continuum Hypothesis is a statement about a single model for set theory.  However, if we are discussing the reals as a more abstract entity - one which happens to have a representation within every model of set theory, then it seems reasonable to say that if the CH is false in any model, then it is false.

The Continuum Hypothesis (in the way people naturally interpret it) is false.

Comments

Post a Comment

Popular posts from this blog

How To Make ASCII Diagrams Beautifuller

Image
I've discovered an excellent tool in asciiflow.com .  The website makes it really easy to create ASCII box diagrams like this They put these things in fruit machines you know! This is ideal for source code banners, which I think should contain helpful documentation - but most programmers think it's a good place for the COPYRIGHT information and nothing else. But wait! we can make it beautifuller... and easier to read... by replacing some of the ASCII characters with ones available in UTF-8: There!  Isn't that better?  (Although some purists may object to non-ASCII characters in your code base.) SOURCE CODE: #!/usr/bin/python2 # coding: utf-8 # + gets converted in different ways depending on it's 4 neighbours # # . N . { nsew(N,S,E,W) has bit 3 set if N in "+|<>" # W + E { nsew(N,S,E,W) has bit 2 set if S in "+|<>" # . S . { nsew(N,S,E,W) has bit 1 set if W in "+-^v" # { nsew(N,S,E,W) has bit 0 set if E ...
Read more

Why growth is falling in all developed countries (as a long term trend)

Image
In this post I argue that economic growth is not the normal state of affairs, it is a blip caused by the discovery of a one-off resource of non-renewable energy.   The logistic equation $$ \frac{dy}{dt} = y(1-y) $$ Here's a simple model.  Humans discover an exploitable but limited resource and start consuming it.  The amount consumed, $y(t)$, is a function of time.  The general form of the equation is $\frac{dy}{dt} = \alpha y (\beta - y)$, but if you choose the right units $\alpha$ and $\beta$ both become $1$. Why should this work, in principle? Early on, the factor $1-y$ is approximately $1$ and can be ignored.  So the model states that annual consumption $dy/dt$ starts off proportional to $y$.  In other words, $y$ grows exponentially at first.  This could happen if exploiting the resource enables further exploitation of the resource.  For example, suppose a few humans are shipwrecked on an island with 1000 trees: they take ages to cut down the ...
Read more

Three ways to look at the Bell/GHZ experiment

Image
In 1964 John Stewart Bell proposed an experiment to determine whether the results of quantum measurements were truly random, or governed by hidden variables, i.e. state that exists prior to the measurement, but which we don’t have access to. The experiment involved creating a large number of EPR pairs, and firing them at two observers, Alice and Bob, who measure their photon’s polarisation, choosing the $\updownarrow$ direction or the $\nearrow\llap\swarrow$ direction at random. Determining the result of the experiment involves doing a complex statistical calculation to see if something called Bell’s inequality is satisfied or violated. The Bell experiment was first performed by in 1982 by Alain Aspect, and the result, as most commonly interpreted, is that hidden variables can only exist if Quantum Mechanics is non-local, i.e. if it supports faster-than-light causality! Some time after Bell proposed his experiment, Greenberger, Horne, and Zeilinger suggested an alternativ...
Read more