﻿ Georg Cantor, Cantor's Theorem and Its Proof
San José State University

applet-magic.com
Thayer Watkins
Silicon Valley
USA

c. 1870

 Georg Cantor and Cantor's Theorem

Georg Cantor's achievement in mathematics was outstanding. He revolutionized the foundation of mathematics with set theory. Set theory is now considered so fundamental that it seems to border on the obvious but at its introduction it was controversial and revolutionary. The controversial element centered around the problem of whether infinity was a potentiality or could be achieved. Before Cantor it was generally felt that infinity as an actuality did not make sense; one could only speak of a variable increasing without bound as that variable going to infinity. That is to say, it was felt that n → ∞ makes sense but n = ∞ does not. Cantor not only found a way to make sense out an actual, as opposed to a potential, infinity but showed that there are different orders of infinity. This was a shock to people's intuition.

Georg Cantor was born March 3, 1845 in Saint Petersburg, Russia. His family background is a bit complex. His parents were of German-Jewish stock but both were Christian; his father was a Protestant and his mother a Catholic. They were Danish citizens. When Georg Cantor's family left St. Petersburg they settled in Germany and Cantor always considered his nationality as German.

Cantor's family initially did not sanction his becoming a mathematician, considering engineering a more practical vocation. Cantor first studied at the University of Zürich and later at the University of Berlin.

Georg Cantor's academic career was at the University of Halle, a lesser level university. He merited an appointment at a top level university in Berlin but opponents to his ideas, such as Leopold Kronecker, were able to prevent him from gaining such an appointment.

In later life, in his forties and thereafter, he was afflicted with bouts of mental illness, what is usually called nervous breakdowns. He died in 1918 in a mental institution at Halle, Germany.

## Cantor's Theorem: The cardinality of the set of all subsets of any set is strictly greater than the cardinality of the set; i.e., for any set A, cardinality(powerset(A)) > cardinality(A).

Often a result this fundamental is called a lemma.

## Proof:

To prove the theorem we must show that there is a one-to-one correspondence between A and a subset of powerset(A) but not vice versa. The function f:A→powerset(A) defined by f(a)={a} is one-to-one into powerset(A). Thus cardinality(A) < powerset(A).

To prove that the cardinality of powerset(A) is not equal to the cardinality of A let us assume there were a one-to-one onto mapping between A and powerset(A), say g:A→powerset(A). There are some elements of A which map into subsets of A of which they are a member and there are some which map into a subset which they are not a member of. Let N be the set of elements of A that do not map into a subset they are member of; i.e., N = {x∈ (belongs to) A and x∉ (does not belong to) g(x)}. Since N is a subset of A and g is one-to-one onto there must be an element z such that N=g(z). This sets up a contradiction. If z belongs to N it cannot belong to N. If it does not belong to N then it must belong to N. Therefore the assumption of the existence of a one-to-one onto function between A and powerset(A) leads to a contradiction and therefore must be false. Thus cardinality(powerset(A)) is strictly greater than cardinality(A). Thus for any cardinality there is another cardinal of a higher order.