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.
Proofs for Undergraduates
-
8Gödel's Incompleteness Theorem seems pretty ambitious. I'd guess that less onerous proofs are best for the occasion. – 2012-09-20
-
1I 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. – 2012-09-20
-
0@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. – 2012-09-20
-
0@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. – 2012-09-20
-
0@JoeJohnson126 There are some problems with this book, as explained in the [AMS Notices Review](http://www.ams.org/notices/200403/rev-mccarthy.pdf). – 2012-09-20
-
2Maybe proofs from the book "[Proofs from THE BOOK](http://www.amazon.com/Proofs-BOOK-Martin-Aigner/dp/3642008550)" would be suitable? – 2012-09-20
3 Answers
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?
-
0As 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. – 2012-09-20
-
1@JohannesKloos In the general version, they often involve some work with ultrafilters, which is fairly advanced for their given background. – 2012-09-20
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.
-
0I like this one a lot since there are multiple ways of proving this and I could have students examine the different methods. – 2012-09-20
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.