Email, Oct 9, 2012

For the homework assignment (due next Thursday, in class) I ask you to write out the principal mathematical steps in the development from Cantor to Gödel. There are no aps -- the idea is simply to make sure that everybody understands the basic conceptual skeleton so that flesh can be added later. If there is something you don't understand, please ask in class, or indicate it on the homework. You should feel free to consult with others as you work your way through this fascinating (and at times deeply perplexing) set of ideas.

Specifically, please write out the following; each point can be answered in no more than a paragraph or two:

  1. A proof that the rationals can be enumerated, and an indication of why this is surprising.

  2. A proof that the reals cannot be enumerated; for extra credit, you can try to reconstruct Cantor's original argument. (This should be pretty easy, with the hints provided.)

  3. A proof that the cardinality of the plane (or, equivalently, the unit square) is the same as the cardinality of the real line. Note the "Dedekind objection" for extra credit, try to repair the problem in Cantor's proof. (This is hard, but you will learn something from struggling.)

  4. In your own words, describe why the combination of these three results was so deeply puzzling to Cantor.

  5. For fun (extra credit): try to prove that the cardinality of [0,1) is the same as the cardinality of (0,1). (Cantor found this difficult.)

  6. Prove (using binary decimals) that each positive real number corresponds to a set of positive integers, and vice versa. (You can ignore the "Dedekind objection" about the uniqueness of the decimal representation.)

  7. Prove Cantor's Theorem. (This is key -- I suggest that you do not look at the hint in the final slide until you have spent 20 minutes thinking about it. If you recall Russell's Paradox and the Gödel argument, you should be able to figure this out, and to see how the idea of paradoxical self-reference runs throughout the mathematical developments.)

  8. In your own words: What counterintuitive implications does Cantor's Theorem entail, and why should a mathematician be legitimately worried about it? Describe Russell's Paradox. Having answered #7, can you now see how Russell derived it from the proof of Cantor's Theorem?

  9. In your own words -- How did Hilbert propose to deal with these problems?

  10. In your own words -- What is the central trick Gödel uses to counter Hilbert's program? How is his trick related to the paradox of the liar (i.e. of the person who says, "This sentence is false"); and how is that trick related to the Russell Paradox?
I don't expect technical proofs of the last three points, and don't expect that this assignment will take much more than an hour or so to complete: we have already seen most of the answers in class. The idea is rather to make sure that you understand how the various pieces fit together.

For Thursday we will discuss the case of Scott v. Harris (which you have already read), and also the article by Orrin Kerr, 'Why Courts Should Not Quantify Probable Cause'

For next week we will read Tribe: Trial by Mathematics 1971 and Langbein: Torture and Plea Bargaining 1978.pdf.