A light year is about 6 trillion miles and the U.S. national debt reached 18 trillion dollars in 2015. Numbers of this magnitude are almost impossible to comprehend, but compared to infinity they are rather small. The German mathematician Georg Cantor (1845-1918) invented set theory and the mathematics of infinite numbers which in Cantor’s time was considered counter-intuitive, utter nonsense, and simply wrong. Many of Cantor’s contemporaries considered him to be nothing more than a charlatan. Set theory and the mathematics of infinite numbers are now part of mainstream mathematics.
To understand why Cantor upset so many mathematicians, I need to explain a basic concept of Cantor’s set theory. The cardinal number of a set or collection of objects equals the number of objects the set contains. Therefore the cardinal number of a gross of pencils equals 144 and the cardinal number of a mole of atoms is about 6.023 x 1023. For finite sets, the concept of cardinality is simple and straight forward, but for infinite sets the concept of cardinality can be counter-intuitive and utter nonsense. Cantor proved that the cardinal number of one infinite set can be greater than the cardinal number of another infinite set; infinity no longer necessarily equals infinity. Cantor also proved that there are infinitely many levels of infinity. In other words, there are infinitely many different infinite cardinal numbers!
What does Cantor mean when he says that two so seemly different infinite sets can have the same cardinality? Why are there as many real numbers between 0 and 1 as there are from –∞ to +∞? Why are there as many counting numbers as there are rational numbers? Why is the cardinality of the set of rational numbers less than the cardinality of the set of real numbers? The purpose of this post is to provide answers to these questions without delving into formal abstract mathematics. If you want a mathematically rigorous discussion of cardinal numbers and set theory, take a graduate level course in set theory or point-set topology. My previous post Relations, Functions, and One-to-One Functions discussed concepts that will be used in this post and therefore readers may find it helpful.
To get started, I will do a quick review of the different types of real numbers. All real numbers are either rational or irrational. The set of rational numbers is composed of counting numbers, whole numbers, integers, and numbers that can be expressed as the ratio of two integers. The decimal expansion of all rational numbers starts to repeat in a pattern of fixed finite length at some point. The decimal expansion of an irrational number never starts to repeat in a pattern of fixed finite length. The text boxes below give examples of the different types of real numbers. Note that there is a pattern in the decimal expansion of n, but the length of the pattern increases. The term “real number” is unfortunate because it suggests that some numbers are valid and other numbers like the imaginary numbers are fake numbers.
Cantor uses the concept of cardinality to define when two sets have the same cardinality. Set A has the same cardinality as set B if and only if there is a one-to-one function that matches elements of A with elements of B such that the domain of the function is set A and the range of the function is set B. When both sets have a finite number of elements, this definition makes perfect intuitive sense. Example: When two bags of golf balls contain an equal number of golf balls, it’s easy to see how we can match the golf balls one-to-one, to show that the two bags of golf balls have the same cardinality. When both sets A and B have infinitely many elements, Cantor’s definition leads to a new and profound understanding of the nature of infinity. The matching rule for the one-to-one function in Cantor’s definition may be described by an equation or general algorithm that tells us how to match domain elements with range elements.
Using Cantor’s definition, let’s see why it makes sense to say that the set of real numbers between 0 and 1 has the same cardinality as the set of real numbers greater than 1. Initially, this seems preposterous. Two numbers are reciprocals if and only if the product of the two numbers equals 1. It’s a mathematical fact that every nonzero real number has a unique reciprocal and the reciprocals of two numbers are different if the numbers are different. If 0 < n < 1, then 1/n > 1. If n > 1, then 0 < 1/n < 1. Therefore the one-to-one function y = 1/x with domain equal to the open interval (0, 1) and range equal to the open interval (1, ∞) leads us to the conclusion that the open intervals (0, 1) and (1, ∞) have the same cardinality. Graph A below shows the graph of this function. If you think about it, the only practical way to show that two sets have the same cardinality is to show that there exists a one-to-one function that pair wise matches the elements of the two sets.
I will now demonstrate that the open interval (p, q) has the same cardinally as the open interval (-∞, +∞) for any pair of real numbers p and q such that q > p. Let the width of the interval w = q – p and midpoint of the interval m = (p + q)/2. The one-to-one function y = Tan(π/w(x – m) with domain (p, q) has a range equal to (-∞, +∞). From Cantor’s definition, it follows that the cardinality of the open interval (p, q) equals the cardinality of the open interval to (-∞, +∞). Graph B below illustrates that the open interval (0.75, 1.25) has the same cardinality as the open interval (-∞, +∞).
The next part of this post will demonstrate that the cardinality of the counting numbers equals the cardinality of the positive rational numbers. This will be accomplished by showing that there is a one-to-one function, f, that matches the counting numbers with the positive rational numbers. The matching rule of the one-to-one function is an algorithm that describes how we can systematically go about matching every counting number with a unique positive rational number in such a manner that every positive rational number gets matched with a counting number. Mathematicians say that the rational numbers are countable.
The algorithm for the matching rule of the one-to-one function is as follows:
1) Organize the positive rational numbers in a rectangular grid as shown below.
2) Start in the upper left corner of the grid. Set the counting number n = 1 and let f(n) = 1/1.
3) Continue moving from grid element to grid element forever as indicated in the diagram. If grid element p/q is not equivalent to a previous function value, then increase n by 1 and let f(n) = p/q. If grid element p/q is equivalent to a previous function value, then skip the grid element and go to the next grid element. (Note that skipped grid elements in the diagram are crossed out.)
Now for Cantor’s famous diagonal proof that the real numbers are not countable. His proof used the sophisticated technique of proof by contradiction which is commonly used by mathematicians to prove a theorem. The diagonal proof goes something like this.
- Assume that there is a one-to-one function f(n) that matches the counting numbers with all of the real numbers. The box below shows the start of one of the infinitely many possible matching rules for f(n) that matches the counting numbers with all of the real numbers. The real numbers in the range of the function are represented as strings of base 2 real number digits or binary digits (i.e. consisting only of zeros and ones).
- Now construct a real number p as follows: Let n equal any counting number and f(n) equal the corresponding function value.
- If the nth binary digit of f(n) = 0, then set the nth binary digit of p = 1.
- If the nth binary digit of f(n) = 1, then set the nth binary digit of p = 0. (See the text box below.) It’s clear that the real number p is not in the range of f(n) which in turn contradicts the original assumption about f(n). Therefore the cardinality of the real numbers is greater than and the cardinality of the counting numbers and the real numbers are not countable.
Some Comments Regarding Cardinal Numbers and Real Numbers:
- The symbol for the cardinal number of the counting numbers is ℵ0. (aleph naught)
- The symbol for the cardinal number of the real numbers is ℵ1.
- The continuum hypothesis states that there is no cardinal number between ℵ0 and ℵ1.
- If you can prove the continuum hypothesis, you will become world famous overnight.
- There are infinitely many rational numbers between any two real numbers.
- The rational numbers are an infinitely small fraction of the real numbers.
- To work with irrational numbers in practical applications, we use rational numbers to approximate irrational numbers. (3.1416 ≠ π)
- The points, lines and curves that we draw on a chalkboard or computer screen are just crude approximations of true mathematical points, lines, and curves.
- True mathematical points and curves are infinitely thin, and therefore they can’t reflect light which in turn tells us that we really can’t see true mathematical points and curves in the physical sense.
- Mathematical objects only exist in the mind of man and God.