Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
Do you consider the fact that "PA (indeed Robinson Q is enough) is $\Sigma_1$-complete" strong enough? –  boumol Mar 28 '14 at 8:56
@boumol Thanks, that sounds very promising. Could give me a link to an explanation of $\Sigma_1$ completeness? –  Tim kinsella Mar 28 '14 at 9:16
This essentially means that all $\Sigma_1$-setences that are true in the standard model are provable in PA. This result can be find in most of logic books dealing with PA (and Robinson's Q). In particular, you can take a look at the notes by Peter Smith logicmatters.net/igt/godel-without-tears (in the current version is Theorem 17 in Episode 5, page 40) –  boumol Mar 28 '14 at 9:27

2 Answers 2

I want the incompleteness theorems to sound impressive and they dont sound impressive unless you think PA is a powerful theory.

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.

share|improve this answer
That's an excellent point. Thank you. –  Tim kinsella Mar 28 '14 at 9:19
Note that one needs to apply "Rosser's trick" to get the theorem mentioned in this answer. $\hspace{1.04 in}$ –  Ricky Demer Mar 28 '14 at 13:02

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$".

share|improve this answer
Thanks, this looks awesome. Actually, though, I was looking for some result or argument that conveys how much of true arithmetic is proved by PA. Basically I want the incompleteness theorems to sound impressive and they dont sound impressive unless you think PA is a powerful theory, able to prove lots of stuff. This might be a very naive request. like I mentioned I'm not a logician. But I was hoping there might be some analogue of the fact that "all computable sets are definable in the language of arithmetic" which somehow gives Tarski's theorem some content. –  Tim kinsella Mar 28 '14 at 8:44
@Timkinsella - limitations due to Godel's result are well explained by Peter Smith, but about "how powerful" is $\mathsf {PA}$, I think that may be enough to stress that all known results of 2,000 and more years of arithmetics has been successfully proved from Peano's axioms, "until 1977 that someone discovered a natural sounding arithmetic statement independent of $\mathsf {PA}$". –  Mauro ALLEGRANZA Mar 28 '14 at 12:28
@Martin : $\:$ If I remember right, PA should also prove all instances of "Every strategy at the $\hspace{.92 in}$ $k$-th level of the arithmetical hierarchy will kill this hydra.". $\;\;\;\;$ –  Ricky Demer Mar 28 '14 at 18:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.