On a Theorem by Bezboruah & Shepherdson

Each language version is independently generated for its own context, not a direct translation.

1. 배경: 거대한 성벽과 작은 돌멩이 (배경 지식)

수학에는 **'괴델의 제 2 불완전성 정리'**라는 유명한 법칙이 있습니다.

"어떤 수학 이론이 스스로의 모순 (불일치) 이 없음을 증명할 수 있다면, 그 이론은 이미 모순이 있는 것이다."

즉, **"자신의 정직함을 스스로 증명할 수 있는 시스템은 존재하지 않는다"**는 뜻입니다.

하지만 이 정리가 성립하려면 그 이론이 충분히 강력해야 합니다. 마치 거대한 성벽을 쌓을 수 있는 기술이 있어야 하죠.
1976 년, 베즈보루아 (Bezboruah) 와 셰퍼드슨 (Shepherdson) 이라는 두 학자는 "이 정리가 아주 약한 이론 (성벽이 아니라 작은 돌멩이 하나만 있는 수준) 에서도 성립할까?"라고 질문했습니다.

2. 크라이젤의 반대: "그건 의미가 없어!" (논쟁)

당시 수학계의 거물 크라이젤 (Kreisel) 은 이 연구에 대해 강력하게 반대했습니다. 그의 주장은 다음과 같습니다.

"그런 약한 이론에서는 '증명'이라는 개념이 제대로 작동하지 않아. 마치 아기에게 고등 물리학 문제를 풀게 하는 것과 같아. 아기가 문제를 풀지 못한다고 해서 '아기가 물리학을 모른다'는 결론을 내리는 게 아니라, '아기에게 그 문제를 풀 수 있는 능력이 없다'는 뜻이지. 그러니 그 이론이 '자신의 모순을 증명하지 못한다'는 건 의미가 없어."

즉, 크라이젤은 **"약한 이론에서는 '자신'이라는 개념 자체가 제대로 정의되지 않으니, 그 이론이 스스로를 증명하지 못한다는 건 아무런 의미가 없다"**고 주장했습니다.

3. 비서의 반박: "의미는 강자에게서 온다" (논증)

저자 비서는 크라이젤의 주장을 **"아기에게 물리학을 가르치지 않는다고 해서 아기가 물리학을 이해할 수 없다는 뜻은 아니다"**라고 반박합니다.

비유의 예: 우리가 ZFC(강력한 수학 이론) 로 어떤 사실을 증명했다고 칩시다. 그런데 "이걸 선택 공리 없이 증명할 수 있니?"라고 물었을 때, "아니, ZF(약한 이론) 에서는 그 문장의 의미가 달라져서 증명할 수 없어"라고 답한다면 어떨까요? 그건 너무 억지스러운 소리입니다.
결론: 약한 이론 (Q 나 PA-) 에서도 '증명'과 '모순'이라는 개념은 강한 이론의 관점에서 볼 때 여전히 유효합니다. 따라서 약한 이론이 스스로의 모순을 증명하지 못한다는 사실은 여전히 기술적으로 의미 있는 도전이자 중요한 결과입니다.

4. 두 가지 다른 접근법 (비교)

이 논문은 두 가지 다른 방식으로 이 문제를 해결한 방법을 비교합니다.

푸들락 (Pudlák) 의 방법 (현대식):
- 비유: 거대한 성벽 (강한 이론) 을 짓기 위해 필요한 최소한의 설계도를 찾아내는 방식입니다.
- 약한 이론 (Q) 이 사실은 강력한 이론 (S1^2) 을 '숨겨진 형태'로 포함하고 있다는 것을 증명하여, 괴델의 정리가 자연스럽게 적용되도록 합니다.
- 특징: 매우 정교하고 일반적이지만, 구체적인 '증명 과정'을 눈으로 보기 어렵습니다.
베즈보루아 & 셰퍼드슨 (B&S) 의 방법 (구식):
- 비유: 가짜 법원을 만들어서, 그 법원에서 "유죄 판결"이 내려지는 상황을 직접 만들어내는 방식입니다.
- 아주 약한 이론 (PA-) 에서도, 특정한 방식으로 코딩 (숫자화) 을 하면, 실제로는 모순이 아닌데 시스템이 '모순'이라고 착각하는 가짜 증명을 만들어낼 수 있습니다.
- 특징: 구체적인 모델을 직접 구성하여, "보여주기"에 초점을 맞춥니다.

5. 비서의 새로운 요리법 (마르코프 코딩)

비서는 이 논문에서 B&S 의 결과를 증명하는 새로운 방법을 제시합니다.

기존 방법 (베타 함수): 숫자들을 나열하는 전통적인 방식.
새로운 방법 (마르코프 코딩): 행렬 (Matrix) 을 이용한 방식입니다.
- 비유: 숫자들을 나열하는 대신, 레고 블록을 특정 규칙 (행렬 곱셈) 으로 쌓아 올리는 방식입니다.
- 비서는 "진실한 산술 (True Arithmetic)"이라는 거대한 세계를 배경으로, 비표준 모델 (일반적인 수학과는 조금 다른, 무한히 큰 숫자가 있는 세계) 을 두 개 (M 과 N) 만들어냅니다.
- 이 두 세계 사이를 오가며, M 에서는 존재하지 않지만 N 에서는 존재하는 특이한 행렬 (증명 서열) 을 만들어냅니다.
- 이 서열을 약한 이론 (PA-) 으로 가져오면, 시스템은 이를 '모순의 증명'으로 인식하지만, 실제로는 그 증명 과정의 중간에 '공백'이 있는 가짜 증명이 됩니다.

6. 결론: 왜 이 연구가 중요한가?

크라이젤의 오해 깨기: 약한 이론에서도 괴델의 정리는 의미가 있으며, 크라이젤의 반론은 타당하지 않음을 보여줍니다.
교육적 가치: 이 연구는 추상적인 수학적 개념을 구체적인 모델 (가짜 법원, 레고 블록) 로 시각화할 수 있게 해줍니다. 특히, "모순의 증명"이 어떻게 만들어지는지를 눈으로 볼 수 있게 합니다.
기술적 도전: 아주 약한 이론에서도 복잡한 수학적 구조를 어떻게 다룰 수 있는지 보여주는 훌륭한 기술적 성과입니다.

한 줄 요약:

"수학의 거물 크라이젤은 '약한 이론에서의 불완전성 증명'을 의미 없는 짓이라고 했지만, 비서는 '그건 오히려 가장 흥미로운 퍼즐 조각이야'라고 말하며, 레고 블록 (행렬) 을 이용해 약한 이론이 스스로를 속이는 가짜 증명을 어떻게 만들어내는지 직접 보여줍니다."

이 논문은 수학의 기초가 얼마나 튼튼하고 흥미로운지, 그리고 약한 시스템에서도 그 깊이가 어떻게 드러나는지를 보여주는 멋진 이야기입니다.

Each language version is independently generated for its own context, not a direct translation.

알베르트 비서 (Albert Visser) 의 논문 "ON A THEOREM BY BEZBORUAH & SHEPHERDSON"은 1976 년 베조보루아 (Bezboruah) 와 셰퍼드슨 (Shepherdson) 이 증명한 약한 산술 이론 $PA^-$ 의 일관성 (consistency) 불증명 정리에 대한 재조명, 크라이젤 (Kreisel) 의 비판에 대한 반박, 그리고 새로운 시퀀스 코딩 (Markov coding) 을 이용한 새로운 증명 방법을 제시하는 내용입니다.

다음은 이 논문의 문제 제기, 방법론, 주요 기여, 결과 및 의의에 대한 상세한 기술적 요약입니다.

1. 문제 제기 (Problem)

배경: 괴델의 제 2 불완전성 정리는 충분히 강력한 산술 이론이 자신의 일관성을 증명할 수 없다는 내용입니다. 그러나 이 정리가 매우 약한 이론인 로빈슨의 $Q$ 나 $PA^-$ (이산적으로 순서화된 가환환의 음이 아닌 부분) 에 적용될 수 있는지에 대해서는 논쟁이 있었습니다.
크라이젤의 비판: 조지 크라이젤 (Georg Kreisel) 은 베조보루아와 셰퍼드슨의 결과를 의미 없다고 비판했습니다. 그의 주장은 다음과 같습니다:
- $Q$ 나 $PA^-$ 와 같은 약한 이론은 증명 가능성 예측자 (provability predicate) 에 대한 힐베르트 - 번스 (Hilbert-Bernays) 조건이나 뢰브 (Löb) 조건을 증명할 수 없습니다.
- 따라서 이러한 약한 이론 내에서 서술된 일관성 명제 ( $con(Q)$ 등) 는 실제로 '일관성'을 표현하는 것이 아니라 단순한 대수적 성질에 불과합니다.
- 결과적으로, 약한 이론이 자신의 일관성을 증명하지 못한다는 것은 철학적으로 무의미합니다.
논문 목적: 저자는 크라이젤의 비판이 타당하지 않음을 주장하고, 베조보루아 - 셰퍼드슨 정리의 기술적 중요성을 재평가하며, 기존의 $\beta$ -함수 코딩 외에 마르코프 (Markov) 코딩을 이용한 새로운 증명을 제시합니다.

2. 방법론 (Methodology)

크라이젤 비판에 대한 반박 (철학적/논리적 접근):
- 의미는 이론에 따라 변하지 않으며, 약한 이론 내의 추론도 강한 이론 (예: $PA$ ) 에서 부여된 의미를 가질 수 있다고 주장합니다.
- 약한 이론이 특정 조건을 증명하지 못한다고 해서 그 이론 내의 명제가 '일관성'을 표현하지 않는다고 단정하는 것은 타당하지 않습니다.
- 뢰브 조건이 너무 강력할 수 있음을 인정하더라도, 약한 이론에서도 일관성 불증명 현상을 연구하는 것은 기술적 도전이자 교육적 가치가 있다고 봅니다.
비교 분석:
- 파벨 푸들라크 (Pavel Pudlák) 의 제 2 불완전성 정리 확장 ( $S_1^2$ 이론과 절단 (cut) 을 이용한 접근) 과 베조보루아 - 셰퍼드슨 정리를 비교합니다.
- 푸들라크의 접근은 해석 (interpretability) 을 기반으로 하여 더 일반적이지만, 베조보루아 - 셰퍼드슨의 접근은 구체적인 모델 구성을 통해 직관적인 이해를 제공합니다.
새로운 증명 방법 (Markov Coding):
- 기존 베조보루아 - 셰퍼드슨 증명은 $\beta$ -함수를 이용한 시퀀스 코딩에 의존했습니다.
- 저자는 **마르코프 코딩 (Markov Coding)**을 도입하여 새로운 증명을 구성합니다. 이는 $SL_2(\mathbb{Z}^+)$ (정수 행렬, 양의 성분을 가진 부분군) 가 2 개의 생성자 ( $A, B$ ) 에 의한 자유 모노이드 (free monoid) 와 동형이라는 사실 (니켈슨 - 마르코프의 통찰) 에 기반합니다.
- 모델 구성: 표준 모델의 비표준 확장 (non-standard extension) 을 사용하여, $PA^-$ 의 모델을 구성합니다. 이 모델에서는 특정 행렬 곱셈을 통해 '증명'으로 보이는 시퀀스를 생성하지만, 실제로는 증명 과정의 전환점 (axioms 에서 conclusion 로의 전환) 을 놓치게 하여 모순 ( $\bot$ ) 을 유도합니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

A. 크라이젤의 비판 반박

저자는 크라이젤의 주장이 "의미는 이론에 의존한다"는 전제 하에 성립하지만, 이는 직관적이지 않으며 약한 이론의 연구 가치를 부정하는 근거가 될 수 없다고 결론지었습니다.
베조보루아 - 셰퍼드슨 정리는 $Q$ 나 $PA^-$ 가 자신의 일관성을 증명하지 못함을 보여주며, 이는 기술적으로 중요한 도전 과제임을 강조했습니다.

B. 푸들라크 정리와의 비교

푸들라크의 정리: $U$ 가 $Q + con(U)$ 를 해석하면 $U$ 는 모순임을 보임. 이는 $S_1^2$ 이론과 절단 (cut) 기술을 사용하여 제 2 불완전성 정리를 매우 약한 이론까지 확장한 것입니다.
베조보루아 - 셰퍼드슨 정리: $PA^-$ 가 특정 약한 이론 ( $BeSh$ ) 의 일관성을 증명하지 못함을 보임.
차이점:
- 푸들라크의 접근은 해석 (interpretability) 에 기반하여 더 일반적이지만, 구체적인 모델 구성이 어렵습니다.
- 베조보루아 - 셰퍼드슨의 접근은 구체적인 모델 (재귀적 모델) 을 구성하여 모순 증명의 존재를 시각화할 수 있게 합니다.
- 두 결과는 서로 다른 범주에 속하지만, $Q$ 의 일관성 불증명이라는 점에서 겹칩니다.

C. 마르코프 코딩을 이용한 새로운 증명 (Theorem 4.1)

주요 정리: $PA^-$ (또는 모든 참인 보편 문장들을 포함한 $PA^-$ ) 는 마르코프 코딩을 사용하여 시퀀스를 인코딩할 때, 이론 $BeSh$ 의 일관성을 증명하지 못한다.
증명 아이디어:
1. $N$ 을 $M$ 의 원소적 끝 확장 (elementary end-extension) 인 비표준 모델로 설정합니다.
2. $a \in M \setminus N$ (비표준 원소) 과 $b \in N \setminus M$ 을 선택합니다.
3. 행렬 $\beta = [n]^a [m]^b$ 를 구성합니다. 여기서 $[n]$ 은 $n$ 을 코딩하는 행렬입니다.
4. 이 행렬 $\beta$ 는 $N$ 에서는 유효한 증명 시퀀스가 아니지만, $N$ 을 $PA^-$ 의 모델 $K$ 로 '얇게' (thinning out) 줄일 때, $\beta$ 는 $K$ 내에서 유효한 증명 시퀀스로 작용하게 됩니다.
5. 구체적으로, $K$ 에서는 $\beta$ 의 시작 부분 (axioms) 과 끝 부분 (conclusion) 이 연결되어 모순 ( $\bot$ ) 을 유도하는 것처럼 보이지만, 실제로는 $N$ 에서는 연결되지 않는 '구멍'이 존재합니다.
6. Lemma 4.3: 이 구성의 핵심은 $x_1$ (비표준 원소) 이 생성된 모델 $K_0$ 에 속하지 않음을 보이는 것입니다. 이를 통해 $K$ 내에서 증명 시퀀스의 일부가 '잘려나간' 상태가 되어 모순이 유도됩니다.

4. 의의 및 결론 (Significance)

기술적 도전의 성취: 약한 이론 $PA^-$ 에서 일관성 불증명 정리를 다양한 코딩 방식 ( $\beta$ -함수, 마르코프 코딩) 으로 증명함으로써, 이 정리가 코딩 방식에 의존하지 않는 보편적인 성질임을 보여줍니다.
교육적 가치: 베조보루아 - 셰퍼드슨의 모델 구성은 $S_1^2$ 과 같은 약한 이론의 모델에서 모순 증명이 어떻게 존재할 수 있는지 시각화할 수 있게 하여, 논리학 교육에 큰 도움이 됩니다.
이론적 명확성: 크라이젤의 비판이 타당하지 않음을 논리적으로 반박함으로써, 약한 산술 이론에서의 불완전성 연구가 여전히 유효하고 중요한 분야임을 재확인시켰습니다.
새로운 도구: 마르코프 코딩과 행렬 이론 ( $SL_2$ ) 을 논리학의 증명 이론에 적용한 것은 새로운 방법론적 통찰을 제공합니다.

요약하자면, 이 논문은 베조보루아 - 셰퍼드슨 정리의 철학적 정당성을 옹호하고, 이를 푸들라크의 현대적 정리와 비교 분석하며, 마르코프 코딩을 활용한 새로운 증명을 통해 약한 산술 이론의 한계를 명확히 규명하는 중요한 작업입니다.