How Many Numbers Are There? (Math Lair)

Math Lair Home > Topics > How Many Numbers Are There?

The number of elements in a set is called its cardinal number. The cardinal number of the empty set, for example, is 0. The cardinal number of the set of natural numbers up to and including 100 is 100. What about the set of all natural numbers? When I was a child I remember spending the better part of an afternoon counting to 1,000 and beyond, likely annoying the rest of my family in the process. If you did something similar, you likely discovered that you could always find another number larger than any given number. The natural numbers (also known as the positive integers, or counting numbers) are infinite in number.

The set of positive integers is customarily written
N = {1, 2, 3, 4, 5, ... }
where N stands for their formal name, the natural numbers. Note that we can list these numbers. We can arrange them in a manner such that, given part of the list, we can say what the next number on the list will be. We can denumerate the positive integers.

The cardinal number of all natural numbers is infinity, and has been given the name aleph nought (I use the notation a₀ here because of character set limitations). Aleph is the first letter of the Hebrew alphabet. Two sets have the same cardinal number if and only if there is a one-to-one correspondence between the elements of the sets.

Therefore, if a set can be put into one-to-one correspondence with the set of the natural numbers, then it has a₀ elements, the same number as the set of the natural numbers. This can lead to some rather counterintuitive conclusions. For example, have a look at Galileo's Paradox and Hilbert's Hotel. We call a set denumerably infinite or countably infinite if that set can be put into one-to-one correspondence with the natural numbers. We are able to make a (incomplete) list of the natural numbers, and we can tell what number comes after any given number.

It is a short step to show that the set of integers (denoted by Z), which is the union of the set of the positive integers, the set of the negative integers, and zero, is denumerably infinite. The following mapping is an example of how to put the integers in a one-to-one correspondence with the natural numbers:

 N       Z
 1 <--->  0
 2 <--->  1
 3 <---> -1
 4 <--->  2
 5 <---> -2
 6 <--->  3
 7 <---> -3
   . . .

We can also show that the cardinality of the set of rational numbers (denoted by Q) is also a₀. In other words, we can make a list of all the rational numbers. In order to make a list that is denumerable, we have to find a way to list them so that we know we will reach any given number if we continue long enough down the list. For example, we could make a list ordered by the size of the sum of the numerator and denominator, like:

  N          Q
  1         0/1
  2         1/1
  3         1/2
  4         2/1
  5         1/3
  6         3/1
  7         1/4
     . . .

It seems rather unintuitive to say that there are no more rational numbers than there are natural numbers, but we have shown this to be true. The concept of the "size" of an infinite set is counterintuitive to our normal thinking and is thus the basis of many paradoxes.

It can also be shown that the set of all algebraic numbers (numbers, whether rational or irrational, that are roots of a polynomial equation with integer coefficients) is also countably infinite.

Is there any set that is not countably infinite, that cannot be put into one-to-one correspondence with the natural numbers? What about the set of the real numbers (the set of real numbers contains all rational numbers and all irrational numbers)? We can show that this set is larger than the set of the natural numbers.

The proof is by Reductio ad absurdum. To show that this set is larger than the set of the natural numbers, let's start by assuming the opposite, that this set as the same cardinality as that of the natural numbers. This means that we could create some one-to-one correspondence between each natural number and each real number. So, let's assume that we have such a correspondence:

1 <--> 0.00000000...
2 <--> 0.14142135...
3 <--> 0.14159265...
4 <--> 0.12345678...
...

Now, let's create a real number as follows:

Take the first decimal place of the number paired with 1, and change the digit to anything other than what it currently is.
Take the second decimal place of the number paired with 2, and change the digit to anything other than what it currently is.
Take the third decimal place of the number paired with 3, and change the digit to anything other than what it currently is.
... and so on, to infinity.

Since our list contains all real numbers, with which natural number does this number correspond? It can't correspond with 1, because the first decimal place is different. It can't correspond with 2, because the second decimal place is different. It can't correspond with 3, because the third decimal place is different. As a matter of fact, it can't correspond with any natural number. This is a contradiction. Since we have reached a contradiction by assuming that the cardinality of the natural numbers and the cardinality of the real numbers is the same, that must mean that our assumption is wrong and the set of the reals is larger than that of the natural numbers.

We call the set of reals between 0 and 1 nondenumerable, or uncountably infinite. It has a cardinality greater than aleph nought. We say that the set of real numbers has cardinality aleph one (a₁), and that a₁ > a₀.

The cardinal number aleph nought is infinite in the sense that it is larger than any natural number. Yet there exists an "infinity" even larger than this one! There exist infinities even larger than this. For example, aleph two is the size of the set of all real curves. There may be a countably infinite hierarchy of "infinities", called transfinite cardinals.