괴델의 불완전성 정리

괴델의 불완전성 정리는 두 개의 핵심 정리로 구성된다.

• 제1 불완전성 정리: 페아노 산술을 포함하는 임의의 일관된 공리적 체계 내에는, 그 체계 내에서 참이지만 증명할 수 없는 명제가 반드시 존재한다.
• 제2 불완전성 정리: 그러한 체계는 자기 자신의 일관성(무모순성)을 체계 내에서 증명할 수 없다.

이 정리는 수학적 진리와 증명 가능성이 서로 별개의 개념임을 명확히 하였다.

19세기 말과 20세기 초, 수학자들은 수학의 엄밀한 기초를 세우기 위해 노력하였다. 특히 다비트 힐베르트는 수학의 모든 명제를 유한한 공리로부터 증명하거나 반증할 수 있는 완전하고 무모순적인 체계를 구축하려는 '힐베르트의 프로그램'을 제안하였다. 그러나 1931년 괴델이 불완전성 정리를 발표하면서, 산술을 포함하는 복잡한 체계에서는 이러한 목표를 달성하는 것이 불가능함이 입증되었다.

괴델은 증명을 위해 수학적 진술과 메타수학적 진술을 구분하고, 이를 연결하는 '괴델 수(Gödel number)' 개념을 도입하였다.

괴델 수화

괴델은 논리 기호, 변수, 명제, 그리고 증명 과정 전체에 고유한 자연수를 부여하는 방식을 고안하였다. 이 과정은 크게 세 단계로 이루어진다.

1. 기본 기호의 부호화: '$\neg$', '$\lor$', '$\forall$', '(', ')'와 같은 논리 기호와 변수들에 각각 고유한 자연수를 할당한다.
2. 수식의 부호화: 기호들의 나열인 수식(명제)은 소수(prime number)의 거듭제곱을 이용하여 하나의 수로 변환한다. 예를 들어, 기호열 $s_1, s_2, s_3$에 대응하는 번호가 $n_1, n_2, n_3$라면, 이 수식의 괴델 수는 $2^{n_1} \times 3^{n_2} \times 5^{n_3}$이 된다. 소인수분해의 유일성 덕분에 이 수로부터 원래의 기호열을 유일하게 복원할 수 있다.
3. 증명의 부호화: 수식들의 나열인 '증명' 역시 같은 방식으로 소수의 거듭제곱을 사용하여 하나의 거대한 자연수로 변환한다.

이를 통해 '이 명제는 증명 가능하다'와 같은 메타수학적 진술을 산술적인 계산의 문제로 변환하였다.

자기 지시적 명제

괴델은 괴델 수화를 이용하여 "이 문장은 이 체계 내에서 증명될 수 없다"는 의미를 담은 자기 지시적 명제 $G$를 구성하였다. 만약 $G$가 증명 가능하다면 $G$의 내용에 따라 $G$는 증명 불가능해야 하므로 모순이 발생한다. 반대로 $G$가 증명 불가능하다면 $G$의 내용은 참이 된다. 따라서 무모순적인 체계 내에는 참이지만 증명할 수 없는 명제가 존재하게 된다.

증명의 구체적 단계

괴델의 증명은 크게 네 단계로 요약할 수 있다.

1. 수학과 메타수학의 구분: 수학적 대상(수, 연산)에 대한 진술과, 그 진술 자체의 성질(증명 가능성 등)에 대한 진술인 '메타수학'을 엄격히 구분한다.
2. 괴델 수화(Gödel Numbering): 논리 기호, 변수, 수식, 그리고 수식들의 나열인 '증명' 전체에 고유한 자연수를 대응시킨다. 이를 통해 논리적 구조를 수의 체계로 부호화한다.
3. 메타수학의 산술화: '명제 $A$는 공리계 $T$에서 증명 가능하다'는 메타수학적 진술을, 괴델 수를 이용해 '수 $x$와 $y$ 사이에 특정 산술적 관계 $Proof(x, y)$가 성립한다'는 수학적 진술로 변환한다.
4. 괴델 문장 $G$의 구성: 대각선 논법과 유사한 기법을 사용하여, 산술적으로는 '자신의 괴델 수가 증명 가능성 관계를 만족하지 않음'을 뜻하는 문장 $G$를 구성한다. 이 문장은 메타수학적으로 "나는 이 체계 내에서 증명될 수 없다"는 의미를 갖게 된다.

괴델의 정리는 현대 수학과 철학, 컴퓨터 과학에 지대한 영향을 미쳤다.

• 수학: 수학적 공리계의 근본적인 한계를 명시하였으며, 형식주의 수학의 패러다임을 변화시켰다.
• 철학: 인간 이성의 한계와 진리의 본질에 대한 새로운 해석을 가능하게 하였다.
• 컴퓨터 과학: 계산 가능성 이론과 알고리즘의 한계를 규명하는 데 기초가 되었다.

오펜하이머는 이 연구에 대해 "인간 이성 일반에 있어서 한계라는 것의 역할을 명확히 한 것"이라고 평가하였다.