V = L 공리의 무모순성

11 Dec 2024

1. 전체

1.1. 폰 노이만 전체

초한귀납적으로 $\lbrace V_\alpha \rbrace$를 정의하자.

• $V_0 = \varnothing$
• $V_{\alpha + 1} = V_\alpha \cup \mathcal{P}(V_\alpha)$
• $\lambda$가 극한 서수일 때, $V_\lambda = \bigcup_{\alpha < \lambda} V_\alpha$

처음 몇 개의 $V_\alpha$는 다음과 같다.

• $V_1 = \lbrace \varnothing \rbrace$
• $V_2 = \lbrace \varnothing, \lbrace \varnothing \rbrace \rbrace$
• $V_3 = \lbrace \varnothing, \lbrace \varnothing \rbrace, \lbrace \lbrace \varnothing \rbrace \rbrace, \lbrace \varnothing, \lbrace \lbrace \varnothing\rbrace \rbrace \rbrace$
• $V_\omega = \mathsf{HF}$

모든 서수 $\alpha$에 대해 $V_\alpha$를 모아둔 모임을 폰 노이만 전체라고 한다.

\[V = \bigcup_{\alpha \in \mathrm{Ord}} V_\alpha\]

$x \in y \in z$가 $x \in z$를 시사할 때 $z$를 추이적 집합(transitive set)이라고 한다. 이것은 $V$의 중요한 특징이다.

정리.

1. $\alpha \in \mathrm{Ord}$에 대해 $V_\alpha$는 추이적이다.
2. $V$는 추이적이다.

증명은 초한귀납법을 이용한다. 이에 따라 $V$를 다음과 같이 정의해도 무방하다.

• $V_0 = \varnothing$
• $V_{\alpha + 1} = \mathcal{P}(V_\alpha)$
• $\lambda$가 극한 서수일 때, $V_\lambda = \bigcup_{\alpha < \lambda}V_\alpha$

직관적으로 생각했을 때 $V$는 모든 집합을 포함하는 듯하다. 실제로 다음을 증명할 수 있다.

정리. $x$가 집합이라면 $x \in V$이다.

증명. 집합 $x$에 대해 $x$의 추이적 폐포 $\bar{x}$를, $x$를 원소로 가지는 가장 작은 추이적 집합으로 정의한다(추이적 집합들의 교집합은 추이적이기 때문에 이 정의는 정당하다).

$x \notin V$라고 가정하자. 분류 공리에 의해 $y = \lbrace u \in \bar{x} : u \notin V \rbrace$가 집합이며, 정초 공리에 의해 $y$의 $\in$-극소 원소 $z$가 존재한다. 만약 $w \notin V$인 $w \in z$가 존재한다면, 추이성에 의해 $w \in y$가 되어 $z$의 $\in$-극소성과 모순된다. 따라서 $z$의 모든 원소는 $V$에 있으며, 치환 공리로부터 $\Omega = \lbrace \alpha \in \mathrm{Ord} \mid \exists w \in z : w \in V_\alpha\rbrace$가 집합이다. 부랄리포르티 정리에 의해 $\beta = \bigcup_{\alpha \in \Omega}\alpha$가 서수이며, $z \in V_{\beta + 1}$이다. (이 부분에서 $V_{\beta + 1} = \mathcal{P}(V_\beta)$임이 필요하다) 따라서 모순이다. ■

이에 따라 $V$는 집합이 아니다. 따라서 $V$는 모든 집합을 포함한다는 점에서 ZFC의 모델이지만, 많은 수학자들은 모델이 집합일 것을 요구하기 때문에 엄격한 의미에서의 모델은 아니다. 하지만 이 글에서는 편의를 위해 $V$를 집합론의 모델이라고 부르도록 한다. 또한 $x \in V$를 “$x$는 집합이다“의 형식적 표현으로 이해하도록 한다.

1.2. 괴델 구성 가능 전체

먼저 다음과 같이 구성 가능성을 정의한다.

정의. $u$가 집합 $S$로부터 구성 가능하다는 것은, 어떤 1차 논리 명제 $\phi(y, x_1, \dots, x_n)$와 $c_1, \dots, c_n \in S$가 존재하여 다음이 성립하는 것이다.

\[y \in u \iff y \in S \land \phi(y, c_1, \dots, c_n)\]

단, $\phi$의 양화사의 정의역은 $S$이다.

예를 들어 $S = \lbrace 0, 1, 2\rbrace$일 때 다음은 $u = \lbrace 1, 2 \rbrace$를 구성한다.

• $\phi(y, x_1, x_2) := (y = x_1) \lor (y = x_2)$
• $c_1 = 1, c_2 = 2$

또한 $S = \mathbb{N}$일 때 다음은 $u = \lbrace 0, 3, 6, 9, \dots \rbrace$를 구성한다.

• $\phi(y, x_1) := x_1 \mid y$
• $c_1 = 3$

괴델의 구성가능성은 일반적인 의미에서의 구성가능성, 즉 언어로서의 표현가능성과 다르다. 일례로 언어로 표현가능한 실수의 집합은 가산이므로, 어떤 실수는 언어로 표현이 불가능하다. 그러한 실수를 $r$이라고 하자. 이제 $S = \mathbb{R}$일 때, 다음은 $u = \lbrace r \rbrace$을 구성한다.

• $\phi(y, x_1) := x_1 = y$
• $c_1 = r$

즉, 괴델의 구성가능성은 자유변수의 초기화를 임의의 원소에 대해 허용한다는 점에서 강력하다. 그러나 자유변수의 수가 유한하다는 점에서 한계를 가진다. 이제 초한귀납적으로 $\lbrace L_\alpha \rbrace$를 정의하자.

• $L_0 = \varnothing$
• $L_{\alpha + 1} = \lbrace x : x \text{ is constructible from } L_\alpha \rbrace$
• $\lambda$가 극한 서수일 때, $L_\lambda = \bigcup_{\alpha < \lambda} L_\alpha$
• $L = \bigcup_{\alpha < \lambda} L_\alpha$

$\alpha < \omega$일 때 $L_\alpha = V_\alpha$임을 쉽게 보일 수 있다. $\alpha = n$일 때, 최대 $n$개의 $\lor$ 연언으로 $x \in V_\alpha$를 구성할 수 있기 때문이다. 따라서,

• $L_1 = \lbrace \varnothing \rbrace$
• $L_2 = \lbrace \varnothing, \lbrace \varnothing \rbrace \rbrace$
• $L_3 = \lbrace \varnothing, \lbrace \varnothing \rbrace, \lbrace \lbrace \varnothing \rbrace \rbrace, \lbrace \varnothing, \lbrace \lbrace \varnothing\rbrace \rbrace \rbrace$
• $L_\omega = \mathsf{HF}$

하지만 $L_{\omega + 1} \subsetneq V_{\omega + 1}$이다. $\mathcal{P}(\mathbb{N}) \subset V_{\omega + 1}$이므로 $V_{\omega + 1}$은 비가산인 반면, 1차 논리 문장들의 집합과 $L_\omega$는 모두 가산이므로 $L_{\omega + 1}$ 또한 가산이기 때문이다. 일반적으로 $\alpha$가 가산일 때 $L_\alpha$는 가산이다.

그럼에도 $L$은 $V$와 많은 특징을 공유한다. 일례로,

정리. $\alpha \in \mathrm{Ord}$에 대해 다음이 성립한다.

1. $L_\alpha$는 추이적이다. (따라서 $L$이 추이적이다)
2. $\alpha \in L_{\alpha + 1} \setminus L_{\alpha}$

증명은 초한귀납법을 사용한다.

$L$은 모든 서수를 포함하므로 부랄리포르티 정리에 의해 집합이 아님에 유의하라. 대신 $x \in L_\alpha$에 대응되는 1차 논리식 $\mathsf{IsInL}_\alpha(x)$가 존재한다. 증명은 조금 까다로운데, 괴델 수를 이용하여 명제를 산술화하면 된다. (링크 참조) 따라서 $x \in L$을 $\exists \alpha \in \mathrm{Ord} :\mathsf{IsInL}_\alpha(x)$를 대체하는 형식적 표현으로 이해하여 사용하도록 한다. (물론 $\alpha \in \mathrm{Ord}$ 또한 1차 논리식을 대체하는 형식적 표현으로 이해되어야 한다)

2. 상대화

2.1. 명제의 상대화

1차 논리 명제는 양화사를 포함할 수 있다. 때문에 양화사의 정의역을 어떻게 설정하느냐의 따라 명제의 의미가 달라진다.

명제 $\phi$와 집합 (또는 모임) $A$에 대해, $\phi$의 상대화 $\phi^A$를 $\phi$의 모든 양화사를 $A$로 제한한 명제로 정의한다. 약간의 서사적 표현을 곁들이자면, $\phi^A$는 $A$의 “내부”에서 이해한 $\phi$라고 할 수 있겠다. 예를 들어, $\phi : \forall x \; \exists y : y < x$일 때

• $\phi^\mathbb{N} : \forall x \in \mathbb{N} \; \exists y \in \mathbb{N} : y < x$
• $\phi^\mathbb{Z} : \forall x \in \mathbb{Z} \; \exists y \in \mathbb{Z} : y < x$

$T_\mathbb{Q}$가 자연수 및 정수를 특정할 수 있는 정도의 표현력을 지니는 유리수 이론이라고 하면,

• $T_\mathbb{Q} \vdash \phi$
• $T_\mathbb{Q} \not\vdash \phi^\mathbb{N}$
• $T_\mathbb{Q} \vdash \phi^{\mathbb{Z}}$

이다. 따라서 $\phi$는 자연수와 유리수를 성공적으로 구분해 내지만, 정수와 유리수는 구분해 내지 못한다. 이 관찰을 일반화하면, 이론 $T$와 집합 $A$에 대해 $T \vdash \phi \leftrightarrow \phi^A$인 $\phi$가 많으면 많을수록 $A$는 $T$의 기술에 잘 “부합한다“고 말할 수 있다.

위 논의를 조금 일반화하여, 다음과 같이 정의한다.

정의. 이론 $T$와 집합 $A$에 대해서

\[T \vdash \forall x_1, \dots, x_n \in A (\phi(x_1, \dots, x_n) \leftrightarrow \phi^A(x_1, \dots, x_n))\]

일 때, $\phi$는 $A$에 대해 절대적(absolute)이라고 한다.

일례로 $T_\mathbb{Q}$에 대해 $\phi(x) : \exists y (y < x)$는 정수에 대해 절대적이지만 자연수에 대해 절대적이지는 않다.

2.2. $L$-상대화

이제 우리의 목표는 $L$이 $\mathsf{ZF}$와 극대적으로 부합함을 보이는 것이다. 즉,

정리 1. $\phi$가 ZF의 공리라면 $\mathsf{ZF} \vdash \phi^L$이다.

정리 1의 의미를 말로 풀어 보자면,

“$L$의 내부에서 보았을 때 $L$은 ZF의 모델이다”를 ZF로 증명할 수 있다.

물론 우리는 $L \subset V$만 알고 $V = L$인지는 알지 못하기 때문에, 어떤 집합 $x$는 $L$에 속하지 않을 수도 있다. 그러나 설령 $x \in V \setminus L$인 집합 $x$가 있더라도, 그러한 $x$의 결여는 $L$의 내적 정합성을 깨뜨리지 않는다는 것이 정리 1의 내용이다.

예를 들어 어떤 집합 $y, z$에 대해 $x = \lbrace y, z \rbrace$가 $L$에 결여되어 있다고 하자. 일면 $x$의 결여는 $L$이 짝 공리 $\mathsf{Pair}$을 만족하지 않음을 시사하는 듯하다.

\[\mathsf{Pair} := \forall y, z \; \exists x \; \forall w: w \in x \leftrightarrow (w = y \lor w = z)\]

하지만 $L$의 내부에서 본 짝 공리는 다음과 같다.

\[\mathsf{Pair}^L := \forall y, z \in L \; \exists x \in L \; \forall w \in L: w \in x \leftrightarrow (w = y \lor w = z)\]

$\forall y, z$의 양화 또한 $L$로 한정됨에 주목하라. 즉, $x = \lbrace y, z \rbrace$의 결여가 $L$에게 문제를 일으키는 경우는 $y, z \in L$일 때이다. 거꾸로 말해, $x = \lbrace y, z \rbrace \notin L$이 $y, z \notin L$을 시사한다면 $L$은 $\mathsf{Pair}^L$을 만족한다. 이것이 “$L$이 내적 정합성을 유지하는 방식으로 집합을 결여한다”의 의미이다.

정리 1이 성립하는 핵심 이유는 $L$과 $V$가 추이성이라는 성질을 공유하기 때문이다.

보조정리. 다음 술어는 ZF에서 $L$에 대해 절대적이다.

1. $x \in y$
2. $x \subset y$
3. $x = \bigcup y$
4. $x = \lbrace y, z \rbrace$
5. $\alpha \in \mathrm{Ord}$
6. $x$는 추이적이다.
7. $\Delta_0$ 논리식

또한 다음을 증명할 수 있다.

정리 2. $\mathsf{ZF} \vdash (V = L)^L$

여기서 $V = L$은, “모든 집합이 $L$에 속한다”를 의미한다. 따라서 일면 보기에 $(V = L)^L$은 “$L$에 속하는 모든 집합이 $L$에 속한다”라는 자명한 명제인 듯하다. 하지만 실제로 $V = L$을 논리식으로 적으면

\[\forall x \; \exists \alpha : \alpha \in \mathrm{Ord} \land x \in L_\alpha\]

이므로 $(V = L)^L$은

\[\forall x \in L \; \exists \alpha \in L : (\alpha \in \mathrm{Ord})^L \land (x \in L_\alpha)^L\]

이다. 특히, $\alpha \in \mathrm{Ord}$와 $x \in L_\alpha$가 진정한 의미에서의 $\in$-술어가 아닌 1차 논리식의 형식적 표현이기 때문에 마찬가지로 $L$로 상대화해야 함에 유의하라. 이에 따라 $(V = L)^L$을 ZF에서 증명하기 위해서는 $\alpha \in \mathsf{Ord}$와 $x \in L_\alpha$가 절대적임을 증명해야 한다. 두 증명 모두 초한귀납법을 사용하면 가능하다.

정리 1과 정리 2로부터 다음을 증명할 수 있다.

정리 3. $\mathsf{ZFL} \vdash \phi \implies \mathsf{ZF} \vdash \phi^L$

증명. $\mathsf{ZFL} \vdash \phi$의 증명 길이에 대한 귀납법으로 증명한다. 증명 길이가 0일 때 $\phi$는 ZFL의 공리이다. $\phi$가 ZF의 공리일 때 정리 1로부터 증명되고, $\phi$가 $V = L$일 때 정리 2로부터 증명된다.

이제 $\phi$가 $\lbrace \psi_1, \dots, \psi_n \rbrace$에 추론 규칙을 적용하는 것으로 증명된다고 가정하자. $\psi_k$의 증명 길이는 $\phi$보다 작으므로 귀납 가정에 의해 $\mathsf{ZF} \vdash \psi_k^L$이며, 논리 공리와 추론 규칙은 $L$에 대해 절대적임을 쉽게 보일 수 있다. 따라서 $(\psi_1 \land \dots \land \psi_n) \rightarrow \phi$가 논리적 참이라면 $(\psi_1^L \land \dots \land \psi_n^L) → \phi^L$ 또한 논리적 참이며, 이에 따라 $\mathsf{ZF} \vdash \phi^L$이다. ■

정리 3의 따름정리로서 정리 4를 얻는다.

정리 4. ZF가 무모순적이라면 ZFL 또한 무모순적이다.

증명. ZFL이 모순적이라면 $\mathsf{ZFL} \vdash \varnothing \neq \varnothing$이며, 정리 3에 의해 $\mathsf{ZF} \vdash (\varnothing \neq \varnothing)^L \iff \mathsf{ZF} \vdash \varnothing \neq \varnothing$이다.

따라서 V = L은 ZF와 일관적이다.