힐베르트의 프로그램

19세기 말과 20세기 초, 수학계는 이른바 '수학의 기초 위기'에 직면하였다. 비유클리드 기하학의 발전과 칸토어의 집합론에서 발견된 러셀의 역설 등은 기존 수학 체계의 신뢰성에 의문을 제기하였다. 다비트 힐베르트는 이러한 혼란을 해결하고 수학을 논리적으로 완벽한 토대 위에 세우기 위해 이 프로그램을 제안하였다.

힐베르트 프로그램의 핵심은 수학의 모든 분야를 엄밀한 공리계로 형식화하는 것이다. 주요 목표는 다음과 같다.

• 형식화: 모든 수학적 진술을 정해진 규칙에 따른 기호의 배열로 변환한다.
• 무모순성: 공리계 내에서 어떤 명제 $P$와 그 부정인 $\neg P$가 동시에 증명되는 모순이 없음을 증명한다.
• 완전성: 체계 내의 모든 참인 명제는 공리로부터 증명 가능해야 한다.
• 결정 가능성: 임의의 명제가 주어졌을 때, 그것의 참과 거짓을 판별할 수 있는 기계적 절차(알고리즘)가 존재해야 한다.

힐베르트는 무모순성을 증명할 때 '유한적 방법(finitary methods)'만을 사용할 것을 강조하였다. 이는 무한에 의존하지 않고 직관적으로 명백하며 유한한 단계 내에서 수행되는 논리적 추론만을 의미한다. 이를 통해 고전 수학의 추상적인 개념들을 안전하게 정당화하고자 하였다.

1931년 쿠르트 괴델은 두 가지 불완전성 정리를 발표하여 힐베르트 프로그램의 원래 목적이 달성될 수 없음을 증명하였다.

1. 제1불완전성 정리: 산술을 포함하는 충분히 강력한 무모순적 공리계에는 참이지만 증명할 수 없는 명제가 존재한다.
2. 제2불완전성 정리: 그러한 공리계는 자신의 무모순성을 그 체계 내부의 방법으로는 증명할 수 없다.

이 결과로 인해 수학 전체를 하나의 완전하고 무모순적인 유한 공리계로 통합하려던 힐베르트의 시도는 근본적인 한계에 부딪혔다.

비록 원래의 목표는 완전히 달성되지 못했으나, 힐베르트의 프로그램은 현대 수리논리학과 증명론의 발전에 결정적인 기여를 하였다. 수학적 증명 자체를 연구 대상으로 삼는 '증명론'이라는 분야가 확립되었으며, 이는 훗날 계산 이론과 컴퓨터 과학의 기초가 되었다.