Countable and uncountable sets

A set is a collection of objects. In this article, we will look at how we go about counting the elements in a set. In particular, we will investigate how we might count the elements in an infinite set, and if that is even possible.

This has some interesting and counter-intuitive results and eventually leads to the idea that there are many different kinds of infinity.

Counting finite sets

Here is a simple set containing some numbers:

This is a finite set because it contains a finite number of elements.

We count the elements of the set in the same way that a small child might count out sweets. We say the first element is 1, the second is 2, and so on. In other words, we assign a natural number to each element in turn, starting at 1 and increasing by 1 for each new element:

We say that a set is countable if it is possible to assign a unique natural number to each element in turn. This means that all finite sets are countable because we can just assign incrementing natural numbers to each element as we described above. For infinite sets, things get a little more involved.

The result of counting the elements of a finite set is that we know how many elements there are in the set. We call this the cardinality of the set. This can be written using the modulus notation:

Reordering

Suppose we arranged the elements of S in a different order:

We can still call this set S because a set is defined by the elements it contains, regardless of their order. This time a different natural number will be mapped onto each of the elements:

Even though the order of the elements is changed, the cardinality is still 4. That is because reordering the element doesn't change how many elements there are. The order of the elements is not important when determining the cardinality.

Can an infinite set be countable?

Is it possible for an infinite set to be countable? It might seem counterintuitive, but yes certain infinite sets are countable.

We can prove this by example - the set of natural numbers, N.

This set is clearly infinite because there are infinitely many natural numbers.

The set is also countable. Remember that to be countable it must be possible to assign a unique natural number to each of the elements in the set. Well, we can do that with the set of natural numbers simply by using the numbers themselves. The value 1 in the set is at position 1. The value 100 in the set is at position 100. The value 1,000,000 in the set is at position 1,000,000.

Being countable doesn't mean that it is literally possible to count them all - that is impossible because there are infinitely many of them. Being countable simply means that for any element, it is possible to know the position of that element in the set, assuming a particular ordering of the set.

What is the cardinality of the set of natural numbers? Well, of course, there are infinitely many natural numbers. But as we will see shortly, some infinite sets are more infinite than others, so when we are talking about the cardinality of sets we have different names for the different cardinalities.

The cardinality of the set of all natural numbers is called aleph 0, written as:

Other infinitely countable sets

What about the set of all the even natural numbers (we will call it E):

In this case, we can map every element of N onto an element of E simply by multiplying it by 2. So the first natural number (which is 1) maps onto first element of E (which is 2). The second natural number (which is 2) maps onto second element of E (which is 4), and so on. This is a one-to-one correspondence - every natural number maps onto exactly one element in E, and every element of E maps onto exactly one natural number. The mapping is shown here:

Since there is a one-to-one relationship between the two sets, then if the set of natural numbers is countable, the set E must also be countable.

Furthermore, the two sets must also have the same cardinality, aleph 0. They both contain exactly the same number of elements.

This last fact leads to a rather counterintuitive result. The number of even natural numbers is equal to the number of all natural numbers. At first, that might seem like nonsense, as this diagram shows:

This shows the set of all natural numbers, N, the set of all even numbers, E, and the set of all odd numbers, O. Since N contains all the elements in E as well as all the elements in O, how could N possibly be the same size as E?

We can prove that it is, using proof by contradiction. If N contains more elements than E, then there must be an element in N that has no corresponding element is E. But that can't be true, because every element in N is a unique natural number, and if we multiply that number by 2 we get a unique even natural number. So N cannot contain any element that doesn't correspond to an element in E. Therefore N cannot contain more elements than E.

Now let's look at another set, the set of all integers, which we will call Z:

This set of numbers is different because it extends to infinity in both directions. It also contains all the negative numbers, which don't exist at all in the natural numbers. Surely Z must be bigger than N?

Well, no it isn't. If we rearrange the elements in Z we get a sequence that starts at 0 and extends to plus and minus infinity, like this:

The translation between N and Z looks like this:

As a final example, let's look at the set of all pairs of two integers (x, y), which we will call set C. These are all the points on the xy plane where the coordinates are both integers, stretching out to infinity in every direction:

This time we have an entire 2-dimensional plane of points, each specified by 2 integers. Surely this set must be larger than the single number line of the set N?

Well, again no it isn't. We can order these points like this:

This allows us to make a one-to-one mapping between N and C, so once again this set is countable and has the same cardinality as N.

Since every rational number has the form x/y where x and y are integers, we can use a scheme similar to the one above to prove that the set of all rational numbers is also countable.

All countably infinite sets have the same cardinality

We say that an infinite set S is countably infinite if there is a one-to-one mapping between the S and the set of natural numbers, N.

Due to the one-to-one mapping, this means that every countable set has the same cardinality as N, which is aleph 0. So all countable sets are the same size.

The set S doesn't need to be a set of numbers, provided a one-to-one mapping can be defined. All that this really requires is to define an unambiguous order for the elements in the set, then each element can be mapped onto a natural number according to its position in the set.

So, for example, consider the set of all possible sequences, of any length, of the uppercase letters "A" to "Z". Example members of this set are "X", "ABC", and "COUNTABLE".

We can order these sequences first by length, then by alphabetical order:

• 26 single character strings, "A", "B" ... "Z"
• 26² 2 character strings, "AA", "AB" ... "ZZ"
• 26³ 3 character strings, "AAA", "AAB" ... "ZZZ"
• And so on.

So "A" would correspond to the natural number 1, "B" to 2, and "Z" to 26. "AA" would be 27, "AB" would be 28, and so on. This creates a one-to-one correspondence with N, so the set is countably infinite.

Uncountable sets

We have met so many countably infinite sets, some of them quite unintuitively so, that you would be forgiven for thinking that all infinite sets are countable.

But that isn't the case. Many sets are uncountable. Perhaps the most famous uncountable set is the set of real numbers, R.

Intuitively, we can understand why the real numbers might be uncountable. To be countable, we must be able to put all the members of the set in some kind of order.

This is easy for integer values because each integer is separate from all the others on the number line. We can visit the integer in order, as we have seen. It can be a simple order like 1, 2, 3... Or a more complex order like 0, 1, -1, 2, -2...

Real numbers aren't like that. Real numbers form what is called a dense set. This means that for any two real numbers, a and b, there will always be another real number c that is in between them. It doesn't matter how close a and b are, they will never be right next to each other, there will always be another number between them. That makes it impossible to define a sequence of real numbers that contains all the real numbers.

Cantor proved this result more formally, using his diagonal argument. Using this argument, for any countably infinite list of real numbers, it is possible to prove that there is at least one real number that is not in the list.

It will make things a little easier if we restrict ourselves to real numbers that are greater than or equal to 0, and less than 1. That is all the numbers that start with "0.", so we only need concern ourselves with the digits that appear after the decimal point. This does not affect the proof - if the real numbers in that restricted range are uncountable, it follows that the complete set of real numbers must also be uncountable.

We will create an infinite list of real numbers according to some method. For illustration, we have used random numbers in the required range, but this proof applies regardless of how the list is created. Here are the first few digits of the first few numbers in the list:

Now we change some of the digits of these numbers, Specifically, we will change the first digit of the first number, the second digit of the second number, and so on, all the way down the list. This changes all the digits on the diagonal, shown in red below:

It doesn't matter how we change the digit, provided we change it. We have chosen to add 1 to the digit, modulo 10 (so a digit of 9 becomes 0).

The diagonal is infinitely long, and we apply the change to every digit on the diagonal.

Now if we take all the diagonal digits, we can form a new number with an infinite number of digits, in this case 0.7454135209...

We can prove this new number can't be in the original list, as follows. It can't be the first element in the list because the first digit can't be the same. It can't be the second element in the list because the second digit is not the same, And so on.

So our countable list doesn't contain this particular real number. Therefore it cannot all the real numbers.

But this proof doesn't care how we created a list. Whatever method we used to create the list, it still wouldn't contain every real number.

This means that no countable set can contain every real number, therefore the cardinality set of real numbers must be greater than the cardinality of the natural numbers, aleph 0.