선택 공리 📂집합론

선택 공리

Axiom of choice

공리 1

$$ \forall U \left( \emptyset \notin U \implies \exists f : U \to \bigcup_{X \in U \\ f(X) \in X } U \right) $$ 모든 공집합이 아닌 집합들의 집합 $U$ 에 대해 $U$ 의 모든 원소로부터 원소 하나씩을 선택하는 선택 함수 $f$ 가 존재한다.

설명

선택 공리는 가령 다음과 같은 집합의 집합 $U$ 가 있을 때, 그 원소인 집합에서 원소 하나을 뽑는 함수 $f$ 가 존재함을 보장해준다. 가령 다음의 예를 생각해보자:

$$ U = \left\{ \left\{ \pi , 1/2 \right\} , \left\{ e , -42 \right\} , \left\{ 3/2, 1/7 , \sqrt{2} \right\} \right\} \\ f(X) = \begin{cases} \pi &, X = \left\{ \pi , 1/2 \right\} \\ e &, X = \left\{ e , -42 \right\} \\ \sqrt{2} &, X = \left\{ 3/2, 1/7 , \sqrt{2} \right\} \end{cases} $$ 물론 치환 공리꼴에 의해 $f$ 의 치역 $f(U) = \left\{ \pi , e, \sqrt{2} \right\}$ 가 존재함도 잘 알 수 있다. 진짜 질문이 되는 것은 ‘이게 왜 공리여야할만큼 당연하지 않은가’다. 위 예시를 잘 보면 $f$ 는 주어진 유한 집합에서 무리수만을 선택했는데, 주어진 $U$ 가 무엇이든간에 이런 $f$ 가 잘 존재해줄지는 전혀 별개의 이야기다.

조금 더 어려운 예로써 실수 집합 $\mathbb{R}$ 에 대해 $U = 2^{\mathbb{R}} \setminus \emptyset$ 을 생각해보자:

  • 실수는 항상 순서의 비교가 가능하기 때문에 대강 그 최소값인 $\min$ 이 선택 함수가 될 것 같지만, 구간 $(0,1] \in 2^{\mathbb{R}}$ 의 경우엔 최소값이 존재하지 않아 선택 함수가 되지 못한다.
  • $\inf$ 은 $0 \notin \inf (0,1]$ 이므로 말할 것도 없이 선택 함수가 못 된다.
  • 구간의 길이? $2^{\mathbb{R}}$ 에는 구간이 아닌 집합도 존재한다.
  • $X$ 가 유한집합이면 $0$ 에 가장 가까운 수를 뽑고 무한집합이면 정수 집합 $\mathbb{Z}$ 와 교집합을 취해 $0$ 에 가장 가까운 수를 뽑는 $g(X) = \begin{cases} \argmin_{x \in X } | x | &, |X| < \infty \\ \argmin_{x \in X \cap \mathbb{Z}} |x| &, | X | = \infty \end{cases}$ 는? $\mathbb{R} \setminus \mathbb{Z}$ 에 대해 정의되지 못한다.

$g$ 정도면 충분히 억지를 부린 것 같은데도 선택 함수가 되지 못했다.

보다시피 $U = 2^{\mathbb{R}} \setminus \emptyset$ 만 돼도 선택 함수를 찾는 것은 생각보다 쉬운 일이 아니다. 하지만 선택 공리는 선택 함수가 어떻게 생겼는지는 몰라도, 일단 존재할 것이라고 못 박는다. 구체적인 $f$ 를 제안하지도 못하면서 존재한다고 단언하는 게 논리적으로 얼마나 대담한 짓인지 생각해보자. 선택 함수의 존재성은 과연 당연한가? 공리 없이도 자신 있게 선택 함수가 존재하노라고 말할 수 있겠는가? 물론 이 포스트를 읽고 있는 독자 중 누군가는 $2^{\mathbb{R}} \setminus \emptyset$ 를 보자마자 기가 막힌 아이디어를 떠올렸을지도 모른다. 하지만 이것은 광활한 수학의 세상에서 아주 작고 작은, 단 하나의 예시에 지나지 않는다. 제 아무리 천재라도 온갖 기상천외한 집합이 주어질 때마다 선택 함수를 찾아낼 용기는 없을 것이다. 어지간하면 선택 공리의 필요성을 인정하고 받아들이도록 하자.

동치 1

한편 선택 공리와 동치로써 다음의 정리들을 소개한다.

  • [1] 하우스도르프의 극대원리: 부분 순서 집합 $(A, \le)$ 의 전순서 부분 집합의 족을 $\mathcal{F}$ 고 할 때, $\mathcal{F}$ 에서의 포함관계 $\subset$ 을 순서로 갖는 부분 순서 집합 $(\mathcal{F}, \subset)$ 에 극대 원소가 존재한다.
  • [2] 초른의 보조정리: 부분 순서 집합 $(A, \le )$ 이 사슬 상계를 가지면 $A$ 의 극대 원소가 존재한다.
  • [3] 정렬 원리: 공집합이 아닌 임의의 집합은 정렬 순서를 갖는다.

선택 공리는 하우스도르프 극대 원리를, 하우스도르프 극대원리는 초른의 보조정리를, 초른의 보조정리는 정렬 원리를, 정렬 원리는 선택 공리를 함의한다. 이 정리들은 표현과 용도가 조금 다를 뿐 선택 공리와 동치다. 용도가 다르다는 말은 단지 어떤 것을 증명할 때 선택 공리를 사용하되 그에 딱맞는 동치를 사용하는 것에 지나지 않는다. 특히 이름 높은 것은 초른의 보조정리로, 여러가지 분야에서 그 이름 그대로 자주 쓰인다.


  1. 이흥천 역, You-Feng Lin. (2011). 집합론(Set Theory: An Intuitive Approach): p289. ↩︎

댓글