워시의 정리

25 Jan 2025

이전 글에서 이어지는 내용이다.

5. 초자연수의 비표준적 특징

지금까지 우리가 살펴본 초자연수는 $[0], [1], [2], \dots$와 같이 표준 자연수와 상응하는 것들이었다. 이제 표준 자연수와는 괴리가 있는 초자연수들을 살펴 보자.

다음의 초자연수 $\mathfrak{n}$을 보자.

\[(1, 2, 3, 4, \dots) \in \mathfrak{n}\]

초자연수의 정의가 동치류이기 때문에 등호가 아닌 포함 관계로 표현함에 유의하라. 초자연수에서 부등호의 정의를 상기하면, 자연수 $n$에 대해 $[n] < \mathfrak{n}$임을 알 수 있다. 즉, $\mathfrak{n}$은 모든 자연수보다 큰 초자연수이다. 따라서 초자연수에서는 다음이 성립한다.

\[\phi_1 : \exists x \; ( \lbrace y : y < x \rbrace \text{ is infinite } )\]

위 명제는 자연수에서는 성립하지 않는다.

이번에는 다음의 초자연수 $\mathfrak{m}$을 보자.

\[(1, 2!, 3!, 4!, \dots) \in \mathfrak{m}\]

표준 자연수 $n$에 대해 $\mathfrak{m}$은 $[n]$으로 나누어떨어진다. 즉, $\mathfrak{m}$은 모든 자연수를 약수로 가진다. 따라서 초자연수에서는 다음이 성립한다.

\[\phi_2 : \exists x \; (\lbrace y : y \mid x \rbrace \text{ is infinite })\]

위 명제 또한 자연수에서는 성립하지 않는다.

그런데 이상한 점이 있다. 저번 글의 서론에서 필자는 자연수와 초자연수가 논리적으로 구분 불가능하다고 했다. 그러나 $\phi_1$과 $\phi_2$는 $\mathbb{N}^*$에서는 참이지만 $\mathbb{N}$에서는 거짓이므로, 둘은 논리적으로 구분 가능한 것으로 보인다. 필자가 거짓말을 한 것일까?

그렇지 않다. 이 표면적인 역설을 해결하는 실마리는, $\phi_1$과 $\phi_2$가 1차 논리로 표현 불가능한 문장이라는 사실이다. 콤팩트성 정리에 의해 “…가 유한하다”는 1차 논리로 표현 불가능하기 때문이다.

$\mathbb{N}^*$과 $\mathbb{N}$이 논리적으로 구분 불가능하다는 말의 엄밀한 의미는 다음과 같다.

정의. 언어 $\mathcal{L}$의 모형 $\mathcal{M}_1$과 $\mathcal{M}_2$가 기초적으로 동등(elementarily equivalent)하다는 것은 임의의 (1차 논리) 문장 $\phi$에 대해

\[\mathcal{M_1} \vDash \phi \iff \mathcal{M}_2 \vDash \phi\]

가 성립하는 것이다.

정리. $\mathbb{N}$과 $\mathbb{N}^*$은 기초적으로 동등하다.

위 정리는 워시의 정리의 특수한 결과이다. 워시의 정리를 소개하기 앞서, 일반화된 초곱의 개념을 먼저 살펴보자.

6. 초곱

집합 $I$와, $I$ 위의 자유 초필터 $\mathcal{U}$가 주어졌다고 하자. 또한, 언어 $\mathcal{L}$의 모형 $\lbrace \mathcal{M}_i \rbrace_{i \in I}$가 주어졌다고 하자. 이때, 초곱(ultraproduct) $\mathcal{M}^* = \prod \mathcal{M}_i / \mathcal{U}$를 다음과 같이 정의한다.

초곱의 원소

$\mathcal{M}^*$의 원소는 $\lbrace (a_i)_{i\in I} : a_i \in \mathcal{M}_i \rbrace$가 $\sim$에 대해 이루는 동치류이다. 여기서 $\sim$은 다음과 같이 정의된다.

\[(a_i)_{i\in I} \sim (b_i)_{i \in I} \iff \lbrace i \in I : a_i = b_i \rbrace \in \mathcal{U}\]

초곱 위의 연산

$f(x)$가 $\mathcal{L}$의 함수라고 하자. $\mathcal{M}^*$의 원소 $\mathfrak{a} = [(a_i)_{i\in I}]$에 대해 다음과 같이 정의한다.

\[f(\mathfrak{a}) = [(f(a_i))_{i \in I}]\]

위 정의는 자연스러운 방식으로 $n$항 함수로 일반화된다.

초곱 위의 술어

$P(x, y)$가 $\mathcal{L}$의 술어라고 하자. $\mathcal{M}^*$의 두 원소 $\mathfrak{a} = [(a_i)_{i\in I}]$와 $\mathfrak{b} = [(b_i)_{i\in I}]$에 대해 다음과 같이 정의한다.

\[\mathcal{M}^* \vDash P(\mathfrak{a}, \mathfrak{b}) \iff \lbrace i \in I : \mathcal{M}_i \vDash P(a_i, b_i) \rbrace \in \mathcal{U}\]

위 정의는 자연스러운 방식으로 $n$항 술어로 일반화된다.

초곱 위의 연산과 술어를 정의할 때, 연산과 술어의 결과가 동치류에서 어떤 원소를 대표자로 선택하든 상관없이 같음을 보여야 한다. 이것은 $\mathcal{U}$의 교집합 속성으로부터 어렵지 않게 얻어지므로 연습문제로 남긴다.

이로써 우리는 초자연수를, $I, \mathcal{U}, \mathcal{L}, \mathcal{M}_i$가 각각 다음과 같을 때 도출되는 초곱으로 재정의할 수 있다.

• $I = \mathbb{N}$
• $\mathcal{U} =$ 프레셰 초필터
• $\mathcal{L} = (0, S, <)$
• $\mathcal{M}_i = \mathbb{N}$

비슷한 방식으로 초실수(hyperreals)를 정의할 수 있다.

• $I = \mathbb{N}$
• $\mathcal{U} =$ 프레셰 초필터
• $\mathcal{L} = (0, 1, +, ⋅, <)$
• $\mathcal{M}_i = \mathbb{R}$

7. 워시의 정리

워시의 정리(Łoś’s Theorem). 초곱 $\mathcal{M}^* = \prod \mathcal{M}_i / \mathcal{U}$가 주어졌을 때, 임의의 $\mathcal{L}$-문장 $\phi$에 대해 다음이 성립한다.

\[\mathcal{M}^* \vDash \phi \iff \lbrace i \in I : \mathcal{M}_i \vDash \phi \rbrace \in \mathcal{U}\]

Proof. $\phi$에 대한 구조적 귀납법으로 증명한다.

1. $\phi$가 원자 명제이다

“초곱 위의 술어” 정의에 의해 자명하게 성립한다.

2. $\phi := \psi \land \theta$

\[\begin{aligned} &\mathcal{M}^* ⊨ φ\\ &\iff \mathcal{M}^* ⊨ ψ \land \mathcal{M}^* ⊨ θ\\ &\iff \lbrace i ∈ I \mid \mathcal{M}_i ⊨ ψ \rbrace ∈ \mathcal{U} \land \lbrace i ∈ I \mid \mathcal{M}_i ⊨ θ \rbrace ∈ \mathcal{U} &&(*) \\ &\iff \lbrace i ∈ I \mid \mathcal{M}_i ⊨ ψ \rbrace \cap \lbrace i ∈ I \mid \mathcal{M}_i ⊨ θ \rbrace ∈ \mathcal{U} &&(**) \\ &\iff \lbrace i ∈ I \mid \mathcal{M}_i ⊨ ψ \land \mathcal{M}_i ⊨ θ \rbrace ∈ \mathcal{U}\\ &\iff \lbrace i ∈ I \mid \mathcal{M}_i ⊨ ψ∧θ \rbrace ∈ \mathcal{U}\\ &\iff \lbrace i ∈ I \mid \mathcal{M}_i ⊨ φ \rbrace ∈ \mathcal{U} \end{aligned}\]

$(*)$는 귀납 가정에 의해 성립하고, $(**)$는 $\mathcal{U}$의 교집합 닫힘 속성으로 성립한다.

3. $\phi := \lnot \psi$

2와 비슷한 방법으로 하면 된다. 단, 귀납 가정과 $\mathcal{U}$의 초필터 속성($A \in \mathcal{U} \lor A^c \in \mathcal{U}$)를 사용한다.

4. $\phi := \exists x\; \psi$

2와 비슷한 방법으로 하면 된다. 단, 귀납 가정만 사용해도 충분하다.

모든 명제는 1, 2, 3, 4로 구성할 수 있으므로 귀납법에 의해 정리가 증명되었다. ■

따름정리. $\mathbb{N}$과 $\mathbb{N}^*$은 기초적으로 동등하다.

Proof. 워시의 정리에 의해 $\mathbb{N}^* \vDash \phi$일 필요충분조건은 $\lbrace i \in \mathbb{N} : \mathbb{N}^\ast_i \vDash \phi \rbrace \in \mathcal{U}$인 것이다. 그런데 $\mathbb{N}^*_i = \mathbb{N}$이므로, 필요충분조건은 $\mathbb{N} \vDash \phi$로 환원된다. ■