[수학의 부스러기] 2. 선택공리

우리는 살면서 여러가지 호기심에 사로잡히게 됩니다. Why?라는 물음을 수없이 던져본 적이 한번쯤 있으실 것입니다. 계속 물음을 던지다 보면,,, 가장 그 밑바닥엔 무엇이 있을까? 이 물음은 수학에서도 굉장히 중요한 토픽 중 하나로, 필연적으로 우리는 묻지말고 인정해야할 몇가지 것들을 정해두어야만 한다는 사실에 직면하게 됩니다. 과학 혹은 신학에서도 비슷한 물음이 있습니다. 이 우주는 누가 만들었을까? 신이 만들었다면 그 신은 누가 만들었을까? 신2가 만들었다면 그 신2는 누가 만들었을까… 확실한건 한가지입니다. ‘아무 것도 없던 적은 없다’는 것입니다. 만약 아무 것도 없던 적이 있다고 가정하면, “Nothing produces nothing.”임이 명백하므로 모순입니다. 데카르트(R. Descartes)가 말했듯이, 우리는 생각하고, 따라서 존재하기 때문입니다. 크리스챤들은 예수라고 불리우는 유일신이 항상 존재해왔다고 생각합니다. 사실 신2, 3, 4…가 계속 존재하면 좀 덜 깔끔해보이는 건 사실이지만…

각설하고, 수학은 왜?라는 물음의 끝을 상정하기로 합니다. 많은 사람들이 수학 이론들에 대해 합의를 보기 위해서 기초적인 약속을 하기로 정한 것입니다. 그것을 공리(Axiom)라고 합니다. 수학자들은 몇 되지도 않는 공리들 위에서 우선적으로 집합론을 만들고, 그것을 기초로 하여 여러가지 수학 이론들을 펼쳐 보이기 시작합니다. 공리의 예에는 다음과 같은 것들이 있습니다.

The Axiom of Existence : $\phi$ (공집합)이 적어도 하나 존재한다.
The Axiom of Extensionality : $X$ 의 원소가 모두 $Y$ 의 원소이고, $Y$ 의 원소가 모두 $X$ 의 원소이면, $X=Y$ 이다.
(기타등등…)

이와 같은 사실들에 대해서는 왜 그러냐? 라는 질문을 하지 않고 인정하기로 약속 합니다. 물론 수학은 자유롭기 때문에, 이런 약속을 인정하지 않아도 됩니다. 하지만 수학을 하기 위해서는, 저것들 말고 다른 것들이라도 최소한으로 약속을 정해놓기는 해야하겠죠. 참고로 저기 공집합이 적어도 하나 존재한다고 적어놓은건, 공집합이 여러개 존재할 수 있다는 말이 아니라 공집합이 유일하게 존재하는 것을 수학적으로 ‘증명’할 수 있다는 사실을 강조하기 위해서 입니다. 즉, 공집합이 왜 유일한가?는 대답할 수 있는 내용이기 때문에 공리일 필요가 없는 것입니다.

사실 이 글을 쓰는 이유는 이와 같은 공리들 중에 상당히 특이해 보이는 것이 하나 있기 때문입니다. 이것은 인간이 할수있는 ‘논의’라는 것의 태생적 한계(?)를 단편적으로 보여주는 공리라고 할 수도 있습니다.

Axoim of choice : $\phi$ 이 아닌 집합들에서 원소를 하나씩만 뽑아서 새로운 집합을 구성할 수 있다.

다음 사례(?)를 보면서 이 공리를 음미해보도록 하죠.

『학급 및 학생수가 많기로 유명한 오유고등학교. 수학 선생님인 힘센과자는 오늘도 자율학습 시간에 아이들 관리할 생각에 머리가 아파옵니다. 악플다는데 신이난 곰팅이랑 한쪽에서 씨크하게 플래쉬 보고있는 Qoo에 바보 운영자까지…
그래서 힘센과자는 한가지 허접한 묘책을 생각해냅니다. 각 학급에서 한명씩 반장을 뽑아 나머지 아이들을 조용히 시키는 것입니다. 그런데 오유고등학교 학생들은 상당히 비협조적이어서, 그냥 학급에서 알아서 선거해서 뽑아라 하면 도저히 반장이 뽑히지 않는다고 합니다.
때문에 선생님이 직접 학급마다 반장을 지정해서 뽑을 필요가 있었습니다. 이윽고 힘센과자는 스피커를 통해 각 학급에 방송을 합니다.
“자, 이제 각 학급에서 내가 지시하는 사람은 반장딱지 붙이고 교무실로 오기 바랍니다.”
과연 힘센과자는 반장들을 무사히 불러 모을 수 있을것인가…』

설명의 편의를 위해, 한명의 학생이 여러 반에 속해있을 수도 있다고 합시다. 상상만해도 상황이 끔찍하죠…; 한 학생이 이반, 저반 죄다 돌아다니고 있으니…

하지만 그래봤자 빈깡통이 아니면 한 방울씩은 들어있을테니 걔네들 꺼낼 수 있는건 당연한거 아닌가라고 생각하실 지 모르겠으나, 각 깡통에 한방울 씩 있다는 것 자체와 그것들을 뽑아 모은다는 것은 약간 다른 문제라는 것을 눈치채는 것이 이 글의 첫번째 목표입니다. 이해를 돕기위해 다음과 같은 예를 봅시다.

$A$ 를 $\{ a,b,c\}$ 라고 합시다. 이 $A$ 의 원소들을 특징짓는 5개의 그룹이 있는데, 그것을 각각

$X_{1} = \{a\}$

$X_{2} = \{b\}$

$X_{3} = \{a,c\}$

$X_{4} = \{b,c\}$

$X_{5} = \{a,b,c\}$

라고 합시다.

이제 반장을 선택하는, 선택함수(choice functlon)을 다음과 같이 정의합니다.

$\displaystyle f:\{1,2,3,4,5\}\rightarrow\bigcup_{i=1}^{5}X_{i}$
(여기서 $\displaystyle \bigcup_{i=1}^{5}X_{i}$ 라는 것은 저 $X_{1}$ , $X_{2}$ .. $X_{5}$ 의 원소들을 전부 합해놓은 전교생을 뜻합니다. 이 경우 처음에 말한 집합 A가 되겠네요.)

(단, $f(1)=a\in X_{1}$
$f(2)=b\in X_{2}$
$f(3)=a\in X_{3}$
$f(4)=c\in X_{4}$
$f(5)=a\in X_{5}$ )

함수값(저번 글의 함수에 대한 설명에서 두번째 좌표를 의미합니다. 즉, 함수값으로 1~5반의 반장을 뱉어내는거죠.)을 일일이 다 써놓긴 했지만, 어쨌든 우리는 이 $f$ 를 통해서 학급 $X_{i}$ 에서 반장을 한명씩 뽑을 수 있습니다.
여기까지만 가능하다면, 이제 “모으는”것은 일도 아니죠. 만약 우리가 R(representatives의 약자로 썼습니다.)이라는 집합을 다음과 같이

$\displaystyle R=\{ f(x)\in\bigcup_{i=1}^{5} X_{i} : x\in\{1,2,3,4,5\}\}$
(표기를 해석하자면 R은 $f(1)$ , $f(2)$ , .. $f(5)$ 를 전부 모은 집합)

로 정의한다면, R이 곧 우리가 원하는 ‘반장들의 모임’이 됩니다.

하지만 ‘학급 및 학생수가 많기로 유명한 오유 고등학교’라고…ㅠ_ㅠ

슬슬 집합의 크기를 늘려 테스트를 해보도록 합시다. 우선 전교생으로 둘 자연수 집합 $\mathbb{N}=\{1,2,3,4, ...\}$ 를 생각합니다. 무한집합이 나왔다고 겁먹으실 필요는 전혀 없습니다. 이제 학급을 3개정도로 나눠볼까요?

$X_{1} = \{1,2,3\}$

$X_{2} = \{2,3,5,6,7,23,25,61346\}$

$X_{3} = \{1,3,5,7,9,11,13,15, ... \}$
(3반은 홀수 전체의 집합인 무한집합임에 주의하시기 바랍니다.)

뭐 복잡할것도 없습니다. 우리는 앞에서의 요령과 마찬가지로, 선택함수를 다음과 같이 정의하면 됩니다.

$\displaystyle f:\{1,2,3\}\rightarrow\bigcup_{i=1}^{3}X_{i}$

(단, $f(1)=3\in X_{1}$
$f(2)=25\in X_{2}$
$f(3)=7\in X_{3}$ )

흠… 이번엔 학급을 조금 늘려볼까요?

$X_{1}=\{1\}$ , $X_{2}=\{2\}$ , $X_{3}=\{3\}$ , … 즉, 일반적으로 $i$ 반을 $X_{i}=\{i\}$ 라고 합시다. 자연수만큼 무한히 많은 반들이 만들어진 것입니다.

조금만 머리를 굴리면 복잡할게 전혀 없습니다.

$\displaystyle f:\{1,2,3, ...\}\rightarrow\bigcup_{i=1}^{\infty}X_{i}$ (다시말해, $\displaystyle f:\mathbb{N}\rightarrow\bigcup_{i\in\mathbb{N}}X_{i}$ )

(단, $f(i)=i\in X_{i}$ )

앞에서는 일일이 함수값을 다 썼지만… 이 경우는 학급이 무한히 많으니 그렇게 쓰기는 불가능합니다 ㅡ 이게 바로 인간이 유한한 존재이기때문에 어쩔수 없이 직면하는 한계이고, 그것을 극복하기 위한 첫번째 노력으로 다음과 같은 공리를 내겁니다.

The Axiom of Infinity : Inductive set(귀납적 집합?)이 적어도 하나 존재한다.

이것으로 자연수 집합을 만들어낼 수 있게 되었고(자세한 설명은 생략하겠습니다.) 우리는 위와 같이 무한한 함수값을 한방에 써버릴 수 있게 된 것입니다.

그런데 이제 문제점이 슬슬 느껴지시는지요? 만약 학급을, $\mathbb{N}$ 의 부분집합 전체(!)를 통해 학급을 정한다면 어떻게 하시겠습니까? 그러니까 학급에는 $\{1,4,9,16,...\}$ 도 있고, $\{23,51346,13473472,234572546,2345234234623462346, ...\}$ 도 있고 별 희한한 자연수의 부분집합 전부가 학급이 될테지요…-_-; ’1. 집합의 크기’에서 말씀드렸듯이 이 학급들을 전부 모으면 $2^{\mathbb{N}}$ 이라 쓰고, 실수집합 $\mathbb{R}$ 과 크기가 동일합니다. 이제 학급이 얼마나 많은 것까지 생각할 것인지 압박이 오시나요?

한번 시도는 해봅시다. $2^{\mathbb{N}}$ 이 $\mathbb{R}$ 과 크기가 같댔으니까, 학급들의 이름은… 실수 번호를 붙이면 빠짐없이 구분이 되겠고… (예를들어 $\pi$ 반 $X_{\pi}$ 같이)우선 함수를 이런식으로…

$\displaystyle f:\mathbb{R}\rightarrow\bigcup_{i\in\mathbb{R}}X_{i}$

그런데 함수값, 그러니까 반장을 어떻게 뽑는다?

여기서 짚어볼 자연수의 중요한 성질이 하나 있습니다. Well-ordered(잘 정렬된?)가 바로 그것입니다. 내용인 즉슨, 자연수 부분집합은 최소 원소를 가진다는 겁니다. 예를들어 홀수집합의 최소값은 1이고, 짝수집합의 최소값은 2이고… 아무리 거지같은 자연수의 부분집합이 있어봤자 거기에 최소값이 반드시 있습니다. 아… 그렇다면…

(단, $f(i)=\min (X_{i})\in X_{i}$ )

요러한 한방으로 선택함수가 말끔하게 정의되고, 고로 우리는 반장을 무리없이 뽑을 수 있게 되는 것이지요.

이제 쬐끔 더 어려운걸 해볼까요? 정수 집합 $\mathbb{Z}$ 를 전교생 집합으로 놓고, 방금과 같이 이것의 모든 부분집합을 생각하여 똑같은 방법을 쓸수 있나 봅시다. 정수 부분집합에 항상 최소원소가 있던가? 만약 어떤 학급이 $\{ ... -3,-1,1,3,5, ...\}$ 와 같은 정수 홀수집합이면, 최소값 같은게 없어서 반장 선출이 난처해집니다.

하지만 우리는 저번에 배웠듯 정수 집합과 자연수 집합이 일대일 대응관계에 있어서, 정수들 각각에 자연수 이름을 빠짐없이 서로 다르게 붙일 수가 있습니다. 아하! 그렇다면 그 ‘자연수 이름으로 볼 때의 최소값’이 달린 정수놈을 뽑아낸다면 문제가 없겠네요! 물론 $\mathbb{Z}$ 와 $\mathbb{N}$ 가 같은 크기이니까 정수들 부분집합 전체는 아까와 마찬가지로 실수만큼 많고, 따라서

$\displaystyle f:\mathbb{R}\rightarrow\bigcup_{i\in\mathbb{R}}X_{i}$
(단, $f(i)=$ “자연수 이름으로 읽었을 때 최소값인 그 정수놈” $\in X_{i}$ )

여기까지 이해하셨더라도 정말 여러분은 대단한 것입니다! 이제 훨씬 더 어려워보이는 다음 문제도 누워서 껌 씹어주시게 되겠습니다 : 전교생이 유리수 집합 $\mathbb{Q}$ 만큼 많고, 학급이 $\mathbb{Q}$ 의 부분집합 전체라면?

유리수 또한 자연수와 크기가 같으므로 일대일 대응을 통해 자연수 이름을 빠짐없이 붙여버려서,

$\displaystyle f:\mathbb{R}\rightarrow\bigcup_{i\in\mathbb{R}}X_{i}$
(단, $f(i)=$ “자연수 이름으로 읽었을 때 최소값인 그 유리수놈” $\in X_{i}$ )

하시면 되겠습니다.

드디어 기대하시는 실수를 생각해봅시다. 이번엔 전교생이 괴물 $\mathbb{R}$ 이고, 학급은… 개구간(open interval) 정도로 둡시다. 즉, 각 반들이 $]a,\;b[$ 꼴인 것입니다. 모르는 분들을 위해 설명을 드리면, $]a,\;b[$ 는 $a$ 와 $b$ 사이의 실수를 전부 모아놓은 집합이라는 뜻입니다. 이제 이런 개구간 학급들을 전부 모으면 그 크기가 $\mathbb{R}$ 과 같게 됩니다(증명은 생략합니다.). 따라서 각 학급들에 실수 이름을 붙일 수 있고, 더욱이 개구간의 처음과 끝(예를들어 $]a,\;b[$ 의 경우 $a$ 와 $b$ )에도 실수 이름을 붙일 수 있겠습니다. 다시말해 각 학급을 $X_{i} =\;\; ]a_{i},\; b_{i}[$ (단, $i\in\mathbb{R}$ )와 같이 표기하여 구분할 수 있다는 것입니다.

그러면 매번과 마찬가지로,

$\displaystyle f:\mathbb{R}\rightarrow\bigcup_{i\in\mathbb{R}}X_{i}$

여기 까진 기계적으로 써내려갈 수 있습니다. 그런데 문제가 있죠? 1과 2 사이의 실수들을 전부 모아놓았을 때 최소값이 있습니까? 1은 1과 2 사이의 실수가 아니므로 최소값이 아니고, 반장으로 얘를 뽑을수도 없겠죠. 하지만 뭐 최소값만 반장으로 뽑으란 법 있습니까!! $]a_{i},\;b_{i}[$ 안에 항상 그 중간값인 $\displaystyle \frac{a_{i}+b_{i}}{2}$ 가 있다는 것을 간파하셨다면, 이놈이 반장으로서 적격이라고 생각하실겁니다.

(단, $\displaystyle f(i)=\frac{a_{i}+b_{i}}{2}\in X_{i}$ )

선택함수를 잡는 것에 대한 자신감이 좀 생기셨습니까? 애석하게도, 실수의 부분집합에는 위와 같은 ‘구간’만 있는것이 아닙니다… 본론을 이제서야 소개하는군요. 실수의 모든 부분집합을 학급으로 둬 봅시다. 실수의 부분집합이래봐야 뭐 별거 있을까요? ……

실수에는 우리의 생각을 뛰어넘는, 묘사하기가 거의 불가능한 복잡한 부분집합들이 수도없이 많습니다(관심있는 분들은 non-measurable set 정도로 구글링 해보시기 바랍니다.). 어쨌거나, 실수의 부분집합을 전부 모으면 그 크기는 $2^{\mathbb{R}}$ 일테니 우리가 원하는 선택함수는

$\displaystyle f:2^{\mathbb{R}}\rightarrow\bigcup_{i\in 2^{\mathbb{R}}}X_{i}$

와 같은 모양이겠습니다. 그런데…… 이번에는 너무 막막하군요. 아무리 생각해봐도 방법이 떠오르질 않습니다. 아마 여러분은 아까부터 계속 입이 근질근질 하셨을겁니다. “아니, 그냥 (단, $\displaystyle f(i)=$ “아무거나 하나” $\in X_{i}$ )라고 하면 되는거 아님?” 그런데 안타깝게도 “아무거나 하나”는 수학적으로 약속된 성질의 것이 아닙니다. 최소값이나, 중간값이나, 아니면 그냥 25(?)와 같이 일일이 쓰는 등 어떤 수학적인 정의된 값을 외쳐야 하는 것입니다. 다행히 최소값, 중간값, 25는 수학적으로 정의된 값이라 무리가 없었습니다만… “아무거나 하나”라…-_-;;;

다시말해, 실수가 너무 더럽게 많기 때문에 오만 생각을 다 동원해도 반장을 일괄적으로 뽑는 방법을 제시하기가 불가능 할지도 모른다는 것입니다.

결국에 기존 공리들만으로는 불가능하다는 것이 proof theory의 본좌인 괴델(K. Godel)과 코헨(P. Cohen)에 의해 증명 되어버립니다. 그래서, 방법을 구체적으로 제시할 수는 없을망정 방법이 있다고는 해야겠다 하고 탄생한게 axiom of choice, 바로 선택공리입니다.

(Specific version)Axiom of choice : 공집합이 아닌 집합을 모아놓은 임의의 collection $\{X_{i} : i\in I\}$ 에 대하여, 다음을 만족하는 함수 $\displaystyle f:I\rightarrow\bigcup_{i\in I}X_{i}$ 가 존재한다 : 임의의 $i\in I$ 에 대하여 $f(i)\in X_{i}$ 이다.

다시말해, 종전처럼 함수를 잘 쓸수는 없더라도 어쨌든 존재는 한다고 박아놓은 약속입니다. 못찾아내면 존재 안하는거 아님?라고 말하는 수학자들은 선택공리 없이 수학을 하기도 합니다. 수학은 자유로우니까요! 어쨌든 이런 의미에서, 선택공리가 쓰인 증명들을 비구성적(non-constructive) 증명이라고 합니다…

수학은 인간의 직관에 위배되어서는 안된다고 주장하는 사람들이 있습니다. 만약 수학의 공리가 인간의 직관에 위배되지 않는다면, 이들로부터 유도된 사실들도 인간의 직관에 위배되어서는 안될 것입니다. 그러나 선택공리로부터 유도된 여러 정리들은 보편적 직관에 위배되다 못해 어처구니 없어 보이기까지 합니다. 다음 글에서는 선택공리가 일으키는 이러한 역설아닌 역설에 대해 다뤄보겠습니다^^

『”자, 잘 들으세요. AC에 의해 반장을 뽑는 방법이 존재합니다. 아 조용조용. 너네끼리 선거 시킨다는게 아니라 내가 뽑아주는거라고. 자 어쨌든 이렇게 선택함수 존재하니, 이놈 함수값으로 튀어나오는 애들 교무실로 집합!!!”

우리의 얘기는 여기까지일 것입니다. 이후 반장들을 본 사람은 아무도 없었습니다. 그들이 존재하는 것을 알 뿐… 끗.』

p.s : nonconstructive proof에 관한 유머

A sociologist, a physicist and a mathematician are each locked in a prison cell and given a supply of canned food, but no can opener.
After thirty days, the cells are unlocked. The sociologist’s cell has dents in the walls, and smashed cans and food everywhere. He threw the cans at the walls randomly until they burst open, and salvaged enough food to survive.
The physicist’s cell wall is covered in calculations, and one corner is heavily damaged. He calculated the optimum way to throw the can at the wall to make it burst open reliably (to within a reasonable margin of error), and he too survived.
The mathematician’s cell wall is likewise covered in calculations, but there are no dents in the walls. In fact, inside the cell sit the pile of cans, unopened, and the corpse of the mathematician. He was able to derive a nonconstructive proof that showed there was a way to throw the can of food at the wall, but could not find the solution.

사회학자, 물리학자, 그리고 수학자가 각자 감옥에 갇혔고 캔으로 봉해진 음식을 받았지만 캔을 여는 기구는 받지 못하였다.
30일이 지나고 감옥이 열렸다. 사회학자의 감옥 안에는 벽에 움푹 파인곳들과 찌그러진 캔들, 그리고 널부러진 음식들로 가득했다. 그는 캔들을 랜덤으로 벽에 던져 그것들이 열리게 했고, 결국 충분한 음식을 먹어 살아남은 것이었다.
물리학자 감옥의 벽은 계산으로 가득차있었고, 벽의 한 구석이 심하게 손상을 입은 상태였다. 그는 캔을 여는데 가장 효율적인 캔 던지는 방법을 계산하였으며(적당히 허용할 만한 오차 범위 내에) 그도 역시 살아남았다.
수학자의 감옥의 벽도 마찬가지로 계산으로 가득 차 있었지만, 벽에 아무런 손상이 없었다. 사실, 감옥의 안쪽에 열리지 않은 캔들이 쌓여있었으며 그 옆에 수학자의 시체가 놓여있었다. 그는 캔을 벽에 던져 여는 방법이 존재한다는 nonconstructive proof를 얻어내는데 성공하였지만 구체적인 solution을 찾아내진 못하였던 것이다.