  # Infinity: Cantor's Theorems

Natural numbers stem from two elementary procedures: counting and comparing. You can compare sizes without counting as follows: A "set" is a collection of different things, usually of numbers. A set is displayed by listing the elements between "{" and "}". What we want to do is to compare the size (cardinality) of sets. When you can match each element of the first set with some element of the second set in pairs such that no element remains unmatched, then the sets have equal size (cardinalities). Now certain sets, like the set {1,2,3,4, ... } of all natural numbers, contain infinitely many elements. Note that nothing in real life is really infinite, according to present scientific theories everything: diameter of the universe, number of atoms, even time are finite.

It was the Czech mathematician Bernard Bolzano (1781-1848) who showed in 1847 that infinite sets could have the same cardinality as proper subsets, like in the examples.

Now let's try to compare different infinite sets. Which one has more numbers, the set of all even natural numbers ? {2,4,6,8, ... } or the set of all natural numbers {1,2,3,4,...}? According to the definition above, they have the same cardinality, since there is a matching between the elements, namely n --- 2n, every natural number n is matched with the even number 2n. The next example was the set {...-3,-2,-1,0,1,2,3,...} of all integers, which has the same cardinality as the set of all natural numbers. The matching now is more difficult to express as a formula, but the pattern would be 1 <---> 0, 2 <---> 1, 3 <---> -1, 4 <---> 2, 5 <---> -2, 6 <---> 3, and so on.

## Cantor's Theorems

Which one is larger: the set of rational numbers or the set of natural numbers? It turns out that both have the same cardinality.

1. Theorem of Cantor: The set of natural numbers and the set of rational numbers have the same cardinality.

Proof: We write all rational numbers on the board in a scheme like shown below. Obviously every rational number occurs---we can even say in which row and column---but since rational numbers have also representations other than that in lowest terms, each rational number occurs often (infinitely many times, in fact). Then we start in the middle, at 0, go around in spirals as shown below, and match the numbers visited with the natural numbers. However, if a number visited is already in the list (in a different representation), we just skip this number. Click the button below to see the procedure.

 1/5 2/5 3/5 4/5 5/5 6/5 1/4 2/4 3/4 4/4 5/4 6/4 1/3 2/3 3/3 4/3 5/3 6/3 1/2 2/2 3/2 4/2 5/2 6/2 -5/1 -4/1 -3/1 -2/1 -1/1 0 1/1 2/1 3/1 4/1 5/1 6/1 -5/2 -4/2 -3/2 -2/2 -1/2 -5/3 -4/3 -3/3 -2/3 -1/3 -5/4 -4/4 -3/4 -2/4 -1/4 -5/5 -4/5 -3/5 -2/5 -1/5
 natural 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 rational

Eventually will arrive at every element (we can even estimate when). Therefore we have a matching between the set of natural numbers and the set of rational numbers, and the two sets have the same cardinality.

#### Georg Cantor (1845-1918)

He was born in Russia and later lived in Germany, becoming a professor in Halle but really wanting to work at the famous University of Berlin. He is best known as founder of set theory and his theorems on cardinal numbers. Very surprising was his result that some infinite sets are larger than others. His main work on cardinalities was around 1874-1884. His enemies included Leopold Kronecker, and Henri Poincaré who raised philosophical objections and said natural numbers came from god and everything is created otherwise. They made his life miserable. After much criticism he suffered depression or Bipolar disorder. More information can be found here or here.

For the next theorem, note that two real numbers that differ in one decimal place are different, except in cases with periodic 9. For instance, 0.556999... is equal to 0.557. (Why is 0.9999... = 1? 0.9999... = 3*0.333... = 3*(1/3) = 1.) One could avoid these representations, but in any case it is safe to say that two real numbers that differ in at least one decimal position without being "0" and "9" are different.

2. Theorem of Cantor: The cardinality of the set of real numbers is strictly larger than the cardinality of the set of natural numbers.
Proof: This is not Cantor's original proof, but the one he found around 1891. Onve again, the method of proof is "Reducto ad Absurdum". Assume both sets have the same cardinality. Then there must be a matching. Let an be the real number matched with the natural number n, and let pn be the nth digit after the decimal point of an. We construct a number r that is not on the list as follows: First we combine all these digits pn into a new number s. For all n, the nth digit of s after the decimal point is pn, s = 0.p1p2p3... . Then we change each digit (and avoid changing a "0" into a "9" or a "9" into a "0"). Therefore the resulting number r differs from every an at the nth digit (by at least 2) (since an has digit pn, but r has something else.) Therefore r is different from all these numbers an, therefore r is a real number not occuring in the matching, a contradiction.

In the last part of class we were shown a third result on cardinalities of infinite sets. A subset of a given set M is any set containing only (some) members of M as elements. The three-element set {A,B,C} for instance has 8 possible subsets: {ABC}, {AB}, {AC}, {BC}, {A}, {B}, {C}, { }. More general, an n-element set has 2n subsets. The "power set" P(M) of a set M is the set of all subsets. Cantor showed that the cardinality of the power set of the set of natural numbers equals the cardinality of the set of real numbers. He also showed:

3. Theorem of Cantor: For every (infinite) set M, the cardinality of the power set P(M) is larger than the cardinality of M itself.

Therefore there are infinitely many different cardinalities of infinite sets: The power set P(R) of the set R of real numbers has higher cardinality than R, the power set P(P(R)) of P(R) has higher caridnality than P(R), and so on.