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.
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.
Which one is larger: the set of rational numbers or the set of natural numbers? It turns out that both 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 |
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.
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.
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:
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.