I plan to give a talk to a group of math PhD students (with no exposure to mathematical logic. I should also mention that I'm certainly no logician, myself) about the incompleteness theorems. I plan to first prove Tarski's theorem on the arithmetic undefinability of arithmetic truth. In this case its somewhat easy to impress upon the audience the expressive power of the language of arithmetic. I plan to say something like "The language of arithmetic can express computable relations and, by alternating quantifiers, a whole hierarchy of uncomputable relations." However when I come to provability and Gödel's theorems its a little harder to convey, in a few words, how robust is Peano arithmetic as a theory. At the moment all I can think to say is that it was not until 1977 that someone discovered a natural sounding arithmetic statement independent of PA. Do you have any ideas? Thanks!
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
This is perhaps misleading. Remember: the first incompleteness theorem is better called (and often is called) Gödel's incompleteability theorem. It isn't just that PA is incomplete, but so is any effectively axiomatized consistent extension of PA (indeed, of Robinson Arithmetic).
To say a bit more: The point of the theorem isn't just that this or that theory which you might have expected to be negation complete isn't complete. Rather, so long as the theory $T$ is consistent, effectively axiomatized (you can effectively decide what's an axiom, what arrays are well-constructed proofs according to the rules of the game), and contains enough arithmetic, it will be incomplete. So you can't patch up an incomplete theory $T$ to make it complete by throwing more axioms into the mix -- unless $T$ stops being consistent, or stops being effectively axiomatized. In this sense, a suitable $T$ is not just incomplete but incompleteable. That is the crucial thing to get across to your audience, and is that which gives Gödel's result its oomph.
To make that result seem impressive, your audience don't have to think that it is surprising that PA in particular is incomplete (they don't have to have a view of PA's strength) -- what they need to find surprising is that e.g. the truths expressible using first-order logic, addition and multiplication (the truths of school-room arithmetic, you might say) can't be completely axiomatized.
Are you searching for a colorful example? Do you know the Hydra Game? PA can prove all the instances of "You can kill this hydra", but can't prove "$\forall$ hydra $H$ you can kill $H$".