괴델의 불완전성 정리

1. 괴델의 불완전성 정리 개요

괴델은 괴델수라는 개념을 도입하여 힐베르트의 수리문제 자동 판별문제에 대한 해답을 제시. 결과적으로 수리문제 자동판별문제는 풀 수 없다는 것이 괴델의 불완전성 정리의 핵심이다. 괴델은 2가지 정리을 증명해냈는데 "참이지만 증명할 수 없는 명제가 존재한다." 라는 정리과 "공리계가 무모순임을 해당 공리예 내에서 증명 불가능하다"라는 정리이다. 

 

---

 

괴델의 불완전성 정리

"기계적인 방식으로는 참/거짓을 밝힐 수 없는 명제가 반드시 존재한다."

 

(1) "참이지만 증명할 수 없는 명제가 존재한다"

(2)  "공리계가 무모순임을 해당 공리계 내에서 증명 불가능하다"

 

---

 

2. 메타수학 명제와 괴델 수

일반적인 수학명제는 아래와 같이 명제의 요소로 수, 집합, 벡터와 같은 것들을 다룬다. 그러나 괴델은 이 명제를 해결하기 위해 메타수학이라는 당시로서는 최근에 도입된 명제 개념을 사용하였다. 메타수학은 수학적 명제를 명제의 요소로 하는데, 예시는 아래와 같다.

 

---

수학명제

p : 1 + 1 = 2이다.

q : 2 x 3 = 5이다.

 

메타수학명제

u : p는 수학적 명제가 아니다

v : q는 증명가능한 명제이다

 

---

 

이러한 메타수학 명제의 경우 수학적인 증명방법인 귀류법과 연역법을 사용하여 풀면 역설이 발생하게 된다. 때문에 명제의 기본요소로 수학적 명제를 다루는 메타명제 문제인 수리문제 자동판별문제를 수학적인 증명방법으로 해결하기 위해 괴델은 괴델 수 라는 것을 도입한다. 괴델 수는 소수를 이용하여 메타수학의 명제(산술식)를 1:1로 자연수에 맵핑하는데, 괴델은 이 괴델 수를 이용해 메타명제를 수학적 명제의 범위 내로 끌어들여온다.

 

산술식 '1+0=1'를 예로 들어보자. 이 식에 등장하는 기호의 유형은 '1', '+', '0', '='로 네 가지다. 이때 각 기호의 유형마다 고유한 자연수를 부여하자. 그 예는 다음과 같다.

 

기호 유형	괴델수
'0'	3
'1'	4
'+'	5
'='	6

이때 식 '1+0=1'은 5개의 기호로 이루어져 있으므로, 그 길이가 5라고 할 수 있다. 그 길이에 해당하는 최초의 소수들, 즉 가장 작은 소수 5개는 2, 3, 5, 7, 11이다. 이 소수들은 각 기호의 위치를 나타낸다. 이에 의거하여 각 위치마다 놓인 기호는 다음과 같이 지수를 사용해 표현가능하다.

 

$Position Prime Number ^ {Godel Number}$

 

예컨대 '1+0=1'의 첫 자리에 나타나는 '1'은 $2^4 = 16$으로 번역가능하다. 그리고 이렇게 번역된 각 자연수들을 다 곱함으로써 식 전체를 그 괴델수로 번역할 수 있다. 이를테면 '1+0=1'의 괴델수는 $2^4$ × $3^5$ × $5^3$ × $7^6$ × $11^4$ = 837134518374000이 된다.

 

3. 제 1 불완전성 정리

---

"참이지만 증명할 수 없는 명제가 존재한다"

 

---

 

제 1 불전성 정리를 증명하기 앞서 2가지 함수를 정의한다. 먼저 함수 dem(n,m)은 괴델수 n과 m을 입력으로 하여 "n은 m의 증명이다"라는 명제를 반환하는 함수이다. 이 함수는 만약 n이 존재한다면, m은 증명가능하다 라는 명제와 동치이다. (n이 m의 증명이기 때문에, m의 증명이 존재하면 m은 증명 가능한 명제가 된다) 다음 함수 sub(n,m,x)는 n에서 m을 x로 교체하면 얻어지는 괴델수를 반환하는 함수이다. 괴델수는 명제 뿐만 아니라 산술식 자체, 산술식의 일부도 괴델수로 표현될 수 있기 때문에 m을 x로 교체할 수 있다.

 

def dem(n:godel , m:godel) -> proposition :
    """
    This function is equavalent to proposition Z : 
    Z = if N existed, M is provable proposition
    
    :param n: godel number of proposition N
    :param m: godel number of proposition M
    :return: proposition
    """
    return proposition("n is proof of m")

    
def sub(n:godel, m:godel, x:variable) -> godel:
    """
    Function to replace M with x in proposition N
    
    :param n: godel number of proposition N, N includes M
    :param m: godel number of proposition M
    :param x: variable to replace M in N
    """
    return godel(n.replace(m, x))
    

 

그 다음 명제 p, q을 정의한다.

 

---

$p \equiv \sim(\exists x) dem(x, sub(y, a, y))$

 

$a$는 y의 괴델수 이고, $sub(y,a,y)$는 그대로 $y$이다.

명제$p$는 "위 $x$는 존재하지 않는다."를 의미한다.

즉, "$sub(y,a,y)$의 증명은 존재하지 않는다."를 의미한다.

 

$k \equiv godel(p)$

$k$는 명제 p의 괴델 수를 의미한다.

 

---

 

여기에서 명제 $p$의 모든 $y$를 $k$로 바꾼 명제 $q$를 정의한다. 즉, 명제 $p$가 가지고 있는 모든 $y$의 syntex를 $k$로 바꾼 명제이다.

 

$q \equiv \sim(\exists x) dem(x, sub(k, a, k))$

 

명제 $q$는 $p$(==$k$)에서 $y$(==$a$)를 $k$로 변경한 명제이다. 다시 생각해보면, $q$ 자체가 $sub(k, a, k)$와 동일하기 때문에, 명제 $q$는 "자기자신의 증명이 존재하지 않는다"라는 명제가 된다. 이 명제를 보고 러셀의 역설(거짓말쟁이의 역설)을 떠올릴 수 있지만, 이 명제는 러셀의 역설에 빠지지 않는다. 러셀의 역설은 "이 문장은 거짓이다"처럼 자기 부정적인 구조를 가지는데, 만약 이 문장이 참이라면, 문장 속의 "이 문장"이 거짓이 되기 때문에 모순이 발생하고, 이 문장이 거짓이라면, 문장 속의 "이 문장"은 참이 되기 때문에 모순이 발생한다.

 

그러나 명제 $q$에는 그 어디에도 자기자신을 가리키는 $q$라는 syntex가 없다. 재귀적인 구조를 띄지 않고, 때문에 이 명제 $q$는 거짓말 쟁이 역설에 빠지지 않는다. 사실, $q$를 가리키는 $sub(k,a,k)$는 의미적으로는 $q$와 동일하지만 함수의 반환값은 괴델수로 이루어진 자연수이기 때문에 $sub(k,a,k)$가 명제 $q$ 그 자체는 아니다.

 

만약 $q$가 참이라고 한다면, 

$q \equiv \sim (\exists) dem(x, sub(k,a,k))$는 참이다.

 

이 말은, $sub(k,a,k)$의 증명 $x$가 존재하지 않는다는 것이고, 함수 $sub(k,a,k)$의 반환값은 명제 $q$의 괴델 수 이기 때문에 명제$q$는 "$q$의 증명이 존재하지 않는다." 라고 해석 된다. 즉, 명제 $q$가 참인 경우, 명제 $q$의 증명은 존재하지 않고, 결과적으로 "참이지만 증명 불가능한 명제가 존재한다."

 

3. 제 2 불완전성 정리

---

"페아노 공리계를 포함하는 공리계가 무모순임을 해당 공리계 내에서 증명 불가능하다"

$S \equiv$ "페아노 공리계가 무모순임을 페아노 공리계 내에선 증명 가능하다"

 

---

제 2정리를 부정하는 명제 S를 정의한다. 만약 정의 S가 거짓이라면 제 2 정리는 참이다. 위에서 등장했던, 명제 $p, q$ 역시 수학적 명제이므로 페아노 공리계에 포함된다. 명제 $q$도 페아노 공리계에 있으므로 만약 명제 $S$가 참이라면 명제 "$r \equiv q$가 무모순임을 증명 가능하다" 역시 반드시 참이여야한다.

 

(1) 명제 $r$이 참일 때, $q$가 참인 경우

$\sim (\exists x) dem(x, sub(k,a,k)$가 참이다.

 

제 1 정리가 참이므로 $q$가 참인 경우, $q$는 증명 불가능하다. 그러나 $r$이 참이려면 $q$의 참 거짓을 밝혀내야만 하는데, 명제 $q$는 증명 자체가 불가하므로 $r$이 참인경우, 명제 $q$는 가정에 모순된다. 즉, 명제 $q$는거짓이 된다.

 

(2) 명제 $r$이 참일 때, $q$가 거짓인 경우

$\sim (\exists x) dem(x, sub(k,a,k))$가 거짓이기 때문에

그의 역인 $(\exists x) dem(x, sub(k,a,k)$는 참이 된다.

 

즉, 명제 $sub(k,a,k)$의 증명 $x$가 존재한다. $sub(k,a,k)$는 $q$와 동치이기 때문에 $q$는 증명 가능하다.

그러나 $q$를 증명한다는 것은 $q$가 증명 불가능 하다는 것을 증명하는 것으로 $q$는 증명 불가능하다. $q$가 증명 불가능하다는 것은 $q$가 참이라는 것으로 이는 $r$이 참일 때, $q$가 거짓이다라는 가정에 모순된다. 결론적으로, 명제 $r$은 거짓이다. 때문에 명제$S$ 역시 거짓이고, 페아노 공리계가 무모순임을 페아노 공리계 안에서는 증명 불가능하다. 명제 $S$가 거짓이기 때문에 제 2불완전성 정리는 참이다.

 

4. Reference