What is the the simplest formal system falling prey to Gödel's incompleteness theorems? Is the answer different for the first and second theorems?

Is the answer Q for the first theorem and PRA for the second theorem, as I suspect? Am I wrong?

I don't really care if the systems are supposed to mimic any portion of mathematics whatsoever.

  • $\begingroup$ Have you considered Peano Arithmetic? $\endgroup$ – Mikhail Katz Apr 13 '16 at 8:32
  • $\begingroup$ @MikhailKatz I am aware Robinson Arithmetic is weaker and is still prey to GIT. $\endgroup$ – Constantine Apr 13 '16 at 8:34
  • 1
    $\begingroup$ Great. You should flesh out your question a bit more along these lines to indicate what kind of answer you might expect. $\endgroup$ – Mikhail Katz Apr 13 '16 at 8:35
  • $\begingroup$ @MikhailKatz done. $\endgroup$ – Constantine Apr 13 '16 at 8:38
  • $\begingroup$ Related: mathoverflow.net/questions/118183/… $\endgroup$ – Carl Mummert Apr 13 '16 at 10:03

There are two ways to answer the question: either take a specific statement and proof of the incompleteness theorems, and look at what system that statement and proof refers to, or else think about all the possible ways to state and prove something that might be called an "incompleteness theorem", and then look at what these need. The first way leads to more objective answers.

For the usual theorem statement and proof, the first incompleteness theorem does indeed require just Robinson's $Q$, while the second incompleteness theorem also requires that the theory can verify the three Hilbert-Bernays conditions. PA is strong enough to do that, but so are weaker theories (we could just take the necessary conditions as the axioms for our candidate theory). In principle, it is only necessary to look through the proof of the incompleteness theorems in enough detail to extract all the axioms that are required to be in the theory.

If we allow ourselves to look at alternate statements and proofs, we can get by with less, at least in some cases. For example, we can prove a version of the first incompleteness theorem that applies to every effective true theory $T$, in the language of arithmetic, as follows. Let the "modified Goedel sentence" for $T$ be the usual Goedel sentence for $T + Q$. Because $T$ is a true effective theory of arithmetic, $T + Q$ is effective and consistent (and true). Thus $T + Q$ does not prove its usual Goedel sentence, which means that $T$ alone also does not prove that sentence. So, given any effective true theory of arithmetic $T$ we can form a modified Goedel sentence which is true and unprovable in $T$. In particular this applies when $T$ is the empty theory, so in this modified form of the first incompleteness theorem we do not need any axioms in $T$ whatsoever (but, if there are axioms, we need them to be true, or at least consistent with $Q$).

Similarly, although more technically, there are proofs in the literature that Q does not prove its own consistency, which rely on completely different methods than the usual proof of the second incompleteness theorem. It is thus a matter of taste whether to say that the second incompleteness theorem applies to $Q$. Certainly the usual proof of the second incompleteness theorem does not go through for $Q$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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