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:
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
- A proof that the rationals can be enumerated, and an indication
of why this is surprising.
- 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.)
- 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.)
- In your own words, describe why the combination of these three
results was so deeply puzzling to Cantor.
- 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
- 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
- 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
- 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?
- In your own words -- How did Hilbert propose to deal with
- 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?
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
and Langbein: Torture and Plea