선택공리(Axiom of Choice)

수학에서는 참인 명제를 바탕으로 다른 참인 명제를 연역논증을 통해 증명합니다. 얻게 된 새로운 명제들을 쌓아 올려 중요도가 높은 명제인 정리를 증명하기도 하고 다른 수학 분야와 연관성을 찾기도 합니다. 이러한 논증을 위해서는 누구나 모두 동일하는, 참이라는 명제가 기반으로서 필요합니다. 그러한 명제를 '공리'라고 합니다. 기하학의 공리에는 예컨대 '모든 직각은 합동이다'나 '선분을 확장하면 직선이 된다' 등이 있습니다. 이들은 수학을 하는 사람들이라면, 증명없이 참이라고 받아들이자는 것입니다.

 

집합론은 모든 수학 과목을 다룸에 있어 초석이 되는 집합이나 명제, 논리에 대한 공리를 만드는 틀을 다루는 과목입니다. 그렇기에 공리들을 계속 만들어가는데, 선택공리라는 것이 등장합니다. 선택공리는 ZFC 공리계의 'C'에 해당하는 핵심으로, 얼핏 보면 '무한'이라는 요소를 제외하고는 우리의 직관에 매우 잘 들어맞습니다. 또한 '무한'히 그러한 '선택' 작업을 한다고 해도 선택공리가 거짓이라는 의심이 쉽사리 들지는 않는다는 점에서 선택공리 자체가 우리의 직관과 크게 충돌한다 보기는 어렵습니다.

 

그런데 문제는, 만일 우리가 선택공리는 받아들이면 하우스도르프 극대원리, 초른의 보조정리, 정렬이론(Well-ordering Theorem)을 정확히 증명가능합니다. 그리고 이들은 전부 '필요충분조건'입니다. 문제는 정렬이론이 우리의 직관과 들어 맞지 않는다는 점입니다. 정렬이론은 존재성만을 보장하는데, 그것이 무엇인지까지 알기는 어렵다는 특징을 가집니다. 마치 고등학교 수학에서 중간값의 정리(사잇값 정리)나 평균값의 정리라던지, 해석학의 볼차노-바이어슈트라스 정리(Bolzano-Weierstrass theorem)^[각주:1], 논리학에서의 괴델의 불완정성 정리^[각주:2]와 비슷합니다. 있긴 있는데, 뭔지까지 구체적으로는 특정하지 못한다는 명제라는 뜻입니다.

 

그래서 집합론의 마지막 부분에 있는 이 네 명제를 연구하는 작업은 거의 순도 99%의 논리와 증명으로 점철되어 있고 난이도도 위상수학 뺨때릴 수준으로 상당히 높습니다.^[각주:3] 그래도 차근차근 하나씩 격파해 봅시다.

---

1. 선택공리

 

선택공리를 표현하는 방법은 여러가지가 존재할 수 있습니다. 제가 참고한 서적들만 해도 본질은 같으나 포장하여 표현하는 방식들이 여러가지입니다. 나름대로 간단한 버전을 소개할 예정입니다.

 

 

정의($S.T$) 5-6) 선택공리(Axiom of choice)
원소들이 공집합이 아닌 집합들 $A_i$ 로 이루어진 집합족을 $\mathcal{S}$ 라 하자.^[각주:4] 그러면 모든 $A_i\in\mathcal{S}$ 에 대하여 $A_i\longmapsto f(A_i)\in A_i$ 로 정의되는 함수
$$f:\mathcal{S} \longrightarrow \bigcup_{A_i\in\mathcal{S}} A_i$$ 가 존재하고, 이를 '선택함수(choice function)'이라 한다.

 

선택공리가 무엇을 의미하는지를, 정의를 통해 그대로 해석해봅시다. 이는 어떤 공집합이 아닌 집합들로 이루어진 집합족(따라서 이 집합족도 공집합은 아님)에서, 특정 집합(= $A_i$ 에 대응됨) 하나를 선택하게 되면, 그 집합 내에서 대표 원소(= $f(A_i)$ 에 대응됨) 를 무조건 뽑을 수 있다는 것을 의미합니다.

 

 

 

예시를 통해 생각해봅시다. 예를 들어 귤, 수박, 딸기들로 이루어진 주머니 $A_1,A_2,A_3$ 가 있다고 해봅시다. $A_i$ 가 공집합이 아니라는 조건만 있고, 유한집합이어야 한다는 조건은 없으니 $A_i$ 의 원소의 개수(= 각 과일들의 개수)에는 특별한 조건이 없습니다.^[각주:5] 예시를 들기 위해 전국 8도에서 대표로 과일을 하나씩 보냈다고 해봅시다. 예를 들어, 귤에는 경기귤, 강원귤, 충청귤, 전라귤, 경상귤, 평안귤, 황해귤, 함경귤이 있고 딸기 주머니에도 경기딸기, 강원딸기, $\cdots$ , 함경딸기가 있으며, 수박도 마찬가지입니다. 마지막으로, 세 주머니는 모두 다시 큰 밀봉된 상자에 들어가 우리의 선택을 기다리고 있습니다.

 

이때 우리는 심사위원입니다. 심사위원이 해야 할 목표는 다음과 같습니다.

 

밀봉된 상자를 열어, 세 주머니를 하나씩 선택한 뒤, 그 주머니에서
제일 맛있는 과일을 골라라.
즉 귤, 딸기, 수박에서 각각 가장 맛있는 도(都)를 골라라!

 

 

대응관계는 다음과 같습니다.

 

밀봉된 큰 상자 = 집합족 = $\mathcal{S}$
주머니들 = 집합족의 원소들 = 집합 $A_i$ 들
우승한 도(都)의 귤, 딸기, 수박 = $f(A_i)$ 들

 

 

즉 여기선 귤 주머니가 $A_1$, 수박 주머니는 $A_2$, 딸기 주머니는 $A_3$ 이 됩니다. 그리고 예컨대 귤은 충청도가 제일 맛있었으면 $f(A_1)$ 은 충북귤, 딸기는 함경도가 1등이었다면 $f(A_2)$ 는 함경딸기가 되는 것이며 수박은 경상도가 최고였다면$f(A_3)$ 는 경상수박인 것이죠.

 

선택함수가 존재한다는 것은 이 심사위원이 임의의 과일이 들어있는 주머니를 열었을 때마다 하나씩 원소를 뽑는 행위, 즉 1등의 과일을 하나 가려낼 수 있음을 의미합니다. 예를 들어 귤 주머니에서 8도의 귤을 다 먹기만 하고 1등 도를 결정하지 않는 경우 따위는 생각하지 않는다는 것이죠.

 

선택함수의 꼴을 보면, 

$$f:\mathcal{S} \longrightarrow \bigcup_{A_i\in\mathcal{S}} A_i$$

 

입니다. 여기서 공역은 그러면 무엇일까요? 바로 모든 과일들을 가리킵니다. 즉 $\displaystyle \bigcup_{A_i\in\mathcal{S}} A_i$ 는 여기서 전국 8도의 귤, 수박, 딸기들에 해당하는 것입니다.^[각주:6] 위에서 과일이 주머니에 몇 개씩 들어있는지가 중요하지는 않다고 말했었지요? 실제로 만일 귤, 딸기, 수박 중 적어도 하나가 무한개 존재한다면 당연히 공역의 원소 개수도 무한개입니다. 만일 $A_i$ 들의 원소 갯수가 모두 유한하다면 단순히 $\left| \displaystyle \bigcup_{A_i\in\mathcal{S}}^{n} A_i \right|=\left| A_1 \right|+\cdots \left| A_n \right|$ 의 기수 관계가 성립할 것이구요.

 

그렇다면 $f(A_i)$ 란 어느 한 종류의 과일 중 제일 맛있는 도의 그 과일을 뜻합니다. 예컨대 위에서 $f(A_2)$ 는 제가 함경딸기라고 했고, 당연히 함경딸기도 $24$ 개의 과일 중 하나이니 공역 $\displaystyle\bigcup_{A_i\in\mathcal{S}}^{3} A_i$ 에 들어가 있어야 하는 것이죠. 그리고 딸기 주머니 $A_2$ 에 함경딸기가 무조건 포함되어 있어야 하니, $f(A)\in A$ 라는 관계가 성립하는 것입니다.

 

이보다 친절하게 설명할 수가 없네요. 정리하면 선택함수의 의미는 다음과 같습니다. 모든 주머니들이 모여 있는 큰 상자 $\mathcal{S}$ 에서 임의의 주머니 $A_i$ 를 고르고, 그 주머니에서 대표 원소를 하나 선택한다는 것입니다. 이 함수가 존재함을 공리로 잡는다는 것은, 이 행위가 무조건 가능하다고 단정을 하는 겁니다. 당연히 되는거 아니냐? 싶은데 핵심은 $i$ 의 값이 유한하지 않을 때, 다시 말해 과일의 종류가 무한개로 있어서 주머니의 갯수가 무한개에 해당한다고 할지라도, 기수로 표현하자면 $\left| \mathcal{S} \right|$ 가 초한기수일 때도, 선택함수가 존재한다고 믿자는 것입니다.

 

이 믿음을 받아들이면 뒤에서 하우스도르프 극대원리, 초른의 보조정리, 정렬이론이 참임을 보일 수 있게 됩니다.

 

 

 

1. 유계인 실수열은 반드시 수렴하는 부분수열을 갖는다.   [본문으로]
2. 모순 없이 잘 만들어진 공리계에서 반드시 증명 불가능한 명제가 적어도 하나 존재한다. [본문으로]
3. 학부 1학년 수준에서는 이들을 엄밀히 증명하는 것보다는 유도된다는 논리 관계나 명제 자체 등이 더 중요한 편입니다. [본문으로]
4. 쉽게 말해 이 집합족의 원소는 집합이고, 그 집합들은 공집합이 아니라는 뜻 [본문으로]
5. 이때 실제로 귤, 수박, 딸기가 각각 몇 개씩 들어있는지는 중요하지 않습니다.각각의 $A_i$ 들의 기수가 같다는 조건도 없으니, 예컨대 귤은 무한개가 있고, 딸기는 3개가 있고, 수박은 500개가 있는 경우도 가능합니다. [본문으로]
6. 그러니까 위의 예시에서 공역의 원소 갯수는 $3\times 8 = 24$ 입니다. [본문으로]