How many numbers of each type are there? Can two infinities be equal? Can one infinity be larger than another infinity?

Number Of Natural Numbers

How many natural numbers (1, 2, 3, …) are there? Is there a largest such number? Do the discrete natural number points on the number line eventually come to a stop?

To answer these questions, let’s use an amusing and powerful logical technique called proof by contradiction (or reductio ad absurdum which is Latin for reduction to absurdity). In such a proof, we assume a statement is true. Then we draw a conclusion from the assumed true statement, following logical steps, and find that the conclusion is wrong/absurd/contradictory. This must mean that the statement that was assumed to be true is false. The original statement has been proven false by contradiction.

As a warm-up, let’s prove by contradiction that there is no largest natural number. Suppose that there is a natural number, let’s call it L, which is larger than all other natural numbers. Then, since natural numbers are closed under addition (i.e. adding two natural numbers gives another natural number), the number obtained by adding 1 to L, let’s call it M, is also a natural number. And, M is larger than L (e.g. because it is one spot to the right of L on the number line). But this contradicts the initial assumption that L is the largest natural number. So that assumption must have been incorrect and we have proved that there is no largest natural number. Natural numbers are unbounded above. The natural number points on the number line extend to infinity to the right. There are infinite natural numbers.

Number Of Whole Numbers

The set of whole numbers is the set of natural numbers and zero. Does this mean there is 1 more whole number than natural numbers? No!

Every natural number corresponds to exactly one unique whole number (e.g. 1 -> 0, 2 -> 1, 3 -> 2, … in other words n -> n-1). And there are no remaining whole numbers that are not mapped to by a natural number. This is called a one-to-one-correspondence between natural numbers and whole numbers. When such a one-to-one-correspondence exists between two infinite sets, it means that the two infinite sets have the same number of elements. The number of whole numbers is equal to the number of natural numbers, both sets being infinite, even though natural numbers are a proper subset of whole numbers!

Another way to think about a one-to-one-correspondence between a set of numbers and natural numbers is that the set of numbers can be enumerated (starting at index 1) without leaving anything out in the set. Such an enumeration for whole numbers would be the following:

1. 0
2. 1
3. 2
4. …

Number Of Integers

Integers are made up of all whole numbers (0, 1, 2, 3, …) and non-fractional negative numbers (-1, -2, -3, …). Surely there are more integers than whole numbers (possibly somewhere in the vicinity of twice as many to account for a negative integer for each natural number)? No!

In fact, the number of integers is the same as the number of natural numbers! How can that be? It must be because there is a one-to-one-correspondence between integers and natural numbers. Here’s an enumeration of all integers that establishes that correspondence:

1. 0
2. 1
3. -1
4. 2
5. -2
6. …

The precise correspondence is that an odd natural number, ‘o’, corresponds to exactly one unique non-positive integer (1-’o’)/2 (so 1 -> 0, 3-> -1, 5 -> -2, …). And an even natural number, ‘e’, corresponds to exactly one unique positive integer ‘e’/2 (so 2 -> 1, 4 -> 2, 6 -> 3, …). The number of integers is equal to the number of natural numbers, both sets being infinite, even though natural numbers are a proper subset of integers!

Number Of Rational Numbers

Rational numbers are made up of integers and fractions of the form p/q (where p, q are integers and q ≠ 0). How many rational numbers are there? Infinite, of course. You can clearly see that by the fact that just between 0 and 1 there are infinitely many rational numbers of the form 1/2, 1/3, 1/4, and so on. It seems that there ought to be infinitely more rational numbers than integers, right? Wrong again!

There is in fact a one-to-one-correspondence between natural numbers and rational numbers leading to the surprising conclusion that the number of rational numbers is the same as the number of integers! The details of the correspondence are a little complicated so I’ll just give you a taste of it. You can enumerate all rational numbers in increasing order of the sum of the numerator and denominator, skipping any previously seen number. So, for a sum of 1, we have the rational 0/1 or 0. For a sum of 2, we have the rational 1/1 or 1. For a sum of 3, we have two rationals: 1/2 and 2/1 or 2. For a sum of 4, we have the following previously unseen rationals: 1/3, 3. For a sum of 5, we have 1/4, 2/3, 3/2, 4. And so on. Once we have a well-defined enumeration that accounts for all the rational numbers, we have a one-to-one-correspondence between natural numbers and rational numbers.

Let that sink in. Although there are infinitely many rational numbers between any two consecutive integers, the number of rational numbers is still equal to the number of integers. This seemingly counterintuitive result is due to the fact that we don’t have much intuition for infinity. Although integers appear to be less dense than rationals on the number line, the fact that integers are unbounded allows us to map each integer to exactly one unique rational number without running out of integers and without leaving any rationals out.

Number Of Irrational Numbers

Irrational numbers are real numbers that are not rational. An irrational number’s decimal expansion has an infinite number of digits after the decimal point, with no infinitely repeating pattern.

How many irrational numbers are there? Infinite, no surprise there. By now we probably expect the number of irrational numbers to be the same as the number of rational numbers (which in turn is the same as the number of natural numbers). But irrationals will belie this expectation. The number of irrational numbers is in fact larger than the number of rational numbers. Here’s a case of one infinity being bigger than another infinity! We can prove this by contradiction: assume irrationals can be fully enumerated and then find an irrational that is not in the enumeration.

Here’s a sketch of the proof. Consider the following arbitrary enumeration of irrational numbers (the details of the enumeration are not important, as long as there is an enumeration):

1: 3.141…

2: 1.414…

3: 2.718…

4: …

Now construct another irrational number in a very particular way. Its first decimal digit will be 1 more than the first decimal digit of the first number in the enumeration, giving 0.2… So this number will clearly be different from the first number. Its second decimal digit will be 1 more than the second decimal digit of the second number in the enumeration, giving 0.22… So this number will clearly be different from the second number. Its third decimal digit will be 1 more than the third decimal digit of the third number in the enumeration, giving 0.229… So this number will clearly be different from the third number. And so on, for all decimal digits to infinity. This irrational number is different from every irrational number in the enumeration. So irrational numbers cannot be enumerated without missing at least one irrational number. This means there cannot be a one-to-one-correspondence with natural numbers and there are more irrational numbers than natural numbers (and consequently more irrational numbers than rational numbers).

Let that sink in. These weird irrational numbers that you probably have not encountered too frequently in your life, there are many more of them than the familiar integers and rational numbers. In fact, there are infinitely many more of them. If you were to close your eyes and pick a point at random on the number line, you will most likely pick an irrational number!

Infinite Weirdness

We have seen that infinite sets can be pretty counterintuitive. Let’s recap some of this weirdness and savor it:

1. An infinite set (e.g. integers) and an infinite proper subset of the set (e.g. natural numbers) can have the same number of elements. In fact, all the following infinite sets have the same number of elements: natural numbers, whole numbers, integers, even numbers, odd numbers, prime numbers, etc.
2. A more dense infinite set (in a geometric representation of the set) can have the same number of elements as a less dense infinite set. This can hold even if one set is infinitely denser than another set. For example, rational numbers are infinitely denser than integers on the number line. And yet there is the same number of rationals as integers.
3. Some infinite sets have more elements than other infinite sets. For example, there are infinitely more irrational numbers than rational numbers.

For an elementary overview of real numbers and their subtypes (naturals, wholes, integers, rationals, irrationals) see “Real Numbers, From The Ground Up”.