proof of gödel's incompleteness theorems

Let theory $\mathcal{T}$ defined by (N; 0, +, ×) is consistent; $\mathcal{T}$ is a system that can process addition and multiplication about natural numbers. This means $\mathcal{T}$ is theory of arithmetic.

 

$\mathcal{T}$ is consistent if $\mathcal{T}$ cannot prove formula P and ￢P simultaneously.

 

we'll use symbol  ￢, ∧, →, ↔, (, ), ∀, ∃, $P_0, f_0, x_0, P_1, f_2, f_2$ …. Symbol having subscript each means predicate, fucntion, variable symbols.

 

Define

$\alpha(\sigma) = n$ where constant symbols(￢, ∧, →, ↔, (, ), ∀, ∃) are endowed n<11, predicate symbols are prime numbers over 10, function symbols are second power of prime number over 10, and variable symbols are third power of prime number over 10.

 

$\beta(\sigma_1\sigma_2\sigma_3\sigma_4…\sigma_m) = 2^{\alpha(\sigma_1)}3^{\alpha(\sigma_2)}…{P_m}^{\alpha(\sigma_m)}$ where $P_m$ means m'th prime number.

$\gamma(x_1, x_2, …, x_n)=2^{\beta(x_1)}3^{\beta(x_2)}…{P_n}^{\beta(x_n)}$ where $x$ is a formula made of finite symbols.

 

By $\beta$, we can construct a single formula by string of symbols, and by $\gamma$, we can construct any proof by enumerating formulas.

 

one can easily check each function is one-to-one; for any given number, one can find a series of formulas, symbols, and vice versa.

 

now we define a function g : {symbols∪strings∪proofs} → $\mathbb{N}$ where g is defined by $\alpha, \beta, \gamma$.

 

g is the function which converts symbols to numbers. we'll call the number n = g(x) the godel number.

 

 

then for any natural number n, we can convert it to the combination of symbols and for given symbols, we can get a number corresponding to them. one can check this function g is one-to-one.

 

now define $P_r(m,n)$ = m is the godel number of a proof of a formula whose godel number is n.

 

knowing m, we can construct the proof of the formula whose godel number is n.

 

 

define $P(g(X)) = ∃x(P_r(x,n) ∧ (x=m))$ where $g(X)=n$. defined predicate says there exists proof whose godel number is m and that is proof of a formula whose godel number is n. we'll call $P(g(X))$ X is provable.

 

now let's write $\vdash x$ means $\mathcal{T}$ proves $x$(or x is a theorem of theory $\mathcal{T}$).

 

 

For the predicate P, you can check below properties.

 

1. If $\vdash X$, then $\vdash P(g(X))$

2. $\vdash P(g(X \rightarrow Y)) \rightarrow (P(g(X)) \rightarrow P(g(Y)))$

3. $\vdash P(g(X)) \rightarrow P(g(P(g(X))))$

4. $\not\vdash P(g(0=1))$  ($0=1$ means $0 \neq 0$)

 

especially for the (4), $P(g(0=1))$ means inconsistency of mathematical systems. since we assumed given theory $\mathcal{T}$ is consistent, $\not\vdash P(g(0=1))$  (it means $0 \neq 0$) holds.

 

Look up all the formulas in $\mathcal{T}$ having one-free variable say n.

 

: $B_1(n), B_2(n), B_3(n), \cdots$

 

 

Consider $\neg P(g(B_n(n)))$ where n is free variable.

 

Let $B_k(n) = \neg P(g(B_n(n)))$ for some $k \in \mathbb{N}$.

 

In particular for n=k(This particular case is secured by Godel's Diagonalization Lemma which is beyond this article's coverage), $\vdash B_k(k) \leftrightarrow \neg P(g(B_k(k)))$.

 

let $A = B_k(k)$.

 

thus below property holds.

 

5. $\vdash A \leftrightarrow \neg P(g(A))$

 

using (5), we can get below.

 

$\vdash P(g(A)) \rightarrow \neg A$ (using contraposition to the (5))

$\vdash P(g(P(g(A)) \rightarrow \neg A)) \rightarrow (P(g(P(g(A)) \rightarrow P(g(\neg A)))$ (using (2))

 

If $\vdash P(g(A)) \rightarrow \neg A$, then $\vdash P(g(P(g(A)) \rightarrow \neg A))$ (using (1))

 

$\vdash P(g(P(g(A))) \rightarrow P(g(\neg A))$ (using Modus Ponens)

 

If $\vdash P(g(A))$, then $\vdash P(g(P(g(A))))$ (using (3))

$\vdash P(g(A)) \rightarrow \vdash P(g(P(g(A))))$ (using right above)

 

using above results, 6 holds.

 

 

6. $\vdash P(g(A)) \rightarrow P(g(\neg A))$

 

 

(6) implies $\vdash A \rightarrow (\neg A \rightarrow (0=1))$.

 

also by (1), $\vdash P(g(A \rightarrow (\neg A \rightarrow (0=1))))$.

 

by (2) and using Modus Ponens, $\vdash P(g(A)) \rightarrow P(g(\neg A \rightarrow (0=1))$.

 

using (2) and MP again, $\vdash P(g(A)) \rightarrow (P(g(\neg A)) \rightarrow P(g(0=1))$

 

using (6) and right above, we derive (7).

 

 

7. $\vdash P(g(A)) \rightarrow P(g(0=1)))$

 

 

now let $\vdash A$. then by (1), $\vdash P(g(A))$.

 

and by (7), $\vdash P(g(0=1))$. this contradicts (4). thus $\not\vdash A$

 

 

8. $\not\vdash A$

 

 

conversely, let $\vdash \neg A$. then by (5), $\vdash P(g(A))$. using (7), we get $\vdash P(g(0=1))$ which contradicts (4). thus $\not\vdash \neg A$.

 

 

9. $\not\vdash \neg A$

 

 

let $\vdash \neg P(g(0=1))$. then by using contraposition to (7) and MP, we get $\vdash \neg P(g(A))$.

 

then by (5), $\vdash A$ which contradicts (8). thus $\not\vdash \neg P(g(0=1))$

 

 

10. $\not\vdash \neg P(g(0=1))$

 

 

above properties of theory $\mathcal{T}$ proves godel's incompleteness theorems.

 

using (8), (9), we get lemma for first godel's incompleteness theorem.

 

Lemma: There exists a sentence in consistent theory of natural numbers $\mathcal{T}$ which is not provable, whose negation is also not provable.

 

Since $A$ and $\neg A$ mentioned in (8), (9) are sentences, either $A$ or $\neg A$ is true in standard model(=$\mathbb{N}$) of Peano Arithmetic, but both cannot be provable in PA. thus first incompleteness theorem holds.

 

First Godel's Incompleteness Theorem : There exists a true sentence in $\mathcal{T}$ which is not provable, provided that $\mathcal{T}$ is consistent.

 

 

during the proof, we said $P(g(0=1))$ means inconsistency. now we can say that negation of that, $\neg P(g(0=1))$, means consistency of theory $\mathcal{T}$. and by (10), we got $\not\vdash \neg P(g(0=1))$ which means theory $\mathcal{T}$ cannot prove its own consistency. thus now we get to the second incompleteness theorem.

 

Godel's Second Incompleteness Theorem : If $\mathcal{T}$ is consistent, then it is not the case that $\not\vdash \neg P(g(0=1))$. that is, If $\mathcal{T}$ is consistent, then its consistency cannot be proved by the mechanism of $\mathcal{T}$.

 

 

 

*위 증명은 IIT Ardindama Singh 교수의 강의에서 뽑아왔습니다. 불완전성을 증명하는 방식에는 크게 self-reference, diagonalization, computability theory 세 가지가 있습니다. 위의 방식은 두 번째 방식을 간략하게 서술한 것입니다. 기회가 된다면 좀더 엄밀한 방식으로 나머지 세 방식을 소개하도록 하겠습니다.

*참이라는 말과 증명가능하다는 말은 서로 다른 층위의 말입니다. 논리학 체계에서는 참/거짓은 특정한 모형 하에서 전개되는 개념입니다. 임의의 수학적 모형에서, 그 모형 하에서 다룰 수 있는 각각의 모든 문장은 참이거나 거짓입니다. 모형은 변항기호, 개체상항기호, 함수기호, 술어기호에 의미를 부여해서 모든 문장이 항상 참이거나 거짓일 수 있도록 합니다. 그런데 증명가능하다는 말은, '특정한 공리들에 추론규칙들을 적용해서 얻어낼 수 있다'는 말입니다. 말의 층위가 서로 다릅니다. 괴델정리에서 보여주는 바는 페아노 공리계를 포함하는 수학이론에서는 증명도 그 명제의 부정도 증명불가능한 경우가 항상 존재한다는 것입니다. 그러나 페아노 공리계를 만족하는 가장 단순한 모형인, 표준적인 자연수 모형(집합의 원소가 0 1 2 3 4 ... 밖에 없고 이런 모든 자연수보다 더 크거나 작은 수가 없는 체계)에서는 참이거나 거짓이겠죠. 물론 페아노 공리계보다 단순한 체계, 혹은 다른 구조를 가진 체계는 완전한 경우도 꽤 많습니다.