괴델의 불완전성 정리: 형식 체계의 불완전성

괴델의 불완전성 정리: 왜 형식적 수학에는 한계가 있는가

1931년, 쿠르트 괴델은 어떤 충분히 강력한 산술 형식 체계에도 근본적인 한계가 있음을 증명했습니다. 그의 불완전성 정리는 자연수에 관한 모든 참인 명제를 증명할 수 있는 일관된 체계를 구성하는 것이 불가능함을 보여주었습니다. 이 발견은 수학 전체를 완전히 형식화하려는 오랜 꿈을 무너뜨렸습니다.

과학과 수학에서의 통일 경향

19세기 말에서 20세기 초로 넘어가는 시기, 과학 분야에서는 강력한 통일 경향이 나타났습니다. 뉴턴은 지상의 중력을 천체 역학과 하나로 통합했고, 맥스웰은 전기·자기·빛을 단일 전자기장으로 설명했습니다. 다윈은 자연선택을 통해 생명의 다양성을 설명했습니다.

수학자들도 유사한 종합을 추구했습니다: 산술·기하·해석학을 하나의 공리 집합에서 유도하려는 시도였습니다. 프레게는 집합론을 기반으로 수를 정의하려 했습니다:

• 0 = ∅ (공집합)
• 1 = {∅}
• 2 = {∅, {∅}}

수 n의 후속수(successor)는 이전까지의 모든 수의 합집합으로 정의되어, 산술 전체를 완전히 형식화할 수 있었습니다. 그러나 러셀의 역설이 이 체계를 붕괴시켰습니다: 해당 공리들로부터 모순—유명한 ‘자신을 포함하지 않는 모든 집합들의 집합’—이 도출되었기 때문입니다.

기초 위기와 힐베르트 프로그램

러셀의 역설은 수학의 기초 위기를 촉발시켰습니다. 다비드 힐베르트는 이에 대응해 대담한 형식화 프로그램을 제안했는데, 어떤 공리 체계라도 다음 세 가지 성질을 만족해야 한다고 주장했습니다:

• 완전성: 체계가 자연수에 관한 모든 참인 명제를 증명할 수 있어야 함.
• 일관성(K): 체계가 거짓 명제를 절대 증명하지 않아야 함.
• 판정 가능성: 주어진 임의의 명제가 증명 가능한지 여부를 판단하는 알고리즘이 존재해야 함.

힐베르트는 이 세 성질이 메타수학적 방식으로, 즉 체계 자체에 대한 유한하고 구체적인 추론을 통해 증명되어야 한다고 강조했습니다.

러셀과 화이트헤드의 『수학 원리』

버트런드 러셀과 앨프레드 노스 화이트헤드는 수학 전체를 재구성할 수 있을 만큼 강력한 공리적 논리 체계인 『수학 원리』(PM)를 저술했습니다. 그들은 산술을 처음부터 다시 구축했으며, 유명하게도 1 + 1 = 2를 증명하는 데 300쪽 이상을 할애했습니다.

PM을 분석하기 위해 괴델은 그 문법을 PM-Lisp 스타일 언어로 단순화했습니다:

| 기호 | 의미 | 예시 |

|------|------|------|

| 0 | 영 | 0 |

| next | 후속수 | (next 0) |

| + | 덧셈 | (+ 0 (next 0)) |

| | 곱셈 | ( 0 (next 0)) |

| = | 동치 | (= 0 (* 0 (next 0))) |

논리 연산자:

| 기호 | 의미 | 예시 |

|------|------|------|

| not | 부정 | (not (= 0 1)) |

| or | 논리합 | (or (= 0 1) (not (= 0 1))) |

| when | 함의 | (when 0 (or 0 1)) |

| there-is | 존재 한정 | (there-is x (= 4 (* x 2))) |

PM의 공리에는 다음과 같은 타우톨로지가 포함되었습니다:

• (when (or p p) p)
• (when p (or p q))
• 논리합의 교환법칙 및 결합법칙
• 삼단논법 규칙

이들로부터 등호와 산술이 단계적으로 유도되었습니다.

괴델 수: 문법을 수로 인코딩하기

괴델은 칸토르 스타일 인코딩을 적용해 모든 수식을 고유한 자연수로 매핑했습니다. 각 기호는 소수 기반의 고유한 괴델 수를 받았습니다:

| 기호 | 괴델 수 |

|------|----------|

| ( | 1 |

| ) | 3 |

| 0 | 5 |

| next | 7 |

| + | 9 |

| * | 11 |

| = | 13 |

| not | 15 |

| or | 17 |

| when | 19 |

| there-is | 21 |

| a, b, c, … | 2, 4, 6, … |

수식 (there-is a (= (next 0) a))는 토큰의 나열로 변환되며, 그 괴델 수는 G = 2^g₁ × 3^g₂ × 5^g₃ × … 로 계산됩니다. 여기서 gᵢ 는 i-번째 토큰의 괴델 수입니다. 이를 통해 수식과 자연수 사이에 완벽한 일대일 대응이 성립합니다.

핵심은 PM-Lisp 산술이 자기 자신 안에서 표현 가능하다는 점입니다: 수식 길이, 치환, 증명 가능성 등 모두 원시 재귀 함수로 환원되므로 자기참조(self-reference)가 가능해집니다.

자기참조와 불완전성 정리

괴델은 자신의 무증명성을 주장하는 수식 G 를 구성했습니다: ∃p Proof(p, ⌜G⌝) — “나를 증명하는 번호 p 를 가진 증명은 존재하지 않는다.”

대각선 보조정리(고정점 정리)에 의해:

G ≡ ¬Provable(⌜G⌝)

정리 1: 만약 PM이 일관적이라면, G 는 PM 내에서 증명 불가능하지만 참이다.

정리 2: 만약 PM이 일관적이라면, PM의 일관성을 주장하는 명제 Con(PM) 은 PM 내에서 증명 불가능하다.

핵심 요약:

• 페아노 산술을 해석할 수 있는 모든 체계는 불완전하다.
• 어떤 체계의 일관성은 그 체계 내부에서 증명할 수 없다.
• 자연수는 문법을 인코딩할 수 있으며, 이것이 자기참조를 가능하게 한다.
• 힐베르트 프로그램은 근본적으로 실현 불가능하다.
• ‘참됨’과 ‘증명 가능성’은 동치가 아니다.

컴퓨터 과학에 미치는 영향

괴델의 정리는 튜링의 정지 문제와 논리적으로 동치입니다. 형식 체계는 본질적으로 ‘맹점’을 지니고 있습니다. 프로그래밍에서는 다음과 같이 드러납니다:

• 계산 불가능한 함수(예: 가상의 정지 판별 오라클).
• 검증 도구에 내재된 논리 폭탄.
• 형식적 소프트웨어 검증의 근본적 한계.

현대 증명 보조 도구(Coq, Lean 등)는 불완전성을 명시적으로 인정하며, 절대적 확실성을 주장하지 않고 신뢰할 수 있는 공리에 의존합니다.

— Editorial Team