집합론, 그 두 번째 이야기 | 선택공리 ( Axiom of Choice )

앞선 글에서 우리는 선택공리라는 것을 보았다.

In the previous post, we saw an axiom named axiom of choice.

 

10. 선택 공리 Axiom of Choice $$\forall S(\varnothing\notin S\Rightarrow\exists f:S\to\bigcup S(\forall A(A\in S\Rightarrow(f(A)\in A))))$$공집합을 원소로 가지지 않는 임의의 집합 $S$에 대해 그 집합의 원소들로부터 원소를 하나씩 고를 수 있다. 10. Axiom of Choice $$\forall S(\varnothing\notin S \Rightarrow \exists f : S \to \bigcup S ( \forall A (A \in S \Rightarrow ( f(A) \in A ))))$$For any set $S$ of nonempty sets, there exists a choice function that is defined on $S$ and maps each set of $S$ to an element of the set.

 

여기서 $S$는 집합족으로 이해하는 것이 좋다. 즉, 집합을 원소로 가지는 집합이라는 뜻이다. 또, 여기서 $\bigcup S$는 그에 속하는 집합들의 모든 원소들을 합쳐놓은 집합이다. 즉, $\displaystyle\bigcup S = \displaystyle\bigcup_{A \in S} A := \{ x \mid \exists A\in S, x \in A \}$ 를 의미한다.

Here, it is better to understand $S$ as a family of sets. In other words, it is better to understand $S$ as a set of sets. In addition, $\bigcup S$ is a set of all elements of elements of $S$ i.e., $\displaystyle \bigcup S = \bigcup_{A \in S} A := \{ x \mid \exists A \in S, x \in A \}$.

 

선택공리를 쉽게 말로 풀어보자면, $S$의 모든 원소가 공집합이 아니라면 $S$의 원소가 되는 집합에서 원소를 하나씩 뽑을 수 있다는 것이다. 예를 들어, $S=\{ \{ 0 \}, \{ 0, 1 \}, \{0,1,2,3\}, \cdots \}$ 가 존재할 때, $ \{ 0 \}$ 에서 $0$, $\{ 0, 1\}$에서 $1$, $ \{ 0,1,2,3 \}$에서 $3$, ... 을 선택할 수 있다는 것이다.

To put it simply, if not all elements of $S$ are non-empty, we can choose elements one by one from the sets which are the elements of $S$. For example, if $S = \{ \{ 0 \}, \{ 0 , 1 \}, \{ 0 , 1 , 2 , 3 \} , \cdots \}$, we can select $0$ from $\{ 0 \}$, $1$ from $\{ 0 , 1 \}$, $3$ from $\{ 0 , 1 , 2 , 3 \}$, and so on.

 

이는 어떻게 보면 매우 자명한 결과같다. 물론 $S$가 유한집합이라면 이는 당연히 자명하게 참이 될 것이다. 하지만 무한집합의 경우에서는 이야기가 다르다.

In a way, this seems to be a very obvious result. Of course, if S is a finite set, it would be clearly true. However, in the case of infinite sets, it is not a trivial result.

 

어떤 종류의 집합인지 모르는 무한집합 $S$에 대해서도 무한히 많은 원소에 대해 원소를 뽑는 선택함수가 존재한다는 것은 차후의 논의에서 상당히 강력한 내용이 된다. 또한, 여러 논의에서 상당히 많이 사용되는 선택공리와 동치인 명제들이 있는데, 그 중 대표적인 명제 3가지만 소개하겠다.

For an infinite set $S$ that doesn't know what kind of set it is, the existence of a choice function for an infinite number of elements becomes quite powerful in future discussions. In addition, there are statements which are equivalent to the axiom of choice used quite often in various discussions, and we'll talk about only three of them which are representative ones.

 

1. 하우스도르프 극대원리(Hausdorff Maximal Principle; HMP) 순서집합 $(P,\leq)$가 부분순서집합일 때, $(P,\leq)$는 항상 극대사슬을 가진다. 2. 초른 보조정리(Zorn's Lemma; ZL) 부분순서집합 $(P,\leq)$의 모든 사슬이 상계를 가지면 $(P,\leq)$는 극대원소를 가진다. 3. 정렬 정리(Well Ordering Theorem) 공집합이 아닌 집합은 언제나 정렬순서를 갖는다. 1. Hausdorff Maximal Principle; HMP In any partially ordered set $(P,\leq)$, $(P,\leq)$ always has a maximal chain. 2. Zorn's Lemma; ZL If a partially ordered set $(P,\leq)$ has a property that every chain in $(P,\leq)$ has a upper bound, then $(P,\leq)$ has a maximal element. 3. Well Ordering Theorem Every non-empty set always has an well-ordering.

 

선택공리는 하우스도르프 극대원리를 함의하며, 하우스도르프 극대원리는 초른 보조정리를 함의하고 초른 보조정리는 정렬 정리를 함의한다. 마지막으로, 정렬 정리는 선택공리를 함의한다. 이에 대한 증명은 추후 포스팅하도록 하겠다.

The axiom of choice implies the Hausdorff maximal principle, the Hausdorff maximal principle implies the Zorn's lemma, and the Zorn's lemma implies the well ordering theorem. Finally, the well ordering theorem implies the axiom of choice. We will post the proof of them later.