You probably have some idea of what infinity means. Something that is infinite goes on forever. But it might surprise you to know that there are different kinds of infinity, and some are bigger than others!
As a simple example, a small circle is infinite in the sense that you can loop around and around the circle forever. At the same time, your entire path along the circle is bounded in the small area of the circle. Compare that to the straight line that extends to infinity. If you travel that line, you follow a path that goes forever in some direction.
What if we draw a larger circle outside the small circle. If there are an infinite number of points on the small circle and an infinite number of points on the large circle, does the larger circle have the same number of points as the small one? [The answer is yes.]
To understand all this, we have to first talk a bit about numbers.
We can start with the counting numbers. They have been with us the longest. From the beginning humans have found it useful to count things: sheep, coins, people; even ships and mountains.
Before numbers were really invented, humans used a one-to-one relationship between what was being counted and some way of representing the count. Hash marks in clay, pebbles in a bag, knots in a rope, are all such representations.
If you’ve ever counted something using the “prisoner’s hash marks,” you’ve used this early counting method.
Technically, it’s called base one notation. One mark (or knot or pebble) stands for one something. A rope with 30 knots is a lot easier to cart around than 30 sheep. Or 30 ships!
Because the process of counting things is natural, the counting numbers are formally known as the natural numbers.
Mathematicians have a symbol that represents the natural number; the symbol is N (or ℕ).
Many of the natural numbers have names: one, two, three,… fifteen, fifty, hundred, and so on. Others are named by tacking names together: fifty-seven, twelve-hundred-and-ninety-nine, and so on.
It might surprise you, but there is no agreement on whether zero is included in the natural numbers. Some do; some don’t.
(In part, this is due to zero having come along later in western mathematics. At first there was no symbol to stand for the unmarked clay, the unknotted rope, the empty pebble bag.)
The next step along the way was the need to sometimes represent a part of something.
If one day’s work was worth one loaf of bread; a half day’s work is worth a half loaf. How many loaves does a worker who worked 10 half days get?
Somehow you had to add up 10 half loaves.
That example is simple enough, but it’s just the start.
Once you develop a way to handle fractions of things, it gets harder. In school, you’ve probably had to add 2/3 to 1/5, and that’s not as intuitive as adding ten halves!
Numbers which are fractions, that can be represented as a/b, are called rational numbers; their symbol is Q (or ℚ), for quotient.
All natural numbers are also rational numbers. For instance, five is 5/1.
Rational numbers have a decimal expansion form. For example, 1/2 is 0.5, 1/5 is 0.2 and 1/3 is 0.333…
That last one illustrates an important point: the decimal form of rational numbers extends forever. In fact, it always extends forever. Technically speaking, 1/2 is 0.500…, and 1/5 is 0.2000…
Another important case comes from 1/11, which is 0.090909…
The decimal expansion of rational numbers either repeats the same digit or it repeats a pattern of digits.
A more complex pattern comes from 2/7, which gives us 0.285714285714285714…
If there are rational numbers, you might think there could be irrational numbers.
You’d be right! All numbers with a decimal point are called real numbers; they have the symbol R (or ℝ). Real numbers with repeating sequences are rational; real numbers that never repeat are irrational.
Irrational numbers cannot be represented with fractions (because all fractions result in rational numbers).
Nearly all real numbers are irrational numbers! The most famous irrational number is π (pi). The digits of π go on forever and never repeat.
Now we’re finally ready to get back to the idea of infinity.
You probably know that the natural numbers, the counting numbers, are infinite.
You can start counting and keep counting forever. No matter how big a number you name, you can always add a one to it to make a bigger number.
This fact is actually the theoretical basis of the natural numbers.
The process of adding a one to a number to get the next number in line is called a successor function.
We can count the natural numbers because there is a successor function (the successor function called “add one”).
Which brings us to the first important concept of infinity: There is a type of infinity that can be counted.
The counting goes on forever, but you can always name the next number in line, no matter where you are in the count.
It turns out that even the rational numbers are countable.
You can design a successor function that enumerates the rational numbers, because rational numbers have the form a/b, and since ‘a‘ and ‘b‘ are natural numbers (which are countable), rational numbers are countable.
This brings us to the second important concept of infinity: All countable infinities are the same “size.”
Suppose you list the natural numbers: 1, 2, 3,…
And then you also list them by tens: 10, 20, 30,…
Even though the second list skips nine numbers for every number on the list, both lists are the same size! (The same logic applies if we take, for example, just the even numbers: 2, 4, 6…)
We prove this by showing that, for every number on the first list, there is a corresponding number on the second list (and vice-versa).
We call this mapping one set (list) onto another. If the map is one-to-one, then the set size must be the same.
The set of natural numbers and the set of rational numbers are also the same size.
You might think the set of fractions was bigger with all those fractions between each natural number, but the two sets can be mapped onto each other, which means they must be the same size.
The same size of infinity. Countable infinity.
Now consider the irrational numbers.
What is the first number after π?
We know the digits of π go on forever with no pattern. A successor function adds something to the current number to generate a new number. What can we add to π to generate the next number? We need something along the lines of an infinity of zeros followed by a one.
But infinities go on forever, so we never stop with the zeros, which means we never get to the one!
And that means we can never name the next number after π. Or the one right below it.
In fact, for any given real number (natural, rational or irrational), we can never name the next irrational number.
Which brings us to the third important concept about infinity: The irrational numbers cannot be counted, because there is no successor function.
What this ends up meaning is that the set of all irrational numbers is a larger infinity than the set of natural (or rational) numbers. There is no map between the two sets.
About 130 years ago, a mathematician by the name of Georg Cantor came up with an elegant proof demonstrating that the real numbers (which includes rationals and irrationals) were uncountable.
His proof uses a trick, called the diagonal argument, that I’ll explain when we take this topic up again.
For now, remember these facts about infinity:
- The natural and rational numbers are infinite but countable.
- All countable infinities are the same size.
- The irrational numbers are infinite and uncountable.
- Uncountable infinities have a larger “size” than countable infinities.
Until next time, don’t count your chicken enchiladas until they’re served!
Update 11/10/2014: The diagonal argument is discussed in detail in the Sideband #54: Cantor’s Diagonal post.