Talking about Gödel's incompleteness theorems...

Question

I will give a talk about Gödel's incompleteness theorems to a group of people consisting of undergraduates of mathematics, graduates of informatics and etc (they are not really familiar with the subject in question). I am an undergraduate student of mathematics myself.

Because of this occasion I read Gödel's Proof and briefly looked at Gödel's Incompleteness. I don't have time to read more books.

As of now I am planning to give a few very simple examples, formulate an elementary logic system which is both consistent and complete, show Gödelian puzzle, formulate a more complex axiomatic system to exploit Richard's paradox which would lead to ideas about Gödel numbering and finally theorems themselves.

If you were me, what else would you mention?

Answer 1

Warning: The following is a "soft" answer. It may not actually be helpful.

I'd mention less, actually. This is a mistake I've made -- trying to fit in as many ideas and examples into a talk as possible. That's often a bad idea, especially when giving a talk to undergraduates. Pick a few ideas you want to develop, even if you won't be able to get to the incompleteness theorems themselves. It will suffice to develop the historical background of the subject, talk about consistency and completeness in logical systems, or go right for the gusto and talk about Godel's incompleteness theorems, but without lingering too much on the technicalities of the proof. That way the audience walks out having learned something concrete rather than getting a whirlwind tour through a subject you spent weeks learning about.

I recommend you make your talk interactive and engage the audience. If you want to introduce Richard's paradox, for example, ask people to propose their own explanations before delving into the distinction between mathematics and meta-mathematics. I think it is mistake (not necessarily your mistake) to think that the speaker needs to always be talking when giving a "talk". This is especially the case for "philosophical" subjects like the incompleteness theorems.

Answer 2

You just don't have the time to explain all that. Don't go setting up theories and proving stuff about them, just start with something they know. Don't go into precise Gödel numbering, set up some easy to reverse function (say interpret the LaTeX for the formula as an integer). Make it easy to grasp how one result follows from the previous one. Concentrate on the why, not the details that make the argument ironclad. Give easy to find references for those whose brain cells didn't try to escape through their ears.

When teaching the closely related halting problem, instead of Turing machines and such I've used the "Hello, world!" detector idea from Hopcroft et al's "Introduction to automata theory, languages, and computation" (2nd edition). And it is hardest for people to wrap their head around the diagonal argument used.