The Cardinality of the Continuum

A nice grand title to pique your interest!  After some thought and a couple of conversations, I have decided to keep this blog very much aimed at the layman; the thinking being that I don’t particularly want to write hard maths in my spare time, mathematicians don’t particularly want to read hard maths in their spare time, and non-mathematicians definitely don’t want to read hard maths ever.

My PhD supervisor recently appeared on a BBC programme about infinity, which, while good viewing, was rather over-ambitious, and so had to skip over some interesting stuff.  I thought I’d fill in some of the gaps in this post.  So what is this continuum?  Technically a continuum can be anything that is continuous – that is it goes through smooth, infinitesimally gradual transitions, and has no discontinuities or “jumps”.  But in reality the word is rarely used outside of Star Trek and mathematics.  The continuum I will write about is not the space-time continuum, but the real numbers,\mathbb{R}.  In my post onp-adic numbers, I mentioned that completeness is an important mathematical attribute for a space of numbers to possess.  The notion of continuity is even more fundamental, and people often refer to mathematics as having 2 distinct branches: continuous mathematics, and discrete – or discontinuous – mathematics.

The best way to define a continuous space of numbers is to say that between any two of them we can find another.  So for example the space of integers,\mathbb{Z}, is not continuous because there are no integers between1and2.On the other hand, the space of rational numbers (fractions),\mathbb{Q}, is continuous, because no matter how closely spaced two fractions are, we can always find another between them (eg. between\frac{1}{1000000}and\frac{2}{1000000}is\frac{3}{2000000}).  However, it can be shown that the cardinality (number of numbers in)\mathbb{Q}is the same as the number of integers (see below).  But how can we even talk about the cardinality of a continuous space?  Surely in order to count the “number of things” in a space, we need them to be in some sense separate from one another?  This is the first of various paradoxes that will arise in this post…our brains are not really wired to deal with the notion of infinity.  As is customary, I will ignore these paradoxes and pretend that I understand!

If a set has the same cardinality as the natural (counting) numbers\mathbb{N}=\{0,1, 2, 3,...\}then we say it is countable.  We can show that a set is countable by showing that there is some correspondence between it and\mathbb{N}such that every element of the set can be mapped to some natural number.  For example,\mathbb{Z}is countable because, given some integern,ifnis positive then map it to2n,and if it is negative map it to\text{-}2n-1.This gives us a  correspondence\mathbb{Z}\rightarrow \mathbb{N},such that:

0\ \mapsto 0

\text{-}1\mapsto 1

1\ \mapsto 2

\text{-}2\mapsto 3

2\ \mapsto 4

And so on.  This proves that there are countably many integers.  In a similar way, it can be shown that there are countably many rational numbers, and so the cardinalities of these sets are the same.  If you like, they are “equally infinite”.  So here is another paradox: between any two integers there are infinitely many rational numbers (eg. between0and1are the fractions:\frac{1}{2},\frac{1}{3},\frac{1}{4},...),so how can there possibly be the same number of rationals numbers as integers?  No comment.

As I mentioned in my previous post,\mathbb{Q}is not complete, and so in some sense there are gaps in it.  If we fill in all these gaps in the usual way – that is by adding all the numbers that can’t be expressed as fractions (those with infinitely long non-repeating decimal expansions) – then we get the space of real numbers\mathbb{R};this is what is referred to as the continuum.  The cardinality of the continuum is much, much greater than that of the integers.  This is one of the most difficult aspects of mathematics to get your head around…how can any number be greater than infinity?  Surely by the very definition of infinity, there is nothing greater than it?

Well, actually there are different “levels” of infinity.   In the late 19th century a mathematician called Georg Cantor proved that there are more real numbers than there are natural numbers.  The best way to see this – if you haven’t already – is to look up his diagonal argument; it is unlikely you will ever see a simpler and more ingenious proof of such a deep result.  The cardinality of the natural numbers is denoted by\aleph_0,and it can be shown using the diagonal argument that the cardinality of the real numbers is2^{\aleph_0}.(To see this, you first need to take it on faith that every real number can be represented as a binary number with\aleph_0digits!  Then just note that for every digit we have two choices:0or1).

Cantor was one of the originators of a very important foundational branch of mathematics called set theory, and it is necessary to delve into some of this to understand so-called “transfinite numbers” such as\aleph_0.So what is a natural number?  The construction usually used is to say that each natural number represents the cardinality of some set.  These sets can all be built up out of the empty set as follows:

0is the cardinality of the empty set\{\}.

1is the cardinality of\{0\},the set containing zero as its only element.

2is the cardinality of\{0,1\},the set containing the two elements0and1.

And so on.  I’m sorry to say that this is probably the best definition of “number” you’ll get…perhaps you will at least agree that it is pleasing in the way it creates an entire system out of nothing.  Now, we can identify the counting number3with the “size of the set containing3objects”, indeed we can do this with all finite numbers.  A numbernis referred to as an “ordinal number”, and it is interchangeable with the “cardinal number”n,that is, the size of a set withnelements.

What Cantor showed is that this does not hold for infinite numbers.  If we counted up1,2,3,4,...forever then we would eventually reach\omega,which is the first infinite ordinal number, and the one that most people probably think of as being infinity.  But\omegais not the same thing as the first infinite cardinal number,\aleph_0,which is the size of the smallest infinite set.  For example:2^{\omega}=\omega,while2^{\aleph_0}\neq \aleph_0.This might well just all sound like gobbledegook.  What I am really trying to get across is that the confusion we feel about these “different levels” of infinity comes down to our fundamental notion of what a number is.  When they get big enough, the rules start to change, and we can’t rely on intuition any more.

Needless to say, Cantor’s work caused a lot of consternation in mathematical, philosophical and religious circles.  He himself was manic depressive (no doubt exacerbated by having been persecuted by his peers), believed that the theory of transfinite numbers had been transmitted to him by God, and is often held up as an example of a “mathematician gone mad”.  (Actually there have not been that many crazy mathematicians, they are more commonly just a bit odd).  However, it didn’t take too long for his ideas to become accepted by the majority of mathematicians, however odd they seemed.  David Hilbert declared in typically flowery language in 1926:

“No one shall expel us from the Paradise that Cantor has created.”

And since then we’ve just had to accept it.

Advertisements

4 Responses to The Cardinality of the Continuum

  1. sue says:

    is this supposed to be not-hard maths? phew… my brain’s sweating

  2. […] so that the directions and lengths of the arrows vary continuously (I mentioned continuity in my last post) from point to point.   The theorem says that there is no way to do this in a way such that at […]

  3. […] almost always given in terms of sets (I gave a definition of numbers in terms of the empty set in this post), and the language and methods of set theory are used throughout mathematics.  The […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: