장 92 내부 모형 이론

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

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

92.1 모형

대표적인 예: $(\omega,\in)$ 는 $\mathrm{PowerSet}$ 을 만족하며, $V_{\kappa}$ 는 $\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)

$\mathscr{M}$ 은 $\mathrm{Pairing}$ 을 만족하지 않는데, $1,3\in\omega$ 이지만 $\{1,3\}$ 은 $\omega$ 에 속하지 않기 때문입니다.
(d)

놀랍게도, $\mathscr{M}$ 은 $\mathrm{Union}$ 을 만족하는데, 임의의 $n\in\omega$ 에 대해 $\cup n$ 이 $n-1$ 이기 때문입니다( $n=0$ 인 경우는 제외). 합집합 공리는 다음을 명시합니다

$\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}$ 에서는 집합이 아닙니다.

특히, 이 낯선 새로운 세계에서는 $2^{n}=n+1$ 이라고 말할 수 있는데, $n=\{0,1,\dots,n-1\}$ 이 실제로 오직 $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$ 에 의해 주어지지 않는 변수들을 말합니다.

앞으로 우리는 $\phi(x_{1},\dots,x_{n})$ 이 매개변수 $x_{1}$ , …, $x_{n}$ 을 가지는 논리식 $\phi$ 를 나타내는 것으로 하겠습니다. 여기서 $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$ 는 매개변수가 하나 더 있음에 유의하십시오.

모델의 정보가 실제로 어디에서 사용되는지 주목하십시오. $x_{1}\in x_{2}$ 를 해석할 때는 오직 $E$ 만을 사용하는데, 이는 놀랍지 않습니다. 그러나 집합 $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}$ 입니다. 이를 표현하는 한 가지 방법은 “ $\exists f$ 가 $x\hookrightarrow\omega$ 인 단사 사상이다”인데, 이는 필연적으로 비유계인 “ $\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}$ 에 대한 목격자로 전파되지는 않는다는 점입니다.

Tarski-Vaught 판정법은 이것이 유일한 장애물임을 말해줍니다: $\mathscr{M}_{2}$ 의 모든 증인을 $\mathscr{M}_{1}$ 의 증인으로 대체할 수 있다면 $\mathscr{M}_{1}\prec\mathscr{M}_{2}$ 입니다.

보조정리 92.4.3 (Tarski-Vaught).

$\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$ 이 다음과 같이 실현될 수 있으면 이를 매개변수를 사용해 $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 Mostowski 붕괴

지금까지는 생각하기 더 쉬웠기 때문에 추이적 모델에 대해서만 이야기해 왔습니다. 여기 우리가 추이적 모델에만 관심을 가져도 되는 두 번째, 더 나은 이유가 있습니다.

보조정리 92.6.1 (Mostowski 붕괴 정리).

$X=(X,\in)$ 을 Extensionality를 만족하는 모델이라 하고, $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$ 의 바닥으로 ”붕괴시키는” 것이며, 이름도 여기서 유래합니다.

그림 작성 예정: Mostowski 붕괴의 그림

92.7 비가측 기수 추가하기

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

이쯤에서 이렇게 물으실 수 있습니다. 그런데 제 $\mathsf{ZFC}$ 의 모델은 어디 있습니까?

유감스럽지만 이제 인정해야 합니다: $\mathsf{ZFC}$ 는 $\mathsf{ZFC}$ 의 모델이 존재한다는 것을 결코 증명할 수 없습니다(단, $\mathsf{ZFC}$ 가 모순적인 경우는 예외이지만, 그것은 더 나쁜 상황일 것입니다). 이것은 괴델의 불완전성 정리라고 불리는 결과입니다.

그럼에도 불구하고, 매우 소박한 가정 몇 가지를 추가하면 실제로 모델이 존재함을 보일 수 있습니다: 예를 들어, 강비가측 기수 $\kappa$ 가 존재한다고 가정하면 그 역할을 하기에 충분하며, $V_{\kappa}$ 가 그러한 모델이 될 것입니다 (문제 92D). 직관적으로 왜 그런지 알 수 있습니다: $\kappa$ 는 너무 커서 그보다 낮은 계수를 가진 어떤 집합도, 심지어 그것의 멱집합을 취하거나, $\mathrm{Replacement}$ 공리를 사용하거나, $\mathsf{ZFC}$ 가 허용하는 다른 어떤 방법을 쓰더라도 그것을 벗어날 수 없습니다.

더 비관적으로 말하면, 이는 그러한 $\kappa$ 가 존재한다는 것을 $\mathsf{ZFC}$ 에서 증명하는 것이 불가능함을 보여줍니다. 그럼에도 불구하고, 편의를 위해 이제부터는 $\mathsf{ZFC}^{+}$ 하에서 논의를 진행하는데, 이는 그러한 $\kappa$ 의 존재를 마지막 공리로 추가한 것입니다. 이제 우리는 가지고 놀 수 있는 모델 $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}$ 의 모든 원소를 포함하는 $X_{n+1}$ 에서 시작합니다.
•

$X_{n}$ 에 속한 논리식 $\phi(x,x_{1},\dots,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

이들 중 어느 것도 $V_{\kappa}$ 의 초등 부분구조가 아닌데, 각 $X_{n}$ 이 $X_{n+1}$ 안의 증인들에 의존하기 때문입니다. 그래서 우리는 대신 합집합을 취합니다:

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

이는 Tarski-Vaught 판정법을 만족하며, 가산입니다.

한 가지 사소한 주의사항이 있습니다: $X$ 는 추이적이지 않을 수도 있습니다. 우리는 신경 쓰지 않는데, 그저 그것의 Mostowski 붕괴를 취하면 되기 때문입니다. ∎

잠시 시간을 내어 이것이 얼마나 미친 짓인지 감상해 보십시오. 이는 우리가 적을 수 있는 문장이 가산 개라는 사실에 돌이킬 수 없이 의존합니다.

비고 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\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$ 의”를 의미합니다) 아래로 우주의 작은 부분만을 차지합니다. $M$ 안의 순서수는 정확히 $V$ 의 순서수 중 우연히 모형 안에 속하는 것들인데, ” $\alpha$ 는 순서수이다”라는 문장이 절대적이기 때문입니다. 반면, $M$ 은 오직 하찮은 집합, 그것도 가산 집합에 불과하므로, 이러한 순서수들의 일부만을 가집니다. $M$ 의 순서수를 나타내기 위해 우리는 $\mathrm{On}^{M}$ 이라고 쓰며, 위 첨자는 ” $M$ 에서 계산된 순서수”를 의미합니다. 마찬가지로, $\mathrm{On}^{V}$ 는 이제 ”실제 순서수의 집합”을 나타낼 것입니다.

그럼에도 불구하고, 모델 $M$ 은 자신만의 버전의 첫 번째 비가산 기수 $\aleph_{1}^{M}$ 을 가지고 있습니다. 참된 우주에서 $\aleph_{1}^{M}$ 은 가산입니다( $\aleph_{1}^{V}$ 보다 작습니다), 하지만 이를 증언하는 필요한 전단사가 $M$ 내부에 존재하지 않을 수 있습니다. 이것이 바로 $\aleph_{1}^{M}$ 이 원래 우주에서는 가산 기수임에도, $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$ 에 대해 $\delta<\alpha<\kappa$ 이면서 $V_{\alpha}\prec V_{\kappa}$ 인 $\alpha$ 가 존재함을 증명하십시오. 다시 말해, $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$ 가 정칙(regular)이라는 사실을 이용하십시오.) 그런 다음, 각 $\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과 비교해 보십시오). 그렇지 않다면, 명제가 성립하지 않는 $\beta$ 로 각 벡터 $\vec{b}$ 를 대응시킴으로써 $\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 (강비가산 기수는 모델을 만들어 냅니다).