선택공리

수학기초론 Foundations of Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px"	다루는 대상과 주요 토픽
수리논리학	논리 · 논증{ 귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{ 증명보조기 · 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문( 조각적 정의) · 명제 논리( 명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리( 존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론
집합론	집합( 원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계( 동치관계 · 순서 관계) · 순서쌍( 튜플) · 서수( 하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC( 선택공리) · 기수( 초한기수) · 절대적 무한 · 모임
범주론	범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성
계산가능성 이론	계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수
정리
드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리( 괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리
기타
예비사항( 약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학
틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보		}}}}}}}}}

1. 개요2. 진술3. 해석4. ZF공리하에서 선택공리와 동치인 명제들5. 선택공리의 결과들6. 선택공리를 함의하는 공리들7. 선택공리와 상치되는 공리들8. 여담9. 관련 문서

1. 개요

選擇公理 / axiom of choice

선택 공리는 체르멜로-프렝켈의 공리적 집합론 ZFC(Axiom of Choice가 포함된 Zermelo–Fraenkel 집합론) 의 공리 중 하나이다.[1] 약칭으로 AC라고도 한다. 수학자들이 암암리에 AC를 쓰고 있다는 것을 체르멜로가 발견하고 이를 명시했다, 직관과 충돌하는 결과들을 얻을 수 있어서 초창기에는 거부하는 이들이 많았으나 아래 항목에서 확인할 수 있듯이 매우 강력한 공리이기 때문에 위상수학, 대수학 등 수학의 여러 분야에 쓰인다.

선택공리는 대표적인 비구성적 명제이다. 즉, 선택함수의 존재성은 보장해주지만 그 함수가 어떻게 주어지는지는 알려주지 않는다. 이 때문에 구성주의자나 직관주의자들은 이 공리를 거부하거나 수정된 버전을 받아들인다.[2] 아래 식에서 집합 [math(S)]를 가산집합으로 한정한 가산 선택공리(axiom of countable choice) 등 보다 약한 버전을 쓰는 경우로 타협하는 경우가 대부분이지만 그것마저 배제하는 극단주의자들도 있다고 한다. 이처럼 수학에서 수정된 선택공리를 사용하는 것이 가능한 이유는 선택공리가 참이든 거짓이든 ZF 공리계와 양립 가능하기 때문이다.

여담으로 결정공리(axiom of determinacy)라는게 있는데, 이 결정공리는 자연수열 공간에서 취하는 모든 부분 집합은 결정집합[3]반드시 한명이 이기는 필승전략이 있는 집합을 의미한다.]이다라는 공리로, 선택공리와 공존할 수 없는 공리[4]이지만, 약화시킬 경우는 선택공리와 동일시할 수 있는 특이한 성질을 지니고 있다. 약화되지 않은 결정공리를 ZF 공리계에 포함시켜도 모순은 발생하지 않기 때문에 ZF 공리계의 일관성이 보장된다는 것 또한 특기할 사항이다.

2. 진술

[math(\forall S \,\ \left[\left(\emptyset \notin S\right) \Rightarrow \left(\exists f \in (\bigcup S)^S \, \forall A \in S \, \left(f\left(A\right) \in A\right)\right)\right])].[5]

3. 해석

즉, 임의의 집합족 [math(S)][6] 대해, [math(S)]의 모든 원소가 공집합이 아니라면, 집합족 [math(S)]의 원소인 각각의 집합에서 그 집합의 원소를 하나씩 뽑는 선택함수(choice function)가 존재한다는 것이다.

예를 들면 집합족 [math(S = \left\{\left\{0,1\right\},\left\{2,3,4\right\},\left\{5,6,7\right\}, \cdots\right\})]에서, 첫 번째 집합에서 [math(0)]을 뽑고, 두 번째 집합에서 [math(3)]를 뽑고, 세 번째 집합에서 [math(7)]을 뽑고...등의 선택행위를 할 수 있다는 것이다. (다만, 선택공리는 선택함수의 존재성을 보일 뿐, 이 예시와 같이 어떤 원소가 각 집합에서 선택되었는지 말해주지 않는다.)

막상 이렇게 설명하면 너무 당연해서 이걸 거부하는 일부 수학자들을 이해하기 힘들지만[7], 사실 [math(S)]가 유한집합일 때는(즉, 유한 번 뽑는 것은) 자명해 보이지만 [math(S)]가 무한집합일 경우, 특히 실수와 같이 셀 수 없는 무한집합일 경우엔 생각보다 그렇게 자명하지 않다는 것을 알 수 있다. 또한 후술할 선택공리와 동치인 명제와 결과들을 보면, 비직관적인 내용이 많다는 것을 알 수 있다.

사실, 극도로 추상적인 분야가 아닌 이상은, 선택공리 없이 선택함수를 직접 구성할 수 있는 경우를 다루는 것이 대부분이다. 예를 들어서, 임의의 실수가 집합이라는 것을 일단 받아들이고[8], [math(\{U_{x}|U_{x}\text{는 }x\text{보다 큰 실수들의 집합}, x\in \mathbb{R}\})]이라는 집합족이 있다고 하자. 여기서 [math(f:U_{x} \mapsto x+3)]인 선택함수 [math(f)]를 다음과 같이 구성할수 있다. 임의의 실수 [math(x)]가 주어지면, [math(x+3\in U_{x})]가 집합이므로, 짝공리와 분류공리를 이용하여 [math((U_{x},x+3)=\{\{U_{x}\},\{U_{x},x+3\}\})]인 순서쌍을 만들 수 있고, [math((U_{x},x+3))]의 유일성은 외연공리로 보일 수 있다. 그런 다음 치환공리를 이용하면, [math(f=\{y|y=(U_{x},x+3), x\in\mathbb{R}\})]는 집합이 되고, 선택함수가 된다.

하지만, 선택공리의 강력함은, 위의 예시와는 다르게 집합족이 도대체 어떻게 생겨먹은 것인지 모르는 경우에도, 어떤 선택함수가 존재한다는 사실을 반드시 보장해준다는 점이다. 그러나 이러한 점은 동시에 선택공리의 한계이기도 한데, 예를 들어서 유한차원 벡터공간의 경우, 선택공리가 없어도 존재하는 기저와 차원을 이용하면 동형이면서 많은 성질이 알려진 Fⁿ으로 대신하여 생각할 수 있다. 반면에, 기저를 알 수 없는 무한차원 벡터공간(예를 들면, 연속실함수의 공간) 같은 경우는 선택공리를 가정하면, 기저는 항상 존재하고, 차원이 잘 정의되지만, 그것 자체가 주어진 공간에 대해 알려주는 내용은 거의 없고 위상이나 측도 등의 추가적인 구조를 주어야 적절한 이해가 가능하다.

4. ZF공리하에서 선택공리와 동치인 명제들

모든 partition은 대표값의 집합을 가진다.
[math(\{X_i|i \in I\})]이 공집합이 아닌 집합들일 때 [math(\forall i \in I (f(X_i) \in X_i))]인 함수가 존재한다.
초른의 보조정리(Zorn's Lemma): 부분순서집합의 임의의 사슬이 상계를 가지면 극대원소가 적어도 하나 존재한다.[9]
임의의 무한집합 [math(X)]에 대해 [math(|X|=|{X^2}|)]. 이게 일반화되면 [math(\forall k \in \mathbb{N}\to\left|X\right|=\left|X^{k}\right|)]가 된다.
즉, 임의의 무한집합은 자기 자신과의 유한 데카르트 곱과 1:1 대응 관계가 존재한다.
예를 들어서 유리수 집합은 [math(\displaystyle{\frac{b}{a}}\to\left(a,b\right) \left(a\neq 0\right))]로의 1:1 대응관계를 주는 것으로 정수 집합 간의 데카르트 곱으로 표현이 가능한데, 선택공리와 동치인 이 명제에 의하여 정수 집합이 무한집합이므로 정수 집합의 데카르트 곱인 유리수와 정수 간에 1:1 대응 관계를 줄 수 있고, 따라서 유리수 집합과 정수 집합, 더 나아가서 자연수 집합의 농도(기수)가 같다. 라는 것이 유도된다.
체르멜로 정렬정리(Well-Ordering Theorem): 공집합이 아닌 모든 집합에 정렬 전순서를 줄 수 있다.[10] 이 또한 선택공리와 동치이다. 즉, 모든 집합에 적절한 순서대로 순서수를 배분하는 게 가능해지면서, 초한귀납법을 적용하는 것이 허용되게 된다.
티호노프 정리: 컴팩트 집합의 곱공간[11]은 컴팩트이다.
모든 벡터공간은 기저를 갖는다.[12]
모든 전사함수(surjective function)들은 우역원(right inverse)을 가진다.
공집합이 아닌 집합에 적절한 이항연산을 줘서 군을 만들 수 있다.

5. 선택공리의 결과들

모든 무한 집합은 가산 부분집합을 가진다.
모든 집합에 대해 기수가 잘 정의된다.
가산 개의 가산집합의 합집합은 가산집합이다.
함수의 치역의 기수는 정의역의 것보다 작거나 같다.
함수[math( f:\mathbb{R}\to \mathbb{R} )]가 코시 함수 방정식 [math( f\left(x+y\right)=f\left(x\right)+f\left(y\right) )] 를 만족하면서도, [math( f\left(x\right)=kx )]의 꼴이 아닐 수 있다.
한-바나흐(Hahn-Banach) 정리
르벡 측도를 갖지 않는 집합(Lebesgue nonmeasurable set)이 존재한다.
1을 갖는 가환환은 극대 아이디얼을 갖는다.
모든 그래프는 최대 경로(Maximal Path)를 갖는다.
모든 체(Field)는 대수적으로 닫힌 체확장(Algebraic Closure)을 갖는다.[13]
바나흐-타르스키 역설 [14]: 구를 유한 개의 조각으로 잘 쪼갠 다음, 그 조각들을 다시 잘 붙여서 원래 구와 같은 크기의 구 두 개로 재구성할 수 있다. 이때 나눠진 각 조각 중 르베그 측도를 갖지 않는 집합이 생긴다.[15]
임의의 무한집합에 자유극대필터가 존재한다.[16]
Order-extension principle: 모든 부분 순서에는 순서관계를 보존하는 전순서가 존재한다.
주이데알 정역(Principal Ideal Domain) 위의 자유가군의 부분가군은 자유가군이다.
3차원 공간을 서로 겹치지 않는 단위원, 또는 서로 겹치지 않고 크기가 전부 다른 원, 또는 서로 평행하지 않는 직선들로 완벽히 채울 수 있다. [17]
배중률(law of excluded middle)[18]
사회구성원의 숫자가 무한하다면 애로의 불가능성 정리를 우회하는 것이 가능하다.[19]

이들 중 가장 흔히 쓰이는 것은 초른의 보조정리이다. 수학과 학생이 아닌 이공계 학생에게는 벡터공간의 기저의 존재성이 선택공리의 가장 대표적인 결과이다.

6. 선택공리를 함의하는 공리들

일반화 연속체 가설(Generalized Continuum Hypothesis, GCH)
구성가능성 공리(Axiom of Constructivity, V=L)

7. 선택공리와 상치되는 공리들

결정공리(Axiom of Determinacy)
실수 집합의 임의의 부분집합은 준열린집합(almost open set)이다.
실수 집합의 임의의 부분집합의 르베그 측도가 잘 정의된다.

8. 여담

개요에서 보여지듯 원래 ZFC에서 ZF만 먼저 발표되었고 나중에 C가 추가되었다. 문제는 이 추가된 C가 ZF 내에서 증명도 반증도 불가능한 불완전성 정리의 완벽한 예시라는 점이다.

괴델은 연속체 가설과 선택공리가 각각 ZF 공리계와 일관적이라는 것을 1939년 증명했다. 이때 사용된 것이 상술한 구성 가능성 공리이다. 이후 폴 코헨은 1963년 연속체 가설과 선택공리의 부정이 각각 ZF 공리계와 일관적이라는 것을 증명했다. 즉, ZF 공리계를 받아들일 때 C는 받아들여도 일관적이고 받아들이지 않아도 일관적이다. 개요에서 간단히 언급된 '선택공리에 대한 수정'이 가능한 이유이다.

이처럼 선택공리를 사람에 따라 받아들일 수도, 받아들이지 않을 수도 있다 보니 이런 농담도 생겨났다.

수학자들의 파티에서 서로 자기가 아는 무서운 이야기를 하고 있었다. 한 수학자가 '선택공리가 거짓이라고 해보자...' 라고 하니 해석학, 위상수학 분야의 수학자들이 거품을 물고 쓰러졌다.[20][21]

The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?

선택공리는 상식적으로 참인 느낌이고 (모든 집합의) 정렬정리는 상식적으로 거짓인 느낌인데 이들이 동치이다 보니 이와 관련된 농담도 있다. #

9. 관련 문서

[1] ZFC에서 선택공리를 제외한 공리들은 ZF 공리계라고 한다. [2] 구성주의 수학(constructive mathematics)은 구성적인 증명(constructive proof)만을 올바른 증명으로 받아들이는 수학의 한 부류로 예나 지금이나 구성주의 수학을 연구하는 수학자들은 소수에 속한다. 구성적 증명이란 어떤 수학적 성질을 만족하는 대상의 존재를 진술하는 명제의 증명들 중에서 그 성질을 만족하는 구체적인 대상을 제시하거나 그러한 대상을 찾을 수 있는 방법을 제시하는 증명을 말한다. [3] 자연수열이 있을 때, 두 사람이 번갈아 수를 고르는 규칙의 게임을 했을 때, [4] 선택공리에 따르면 결정집합은 가측집합인데, 역시 선택공리하에서는 자연수 집합의 부분집합중에는 르베그 측도가 정의되지 않는 비가측집합이 존재할 수 밖에 없어서 결정공리의 모든 부분집합은 결정집합이다이라는 내용과 충돌한다. [5] 이 표현에서 사용하는 집합론 기호들에 대해 알고 싶다면 여기를 참고하기 바람. [6] 여기서 [math(S)]는 집합들의 집합, 즉 집합족으로 이해하는 것이 직관적으로 편하다. 그런데, 공리적 집합론인 ZFC에서는 집합과 원소를 구별하지 않는다. 즉, 어떤 집합이 원소라는것은, 그 집합이 다른 집합에 포함돼있다는 것을 말하지, 원소만 될수있는 오브젝트와 집합만 될수있는 오브젝트가 정해져있는것이 아니다.(물론, 모든 집합의 모임처럼, 집합이 될 수 없는 오브젝트는 있을수 있다. 이 경우엔, 집합들의 모임이라고 해도, 집합이 아니기 때문에 선택공리를 적용하지 않는다.) 예를 들어서, 순서수의 폰 노이만식 정의에 의하면 2란 것은 자연수 집합의 원소이기도 하지만

\{\emptyset,\{\emptyset\}\}

이라는 일종의 집합이다. 물론, 이 때 2는 공집합을 원소로 가지므로, 선택공리의 적용대상이 될 수 없다. [7] 자명해 보이는 명제를 공리로 삼고 다른 명제를 유도하는 것이 다른 명제를 가정하고 정리로써 증명하는 것보다 더 직관적이다. [8] 이를 증명하는데 선택공리가 필요하지는 않다. [9] 주로 AoC→Zorn→WOP→AoC 순서로 증명한다. [10] 이것만 보면 반직관적이지는 않으나, 실수의 정렬순서를 찾아보면 반직관적이라는 것을 알 것이다. 실수의 정렬순서를 찾기 어려울 것인데, 이는 선택공리가 비구성적 명제라는 것을 단적으로 보여준다. [11] 꼭 유한곱일 필요는 없다. [12] 보통은 선택공리에서 직접 유도하기보다는 위의 초른의 보조정리를 이용한다. 다만 내적이 정의된 유한차원 내적벡터공간이라면 그람-슈미트 과정을 거쳐서 정규직교기저를 가진다는게 알려져 있으므로, 선택공리는 내적이 정의되지 않은 벡터공간이나 무한차원에 대해서도 기저를 가진다는걸 보여주는 셈이다. [13] 이 증명에 초른의 보조정리를 사용한다. [14] 역설일 뿐 모순을 만들어내지는 않는다. 대표적인 반직관적 정리이다. [15] 여기서는 간단하게 설명한건데, 실제로는 공간상의 부피를 집합의 분할을 이용하여 잘게 쪼개고, 유클리드 이동만을 통하여 겹치지 않게 잘 쌓으면 다른 부피로 변환할 수 있다는 소리. 얼핏 들어서는 모순이 생길 것 같지만, 사실은 3차원 이상의 거리공간에서는 위상수학자인 하우스도르프가 부피라고 정의 가능한 일관된 특성을 지닌 함수가 존재하지 않음을 보였다. 집합의 분할을 이용한다는 소리는 자연스럽게 위상수학적인 과정을 거치게 되는데 이 과정에서 부피를 정의할 수 없는 집합. 즉 르벡 측도를 가지지 못하는 집합이 발생하게 되므로 모순을 만들지 않는다. 좀 더 쉽게 풀어쓰면, 3차원 공간상에서 '(평행이동과 회전변환에 대한 불변량인) 부피'를 정의 할 수 없으므로 평행이동과 회전만으로 부피가 두 배로 늘어나도 전혀 모순이 아니라고 이해하면 된다. [16] 자유극대필터를 이용해 르베그 측도를 갖지 않는 집합의 존재성을 보일 수 있다. [17] 3차원 공간의 정렬전순서를 설정하고 그 위에서 초한귀납법을 적용한다. [18] 선택공리로부터 논리학의 원리인 배중률이 도출된다는게 의아할 수 있겠지만 증명가능하다. 흔히 다이아코네스쿠의 정리(Diaconescu's theorem)라고 하며 앞서 말한 구성주의 수학에서 선택공리를 받아들이지 않는 결정적인 이유이다. 게다가 선택공리는 기본적으로 무한한 집합에 대해서 정의되므로 그보다 약화된 가산집합. 조금 더 약화시킨 유한집합에서의 배중률은 당연한게 아닌가 하는 의문도 있겠지만, 애당초 ZF공리계에서 가산집합/유한집합에 선택공리를 적용할 수 있다라는 것 자체가 배중률로 유도되는거라 결국은 불가분의 관계다. [19] 자유 극대필터가 필요한데 독재자는 없어지지만 측도가 0보다는 큰 독재집단이 출현한다. [20] 선택공리를 거짓이라고 하면 해당 분야 수학자들은 밥줄이 날아간다. 당장에 가장 기본적인 개념인 무한집합의 기수부터가 날아가버린다. [21] 해석학과 위상수학이 제일 대표적이여서 그렇지, 다른 분야도 만만치 않다. 예를들면 대수학의 경우, 위의 선택공리와 동치인 부분에 있는 '모든 벡터공간은 기저를 갖는다'는 아예 부정이 되므로 '기저를 갖지 않는 벡터공간'에 대한 논의가 필요하게 되고, 선택공리의 결과인 '1을 갖는 가환환은 극대 아이디얼을 가진다' 혹은 '주이데알 정역(Principal Ideal Domain) 위의 자유가군의 부분가군은 자유가군이다' 라는 주장들에 대해서 '선택공리가 없어도 정말 맞는 주장이야?'라고 검토해야한다. [22] 쿠르트 괴델과 폴 코헨 두 사람은 선택공리가 기존의 ZF공리계로부터 증명도 반증도 불가능하다는 것을 증명해냈다.