How Large Is Infinity?
When you hear the word infinity, what do you think of? Do you think of an impossibly large number that you could never reach no matter how long you counted? Does it make you think of the incredibly large distances in outer space?
We all have different concepts of infinity, but something that often surprises people is that there are actually different levels of infinity; one infinitely large group can be larger than another infinitely large group.
Let’s find out how this happens.
We all have different concepts of infinity, but something that often surprises people is that there are actually different levels of infinity; one infinitely large group can be larger than another infinitely large group.
Let’s find out how this happens.
Georg Cantor 1845–1918
Georg Cantor and set theory
Most of the mathematics in this article comes from the work of the German mathematician Georg Cantor (1845–1918). Cantor is the father of set theory, a branch of mathematics which studies sets (collections of objects) and the relationships between them. This work led Cantor to look at the sizes of different sets which in turn led to his discoveries on the nature of infinity.
What is a bijection?
Before we start looking at infinity, it is helpful to understand what a bijection is. Suppose there is a shepherd who every day lets his sheep out into the field to play and eat grass before collecting them all together again at the end of the day. Unfortunately, this shepherd has no concept of numbers and hence cannot count. What can he do to ensure that he always collects all of his sheep back in at the end of the day and doesn’t lose any?
One idea would be for him to have a bucket and a pile of pebbles. As each sheep is released into the field at the beginning of the day, the shepherd puts one pebble into the bucket. He then ends up with the same number of pebbles as there are sheep and can check his flock at the end of the day by matching each sheep up with a pebble from his bucket. If there is a spare pebble left, he has lost a sheep. On the other hand, if he runs out of pebbles, he has somehow gained a sheep.
For every pebble in the bucket, there is a matching sheep and for every sheep in the herd, there is a matching pebble. In other words, the sheep and pebbles can be matched up one-to-one. This is a bijective relationship. We will see why this is important soon.
One idea would be for him to have a bucket and a pile of pebbles. As each sheep is released into the field at the beginning of the day, the shepherd puts one pebble into the bucket. He then ends up with the same number of pebbles as there are sheep and can check his flock at the end of the day by matching each sheep up with a pebble from his bucket. If there is a spare pebble left, he has lost a sheep. On the other hand, if he runs out of pebbles, he has somehow gained a sheep.
For every pebble in the bucket, there is a matching sheep and for every sheep in the herd, there is a matching pebble. In other words, the sheep and pebbles can be matched up one-to-one. This is a bijective relationship. We will see why this is important soon.
The natural numbers
The natural numbers (also known as the counting numbers) are all of the whole numbers larger than zero. In set notation we denote this group Ν = {1, 2, 3, 4, 5 …}. It is quite easy to see that this group is infinitely large. If I were to pick a number, x, and say that this is the biggest number in the set, you could say ‘what about x+1?’ and you’ve got a larger number. Therefore, there is no biggest number; they carry on infinitely.
Now let’s look at the odd and even numbers. In set notation we denote these as O = {1, 3, 5, 7, 9 …} and E = {2, 4, 6, 8, 10 …}. We can see again that these two sets are infinitely large, but as we have created them by effectively cutting N in half, it is tempting to say that their infinite size must be half of the infinite size of N. This isn’t the case however.
If we compare N and E, we can quickly see why. We can create a bijection between these two sets by letting every number in N match up with its double in E. This is shown in the following diagram.
The two groups have a perfect one-to-one match (a bijection) and so, just like the pebbles and the sheep, there must be the same number of elements in each one. Therefore the sets of natural numbers and even numbers are the same size. By a similar process we can see that the odd numbers are also the same size.
Now let’s look at the odd and even numbers. In set notation we denote these as O = {1, 3, 5, 7, 9 …} and E = {2, 4, 6, 8, 10 …}. We can see again that these two sets are infinitely large, but as we have created them by effectively cutting N in half, it is tempting to say that their infinite size must be half of the infinite size of N. This isn’t the case however.
If we compare N and E, we can quickly see why. We can create a bijection between these two sets by letting every number in N match up with its double in E. This is shown in the following diagram.
The two groups have a perfect one-to-one match (a bijection) and so, just like the pebbles and the sheep, there must be the same number of elements in each one. Therefore the sets of natural numbers and even numbers are the same size. By a similar process we can see that the odd numbers are also the same size.
The bijection between the natural numbers and the even numbers
Cardinality
We use the word ‘cardinality’ to denote the number of elements (items) in a set. For example card{a, b, c} = 3 as there are three elements in this group. Card{pack of playing cards} = 52 as there are 52 playing cards in a pack. Cantor used the Hebrew symbol ‘aleph’ with a zero after it to represent the infinite number of elements in the natural numbers and so we write card{N} = aleph nought.
As we have seen above, the sets of even numbers and odd numbers are the same size as the set of natural numbers and so card{E} = card{O} = aleph nought.
What about other sets of numbers?
As we have seen above, the sets of even numbers and odd numbers are the same size as the set of natural numbers and so card{E} = card{O} = aleph nought.
What about other sets of numbers?
Aleph nought
The rational numbers
In between all of the natural numbers, there are fractions such as 1/2, 1/3, 6/5 etc. The set of all numbers that can be written as fractions is known as the rational numbers or Q. Intuition suggests that are more rational numbers than natural numbers. After all, the set of rational numbers contains the natural numbers and all the fractions in between them. But is this the case? What is the cardinality of the set of rational numbers? Let’s start by looking at the positive rational numbers.
We start by writing out the natural numbers in a row. Beneath this we write all of the fractions with 2 as a denominator which do not already appear on the top row e.g. we skip 4/2 as this equals 2 which is on the top row.
On the third row we write all fractions with 3 as a denominator, again skipping any which have already appeared in the rows above. We continue doing this infinitely.
Look at the diagrams below. You can see from these that it is possible to trace a path (shown in the right-hand diagram) through our list of fractions (shown in the left-hand diagram) such that every fraction is covered. We can therefore match each fraction up with its numbered position on the path; hence we have a bijection between the natural numbers and the positive rational numbers. Therefore the two sets are the same size and card{positive rational numbers} = aleph nought.
We can also create bijections between the natural numbers and all integers (positive and negative). See if you can work out a way to do this.
This leads us to card{whole numbers} = card{rational numbers} = aleph nought.
The sets we have seen, as well as other sets with cardinality aleph nought are described as being 'countably infinite' or 'numerable'.
We start by writing out the natural numbers in a row. Beneath this we write all of the fractions with 2 as a denominator which do not already appear on the top row e.g. we skip 4/2 as this equals 2 which is on the top row.
On the third row we write all fractions with 3 as a denominator, again skipping any which have already appeared in the rows above. We continue doing this infinitely.
Look at the diagrams below. You can see from these that it is possible to trace a path (shown in the right-hand diagram) through our list of fractions (shown in the left-hand diagram) such that every fraction is covered. We can therefore match each fraction up with its numbered position on the path; hence we have a bijection between the natural numbers and the positive rational numbers. Therefore the two sets are the same size and card{positive rational numbers} = aleph nought.
We can also create bijections between the natural numbers and all integers (positive and negative). See if you can work out a way to do this.
This leads us to card{whole numbers} = card{rational numbers} = aleph nought.
The sets we have seen, as well as other sets with cardinality aleph nought are described as being 'countably infinite' or 'numerable'.
Creating a bijection between the natural numbers and the rational numbers
The irrational numbers
The irrational numbers are numbers that cannot be expressed as a fraction with integer numerator and denominator. When written as decimals, these numbers neither end nor repeat. Famous examples include π and √2. The set of all rational (can be expressed as a fraction) and irrational numbers is called the real numbers and can be denoted as R. So what is card{R}?
We have seen that if we can create a bijection between the natural numbers and the irrational numbers, then they must be of the same cardinality. To make this simpler, let’s see if we can create a bijection between the natural numbers and all real numbers between 0 and 1.
Let’s assume we can create a list of all of the real numbers.
All real numbers can be written as an infinite decimal e.g. 0.15789… or 0.200000… and so our set can be written as {r1, r2, r3, r4, …} where r1 = 0.a1a2a3a4…, r2 = 0.b1b2b3b4..., r3 = 0.c1c2c3c4… etc. where a1, b1, c1 etc. are digits between 0 and 9 inclusive.
Suppose now we create a new number x = 0.x1x2x3x4… where x1 ≠ a1, x2 ≠ b2, x3 ≠ c3, etc. As x differs from all of the numbers in our list by at least one decimal place, it must lie outside our set. This contradicts our initial statement of creating a list of all real numbers, hence this list cannot be written. This idea is known as the diagonalization argument. The reason why can be seen in the diagram below.
As we cannot write a list of all of the elements of the set, we cannot create a bijection. This extends from the real numbers between 0 and 1 to the set of all real numbers too. Therefore the set of real numbers is not the same size as the set of rational numbers. It is in fact larger and Cantor denoted this as card{set of real numbers} = aleph one.
It can also be shown that the imaginary numbers have a cardinality of aleph one (see the links below for further reading on this).
We have seen that if we can create a bijection between the natural numbers and the irrational numbers, then they must be of the same cardinality. To make this simpler, let’s see if we can create a bijection between the natural numbers and all real numbers between 0 and 1.
Let’s assume we can create a list of all of the real numbers.
All real numbers can be written as an infinite decimal e.g. 0.15789… or 0.200000… and so our set can be written as {r1, r2, r3, r4, …} where r1 = 0.a1a2a3a4…, r2 = 0.b1b2b3b4..., r3 = 0.c1c2c3c4… etc. where a1, b1, c1 etc. are digits between 0 and 9 inclusive.
Suppose now we create a new number x = 0.x1x2x3x4… where x1 ≠ a1, x2 ≠ b2, x3 ≠ c3, etc. As x differs from all of the numbers in our list by at least one decimal place, it must lie outside our set. This contradicts our initial statement of creating a list of all real numbers, hence this list cannot be written. This idea is known as the diagonalization argument. The reason why can be seen in the diagram below.
As we cannot write a list of all of the elements of the set, we cannot create a bijection. This extends from the real numbers between 0 and 1 to the set of all real numbers too. Therefore the set of real numbers is not the same size as the set of rational numbers. It is in fact larger and Cantor denoted this as card{set of real numbers} = aleph one.
It can also be shown that the imaginary numbers have a cardinality of aleph one (see the links below for further reading on this).
The Diagonalisation Argument
Further alephs
One fascinating aspect of Cantor’s measures of infinity is that the list of alephs themselves go on to infinity. In essence, there are an infinite number of sizes of infinity. The proof of this is beyond the scope of this article, but again, the links below provide some fascinating reading around this.
Comments
Don't forget to leave your comments below.