로비어 정리: 칸토어, 러셀, 튜링, 타르스키, 괴델의 일반화

27 Oct 2026

수학

범주론

논리학

수리논리학을 공부한 독자라면 칸토어의 실수 비가산성 증명, 러셀의 집합론적 역설, 튜링의 정지 문제, 괴델의 불완전성 정리, 타르스키의 정의불가능성 정리가 서로 닮아 있다는 것을 한 번쯤 눈치챘을 것이다. 이들은 모두 어떤 대상을 그 자신에게 “먹이는” 대각선 논법_{diagonal argument}을 사용한다. 이 유사성은 범주론의 언어로 정확하게 정식화할 수 있다.

로비어 정리

정의. 범주 $\mathcal{C}$가 다음을 만족하면 $\mathcal{C}$를 데카르트 닫힌 범주_{Cartesian closed category}라고 한다.

$\mathcal{C}$는 종대상_{terminal object} $1$을 가진다.

$\mathcal{C}$는 유한 개의 대상들의 곱을 언제나 가진다.

모든 $B \in \mathcal{C}$에 대해, $(-) \times B : \mathcal{C} \to \mathcal{C}$는 오른쪽 수반_{right adjoint}을 가진다.

$(-) \times B$의 오른쪽 수반을 지수_exponential라 하고 $(-)^B$로 표기한다. 즉,

\[\hom(A \times B, C) \cong \hom(A, C^B)\]

가 $A, B, C$에 대해 자연스럽게 성립한다. 말하자면 데카르트 닫힌 범주는 커링_currying의 일반화이다. 별도의 언급이 없는 한, $\mathcal{C}$는 데카르트 닫힌 범주라고 가정하자.

정의. $A \in \mathcal{C}$의 대각사상_{diagonal map} $\Delta_A$를 다음 도식이 유도하는 유일한 사상으로 정의한다.

정의. $X \in \mathcal{C}$의 점_point은 사상 $1 \to X$이다.

점은 집합의 원소를 범주론적으로 일반화한 개념이다. 예를 들어 $\mathbf{Set}$에서 $\Delta_A: A \to A \times A$는 사상 $a \mapsto (a, a)$이다.

이를 이용해 전사성의 개념을 일반화할 수 있다.

정의. $f: X \to Y$가 점 전사적_{point surjective}이라는 것은, $Y$의 모든 점 $y$에 대해 $f\circ x = y$를 만족하는 $X$의 점 $x$가 존재한다는 것이다.

앞으로 $f \circ x = y$를 $f(x) = y$로도 쓰도록 한다.

다음 정리는 대각선 논법의 범주론적 일반화이다.

로비어 정리. $\mathcal{C}$가 데카르트 닫힌 범주라고 하자. $f: A \to B^A$가 점 전사적이면, 모든 $g: B \to B$에 대해 $g(b) = b$를 만족하는 $B$의 점 $b$가 존재한다.

증명. $\bar{f} : A \times A \to B$를 $f$의 수반이라 하고, $\phi: A \to B$를 $g \circ \bar{f} \circ \Delta_A$로 정의하자.

\[\hom(A, B) \cong \hom(1 \times A, B) \cong \hom(1, B^A)\]

이므로, $\bar{\phi} : 1 \to B^A$를 $\phi$의 수반이라 하자. $f$의 점 전사성에 의해 $f(a) = \bar{\phi}$를 만족하는 점 $a: 1 \to A$가 존재한다. 수반의 자연성에 의해 다음 도식이 가환한다.

\[\begin{CD} \hom(1\times A,\, B) @>{\overline{(-)}}>{\cong}> \hom(1,\, B^A) \\ @A{(-)\circ(a\,\times\,\mathrm{id}_A)}AA @AA{(-)\circ a}A \\ \hom(A\times A,\, B) @>{\cong}>{\overline{(-)}}> \hom(A,\, B^A) \end{CD}\]

$\bar f$를 위 사각형을 따라 옮기고, $1 \times A$를 $A$와 동일시하면 (이때 $a \times \mathrm{id}_A$는 $\langle a \circ \operatorname{!}_A, \mathrm{id}_A \rangle : A \to A \times A$가 된다) 다음을 얻는다.

\[\bar{f} \circ \langle a \circ \operatorname{!}_A, \mathrm{id}_A \rangle = \phi\]

그런데 $\langle a \circ \operatorname{!}_A, \mathrm{id}_A \rangle \circ a = \langle a, a \rangle = \Delta_A \circ a$이므로,

\[\begin{align} \bar{f} \circ \langle a \circ \operatorname{!}_A, \mathrm{id}_A \rangle \circ a &= \bar{f} \circ \Delta_A \circ a \\ &= \phi \circ a \end{align}\]

이다. $b := \bar f \circ \Delta_A \circ a$라 하면 다음 도식이 가환한다.

특히 $g(b) = g \circ \bar f \circ \Delta_A \circ a = \phi(a) = \bar f \circ \Delta_A \circ a = b$이다. ■

칸토어와 러셀

따름정리 (칸토어). $\mathbf{Set}$에서 (점) 전사인 사상 $f: A \to 2^A$는 존재하지 않는다.

증명. 그렇지 않다고 가정하자. 그러면 로비어의 정리에 의해 모든 사상 $2 \to 2$가 고정점을 가진다. 그러나 $0 \mapsto 1, 1 \mapsto 0$은 고정점을 갖지 않는다. ■

따름정리 (러셀). 소박한 내포 공리_{axiom of naive comprehension}는 모순이다.

증명. 소박한 내포 공리를 가정하고, 이 공리가 만들어내는 집합들이 $\mathbf{Set}$에서처럼 데카르트 닫힌 범주를 이룬다고 하자. 그러면 $\phi(x): x = x$는 모든 집합의 집합 $S$를 정의하며, $2^S$는 $S$ 위의 모든 명제들의 집합이다. 다음 사상을 생각하자.

\[f : S \to 2^S, \qquad x \mapsto (y \mapsto [y \in x]).\]

소박한 내포 공리에 의해 모든 $P \in 2^S$는 집합 ${y : P(y)}$를 결정하므로, $f$는 (점) 전사적이다. 이는 $0 \mapsto 1, 1 \mapsto 0$에 대해 로비어의 정리와 모순이다. (증명을 풀어 보면, 점 $a$는 바로 집합 ${x : x \notin x}$이다.) ■

약한 점 전사성

$\mathcal{C}_{\mathsf{PA}}$를 다음과 같은 결정가능 집합의 범주라 하자.

대상: PA에서 증명가능한 동치 관계로 나눈 $\mathbb{N}$의 결정가능 부분집합.
사상: PA가 전역적_total임을 증명하는 함수 (PA에서 증명가능한 동치 관계로 나눈 것).

그러면 $1 = {0}$은 종대상이고,

\[\begin{gather} A \times B = \{ \langle a, b \rangle : a \in A, b \in B \} \\ \pi_1 : \langle a, b \rangle \mapsto a, \quad \pi_2 : \langle a, b \rangle \mapsto b \end{gather}\]

는 곱이다. 여기서 $\langle \cdot, \cdot \rangle$은 순서쌍의 코드이다.

다음 보조정리를 증명하자.

보조정리. $\mathsf{PA}$가 무모순이면, $\mathcal{C}_\mathsf{PA}$는 데카르트 닫힌 범주가 아니다.

보조정리의 증명. 그렇지 않다고 가정하자. 그러면 $2^\mathbb{N}$의 점은 전역성이 증명가능한 함수 $\mathbb{N} \to 2$의 수반이다. 특히 $2^\mathbb{N}$은 상수함수 $0$의 수반인 점 $e_0$를 가진다. $2^\mathbb{N}$은 $\mathcal{C}_\mathsf{PA}$의 대상이므로 결정가능 부분집합 $E \subseteq \mathbb{N}$이고, 포함사상 $i : E \to \mathbb{N}$을 가진다.

$\Theta: \mathbb{N} \to 2^\mathbb{N}$를 다음과 같이 정의하자.

\[\Theta(n) = \begin{cases} n &n \in E \\ e_0 &\text{그 외} \end{cases}\]

그러면 $\Theta$는 사상이고 ($E$가 결정가능하므로 전역성이 증명가능하다), $\Theta \circ i = \mathrm{id}_E$이다. 따라서 $2^\mathbb{N}$의 모든 점 $p$에 대해 $\Theta(i \circ p) = p$이므로, $\Theta$는 점 전사적이다. 그러므로 로비어의 정리에 의해 모든 사상 $h: 2 \to 2$는 고정점을 가진다. 그런데 그렇다면 $0 \mapsto 1, 1 \mapsto 0$ 역시 고정점을 가지게 되고, 이로부터 $\mathsf{PA} \vdash 0 = 1$이 따라 나온다. □

따라서 위에서 진술한 형태의 로비어의 정리는, 계산과 산술이 사는 범주에서는 써먹을 수가 없다. 다행히도 로비어의 정리의 증명은 지수를 실제로 사용하지 않는다. 지수는 “모든 $g$가 코드를 가진다”는 사실을 하나의 사상 $f : A \to B^A$로 포장해줄 뿐이다. 지수를 걷어내면 다음을 얻는다.

정의. $\mathcal{C}$가 유한곱을 가진다고 하자. 사상 $\phi : A \times A \to B$가 약하게 점 전사적_{weakly point surjective}이라는 것은, 모든 $h : A \to B$에 대해 $A$의 모든 점 $x$에서 $\phi(\langle a, x \rangle) = h(x)$를 만족하는 $A$의 점 $a$가 존재한다는 것이다.

로비어 정리 (유한곱). $\mathcal{C}$가 유한곱을 가지는 범주라고 하자. $\phi : A \times A \to B$가 약하게 점 전사적이면, 모든 $g : B \to B$에 대해 $g(b) = b$를 만족하는 $B$의 점 $b$가 존재한다.

증명. $h := g \circ \phi \circ \Delta_A$라 하자. 정의에서처럼 $a$를 고르고, $b := \phi \circ \langle a, a \rangle$라 하면

\[b = \phi(\langle a, a \rangle) = h(a) = g \circ \phi \circ \Delta_A \circ a = g(b). \quad ■\]

원 로비어 정리는 $\phi = \bar f$인 특수한 경우이다.

튜링, 타르스키, 괴델

따름정리 (튜링). 정지 문제는 결정불가능하다.

증명. $\mathbf{Rec}$을 대상이 $\mathbb{N}$의 결정가능 부분집합이고, 사상이 전역 계산가능 함수인 범주라 하자. (이때 전역성이 증명가능할 필요는 없다.) 결정가능 부분집합과 그에 대응하는 결정 프로그램은 동일시하겠다. $\mathcal{C}_\mathsf{PA}$에서와 마찬가지로 $\mathbf{Rec}$은 순서쌍 코드를 통해 유한곱을 가지며, $1 = {0}$, $2 = {0, 1}$이다.

정지 문제가 결정가능하다고 가정하자. 즉, 프로그램 $e$가 입력 $n$에서 정지하면 $h(e, n) = 1$, 그렇지 않으면 $h(e, n) = 0$인 사상 $h : \mathbb{N} \times \mathbb{N} \to 2$가 존재한다고 하자. 사상 $f: \mathbb{N} \to 2$에 대해, $e_f$를 다음 프로그램이라 하자.

on input n:
  if f(n) = 1: return
  else: infinite loop

그러면 모든 $n$에 대해 $h(e_f, n) = f(n)$이므로 $h$는 약하게 점 전사적이다. 로비어의 정리에 의해 $0 \mapsto 1, 1 \mapsto 0$이 고정점을 가지게 되어 모순이다. ■

따름정리 (타르스키). 모든 문장 $\sigma$에 대해
\[\mathbb{N} \models \mathrm{True}(\ulcorner \sigma \urcorner) \iff \mathbb{N} \models \sigma\]
를 만족하는 논리식 $\mathrm{True}(x)$는 존재하지 않는다.

증명. 자유변수가 하나인 논리식들의 괴델 번호 매김_{Gödel numbering} $\psi_0, \psi_1, \dots$을 고정하자. $\mathbf{Def}$를 대상이 $\mathbb{N}^k \; (k = 0, 1, 2, …)$와 $2$이고, 사상이 표준 산술에서 정의가능한 함수인 범주라 하자.

$\mathrm{True}$가 존재한다고 가정하자. 대입 함수 $\mathrm{sub}(m, n) = \ulcorner \psi_m(\bar n) \urcorner$는 계산가능하므로 정의가능하다. 따라서

\[\phi(m, n) := [\mathbb{N} \models \psi_m(\bar n)] = \chi_{\mathrm{True}}(\mathrm{sub}(m, n))\]

는 $\mathbf{Def}$의 사상이다. 이 사상은 약하게 점 전사적이다. $g : \mathbb{N} \to 2$가 논리식 $\gamma(x, y)$로 정의된다면, $\psi(x) := \gamma(x, 1)$은 $\phi(\ulcorner \psi \urcorner, n) = g(n)$을 만족하기 때문이다. 그런데 $0 \mapsto 1, 1 \mapsto 0$은 정의가능하며 고정점을 갖지 않으므로, 이는 로비어의 정리와 모순이다. ■

괴델의 정리를 위해, 로빈슨 산술_{Robinson arithmetic} $\mathsf{Q}$에 관한 다음 사실을 떠올리자.

모든 결정가능 집합 $D \subseteq \mathbb{N}$에 대해, $n \in D \Rightarrow \mathsf{Q} \vdash \psi_D(\bar n)$이고 $n \notin D \Rightarrow \mathsf{Q} \vdash \neg\psi_D(\bar n)$을 만족하는 논리식 $\psi_D(x)$가 존재한다.

따름정리 (괴델). $\mathsf{Q}$를 포함하는 무모순이고 재귀적으로 열거가능한 산술의 공리화 $T$에 대해, $T$에서 증명불가능한 산술적 참이 존재한다.

증명. 다음 보조정리를 증명하자.

보조정리. $T$가 $\mathsf{Q}$의 무모순인 확장이면, $T$의 정리들의 집합은 결정불가능하다.

증명. 결정가능하다고 가정하고 $\mathbf{Rec}$에서 논의하자. 다음과 같이 정의한다.

\[\phi(m, n) = \begin{cases} 1 & T \vdash \psi_m(\bar n) \\ 0 & \text{그 외} \end{cases}\]

$\mathrm{sub}$가 계산가능하고 $T$가 결정가능하므로 $\phi$는 계산가능하다. 또한 $\phi$는 약하게 점 전사적이다. 계산가능한 $g : \mathbb{N} \to 2$가 주어졌을 때 $D = g^{-1}(1)$이라 하면 다음이 성립하기 때문이다.

$g(n) = 1$이면 $T \vdash \psi_D(\bar n)$이므로 $\phi(\ulcorner \psi_D \urcorner, n) = 1$이다.
$g(n) = 0$이면 $T \vdash \neg\psi_D(\bar n)$이므로, 무모순성에 의해 $T \nvdash \psi_D(\bar n)$이고 $\phi(\ulcorner \psi_D \urcorner, n) = 0$이다.

로비어의 정리에 의해 $0 \mapsto 1, 1 \mapsto 0$이 고정점을 가지게 되어 모순이다. □

이제 $T$가 완전하다고 가정하자. 그러면 다음 절차는 전역적이고, 따라서 $T$는 결정가능해진다.

for n in ℕ:
  if n is a proof of φ:
    return True
  if n is a proof of ¬φ:
    return False

이는 위의 보조정리와 모순이다. ■

몇 가지 덧붙이자면:

이 논증은 $\omega$-무모순성이 아니라 무모순성만을 사용하므로, 괴델–로서_{Gödel–Rosser} 정리와 같은 강도를 가진다.
증명을 풀어 보면, 점 $a$는 $n \mapsto [T \nvdash \psi_n(\bar n)]$을 표현하는 논리식의 코드이다. 따라서 $\psi_a(\bar a)$는 괴델 문장, 즉 “나는 증명가능하지 않다”라고 말하는 문장이다.

디멘의 블로그 Jeongdam's Blog

로비어 정리: 칸토어, 러셀, 튜링, 타르스키, 괴델의 일반화

로비어 정리

칸토어와 러셀

약한 점 전사성

튜링, 타르스키, 괴델