3

괴델의 불완전성 정리✔

“참이지만 기계적인 논리체계로는 증명 불가능한 것이 존재한다. 자연수에 대한 명제들의 세계로 국한되더라도 그런 것이 존재한다.”

(X is not provable)=X (1)

만약 모든 명제가 증명 가능하다면

X가 참인 경우, 등식 (1)의 좌변도 참이라는 이야기이므로,X는 증명 불가능하다.

X가 거짓이라면 그 반대가 참이므로, 등식 (1)에 따라 X는 증명 가능하다.

명제✔

‘x는 증명 불가능하다’= np(x)

명제A_ = 그 명제의 괴델수(Godel number)

거꾸로 괴델수 Z에 윗줄을 그은 _Z = 그 괴델수에 해당하는 명제

A[‘x'->C] = 명제 A에 있는 변수 x를 C로 바꾼 명제

[‘x'->C]에서 ‘x'는 상수기호로서 심벌 x를 뜻한다. 다른 것으로 바꿀 수 있는 변수가 아니다.

기호 :=는 그렇게 정의한다는 뜻이다. 양변이 같다는 판단이 아니다.

다루는 논리체계는 자연수에 대한 세계이다. 자연수에 대한 논리 안에서 증명 불가능한 명제가 있음을 보여야 한다.

그런데 ‘x는 증명 불가능하다’는 명제는, 명제 x에 대한 명제이지 자연수에 대한 명제가 아니다. 그러나 자연수에 대한 명제로 만들 수 있다. 괴델은 명제들을 고유의 자연수로 표현하는 방법을 정의한다. 명제에 해당하는 자연수가 있고, 거꾸로 그런 자연수에서 해당 명제를 정확히 복구할 수 있는 이 형식을 괴델 숫자붙이기(Godel numbering)라고 부른다.

명제는 기호들이 한 줄로 서 있는 문장이다. 명제를 표현하는 데 사용할 수 있는 기호들이 예를 들어 24개라고 할 때, 기호마다 1부터 24까지 고유번호를 붙인다. 한 명제가 (7,15,1,19)라고 하자.

이 명제는 소수를 차례대로 이용해서 2의 7승×3의 15승×5의 1승×7의 19승으로 표현할 수 있고, 그 결과 하나의 자연수가 나온다. 이 자연수를 소인수분해하면 원래의 명제를 찾아낼 수 있다.

이 방식을 통해서, 명제에 대한 명제는 모두 자연수에 대한 명제가 된다. 그래서 ‘x는 증명 불가능하다’는 명제도 명제 x에 해당하는 괴델수 x 를 사용해서 자연수에 대한 명제 ‘x는 증명 불가능하다’로 만들 수 있다.

                                    "증명에 해당하는 괴델수들은 X_로 나누어지지 않는다"

그러면 다음을 만족시키는 자연수계의 명제 X가 존재한다. X = np(X)

그러한 X는 다음과 같다.

X := G['x'-> k]

G := np(_X['x'->x])

k := G

그 이유는 이와 같다.

X = G['x'-> k]

=(np(_x['x'->x]))['x'->k]

=np(_k['x'-> k])

=np(G['x'-> k]

=np(X)

이렇게 괴델의 증명이 끝나게 됩니다.