초른의 보조정리

Zorn's lemma

ZF 하에서는 선택공리와 동치인 명제이다.

보통 부분 순서 관계를 더 보기 쉽기 때문에 부분 순서 버전으로 더 잘 알려져 있다. 부분 순서 버전을 증명해도 상집합으로 나누어 준순서 버전도 쉽게 보일 수 있다.

독일 태생의 수학자 막스 아우구스트 초른이 고안했다.

사슬이란 전순서를 이루는 부분집합을 말한다.[1]

사슬 $C$에 대해 부분집합 $S \sub C$가

를 만족한다면 $S$를 $C$의 초기 절편(initial segment)이라 한다. 편의상 이후부터는 그냥 절편이라고 칭한다.

이어서 다음 보조정리들을 먼저 보인다.

$X$가 모든 사슬이 상계를 가지는 준순서 집합이라 하고 $\mathscr C$를 $X$의 모든 사슬들의 집합이라 하자.

모든 사슬 $\forall C \in \mathscr C$에 대해 강한 상계들의 집합 $U_C$를

다음과 같이 생각할 수 있다. 해당 집합이 전부 공집합이 아니라고 가정하자. 그럼 선택공리에 의해 임의의 사슬 $\forall C \in \mathscr C$에서 $f(C) \in U_C$와 같이 해당 강한 상계 중 하나를 선택하는 함수 $f : \mathscr C \to X$가 존재한다.

이어서 집합 $\mathcal C$를 정의하자. $C$가 $\mathcal C$의 원소일 필요충분조건은 다음과 같다.

$\forall A, B \in \mathcal C$에 대해 하나가 다른 하나의 절편임을 보이자. 우선 그렇지 않은 두 $A$, $B$가 존재한다고 가정하자.

$\mathcal M$을 $A$와 $B$ 모두의 절편이 되는 모든 사슬의 집합이라 하고 $M = \bigcup \mathcal M$라 하자. $M$은 당연히 $A$와 $B$ 모두의 절편이 되며, $A$와 $B$ 모두의 절편들의 포함 순서에 대해 극대가 된다.

가정에 의해 $M$은 항상 $A$, $B$ 모두의 진절편이 되므로 $f(M)$은 $A \setminus M$와 $B \setminus M$ 모두의 최소가 된다. 우선 $f$가 항상 강한 상계를 찾으므로 보조정리 3.에 의해 $M \cup \set{ f(M) }$은 정렬집합이다.

또한 $a \leq m$이 되는 $a \in A$, $m \in M \cup \set{ f(M) }$에 대해, $m \in M$이라면 당연히 $a \in M \sub M \cup \set{ f(M) }$이 된다. 아니라면 $m = f(M)$인 경우인데, $f(M)$이 $A \setminus M$의 최소이므로 $a = f(M)$ 이거나 $a \in M$이 되며, 따라서 $M \cup \set{ f(M) }$은 $A$의 절편이다. $B$에 대해서도 비슷하게 하면 $B$의 절편임도 알 수 있다.

$M \cup \set{ f(M) }$이 $A$와 $B$ 모두의 절편이라면 극대인 $M$에 포함되어야 하나, $f(M)$이 강한 상계이므로 $f(M) \notin M$이 되어 모순이 발생한다. 따라서 $\mathcal C$의 두 원소 중 하나는 반드시 다른 하나의 절편이 된다.

이제 이런 사슬들의 합집합 $U = \bigcup \mathcal C$를 생각하자. 당연히 $\varnothing \in \mathcal C$이므로, $U$는 공집합이 아니다. 또한 보조정리 2.에 의해 $U$도 정렬집합이 된다.

$A$가 $U$의 진절편이라고 하자. 그럼 $\exists a \in U \setminus A$가 존재하며, 이를 포함하는 $\exists B \in \mathcal C$를 찾을 수 있다. 보조정리 2.에 의해 $B$는 $U$의 절편이며, 따라서 보조정리 1.에 의해 $A$, $B$ 둘 중 하나는 다른 하나의 절편이 된다. $a \in B$이므로 당연히 $B$가 $A$의 절편이 되는 것은 불가능하며, $A$가 $B$의 절편이 되는 경우만 남았으므로 $a \in B \setminus A$에 의해 $A$는 $B$의 진절편이 된다. 따라서 $f(A)$는 $B \setminus A$의 최소가 되고, $B$가 $U$의 절편이므로 $f(A)$는 $U \setminus A$의 최소도 된다. 따라서 $U$ 또한 $\mathcal C$의 원소임을 알 수 있다.

$U$ 또한 사슬이므로, $f(U)$로 강한 상계를 찾을 수 있다. 보조정리 3.에 의해 $U \cup f(U)$는 정렬집합이 된다.

$S$가 $U \cup f(U)$의 진절편이라면 $f(U)$를 원소로 가질 수 없다. 따라서 $S$는 $U$의 절편이 되며, $S = U$라면 $f(S) = f(U)$는 $\set{ f(U) }$의 최소이다. 반대로 $S \neq U$라면 이는 $U$의 진절편이므로 $f(S)$는 $U \setminus S$의 최소가 된다. $f(U)$가 강한 상계이므로, $f(S)$는 $( U \cup \set{ f(U) } ) \setminus S$의 최소도 된다. 따라서 $U \cup \set{ f(U) }$ 또한 $\mathcal C$의 원소임을 알 수 있다.

$U \cup \set{ f(U) }$가 $\mathcal C$의 원소라면 그 합집합인 $U$의 원소여야 하므로 $f(U) \in U$가 된다. 당연히 $f$가 강한 상계를 가지기 때문에 이는 모순이 된다.

가정이 틀렸으므로, $X$는 강한 상계를 가지지 않는 사슬을 적어도 하나는 가진다. 가정에 의해 모든 사슬은 상계를 가지므로, 해당 사슬의 상계는 $X$의 극대이다.

선택공리를 제외한 ZF 공리만을 가정하자.

$\mathcal A$가 공집합을 원소로 가지지 않는 집합이라고 생각하자. 이어 다음과 같은 집합을 생각하고, 이를 $X$라 하자.

$\varnothing \in X$이므로 $X$는 공집합이 아니다.

$X$에는 포함 관계에 대해 부분 순서를 줄 수 있으며, $C$를 $X$에서의 사슬이라 하자. 자연히 $\bigcup C$는 $C$의 상계이다.

$p$가 $\bigcup C$의 원소라면 이를 포함하는 적당한 $c \in C$가 존재하고, 이는 $P ( \mathcal A \times \bigcup \mathcal A))$의 원소이므로 자연히 $p$는 $\mathcal A \times \bigcup \mathcal A$의 원소가 된다. 또한 $p = (A, a)$라면 $(A, a) \in c$이므로 $a \in A$이다.

$(A, a)$, $(A, a')$이 $\bigcup C$의 원소라면 이를 각각 포함하는 $\exists c \in C$, $\exists c' \in C$가 있는데, $C$가 사슬이므로 $c \sub c'$이거나 $c' \sub c$가 된다. 적당히 $c' \sub c$라고 가정하면 $(A, a')$도 $c$의 원소이므로 $a = a'$가 보여지며, 마찬가지로 $c \sub c'$인 경우에도 비슷하게 보일 수 있다. 따라서, $\bigcup C$는 $X$의 원소이다.

모든 사슬 $C$가 $X$ 내에 상계 $\bigcup C$를 가지므로 초른의 보조정리에 의해 $X$는 극대 $f$를 가진다.

만약 $\forall a \in \bigcup \mathcal A$에 대해 $(A, a) \notin f$인 $\exists A \in \mathcal A$가 존재한다면, $A$가 공집합이 아니므로 원소 하나 $x \in A$를 뽑을 수 있다. 가정에 의해 어떤 기존의 $a \in \bigcup \mathcal A$에 대해서도 $(A, a) \in f$가 될 수 없으므로, $f \cup \set{ ( A, x ) }$는 $X$의 원소가 될 수 있다. 당연히 $f \sub f \cup \set{ ( A, x ) }$이나 $( A, x ) \notin f$이므로, 이는 $f$가 극대라는 사실에 모순된다. 따라서 이런 $A$는 존재하지 않는다.

때문에 모든 $A \in \mathcal A$가 $f$에 의해 대응되므로 $f$는 함수이며, $A \in \mathcal A$에 대해 $f(A) \in A$이므로 이는 $\mathcal A$의 선택함수이다.

선택공리와 동치인 여러 명제 중에서도 가장 써먹기 좋게(?) 가공한 형태로, 무한을 다룰 때 선택공리 자체보다도 더 자주 쓰이는 것을 볼 수 있다. 워낙 쓰기 쉬운 편인게, 많은 경우는 순서가 포함 관계로 주어지는데 이런 경우 적당히 합집합 같은 거 잡아서 상계만 보이면 마법처럼 극대의 존재가 딸려오기 때문.

막스 초른이 독일인이기 때문에 조른이 아닌 /tsɔrn/처럼 읽어야 한다. 가끔 오래된 한국어 교재에는 소른의 보조정리로 번역하기도 한다.

동명의 영화가 존재한다.