In 1877, a mathematician called Georg Cantor put forward a simple hypothesis called the continuum hypothesis. It was a statement about infinity which he believed to be true, but was unable to prove. With hindsight, this was nothing to be ashamed of; it would be 100 years before the mystery surrounding the difficulty of its proof would be understood.

Throughout the 1870’s Cantor had been working on set theory and the theory of the infinite but his work was not received well. People debated about whether or not his ‘theory of the infinite’ was mathematics at all: Did his work really belong to philosophy? Should it be discarded because it challenged the uniqueness of the absolute infinity of God? Infinity had sometimes been seen as a convenient tool to be used when reasoning informally but ultimately when reasoning about the finite world. The ‘actual infinity’ of Cantor’s work was too alien for many mathematicians and philosophers of the time. So, what was his bold hypothesis? And what was so weird and abhorrent about infinity? In this first post on the topic I will introduce infinite sets and we’ll think about how to think about them mathematically.

How Many Numbers Are There?

In the ‘What are numbers?‘ series of posts, we talked about how to define the natural numbers (the positive whole numbers). In this post we’ll be thinking about how large a set the set of natural numbers is, so let’s kick off by making the trivial observation that there are infinitely many natural numbers. In facilitation of a basic illustration of infinity, let’s also consider the set of square numbers. These are numbers which are the square of a natural number, and so this set includes numbers such as four, nine and sixteen, being the squares of two, three and four respectively. They seem to be significantly sparser than the natural numbers themselves. So much so that there appears to be fewer square numbers than there are natural numbers, but this distinction is, however, artificial.

There is a precise sense in which the natural numbers are ‘the same size as’ the square numbers. In fact, we discussed bijections in the ‘Pairing Up’ section of this post.

A set X is said to be in bijection with a set Y if each element of the set X corresponds to exactly one element of the set Y and each element of the set Y corresponds to exactly one element of the set X. We also say that the sets are in ‘one-to-one correspondence’ or that ‘there exists a bijection between the two sets’. So, a bijection exists between two sets when their elements can be paired off one-by-one.

A similar, if more gentle, introduction to the concept is to be found in the post linked above. The idea of a bijection was useful to us in previous posts because it allowed us to say when two finite sets had the same size without appealing to the notion of number. Their usefulness here is similarly motivated: We are unable to describe the ‘size’ of an infinite set using the notion of number (in some sense this what infinite means).

It is simple enough to check that there exists a bijection between the set of natural numbers and the set of all square numbers: To each natural number, n, there corresponds exactly one square, namely , and vice versa. We pair up one with one, two with four, three with nine, etc. in the obvious way. So, although it is perhaps counter-intuitive at first it is actually easy to check that the natural numbers are ‘the same size’ as the set of square numbers.

Any set which can be put in bijection with the natural numbers is said to be countably infinite or merely countable. Gaining some intuition for working with such sets is the key to understanding the well-known Hilbert’s Hotel Paradox (do check out the link or google it yourself; it’s interesting!). The heart of the counter-intuitiveness is that an infinite set can be put into bijection with a subset of itself. The square numbers are a proper subset of the natural numbers  (that means that every square number is a natural number but not every natural number is a square number), and yet the bijection still exists.

With this idea about bijections under our belt, we now have the power to decide when two infinite sets are the same size. Naturally, the next question to ask is “Can two infinite sets be of different sizes?”. I’m asking whether some infinities are bigger than others. And how this might come about? Well, what if I find an infinite set which cannot be put into bijection with the natural numbers?