Background

• Georg Ferdinand Ludwig Philipp Cantor lived 1845-1918
• Studied some with Weierstrauss, and wrote his dissertation at the age of 22 under Kummer and Kronecker
• Determined that Naturals is smaller than Reals in 1873
• Showed all real spaces have the same number of points around 1878
• Began struggle with Kronecker in late 1870s (Kronecker was a finitist who believed all math must be built of natural numbers)
• Developed his theory of transfinite ordinals in his Grundlagen einer allgemeinen Mannichfaltigkeitslehre ("Foundations of a general theory of sets"), published 1882.
• 1884 had first of several "mental break downs"
• Struggled in 1884 with continuum hypothesis
• Diagonal argument revealed 1891
• Disappointed by his inability to prove the continuum hypothesis, and by the attacks of Kronecker, he came to devote more and more of his life to being a pious Catholic

Basic concepts of set theory

• Sets are collections, and are wholly defined by their members (also called "elements"). The empty set, with no members, is also a set.
• Operators include: membership, subset, proper subset, identity. A set is defined by its members; if A and B are sets, and if the members of A are members of B, then A is a subset of B; if the members of A are members of B, but there are members of B not in A, A is a proper subset of B; but if A is a subset of B and B is a subset of A, then A=B.
• Power set: the power set P of some set S, written P(S), is the set of all subsets of S. The power set of {1, 2}, for example, is {{}, {1, 2}, {1}, {2}}.
• Functions. It's useful to have a notion of functions in order to make sense of the one-to-one relationship described in our definition of cardinality. The idea of a function is that it is a relation between two sets. The stuff that "goes into" the function is the domain, and the stuff that "comes out" of the function is the range. It is a special relation in that, if I put something in, I always get one and only one thing out. So, if we can write Fab to mean F is a function relating thing a of set A to thing b of set B, then it is the case that if Fab and Fac, then b=c. Some other useful terminology: a function F is....
  • from a set A if its domain is a subset of A
  • on a set A if its domain is A
  • into a set B if its range is a subset of B
  • onto a set B if its range is B
  • one-to-one if the following is true: if Fab and Fcb then a=c. Another way to say this is to say that the function is one-to-one if its inverse is a function (if reversed it is a function).
• Cardinality: the quantity of members of a set. For the cardinality of a set A we write |A|. Cantor defines cardinality in terms of functions relating sets. So:

  A and B have the same cardinality (for which we write |A| = |B|) if and only if there exists a function on A and onto B that is one-to-one.

• Two useful claims:
  • Useful Claim: If there is a function on A and into B that is one-to-one, then |A| ≤ |B|.
  • Useful Corollary: if A ⊆ B then |A| ≤ |B|.
• Cantor's Claim. We will call "Cantor's Claim," Cantor's observation that infinite sets can have proper subsets that are infinite, including proper subsets of the same cardinality. Examples include that the squares of the natural numbers have the same cardinality as the natural numbers, but the squares are a proper subset of the natural numbers.
• Cantor's Theorem. The cardinality of a set S is always smaller than the cardinality of its power set P(S).
• Ordinal numbers: numbers that are used to refer to a place in an order are ordinal (as opposed to cardinal).

The Diagonal Argument (and the Hierarchy of Cardinalities)

• Cantor named the cardinality of the natural numbers Aleph-0.
• The 1891 diagonal argument provides a powerful and simple proof that the cardinality of the reals exceeds that of the naturals.
  

  Proof: to show that the cardinality of the Reals is greater than the cardinality of the Naturals, assume this is false and show a contradiction results from this assumption.
  
  So: suppose the cardinality of the Reals were not larger than the cardinality of the Natural numbers. Then the cardinality of the Natural numbers would be greater than or equal to the cardinality of the Reals. Since every Natural number appears among the reals (the natural numbers is a subset of the reals), we know that there is a function on N and into R that is 1-to-1 (the identity function is one example); so |N| ≤ |R|. But if |N| ≥ |R| and |N| ≤ |R|, then |N| = |R|.
  
  If their cardinalities were the same, then there would be some function f on the naturals and onto the reals that is one-to-one. Suppose f is this function. That is, f(1) is some unique real number, and f(2) is a different unique real number, and so on; and the range of this function will be all of the real numbers. As we go from f(1), f(2), f(3), on forever, every real number number will eventually appear on this list as f(n) for some natural number n.
  
  Let us suppose then that we make a list of these mappings. That is, we list f(1), f(2), etc. For convenience, we will look only at the decimal extensions of these numbers (as you will see from the argument, that a real may be larger than 1 has no bearing on the the conclusion). We could then write this out:
  
  f(1) = a.a₁ a₂ a₃ a₄ a₅ a₆ a₇.....
  f(2) = b.b₁ b₂ b₃ b₄ b₅ b₆ b₇.....
  f(3) = c.c₁ c₂ c₃ c₄ c₅ c₆ c₇.....
  f(4) = d.d₁ d₂ d₃ d₄ d₅ d₆ d₇.....
  f(5) = e.e₁ e₂ e₃ e₄ e₅ e₆ e₇.....
  f(6) = f.f₁ f₂ f₃ f₄ f₅ f₆ f₇.....
  f(7) = g.g₁ g₂ g₃ g₄ g₅ g₆ g₇.....
  ....
  
  Here, a and so on are natural numbers; and a1 means some number between 0 and 9. That is, each of these is some decimal extension of a Real number.
  
  Now, we can construct the following number, z. Let z be the decimal extension where the first decimal place is a₁+1 (if a₁=9, then use 0), second decimal place is b₂+1, third is c₃+1, and so on. This is easy to construct if we have f, and this is also obviously a real number between 0 and 1. But z cannot be in this list. That is, z cannot be in the range of the function f. For any n, it cannot be the case that f(n)=z, because f(n) must differ from z at least at the nth decimal place of f(n).
  
  Note that z is obviously a Real number. Any decimal extension is a Real number. So z ∈ R.
  
  We assumed every real is in the range of this function, so z is on the list because z is real.
  
  BUT we just showed that z is not in the range of f, so z is not on the list.
  
  This is a contradiction. Something went wrong.
  
  What went wrong? We conclude it was the assumption that the cardinality of the Reals is not greater than the cardinality of the Naturals. (NOTE: we did not prove that the Reals have one more thing, z, than does the Naturals. That wouldn't make any difference to their cardinalities. Rather, we proved that it is contradictory to assumer that there is a function f on N and onto R that is one-to-one.)
  
  Hence, the Reals must be of a larger cardinaility than the Naturals. |R| > |N|.

• Cantor also showed that the cardinality of the power set of any set S is greater than the cardinality of that set; that is, for any set S, |P(S)| > |S|. From this, which we have called Cantor's Theorem, we can see that there is in fact an infinite hierarchy of cardinalities.

A Proof of Cantor's Theorem

Some of you asked me to post a version of this proof.

Let S be some arbitrary set. Suppose for reductio that ¬ |P(S)| > |S| (that is, it is not the case that the cardinality of the powerset of S is greater than the cardinality of S). Then |P(S)| ≤ |S|. But note: there is a simple function that is on S and into P(S) and is one-to-one. This the function that relates each element x, where x ∈ S, to the set of just that element {x}; note that by definition of powerset, {x} ∈ P(S) because x ∈ S. Since such a function exists, this tells us that |P(S)| ≥ |S|. So if |P(S)| ≥ |S| and |P(S)| ≤ |S|, then |P(S)| = |S|. So by definition of cardinality, there exists a function f on S and onto P(S) that is one-to-one. Now consider the set t ∈ P(S), where t is {x | x ∉ f(x)}. This is a little tricky. What it says is, t is the set of all those elements of S that are related by the function f to a set in P(S) that does not contain that element. Such a set must be in P(S) because every possible combination of elements of S, including the empty set, is in P(S). Now observe, the function f cannot relate any element of S to t. For suppose for some x ∈ S, f(x) = t. Is x ∈ t? If it is, then this contradicts the definition of t. But if it is not, then by definition it should be the case that x ∈ t. We conclude that the source of this contradiction was the assumption that ¬ |P(S)| > |S|. Hence |P(S)| > |S|.

Galileo redux

What about the lines of different length? And the squares? Cantor's claim provides a quick solution to both of these puzzles by Galileo.

(Instead, the modern claim that a finite group of points cannot make up a volume or area; and also that all line segments and volumes have the same number of points (aleph-1), solve the problem of the soapdish and his claims about our inability to reason about infinitesimals.)

Ordinal Numbers

Sets that can be ordered can count as ordinal numbers. Cantor also developed a theory of transfinite ordinal numbers. We will not be devoting time to this notion, but suffice it to say it is also very controversial. The basic notion is that we define a successor to the naturals, called w (omega). Thus, one could refer to the omega-th element of some order. Then we can add to omega, and get the successor, w+1, and so on; there is also w+w. The math of transfinites is similar to that of finites, although in some systems the order (adding to the left as opposed to the right of the number) matters.

The Antinomy

• Around 1895 Cantor discovered a problem with his set theory, and was working to fix the problem with minimal changes to his theory. A mathematician Zermelo also found the same problems, but did not publish them. Burali-Forti published a paper on the problems in 1987.
• Cantor allowed a kind of unrestricted set formation rule: any particular and clear concept could be used to form a set (for example, from natural numbers I make the set of all natural numbers).
• Here's is what appears to be a clear, particular concept: the set of all sets (or: the collection of all ordinal numbers, etc. -- there are several versions). Call this the Universal Set, U.
• The set of all sets seems very clear; it is just like the set of all natural numbers.
• But:
  • Consider the power set of the Universal Set, P(U). Cantor showed that the cardinality |P(S)| > |S| for any set S. But then |P(U)| > |U|.
  • U is the set of all sets, including all of the contents of P(U). So, P(U) is a subset of U since all its members must be in U (every set is in U). So, there must be a funtion on P(U) and into U that is one-to-one (the identity function does this). And so |P(U)| ≤ |U| (see above in our notes on cardinality, Useful Claim).
  • We have a contradiction! |P(U)| > |U| and |P(U)| ≤ |U|.
• The Cantorian Set Theory Antinomy did not cause much of a stir at first. However, it inspired Bertrand Russell to discover the Russell paradox, which was also very influential.
• Over the next several decades, paradoxes and contradictions will drive the reasoning about reason. Attempts to get clear about the nature of reasoning, especially logic and math, are motivated by both trying to settle such issues as whether we can reason about infinites; but they also confront challenges in a series of paradoxes.

---

Next, three schools of thought about mathematics: logicism, formalism, intuitionism.