괴델의 불완전성 정리에 대한 개략적인 아이디어

Standford university에서 출간한 godel's incompleteness theorems 앞부분에 나오는 설명이다.

 

뒤쪽은 학기 중이라 바빠서 나중에 읽기로 했고, 앞부분에 쉬운 설명만 간략하게 적어본다.

 

일관적인 체제 L(Language)을 가정하고, 이 체계가 무모순이라고 가정하자.

 

그렇다면 L은 참인 문장밖에 산출할 수 없다(다시 말해 provable한 것들만 산출할 수 있다).

 

그렇지 않다면 L은 무모순이면서 일관적이라는 대전제에 위반되기 때문이다.

 

L에서 사용할 수 있는 문자들은 ~ ( ) P N X 라고 가정하자.

(P = provable, N = norm)

 

P(X) = X is provable

N(X) = the norm of X = X(X)

PN(X) = the norm of X is provable

등을 만들어 낼 수 있다.

 

L에서 임의의 statement X에 대해서, P(X)는 항상 L에 무모순하다. 즉, L 내에서 P(X)는 증명가능하고 따라서 산출가능하다는 의미다.

 

그렇다면 참이지만 L에서 증명불가능한 명제를 이끌어 낼 수 있을까?

 

 

~PN(~PN)을 생각해보자.

 

문자적으로 the norm of ~PN is not provable와 동치이다.

 

the norm of ~PN는 N의 정의에 의해서 ~PN(~PN)이다.

 

따라서 the norm of ~PN is not provable = ~PN(~PN) is not provable이다.

 

 

~PN(~PN)을 구하려고하니, ~PN(~PN) is not provable 다시 말해서 본명제가 증명가능하지 않다는 결론에 이르렀다. 이는 어떤 의미인가.

 

이는 ~PN(~PN) is true if and only if ~PN(~PN) is not provable과 동치이다.

( if ~PN(~PN) then ~PN(~PN) is not provable + if ~PN(~PN) is not provable then ~PN(~PN) )

 

두 가지 결론이 있다.

 

1. ~PN(~PN) is wrong and provable in L

 

2. ~PN(~PN) is true but cannot be provable in L

 

 

1은 확실히 틀렸다고 할 수 있다. 대전제인 L is consistent에 대해서 모순이 생기기 때문이다.

 

L이 일관적이라는 말은 L에서 산출할 수 있는 값은 모두 True라는 의미이다.

 

따라서 1을 선택한다면, L이 무모순(일관적)이라는 것에 모순이고 따라서 1은 선택할 수 없다. L에서 wrong한 명제를 산출할 수 있다는 의미기 때문이다(자기모순).

 

결론적으로 선택할 수 있는 명제는 2번이다.

 

~PN(~PN)은 참이지만 L에서는 증명불가능한 것이다.

 

 

같은 방식으로 PN(~PN)의 값은 false이고 ~PN(~PN)이 L에서 not provable이기 때문에 PN(~PN)도 false값을 가지지만, L에서는 증명가능하지 않다.

 

 

이는 any consistent L에 대해서 성립하는 명제이다. 따라서 어느 일관적인 체계는 반드시 참이지만 증명불가능한 명제가 존재한다.

 

 

 

이런 논증이다. 책에서는 rough proof라고 서술하고 있다. 정확한 기호와 논증은 복잡하니 기약없는 나중으로 미뤄두고 일단 개략적인 증명법은 여기까지로.