On a Question of Hamkins'

이 논문은 햄킨스 (Hamkins) 의 질문을 다루며 확장성 (Extensionality) 조건 하에서는 어떤 복잡도의 로서 (Rosser) 수식도 존재할 수 없음을 증명하고, 조건부 확장성 (Conditional Extensionality) 에 대해서는 긍정적 해답을 제시하지만 일관된 확장성 (Consistent Extensionality) 에 대한 문제는 여전히 미해결로 남긴다.

핵심

🕵️‍♂️ 핵심 질문: "진실을 말하되, 상황에 따라 달라지는 말"은 가능한가?

저자 앨버트 비서 (Albert Visser) 는 조엘 햄킨스 (Joel Hamkins) 가 던진 아주 흥미로운 질문을 해결했습니다.

햄킨스의 질문:
"우리가 어떤 명제 (φ) 를 가정했을 때, 그 명제가 참인지 거짓인지 알 수 없는 '중립적인 진술 (ρ)'을 만들 수 있을까요? 그리고 이 진술은 가설이 무엇이든 상관없이 (Extensionality), 그 가설과 논리적으로 동등한 다른 가설이 나오면 똑같이 반응해야 합니다."

즉, **"어떤 상황 (가설) 이든, 그 상황과 논리적으로 똑같은 다른 상황에서는 똑같은 반응을 보여야 하는, 하지만 그 상황 자체에서는 참도 거짓도 될 수 있는 마법 같은 문장"**을 만들 수 있느냐는 것입니다.

🚫 결론 1: 완벽한 '마법 문장'은 존재하지 않습니다 (부정적 답변)

논문의 첫 번째 결론은 **"그런 완벽한 문장은 없습니다"**입니다.

🌰 비유: 변덕스러운 심판
가상적인 심판 (이론) 이 있다고 가정해 봅시다. 이 심판은 "A 팀과 B 팀이 똑같이 뛰었다면 (논리적 동등), A 팀에게도 B 팀에게도 똑같은 점수를 줘야 한다 (확장성)"는 규칙을 따릅니다.
하지만 햄킨스는 "그런 심판이 있으면, A 팀이 이길 수도 있고 질 수도 있는 상황 (독립성) 을 만들어내라"고 요구했습니다.

논증에 따르면, 만약 그런 심판이 존재한다면 모순이 발생합니다.

1. 심판이 A 팀에게 점수를 주면, A 팀은 패배하게 됩니다.
2. 심판이 A 팀에게 점수를 주지 않으면, A 팀은 승리하게 됩니다.
3. 그런데 심판은 A 팀과 논리적으로 같은 B 팀에게도 똑같이 점수를 줘야 합니다.
4. 결국 심판은 "A 팀이 이겼다"라고 말하면서도 "A 팀이 졌다"라고 말하게 되어, 심판 시스템 자체가 붕괴됩니다.

즉, 완벽하게 공정하고 (확장성), 동시에 중립적일 수 있는 (독립성) 문장은 수학적으로 불가능합니다.

---

✅ 결론 2: 규칙을 조금만 바꾸면 '마법'이 가능합니다 (긍정적 답변)

하지만 비서 교수는 "완벽한 것은 아니지만, 약간 조건을 완화하면 그런 문장을 만들 수 있다"고 말합니다.

조건의 변화:

• 기존 조건 (완전 확장성): "A 와 B 가 논리적으로 같다면, 어떤 상황에서도 A 와 B 에 대해 똑같이 반응하라."
• 새 조건 (조건부 확장성): "A 와 B 가 논리적으로 같다면, A 가 참인 상황 (일관된 상황) 에만 A 와 B 에 대해 똑같이 반응하라."

🌰 비유: 상황 판단이 빠른 변호사
완벽한 심판은 실패했지만, **"상황을 잘 파악하는 변호사"**는 성공했습니다.
이 변호사는 "당신이 무죄라면 (일관된 상황), 당신과 똑같은 다른 사람도 무죄라고 주장할 수 있다"고 말합니다. 하지만 "당신이 이미 유죄로 밝혀진 상황"에서는 그 규칙을 적용하지 않습니다.

이 조건을 만족하면, **π₀₁-유연성 (Π₀₁-Flexibility)**이라는 놀라운 능력을 가진 문장을 만들 수 있습니다.

이 '유연성'이 뭐죠?
이 문장은 **"내가 어떤 진술 (π) 이 되든, 그 진술과 내가 같은지 다른지 결정할 수 있다"**는 뜻입니다.

• "내가 '1+1=2'와 같다"고 해도 모순이 안 납니다.
• "내가 '1+1=3'과 같다"고 해도 모순이 안 납니다.
• 즉, 이 문장은 **상황에 따라 자신의 성격을 자유롭게 바꿀 수 있는 '변신 능력'**을 가집니다.

---

🧩 요약: 이 논문이 우리에게 주는 메시지

1. 완벽한 중립은 불가능합니다: 어떤 이론이든, 그 이론과 논리적으로 동등한 모든 경우에 똑같이 반응하면서 동시에 그 이론의 진위를 결정하지 않는 문장은 만들 수 없습니다. (논리적 모순이 생기기 때문입니다.)
2. 조건부 중립은 가능합니다: "일관된 상황 (모순이 없는 상황) 에만" 똑같이 반응하도록 규칙을 바꾸면, **자신의 성격을 상황에 따라 자유롭게 바꿀 수 있는 '유연한 문장'**을 만들 수 있습니다.
3. 남은 미스터리: "일관된 경우만"과 "완전한 경우" 사이의 중간 단계인 **"일관된 확장 (Consistent Extensionality)"**에 대해서는 아직 답을 찾지 못했습니다. 이것이 현재 열려 있는 가장 중요한 질문입니다.

💡 한 줄 요약

"완벽하게 공정하면서도 상황에 따라 변할 수 있는 마법 문장은 없지만, '일관된 상황'에서만 공정하게 변신하는 문장은 만들 수 있습니다."

이 연구는 수학이 얼마나 정교하고, 동시에 그 정교함 때문에 어떤 한계가 있는지를 보여주는 아름다운 사례입니다.

기술 요약

논문 요약: Hamkins 의 질문에 대하여

1. 연구 배경 및 문제 제기 (Problem)

Joel Hamkins 는 [Ham22] 에서 다음과 같은 질문 (Question 28) 을 제기했습니다.

질문: 페아노 산술 (PA) 에 대해 다음 두 성질을 만족하는 $\Pi^0_1$-공식 $\rho(x)$ 가 존재하는가?

1. 독립성 (Independence): $PA + \varphi$가 일관적 (consistent) 이라면, $PA + \varphi + \rho(\ulcorner\varphi\urcorner)$와 $PA + \varphi + \neg\rho(\ulcorner\varphi\urcorner)$ 모두 일관적이다.
2. 확장성 (Extensionality): $PA \vdash \varphi \leftrightarrow \psi$라면, $PA \vdash \rho(\ulcorner\varphi\urcorner) \leftrightarrow \rho(\ulcorner\psi\urcorner)$이다.

이 두 성질을 모두 만족하는 공식을 **확장형 로서 공식 (Extensional Rosser formula)**이라고 부릅니다. Hamkins 는 이러한 공식이 $\Pi^0_1$ 복잡도에서 존재할 수 있는지 물었습니다.

2. 주요 결과 (Key Results)

이 논문은 Hamkins 의 질문에 대해 다음과 같은 두 가지 상반된 결과를 도출합니다.

A. 부정적 결과: 확장형 로서 공식의 부재

• 명제: 확장성 (Extensionality) 과 독립성 (Independence) 을 동시에 만족하는 어떤 복잡도의 공식도 존재하지 않습니다.
• 증명 개요:
  • 고정점 정리 (Fixed Point Theorem) 를 사용하여 $\varphi_0 \leftrightarrow \rho(\ulcorner\varphi_0\urcorner)$와 $\varphi_1 \leftrightarrow \neg\rho(\ulcorner\varphi_1\urcorner)$인 문장들을 구성합니다.
  • 독립성에 의해 $PA \vdash \neg\varphi_0$ 및 $PA \vdash \neg\varphi_1$이 도출됩니다. 즉, $\varphi_0$와 $\varphi_1$은 모두 PA 에서 거짓 ($\bot$) 과 동치입니다.
  • 확장성에 의해 $\rho(\ulcorner\varphi_0\urcorner)$와 $\rho(\ulcorner\bot\urcorner)$가 동치이며, $\rho(\ulcorner\varphi_1\urcorner)$와 $\rho(\ulcorner\bot\urcorner)$가 동치여야 합니다.
  • 이를 고정점 방정식과 결합하면 $PA \vdash \rho(\ulcorner\bot\urcorner)$와 $PA \vdash \neg\rho(\ulcorner\bot\urcorner)$가 동시에 도출되어 PA 의 일관성에 모순이 발생합니다.
• 의미: Hamkins 가 요구한 '완전한 확장성'을 가진 $\Pi^0_1$ 공식은 존재할 수 없습니다.

B. 긍정적 결과: 조건부 확장성과 $\Pi^0_1$-유연성

• 조건부 확장성 (Conditional Extensionality) 도입:
  • 확장성을 약화시켜 다음과 같이 정의합니다: $PA \vdash \varphi \leftrightarrow \psi$라면, $PA + \varphi \vdash \rho(\ulcorner\varphi\urcorner) \leftrightarrow \rho(\ulcorner\psi\urcorner)$이다.
  • 즉, $\varphi$와 $\psi$가 동치일 때, $\varphi$가 가정된 이론 내에서만 $\rho$의 값이 동치임을 요구합니다.
• 주요 정리: 조건부 확장성을 만족하는 $\Pi^0_1$-유연한 (Flexible) 공식 $\rho(x)$가 존재합니다.
  • $\Pi^0_1$-유연성 ($\Pi^0_1$-Flexibility): $PA + \varphi$가 일관적이라면, 모든 $\Pi^0_1$ 문장 $\pi$에 대해 $PA + \varphi + (\rho(\ulcorner\varphi\urcorner) \leftrightarrow \pi)$는 일관적입니다.
  • 이는 독립성을 훨씬 더 강력한 형태로 강화한 것입니다 (단순히 참/거짓 중 하나를 선택하는 것을 넘어, 임의의 $\Pi^0_1$ 문장과 동치일 수 있음을 의미).

3. 방법론 (Methodology)

저자는 Shavrukov 와 Visser 의 이전 연구 [SV14] 및 Visser 의 [Vis21] 에 있는 기법을 변형하여 새로운 구성을 제시했습니다.

1. 균일한 증명 (Uniform Provability) 및 작은 증명 (Smallness):

   • 증명 길이에 따른 '작음 (Smallness)' 개념을 도입했습니다. $S_\varphi(x)$는 $x$ 이하의 모든 $\Sigma^0_1$ 문장 $\sigma$에 대해, $\varphi$가 $x$ 이하의 길이로 증명된다면 $\sigma$가 참임을 의미합니다.
   • 이는 외부 세계에서는 큰 수일지라도 내부 이론 ($U+\varphi$) 에서는 '작은' 수로 간주되는 'Outside-big-inside-small' 원리를 활용합니다.

2. 느린 증명 가능성 (Slow Provability):

   • $\triangle_\varphi \psi$를 정의합니다. 이는 $\varphi$-작은 (small) 공리들로부터 $\psi$가 증명될 수 있음을 의미합니다.
   • 이 $\triangle_\varphi$는 Fefermanian 증명 가능성 술어 (provability predicate) 의 일종으로, Lob 조건을 만족합니다.

3. 구성:

   • 최종적으로 $\rho(x)$를 $\triangle_x \top$ (즉, $x$가 일관적인지 여부에 대한 느린 증명 가능성) 으로 정의하거나 이와 유사한 형태로 구성합니다.
   • 이 구성은 고정점 (fixed-point) 을 사용하지 않는 (fixed-point-free) 방식으로 이루어지며, 이는 논리의 명확성을 보장합니다.

4. 논의 및 미해결 문제 (Discussion & Open Questions)

• 일관적 확장성 (Consistent Extensionality):
  • 논문의 가장 중요한 미해결 질문은 '일관적 확장성'의 경우입니다.
  • 정의: $PA \nvdash \neg\varphi$ (즉, $\varphi$가 일관적) 이고 $PA \vdash \varphi \leftrightarrow \psi$라면, $PA \vdash \rho(\ulcorner\varphi\urcorner) \leftrightarrow \rho(\ulcorner\psi\urcorner)$인가?
  • 이는 '완전한 확장성'과 '조건부 확장성' 사이의 중간 개념입니다. 저자는 이 문제가 여전히 열려 있으며, 이 문제가 해결되지 않으면 Hamkins 의 문제가 완전히 해결된 것으로 보기 어렵다고 명시했습니다.

5. 의의 (Significance)

1. 논리적 한계의 명확화: Hamkins 가 제기한 '완전한 확장성'을 가진 로서 공식의 불가능성을 증명함으로써, 논리 시스템 내에서 특정 성질들을 동시에 만족하는 데 본질적인 한계가 있음을 보였습니다.
2. 유연성 (Flexibility) 의 일반화: Kripke 가 도입한 유연성 개념을 확장하여, 조건부 확장성 하에서 $\Pi^0_1$-유연한 공식이 존재함을 보였습니다. 이는 로서 문장 (Rosser sentence) 의 성질을 더 강력한 형태로 일반화한 것입니다.
3. 새로운 증명 기법: '느린 증명 가능성 (Slow Provability)'과 '균일한 작은성 (Uniform Smallness)'을 결합한 기법은 incompleteness theorem 과 관련된 새로운 구성을 가능하게 하여, 향후 관련 분야 연구에 중요한 도구를 제공합니다.
4. 연구 방향 제시: '일관적 확장성'이라는 새로운 개념을 제시하고 이를 해결하기 위한 과제를 남김으로써, 향후 논리학 연구의 방향을 제시했습니다.

결론적으로, 이 논문은 Hamkins 의 원래 질문 (완전한 확장성) 에 대해서는 부정적인 답을 내렸지만, 조건부 확장성이라는 약화된 조건 하에서는 강력한 긍정적 결과 ($\Pi^0_1$-유연성) 를 도출하여 논리의 구조에 대한 심층적인 통찰을 제공했습니다.