Cantor, Gödel, Incompleteness and the Continuum

  1. Two sets have the same cardinality (the "same number of elements") if you can pair up their elements into a one-to-one correspondance. All sets with the same cardinality are assigned the same cardinal number.

  2. A set is called finite if there is no one-to-one correspondance between it and a proper subset of itself; otherwise it is called infinite. Let N denote the set of all positive whole numbers: the Natural Numbers. The correspondance $n\rightarrow 2n$ is a one-to-one correspondance between N and the proper subset of even natural numbers; thus, N is infinite.

  3. A finite set is always assigned the cardinal denoted by the usual counting number. Thus, the set of fingers on my left hand is assigned the cardinal 5; the set of planets is assigned the cardinal 9.

  4. The infinite set N is assigned the cardinal denoted $\aleph _{0}$ (read: aleph null). It is the first non-finite cardinal. The set of all integers (Z), the set of all rationals (Q) and the set of all algebraic numbers all have cardinal $\aleph _{0}$.

  5. George Cantor (1845--1918), in his famous "diagonal argument," showed that the set of all reals R (represented by decimals of finite or infinite length) can not be put into one-to-one correspondance with N. Thus, R has a cardinality greater than that of N. We usually use the symbol $\QTR{cal}{C}$ to denote this cardinal number: the cardinal number of the continuum.

    Theorem (The Continuum Hypothesis): Any subset of the real numbers is either finite, or has cardinal $\aleph _{0}$, or has cardinal $\QTR{cal}{C}$.

    For many years mathematicians tried to prove the Continuum Hypothesis, much the same way they had tried to prove the Parallel Postulate centuries ago; also without success.

  6. In 1931 Kurt Gödel (1906--1978) proved his famous theorem.

    Theorem (Gödel's Incompleteness Theorem):

    I. If mathematics is consistent, then there are statements for which neither they or their negations can be proved. [Such statements are called formally undecidable.]

    II. If mathematics is consistent, there can be no proof of this consistency within mathematics.

    (By mathematics we mean the basic axiomatic system that $20^{th}$-century mathematicians have been using. This includes the axioms which determine N, but doesn't include, of course, the Axiom of Choice.)

  7. In the years 1935-1938, Gödel was able to prove that the negation of the Continuum Hypothesis (as well as of the Axiom of Choice) could not be proved. In 1963, Paul Cohen (1934--2007) proved that neither the Continuum Hypothesis nor the Axiom of Choice can be proved; thus, both of these statements are now known to be Formally Undecidable. The work of Gödel and Cohen has showed us that the truth value of the Continuum Hypothesis is completely arbitrary and independent of the other axioms of mathematics. We will never "know" if there is a cardinal between $\aleph _{0}$ and $\QTR{cal}{C}$.