For a Formal axiomatic system to obey Godel's incompleteness theorems, It has to be powerful enough to incorporate Peano Axioms.

Why It does not apply to say, Presburger arithmetic or the axioms of Euclid in Tarski's formulation?

I understand that the two latter axiomatic systems are not capable of arithmetic and hence not subject to the incompleteness theorems, But my question is why being capable of doing arithmetic render a system incomplete in the first place?

  • 3
    $\begingroup$ Pace the author's of a zillion popular accounts of Goedel's work, how can you expect an answer in "laymen's terms" to a technical question in mathematical logic? $\endgroup$
    – Rob Arthan
    Commented May 31, 2015 at 22:20
  • $\begingroup$ As I have understood the incompleteness theorem, it's basically constructs a sentence that is not provable, but the construction requires a strong enough axiomatic system in order to make sense. "Strong enough" happens to mean "capable of doing arithmetic". $\endgroup$
    – Arthur
    Commented May 31, 2015 at 23:36
  • 1
    $\begingroup$ Goedel's theorem applies to formal systems in which every primitive recursive function is strongly representable. That's why it doesn't apply to Presburger arithmetic or Tarski geometry. If you want to understand why Goedel had to use this property of a formal system then you should read his 1931 paper. A good English translation is available on-line for free. $\endgroup$
    – Rupert
    Commented Jun 1, 2015 at 14:14

1 Answer 1


Gödel's theorem says that, for any consistent theory $T$ strong enough to express some elementary arithmetic, there will be a true but non-provable statement "this sentence is not provable" in it. Basically, the idea is that if $T$ proves it we get a contradiction, but $T$ is consistent, so it does not prove it and consequently the statement is true.

Gödel found that the statement "this sentence is not provable" can be expressed arithmetically through a encoding technique now know as a Gödel numbering. Here is a simple example. Take the alphabet $PROP_{pq}=\{p,q,\neg,\rightarrow,(,)\}$ and call it a word any concatenation of those signs. For example, '$(\neg q)$', '$(p\rightarrow q)$' or even '$q))\rightarrow$'. A word is then a sequence $x_1,...,x_n$ where every $x_n$ is either '$p$','$q$','$\neg$','$\rightarrow$','$($' or '$)$'. We can then enumerate the words of $PROP_{pq}$ as

$$2^{g_1}\cdot 3^{g_2} \cdot ... \cdot p_n^{g_n}$$ where $p_i$ is the $i$'th prime number and $g_j$ defined as

$$g=\cases{1, when &$j=p$\cr 2, when&$j=q$\cr 3, when&$j=\neg$\cr 4, when&$j=\rightarrow$\cr 5, when&$j=($\cr 6, when&$j=)$\cr}$$

Then, in the first example above, $(\neg q)=2^5 \cdot 3^3 \cdot 5^2 \cdot 7^6=2541218400$. (In fact, you can see that this encoding are unique by the fundamental theorem of arithmetic.)

This is supposed to explain why a theory must be capable of expressing natural numbers in order to Gödel's theorem apply to it. But why it isn't sufficient? If it were, other theories like Presburger arithmetic, would be incomplete as well. The second point thus is that a theory $T$ must be strong enough to represent recursive functions, which, very briefly, allows $T$ to represent its own provability and express the self-reference required in "this sentence is not provable (in T)".

  • $\begingroup$ For a formal system to obey Godel's theorems it has to satisfy two conditions: 1)It has to include recursive functions so as to allow a construction of a true but non-provable self-referential statement like "this statement is not provable" within our formal system. 2)it has to be able to do arithmetic. This condition however, is not clear to me why it's a necessary one. I mean why can't we construct the above self-referential statement within a formal system that admits only recursive functions but does not include arithmetic? can you edit your answer and address that? $\endgroup$
    – Omar Nagib
    Commented Jun 2, 2015 at 15:15
  • 1
    $\begingroup$ @OmarNagib For the theorem to work you need to express the statement "$T$ is consistent". How can you do this if not encoding it arithmetically? $\endgroup$ Commented Jun 8, 2015 at 5:22
  • $\begingroup$ I'm quite ignorant on this subject, so I do not know. Can you explain in some detail, why it is not possible to express self-referential statements in systems which do not admit arithmetic, nevertheless, they have recursive functions? $\endgroup$
    – Omar Nagib
    Commented Jun 8, 2015 at 19:42
  • $\begingroup$ @OmarNagib Because in order to express something like "$Con(T)$", you need to incorporate the notion of provability in the very object language, that is, something like "there is no sequence of formulas of $T$ that proves $\bot$". But for a detailed explanation, I would recommend you to refer to, for example, Peter Smith's An Introduction to Gödel's theorems Ch. 24 or Franzén's Gödel's Theorem: An Incomplete Guide to Its Use and Abuse Sec 2.6. $\endgroup$ Commented Jun 9, 2015 at 5:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .