선택공리
1. 개요
axiom of choice
[1]
선택공리(AC)는 체르멜로-프렝켈의 공리적 집합론 ZFC의 공리 중 하나이다.[2] 수학자들이 암암리에 AC를 쓰고 있다는 것을 체르멜로가 발견하고 이를 명시했다, 직관과 충돌하는 결과들을 얻을 수 있어서 초창기에는 거부하는 이들이 많았으나 아래 항목에서 확인할 수 있듯이 매우 강력한 공리이기 때문에 위상수학, 대수학 등 수학의 여러 분야에 쓰인다.
선택공리는 대표적인 비구성적 명제이다. 즉, 선택함수의 존재성은 보장해주지만 그 함수가 어떻게 주어지는지는 알려주지 않는다. 이 때문에 구성주의자나 직관주의자들은 이 공리를 거부하거나 수정된 버전을 받아들인다.[3] 아래 식에서 집합 $$S$$를 가산집합으로 한정한 가산 선택공리(axiom of countable choice) 등 보다 약한 버전을 쓰는 경우로 타협하는 경우가 대부분이지만 그것마저 배제하는 극단주의자들도 있다고 한다. 이처럼 수학에서 수정된 선택공리를 사용하는 것이 가능한 이유는 선택공리가 참이든 거짓이든 ZF 공리계와 양립 가능하기 때문이다.[4]
수학자들에게 무서운 얘기를 해보라 하니, "선택공리가 거짓이라고 해보자..."로 운을 뗐더니 다른 해석학, 위상수학 분야의 수학자들이 거품을 물고 쓰러졌더라는 농담도 있다. 수학을 좀 공부한 위키러라면 당장 아래에 '동치인 명제들'이 전부 거짓이거나 '결과들' 항목 중 어떤 것도 장담할 수 없다고 생각해보자. 당장에 가장 기본적인 개념인 무한집합의 기수#s-8부터가 날아가버린다...
2. 진술
3. 해석
즉, 임의의 집합 $$S$$[5] 대해, $$S$$의 모든 원소가 공집합이 아니라면, 집합족 $$S$$의 원소인 집합들에서 원소를 하나씩 뽑는 선택함수가 존재한다는 것이다.
선택함수란것은 쉽게 얘기 하면, 집합족 $$S = \left\{\left\{0,1\right\},\left\{2,3,4\right\},\left\{5,6,7\right\}, \cdots\right\}$$ 가 있을 때, $$S$$의 원소인 집합들에서 원소를 하나씩 뽑아 첫 번째 집합에서 [math(0)]을 뽑고, 두 번째 집합에서 $$3$$를 뽑고, 세 번째 집합에서 $$7$$을 뽑고....할 수 있다는 것. (다만, 선택공리로 선택함수의 존재성을 보일 경우에는, 이 예시와 같이 뭘 뽑았는지는 말해주지 않는다.)
막상 이렇게 설명하면 너무 당연해서 이걸 거부하는 일부 수학자들을 이해하기 힘들지만[6], 사실 $$S$$가 유한집합일 때는(즉, 유한 번 뽑는 것은) 자명해 보이지만 $$S$$가 무한집합일 경우, 특히 실수와 같이 셀 수 없는 무한집합일 경우엔 생각보다 그렇게 자명하지 않다는 것을 알 수 있다. 또한 후술할 선택공리와 동치인 명제와 결과들을 보면, 비직관적인 내용이 많다는 것을 알 수 있다.
사실, 극도로 추상적인 분야가 아닌 이상은, 선택공리 없이 선택함수를 직접 구성할 수 있는 경우를 주로 다루는 것이 대부분이다. 예를 들어서, 임의의 실수가 집합이라는 것을 일단 받아들이고[7], $$\{U_{x}|U_{x}\text{는 }x\text{보다 큰 실수들의 집합}, x\in \mathbb{R}\}$$이라는 집합족이 있다고 하자. 여기서 $$f:U_{x} \mapsto x+3$$인 선택함수 $$f$$를 다음과 같이 구성할수 있다. 임의의 실수 $$x$$가 주어지면, $$x+3\in U_{x}$$가 집합이므로, 짝공리와 분류공리를 이용하여 $$(U_{x},x+3)=\{\{U_{x}\},\{U_{x},x+3\}\}$$인 순서쌍을 만들 수 있고, $$(U_{x},x+3)$$의 유일성은 외연공리로 보일 수 있다. 그런 다음 치환공리를 이용하면, $$f=\{y|y=(U_{x},x+3), x\in\mathbb{R}\}$$는 집합이 되고, 선택함수가 된다.
하지만, 선택공리의 강력함은, 위의 예시와는 다르게 집합족이 도대체 어떻게 생겨먹은 것인지 모르는 경우에도, 어떤 선택함수가 존재한다는 사실을 반드시 보장해준다는 점에서 나온다. 그러나 이러한 점은 동시에 선택공리의 한계이기도 한데, 예를 들어서 유한차원 벡터공간의 경우, 선택공리가 없어도 존재하는 기저와 차원을 이용하면 동형이면서 많은 성질이 알려진 Fⁿ으로 대신하여 생각할 수 있다. 반면에, 기저를 알 수 없는 무한차원 벡터공간(예를 들면, 연속실함수의 공간) 같은 경우는 선택공리를 가정하면, 기저는 항상 존재하고, 차원은 유일하지만, 그것이, 주어진 공간에 대해 알려주는 내용은 거의 없고 위상 등의 추가적인 구조를 주어야 적절한 이해가 가능하다.
4. ZF공리하에서 선택공리와 동치인 명제들
- 모든 partition은 대표값의 집합을 가진다.
- $$\{X_i|i \in I\}$$이 공집합이 아닌 집합들일 때 $$\forall i \in I (f(X_i) \in X_i)$$인 함수가 존재한다.
- 초른의 보조정리(Zorn's Lemma): 부분순서집합의 임의의 사슬이 상계를 가지면 극대원소가 적어도 하나 존재한다.
- 임의의 무한집합 $$X$$에 대해 $$|X|=|{X^2}|$$. 이게 일반화되면 $$\forall k \in N\to\left|X\right|=\left|X^{k}\right|$$가 된다.
즉, 임의의 무한집합은 자기 자신과의 가산 데카르트 곱을 한 집합과 1:1 대응 관계가 존재한다.
예를 들어서 유리수 집합은 $$\displaystyle{\frac{b}{a}}\to\left(a,b\right) \left(a\neq 0\right)$$로의 1:1 대응관계를 주는 것으로 정수 집합 간의 데카르트 곱으로 표현이 가능한데, 선택공리와 동치인 이 명제에 의하여 정수 집합이 무한집합이므로 정수 집합의 데카르트 곱인 유리수와 정수 간에 1:1 대응 관계를 줄 수 있고, 따라서 유리수 집합과 정수 집합, 더 나아가서 자연수 집합의 농도(기수)가 같다. 라는 것이 유도된다. - 정렬가능성(Well-Ordering Principle): 공집합이 아닌 모든 집합에 정렬 전순서를 줄 수 있다.[8] 이 또한 선택공리와 동치이다. 즉, 모든 집합에 적절한 순서대로 순서수를 배분하는 게 가능해지면서, 초한귀납법을 적용하는 것이 허용되게 된다.
- 티호노프(Tychonoff)의 정리: 컴팩트 집합의 곱공간[9]은 컴팩트이다.
- 모든 벡터공간은 기저를 갖는다.[10]
- 모든 전사함수들은 우역원(right inverse)을 가진다.
5. 선택공리의 결과들
- 모든 무한 집합은 가산 부분집합을 가진다.
- 모든 집합에 대해 기수#s-8가 잘 정의된다.
- 가산집합의 가산 합집합은 가산집합이다.
- 함수의 치역의 기수는 정의역의 것보다 작거나 같다.
- 공집합이 아닌 집합에 적절한 이항연산을 줘서 아벨군을 만들 수 있다.
- $$a$$가 고립점이 아닌 것과 $$ a $$ 로 수렴하는 수열이 존재하는 것은 서로 동치이다.
- 함수$$ f:\mathbb{R}\to \mathbb{R} $$가 코시 함수 방정식 $$ f\left(x+y\right)=f\left(x\right)+f\left(y\right) $$ 를 만족하면서도, $$ f\left(x\right)=kx $$의 꼴이 아닐 수 있다.
- 한-바나흐(Hahn-Banach) 정리
- 르벡 측도를 갖지 않는 집합(Lebesgue nonmeasurable set)이 존재한다.
- 1을 갖는 가환환은 최대아이디얼을 갖는다.
- 모든 그래프는 최대 경로(Maximal Path)를 갖는다.
- 모든 체(Field)는 대수적으로 닫힌 체확장(Algebraic Closure)을 갖는다.
- 바나흐-타르스키 역설[11]: 구를 유한 개의 조각으로 잘 쪼갠 다음, 그 조각들을 다시 잘 붙여서 원래 구와 같은 크기의 구 두 개로 재구성할 수 있다. 이때 나눠진 각 조각 중 르베그 측도를 갖지 않는 집합이 생긴다.[12]
- 임의의 무한집합에 자유극대필터가 존재한다.[13]
- 주이데알 정역(Principal Ideal Domain) 위의 자유가군의 부분가군은 자유가군이다.
- 배중률(law of excluded middle)[14]
- 사회구성원의 숫자가 무한하다면 애로의 불가능성 정리를 우회하는 것이 가능하다.[15]
6. 관련 문서
[1] ZF공리하에서 일반화된 연속체 가설(GCH)로 선택공리를 증명가능하고 GCH보다 강력한 구성가능성 공리같은 것도 있지만 AC에 비해 공리로 받아들이는 수학자의 수가 훨씬 적은 지라 '수학계'의 데우스 엑스 마키나라기엔 무리가 있다.[2] ZFC에서 선택공리를 제외한 공리들은 ZF 공리계라고 한다.[3] 구성주의 수학(constructive mathematics)은 구성적인 증명(constructive proof)만을 올바른 증명으로 받아들이는 수학의 한 부류로 예나 지금이나 구성주의 수학을 연구하는 수학자들은 소수에 속한다. 구성적 증명이란 어떤 수학적 성질을 만족하는 대상의 존재를 진술하는 명제의 증명들 중에서 그 성질을 만족하는 구체적인 대상을 제시하거나 그러한 대상을 찾을 수 있는 방법을 제시하는 증명을 말한다.[4] 괴델이 연속체 가설과 선택공리가 각각 ZF 공리계와 일관적이라는 것을 먼저 증명했고 이후 폴 코헨은 연속체 가설과 선택공리의 부정이 각각 ZF 공리계와 일관적이라는 것을 증명했다.[5] 여기서 $$S$$는 집합들의 집합, 즉 집합족으로 이해하는 것이 직관적으로 편하다. 그런데, 현대의 공리적 집합론에서는 집합과 원소를 구별하지 않는다. 즉, 어떤 집합이 원소라는것은, 그 집합이 다른 집합에 포함되있다는 것을 말하지, 원소만 될수있는 오브젝트와 집합만 될수있는 오브젝트가 정해져있는것이 아니다.(물론, 모든 집합의 모임처럼, 집합이 될 수 없는 오브젝트는 있을수 있다. 이 경우엔, 집합들의 모임이라고 해도, 집합이 아니기 때문에 선택공리를 적용하지 않는다.) 예를 들어서, 순서수의 폰 노이만식 정의에 의하면 2란 것은 자연수 집합의 원소이기도 하지만 $$\{\emptyset,\{\emptyset\}\}$$이라는 일종의 집합이다. 물론, 이 때 2는 공집합을 원소로 가지므로, 선택공리의 적용대상이 될수는 없다. [6] 자명해 보이는 명제를 공리로 삼고 다른 명제를 유도하는 것이 다른 명제를 가정하고 정리로써 증명하는 것보다 더 직관적이다.[7] 이를 증명하는데 선택공리가 필요하지는 않다.[8] 이것만 보면 반직관적이지는 않으나, 실수의 정렬순서를 찾아보면 반직관적이라는 것을 알 것이다. 실수의 정렬순서를 찾기 어려울 것인데, 이는 선택공리가 비구성적 명제라는 것을 단적으로 보여준다.[9] 꼭 유한곱일 필요는 없다.[10] 보통은 선택공리에서 직접 유도하기보다는 위의 초른의 보조정리를 이용한다.[11] 역설일 뿐 모순을 만들어내지는 않는다. 대표적인 반직관적 정리이다.[12] 여기서는 간단하게 설명한건데, 실제로는 공간상의 부피를 집합의 분할을 이용하여 잘게 쪼개고, 유클리드 이동만을 통하여 겹치지 않게 잘 쌓으면 다른 부피로 변환할 수 있다는 소리. 얼핏 들어서는 모순이 생길 것 같지만, 사실은 3차원 이상의 거리공간에서는 위상수학자인 하우스도르프가 부피라고 정의 가능한 일관된 특성을 지닌 함수가 존재하지 않음을 보였다. 집합의 분할을 이용한다는 소리는 자연스럽게 위상수학적인 과정을 거치게 되는데 이 과정에서 부피를 정의할 수 없는 집합. 즉 르벡 측도를 가지지 못하는 집합이 발생하게 되므로 모순을 만들지 않는다. 좀 더 쉽게 풀어쓰면, 3차원 공간상에서 '(평행이동과 회전변환에 대한 불변량인) 부피'를 정의 할 수 없으므로 평행이동과 회전만으로 부피가 두 배로 늘어나도 전혀 모순이 아니라고 이해하면 된다.[13] 자유극대필터를 이용해 르베그 측도를 갖지 않는 집합의 존재성을 보일 수 있다.[14] 선택공리로부터 논리학의 원리인 배중률이 도출된다는게 의아할 수 있겠지만 증명가능하다. 흔히 다이아코네스쿠의 정리(Diaconescu's theorem)라고 하며 앞서 말한 구성주의 수학에서 선택공리를 받아들이지 않는 결정적인 이유이다.[15] 자유 극대필터가 필요한데 독재자는 없어지지만 측도가 0보다는 큰 독재집단이 출현한다.