I am teaching a course in proof technique to undergraduate students. One of the things they can do for their project is read an involved proof and explain it, for example Gödel's Incompleteness Theorem. Does anyone have any good proofs? They can come from any field accessible to a student with a month to work on it and with knowledge of multivariable calculus and abstract algebra.

-
Gödel's Incompleteness Theorem seems pretty ambitious. I'd guess that less onerous proofs are best for the occasion. – Michael Hardy Sep 20 '12 at 17:21
I agree that you should be less ambitious. I would start with proofs in elementary number theory and combinatorics (graph theory, enumeration, etc.). Some of them can be involved too, but the technical prerequisites are at a minimum and I think this makes it easier to concentrate on the proof itself. – Qiaochu Yuan Sep 20 '12 at 17:23
@MichaelHardy I've taught them the propositional calculus. I would have them read Newman and Nagel's "Godel's Proof" or some other less rigorous explanation. – Joe Johnson 126 Sep 20 '12 at 17:26
@QiaochuYuan My projects are in two flavors. One is what my question addresses. The other is what you are saying. I want to offer different degrees of difficulty. – Joe Johnson 126 Sep 20 '12 at 17:27
Maybe proofs from the book "Proofs from THE BOOK" would be suitable? – user12477 Sep 20 '12 at 20:25

Would a proof of the compactness theorem for propositional logic be suitable as an "involved proof", not to be required of all students, but as an item on a menu from which each student may choose one?

-
As far as I remember, the proof for that is fairly short and sweet. Since Joe asked for something that should take them about a month, I think it's possibly too simple. – Johannes Kloos Sep 20 '12 at 17:32
@JohannesKloos In the general version, they often involve some work with ultrafilters, which is fairly advanced for their given background. – Michael Greinecker Sep 20 '12 at 17:34

In the same vein as Michael Hardy's proposal, how about the completeness theorem for the Hilbert calculus in propositional logic? It is fairly involved and introduces them to Zorn's lemma as well.

-
I like this one a lot since there are multiple ways of proving this and I could have students examine the different methods. – Joe Johnson 126 Sep 20 '12 at 17:38

I like the idea of using Euclidean geometry results, since you prove surprising facts, such as Miquel's theorem (Name of a Euclidean Geometry Theorem) or, more complicated, the 9-point circle. Also students nowadays don't even know that the angle in a semi circle is a right angle, or how to prove it. This whole geometry background is a great cultural loss. I get an impression, probably wrongly, that some courses on "poofs" are about teaching students to write out clear proofs of boring facts. The need for clear proofs is more certain when the result has something of a "wow" aspect.

-