괴델의 불완전성 정리

괴델의 불완전성 정리는 다음과 같은 두 가지 핵심 정리로 이루어진다.

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

이 정리는 수학적 진리와 증명 가능성이 서로 별개의 개념임을 명확히 하였으며, 체계의 완전성과 무모순성을 동시에 확보하는 것이 불가능함을 시사한다.

19세기 말과 20세기 초, 수학자들은 수학의 엄밀한 기초를 세우기 위해 노력하였다. 특히 다비트 힐베르트는 수학의 모든 명제를 유한한 공리로부터 증명하거나 반증할 수 있는 완전하고 무모순적인 체계를 구축하려는 '힐베르트의 프로그램'을 제안하였다.

당시 수학 기초론에서는 세 가지 접근 방식이 대립하였다.

1. 직관주의: 인간의 직관에 의해 수학이 도출된다고 본다.
2. 형식주의: 수학을 내용 없는 형식적 조작으로 귀착시키려 한다.
3. 논리주의: 수학의 개념이 논리학의 공리계에서 연역될 수 있다고 본다.

괴델의 정리는 산술을 포함하는 복잡한 체계에서 힐베르트의 목표를 달성하는 것이 불가능함을 입증하며 형식주의의 한계를 드러냈다.

괴델은 증명을 위해 수학적 진술과 메타수학적 진술을 연결하는 괴델 수(Gödel number) 개념을 도입하였다. 논리 기호, 변수, 명제, 증명 과정 전체에 고유한 자연수를 부여하는 방식이다.

1. 기호의 부호화: 논리 기호와 변수에 고유 번호를 할당한다.
2. 수식의 부호화: 기호열을 소수의 거듭제곱을 이용해 하나의 수로 변환한다. 예를 들어 기호열 $s_1, s_2, s_3$에 대응하는 번호가 $n_1, n_2, n_3$라면, 괴델 수는 $2^{n_1} imes 3^{n_2} imes 5^{n_3}$이 된다. 소인수분해의 유일성 덕분에 원래 기호열을 복원할 수 있다.
3. 증명의 부호화: 수식들의 나열인 증명 역시 하나의 거대한 자연수로 변환한다.

이를 통해 '명제 $A$는 공리계 $T$에서 증명 가능하다'는 메타수학적 진술을 산술적인 계산 문제로 변환하였다.

괴델은 괴델 수화를 이용하여 "이 문장은 이 체계 내에서 증명될 수 없다"는 의미를 담은 자기 지시적 명제 $G$를 구성하였다.

• 만약 $G$가 증명 가능하다면, $G$의 내용에 따라 $G$는 증명 불가능해야 하므로 모순이 발생한다.
• 만약 $G$가 증명 불가능하다면, $G$의 내용은 참이 된다.

따라서 무모순적인 체계 내에는 참이지만 증명할 수 없는 명제 $G$가 반드시 존재하게 된다. 이는 대각선 논법과 유사한 기법을 사용하여 산술적으로 구현되었다.

괴델의 정리는 현대 학문에 지대한 영향을 미쳤다.

• 수학: 수학적 공리계의 근본적 한계를 명시하고 형식주의 패러다임을 변화시켰다.
• 철학: 인간 이성의 한계와 진리의 본질에 대한 새로운 해석을 가능하게 하였다. 오펜하이머는 이를 "인간 이성 일반에 있어서 한계의 역할을 명확히 한 것"이라 평가하였다.
• 컴퓨터 과학: 계산 가능성 이론의 기초가 되었으며, 앨런 튜링의 정지 문제와 연결되어 결정 불가능한 문제의 존재를 규명하는 데 기여하였다.

이 정리는 모든 수학 체계에 적용되는 것이 아니다. 자연수 산술을 표현할 수 있을 만큼 충분히 강력하고 효과적으로 공리화된 일관된 형식 체계에만 적용된다.

예를 들어, 프레스버거 산술(Presburger arithmetic)과 같이 곱셈을 제외한 덧셈 위주의 약한 체계는 완전하고 무모순적일 수 있다. 또한, 이 정리는 '참이지만 증명 불가능한 명제'가 존재한다는 것이지, 모든 참인 명제가 증명 불가능하다는 뜻은 아니다.