장 92 내부 모형 이론

모형 이론은 정말로 메타적이므로, 여기서는 주의를 기울여야 합니다.

대략적으로 말하면, 군이 군 공리를 만족하는 이항 연산을 갖춘 집합인 것과 마찬가지로, “ $\mathsf{ZFC}$ 의 모형”은 $\mathsf{ZFC}$ 공리를 만족하는 이항 관계를 갖춘 집합입니다. 안타깝게도 군의 경우와 달리 흥미로운 모형의 예를 제시하기는 매우 어려운데, 그 이유는 간단합니다. 우리는 말 그대로 우주 전체를 모형화하려 하고 있기 때문입니다.

92.1 모형

대표적인 예: $(\omega,\in)$ 는 $\mathrm{PowerSet}$ 을 만족하며, $\kappa$ 가 도달 불가능할 때 $V_{\kappa}$ 는 모형입니다(나중에 다룹니다).

정의 92.1.1.

모형 $\mathscr{M}$ 은 집합 $M$ 과 이항 관계 $E\subseteq M\times M$ 으로 이루어집니다. ( $E$ 관계는 모형에서의 “ $\in$ ”입니다.)

비고 92.1.2.

여기서는 $M$ 이 집합인 집합 크기의 모형만을 고려합니다. 전문가라면 $M$ 이 클래스인 경우도 다룰 수 있다는 것을 알고 있겠지만, 지금으로서는 그렇게 하려면 너무 많은 주의가 필요합니다.

모형이 있으면 그 모형에 대해 “ $\mathrm{EmptySet}$ 을 만족하는가?”와 같은 것들을 물어볼 수 있습니다. 제가 의미하는 바의 예를 먼저 보여 드린 다음 이를 엄밀하게 만들겠습니다.

예제 92.1.3 (어리석은 모형).

$\mathscr{M}=(M,E)=\left(\omega,\in\right)$ 로 둡시다. 이것은 $\mathsf{ZFC}$ 의 그다지 좋은 모형은 아니지만, 처음 몇 개의 공리를 이해할 수 있는지 살펴봅시다.

(a)

$\mathscr{M}$ 은 $\mathrm{Extensionality}$ 를 만족하며, 이는 다음 문장입니다

$\forall x\forall y\forall a:\left(a\in x\iff a\in y\right)\implies x=y.$

이는 단지 $E$ 가 실제로 $\in$ 이라는 사실로부터 따라 나옵니다.
(b)

$\mathscr{M}$ 은 $\mathrm{EmptySet}$ 을 만족하며, 이는 다음 문장입니다

$\exists a:\forall x\;\neg(x\in a).$

즉, $a=\varnothing\in\omega$ 로 두면 됩니다.
(c)

$1,3\in\omega$ 임에도 $\{1,3\}$ 은 $\omega$ 에 속하지 않으므로, $\mathscr{M}$ 은 $\mathrm{Pairing}$ 을 만족하지 않습니다.
(d)

놀랍게도, 임의의 $n\in\omega$ 에 대해 $\cup n$ 은 ( $n=0$ 인 경우를 제외하면) $n-1$ 이므로 $\mathscr{M}$ 은 $\mathrm{Union}$ 을 만족합니다. 합집합 공리는 다음과 같이 서술합니다

$\forall a\exists U\quad\forall x\;\left[(x\in U)\iff(\exists y:x\in y\in a)% \right].$

주목해야 할 중요한 점은 “ $\forall a$ ”가 우주의 모형 $\mathscr{M}$ 에 있는 집합들만을 범위로 한다는 것입니다.

예제 92.1.4 (중요: 이 어리석은 모형은 $\mathrm{PowerSet}$ 을 만족합니다).

무엇보다도 가장 놀라운 것은 $\mathscr{M}=(\omega,\in)$ 이 $\mathrm{PowerSet}$ 을 만족한다는 것입니다. 이것은 정말로 중요한 예입니다.

이것이 터무니없다고 생각할 수도 있습니다. $2=\{0,1\}$ 을 보십시오. 이것의 멱집합은 $\{0,1,2,\{1\}\}$ 이고, 이는 모형에 속하지 않습니다. 그렇지 않습니까?

그러면 $\mathrm{PowerSet}$ 을 좀 더 자세히 살펴봅시다. 이 공리는 다음과 같이 서술합니다:

\forall x\exists a\forall y(y\in a\iff y\subseteq x).

$x=2=\{0,1\}$ 로 두면 어떻게 될까요? 사실, 우리는 $a=3=\{0,1,2\}$ 가 조건을 충족한다고 주장합니다. 핵심은 “모든 $y$ 에 대하여”입니다. 이것은 $\mathscr{M}$ 에 있는 대상들만을 범위로 합니다. $\mathscr{M}$ 에서 $2$ 의 부분집합은 $0=\varnothing$ , $1=\{0\}$ , $2=\{0,1\}$ 뿐입니다. “현실 세계”( $V$ )에서의 “집합” $\{1\}$ 은 모형 $\mathscr{M}$ 에서는 집합이 아닙니다.

특히, $n=\{0,1,\dots,n-1\}$ 은 실제로 부분집합을 $n+1$ 개만 가지므로, 이 이상한 새로운 세계에서는 $2^{n}=n+1$ 이 성립한다고 말할 수도 있습니다.

예제 92.1.5 (매개변수가 있는 문장).

모형에 묻는 문장에는 “매개변수”가 있어도 됩니다. 예를 들어, 앞에서와 같이 $\mathscr{M}=(\omega,\in)$ 이면 $\mathscr{M}$ 은 다음 문장을 만족합니다

\forall x\in 3(x\in 5).

92.2 문장과 만족

이 직관적인 개념을 바탕으로, 모형이 문장을 만족한다는 것이 무엇을 의미하는지 정의할 수 있습니다.

정의 92.2.1.

모든 문장 $\phi$ 는 다음 다섯 가지 형태 중 하나로 쓸 수 있다는 점에 유의하십시오.

•

$x\in y$
•

$x=y$
•

더 짧은 어떤 문장 $\psi$ 에 대하여 $\neg\psi$ (“ $\psi$ 가 아님”)
•

더 짧은 어떤 문장 $\psi_{1}$ , $\psi_{2}$ 에 대하여 $\psi_{1}\lor\psi_{2}$ (“ $\psi_{1}$ 또는 $\psi_{2}$ ”)
•

더 짧은 어떤 문장 $\psi$ 에 대하여 $\exists x\psi$ (“ $x$ 가 존재함”).

질문 92.2.2.

$\land$ (그리고)와 $\forall$ (모든)은 어떻게 되었습니까? (힌트: $\neg$ 를 사용하십시오.)

우리는 종종(사실은 거의 항상) 이른바 “논리식 복잡도에 대한 귀납법”으로 논의를 진행할 것입니다. 이는 이 사실을 이용한 귀납법으로 무언가를 정의하거나 증명한다는 뜻입니다. 모든 논리식은 유한해야 한다는 점에 유의하십시오.

이제 $a=b$ 나 $\exists a\forall x\neg(x\in a)$ 와 같은 문장 $\phi$ 와 모형 $\mathscr{M}=(M,E)$ 가 주어졌다고 합시다. 우리는 $\mathscr{M}$ 이 $\phi$ 를 만족하는지 묻고자 합니다.

이 물음에 의미를 부여하려면 특정 변수들을 매개변수로 지정해야 합니다. 예를 들어 제가 여러분에게

“ $a=b$ 입니까?”

라고 묻는다면, 여러분이 가장 먼저 던질 질문은 $a$ 와 $b$ 가 무엇이냐는 것입니다. 따라서 $a$ , $b$ 는 매개변수가 됩니다. 이 문장이 의미를 가지려면 제가 이들에게 값을 주어야 합니다.

반면에 제가 여러분에게

“ $\exists a\forall x\neg(x\in a)$ 입니까?”

라고 묻는다면, 여러분은 그냥 “예”라고 답할 것입니다. 이 경우 $x$ 와 $a$ 는 매개변수가 아닙니다. 일반적으로 매개변수란 그 의미가 어떤 $\forall$ 이나 $\exists$ 에 의해 주어지지 않는 변수를 말합니다.

이하에서는 매개변수가 $x_{1}$ , …, $x_{n}$ 인 논리식 $\phi$ 를 $\phi(x_{1},\dots,x_{n})$ 으로 나타내겠습니다. $n=0$ 일 수도 있다는 점에 유의하십시오. 예를 들어 모든 $\mathsf{ZFC}$ 공리에는 매개변수가 없습니다.

질문 92.2.3.

아래의 정의를 읽기 전에 만족의 정의를 추측해 보십시오. (추측하기가 그리 어렵지 않습니다!)

정의 92.2.4.

$\mathscr{M}=(M,E)$ 를 모형이라 합시다. $\phi(x_{1},\dots,x_{n})$ 을 문장이라 하고, $b_{1},\dots,b_{n}\in M$ 이라 합시다. 우리는 관계

\mathscr{M}\vDash\phi[b_{1},\dots,b_{n}]

를 정의하고, $\mathscr{M}$ 이 매개변수 $b_{1},\dots,b_{n}$ 을 갖는 문장 $\phi$ 를 만족한다고 말할 것입니다.

이 관계는 논리식 복잡도에 대한 귀납법으로 다음과 같이 정의됩니다.

•

$\phi$ 가 “ $x_{1}=x_{2}$ ”이면 $\mathscr{M}\vDash\phi[b_{1},b_{2}]\iff b_{1}=b_{2}$ 입니다.
•

$\phi$ 가 “ $x_{1}\in x_{2}$ ”이면 $\mathscr{M}\vDash\phi[b_{1},b_{2}]\iff b_{1}\;E\;b_{2}$ 입니다.
(이것이 “ $E$ 가 $\in$ 을 해석한다”는 말의 의미입니다.)
•

$\phi$ 가 “ $\neg\psi$ ”이면 $\mathscr{M}\vDash\phi[b_{1},\dots,b_{n}]\iff\mathscr{M}\not\vDash\psi[b_{1},% \dots,b_{n}]$ 입니다.
•

$\phi$ 가 “ $\psi_{1}\lor\psi_{2}$ ”이면 $\mathscr{M}\vDash\phi[b_{1},\dots,b_{n}]$ 은 어떤 $i=1,2$ 에 대하여 $\mathscr{M}\vDash\psi_{i}[b_{1},\dots,b_{n}]$ 임을 뜻합니다.
•

가장 중요한 경우: $\phi$ 가 $\exists x\psi(x,x_{1},\dots,x_{n})$ 이라 합시다. 그러면 $\mathscr{M}\vDash\phi[b_{1},\dots,b_{n}]$ 일 필요충분조건은 다음과 같습니다.

$\exists b\in M\text{다음을 만족하는}\mathscr{M}\vDash\psi[b,b_{1},\dots,b_{n}].$

$\psi$ 에는 매개변수가 하나 더 있다는 점에 유의하십시오.

모형의 정보가 실제로 어디에 쓰이는지 주목하십시오. $E$ 는 $x_{1}\in x_{2}$ 를 해석할 때만 쓰이는데, 이는 놀라운 일이 아닙니다. 그런데 집합 $M$ 은 $\exists$ (따라서 $\forall$ )를 훑을 때만 쓰입니다. 이 점은 충분히 기억해 둘 만합니다:

모형의 동작은 본질적으로 전체 모형 $M$ 을 탐색하는 $\exists$ 와 $\forall$ 에서 나옵니다.

그리고 마지막으로,

정의 92.2.5.

$\mathsf{ZFC}$ 의 모형은 모든 $\mathsf{ZFC}$ 공리를 만족하는 모형 $\mathscr{M}=(M,E)$ 입니다.

우리는 특히 $M$ 이 추이적 집합인 $(M,\in)$ 꼴의 모형에 관심이 있습니다. (우리는 우주가 추이적이기를 원합니다. 그렇지 않으면 집합의 원소 중에 우주에 속하지 않는 것이 생기는데, 이는 매우 이상한 일입니다.) 이러한 모형을 추이적 모형이라고 합니다.

표기의 남용 92.2.6.

$M$ 이 추이적 집합이면 모형 $(M,\in)$ 을 간단히 $M$ 으로 줄여 씁니다.

정의 92.2.7.

$\mathsf{ZFC}$ 의 내부 모형은 $\mathsf{ZFC}$ 를 만족하는 추이적 모형입니다.

비고 92.2.8.

$\mathsf{ZFC}$ 의 모형의 정의에서는 $\varphi$ 에 매개변수가 없는 경우의 $M\vDash\varphi$ 만 사용합니다. 그럼에도 $\varphi$ 에 매개변수가 있을 때 $M\vDash\varphi$ 가 무엇을 뜻하는지도 정의했음을 알 수 있는데, 이는 그것이 $M\vDash\exists x\psi(x)$ 의 정의에 쓰이기 때문입니다.

확장 $\varphi(x_{1},\dots,x_{n})$ 은 둥근 괄호로 쓰지만 $M\vDash\varphi[b_{1},\dots,b_{n}]$ 은 대괄호로 씁니다 — 이는 매개변수 $b_{1},\dots,b_{n}$ 을 $\varphi$ 에 “형식적으로 대입”한 것으로 생각할 수 있습니다. $b_{1},\dots,b_{n}$ 을 $\varphi$ 에 “실제로” 대입하면 $\varphi(b_{1},\dots,b_{n})$ 은 단지 하나의 불리언 값이 되기 때문입니다.

92.3 레비 위계

대표적인 예: $\mathtt{isSubset}(x,y)$ 는 절대적입니다. 공리 $\mathrm{EmptySet}$ 은 $\Sigma_{1}$ 이고, $\mathtt{isPowerSetOf}(X,x)$ 는 $\Pi_{1}$ 입니다.

기억해야 할 핵심은 모형의 동작이 대체로 $\exists$ 와 $\forall$ 에 의해 결정된다는 점입니다. 사실 이보다 더 많은 것을 말할 수 있습니다.

다음과 같은 논리식을 생각해 봅시다

\mathtt{isEmpty}(x):\neg\exists a(a\in x)

이 논리식은 주어진 집합 $x$ 에 원소가 있는지 확인합니다. 엄밀히 말하면 여기에는 “ $\exists$ ”가 들어 있습니다. 그러나 이 $\exists$ 는 $x$ 안에서만 탐색하도록 유계이므로, 어쩐지 실제로 전체 모형을 탐색하지는 않습니다. 즉, 이를 비형식적으로 다음과 같이 다시 쓸 수 있습니다

\neg(\exists a\in x)

이는 엄밀한 형태에는 맞지 않지만, 우리가 $a\in x$ 인 범위만 살펴본다는 점을 드러냅니다. 이러한 한정기호를 유계 한정기호라고 부릅니다.

유계 한정기호를 가진 문장이 좋은 이유는, 그러한 문장이 추이적 모형에 대해 절대적인 성질을 나타내기 때문입니다. 주변 모형 $M$ 이 얼마나 이상한지는 상관없습니다. $M$ 이 추이적이기만 하면,

M\vDash\mathtt{isEmpty}(\varnothing)

항상 성립합니다. 마찬가지로, 다음 문장

\mathtt{isSubset}(x,y):x\subseteq y\text{ i.e. }\forall a\in x(a\in y)

역시 절대적입니다. 이러한 성질을 갖는 문장을 $\Sigma_{0}$ 또는 $\Pi_{0}$ 라고 합니다.

다음과 같은 문장의 경우에는 상황이 다릅니다

\mathtt{isPowerSetOf}(y,x):\forall z\left(z\subseteq x\iff z\in y\right)

이 문장을 말로 풀면 “ $y$ 는 $x$ 의 멱집합이다”, 즉 간단히 $y=\mathcal{P}(x)$ 라는 뜻입니다. 여기서 $\forall z$ 는 유계가 아닙니다. 이 기묘함 때문에 다음과 같은 일이 가능해지며

\omega\vDash\text{``$\{0,1,2\}$는 $\{0,1\}$의 멱집합입니다''}

따라서

\omega\vDash\mathrm{PowerSet}

이는 앞에서 본 어처구니없는 예였습니다. 문장 $\mathtt{isPowerSetOf}$ 는 유계가 아닌 $\forall$ 뒤에 절대적인 문장이 오는 꼴이므로, 이를 $\Pi_{1}$ 이라고 합니다.

더 일반적으로, 레비 위계는 한정기호가 얼마나 유계인지를 추적합니다. 구체적으로,

•

유계 한정기호만 가진 논리식은 $\Delta_{0}=\Sigma_{0}=\Pi_{0}$ 입니다.
•

$\psi$ 가 $\Pi_{n}$ 일 때 $\exists x_{1}\dots\exists x_{k}\psi$ 꼴의 논리식은 $\Sigma_{n+1}$ 로 간주합니다.
•

$\psi$ 가 $\Sigma_{n}$ 일 때 $\forall x_{1}\dots\forall x_{k}\psi$ 꼴의 논리식은 $\Pi_{n+1}$ 로 간주합니다.

( $\Sigma_{n}$ 이면서 동시에 $\Pi_{n}$ 인 논리식을 $\Delta_{n}$ 이라고 부르지만, $n=0$ 인 경우를 제외하면 이 개념은 사용하지 않겠습니다.)

예제 92.3.1 ( $\Delta_{0}$ 문장의 예).

(a)

앞에서 논의한 문장 $\mathtt{isEmpty}(x)$ , $x\subseteq y$ 입니다.
(b)

“ $x$ 가 추이적임”이라는 논리식은 $\Delta_{0}$ 문장으로 풀어 쓸 수 있습니다.
(c)

“ $x$ 가 순서수임”이라는 논리식은 $\Delta_{0}$ 문장으로 풀어 쓸 수 있습니다.

연습문제 92.3.2.

“ $x$ 가 추이적임”과 “ $x$ 가 순서수임”을 $\Delta_{0}$ 꼴로 풀어 쓰십시오.

예제 92.3.3 (더 복잡한 논리식).

(a)

공리 $\mathrm{EmptySet}$ 은 $\Sigma_{1}$ 입니다. 이 공리는 $\exists a(\mathtt{isEmpty}(a))$ 이고, $\mathtt{isEmpty}(a)$ 는 $\Delta_{0}$ 입니다.
(b)

앞에서 논의한 대로 “ $y=\mathcal{P}(x)$ ”라는 논리식은 $\Pi_{1}$ 입니다.
(c)

“ $x$ 가 가산임”이라는 논리식은 $\Sigma_{1}$ 입니다. 이를 표현하는 한 가지 방법은 “단사 사상 $x\hookrightarrow\omega$ 인 $\exists f$ ”이며, 여기에는 반드시 비유계 “ $\exists f$ ”가 들어갑니다.
(d)

공리 $\mathrm{PowerSet}$ 은 $\Pi_{3}$ 입니다.

$\forall y\exists P\forall x(x\subseteq y\iff x\in P).$

비고 92.3.4 (왜 교대하는 비유계 한정기호만 세는가?).

논리식 $\exists a\exists b\psi(a,b)$ 는 $\exists c(\text{$c$는 순서쌍 $(a,b)$}\land\psi(a,b))$ 로도 쓸 수 있다는 점에 주목하십시오. 논리식 $\exists a\exists b\psi(a,b)$ 를 $\Sigma_{1}$ 로만 간주하려는 이유가 바로 이것입니다.

92.4 부분구조와 타르스키-보트

$\mathscr{M}_{1}=(M_{1},E_{1})$ 과 $\mathscr{M}_{2}=(M_{2},E_{2})$ 를 모형이라고 합시다.

정의 92.4.1.

$M_{1}\subseteq M_{2}$ 이고 $E_{1}$ 이 $E_{2}$ 와 일치하면 $\mathscr{M}_{1}\subseteq\mathscr{M}_{2}$ 라고 하며, $\mathscr{M}_{1}$ 을 $\mathscr{M}_{2}$ 의 부분구조라고 합니다.

이것은 따분합니다. 흥미로운 부분은 다음과 같습니다.

정의 92.4.2.

$\mathscr{M}_{1}\subseteq\mathscr{M}_{2}$ 이고 모든 문장 $\phi(x_{1},\dots,x_{n})$ 과 매개변수 $b_{1},\dots,b_{n}\in M_{1}$ 에 대하여 다음이 성립하면 $\mathscr{M}_{1}\prec\mathscr{M}_{2}$ 라고 하거나, $\mathscr{M}_{1}$ 을 $\mathscr{M}_{2}$ 의 초등 부분구조라고 합니다.

\mathscr{M}_{1}\vDash\phi[b_{1},\dots,b_{n}]\iff\mathscr{M}_{2}\vDash\phi[b_{1% },\dots,b_{n}].

다시 말해, $\mathscr{M}_{1}$ 과 $\mathscr{M}_{2}$ 는 가능한 모든 문장에 대하여 일치합니다. $b_{i}$ 는 반드시 $\mathscr{M}_{1}$ 에서 와야 한다는 점에 주목하십시오. $b_{i}$ 가 $\mathscr{M}_{2}$ 에서 온다면 $\mathscr{M}_{1}$ 에 대하여 무언가를 묻는 것이 의미가 없습니다.

이제 다음을 물어봅시다. $\mathscr{M}_{1}\prec\mathscr{M}_{2}$ 는 어떻게 성립하지 않을 수 있겠습니까? 가능한 문장을 살펴보면, 원자 논리식도, “ $\land$ ”와 “ $\neg$ ”도 문제를 일으키지 않습니다.

이쯤이면 $\forall$ 와 $\exists$ 를 만나는 순간 문제가 생긴다는 직관이 들어야 합니다. 유계 한정기호에서는 문제가 생기지 않습니다. 그러나 비유계 한정기호는 모형 전체를 탐색하며, 바로 거기서 문제가 생깁니다.

“구체적인 예”를 들어 보겠습니다. $\mathscr{M}_{1}$ 이 MIT이고 $\mathscr{M}_{2}$ 가 매사추세츠주라고 상상해 보십시오. $\mathscr{M}_{1}$ 이 MIT에 해커가 있다고 생각한다면, 매사추세츠주에도 당연히 해커가 있습니다. 문제가 생기는 것은 다음과 같은 경우입니다.

\mathscr{M}_{2}\vDash\text{``$\exists x$ : $x$는 번호가 $>50$인 강의입니다''}.

이 문장은 $\mathscr{M}_{2}$ 에서 참입니다. 예를 들어 증인으로 $x=\text{Math 55}$ 를 잡을 수 있기 때문입니다. 그러나 $\mathscr{M}_{1}$ 에서는 거짓입니다. MIT에서는 모든 과목에 $18.701$ 같은 번호가 붙어 있기 때문입니다.

문제는 $\mathscr{M}_{2}$ 에서 성립하는 명제의 증인이 반드시 $\mathscr{M}_{1}$ 의 증인으로 내려오지는 않는다는 것입니다.

타르스키-보트 판정법에 따르면 이것이 유일한 장애물입니다. 즉 $\mathscr{M}_{2}$ 의 모든 증인을 $\mathscr{M}_{1}$ 의 증인으로 바꿀 수 있다면 $\mathscr{M}_{1}\prec\mathscr{M}_{2}$ 입니다.

보조정리 92.4.3 (타르스키-보트).

$\mathscr{M}_{1}\subseteq\mathscr{M}_{2}$ 라고 합시다. 그러면 $\mathscr{M}_{1}\prec\mathscr{M}_{2}$ 일 필요충분조건은 다음과 같습니다. 모든 문장 $\phi(x,x_{1},\dots,x_{n})$ 과 매개변수 $b_{1},\dots,b_{n}\in M_{1}$ 에 대하여, $\mathscr{M}_{2}\vDash\phi(\tilde{b},b_{1}\dots,b_{n})$ 에 대한 증인 $\tilde{b}\in M_{2}$ 가 존재하면 $\mathscr{M}_{1}\vDash\phi(b,b_{1},\dots,b_{n})$ 에 대한 증인 $b\in M_{1}$ 도 존재합니다.

증명.

위의 논의를 거치고 나면 쉽습니다. 이를 형식화하려면 논리식의 복잡도에 대한 귀납법을 사용하십시오. ∎

92.5 $\mathsf{ZFC}$ 의 공리 얻기

이제 $M$ 이 $\mathsf{ZFC}$ 공리를 만족하기 위한 조건을 적어 보려고 합니다. 요지는 $\mathsf{ZFC}$ 공리 거의 전부가 원하는 어떤 집합에 대한 $\Sigma_{1}$ 주장일 뿐이라는 점입니다. 따라서 공리를 검증하는 일은 적절한 “닫힘” 조건, 즉 공리의 증인이 실제로 모형 안에 있는지를 확인하는 일로 귀결됩니다.

예를 들어 $\mathrm{EmptySet}$ 공리는 “ $\exists a(\mathtt{isEmpty}(a))$ ”이므로 $\varnothing\in M$ 이기만 하면 충분합니다. 물론 이는 공집합이 아닌 모든 추이적 집합 $M$ 에 대해 참입니다.

보조정리 92.5.1 ( $\mathsf{ZFC}$ 를 물려받는 추이적 집합).

$M$ 이 공집합이 아닌 추이적 집합이라고 합시다. 그러면 다음이 성립합니다.

(i)

$M$ 은 $\mathrm{Extensionality}$ , $\mathrm{Foundation}$ , $\mathrm{EmptySet}$ 을 만족합니다.
(ii)

$x,y\in M\implies\{x,y\}\in M$ 이면 $M\vDash\mathrm{Pairing}$ 입니다.
(iii)

$x\in M\implies\cup x\in M$ 이면 $M\vDash\mathrm{Union}$ 입니다.
(iv)

$x\in M\implies\mathcal{P}(x)\cap M\in M$ 이면 $M\vDash\mathrm{PowerSet}$ 입니다.
(v)

모든 $x\in M$ 과, 매개변수를 가지고 $M$ -정의 가능한 모든 함수 $F\colon x\to M$ 에 대하여 $F^{\text{img}}(x)\in M$ 도 성립하면 $M\vDash\mathrm{Replacement}$ 입니다.
(vi)

$\omega\in M$ 이기만 하면 $M\vDash\mathrm{Infinity}$ 입니다.

여기서 집합 $X\subseteq M$ 을 다음과 같이 나타낼 수 있으면 $X$ 가 매개변수를 가지고 $M$ -정의 가능하다고 합니다.

X=\left\{x\in M\mid\phi[x,b_{1},\dots,b_{n}]\right\}

이때 매개변수 $b_{1},\dots,b_{n}\in M$ 은 어떤 (고정된) 선택입니다. $n=0$ 인 경우도 허용하며, 이 경우 $X$ 가 매개변수 없이 $M$ -정의 가능하다고 합니다. $X$ 자체가 $M$ 에 속할 필요는 없다는 점에 유의하십시오! 자명한 예로, $X=M$ 은 매개변수 없이 $M$ -정의 가능하지만(그냥 $\phi[x]$ 를 항상 참인 식으로 잡으면 됩니다) $X\in M$ 은 당연히 성립하지 않습니다.

연습문제 92.5.2.

위의 (i)-(iv)를 확인하십시오.

비고 92.5.3.

보조정리 92.5.1의 명제들의 역은 (vi)을 제외한 모든 주장에 대해 참입니다.

92.6 모스토프스키 붕괴

지금까지는 다루기가 더 쉬웠기 때문에 추이적 모형만 이야기했습니다. 추이적 모형만 신경 써도 되는 두 번째 이유가 있으며, 이 이유가 더 좋습니다.

보조정리 92.6.1 (모스토프스키 붕괴 보조정리).

$X=(X,\in)$ 가 외연 공리를 만족하는 모형이고 $X$ 는 (추이적이 아닐 수도 있는) 집합이라고 합시다. 그러면 어떤 추이적 모형 $M=(M,\in)$ 에 대하여 동형사상 $\pi\colon X\to M$ 이 존재합니다.

이를 추이적 붕괴라고도 합니다. 사실 $\pi$ 와 $M$ 은 모두 유일합니다.

증명.

증명의 아이디어는 매우 간단합니다. $\in$ 은 정초적이고 외연적이므로(각각 $\mathrm{Foundation}$ 과 $\mathrm{Extensionality}$ 를 만족하므로), $\in$ 에 대한 $X$ 의 $\in$ -극소 원소 $x_{\varnothing}$ 을 생각할 수 있습니다. 당연히 이 원소는 $0=\varnothing$ 으로 보내고자 합니다.

다음으로 $\in$ 에 대해 그다음으로 작은 집합을 잡아 $1=\{\varnothing\}$ 으로 보냅니다. 이 과정을 “계속 반복합니다”. 이렇게 하면 정확히 원하는 결과를 얻는다는 것을 어렵지 않게 알 수 있습니다.

이를 형식화하기 위해 초한 재귀로 $\pi$ 를 다음과 같이 정의합니다.

\pi(x)\coloneqq\left\{\pi(y)\mid y\in x\right\}.

이렇게 구성한 $\pi$ 가 바로 원하는 역할을 합니다. ∎

비고 92.6.2 (전문가를 위한 여담).

Napkin의 이전 판에서는 이것이 $\mathscr{X}\vDash\mathrm{Foundation}+\mathrm{Extensionality}$ 인 일반적인 모형 $\mathscr{X}=(X,E)$ 에 대해 성립한다고 주장했습니다. 이는 거짓입니다. 이 조건으로는 $E$ 가 정초적이라는 것조차 보장되지 않습니다. $X$ 자체에는 속하지 않는 $X$ 의 부분집합들로 이루어진 무한 하강 사슬이 존재할 수 있기 때문입니다. 또 다른 문제는 $E$ 가 집합적(set-like)이지 않을 수도 있다는 점입니다.

이를 그림으로 나타내면 $M$ 의 원소들을 $V$ 의 바닥으로 “붕괴”시키는 모습이 되며, 이름도 여기에서 유래했습니다.

그림 작성 예정: 모스토프스키 붕괴의 그림

92.7 도달 불가능 기수 추가하기

대표적인 예: $V_{\kappa}$

여기까지 오면 그래서 $\mathsf{ZFC}$ 의 모형은 도대체 어디에 있느냐고 물으실지도 모르겠습니다.

안타깝게도 이제 인정해야 합니다. $\mathsf{ZFC}$ 는 $\mathsf{ZFC}$ 의 모형이 존재한다는 것을 결코 증명할 수 없습니다( $\mathsf{ZFC}$ 가 모순적이라면 예외이지만, 그것은 더욱 나쁜 상황입니다). 이것이 Gödel의 불완전성 정리라고 불리는 결과입니다.

그럼에도 아주 온건한 가정을 몇 가지 추가하면 모형이 실제로 존재함을 보일 수 있습니다. 예를 들어 강한 도달 불가능 기수 $\kappa$ 가 존재한다고 가정하면 충분하며, 이때 $V_{\kappa}$ 가 그러한 모형이 됩니다(문제 92D). 그 이유는 직관적으로 알 수 있습니다. $\kappa$ 는 너무나 커서, 그보다 낮은 계수를 가진 집합은 멱집합을 취하든, $\mathrm{Replacement}$ 공리를 사용하든, 그 밖에 $\mathsf{ZFC}$ 가 허용하는 어떤 방법을 쓰든 $\kappa$ 를 벗어날 수 없습니다.

더 비관적으로 보면, 이는 그러한 $\kappa$ 가 존재함을 $\mathsf{ZFC}$ 안에서 증명하는 것이 불가능하다는 뜻입니다. 그럼에도 이제부터는 편의상 그러한 $\kappa$ 의 존재를 마지막 공리로 추가한 $\mathsf{ZFC}^{+}$ 아래에서 논의를 진행합니다. 이제 우리에게는 가지고 놀 수 있는 모형 $V_{\kappa}$ 가 생겼습니다. 기쁜 일입니다!

좋습니다. 이제 정말로 말도 안 되는 일을 해 보겠습니다.

정리 92.7.1 (가산 추이적 모형).

$\mathsf{ZFC}^{+}$ 를 가정합니다. 그러면 $X$ 가 가산 집합인 $\mathsf{ZFC}$ 의 추이적 모형 $X$ 가 존재합니다.

증명.

안전벨트를 단단히 매십시오.

먼저 $\mathsf{ZFC}^{+}$ 를 가정했으므로 $V_{\kappa}=(V_{\kappa},\in)$ 를 $\mathsf{ZFC}$ 의 모형으로 삼을 수 있습니다. 집합 $X_{0}=\varnothing$ 에서 시작합니다. 그런 다음 모든 정수 $n$ 에 대해 다음을 수행하여 $X_{n+1}$ 을 얻습니다.

•

먼저 $X_{n+1}$ 이 $X_{n}$ 의 모든 원소를 포함하도록 합니다.
•

논리식 $\phi(x,x_{1},\dots,x_{n})$ 과 $X_{n}$ 의 원소 $b_{1},\dots,b_{n}$ 을 생각합니다. $V_{\kappa}$ 가 다음을 만족하는 $b\in V_{\kappa}$ 가 존재한다고 여긴다고 가정합시다.

$V_{\kappa}\vDash\phi[b,b_{1},\dots,b_{n}].$

그러면 원소 $b$ 를 $X_{n+1}$ 에 추가합니다.
•

이 작업을 집합론의 언어로 쓸 수 있는 모든 논리식에 대해 수행합니다. 또한 이전 집합 $X_{n}$ 에서 가져올 수 있는 모든 매개변수 집합도 넣어야 합니다.

매 단계에서 $X_{n}$ 은 가산입니다. 이유는 다음과 같습니다. $X_{n}$ 안의 매개변수로 이루어질 수 있는 유한집합은 가산 개이고, 가능한 논리식도 가산 개이므로, 결국 각 단계에서 추가하는 것은 가산 개뿐입니다. 이로써 다음과 같이 가산 집합들이 무한히 중첩된 열을 얻습니다

X_{0}\subseteq X_{1}\subseteq X_{2}\subseteq\dots

각 $X_{n}$ 은 $X_{n+1}$ 에 있는 증인에 의존하므로, 이들 중 어느 것도 $V_{\kappa}$ 의 기본 부분구조가 아닙니다. 그래서 대신 합집합을 취합니다.

X=\bigcup_{n}X_{n}.

이 집합은 타르스키-보트 판정법을 만족하며 가산입니다.

사소한 단서가 하나 있습니다. $X$ 가 추이적이지 않을 수도 있다는 것입니다. 그러나 그 모스토프스키 붕괴를 취하면 되므로 상관없습니다. ∎

이것이 얼마나 정신 나간 일인지 잠시 감상해 보십시오. 이 결과는 우리가 적을 수 있는 문장이 가산 개뿐이라는 사실에 전적으로 의존합니다.

비고 92.7.2.

이 증명은 원소 $b$ 를 $X_{n+1}$ 에 추가할 때 선택 공리에 크게 의존합니다. 선택 공리 없이는 이러한 결정을 한꺼번에 내릴 방법이 없습니다.

보통 선택 공리의 사용을 형식화하는 올바른 방법은, 모든 논리식 $\phi(x,x_{1},\dots,x_{n})$ 에 대하여 (맨 처음에) 함수 $f_{\phi}(x_{1},\dots,x_{n})$ 를 미리 정해 두어, 임의의 $b_{1},\dots,b_{n}$ 이 주어지면 $f_{\phi}(b_{1},\dots,b_{n})$ 가 (존재한다면) 적절한 $b$ 의 값을 내놓도록 하는 것입니다. 개인적으로는 이 방식이 증명의 본질을 가린다고 생각하지만, 선택 공리가 정확히 어떻게 쓰이는지는 분명히 보여 줍니다.

이러한 $f_{\phi}$ 들에는 이름이 있습니다. 바로 스콜렘 함수입니다.

이 증명에서 사용한 기법은 더 일반적인 상황에서도 통합니다.

정리 92.7.3 (하향 Löwenheim-Skolem 정리).

$\mathscr{M}=(M,E)$ 가 모형이고 $A\subseteq M$ 이라고 합시다. 그러면 $A\subseteq B\subseteq M$ 이고 $(B,E)\prec\mathscr{M}$ 을 만족하는 집합 $B$ ( $A$ 의 스콜렘 껍질이라고 부릅니다)가 존재하며,

\left\lvert B\right\rvert=\max\left\{\omega,\left\lvert A\right\rvert\right\}.

우리의 경우에는 단순히 $A$ 를 공집합으로 잡은 것입니다.

질문 92.7.4.

이를 증명하십시오. (앞의 증명과 완전히 같습니다.)

92.8 가산 모형에 관한 자주 묻는 질문

가장 흔한 질문은 “이게 어떻게 가능합니까?”이고, 그다음은 “방금 무슨 일이 일어난 겁니까?”입니다.

첫 번째 질문에 최선을 다해 답해 보겠습니다. 두 가지 사실이 서로 충돌하는 것처럼 보입니다.

(1)

$M$ 은 $\mathsf{ZFC}$ 의 추이적 모형이지만, 그 우주는 가산입니다.
(2)

$\mathsf{ZFC}$ 는 비가산 집합이 존재한다고 말합니다!

(이것은 너무나 많은 사람을 혼란스럽게 해서 스콜렘 역설이라는 이름까지 붙어 있습니다.)

이것이 성립하는 이유는 사실 앞에서 이미 지적했습니다. 가산성은 절대적이지 않으며, $\Sigma_{1}$ 개념입니다.

집합 $x$ 가 가산이라는 것은 단사 사상 $x\hookrightarrow\omega$ 가 존재한다는 뜻임을 상기하십시오. 첫 번째 명제는 단지 우주 $V$ 에서 단사 사상 $F\colon M\hookrightarrow\omega$ 가 존재한다는 것을 말할 뿐입니다. 특히 임의의 $x\in M$ 에 대하여 ( $M$ 이 추이적이므로 $x\subseteq M$ 이기도 합니다), $x$ 는 $V$ 에서 가산입니다. 이것이 첫 번째 명제의 내용입니다.

그러나 $M$ 이 $\mathsf{ZFC}$ 의 모형이 되려면, $M$ 은 $\mathsf{ZFC}$ 의 명제들이 참이라고 여기기만 하면 됩니다. 요점을 말하자면, $\mathsf{ZFC}$ 가 비가산 집합이 존재한다고 말한다는 사실은 다음을 뜻합니다

M\vDash\text{$\exists x$ 비가산}.

다시 말해,

M\vDash\exists x\forall f\text{$f\colon x\to\omega$이면 $f$는 단사가 아닙니다}.

핵심은 $\forall f$ 가 우리의 작은 모형 $M$ 안에 있는 함수들만 탐색한다는 점입니다. “현실 세계” $V$ 에서는 단사 함수 $f\colon x\to\omega$ 가 존재하는 것이 사실입니다.¹¹1 $M$ 이 추이적이고 가산이므로, 임의의 $x\in M$ 에 대하여 $x$ 자체는 많아야 가산 개의 원소를 가질 수 있습니다. $M$ 이 추이적이지 않다면 이는 반드시 참이지는 않습니다. 그러나 $M$ 은 그런 함수가 존재한다는 것을 전혀 모릅니다! $M$ 은 통 속의 뇌입니다. $M$ 은 자신 바깥의 어떤 정보도 알지 못합니다.

따라서 사실 $M$ 에 나타나는 모든 순서수는 현실 세계에서 가산입니다. 단지 $M$ 에서 가산이 아닐 뿐입니다. $M\vDash\mathsf{ZFC}$ 이므로, $M$ 은 가장 작은 비가산 기수, 이를테면 $\aleph_{1}^{M}$ 이 존재한다고 여길 것입니다. 이것은 모형 $M$ 안에서 $\aleph_{1}^{M}$ 과 $\omega$ 사이의 전단사가 존재하지 않는다는 성질을 가진 $M$ 의 가장 작은 (무한) 순서수일 것입니다. 그러나 우리는 현실 세계 $V$ 에서는 그러한 전단사가 반드시 존재한다는 것을 알고 있습니다.

달리 말하면, 기수는 전단사로 측정되기 때문에 $M$ 에서의 기수는 현실 세계에서의 기수와 크게 다르게 보일 수 있습니다. 이는 아마 불가피한 일이겠지만, 혼란을 불러일으킵니다.

92.9 내부 모형 그려 보기

다음은 가산 추이적 모형 $M$ 을 나타낸 그림입니다.

모든 유한집합에는 그것을 표현하는 논리식이 있으므로, $M$ 과 $V$ 는 유한집합에 대해 반드시 일치해야 한다는 점에 유의하십시오. 그러나 $V_{\omega}$ 를 넘어서면 모형과 진짜 우주는 갈라지기 시작합니다.

모형 $M$ 전체는 가산이므로, 우주의 작은 부분, 즉 첫 번째 비가산 기수 $\aleph_{1}^{V}$ (여기서 위첨자는 “참된 우주 $V$ 의”라는 뜻입니다) 아래의 부분만을 차지합니다. “ $\alpha$ 는 순서수이다”라는 문장은 절대적이므로, $M$ 의 순서수는 정확히 모형 안에 속해 있는 $V$ 의 순서수들입니다. 한편 $M$ 은 한낱 집합, 그것도 가산 집합에 불과하므로 이러한 순서수 중 일부만을 가집니다. $M$ 의 순서수를 나타내기 위해 $\mathrm{On}^{M}$ 이라고 쓰며, 여기서 위첨자는 “ $M$ 에서 계산한 순서수”라는 뜻입니다. 마찬가지로 이제 $\mathrm{On}^{V}$ 는 “참된 순서수의 집합”을 나타냅니다.

그럼에도 모형 $M$ 에는 첫 번째 비가산 기수의 자기 나름의 판본인 $\aleph_{1}^{M}$ 이 있습니다. 참된 우주에서 $\aleph_{1}^{M}$ 은 가산입니다( $\aleph_{1}^{V}$ 보다 작습니다). 그러나 이를 보여 주는 데 필요한 전단사가 $M$ 안에는 없을 수도 있습니다. 그렇기 때문에 $\aleph_{1}^{M}$ 이 원래 우주에서는 가산 기수이더라도 $M$ 은 $\aleph_{1}^{M}$ 을 비가산이라고 여길 수 있습니다.

즉, 우리의 모형 $M$ 은 통 속의 뇌입니다. $M$ 은 마침 $\mathsf{ZFC}$ 의 모든 공리를 믿고 있으므로, $M$ 에서 참인 모든 명제는 $V$ 에서도 참일 수 있습니다. 그러나 $M$ 은 자신을 둘러싼 우주를 볼 수 없습니다. $M$ 은 자신이 비가산인 $\aleph_{1}^{M}$ 이라고 믿는 것이 사실은 평범한 가산 순서수에 불과하다는 것을 전혀 알지 못합니다.

92.10 생각해 볼 만한 조금 더 어려운 문제

문제 92A.

임의의 추이적 모형 $M$ 에 대하여, $M$ 에 속한 순서수들의 집합 자체가 어떤 순서수임을 보이십시오.

문제 92B.

$\mathscr{M}_{1}\subseteq\mathscr{M}_{2}$ 라고 가정합시다. 다음을 보이십시오.

(a)

$\phi$ 가 $\Delta_{0}$ 이면, $\mathscr{M}_{1}\vDash\phi[b_{1},\dots,b_{n}]\iff\mathscr{M}_{2}\vDash\phi[b_{1% },\dots,b_{n}]$ 입니다.
(b)

$\phi$ 가 $\Sigma_{1}$ 이면, $\mathscr{M}_{1}\vDash\phi[b_{1},\dots,b_{n}]\implies\mathscr{M}_{2}\vDash\phi[% b_{1},\dots,b_{n}]$ 입니다.
(c)

$\phi$ 가 $\Pi_{1}$ 이면, $\mathscr{M}_{2}\vDash\phi[b_{1},\dots,b_{n}]\implies\mathscr{M}_{1}\vDash\phi[% b_{1},\dots,b_{n}]$ 입니다.

(이 장을 이해했다면 쉬울 것입니다.)

문제 92C (반영).

^†^†margin:

$\kappa$ 가 모든 $\alpha<\kappa$ 에 대하여 $|V_{\alpha}|<\kappa$ 를 만족하는 도달 불가능 기수라고 합시다. 임의의 $\delta<\kappa$ 에 대하여 $V_{\alpha}\prec V_{\kappa}$ 를 만족하는 $\delta<\alpha<\kappa$ 가 존재함을 증명하십시오. 다시 말해, $V_{\alpha}\prec V_{\kappa}$ 를 만족하는 $\alpha$ 들의 집합은 $\kappa$ 에서 비유계입니다. 이는 $V_{\kappa}$ 의 성질이 $V_{\alpha}$ 의 성질로 아래로 반영된다는 뜻입니다.

힌트. 이는 Löwenheim-Skolem 정리의 증명과 매우 비슷합니다. 문장 $\phi$ 에 대하여, $f_{\phi}$ 가 $\alpha$ 를 다음 조건을 만족하는 가장 작은 $\beta<\kappa$ 로 보낸다고 합시다. 모든 $\vec{b}\in V_{\alpha}$ 에 대하여, $V_{\kappa}\vDash\phi[a,\vec{b}]$ 를 만족하는 $a\in V_{\kappa}$ 가 존재하면 $V_{\kappa}\vDash\phi[a,\vec{b}]$ 를 만족하는 $\exists a\in V_{\beta}$ 가 성립합니다. (이러한 $\beta$ 가 존재함을 증명하려면 $\kappa$ 가 정칙이라는 사실을 이용하십시오.) 그런 다음, 각 $\alpha$ 에 대하여 가산 개의 문장 전체에 걸친 상한을 취하십시오.

풀이. 문장 $\phi$ 에 대하여

$f_{\phi}\colon\kappa\to\kappa$

가 $\alpha$ 를 다음 조건을 만족하는 가장 작은 $\beta<\kappa$ 로 보낸다고 합시다. 모든 $\vec{b}\in V_{\alpha}$ 에 대하여, $V_{\kappa}\vDash\phi[a,\vec{b}]$ 를 만족하는 $a\in V_{\kappa}$ 가 존재하면 $V_{\kappa}\vDash\phi[a,\vec{b}]$ 를 만족하는 $\exists a\in V_{\beta}$ 가 성립합니다.

이것이 잘 정의됨을 주장합니다. $\vec{b}$ 로 가능한 선택은 $\left\lvert V_{\alpha}\right\rvert^{n}$ 개뿐이며, 특히 그 개수는 $\kappa$ 보다 적습니다( $\left\lvert V_{\alpha}\right\rvert<\kappa$ 임을 알고 있기 때문입니다. 문제 91C와 비교하십시오). 그렇지 않다면, 각 벡터 $\vec{b}$ 를 명제가 성립하지 않는 $\beta$ 로 보냄으로써 $\left\lvert V_{\alpha}^{n}\right\rvert$ 에서 $\kappa$ 로 가는 공종 사상을 구성할 수 있습니다. 그런데 $\kappa$ 가 정칙이므로 이는 불가능합니다!

다시 말해, 우리가 한 일은 $\phi$ 를 고정한 다음 모든 $\vec{b}\in V_{\alpha}^{n}$ 에 대하여 타르스키-보트 판정법을 사용한 것입니다. 이제 $g\colon\kappa\to\kappa$ 를 다음과 같이 정의합시다.

$\alpha\mapsto\sup f_{\phi}(\alpha).$

$\kappa$ 가 정칙이고 논리식은 가산 개뿐이므로, $g(\alpha)$ 는 잘 정의됩니다.

$\alpha$ 가 $g$ 에 의해 $\alpha$ 자신으로 사상된다는 성질(다시 말해 $\alpha$ 가 $g$ 에 대해 닫혀 있다는 성질)을 가지면, 타르스키-보트 판정법에 의해 $V_{\alpha}\prec V_{\kappa}$ 가 성립함을 확인하십시오.

따라서 $g$ 에 대하여 닫혀 있는 $\alpha<\kappa$ 가 임의로 크게 존재함을 보이면 충분합니다. $\alpha_{0}$ 을 고정합시다. $\alpha_{1}=g(\alpha_{0}$ ) 등으로 두고 다음을 정의합시다.

$\alpha=\sup_{n<\omega}\alpha_{n}.$

이 $\alpha$ 는 $g$ 에 대하여 닫혀 있으며, $\alpha_{0}$ 을 임의로 크게 잡으면 $\alpha$ 를 원하는 만큼 크게 만들 수 있습니다.

문제 92D (강하게 도달 불가능한 기수는 모형을 만들어 냅니다).