Counting Infinities ∞

In the post I will give a brief discussion about how to understand the size or cardinality of an infinite set. To start with something easy to understand let us first consider the set A = {1, 2, 3, 4, 5}. If I asked you how many elements are in this set we could find the answer by simply counting the number of objects in the set. So for the set A we see that it has 5 elements. In mathematics we say that the cardinality of the set A is 5.

Can you find any other sets with a cardinality of 5? Of course there are an infinite number of such sets. For example, the sets {8, 4, 3, 9, 10} and {100, 7, - 10, 11, 0} also are examples of sets with cardinality of 5.

We would like to define the cardinality for infinite sets as well. Let us consider the infinite set of integers (whole numbers) Z = {..., -2, -1, 0, 1, 2, ...}. How can we define the cardinality of such an infinite set? If we try to just count the elements of the set we will never complete the task because we will have to do it forever. Thus we need another way to understand the cardinality of a set besides counting the number of elements.

Let us consider the finite sets A = {1, 2, 3, 4, 5} and B = {8, 4, 3, 9 , 10} which we know both have cardinality 5. We will show another way to determine these sets have the same cardinality without counting the elements. The idea is that we can find a bijection between the sets A and B. A bijection is just a way to put the elements of the two sets in 1 to 1 correspondence with each other. So for the sets A and B we can do this as follows

1 -> 8
2 -> 4
3 -> 3
4 -> 9
5 -> 10

where the numbers on the left side are elements of A and on the right side are the elements of B. Notice that for each element of A we have assigned exactly one element of B and all the elements of A and B appear on their respective sides. Thus we have shown that we have the same number of elements in A and B by this 1 to 1 correspondence.

We can use this same idea to define the cardinality of an infinite set. Thus for any two sets (including infinite sets) we will say that they have the same cardinality if there is a bijection (1 to 1 correspondence) between the elements of a set. Let us briefly consider the two finite sets A = {1, 2} and B = {-2, -1, 0, 1, 2}. Since these are finite sets we can find their cardinalities by just counting the elements. It is clear that A has cardinality 2 and B has cardinality 5 so there is no bijection between the sets.

Now let us consider the two infinite sets N = {0, 1, 2, ...} (natural numbers) and Z = {..., -2, -1, 0, 1, 2, ...}. So N is the set of all nonnegative whole numbers and Z is the set of all whole numbers including the negatives. These are both infinite sets and we would like to know if they have the same cardinality. Intuitively we might think the set Z has more elements than N because it contains every element of N plus all of the negative numbers which are not in N. However, we need to be careful when dealing with infinite sets and it turns out that N and Z actually have the same cardinality. We can show this by giving a 1 to 1 correspondence between the elements of N and Z as follows:

0 -> 0
1 -> -1
2 -> 1
3 -> -2
4 -> 2
5 -> -3
6 -> 3
7 -> -4
8 -> 4
...

and continue the pattern. So we are assigning the even numbers of N to the nonnegative numbers in Z and the odd numbers of N to the negative numbers in Z. If we continue in this manner we have assigned every element of Z to exactly one element of N so we have a bijection from N to Z and the cardinalities are the same.

This shows some of the counter intuitive and interesting behavior of the cardinality of infinite sets. It can also be shown that the set of rational numbers Q has the same cardinality as N but that the cardinality of the set of real numbers R (irrational numbers) is larger than the cardinality of N. Any set with the same cardinality as N is called countably infinite and the set R of real numbers is called uncountable. Can you find any other infinite countable sets than the ones described here? Let me know in the comments!