선택공리(Axiom of Choice)의 동치명제(1)

할 일 없는 토요일 오후.. 오랜만에 수학 포스팅이나 하련다.

지난 학기 집합론을 수강하면서 가장 재밌게 배웠던 부분이 이 선택공리에 관한 내용이었다.

영어로는 Axiom of Choice. 뭔가 멋있으면서도 낭만적인 분위기가 풍겨오지 않는가......

이런 노래 가사도 있더라. You are my axiom of choice.

줄여서는 AC라고 많이 쓴다. 카이스트 수학동아리를 떨어진 분노의 KSA 수학도들이

만든 그룹의 이름이기도 하다. 카이스트 수학문제연구회 뻐큐머거.

선택공리 명제는 이전 포스팅에서 잘 설명해 놓았다.

링크 - 집합론의 공리(2) :  http://blog.naver.com/tonyslee93/120142391360

선택공리를 사용하기 쉽도록 여러가지 다른 형태로 바꾸어보면

[정리]아래 명제들은 동치이다.

(a) Axiom of Choice
(b) $<Y_i | i\in I >$ 가 각 $i∈I$ 에 대해 $Y_i≠Ø$ 이면 $\prod_{i∈I} Y_i≠Ø$ 이다.
(c) $Ø∉S$ 이면 there exist function $f$ on $S$ s.t. $f(X)∈X$ for all $X∈S$. 이 함수 $f$를 $S$의 choice function이라고 한다.

이 명제들이 동치인 것은 각각의 정의를 떠올려보면 쉽게 알 수 있다.

그런데 수학에서 이 선택공리를 채택하고 적용할 때, 이러한 원래 선택공리의 형태보다 더 많이 쓰이는 동치명제가 있는데 그것이 바로 Zorn's Lemma 이다. 특히 대수학에서 선택공리를 사용할 때에 이 형태로 쓰는 경우가 훨씬 많다.

[AC]Zorn's Lemma

순서집합 $X$에서 모든 chain 이 upper bound 를 가지면 $X$는 maximal을 갖는다.

AC의 또 하나의 동치명제로 Well-ordering principle이 있다.

[AC]Well-ordering principle

모든 집합은 well-order를 갖는다.

즉

[정리]아래 세 명제는 (ZF집합론에서) 동치이다.

(a)Axiom of Choice
(b)Well-ordering principle
(c)Zorn's Lemma

Well-ordering principle를 이용해 Axiom of Choice를 보이는 것은 간단하다.

[증명] Well-ordering principle -> Axiom of Choice

    집합 $A$를 잡고, $S$를 $A$의 분할이라고 하자. $A$의 well-order를 $<$라고 하자. $S$의 원소 $X$는 공집합이 아닌 $A$의 부분집합이므로 $(A,<)$에서 least를 단 하나 갖는다. 그러므로 집합 $C=\{ x|X∈S, x$ is a least of $X \}$가 대치공리에 의해 존재한다. 이것이 대표집합임을 보이자. 각 $X∈S$ 에 대해서 $X$의 least $x$가 $C$에 속하는 것은 자명하다. 그 외에 $X∩C$의 원소가 없음을 보이자. 만약 $y∈X∩C$ 라면 $y∈C$ 이므로 어떤 $Y∈C$ 가 존재하여 $y$가 $Y$의 least가 된다. $y$가 $x$가 아니라면, $Y$가 $X$가 아닐 것이다. 그런데 $y∈X∩Y$ 이므로 $S$가 분할이라는 것에 모순이 된다. 즉 $C$는 $S$의 대표집합이 된다.

이번에는 Axiom of Choice으로부터 Zorn's Lemma를 증명해 보자. 이 경우는 조금 많이 nontrivial 하다.

[증명] Axiom of Choice -> Zorn's Lemma

    $(X,≺)$가 모든 chain이 upper bound를 갖는 순서집합이며, maximal을 갖지 않는다고 가정하자.

    $X$의 모든 chain $C$에 대해서 $\hat{C} = { x∈X | y≺x \forall y∈C }$ 라고 하면, $C$가 upper bound를 가지며 $X$의 maximal이 없다고 가정했으므로 $\hat{C}$는 공집합이 되지 않는다. 이제 $Ω$를 $X$의 Hartogs 수라고 하자.

     $S=P(X)-\{Ø\}$로 두고 위의 선택공리 (c) 형태를 적용하면, $S$의 choice function $h$를 얻는다.  -> ## 이 부분이 바로 Axiom of choice 를 사용하는 부분이다! ##

    이제 함수 $g : \bigcup_{α<Ω} X^α\to X$ 를 $V∈X^α$ 에 대해 $ran V$ 가 chain 이면 $g(V)=h(\hat{ranV})$으로, 그렇지 않을 경우는 $g(V)=g(Ø)$로 정의하자. Recursion 1에 의해 함수 $f : Ω\to X$가 유일하게 존재하여 $f(α)=g(f ↾α) \forall α<Ω$ 가 성립한다.

    Claim : 모든 $α<Ω$에 대해 $f[α]$ 는 chain 이다.

    $f[0]=Ø$는 chain 이다. $f[α]$가 chain 이라고 가정하면 $f[α+1]=f[α]∪f(α)$ 이고 $f[α]≺f(α)$ 이므로 $f[α+1]$도 chain 이 된다. $α$가 limit ordinal일 경우 모든 $β<α$에 대해 $f[β]$가 chain 이라면 $f[α]=\bigcup_{β<α} f[β]$ 또한 chain이 되는데, 그 이유는 임의의 두 $x,y∈f[α]$ 에 대해서, $x∈f[β_1], y∈f[β_2]$인 $β_1 , β_2<α$가 존재하고, $β_1 <β_2$이라면 $f[β_1]⊆f[β_2]$이므로 $x,y∈f[β_2]$이 되어 $x,y$의 순서를 정할 수 있기 때문이다.

    이제, $β<α$라고 하면 $f(β)∈f[α]$이고,$f[α]≺f(α)$ 이므로 $f(β)≺f(α)$가 성립한다. 즉 $f$는 increasing이므로 injective이다. 그러므로 $f : Ω\to X$ 가 injective function이므로, $Ω$는 $f[Ω]⊆X$ 와 cardinality 가 같다. 이것은 $Ω$가 Hartogs 수라는 가정에 모순된다. 그러므로 $X$는 maximal을 갖는다.

사실 이 증명을 이해하려면 Hartogs수가 뭔지, $X^α$는 뭘 말하는 건지, 또 ordinal은 뭔지 먼저 알아야 한다. 차후에 포스팅하겠다. 근데 지금 본인도 배운지 오래되어서 잘 모르겠으므로 얼마나 걸릴 지 모르겠다...


그럼 다음 포스팅에서는 Zorn's lemma에서부터 Well-ordering principle을 증명해 세 명제가 동치임을 보이고, Zorn's lemma가 어디서 사용되는 예를 소개하겠다. 마지막으로 과연 Zorn이 누군가 하여 Zorn에 대해서 검색해 보았다.

http://en.wikipedia.org/wiki/Max_Zorn

Zorn's lemma 답게 생겼다. 독일 출신 미국인 수학자라고 한다.


증명 출처 : 집합론 입문 (최창선 저)