**Georg Cantor (1845 – 1918)**

In this unit we will discuss the infinite. You probably have an understanding of the infinite. For example, you know that the set of natural numbers N = {1, 2, 3, 4, 5, …} is an infinite set as are the real numbers R. It was the genius of Cantor who says that N and R are very different infinite sets. In a way, he shows us that there are *levels* of infinity.

We say that the *cardinality* of two sets A and B are the same – written card(A) = card(B), if there is a one-to-one correspondence between these two sets. So, for example, there is a one-to-one correspondence between the sets A = {1, 2, 3, 4, 5} and B = {a, b, c, d, e}. We do this by 1 → a, 2→b, 3→c, 4→d, 5→e. So we say that card(A) = card(B). If we have two sets with a finite number of elements in it, the concept of cardinality means, as it should, the number of elements in the set.

**Warning: **Don’t get fooled (or confused) by the notation card(A) = card(B). When A and B are finite sets then card(A) and card(B) are numbers (integers) and equality is just equality of integers. When A and B are infinite sets then card(A) and card(B) are not numbers any more and “card(A) = card(B)” does not mean we are comparing numbers. It just means that there is a one-to-one correspondence between the sets A and B. We will see in a little while that there is a notion of card(A) < card(B)!

What about infinite sets? How do we compare infinite sets?

**Example:** *The cardinality of N (the natural numbers) is the same as the cardinality of the even numbers*. That is to say, card({1, 2, 3, 4….}) = card({2, 4, 6, 8…}). We can do this by the correspondence 1→2, 2→4, 3→6,….n→2n,…….. This is kind of interesting that the even numbers are a proper subset of the natural numbers but they, in some strange way, have the “same” number of elements.

**Example:** *The cardinality of the natural numbers {1, 2, 3, 4, …..} is the same as the cardinality of the natural numbers with zero included {0, 1, 2, 3, …..}. *We can do this by the correspondence 1→0, 2→1, 3→2, ……, n→n – 1,…….. Thus card({1, 2, 3….}) = card({0, 1, 2, 3…}).

**Example:** *The cardinality of the natural numbers is the same as the squares of the natural numbers.* The one-to-one correspondence is 1→1², 2→2², 3→3², …..,n→n²,…………

**Example: ***card((0, 1)) = card((0, 2)).* The one-to-one correspondence is given by the following diagram.

In other words, a point on (0, 1) corresponds to the point on (0, 2) which lies on the same red line.

**Example:*** card((0, 1)) = card(R).* Again, a drawing explains the one-to-one correspondence.

So far, the examples have been relatively easy. Here is a more surprising correspondence.Recall that N = {1, 2, 3, ….} (the natural numbers). Let us use the letter Q to denote the positive rational numbers Q = {p/q: p, q are in N}. Certainly Q contains N but it contains a lot of other numbers too such as 1/2, 4/5, 11/99, etc…

**Theorem ****(Cantor):** *card(N) = card(Q).*

**Proof:** This is a wonderful argument called the *Cantor diagonalization argument*. First we list all of Q (the positive rational numbers) in the following way

Now, like in the above drawing, weave your way through the rational numbers assigning the next natural number to a rational number you have not seen before. So, using the drawing above,

1→1/1 2→1/2 3→2/1 4→3/1 5→1/3 (skip over 2/2 since we have seen 2/2 = 1/1 before) 6→1/4 7→2/3 8→3/2 ….This correspondence will be a one-to-one correspondence between N and Q. Thus card(N) = card(Q). **QED.**

Stand back and think about this and realize how intriguing this is. There seem to be so many more rational numbers Q than there are natural numbers N yet they have the same cardinality.

Just in case you are being lulled in to believing that *all* infinite sets have the same cardinality, here is another surprise.

**Theorem (Cantor):** *The cardinality of the natural numbers is not the same as the cardinality of the real numbers. In other words, there is no one-to-one correspondence between the natural numbers and the real numbers.*

**Proof:** This is a variation of Cantor’s diagonalization argument. We will argue by contradiction (like we did in proving that the square root of 2 was irrational). Suppose there *were* a one-to-one correspondence between N (the natural numbers) and R (the real numbers). Then we could match up each natural number with a real number (written in decimal form)

We will now create a real number which is not on this list. Define a number as follows:

This new real number 0.683175…. is not equal to the real number corresponding to 1 (since it differs from 2.397… in the first decimal place). It is not equal to the real number corresponding to 2 (since it differs from 14.526613… in the second decimal place). It is not equal to the real number corresponding to 3 (since it differs from 0.498310…) in the third decimal place. This new number 0.683175…..is not on our list. Thus this list in incomplete and this there is no one-to-one correspondence between N and R. So card(N) is *not* the same as card(R). **QED.**

Wow! This shows that there are, in some weird sense, different types of infinity. Perhaps you are thinking that there are “more” real numbers than natural numbers. Though there are an “equal amount” of rational numbers as there are natural numbers.

Way back when we studied Archimedes, we considered the number π and mentioned that it was irrational. We didn’t prove this but it is nevertheless true. If you know some calculus, you can prove that π is irrational. Here is a link with several proofs. What is more amazing, and more difficult to prove, is that π is *transcendental. *This means that π is not the root of any polynomial with integer coefficients. Numbers which are roots of polynomials with integer coefficients, are called* algebraic*. For example, any integer n is algebraic since it is the root of the polynomial x – n. Any rational number p/q is also algebraic since it is the root of the polynomial q x – p. The number √2 (though irrational) is algebraic since it is one of the roots of x² – 2.

An application of Cantor’s diagonalization argument (it is a bit tricky and technical so we won’t do it here) will show the following:

**Theorem:** *The cardinality of the algebraic numbers is the same as the cardinality of the natural numbers.*

Cantor’s theorem, in some strange way, says that “most” real numbers are transcendental! However we only can prove a few special ones are transcendental.

Here are some known transcendental numbers. Keep in mind that proving a number is transcendental is very very difficult. Click here for the references.

π, e, (√2)^(√2), e^(π), ln(2), sin(2), cos(2), tan(2)Now things get really weird.

**Theorem (Cantor):** *card(R) = card(R^2). In other words, there are just as many real numbers as there are points in the plane.*

**Proof **(this proof is from Proofs from the Book): We will show a slightly different version of this, namely the cardinality of the open interval (0, 1) is the same as the cardinality of the open unit square {(x, y): 0 < x, y < 1}.

Consider a pair (x, y) in the unit square (i.e., 0 < x, y < 1). Write their decimal expansions as

x = 0.301200708… y = 0.00920510008…… x = 0.3 01 2 007 08…. y = 0.009 2 05 1 0008…..This pair (x, y) will correspond to the point z = 0.30090122050071080008….**QED**

After Cantor, people wondered if such a one-to-one correspondence between [0, 1] and [0, 1] x [0, 1] could be made to be continuous. It can’t. This was shown by Netto in 1879. If one is willing to insist that the correspondence does not have to be injective, then there are numerous examples which get us into the topic of space filling curves.

**Theorem (Cantor):** *card(R) = card(R³)*

**Proof:** Exercise.

Now things get really strange. Let’s get some notation for this. In class we discuss the notion 1-1 and onto.

card(A) ≤ card(B) means that there is a 1-1 map from A to B

card(A) < card(B) means that there is a 1-1 map from A to B but there is no onto map from A to B.

**Example:** card(N) = card(Q)

**Example**: card((0, 1)) = card(R)

**Example:** card(N) < card(R) since there the map x → x from N to R is 1-1 but Cantor says that card(N) is not card(R).

Given any set A, define P(A), the *power set* of A to be the set of all subsets of A.

**Example**: A = {1, 2, 3}, P(A) = {ø, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}}

**Example:** A = {a, b, c, d, e, f, g}

P(A) = {ø, {a}, {b}, {c}, {d}, {e}, {f}, {g}, {a, b}, {a, c}, {a, d}, {a, e}, {a, f}, {a, g}, {b, c}, {b, d}, {b, e}, {b, f}, {b, g}, {c, d}, {c, e}, {c, f}, {c, g}, {d, e}, {d, f}, {d, g}, {e, f}, {e, g}, {f, g}, {a, b, c}, {a, b, d}, {a, b, e}, {a, b, f}, {a, b, g}, {a, c, d}, {a, c, e}, {a, c, f}, {a, c, g}, {a, d, e}, {a, d, f}, {a, d, g}, {a, e, f}, {a, e, g}, {a, f, g}, {b, c, d}, {b, c, e}, {b, c, f}, {b, c, g}, {b, d, e}, {b, d, f}, {b, d, g}, {b, e, f}, {b, e, g}, {b, f, g}, {c, d, e}, {c, d, f}, {c, d, g}, {c, e, f}, {c, e, g}, {c, f, g}, {d, e, f}, {d, e, g}, {d, f, g}, {e, f, g}, {a, b, c, d}, {a, b, c, e}, {a, b, c, f}, {a, b, c, g}, {a, b, d, e}, {a, b, d, f}, {a, b, d, g}, {a, b, e, f}, {a, b, e, g}, {a, b, f, g}, {a, c, d, e}, {a, c, d, f}, {a, c, d, g}, {a, c, e, f}, {a, c, e, g}, {a, c, f, g}, {a, d, e, f}, {a, d, e, g}, {a, d, f, g}, {a, e, f, g}, {b, c, d, e}, {b, c, d, f}, {b, c, d, g}, {b, c, e, f}, {b, c, e, g}, {b, c, f, g}, {b, d, e, f}, {b, d, e, g}, {b, d, f, g}, {b, e, f, g}, {c, d, e, f}, {c, d, e, g}, {c, d, f, g}, {c, e, f, g}, {d, e, f, g}, {a, b, c, d, e}, {a, b, c, d, f}, {a, b, c, d, g}, {a, b, c, e, f}, {a, b, c, e, g}, {a, b, c, f, g}, {a, b, d, e, f}, {a, b, d, e, g}, {a, b, d, f, g}, {a, b, e, f, g}, {a, c, d, e, f}, {a, c, d, e, g}, {a, c, d, f, g}, {a, c, e, f, g}, {a, d, e, f, g}, {b, c, d, e, f}, {b, c, d, e, g}, {b, c, d, f, g}, {b, c, e, f, g}, {b, d, e, f, g}, {c, d, e, f, g}, {a, b, c, d, e, f}, {a, b, c, d, e, g}, {a, b, c, d, f, g}, {a, b, c, e, f, g}, {a, b, d, e, f, g}, {a, c, d, e, f, g}, {b, c, d, e, f, g}, {a, b, c, d, e, f, g}}

**Proposition:** *If card(A) = n, then card(P(A)) = 2^n.*

**Proof: **The way you form a subset of A it to decide if each member of A will be an element of your subset. The set of all possible decisions will correspond to the set of all subsets of A. For example, if you decide that no member of A will belong to your subset, then your subset is the empty set. If you decide that every member of A will belong to your subset, then your subset will be all of A. If you decide that the first element of A will belong to your subset, then your subset will be a one element subset. So, for each element of A, you can make two choices (include the element in the subset or not). Each choice will correspond to a different subset. Thus there are two choices for the first element, two for the second, two for the third,….., and two for the nth element. This leaves with 2^n choices. **QED**

Notice for finite sets A that card(A) < card(P(A)) since the first has size n and the second has size 2^n. Here is the amazing fact. The same holds for* any set whatsoever! Finite or not!
*

**Theorem (Cantor):** *If A is any set, then card(A) < card(P(A)).*

**Proof:** See class notes.

This is a truly amazing fact. This shows that there are levels of infinity and there is no “biggest” infinity. Just think about it, if N is the natural numbers then we have the following string of inequalities.

card(N) < card(P(N)) < card(P(P(N))) < card(P(P(P(N))))) < ……..

After thinking about this for a while, take a well deserved nap.

In case you are wondering, Cantor also proved that card(P(N)) =card(R). We will discuss this more when we talk about the continuum hypothesis.