Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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)".
