Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Cantor and Cohen: Infinite investigators part II

      Richard Elwes
      2 June, 2008
      6 comments
      June 2008

      The continuum hypothesis

      This is one half of a two-part article telling a story of two mathematical problems and two men: Georg Cantor, who discovered the strange world that these problems inhabit, and Paul Cohen (who died last year), who eventually solved them. This article explores what is known as the continuum hypothesis, while the other article explores the axiom of choice. Each article is self-contained, so you don't have to read both to get the picture.

      Cantor: The infinite match-maker

      Georg Cantor was a German logician who, in the late 19th century, achieved a feat which scientists, philosophers, and theologians had previously only dreamed about: a detailed analysis of infinity. For Cantor personally, the consequences of this triumph were not happy. Unable to solve one of the questions his work opened up, he became obsessive and miserable with his failure. This fixation combined with personal tragedy, the death of his son, and the public insult of having his work rejected as being "a hundred years too soon", Cantor spent the last years of his life in and out of sanatoria.

      Georg Cantor

      Georg Cantor

      Cantor's discovery was that there is not just one infinity, but a never-ending hierarchy, each infinitely bigger than the last. It's a mind-bending thought, but the entrance to his exotic world is a surprisingly easy and familiar concept.

      Suppose you have two collections of objects. Call them collection A and collection B. How could you tell which is bigger, or if the two are the same size? Of course, you could just count all the objects in collection A, then count all the objects in collection B, and compare the two numbers. But it might be easier (and eliminate the risk of losing count), to try to match the two sets up: pair every object from A with one from B, until one or the other runs out. Sets which can be matched up are the same size, and sets which can't are different. This idea could hardly be simpler, but in Cantor's hands it yielded an extraordinary discovery: he proved that some infinite sets can never be matched with others. So immediately we know that there are different levels of infinity, with some bigger than others.

      Cantor applied this method to some common mathematical objects. For instance the natural numbers are just the ordinary counting numbers: 0, 1, 2, 3, 4,... . It might seem obvious that the set of even numbers {0, 2, 4, 6, 8,...} should be smaller than the set of natural numbers, after all, aren't there only half as many of them? Surprisingly though, the two sets can easily be matched up: 0 to 0, 1 to 2, 2 to 4, 3 to 6, and so on, just multiplying by 2 every time. So we have to conclude that the two sets are, in Cantor's sense, actually the same size.

      The set of real numbers is another fundamental object, which can be thought of as the collection of all infinite decimal expansions (such as 19.000000000... or 1.234567891011121314151617181920 ...). You can also think of the real numbers as being the points of an infinitely long line with no holes in it. For this reason the set of real numbers is sometimes called the continuum. Cantor proved that any attempt to match the real numbers with the natural numbers will fail: there will always be some real numbers which get missed out. So we are forced to conclude that the infinity of real numbers is bigger than that of the natural numbers.

      Here's a question: is there an infinity between that of the natural numbers and the real numbers? That is, if I take any collection of real numbers, is it true that it can be matched either with natural numbers, or with the entire set of real numbers? Or is there an intermediate size that it could be? The continuum hypothesis is the statement that there is no such middle ground, and this was the question which brought Cantor so much frustration and misery. We can go into more detail using Cantor's system of infinite numbers.

      abstract design

      The natural numbers and the continuum — is there an infinity between them?

      Cardinal importance

      Cantor built a system of special numbers called cardinal numbers, which measure the different possible sizes of sets. The crucial characteristic is that every single set can be matched up to exactly one cardinal. The finite cardinals are just the natural numbers: 0, 1, 2, 3, 4, 5,... . These correspond to the finite sets of the relevant size: a set with one object in it has cardinality 1, a set with two objects has cardinality 2, and so on. But there are infinite cardinals too, infinitely many of them. Cantor discovered how to extend basic operations, such as addition and multiplication, to these infinite numbers.

      Paul Cohen

      You can count the natural numbers and even the fractions, but the points along a line form an uncountable set.

      The first infinite cardinal is called ℵ0 (that's "aleph nought", where ℵ is the first letter of the Hebrew alphabet). ℵ0 is the size of the set of natural numbers. So a set has size ℵ0 if its elements can be matched up with the natural numbers: that is to say, if you can count it. For this reason, sets of cardinality ℵ0 are called countable. The next cardinal is ℵ1: the first uncountable cardinal. Then there's ℵ2, ℵ3 and so on (and that's just for starters). There is no biggest cardinal: however huge a cardinal is, you can always talk about the next cardinal number, which is the smallest one bigger than the one you already have.

      But that's not the only way of obtaining a larger cardinal number from one you already have. If you have a set X, you can form a bigger set P(X) called the power set of X. The set P(X) is the collection of all subsets of X. So for instance if X is the three element set {1,2,3} then P(X) is \ \ {∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}, \ \ where ∅ is the empty set: the set with no members. If X is the set of natural numbers, then P(X) includes the set of numbers between 1 and 100: {1,2,3,...,100}, the set of primes {2,3,5,7,11,...}, the set of odd numbers {1,3,5,7,9,11,...}, the empty set ∅, and every other conceivable collection of natural numbers. If you do this with a finite set (the above set {1,2,3} has 3 elements), then the number of elements in P(X) is 2 to the power of the size of X (in this case 23=2×2×2=8). Cantor proved that for infinite sets too, the power set P(X) is always bigger than the original set X: the two can never be matched up. If X has cardinal number A, then we say that P(X) has cardinality 2A. So the cardinal number 2ℵ0 is the size of the power set of the natural numbers, and it has a special significance. Many important sets, including the set of real numbers, have cardinality 2ℵ0 and this is the reason why 2ℵ0 is called the continuum. Now we can rephrase the continuum hypothesis: it is the assertion that 2ℵ0=ℵ1. If the continuum hypothesis is true, then there is no cardinal number between ℵ0 and 2ℵ0 . So any infinite collection of real numbers must either have cardinality ℵ0, or 2ℵ0: there is no middle ground. But if the continuum hypothesis is false, then ℵ1 lies between ℵ0 and 2ℵ0. So there must be a collection of real numbers of cardinality ℵ1: too big to be matched with the natural numbers, but too small to be matched with the whole set of real numbers.

      Cantor believed that the continuum hypothesis was true, and spent many years trying to prove it, up until his death in 1918. In 1900, the influential mathematician David Hilbert set out 24 mathematical questions for the new century, which set the course of mathematics for the next 100 years. Hilbert was enthusiastic about set theory, which he called "Cantor's paradise". He put the continuum hypothesis as the first problem on his list.

      Paul Cohen: Conquering the continuum

      Paul Cohen

      Paul Cohen

      The tale of the continuum hypothesis is very similar to that of the axiom of choice, which is treated in another article in this issue of Plus. Mathematicians at the beginning of the twentieth century had been trying to devise a system of axioms that would serve as the foundation of all mathematics. The purpose of working from axioms was to make mathematics rigorous so that the leaps of faith and strokes of inspiration which naturally form part of every mathematician's work can be verified properly from these basic rules. The presumption was that it should be possible to derive every mathematical truth from these axioms, using only the rules of logic.

      The work of the mathematician Ernst Zermelo in the early twentieth century provided the basis for such an axiomatic system, built on the theory of sets. This system is now known as ZFC (after Zermelo, Abraham Fraenkel, and choice — see the other article in this issue of Plus), and this version of set theory still underpins almost the whole subject today: all numbers and virtually every mathematical object can easily be constructed within a set-theoretic universe founded on ZFC.

      Mathematicians at the time thought that the continuum hypothesis too would find its place in this universe: they set about trying to prove it from the ZFC axioms. But they failed. The first real progress was made in 1940 by the mathematician Kurt Gödel, who showed that at least the continuum hypothesis does not introduce any contradictions into ZFC. Of course this is a long way short of proving that it is actually true.

      Paul Cohen's triumph was the invention of forcing, a powerful technique for building new universes of sets which obey ZFC, but which can be tailored to satisfy extra conditions too. In 1963 Cohen turned his pioneering technique upon the continuum hypothesis. He constructed a set-theoretic universe satisfying ZFC, but in which the continuum hypothesis was false. Together with Gödel's work, this proved that the continuum hypothesis is independent of ZFC. It is impossible to conclude from the ordinary rules of mathematics as we understand them, whether the continuum hypothesis is true or not. This was the remarkable result for which in 1966 Cohen won the Fields Medal (the equivalent of the Nobel Prize for mathematics), and in 1967 we was awarded a National Medal Of Science by US President Johnson.

      The continuum: The debate continues

      Thanks to Cohen's work, we know that we cannot hope to resolve the continuum hypothesis one way or the other from ZFC. But set-theoretic axioms do not exist in a vacuum: they are picked to reflect our intuition about how sets should work. So although we can never prove it, we can still ask whether the continuum hypothesis is a natural assumption, which chimes with our innate ideas about sets.

      The celebrated set-theorist Hugh Woodin has argued a case for considering the continuum hypothesis wrong, and that 2ℵ0=ℵ2 is a more natural assumption. Other people have argued for much larger values of the continuum: Cohen himself wrote that he believed 2ℵ0 should be bigger than ℵℵ0, and even ℵℵℵ0.

      To infinity and way, way beyond

      It was David Hilbert who said "No one shall expel us from the paradise that Cantor has created for us", and over a hundred years after its birth, research in set theory is still going strong. The continuum hypothesis is just the first of a series of "large cardinal axioms" dealing with cardinal numbers unimaginably bigger than ℵ0 . Typically there is no way to write down these cardinals, and their existence is usually independent of ZFC. It is remarkable that such objects from the set-theoretic stratosphere can have consequences back down on Earth, among the natural numbers.

      Paul Cohen will not only be remembered for his decisive contributions to the continuum hypothesis and the axiom of choice: the technique he invented, forcing, remains today the standard way to build new universes of set theory, and to illuminate the upper reaches of Cantor's paradise.





      Further reading

      • Find out more about Cantor's infinities and the axiom of choice in the first part of this article The axiom of choice by Richard Elwes;
      • You can find out more about Gödel's work in Plus article Gödel and the limits of logic by John W Dawson.

      About the author

      Richard Elwes is a writer and mathematician based in Leeds. He was the winner of the Plus New Writers Award 2006 and has since published articles in New Scientist and talked about maths on Channel 4 radio's The Tube. As well as teaching and researching maths, he enjoys writing about everything from politics to horror films.

      • Log in or register to post comments

      Comments

      JRStern

      16 March 2018

      Permalink

      ... has cardinality aleph0 or C? I'm curious whether the word "real" was used, because that would equate natural numbers and real numbers, a slippery idea.

      • Log in or register to post comments

      Leslie.Green

      9 September 2018

      Permalink

      The infinity symbol is defined loosely as "a very large number" and is not treated as a value. You can't multiply it, you can't divide it, you can't add other infinite values to it. If you create a new symbol which does behave naturally you get a much better mathematics which doesn't suffer from the metaphysical rubbish like mapping (bijection) a set of order O(N) to a set of order O(N²).

      Here is a more useful set of tools to work with infinity: http://lesliegreen.byethost3.com/articles/new_maths.pdf

      • Log in or register to post comments

      Leslie.Green

      21 June 2022

      In reply to The problem is using a poor definition of the infinity symbol by Leslie.Green

      Permalink

      My “loose definition” of infinity above is horrible! The infinity symbol is defined as being larger than any number, and therefore not itself a number. Since it is not a number (but a concept), number-like operations do not necessarily apply.

      • Log in or register to post comments

      Leslie.Green

      31 May 2019

      Permalink

      It is nice to be able to chart the different sizes of Infinity, since some infinities are much more infinite than others!

      It turns out that the Continuum Hypothesis is wrong. H² is much bigger than H, but not nearly as big as 2^H ..... as H tends to infinity.

      • Log in or register to post comments

      Leslie.Green

      20 June 2022

      Permalink

      Putting a set into supposed 1:1 correspondence with the natural numbers does not prove that both sets have the same “size” (cardinality). It is a circular argument for those who first believe that infinities have the same size. I made a simple little problem out of it to show the circularity:

      • Log in or register to post comments

      Moe Badderman

      19 May 2023

      Permalink

      # "in 1966 Cohen won the Fields Medal (the equivalent of the Nobel Prize for mathematics)"
      The prestigious Fields Medal is in *no_way* "equivalent" to the Nobel Prize.

      • Log in or register to post comments

      Read more about...

      history of mathematics
      philosophy of mathematics
      axiom
      logic
      hilbert problems
      set theory
      Zermelo-Fraenkel axiomatisation of set theory
      infinity
      continuum hypothesis
      what is infinity
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms