Agnijo's Mathematical Treasure Chest banner
Home > Number theory > Set theory

Types of infinity


Suppose you had all the natural numbers 1, 2, 3... and counted them. There would be an infinite number. This set is known as a countably infinite set. A set is countably infinite if and only if you can put all the elements in a list labelled 1, 2, 3 and so on. This can give rise to some counterintuitive results. The mathematician Hilbert devised a thought experiment known as Hilbert's Hotel to analyse this. Hilbert's Hotel is simply a hotel with rooms numbered 1, 2, 3... Thus it has infinitely many rooms.


Hilbert's Hotel

First, consider the set of all natural numbers and 0. Is that set countable? You can put them in a list in the following way: 0, 1, 2, 3... So this set is countable. Consider the analogous situation in Hilbert's Hotel. Hilbert finds that he has a guest in each room (assuming there are infinitely many people). Then a new guest arrives and wants a room. Even though there are no empty rooms, the guest can still get a room. Hilbert asks the guest in Room 1 to move to Room 2, the guest in Room 2 to move to Room 3, and so on. Room 1 is empty so the guest can stay. In a finite hotel this doesn't work as the guest in the last room has no room to go to. However, in an infinite hotel there is no last room. In the end, each original guest still has a room to themselves but the new guest also has a room.

Now, consider the set of all integers. Is that set countable? Here is the list: 0, 1, -1, 2, -2, 3, -3... This set is also countable. In Hilbert's Hotel, Hilbert again has a guest in every room and finds a bus parked outside his hotel. This bus has infinitely many passengers, in seats numbered 1, 2, 3, 4... Now, Hilbert can still fit all of the guests in his hotel. He asks the guest in Room 1 to move to Room 2, the guest in Room 2 to move to Room 4, and the guest in Room n to move into Room 2n. Now all odd-numbered rooms are free for the bus passengers. The passenger in seat 1 moves to Room 1, the passenger in seat 2 moves to Room 3, and the passenger in seat n moves to Room 2n-1. Thus you can fit an infinite bus full of passengers into a full hotel.


Rational numbers

It gets stranger still. Consider the set of all rational numbers. Is this set countable? It is much harder this time. Here is an array of rationals:

1/1 1/2 1/3 1/4 1/5 1/6 1/7 ...
2/1 2/2 2/3 2/4 2/5 2/6 2/7 ...
3/1 3/2 3/3 3/4 3/5 3/6 3/7 ...
4/1 4/2 4/3 4/4 4/5 4/6 4/7 ...
5/1 5/2 5/3 5/4 5/5 5/6 5/7 ...
6/1 6/2 6/3 6/4 6/5 6/6 6/7 ...
7/1 7/2 7/3 7/4 7/5 7/6 7/7 ...
...

Now consider the diagonals from top-right to bottom-left. List these in order to get this list: 1/1; 1/2, 2/1; 1/3, 2/2, 3/1; 1/4, 2/3, 3/2, 4/1; and so on. Now remove duplicates e.g. 2/2, add 0, and add negatives to get the list: 0, 1, -1, 1/2, -1/2, 2, -2, 1/3, -1/3, 3, -3, 1/4, -1/4, 2/3, -2/3, 3/2, -3/2, 4, -4... This contains every rational number.

In Hilbert's Hotel, there is a guest in every room when an infinite array of buses come, numbered Bus 1, 2, 3, and so on. Each bus can hold infinitely many people. Hilbert first wants to move everyone to Bus 1. How does he go about doing this? He first assigns each person a two-number address. The first number is their bus number and their second number is their seat number. For example, the person in seat 1 of Bus 3 has the address 3-1..Here is the array:

1-1 1-2 1-3 1-4 1-5 1-6 1-7 ...
2-1 2-2 2-3 2-4 2-5 2-6 2-7 ...
3-1 3-2 3-3 3-4 3-5 3-6 3-7 ...
4-1 4-2 4-3 4-4 4-5 4-6 4-7 ...
5-1 5-2 5-3 5-4 5-5 5-6 5-7 ...
6-1 6-2 6-3 6-4 6-5 6-6 6-7 ...
7-1 7-2 7-3 7-4 7-5 7-6 7-7 ...
...

He takes the diagonals in order: 1-1; 1-2, 2-1; 1-3, 2-2, 3-1; 1-4, 2-3, 3-2, 4-1; and so on. Now everyone must move to Bus 1. 1-1 goes into seat 1, 1-2 goes into seat 2, 2-1 goes into seat 3, 1-3 goes into seat 4, etc. Now everyone is in Bus 1 so all other buses can go away. The situation now is that there is only one infinite bus. However, Hilbert already knows how to deal with this. Thus everyone gets into his hotel.


Real numbers

You may now think that any set is countable or that any group of people can fit into Hilbert's Hotel. However, this is not the case. Consider the real numbers. Suppose you have a list of real numbers from 0 to 1 (1=0.9999999...) inclusive. Here is an example list, but the same principles can work with any list. It does not have to be in order of magnitude.

0.1234567...
0.0000000...
0.9999999...
0.1415926...
0.7182818...
0.1111111...
0.9876543...
...

Now construct a real number x. Its first digit is the first digit of the first real number. Its second digit is the second digit of the second real number etc. In this case, x=0.1095813... Now, construct a real number y such that the nth digit of y is different from the nth digit of x. Here is an example: y=0.2106924... Is y on our list? It is clear that y is not the first number as the first digit of y is different from the first digit of x, which is the first digit of the first number. Likewise, the second digit of y is different from the second digit of the second number. In general, the nth digit of y is different from the nth digit of the nth number so y is not the nth number. In short, y is not on our list. Thus no list of real numbers between 0 and 1 inclusive can be made, in which case there is no list of real numbers, as such a list would also contain all real numbers between 0 and 1.


Types of cardinals

In fact, every cardinal infinity (an infinity that describes the size of an infinite set) has a name beginning with aleph. Countable infinity is aleph-0, which is the smallest infinity. This is the number of natural numbers, integers, and rational numbers. The next infinity is aleph-1. However, for the remainder of this article, it will be more convenient to talk about beth numbers. Aleph-0 is equal to beth-0. Now, the set of real numbers between 0 and 1 inclusive has cardinality beth 1. The set of all real numbers also has cardinality beth 1. How can this be the case? For this to be true, there must be a one-to-one correspondence between the sets. It is easier to start with the following statement: The set of real numbers from 0 to 1 inclusive has te same cardinality as the set of real numbers from 0 to 1 exclusive. Here is a one-to-one correspondence:

If the number is of the form 2s,where s is an integer <= 0, then map it to 2s-2.
If the number is 0, map it to 1/2.
Else, map the number to itself.

It is possible to prove (using similar techniques to Hilbert's Hotel) that every element in one set maps to exactly one element in the other set. Thus there are as many real numbers between 0 and 1 inclusive as real numbers between 0 and 1 exclusive. Now consider the set of real numbers between -π/2 and π/2 exclusive. Does this have the same cardinality as the set of real numbers between 0 and 1 exclusive? It turns out that it does. Map every number x in the first set to (x/π)+1/2 in the second set. Thus these sets have the same cardinality. Finally, what about the set of all real numbers? Does this have the same cardinality as the set of reals between -π/2 and π/2 exclusive? Simply map x to tan-1(x). As long as you work in radians, this map works. (If you prefer degrees, replace π wherever it appears in this argument with 180.) Thus there are as many real numbers as real numbers from 0 to 1 inclusive. This number is beth-1.


Beth-2

All this had been proved by Georg Cantor (although with a different one-to-one correspondence). His next aim was to find a cardinal larger than that of the set of reals (beth-1, which he called the continuum or c). There are as many reals as points on an infinite Euclidean line (just consider a number line) so his next idea was to consider the plane. First, he showed that there are as many points on the plane as points in a square with vertices (0,0), (0,1), (1,1), (1,0). Simply take the fact that there are as many reals as reals from 0 to 1 inclusive, and apply it to both co-ordinates of any point. Now, he proved that there are c (or beth-1) points on this plane. Let a point be (0.abcdefg, 0.hijklmn) where 1=0.9999999... Now, this maps to 0.ahbicjdkelfmgn... For example, (0.3141529..., 0.7182818) maps to 0.37114812582198.. Thus there are beth-1 points on the plane. When he first proved this Cantor was so shocked that he exclaimed "I see it but I do not believe it." However, there is a set with cardinality beth-2. It is the set of functions from R to R. It can be proved that there are more functions from R to R than real numbers in a manner very similar to Cantor's diagonal argument.. Assume otherwise. Then, for every real number x, there is a function fx. Construct the function g(x) = fx(x) + 1. Does g map to a real? If so, there exists an x such that g = fx. Then g(x) = fx(x). However, g(x) = fxx + 1 so g is not fx. The function g does not map to any real. Thus there is no one-to-one correspondence between functions and reals. There are more functions than reals. In fact, there are beth-2 functions.


The continuum hypothesis

You may notice that I have been using beth numbers rather than aleph numbers. This is a very important point. Cantor conjectured that c = aleph-1 but could not prove it. This is the continuum hypothesis and was the first of Hilbert's 23 problems. It was solved in 1963 by Paul Cohen, who proved that it cannot be proved in ZFC. It can be taken as an axiom without making the system inconsistent (assuming ZFC is consistent in the first place) but its negation can also be taken as an axiom (as long as you don't take both at once). If the continuum hypothesis is true, aleph-1 = beth-1. In fact, there is a more general version called the general continuum hypothesis. This states that for any ordinal α, aleph-α = beth-α. However, there is a family of axioms known as forcing axioms. If these are assumed, the continuum hypothesis can be proven false.


Related entries

   •Coming soon