산술의 증명은 끝없이
내려갈 수 있을까요?

두 문장은 서로 다른 증명 기반을 말합니다. 괴델의 두 번째 불완전성 정리는 충분히 강하고 일관된 산술 체계가 통상적인 방식으로 표현된 Con(PA)를 그 체계 안에서 증명할 수 없다고 말합니다. 겐첸은 산술 바깥의 메타수학에서, 산술이 자체로 정당화하지 못하는 초한귀납 원리를 명시해 상대적인 무모순성 논증을 세웠습니다.

따라서 1936년 결과는 불완전성 정리를 피한 내부 증명이 아닙니다. 어떤 원리를 더 받아들이면 산술의 모순 도출이 불가능한지 정확히 보여 줍니다. 이 경계가 바로 증명론의 연구 대상이 됩니다.

형식 체계가 무모순하다는 말은 어떤 문장 A와 그 부정 ¬A를 모두 증명할 수 없다는 뜻입니다. 고전논리에서는 정해 둔 명백한 모순, 예를 들어 0 = 1이 증명되지 않는다고 표현해도 됩니다. 하나의 모순을 증명하면 폭발 원리에 따라 모든 문장을 얻을 수 있기 때문입니다.

무모순성은 ‘모든 산술 명제가 참인지 판정할 수 있다’거나 ‘산술이 완전하다’는 말과 다릅니다. 겐첸의 목표는 증명 가능한 문장의 범위를 모두 결정하는 것이 아니라 모순 도출의 부재를 보이는 일입니다.

자연수 0, 후속자, 덧셈과 곱셈을 다루며 완전귀납법을 쓰는 일차 산술입니다. 겐첸은 논증을 위해 형식 체계를 세밀하게 배열하고, 논리 추론과 수론적 규칙이 증명에서 어떻게 작동하는지 분석합니다. 오늘날에는 페아노 산술 PA의 증명론적 분석이라는 말로 핵심을 설명합니다.

다만 1936년 논문의 표기와 계산을 현대 교과서의 PA 표기와 그대로 동일시하면 안 됩니다. 이 글은 원문의 체계를 현대 독자가 알아볼 수 있는 말로 옮기되, 현대적 약칭을 원문의 문장처럼 제시하지 않습니다.

모순을 증명했다고 가정하고 그 증명을 더 단순한 증명으로 바꾸는 과정을 생각합니다. 논리적 우회와 불필요한 중간 단계를 걷어내면, 마지막에는 참인 수치 등식으로 끝나거나 거짓인 수치 등식을 전제로 삼는 식의 명백한 상태에 이르러야 합니다. 모순 증명은 그런 정상적인 종착점에 도달할 수 없습니다.

문제는 환원을 계속 적용했을 때 반드시 멈추는지입니다. 증명 크기만 세면 한 부분을 줄이는 동안 다른 부분이 복제되어 더 커질 수 있습니다. 그래서 겐첸은 단순한 줄 수보다 정교한 감소 척도를 사용합니다.

증명에 실제로 붙이는 것은 0, 1, ω, ω+1, ω², ω^ω처럼 유한하게 적은 기호열입니다. 이 표기들은 자연수보다 긴 잘 정렬된 순서를 압축해 나타냅니다. 증명 하나에는 유한한 표기 하나가 배정되고, 환원 전후 표기를 비교합니다.

여기서 순서수는 시간의 길이나 실제 무한 단계의 목록이 아닙니다. 복잡성의 층위를 비교하는 색인입니다. 자연수 17보다 16이 작듯, 정해 둔 순서수 표기 체계에서도 두 유한 표기 가운데 어느 것이 앞서는지 계산합니다.

아래 카드는 낮은 층에서 높은 층으로 배열되어 있습니다. 카드를 눌러 칸토어 정규형과 읽는 법을 확인해 보세요. 이 실험은 현대 순서수 표기의 입문 모형이며, 겐첸이 1936년 논문에서 사용한 십진 부호 체계를 그대로 복제한 것이 아닙니다.

두 자연수 a, b로 작업의 상태를 적어 봅시다. a는 남은 큰 작업의 수, b는 현재 큰 작업 안에서 남은 작은 작업의 수입니다. b가 양수이면 1을 줄입니다. b가 0이고 a가 양수이면 큰 작업 하나를 마치고, 다음 큰 작업의 작은 작업 수를 유한한 값으로 정합니다.

상태 (a,b)에 ω·a+b를 붙이겠습니다. ω는 모든 자연수보다 뒤에 오는 첫 무한 순서수입니다. a가 그대로이면 b가 줄 때 값이 작아집니다. a가 줄면 새 b가 아무리 큰 유한한 수여도 이전 큰 작업의 경계를 넘지 못합니다. 예를 들어 ω+4는 ω·2보다 작습니다.

그래서 (2,0)에서 (1,4)로 바뀌면 두 수의 합은 2에서 5로 늘지만, 순서수 값은 ω·2에서 ω+4로 줄어듭니다. 이 비교는 “줄 수가 늘어도 더 높은 층의 감소를 측정할 수 있다”는 원리를 보여 줍니다. 실제 산술 증명에 값을 배정하는 겐첸의 규칙은 훨씬 복잡합니다.

논리식의 연결사를 한 겹 벗기는 환원은 대체로 식의 구조를 따라갑니다. 완전귀납법은 밑단계와 ‘n에서 n+1로’ 가는 단계를 묶어 모든 자연수에 대한 결론을 만듭니다. 특정 수치에 귀납 증명을 펼치면 귀납 단계가 여러 번 복제되고, 증명 크기가 급격히 변할 수 있습니다.

앞 회차의 컷 제거만으로 산술 전체가 곧바로 정규화되지 않는 이유도 여기에 있습니다. 귀납식의 복잡성과 중첩을 함께 제어하려면 자연수 높이보다 긴 척도가 필요합니다.

엡실론 제로라고 읽습니다. 현대적으로는 α = ω^α를 만족하는 가장 작은 순서수이며, 1에서 시작해 ω를 지수로 반복해서 쌓는 유한 탑들의 상한으로 설명할 수 있습니다. 겐첸의 환원에 필요한 유한 순서수 표기들이 이 경계 아래에 놓입니다.

1936년 논문은 오늘날 교과서처럼 ε₀ 표기 하나만 앞세우기보다 십진 부호를 이용해 초한귀납의 범위를 제시합니다. ‘ε₀까지의 귀납’은 그 논증을 현대 순서수 분석으로 정리한 말입니다. 1938년 새 증명에서는 순서수 표기의 역할이 더 분명하게 드러납니다.

단계를 눌러 표기와 다음 단계를 확인해 보세요. 화면은 유한 높이의 지수 탑들을 보여 줍니다. ε₀라는 이름은 유한하게 쓸 수 있지만, 이 탑들의 어느 한 유한 단계와도 같지 않습니다. 어느 유한 단계도 다음 단계를 가질 수 있고, 그 전체 과정의 상한을 ε₀라고 부른다는 점을 보여 줍니다.

자연수에서 5, 4, 3처럼 계속 작아지면 결국 멈춥니다. ε₀ 아래의 순서수 표기도 잘 정렬되어 있어 엄격히 감소하는 무한열이 없습니다. 이 사실을 해당 표기 체계에 대한 초한귀납법으로 사용합니다.

따라서 모순 증명을 환원할 때 값이 매번 작아진다면 환원은 유한 번 뒤에 끝나야 합니다. 그런데 끝에 남을 정상 증명은 모순을 결론으로 가질 수 없습니다. 처음의 모순 증명 가정이 배제됩니다.

각 버튼은 상태 (a,b)가 한 번 바뀌는 경우입니다. 앞의 규칙에서 허용되는 이동인지 먼저 보고, 허용된다면 순서수 값이 왜 작아지는지 설명해 보세요. 두 수를 단순히 더한 값과 순서수 값도 함께 비교할 수 있습니다.

이 모형은 자연수의 단순 감소만으로는 놓치기 쉬운 여러 층의 작업을 보여 줍니다. 겐첸의 무모순성 증명으로 이어가려면 실제 증명의 환원 규칙마다 감소를 확인하고, 정상적인 마지막 증명이 모순을 결론으로 갖지 않는다는 점까지 증명해야 합니다.

절대적이라는 말은 적절하지 않습니다. 증명은 ε₀ 아래 순서수 표기의 잘 정렬됨과 그에 대한 초한귀납을 받아들입니다. 이 원리는 산술 내부에서 산술이 스스로 정당화할 수 있는 통상적 귀납보다 강합니다. 겐첸은 무모순성 문제를 더 분명하다고 여긴 구성적 원리로 환원했습니다.

이 때문에 결과의 철학적 평가는 갈렸습니다. 힐베르트가 요구한 엄격한 유한주의를 충족했는지와, 초한귀납이 어느 의미에서 구성적인지는 별도 논점입니다. 수학적 성과는 의존 원리를 드러내고 PA의 증명론적 강도를 ε₀와 연결했다는 데 있습니다.

겐첸이 정한 환원 규칙과 ε₀ 아래의 순서수 척도에서는 산술 증명이 끝없이 내려갈 수 없습니다. 모순 증명이 있다면 엄격히 감소하는 환원을 거쳐 정상 종착점에 이르러야 하지만, 그런 종착점은 모순 증명이 될 수 없습니다. 따라서 초한귀납 원리 아래에서 산술의 무모순성이 따라옵니다.

이 논증은 증명에 결론의 참·거짓 외에도 ‘어느 정도 강한 귀납이 필요한가’라는 정량적 정보를 붙였습니다. 이후 순서수 분석은 형식 이론의 강도를 비교하고, 정규화와 프로그램 종료를 설명하며, 증명에서 계산적 내용을 추출하는 연구로 이어집니다.