Cantor Defeated Galileo in the Battle of Infinite Numbers


Home / Cantor Defeated Galileo in the Battle of Infinite Numbers

While Cantor and Galileo did not squabble over their infinite sets, Cantor’s set of Real numbers is indeed larger than Galileo’s set of Natural numbers. How can one infinity exceed another?

Building a Foundation for Cantor’s Infinities

Understanding how Georg Cantor’s “Real” infinity is larger than the infinities in Galileo’s paradox requires dealing with set theory. We start with some definitions.

A Cardinal is More than Just a Bird

While a “cardinal” is a favorite red bird, the word “cardinality” in set theory has nothing to do with birds. When the elements of two sets can be placed in a one-to-one mapping, the two sets have the same “cardinality“. The cardinality of a finite set, such as the letters of the alphabet, is a specific finite natural number. For an infinite set, the cardinality is a trickier concept.

For any set A, the cardinality of A is shown as |A|.

You Can Count on the Natural Numbers

Define N to be the infinite set of Natural numbers {0, 1, 2,…}. (Thomas Jech’s article starts at zero; some of my previous articles excluded zero from the set of Natural numbers).

Any infinite set S is “countable” if |S| = |N|. That is to say, if there is a one-to-one mapping between S and N, then S is “countable”.

Cross Products and Rational Numbers are all Equally Countable

Threading a Cross Product of Sets

Countable Cross Product of Natural Numbers. Image by Mike DeHaan

Define a cross product of two sets “A X B” as follows. Let A = {a1, a2, a3…} and B = {b1, b2, b3…}. Then A X B = {(a1, b1), (a1, b2), (a1, b3)…(a2, b1), (a2, b2), (a2, b3)…(a3, b1), (a3, b2), (a3, b3)…}.

Can N map one-to-one to N X N?

Yes, Jech supplies such a mapping. Let function f(p, q) = ( (2^p)*(2*q + 1) – 1 ), where p and q are in N. The result n=f(p,q) will be in N. Will the triplets (p, q, n) be unique for every unique (p, q)? Yes. The factor “2^p” will be a power of two, unless p=0, in which case 2^0 = 1. Then we have the first triple = (0, 0, 1). The factor “(2*q + 1)” is never a multiple of two. Therefore each (p, q, n) will be unique.

Also, we can “thread” all the (p, q) by threading along the diagonals, as shown in the image “Countable Cross Product of Natural Numbers”.

Since f(p, q) gives a unique result for each unique (p, q) pair, and since we can “count” all (p, q) by the diagonal method, there is indeed a mapping between N and N X N.

Therefore |N| = |N X N|.

Dense Sets

Define any set D as “dense” if it has at least two numbers a and b, plus a “less than” relation (‘<‘), and the property that for all a and b in D, if a < b, then there is another number x in D such that a < x < b.

The Rational Numbers are Dense but Incomplete

Define Q as the set of rational numbers p/q, where p and q are in N, and q is not zero. Also allow repeatedly adding or subtracting ‘1’ from any element in Q, so this set is unbounded. The rational numbers are dense: we can always derive x = ( p + q )/2 to suit the definition of “dense”.

There is an obvious one-to-one mapping between Q to the cross product of N X ( N – zero ), namely the function f(p,q) = p/q.

Since there is also a mapping between N and ( N X N ), then there is a mapping between Q and ( N X N ) and therefore between Q and N. Therefore |Q| = |N|.

So Q is both “countable” and “dense”. It is countable because |Q| = |N|. It is dense because any two different elements in Q has another element between them.

Q is notcomplete“, however, because there are gaps. For example, the square root of two is not rational. No fraction can exactly equal 2^(1/2).

The Real Numbers are Complete

Define R to be the infinite set of Real numbers. This includes N, Q, roots like the square root of two, or 2^(1/2), transcendental numbers like pi (π), and any other non-imaginary and non-infinite number that anyone would invent.

Jech calls R the “completion” of Q. “Completeness” means that there are no gaps in R, although there are gaps in Q.

Galileo was a Natural at Infinities

The Paradox of the Infinite Series of Square Numbers by Galileo” explained that two infinities were the same. Specifically, Galileo dealt with the infinite number of natural numbers, both N and its subset, square numbers.

There may be no end to square numbers, but there are far fewer square numbers than natural numbers. On the other hand, since each natural number has a square, there must be exactly as many square numbers as natural numbers. If there is a one-to-one relationship between sets, they have the same cardinality.

The “Sparse or Dense…” image shows how these two mappings mappings coexist.

Sparse or Dense but 1-to-1 Image by Mike DeHaan (Non-square values on the left and squares on the right)

Georg Cantor Helps Galileo Get Real

Galileo’s Mismatched Example

Unfortunately, Galileo was trying to prove something about the Real numbers when he proved that infinite subsets of Natural numbers have the same cardinality. He truly was trying to deal with the number of points in two line segments of Real numbers, and claimed that there were as many points in a short Real line as in a longer Real line.

Galileo’s statement was correct, but his example was from a different situation, the natural numbers.

Georg Cantor’s Proof by Contradiction

Georg Cantor was up to the challenge, however. He used a “proof by contradiction”, which started with the assumption that |N| = |R|.

To keep it simple, let’s consider a Real number r, where 0 < r < 1. Then r can be written as an infinite string of digits, “ds”, after the decimal point.

We need to have an infinite number of rs, so let’s say that the “j-th” digit of the “i-th” number r is “d[i, j]”.

For example, let’s say that our first number is one-quarter or 0.25000…, and the second number is one-third or 0.333… Speaking of the digits to the right of the decimal place, we have d[1, 1]=’2′, d[1,2]=’5′, and d[1,k]=’0′ for all k>2. Likewise, d[2, k]=’3′ for all k.

Follow the Diagonal

Uncountable Real Numbers Image by Mike DeHaan

Cantor sets up the contradiction by making assumptions required to support the claim that |N| = |R|.

Cantor “assumes” there is a countable list of all Real numbers in R, and “assumes” that there is some way of ordering them to find the “i-th” number in the list. That would provide a one-to-one mapping from N to R.

Likewise, we can find the “j-th” digit of that “i-th” number: d[i, j].

Cantor then demonstrates the contradiction. He can construct a new Real number that is not equal to any of the listed numbers, which should have been the complete set of Real numbers. (In fact, he can continue to construct new, different numbers an infinite number of times).

How can he do this? Cantor can build the new exception, x, by “following the diagonal” of the listed numbers. Choose the “n-th” digit of the “n-th” Real number, which is d[n, n]. Make the new number’s n-th digit x[n] = 1 + d[n, n] unless d[n, n] is 8 or 9; in those cases, set x[n] = 3.

Therefore the new number x cannot be found in the list of Real numbers because it differs from the n-th listed number in the n-th digit. Therefore R cannot be mapped from N, and so |R| differs from |N|.

We are out of room to prove that |R| > |N|; in fact we don’t have room to discuss what ‘>means for infinite cardinality. Let’s note in passing that |R| is also the cardinality of several other sets, and that an ongoing controversy concerns whether any other cardinality exists between |R| and |N|.

Mathematicians do not need a space ship to explore the infinite.

Leave a Comment