오일러-라그랑주 방정식과 라그랑주 역학

27 Feb 2025

1. 도입

1차원 위에서 운동하는 입자의 운동 경로는 $x(t)$와 같이 표현할 수 있다. 입자의 위치와 속도에 의존적인 함수 $f(x, x’)$를 생각하자. 이 입자가 시간 $t_1$일 때 $x_1$에서 출발하여 시간 $t_2$일 때 $x_2$에 도착하는데, 그 과정에서 다음 값을 극화_extremise하는 경로, 즉 다음 값이 극대 또는 극소가 되도록 하는 경로 $x(t)$를 찾는 것이 목표이다.

\[A[x] = \int^{t_2}_{t_1} f(x, \dot{x}) dt\]

대괄호는 $A$의 매개변수가 실수가 아닌 함수임을 의미한다. 따라서 직관적으로 생각했을 때 $A[x]$를 최소화하는 $x(t)$를 찾기 위해서는 함수에 대한 미분식을 세워야 한다.

\[\frac{dA[x]}{dx(t)} = 0?\]

2. 오일러-라그랑주 방정식

물론 함수에 대한 미분을 우리는 정의한 적이 없다. 하지만 간단한 트릭을 통해 함수에 대한 미분을 일반적인 미분으로 환원할 수 있다. 먼저 $x_0(t)$가 우리가 찾고자 하는 경로, 즉 $A[x]$를 극화시키는 경로라고 하자. $x_0(t)$의 ‘주변’에 있는 경로는 다음과 같은 꼴이다.

\[x(\alpha, t) = x_0(t) + \alpha h(t)\]

경계 조건은 $h(t_1) = h(t_2) = 0$이다. $x_0(t)$가 $A[x]$를 극화시키므로, 충분히 작은 $\epsilon$에 대해 $A[x_0] = A[x(0, t)] \leq A[x(\epsilon, t)]$이다. 따라서,

\[\left. \frac{dA[x(\alpha, t)]}{d\alpha} \right\vert_{\alpha = 0} = 0\]

위 식을 전개하면 다음과 같다.

\[\begin{aligned} \frac{dA}{d\alpha} &= \int^{t_2}_{t_1} \frac{d}{d\alpha} \Big[ f \big( x(\alpha, t), \dot{x}(\alpha, t) \big) \Big] dt \\ &= \int^{t_2}_{t_1} \left( \frac{\partial f}{\partial x}\frac{\partial x}{\partial \alpha} + \frac{\partial f}{\partial \dot{x}}\frac{\partial \dot{x}}{\partial \alpha} \right) dt \\ &= \int^{t_2}_{t_1} \frac{\partial f}{\partial x}\frac{\partial x}{\partial \alpha} dt + \int^{t_2}_{t_1} \frac{\partial f}{\partial \dot{x}} \cdot \frac{d}{dt} \left( \frac{\partial x}{\partial \alpha} \right) dt \\ &= \int^{t_2}_{t_1} \frac{\partial f}{\partial x}\frac{\partial x}{\partial \alpha} dt + \left[ \frac{\partial f}{\partial \dot{x}} \frac{\partial x}{\partial \alpha} \right]^{t_2}_{t_1} - \int^{t_2}_{t_1} \frac{d}{dt} \left( \frac{\partial f}{\partial \dot{x}} \right) \frac{\partial x}{\partial \alpha} dt \end{aligned}\]

3번 식에서 4번 식으로 넘어가는 데 부분적분이 쓰였다. ${\partial x}/{\partial \alpha} = h(t)$이므로, 경계 조건에 의해 4번 식의 두 번째 항은 소거된다. 따라서,

\[\frac{dA}{d\alpha} = \int^{t_2}_{t_1} \left( \frac{\partial f}{\partial x} - \frac{d}{dt}\left( \frac{\partial f}{\partial \dot{x}} \right) \right) \frac{\partial x}{\partial \alpha} dt = 0\]

임의의 $h \in C^1$에 대해 위 식이 만족되어야 하므로, $x(t)$가 $A$를 극화할 다음의 필요조건을 얻는다.

\[\frac{\partial f}{\partial x} = \frac{d}{dt}\left( \frac{\partial f}{\partial \dot{x}} \right)\]

이것이 오일러-라그랑주 방정식_{Euler-Lagrange equation}이다. 값 $A$를 극화한다는 것을 $\delta A = 0$과 같이 표현하므로, 오일러-라그랑주 방정식의 결론은 다음과 같이 적을 수 있다.

\[\delta A = 0 \implies \frac{\partial f}{\partial x} = \frac{d}{dt}\left( \frac{\partial f}{\partial \dot{x}} \right)\]

방금 우리는 일변수 함수에 대해 증명했지만, 다변수 함수에 대해서도 마찬가지 식이 성립한다. 즉, 어떤 입자(들)의 운동을 나타내는 좌표가 $\lbrace q_i \rbrace _{i \leq n}$라고 하자. 예를 들어 2개의 입자가 3차원에서 운동하는 경우 $n = 6$이다. 이들의 운동이 $\int f(q_1, \dot{q_1}, \dots, q_n, \dot{q_n}) dt$를 극화할 필요조건은 각 $i$에 대해 다음이 성립하는 것이다.

\[\frac{\partial f}{\partial q_i} = \frac{d}{dt}\left( \frac{\partial f}{\partial \dot{q_i}} \right)\]

3. 라그랑주 역학

정의. 계 $S$의 입자(들)의 운동을 나타내는 좌표가 $\lbrace q_i \rbrace _{1 \leq i \leq n}$라고 하자. $S$의 라그랑지안_Lagrangian $\mathcal{L}(\lbrace q , \dot{q} \rbrace, t)$를, 다음의 값을 극화시키는 조건에 대한 방정식이 입자들의 운동 방정식과 같아지도록 하는 함수로 정의한다.

\[\mathcal{S} = \int^{t_2}_{t_1} \mathcal{L}(\{ q, \dot{q} \}, t) dt\]

$\mathcal{S}$를 작용_action이라고 부른다.

예를 들어 1차원 퍼텐셜 장 $V(x)$에 속하는 입자의 라그랑지안은 다음과 같다.

\[\begin{aligned} \mathcal{L}(x, \dot{x}) &= T - V \\ &= \frac{1}{2}m\dot{x}^2 - V(x) \end{aligned}\]

위 함수가 라그랑지안이라는 것을 확인해 보자. 오일러-라그랑주 방정식을 사용하면 해당 라그랑지안에 따른 작용이 극화될 조건은 다음과 같다.

\[\begin{aligned} \delta \mathcal{S} = 0 &\implies \frac{\partial \mathcal{L}}{\partial x} = \frac{d}{dt} \frac{\partial \mathcal{L}}{\partial \dot{x}} \\ &\iff -\frac{dV}{dx} = \frac{d}{dt}(m\dot{x}) \\ &\iff -\frac{dV}{dx} = m\ddot{x} \end{aligned}\]

마지막 식은 뉴턴의 운동 방정식이다. 따라서 $\mathcal{L}$은 이 계의 라그랑지안이 맞다. 일반적으로 다음이 성립한다.

정리. 다음 두 조건을 만족하는 고전역학적 계의 라그랑지안은 $\mathcal{L} = T - V$로 주어진다.

1. 계의 경계 조건이 홀로노믹_holonomic하다. 즉, 경계 조건이 입자들의 위치에만 의존하고 속도에 의존하지 않는다.
2. 계에 작용하는 힘 $\mathbf{F}_i$가 퍼텐셜 함수 $U_i(\lbrace q, \dot{q} \rbrace, t)$를 가진다.

증명. 링크된 SE 포스트를 참조.

그러나 일반적으로 계의 라그랑지안이 $T - V$로 주어지는 것은 아니다. 예를 들어 상대론적 입자의 운동 에너지는 $(\gamma - 1)m_0c^2$이지만, 올바른 라그랑지안은 $-m_0c^2/\gamma$이다.

뉴턴 역학과 달리 라그랑주 역학은 매우 자유로운 좌표계 변환을 허용한다는 점에서 강점을 가진다. 뉴턴 역학과 달리 라그랑주 역학은 일반 공변성을 가지기 때문이다. 이에 대한 자세한 설명은 다음 글에 있다.

르베그 가측 집합과 보렐 가측 집합

25 Feb 2025

1. 르베그 측도

카라테오도리 정리로부터 다음과 같이 측도 $m$을 정의할 수 있다.

1. $\mathcal{A}_0 = \lbrace \cup^n_{k=1} (a_k, b_k] : a_k, b_k \in \mathbb{R}^\infty \rbrace $는 대수임을 보인다.

2. $A \in \mathcal{A}_0$에 대해, $A = \sqcup^n_{k=1} (a_k, b_k]$로 표현하는 방법이 유일함을 보인다.

3. 함수 $\rho: \mathcal{A}_0 \to [0, \infty]$를

   \[\rho(\sqcup^n_{k=1} (a_k, b_k]) = \sum^n_{k=1}(b_k - a_k)\]

   와 같이 정의했을 때 $\rho$가 예비측도임을 보인다.

4. $\mathcal{A}_0, \rho$에 대해 카라테오도리 구축 정리를 적용하여 외측도 $m^\ast$을 얻는다.

5. $m^\ast$의 정의역을 $m^\ast$-가측집합으로 제한하여 측도 $m$을 얻는다.

대수는 유한 합집합에만 닫혀 있기 때문에 1, 2, 3은 거의 자명하다. 4, 5의 증명은 관련 글을 참조하라.

정의. 상술한 $m$을 르베그 측도_{Lebesgue measure}라고 부른다. 또한, $m$의 정의역에 속하는 집합을 르베그 가측_{Lebesgue measurable}이라고 부른다.

카라테오도리 정리들로부터 다음 사실들이 어렵지 않게 따라 나온다.

정리.

1. $m([a, b]) = m((a, b)) = m((a, b]) = m([a, b)) = b - a$
2. $A \subset \mathbb{R}$이 가산일 때, $m(A) = 0$

그리고 카라테오도리 확장 정리로 얻어지는 측도는 완비 측도_{complete measure}이므로 다음이 성립한다.

정리. $m$은 완비 측도이다.

또한 $\sigma(\mathcal{A}_0)$는 보렐 $\sigma$-대수 $\mathcal{B}$이므로, 다음이 따라 나온다.

정리. 보렐 가측 집합은 르베그 가측이다.

2. 르베그 가측이지만 보렐 가측이 아닌 집합

정의. 집합열 $\lbrace C_n \rbrace$을 다음과 같이 정의한다.

\[\begin{gather} C_0 = [0, 1]\\ C_1 = I_0 \setminus (1/3, 2/3) \\ C_2 = I_1 \setminus \{ (1/9, 2/9) \cup (7/9, 8/9) \} \\ \vdots \end{gather}\]

칸토어 집합_{Cantor set} $C$를 $\cap^\infty_{n = 0}C_n$으로 정의한다.

정리.

1. 칸토어 집합은 비가산이다.
2. 칸토어 집합은 르베그 측도 0이다.

증명.

1. 칸토어 집합에 속하는 원소들은 삼진법으로 소숫점 전개했을 때 어느 자리에도 2가 등장하지 않는 수들이다. 그러한 수는 $2^\aleph_0$개 있으므로 비가산이다.

2. $m(C_n) = (2/3)^n$이므로 $m(C) = \lim_{n \to infty} (2/3)^n = 0$. ■

정의. 칸토어 집합을 정의할 때 각 단계에서 빠지는 집합을 $J_n$이라고 하자. 즉,

\[\begin{gather} J_1 = (1/3, 2/3) \\ J_2 = (1/9, 2/9) \cup (7/9, 8/9) \\ \vdots \end{gather}\]

다음과 같이 함수열을 정의한다.

\[\begin{gather} \operatorname{dom} f_1 = J_1,\; f_1(x) = \frac{1}{2} \\\\ \operatorname{dom} f_2 = J_1 \cup J_2, \; f_2(x) = \begin{cases} 1/4 & x \in (1/9, 2/9) \\ 1/2 & x \in (1/3, 2/3) \\ 3/4 & x \in (7/9, 8/9) \end{cases} \\\\ \vdots \end{gather}\]

$f: I \to I$를 다음과 같이 정의한다.

\[f(x) = \inf \{ f_n(y) : y \geq x, y \in \mathrm{dom} f \}\]

$f$를 칸토어 함수_{Cantor function}라고 한다.

정리. 칸토어 함수는 연속이다.

증명. $f$를 칸토어 함수라고 하자. $f$는 증가함수이므로 $f$가 불연속점을 가진다면 해당 불연속은 틈 불연속_{gap discontinuity}이며, 따라서 어떤 $\epsilon > 0$와 $y_0 \in I$에 대해 $(y_0 - \epsilon, y_0 + \epsilon)$이 $\operatorname{im} f$ 밖에 속한다. 그런데 $(y_0 - \epsilon, y_0 + \epsilon)$의 원소 중에는 이진법으로 소숫점 전개했을 때 자릿수가 유한한 수가 존재한다. 해당 수는 $\operatorname{im}f$에 속하므로 모순이다. ■

정리. 르베그 가측이지만 보렐 가측이 아닌 함수가 존재한다.

증명.

보조정리. $f$가 증가함수라면 $f^{-1}$은 보렐 집합을 보렐 집합에 사상한다.

보조정리의 증명. $\mathcal{A} = \lbrace S \subset I : f^{-1}(S) \in \mathcal{B} \rbrace $라고 하자. 열린 집합들의 모음 $\mathcal{G}$에 대해 $\mathcal{G} \subset \mathcal{A}$임이 자명하다. 또한 $\mathcal{A}$가 $\sigma$-대수임이 역함수의 성질로부터 자명하다. 따라서 $\mathcal{A} = \sigma(\mathcal{G}) = \mathcal{B}$이다.

$f$가 칸토어 함수라고 하고, $F$를 다음과 같이 정의하자.

\[F(x) =\inf \{y : f(y) \geq x \}\]

$F$는 엄격히 증가하는 함수이고, $\operatorname{im} F = C$이다($C$는 칸토어 집합). $V$를 비탈리 집합이라고 하자. $F[V]$는 $C$에 포함되므로 르베그 측도 0이며, 르베그 측도의 완비성에 따라 르베그 가측이다. 그러나 $F[V]$는 보렐 가측이 아니다. 만약 보렐 가측이었다면 $F$가 증가함수이므로 $F^{-1}(F[V]) = V$가 가측이어야 하기 때문이다. ■

카라테오도리 정리를 이용한 측도의 구성

25 Feb 2025

필자는 카라테오도리 정리_{Carathéodory theorem}를 3가지로 구분해서 이해하는 방식을 선호하기 때문에, 이 글에서도 해당 방식을 따른다. 각각 다음과 같다.

1. 카라테오도리 구축 정리: 임의의 집합족과 양함수로부터 외측도_{outer measure} 를 정의할 수 있다.
2. 카라테오도리 제한 정리: 외측도의 정의역을 가측 집합으로 제한한 함수는 측도가 된다.
3. 카라테오도리 확장 정리: 대수 $\mathcal{A}_0$ 위의 예비측도_premeasure $\mu_0$를 확장하는 $\sigma(\mathcal{A}_0)$ 위의 측도는, 집합족을 $\mathcal{A}_0$, 양함수를 $\mu_0$로 잡은 뒤 구축 정리를 적용하여 얻은 외측도 $\mu^\ast$에, 제한 정리를 적용하여 얻은 측도가 유일하다.

도식적으로, 다음과 같이 이해할 수 있다.

	(1)	(2)	(3)
정의역	대수 $\mathcal{A}_0$	$\sigma$-대수 $\mathcal{A}$	멱집합 $\mathcal{P}(X)$
함수	예비측도 $\mu_0$	측도 $\mu$	외측도 $\mu^\ast$

구축 정리는 (1) → (3), 제한 정리는 (3) → (2), 확장 정리는 (1) → (2)의 방향을 가진다. 하나하나 살펴 보자.

정의. $X$ 위의 외측도 $\mu^\ast: \mathcal{P}(X) \to [0, \infty]$는 다음을 만족하는 함수이다.

1. $\mu^\ast(\varnothing) = 0$
2. $A \subset B \implies \mu^\ast(A) \leq \mu^\ast(B)$
3. $\mu^\ast\left( \bigcup_{n \in \mathbb{N}} A_n \right) \leq \sum_{n \in \mathbb{N}} \mu^\ast(A_n)$

카라테오도리 구축 정리. $X$의 부분집합으로 이루어진 임의의 집합족 $\mathcal{S}$와, $l(\varnothing) = 0$을 만족하는 임의의 함수 $l: \mathcal{S} \to [0, \infty]$가 주어졌을 때, 다음과 같이 정의된 $\mu^\ast$은 외측도이다.

\[\mu^*(E) = \inf \left\{ \sum_{n \in \mathbb{N}} l(A_n) : \{ A_n \} \subset \mathcal{S} \text{ covers }E \right\}\]

즉, $\mu^\ast$은 덮개의 극한으로서 $E$의 ‘측도’ 비스무리한 것을 정의하는 함수이며, 구분구적법에서 상합_{upper sum}과 개념적으로 비슷하다.

증명. 1과 2는 자명하다. 3을 보인다.

$A = \bigcup A_n$이라고 하고, 임의의 $\epsilon > 0$이 주어졌다고 하자. $\mu^\ast$의 정의에 의해, 각 $n$에 대해 다음을 만족하는 $A_n$의 덮개 $\mathcal{C}_n = \lbrace A_{nm} \rbrace_{m \in \mathbb{N}} \subset \mathcal{S}$가 존재한다.

\[\sum l(A_{nm}) \leq \mu^*(A_n) + \epsilon/2^n\]

따라서,

\[\sum_{n, m \in \mathbb{N}} l(A_{nm}) \leq \sum \mu^*(A_n) + \epsilon.\]

그리고 $\bigcup \mathcal{C}_n$이 $A$를 덮으므로, $\mu^\ast$의 정의에 의해 $\mu^\ast(A) \leq \sum_{n, m \in \mathbb{N}} l(A_{nm})$이다. ■

정의. $\mu^\ast$가 외측도라고 하자. 임의의 $E$에 대해 다음을 만족하는 집합 $A$를 $\mu^\ast$에 대해 가측_measurable이라고 한다.

\[\mu^*(E) = \mu^*(E \cap A) + \mu^*(E \cap A^c)\]

정의. $\mu^\ast$가 외측도라고 하자. $\mu^\ast(N) = 0$인 $N$을 영집합_{null set}이라고 한다.

즉, 가측 집합은 $\mu^\ast$에 대해 임의의 집합을 ‘깔끔하게’ 분할하는 집합이다. 따라서 가측 집합으로만 이루어진 모임 위에서 $\mu^\ast$은 일반적인 측도와 같이 행동할 것으로 예측할 수 있다. 이 예측을 입증하는 것이 다음의 제한 정리이다.

카라테오도리 제한 정리. $\mu^\ast$가 외측도라고 하자. $\mu^\ast$에 대해 가측인 집합들의 모임을 $\mathcal{A}$라고 할 때, 다음이 성립한다.

1. $\mathcal{A}$는 $\sigma$-대수이다.
2. $\mu^\ast |_\mathcal{A}$는 측도이다.
3. $\mathcal{A}$는 $\mu^\ast$의 모든 영집합을 포함한다.

증명.

1. $\mathcal{A}$는 대수이다.

여집합 닫힘은 자명하다. 유한 교집합 닫힘임을 보인다.

$A, B$가 가측이라고 하자. $A \cap B$가 가측임을 보이기 위해 다음을 보이면 충분하다.

\[\mu^*(E \cap (A \cap B)) + \mu^*(E \cap (A \cap B)^c) \leq \mu^*(E) \quad \cdots \quad (*)\]

$A, B$가 가측이므로 다음이 성립한다.

\[\begin{aligned} \mu^*(E) &= \mu^*(E \cap A) + \mu^*(E \cap A^c) \\ &= \mu^*(E \cap A \cap B) + \mu^*(E \cap A \cap B^c) \\ &+ \mu^*(E \cap A^c \cap B) + \mu^*(E \cap A^c \cap B^c) \end{aligned}\]

따라서 $(\ast)$은 다음과 동치이다.

\[\begin{aligned} \mu^*(E \cap (A^c \cup B^c)) &\leq \mu^*(E \cap A \cap B^c) \\ &+ \mu^*(E \cap A^c \cap B) \quad \cdots \quad (**) \\ &+ \mu^*(E \cap A^c \cap B^c) \end{aligned}\]

간단한 집합론으로부터 다음을 알 수 있다.

\[A^c \cup B^c = (A \cap B^c) \cup (A^c \cap B) \cup (A^c \cap B^c)\]

따라서 $(\ast\ast)$가 성립한다. □

2. $\mathcal{A}$는 $\sigma$-대수이다.

$A_n \uparrow A$인 $\lbrace A_n \rbrace \subset \mathcal{A}$에 대해 $A \in \mathcal{A}$임을 보이면 충분하다. (why?)

외측도의 정의에 의해 $\mu^\ast(E \cap A_n) \leq \mu^\ast(E \cap A)$이다. $C_1 = A_1, C_n = A_n \setminus A_{n - 1}$이라고 하자. $\bigsqcup C_n = A$이다. 또한,

\[\begin{aligned} \mu^*(E \cap A_n) &= \mu^*(E \cap A_n \cap C_n) + \mu^*(E \cap A_n \cap C_n^c) \\ &= \mu^*(E \cap C_n) + \mu^*(E \cap A_{n - 1}) \\ &= \cdots \\ &= \sum^n_{k = 1} \mu^*(E \cap C_k) \end{aligned}\]

이다. 따라서 $\sum^\infty \mu^\ast(E \cap C_n) \leq \mu^\ast(E \cap A)$이다. 그런데 $\lbrace E \cap C_n \rbrace $이 $E \cap A$를 덮으므로, $\sum^\infty \mu^\ast(E \cap C_n) \geq \mu^\ast(E \cap A)$이다. 따라서 $\sum^\infty \mu^\ast(E \cap C_n) = \mu^\ast(E \cap A)$이다.

따라서 임의의 $\epsilon > 0$에 대해, 충분히 큰 $N$이 존재하여 $\mu^\ast(E \cap A) - \epsilon \leq \mu^\ast(E \cap A_n)$이다. 따라서,

\[\begin{aligned} \mu^*(E \cap A_n^c) &= \mu^*(E) - \mu^*(E \cap A_n) \\ &\leq \mu^*(E) - \mu^*(E \cap A) + \epsilon \end{aligned}\]

이므로 다음을 얻는다.

\[\mu^*(E) \leq \mu^*(E \cap A_n) + \mu^*(E \cap A_n^c) \leq \mu^*(E) + \epsilon\]

$n \to \infty$로 보내면 $\mu^\ast(E \cap A) + \mu^\ast(E \cap A^c) = \mu^\ast(E)$이다. □

3. $\mu^\ast|_\mathcal{A}$는 측도이다, 4. $\mathcal{A}$는 모든 영집합을 포함한다.

Left as an exercise to the readers. (어렵지 않음) ■

정의. $\mathcal{A}_0$가 대수라고 하자. $\rho: \mathcal{A}_0 \to [0, \infty]$가 예비측도라는 것은 다음을 만족한다는 것이다.

1. $\rho(\varnothing) = 0$
2. 쌍으로 서로소인 가산 집합족 $\lbrace A_n \rbrace $에 대해, $\bigcup A_n \in \mathcal{A}_0$라면 $\rho\left( \bigcup A_n \right) = \sum \rho(A_n)$

카라테오도리 확장 정리. 대수 $\mathcal{A}_0$ 위의 예비측도 $\rho$에 대해, 다음과 같이 정의하자.

\[\mu^*(E) = \inf \left\{ \sum_{n \in \mathbb{N}} \mu_0(A_n) : \{ A_n \} \subset \mathcal{A}_0 \text{ covers }E \right\}\]

이 때, 다음이 성립한다.

1. $A \in \mathcal{A}_0$라면 $\mu^\ast(A) = \rho(A)$이다.
2. $\sigma(\mathcal{A}_0)$는 $\mu^\ast$에 대해 가측이다.
3. $\rho$가 $\sigma$-유한이라면, $\rho$의 정의역을 $\sigma(\mathcal{A}_0)$로 확장하는 측도는 $\mu^\ast|_{\sigma(\mathcal{A}_0)}$가 유일하다.

증명.

1. $A \in \mathcal{A}_0$라면 $\mu^\ast(A) = \rho(A)$이다.

$A$가 $A$의 덮개이므로 $\mu^\ast(A) \leq \rho(A)$이다. 만약 $\mu^\ast(A) < \rho(A)$라면 어떤 $A$의 덮개 $\lbrace A_n \rbrace $이 존재하여 $\sum \rho(A_n) < \rho(A)$이다. 그런데 $\rho$가 예비측도이므로 이는 모순이다. □

2. $\sigma(\mathcal{A}_0)$는 $\mu^\ast$에 대해 가측이다.

먼저 $\mathcal{A}_0$가 가측임을 보인다. 임의의 $A \in \mathcal{A}_0$에 대해 $\mu^\ast(E \cap A) + \mu^\ast(E \cap A^c) \leq \mu^\ast(E)$임을 보이면 충분하다. $\mu^\ast$의 정의에 의해, 임의의 $\epsilon > 0$에 대해 어떤 $E$의 덮개 $\mathcal{C}$가 존재하여 다음이 성립한다.

\[\sum^\infty_{n = 1} \rho(C_n) \leq \mu^*(E) + \epsilon\]

$\mathcal{A}_0$가 대수이므로, $A \cap C_n, A^c \cap C_n \in \mathcal{A}_0$이다. 따라서,

\[\begin{aligned} \mu^*(E \cap A) + \mu^*(E \cap A^c) &\leq \sum^\infty_{n = 1} \mu^*(A \cap C_n) + \sum^\infty_{n = 1} \mu^*(A^c \cap C_n) \\ &= \sum^\infty_{n = 1} \rho(A \cap C_n) + \sum^\infty_{n = 1} \rho(A^c \cap C_n) \\ &= \sum^\infty_{n = 1} \rho(C_n) \leq \mu^*(E) + \epsilon \end{aligned}\]

(엄밀히 따지자면 $\sum^n_{k=1}$을 고려한 다음에 $n \to \infty$ 극한을 취해야 한다) 따라서 $\mu^\ast(E \cap A) + \mu^\ast(E \cap A^c) \leq \mu^\ast(E)$이며, $\mathcal{A}_0$는 가측이다. 카라테오도리 제한 정리에 의해 가측 집합은 $\sigma$-대수를 이루므로, $\sigma(\mathcal{A}_0)$ 또한 가측이다. □

3. $\rho$가 $\sigma$-유한이라면, $\rho$의 정의역을 $\sigma(\mathcal{A}_0)$로 확장하는 측도는 $\mu^\ast|_{\sigma(\mathcal{A}_0)}$가 유일하다.

먼저 $\rho < \infty$를 가정하자. $\sigma(\mathcal{A}_0)$ 위에서 정의된 측도 $\nu$가 $\mathcal{A}_0$에서 $\rho$와 일치한다고 하자. 또한 $\mu = \mu^\ast|_{\sigma(\mathcal{A}_0)}$라고 하자. $\nu = \mu$임을 보인다.

$E \in \sigma(\mathcal{A}_0)$라고 하자. 어떤 $E$의 덮개 $\lbrace A_n \rbrace \subset \mathcal{A}_0$가 존재하여,

\[\sum \rho(A_n) \leq \mu(E) + \epsilon\]

이다. $\nu$가 $\mathcal{A}_0$에서 $\rho$와 일치하므로, $\sum \rho(A_n) = \sum \nu(A_n) \geq \nu(E)$이다. 따라서 $\nu \leq \mu$이다.

이제 $B_n = \bigcup^n_{k=1}A_k$로 정의하고, $A = \bigcup^\infty_{n = 1} A_n = \lim_{n \to \infty} B_n$이라고 하자. $\mu(B) = \sum \rho(A_n) \leq \mu(E) + \epsilon$이므로 $\mu(B \setminus E) \leq \epsilon$이다. $\nu$가 측도이므로,

\[\mu(A) = \lim \rho(B_n) = \lim \nu(B_n) = \nu(A)\]

따라서,

\[\begin{aligned} \mu(E) \leq \mu(B) &= \mu(B \setminus E) + \mu(E) \\ &\leq \epsilon + \nu(E) \end{aligned}\]

즉 $\mu \leq \nu$이다. 따라서 $\mu = \nu$이다.

이제 $\rho$가 $\sigma$-유한하다고 가정하자. 어떤 집합족 $\lbrace C_n \rbrace $이 존재하여 $C_n \uparrow X$이고, $\rho(C_n) < \infty$이다. 앞선 논의에 의해 $C_n$에서 $\mu$와 $\nu$는 일치한다. 따라서,

\[\mu(A) = \lim \mu(A \cap C_i) = \lim \nu (A \cap C_i) = \nu(A)\]

이므로 $\mu$와 $\nu$는 전체 공간에서 일치한다. ■

다음 글에서는 카라테오도리 정리를 이용하여 르베그 측도를 구성한 뒤, 모든 보렐 가측 집합은 르베그 가측 집합이지만 그 역은 성립하지 않음을 보인다.

대수와 측도의 정의

24 Feb 2025

1. 비탈리 정리

정의. $\mu$가 집합 $X$ 위의 측도_measure라는 것은 다음을 만족한다는 것이다.

1. $\mu(\varnothing) = 0$
2. 쌍으로 서로소_{pairwise disjoint}인 가산 집합족 $\lbrace A_n \rbrace$에 대해, $\mu\left( \bigcup A_n \right) = \sum \mu(A_n)$

유감스럽게도 $X = \mathbb{R}$일 때, 측도 $\mu$는 실수의 모든 부분집합에 대해서 정의될 수 없다.

비탈리 정리. 다음을 모두 만족하는 $\mathbb{R}$의 측도 $\mu$는 존재하지 않는다.

1. 항등적으로 0이 아니다.
2. 평행이동에 대해 보존적이다. 즉, 임의의 $r \in \mathbb{R}$에 대해 $\mu(A + r) = \mu(A)$.
3. $\operatorname{dom} \mu = \mathcal{P}(\mathbb{R})$

증명. 그러한 측도 $\mu$가 존재한다고 가정하자. $\mathbb{R}$ 위에서 다음의 동치 관계를 정의하자.

\[x \sim y \iff x - y \in \mathbb{Q}\]

선택 공리에 의해 $[0, 1]/{\sim}$의 선택 함수 $\iota$가 존재한다. $V = \operatorname{im} \iota$라고 하자. $V$를 비탈리 집합_{Vitali set}이라고 부른다. 예를 들어 $V = \lbrace 0.1, \pi - 3, \sqrt{2} - 1, \dots \rbrace$이다. $\mu$는 $V$에서 정의될 수 없음을 보인다.

$V$의 정의에 의해, $q \in \mathbb{Q}$에 대해 $V$와 $V + q$는 서로소이다. 또한 $[0, 1] \subset \bigcup_{q \in \mathbb{Q}} (V + q) \subset [-1, 3]$이다. 따라서,

\[1 \leq \sum_{q \in \mathbb{Q}}\mu(V + q) \leq 4.\]

그런데 $\mu(V + q) = \mu(V)$이므로, $\mu(V) = 0$이면 왼쪽 부등식이 성립하지 않고 $\mu(V) > 0$이면 오른쪽 부등식이 성립하지 않는다. 따라서 모순이다. ■

2. $\sigma$-대수

따라서 올바른 측도를 구축하기 위해서는 측도의 정의역을 적절히 제한할 필요가 있다. 이에 대수의 개념을 도입한다.

정의. 집합 $X$의 대수_algebra $\mathcal{A}_0$는 다음을 만족하는 집합족이다.

1. $\varnothing, X \in \mathcal{A}_0$
2. $A \in \mathcal{A}_0 \implies A^c \in \mathcal{A}_0$
3. $A, B \in \mathcal{A}_0 \implies A \cup B \in \mathcal{A}_0$

Remark. 2번 공리와 드모르간의 법칙에 의해, 3번 공리는 $A \cap B \in \mathcal{A}_0$ 또한 시사한다.

대수의 3번 정의를 가산 합집합으로 강화하면 $\sigma$-대수의 정의를 얻는다. 즉,

정의. 집합 $X$의 $\sigma$-대수 $\mathcal{A}$는 다음을 만족하는 대수이다.

1. $\lbrace A_n \rbrace _{n \in \mathbb{N}} \subset \mathcal{A}_0 \implies \bigcup_{n \in \mathbb{N}} A_n \in \mathcal{A}$

정리. $\lbrace \mathcal{A}_i \rbrace_{i \in I}$가 $X$의 $\sigma$-대수들의 모임이라면 $\bigcap_{i \in I}\mathcal{A}_i$ 또한 $X$의 $\sigma$-대수이다.

증명. $\sigma$-대수의 정의로부터 쉽게 증명할 수 있다. 그런데 이렇게만 적으면 재미 없으니까, 조금 독특한 증명을 남긴다. 워시-타르스키 정리_{Łoś-Tarski theorem}에 따르면 1차 이론이 교집합에 대해 보존적일 필요충분조건은 1차 이론의 모든 문장이 $\Pi_1$ 문장인 것이다. 그리고 $\sigma$-대수의 세 공리는 모두 $\Pi_1$ 문장이므로, $\sigma$-대수는 교집합에 대해 보존적이다. ■

따름정리. $\mathcal{C}$가 $X$의 부분집합으로 이루어진 집합족일 때, $\mathcal{C}$를 포함하는 가장 작은 $\sigma$-대수가 존재한다. 그러한 $\sigma$-대수를 $\sigma(\mathcal{C})$와 같이 적는다.

증명. $\mathcal{S} = \lbrace \mathcal{A} : \mathcal{A} \text{ is an algebra containing } \mathcal{C} \rbrace$라고 하자. $\mathcal{P}(X) \in \mathcal{S}$이므로 $\mathcal{S}$는 공집합이 아니다. $\sigma(\mathcal{C}) = \bigcap_{\mathcal{A} \in \mathcal{S}} \mathcal{A}$이다.

대표적인 $\sigma$-대수의 예시로, 보렐 $\sigma$-대수를 살펴보자.

정의. $\mathcal{G}$가 $\mathbb{R}$의 열린 집합들의 집합족이라고 하자. $\sigma(\mathcal{G})$를 보렐 $\sigma$-대수_{Borel $\sigma$-algebra}라고 하며, $\mathcal{B}$와 같이 적는다.

보렐 $\sigma$-대수는 보렐 위계_{Borel hierarchy}를 통해서 이해할 수도 있다. $\Sigma_1$을 열린 집합들의 모임, $\Pi_1$을 닫힌 집합들의 모임이라고 하자. 다음과 같이 정의한다.

• $\Delta_n = \Sigma_n \cap \Pi_n$
• $\Sigma_{n + 1} = \lbrace S : \exists \lbrace P_n \rbrace _{n \in \mathbb{N}} \subset \Pi_n \; S = \bigcup_{n \in \mathbb{N}} P_n \rbrace$
• $\Pi_n = \lbrace P : \exists S \in \Sigma_n \; P = S^c \rbrace$

즉 $\Sigma_2 = F_\sigma$, $\Pi_2 = G_\delta$이다. 합집합을 $\exists$, 교집합을 $\forall$로 생각했을 때 산술 위계와 정의의 형태가 유사함에 주목하라.

정리. $\mathcal{B} = \Sigma_{\omega_1} = \Pi_{\omega_1} = \Delta_{\omega_1}$

증명. 생략. 하지만 직관적으로 이해할 수 있다. $\mathcal{B}$는 가산 교집합과 가산 합집합, 그리고 여집합에 대해 닫혀 있어야 하므로 모든 가산 서수 $\alpha$에 대해 $\Sigma_\alpha, \Pi_\alpha, \Delta_\alpha \subset \mathcal{B}$이다. 이 사실로부터 초한 귀납을 취해 정리를 얻는다. ■

어떤 집합 위의 대수와 예비측도라는 것이 주어졌을 때, 이로부터 측도를 정의하는 방법이 알려져 있다. 이 방법을 카라테오도리 방법_{Carathéodory method}이라고 부른다. 예비측도는 구성하기가 매우 쉽기 때문에, 이 방법을 이용하면 측도를 아주 쉽게 구성할 수 있다. 카라테오도리 방법에 대해서는 다음 글에서 알아본다.

램지 수와 무한 램지 정리

20 Feb 2025

초록. 램지 수의 정의와, 램지 수가 잘 정의됨을 보장하는 램지 정리를 살펴보고, 이를 무한 그래프로 확장한다. 또한 콤팩트성 정리를 이용하여 무한 램지 정리로부터 유한 램지 정리를 도출하는 논증을 소개한다.

도입

문제. 6개의 정점을 가지는 완전 그래프의 간선을 빨간색 또는 파란색으로 색칠할 때, 세 변의 색이 모두 같은 삼각형이 존재함을 보이시오.

일례로 다음 그림에서는 삼각형 ACF, 그리고 삼각형 BEF가 문제의 조건을 충족한다.

풀이. 임의의 정점에서 뻗어 나오는 간선의 개수는 5개이므로, 비둘기집의 원리에 따라 그중 적어도 3개는 같은 색을 가진다. 일반성을 잃지 않고, 간선 AB, AC, AD가 모두 빨간색이라고 하자. 만약 간선 BC, CD, DB 중 어느 하나가 빨간색이라면 세 변의 색이 모두 빨간색인 삼각형이 있다. 예를 들어 BC가 빨간색이라면 삼각형 ABC가 그러하다. 한편 BC, CD, DB가 모두 파란색이라면 삼각형 BCD는 세 변의 색이 모두 파란색이다. 따라서 세 변의 색이 모두 같은 삼각형이 적어도 하나 존재한다. ■

램지 정리

위 문제의 결론은 다음과 같이 표현할 수 있다. $G$가 정점수 6 이상인 완전 그래프일 때, $G$의 간선을 빨간색이나 파란색으로 칠하면 모든 간선이 빨간색인 정점수 3 이상의 부분 완전 그래프가 존재하거나, 모든 간선이 파란색인 정점수 3 이상의 부분 완전 그래프가 존재한다.

이 결론을 일반화하여, 다음 질문을 던질 수 있다. $r, b$가 임의의 자연수라고 하자. $G$가 정점수 $j$ 이상인 완전 그래프일 때, $G$의 간선을 빨간색이나 파란색으로 칠하면 모든 간선이 빨간색인 정점수 $r$ 이상의 부분 완전 그래프가 존재하거나, 모든 간선이 파란색인 정점수 $b$ 이상의 부분 완전 그래프가 존재함이 보장되는 자연수 $j$가 존재하는가?

램지 정리에 따르면 답은 그렇다이다. 구체적으로, 그러한 $j$ 중 가장 작은 수를 $R(r, b)$로 정의할 때, 다음이 성립한다.

램지 정리. 임의의 자연수 $r, b$에 대해 $R(r, b)$가 존재한다.

증명. $r + b$에 대한 귀납법으로 증명한다. 다음이 성립함을 보이면 충분한다.

\[R(r, b) \leq R(r-1, b) + R(r, b-1)\]

$R(r-1, b) = i, R(r, b-1) = j$라고 하자. $G$가 정점수 $i + j$인 완전 그래프라고 하고, $G$의 간선이 빨간색 또는 파란색으로 색칠되었다고 하자. 임의의 정점 $v \in G$에 대해, $v$와 빨간색 간선으로 연결된 정점들이 이루는 부분 완전 그래프를 $R$, 파란색 간선으로 연결된 정점들이 이루는 부분 완전 그래프를 $B$라고 하자. 다음이 성립한다.

\[|R| + |B| + 1 = i + j\]

따라서 다음 중 하나가 성립해야 한다.

1. $|R| \geq i$
2. $|B| \geq j$

1의 경우, $R(r-1, b) = i$이므로 $R$은 모든 간선이 빨간색인 정점수 $r-1$의 부분 완전 그래프를 가지거나, 모든 간선이 파란색인 정점수 $b$의 부분 완전 그래프를 가진다. 후자의 경우 $R(r, b)$의 조건이 충족되고, 전자의 경우 해당 그래프에 $v$를 추가한 그래프가 $R(r, b)$의 조건을 충족한다. 2의 경우도 마찬가지 논리가 성립한다. ■

서두의 문제는 $R(3, 3) \leq 6$임을 시사한다. 그리고 정점수가 5인 그래프 중에서는 문제의 조건을 만족하지 않는 그래프가 있음이 알려져 있기 때문에, $R(3, 3) = 6$이다. 또한 다음이 자명하다.

• $R(r, b) = R(b, r)$
• $R(r, 2) = r$

그러나 일반적인 값에 대해 램지 수를 정확히 계산하는 것은 매우 어려운 문제이다. 그래프의 정점 수에 따라 탐색해야 하는 경우의 수가 지수적 증가보다 빠르게 증가하기 때문이다. 현재 알려진 가장 빠른 램지 수 탐색 알고리즘의 시간 복잡도는 $O(c^{n^2})$이다. $R(5, 5)$의 값을 구하는 문제는 아직도 미해결 문제이며, 다만 43 이상 48 이하라는 사실이 알려져 있다. 이에 관해 다음 일화가 전해진다.

에르되시는 이런 이야기를 한 적이 있다. 우리보다 훨씬 진보한 외계 군단이 지구에 착륙해서는, $R(5, 5)$의 값을 계산해 내놓지 않는다면 지구를 산산조각낼 것이라 말했다고 상상해 보자. 에르되시가 주장하길, 이 경우에는 우리가 가진 모든 컴퓨터와 수학자를 모아들여서 계산을 시도해 봐야 한다. 그러나 만약 그들이 요구한 값이 $R(6, 6)$이라면, 에르되시 왈 이 경우에는 외계 군단을 무찌를 계획을 세우는 편이 낫다.¹

다수의 색에 대한 램지 정리

두 가지보다 많은 색을 사용하는 경우에도 램지 정리가 성립한다. 먼저 $R(n_1, n_2, \dots, n_k) = j$를, $k$가지 색을 사용하여 정점수가 $j$인 완전 그래프의 간선을 색칠했을 때 다음 중 적어도 하나가 언제나 존재하게 되는 가장 작은 $j$로 정의하자.

• 모든 간선이 1번째 색인 정점수 $n_1$의 부분 완전 그래프
• 모든 간선이 2번째 색인 정점수 $n_2$의 부분 완전 그래프
• …
• 모든 간선이 $k$번째 색인 정점수 $n_k$의 부분 완전 그래프

예를 들어 $R(3, 3, 3) = 17$임이 알려져 있다. 이는 정점수가 17 이상인 완전 그래프의 간선을 빨간색, 파란색, 또는 노란색으로 색칠하면 세 변의 색이 모두 빨간색이거나, 파란색이거나, 노란색인 삼각형이 언제나 존재한다는 의미이다.

다수의 색에 대한 램지 정리. 임의의 자연수 $n_1, \dots, n_k$에 대해 $R(n_1, \dots, n_k)$가 존재한다.

증명. $k$에 대한 귀납법으로 증명한다. 다음이 성립함을 보이면 충분하다.

\[R(n_1, \dots, n_k) \leq R(n_1, \dots, n_{k-2}, R(n_{k-1}, n_k))\]

부등식의 우변을 $j$라고 하자. $G$가 정점수 $j$인 완전 그래프라고 하고, $G$의 간선을 $k$개의 색을 사용하여 색칠하자. 잠시 $k - 1$번째 색과 $k$번째 색을 동일시하자. 그렇다면 $j$의 정의에 의해 다음 중 적어도 하나가 $G$에 존재한다.

• 모든 간선이 1번째 색인 정점수 $n_1$의 부분 완전 그래프
• 모든 간선이 2번째 색인 정점수 $n_2$의 부분 완전 그래프
• …
• 모든 간선이 $k-2$번째 색인 정점수 $n_{k-2}$의 부분 완전 그래프
• 모든 간선이 $k - 1$번째 색 = $k$번째 색인 정점수 $R(n_{k-1}, n_k)$의 부분 완전 그래프

마지막 경우를 제외하고는 $R(n_1, \dots, n_k)$의 조건을 만족하므로, 마지막 경우만 고려하면 된다. 마지막 경우가 보장하는 부분 완전 그래프를 $H$라고 하자. $R(n_{k-1}, n_k)$의 정의에 의해 $H$는 다음 중 적어도 하나를 가진다.

• 모든 간선이 $k-1$번째 색인 정점수 $n_{k-1}$의 부분 완전 그래프
• 모든 간선이 $k$번째 색인 정점수 $n_k$의 부분 완전 그래프

각 경우가 $R(n_1, \dots, n_k)$의 조건을 만족하므로, 모든 경우에 대해 $G$는 $R(n_1, \dots, n_k)$를 만족한다. ■

에르되시-라도 화살표

지금까지 우리는 간선의 색칠을 살펴 보았다. 간선은 두 정점 사이의 관계이다. 여기서 나아가, $n$개의 정점 사이의 관계를 색칠하는 상황을 떠올릴 수 있다.

논의의 편의를 위해 몇 가지 정의를 도입하자. 먼저 집합론적 자연수의 정의를 채택하여, $n = \lbrace0, 1, \dots, n-1\rbrace$로 정의한다. 또한 다음의 표기를 도입한다.

정의. $A$가 집합일 때, 다음과 같이 정의한다.

\[A^{(n)} = \{ S: S \subset A, |S| = n \}\]

즉, 자연수 $j$에 대해 $j^{(n)}$은 $_jC_n$의 각 경우를 원소로 가지는 집합이다. 예를 들어,

\[4^{(2)} = \bigg\{ \{ 0, 1\}, \{0, 2 \}, \{0, 3\}, \{1, 2 \}, \{1, 3\}, \{2, 3\} \bigg\}\]

주어진 집합을 $m$으로 분할한다는 것은, 집합의 각 원소를 $m$개의 범주 중 하나로 분류하는 것을 말한다. 예를 들어 $4^{(2)}$를 3개로 분류한 한 가지 결과는 다음과 같다.

\[\bigg\{ \big\{ \{0, 1\}, \{ 0, 2 \}, \{1, 2\} \big\}, \big\{ \{0, 3\}, \{2, 3 \} \big\}, \big\{ \{1, 3 \} \big\} \bigg\}\]

위 분할에서 $0, 1, 2$끼리 이루어진 집합은 모두 같은 범주에 속해 있다. 이것을 두고 $0, 1, 2$는 해당 분할에 대해 동질적_homogeneous이라고 한다.

다음의 표기를 정의한다. 이 표기를 에르되시-라도 화살표_{Erdős-Rado arrow}라고 부른다.

정의. $j^{(n)}$을 $m$으로 분할할 때 동질적인 $k$개의 원소가 언제나 존재할 경우 다음과 같이 표기한다.

\[j \rightarrow (k)^n_m\]

서두의 문제는 $6 \rightarrow (3)^2_2$임을 시사한다. $n = 2$인 이유는 간선이 두 정점 사이의 관계이기 때문이고, $m = 2$인 이유는 색이 두 가지이기 때문이다.

앞서 본 램지 정리에 의해 다음이 성립한다.

\[\forall k\; \exists j: j \to (k)^2_2\]

한편 다수의 색에 대한 램지 정리는 다음을 시사한다.

\[\forall k, m \; \exists j : j \to (k)^2_m\]

일반적으로 다음이 알려져 있다.

유한 에르되시-라도 정리. 임의의 자연수 $n, m, k$에 대해, 다음을 만족하는 자연수 $j$가 존재한다.

\[j \rightarrow (k)^n_m\]

무한 램지 정리

흥미롭게도 램지 정리는 $k$가 무한 기수_cardinal일 때에도 성립한다. 다음이 알려져 있다.

에르되시-라도 정리. 임의의 기수 $\lambda$와 자연수 $n, m$에 대해, 다음을 만족하는 기수 $\kappa$가 존재한다.

\[\kappa \rightarrow (\lambda)^n_m\]

특히 다음이 성립한다.

무한 램지 정리. \(\aleph_0 \rightarrow (\aleph_0)^n_m\)

즉 힐베르트 호텔의 투숙객들이 임의로 악수를 나눌 때, 서로 모두 악수를 나눈 사람들이 무한히 많거나, 서로 전혀 악수를 나누지 않은 사람들이 무한히 많다.

위 정리에 대한 증명은 필자 뇌피셜이기 때문에 오류가 있다면 알려주길 바란다.

증명. $n = m = 2$인 경우에 대해 증명한다. $G$가 크기가 $\aleph_0$인 완전 그래프라고 하자. $G$의 간선들을 빨간색 또는 파란색으로 색칠한다. $G$의 정점 $v, w$에 대해, $\overline{vw}$가 빨간색이면 $\overline{vw} \in R$, 파란색이면 $\overline{vw} \in B$와 같이 표현하자.

임의의 $G$의 정점 $v_0$에 대해, 다음과 같이 정의하자.

\[\begin{aligned} R_1 = \{ w \in G : \overline{v_0w} \in R \}\\ B_1 = \{ w \in G : \overline{v_0w} \in B \} \end{aligned}\]

$R_1 \cup B_1 \cup \lbrace v_0 \rbrace = G$이므로, $R_1$과 $B_1$ 중 적어도 하나는 무한집합이다. 만약 $R_1$이 무한집합이라면 $v_0 \in R$와 같이 표기하고, $B_1$이 무한집합이라면 $v_0 \in B$와 같이 표기하자.

$R_1$이 무한집합이라고 가정하자. 선택 공리로부터 $R_1$의 원소 $v_1$을 선택할 수 있다. 이제 다음과 같이 정의하자.

\[\begin{aligned} R_2 = \{ w \in R_1 : \overline{v_1w} \in R \}\\ B_2 = \{ w \in R_1 : \overline{v_1w} \in B \} \end{aligned}\]

$R_2 \cup B_2 \cup \lbrace v_1\rbrace = R_1$이므로, $R_2$와 $B_2$ 중 적어도 하나는 무한집합이다. 마찬가지로 $R_2$가 무한집합이라면 $v_1 \in R$, $B_2$가 무한집합이라면 $v_1 \in B$와 같이 표기하자.

$B_2$가 무한집합이라고 가정하자. $B_2$의 원소 $v_2$를 선택하여 다음과 같이 정의하자.

\[\begin{aligned} R_3 = \{ w \in B_2 : \overline{v_2w} \in R \}\\ B_3 = \{ w \in B_2 : \overline{v_2w} \in B \} \end{aligned}\]

이같은 식으로 반복함으로써 다음의 정점열을 얻는다.

\[V = \{ v_0, v_1, v_2, v_3, \dots \}\]

각 $v \in V$에 대해 $v \in R$ 또는 $v \in B$이다. $V$가 무한집합이므로, 다음 중 하나는 무한집합이다.

\[\begin{aligned} H = \{ v \in V : v \in R \} \\ K = \{ v \in V : v \in B \} \end{aligned}\]

만약 $H$가 무한집합이라면 $H$의 정점들이 이루는 완전 그래프는 간선의 색이 모두 빨간색이다. 한편 $K$가 무한집합이라면 $K$의 정점들이 이루는 완전 그래프는 간선의 색이 모두 파란색이다. 따라서 $\aleph_0 \rightarrow (\aleph_0)^2_2$이다. ■

따름정리. $A$가 $\mathbb{N}$의 무한 부분집합일 때, 어떤 $A$의 무한 부분집합 $B$가 존재하여 다음 중 하나가 성립한다.

• 임의의 $b \in B$에 대해, $c$가 $b$보다 큰 $B$의 원소라면 $b \mid c$이다.
• 임의의 $b, c \in B$에 대해, $b \nmid c, c \nmid b$이다.

증명. $k = A$로 잡고, $x < y$에 대해 $x \mid y$라면 $\lbrace x, y \rbrace$를 1번 범주로, 그렇지 않으면 2번 범주로 분류하는 분할을 고려한 뒤 $\aleph_0 \rightarrow (\aleph_0)^2_2$임을 사용한다. ■

무한에서 유한으로

흥미롭게도 콤팩트성 정리를 사용하면 무한 램지 정리로부터 유한 램지 정리를 증명할 수 있다. 즉, 다음이 성립한다.

보조정리. $\aleph_0 \rightarrow (\aleph_0)^n_m$라면, 임의의 자연수 $k$에 대해 $j \to (k)^n_m$을 만족하는 자연수 $j$가 존재한다.

증명. $n = 2$일 때를 증명한다. 간선이 $m$가지 색으로 색칠된 그래프는 다음과 같이 형식화할 수 있다. 먼저 언어 $\mathcal{L} = (V, f, 1, 2, \dots, m)$의 부호수_signature을 다음과 같이 정의한다.

• $V$는 단항 관계이다.
• $f$는 이변수 함수이다.
• $1, 2, \dots, m$은 상수이다.

$T$가 다음으로 이루어진 $\mathcal{L}$-이론이라고 하자.

• $\psi : \lnot V(1) \land \lnot V(2) \land \lnot V(m)$
• $\theta : \forall x, y \; (V(x) \land V(y) \land x \neq y) \rightarrow ( f(x, y) = 1 \lor f(x, y) = 2 \lor \cdots \lor f(x, y) = m )$
• $\phi_1 : \exists x_1, x_2 \; V(x_1) \land V(x_2) \land x_1 \neq x_2$
• $\phi_2 : \exists x_1, x_2, x_3 \; V(x_1) \land V(x_2) \land V(x_3) \land x_1 \neq x_2 \land x_2 \neq x_3 \neq x_1 \neq x_3$
• 각 $n \in \mathbb{N}$에 대해, $\phi_n$

$\psi$는 $1, 2, \dots, m$이 정점이 아니라 색을 표현한다는 의미이다. $\theta$는 임의의 두 정점 간 간선이 $1$부터 $m$ 중 하나의 색을 가짐을 의미한다. 그리고 $\phi_n$은 적어도 $n$개의 정점이 존재한다는 의미이다. 임의의 $n$에 대해 $\phi_n \in T$이므로, $T$의 모델은 무한 완전 그래프이다.

다음의 문장을 $\chi$라고 하자.

\[\exists x_1, x_2, \dots, x_k : f(x_1, x_2) = f(x_1, x_3) = \dots = f(x_{k-1}, x_k)\]

즉, $\chi$는 정점수 $k$인 동색의 부분 완전 그래프가 존재한다는 의미이다. 따라서 무한 램지 정리에 따라 다음이 성립한다.

\[T \vDash \psi\]

그리고 콤팩트성 정리에 따라 어떤 유한 부분이론 $T’ = \lbrace \psi, \chi, \phi_1, \dots, \phi_j \rbrace$가 존재하여 다음이 성립한다.

\[T' \vDash \psi\]

즉, 정점수 $j$ 이상인 모든 완전 그래프는 $\psi$를 만족한다. 다시 말해, $j \to (k)^2_m$이다. 임의의 $n$에 대해서 증명하려면 $R$을 $n$항 관계로 두면 된다. ■

¹ Joel H. Spencer (1994), Ten Lectures on the Probabilistic Method