Today marks the 178th birthday of Georg Cantor. My topology professor at Tennessee, Bob Daverman, once told our class that when called upon to talk to laymen about mathematics, he brings up Cantorian Set Theory. “It’s easy to explain and it’s fascinating as hell.” Without further ado:
Consider the set A = {2, -7, 184, pi/2, 23/125, 0, -176, 2.8}. The cardinality of A is 8; we say this because when we point to each element of A in turn and say “one, two, three, four, five, six, seven, eight,” we are establishing a one-to-one correspondence between the elements of A and the elements of B= {1, 2, 3, 4, 5, 6, 7, 8}. Similarly, C={-8, 3, -34} has cardinality 3 because the elements of C can be put into a one-to-one correspondence with D={1, 2, 3}. Simple idea, not original with Cantor. It’s fairly painless to prove that, for example, the elements of B and D cannot be put into an one-to-one correspondence with each other. B and D are examples of finite sets.
Consider the set of N of natural numbers, N={1, 2, 3, 4, 5, ... }. It's easy to show that the elements of N cannot be put into an one-to-one correspondence with the elements of any finite set; N is infinite. The question is: what subsets F of the real numbers can have its elements put into an one-to-one correspondence with the elements of N? To do this, all you need is some algorithm which can match each element of F with a unique element of N, and vice versa. For example, {7, 8, 9, 10, ... }, {1/2, 1, 3/2, 2, 5/2, 3, ...} and Z={0, 1, -1, 2, -2, 3, -3, ...} can each be put into an one-to-one correspondence with N. (And, it follows, with each other.) Note that in each example you can figure exactly what the next element will be. Use Z to convince yourself that the order of the elements is irrelevant. (Z is standard notation: zahlen means "count" in German.)
Consider Q, the set of all rational numbers, positive and negative fractions, plus zero. (Q: "quotient".) Since, for example, 5/1 is a rational number, N is a proper subset of Q. Indeed, one can readily envision millions upon untold millions of elements of Q, rational numbers, which are themselves not elements of N. Example: -2/532826721 is in Q, but not in N. Here is Cantor's proof that the elements of Q can be put into a one-to-one correspondence with the elements of N; it's a sweet idea.
For each k>1, let G(k) be the set of all positive rational a/b, where a/b is reduced, that is, a and b have no common prime factors, such that a+b=k, along with -a/b. For example, G(2)={1/1, -1/1}, G(3)={2/1, -2/1, 1/2, -1/2}, G(4)={3/1, -3/1, 1/3, -1/3} (note that 2/2=1/1 is in G(2), not in G(4): 2/2 is not reduced), G(5)={4/1, -4/1, 3/2, -3/2, 2/3, -2/3, 1/4, -1/4}. It's easy to see that each plus or minus a/b is either in G(a+b) if a/b is reduced or in some G(k) where k<a+b if a/b is not reduced: -13/25 is an element of G(38), and 12/20=3/5 is an element of G(8). Each G(k) is finite and the G(k) are mutually disjoint: each a/b is in exactly ONE G(k). Here's how Cantor listed the elements of Q:
Q={0, G(1), G(2), G(3), ...} that is, he lists the elements of each G(k) in turn (which is possible because each G(k) is finite). In effect:
Q={0, 1/1, -1/1, 2/1, -2/1, 1/2, -1/2, 3/1, -3/1, 1/3, -1/3, 4/1, -4/1, 3/2, -3/2, 2/3, -2/3, 1/4, -1/4, ...}. Since each nonzero rational a/b is in exactly one G(k), we know that a/b is going to show up in this list, eventually, and exactly once. Done.
Of course, this wasn't all Cantor did; if this thread doesn't self-destruct I'll later explain his very simple proof that the real numbers CANNOT be put into an one-to-one correspondence with N.
I don't know how the layman will react to this but this was a very big deal back in Cantor's day, and he got a whole lot of grief over it; some very prominent mathematicians were very harsh about these ideas. To me it's one of the greatest things ever. Cormac McCarthy has a shrink ask a mathematician, "Is it worth it?" "Like nothing else on earth."
Consider the set A = {2, -7, 184, pi/2, 23/125, 0, -176, 2.8}. The cardinality of A is 8; we say this because when we point to each element of A in turn and say “one, two, three, four, five, six, seven, eight,” we are establishing a one-to-one correspondence between the elements of A and the elements of B= {1, 2, 3, 4, 5, 6, 7, 8}. Similarly, C={-8, 3, -34} has cardinality 3 because the elements of C can be put into a one-to-one correspondence with D={1, 2, 3}. Simple idea, not original with Cantor. It’s fairly painless to prove that, for example, the elements of B and D cannot be put into an one-to-one correspondence with each other. B and D are examples of finite sets.
Consider the set of N of natural numbers, N={1, 2, 3, 4, 5, ... }. It's easy to show that the elements of N cannot be put into an one-to-one correspondence with the elements of any finite set; N is infinite. The question is: what subsets F of the real numbers can have its elements put into an one-to-one correspondence with the elements of N? To do this, all you need is some algorithm which can match each element of F with a unique element of N, and vice versa. For example, {7, 8, 9, 10, ... }, {1/2, 1, 3/2, 2, 5/2, 3, ...} and Z={0, 1, -1, 2, -2, 3, -3, ...} can each be put into an one-to-one correspondence with N. (And, it follows, with each other.) Note that in each example you can figure exactly what the next element will be. Use Z to convince yourself that the order of the elements is irrelevant. (Z is standard notation: zahlen means "count" in German.)
Consider Q, the set of all rational numbers, positive and negative fractions, plus zero. (Q: "quotient".) Since, for example, 5/1 is a rational number, N is a proper subset of Q. Indeed, one can readily envision millions upon untold millions of elements of Q, rational numbers, which are themselves not elements of N. Example: -2/532826721 is in Q, but not in N. Here is Cantor's proof that the elements of Q can be put into a one-to-one correspondence with the elements of N; it's a sweet idea.
For each k>1, let G(k) be the set of all positive rational a/b, where a/b is reduced, that is, a and b have no common prime factors, such that a+b=k, along with -a/b. For example, G(2)={1/1, -1/1}, G(3)={2/1, -2/1, 1/2, -1/2}, G(4)={3/1, -3/1, 1/3, -1/3} (note that 2/2=1/1 is in G(2), not in G(4): 2/2 is not reduced), G(5)={4/1, -4/1, 3/2, -3/2, 2/3, -2/3, 1/4, -1/4}. It's easy to see that each plus or minus a/b is either in G(a+b) if a/b is reduced or in some G(k) where k<a+b if a/b is not reduced: -13/25 is an element of G(38), and 12/20=3/5 is an element of G(8). Each G(k) is finite and the G(k) are mutually disjoint: each a/b is in exactly ONE G(k). Here's how Cantor listed the elements of Q:
Q={0, G(1), G(2), G(3), ...} that is, he lists the elements of each G(k) in turn (which is possible because each G(k) is finite). In effect:
Q={0, 1/1, -1/1, 2/1, -2/1, 1/2, -1/2, 3/1, -3/1, 1/3, -1/3, 4/1, -4/1, 3/2, -3/2, 2/3, -2/3, 1/4, -1/4, ...}. Since each nonzero rational a/b is in exactly one G(k), we know that a/b is going to show up in this list, eventually, and exactly once. Done.
Of course, this wasn't all Cantor did; if this thread doesn't self-destruct I'll later explain his very simple proof that the real numbers CANNOT be put into an one-to-one correspondence with N.
I don't know how the layman will react to this but this was a very big deal back in Cantor's day, and he got a whole lot of grief over it; some very prominent mathematicians were very harsh about these ideas. To me it's one of the greatest things ever. Cormac McCarthy has a shrink ask a mathematician, "Is it worth it?" "Like nothing else on earth."
Last edited:
