선택 공리

집합론에서 선택 공리(選擇公理, 영어: axiom of choice, 약자 AC)는 공집합이 아닌 집합에서 한 원소를 고를 수 있으며, 또한 이를 무한 번 반복할 수 있다는 공리이다. 직관적으로 자연스러워 보이지만, 비직관적인 결과를 함의한다.

선택 공리의 형상화. 선택 함수는 각 집합 ${\displaystyle S_{i}}$를 그 속의 원소 ${\displaystyle x_{i}\in S_{i}}$로 대응시킨다.

정의

집합족 ${\displaystyle \{S_{i}\}_{i\in I}}$ 위의 선택 함수(選擇函數, 영어: choice function)는 다음 성질을 만족시키는 함수 ${\displaystyle f}$이다.

${\displaystyle f\colon I\to \bigcup _{i\in I}S_{i}}$

${\displaystyle \forall i\in I\colon f(i)\in S_{i}}$

만약 ${\displaystyle \varnothing \in \{S_{i}\}_{i\in I}}$라면, ${\displaystyle \{S_{i}\}_{i\in I}}$는 물론 선택 함수를 가질 수 없다. 선택 공리 ${\displaystyle {\mathsf {AC}}}$에 의하면, 공집합을 포함하지 않는 모든 집합족은 선택 함수를 갖는다.

약화된 형태

임의의 기수 ${\displaystyle \kappa }$에 대하여, ${\displaystyle {\mathsf {AC}}_{\kappa }}$는 "크기가 ${\displaystyle \kappa }$ 이하인, 공집합을 포함하지 않는 집합족은 선택 함수를 갖는다"는 명제이다. 특히, ${\displaystyle \kappa =\omega }$일 때 ${\displaystyle {\mathsf {AC}}_{\omega }}$를 가산 선택 공리(可算選擇公理, 영어: axiom of countable choice)라고 한다.

임의의 집합 ${\displaystyle S}$ 및 이항 관계 ${\displaystyle R\subseteq S^{2}}$가 주어졌고, 또한 이들이 다음 성질들을 만족시킨다고 하자.

• ${\displaystyle S\neq \varnothing }$
• 임의의 ${\displaystyle s\in S}$에 대하여, ${\displaystyle (s,t)\in R}$인 ${\displaystyle t\in S}$가 존재한다.

그렇다면, 의존적 선택 공리(依存的選擇公理, 영어: axiom of dependent choice) ${\displaystyle {\mathsf {DC}}}$에 따르면 다음 성질을 만족시키는 열

${\displaystyle s\colon \mathbb {N} \to S}$

${\displaystyle i\mapsto s_{i}}$

이 존재한다.

• 임의의 ${\displaystyle i\in \mathbb {N} }$에 대하여, ${\displaystyle (s_{i},s_{i+1})\in R}$

대역적 선택 공리

집합론의 언어 ${\displaystyle {\mathcal {L}}_{\in }}$에 1항 연산 ${\displaystyle \tau }$를 추가하자. 그렇다면, 이 언어 ${\displaystyle {\mathcal {L}}_{\in ,\tau }}$에서, 대역적 선택 공리(大域的選擇公理, 영어: axiom of global choice)는 다음과 같은 문장이다.

${\displaystyle \forall x\colon \left(\exists y\colon y\in x\implies \tau (x)\in x\right)}$

이 경우, ${\displaystyle \tau }$를 선택 연산(영어: choice operator)이라고 한다.

대역적 선택 공리는 선택 공리를 함의하며, ZF + 대역적 선택 공리는 ZFC의 보존적 확장이다.

성질

집합족 ${\displaystyle (X_{i})_{i\in I}}$가 주어졌으며, 각 ${\displaystyle X_{i}}$ 위에 정렬 순서 ${\displaystyle \leq _{i}}$가 주어졌다고 하자. 그렇다면, 선택 함수

${\displaystyle f\colon I\to \bigcup _{i\in I}X_{i}}$

를 다음과 같이 자명하게 정의할 수 있다.

${\displaystyle f(i)=\min X_{i}}$

특히, 만약 ${\displaystyle \textstyle \bigcup _{i\in I}X_{i}}$ 위에 정렬 순서가 주어졌다면, 이는 각 ${\displaystyle X_{i}}$에 대하여 제한할 수 있으며, 이에 따라 선택 함수를 정의할 수 있다.

함의 관계

체르멜로-프렝켈 집합론 아래, 임의의 자연수 ${\displaystyle n\in \mathbb {N} }$에 대하여 ${\displaystyle {\mathsf {AC}}_{n}}$을 증명할 수 있다.

${\displaystyle \forall n\in \mathbb {N} \colon ({\mathsf {ZF}}\vdash {\mathsf {AC}}_{n})}$

즉, 체르멜로-프렝켈 집합론에서는 유한 개의 선택을 할 수 있지만, 무한 개의 선택은 (체르멜로-프렝켈 집합론이 무모순적이라면) 불가능하다.

체르멜로-프렝켈 집합론 아래, 선택 공리는 의존적 선택 공리를 함의하며, 의존적 선택 공리는 가산 선택 공리를 함의한다.

${\displaystyle {\mathsf {ZF}}\vdash \left({\mathsf {AC}}\implies {\mathsf {DC}}\implies {\mathsf {AC}}_{\omega }\right)}$

증명 (${\displaystyle {\mathsf {DC}}\implies {\mathsf {AC}}_{\omega }}$):

집합족 ${\displaystyle (X_{i})_{i\in \mathbb {N} }}$이 주어졌다고 하자. 집합

${\displaystyle X=\bigsqcup X_{i}}$

위에 다음과 같은 이항 관계 ${\displaystyle R\subseteq X^{2}}$를 정의한다.

${\displaystyle (x,y)\in R\iff (\exists i\in \mathbb {N} \colon x\in X_{i}\land y\in X_{i+1})}$

그렇다면, ${\displaystyle {\mathsf {DC}}}$에 의하여 열

${\displaystyle (x_{i})_{i\in \mathbb {N} }}$

${\displaystyle \exists k\in \mathbb {N} \forall i\in \mathbb {N} \colon x_{i}\in X_{i+k}}$

가 존재한다. 따라서 ${\displaystyle {\mathsf {AC}}_{k}}$를 사용하여

${\displaystyle y_{i}\in X_{i}\qquad (i=0,1,\dots ,k)}$

를 고른 뒤

${\displaystyle y_{i+k}=x_{i}\qquad (i\in \mathbb {N} )}$

이라고 정의하면, ${\displaystyle y_{i}\in X_{i}\forall i\in \mathbb {N} }$이다. 따라서 ${\displaystyle i\mapsto y_{i}}$는 가산 무한 집합족 ${\displaystyle (X_{i})_{i\in \mathbb {N} }}$의 선택 함수이다.

증명 (${\displaystyle {\mathsf {AC}}\implies {\mathsf {DC}}}$):

집합 ${\displaystyle X}$ 위의 이항 관계 ${\displaystyle R\subseteq X^{2}}$가 주어졌다고 하고, 또한

${\displaystyle \forall x\in X\exists y\in X\colon (x,y)\in R}$

가 성립한다고 하자. 그렇다면, 선택 공리에 의하여 집합족

${\displaystyle \{\{y\in X\colon (x,y)\in R\}\}_{x\in X}}$

의 선택 함수

${\displaystyle f\colon X\to \{\{y\in X\colon (x,y)\in R\}\}_{x\in X}}$

${\displaystyle \forall x\in X\colon f(x)\in \left\{y\in X\colon (x,y)\in R\right\}}$

가 존재한다. 임의의 원소 ${\displaystyle x_{0}\in X}$를 고르고

${\displaystyle x_{i}=\overbrace {(f\circ f\circ \cdots \circ f)} ^{i}(x_{0})}$

을 정의하면, 이는 의존적 선택 공리에 등장하는 조건을 만족시킨다.

증명 이론적 성질

만약 체르멜로-프렝켈 집합론(ZF)이 일관적이라면, 선택 공리는 체르멜로-프렝켈 집합론과 독립적이다. 즉, 다음을 보일 수 있다.

${\displaystyle {\mathsf {ZF}}\vdash \operatorname {Con} ({\mathsf {ZF}})\iff \operatorname {Con} ({\mathsf {ZFC}})}$

${\displaystyle {\mathsf {ZF}}\vdash \operatorname {Con} ({\mathsf {ZF}})\iff \operatorname {Con} ({\mathsf {ZF\lnot C}})}$

모형 이론적 성질

구성 가능 전체에서는 선택 공리가 성립한다.

${\displaystyle {\mathsf {ZF}}\vdash (V=L\implies {\mathsf {AC}})}$

즉, 체르멜로-프렝켈 집합론의 모형 ${\displaystyle M}$이 주어졌을 때, ${\displaystyle M}$ 속의 구성 가능 전체 ${\displaystyle L^{M}\subseteq M}$은 ZFC의 모형을 이룬다.

반면, 강제법을 사용하여 선택 공리가 실패하는 모형들을 구성할 수 있다.

선택 공리를 함의하는 명제

체르멜로-프렝켈 집합론 아래, 다음 명제들은 선택 공리를 함의한다.

• 구성 가능성 공리 ${\displaystyle V=L}$
• 일반화 연속체 가설

선택 공리와 동치인 명제

집합족 ${\displaystyle {\mathcal {S}}}$가 다음 두 조건을 만족시키면, 유한 지표 집합족(有限指標集合族, 영어: family of sets of finite character)이라고 한다.

• 임의의 ${\displaystyle S\in {\mathcal {S}}}$에 대하여, ${\displaystyle S}$의 모든 유한 부분 집합은 ${\displaystyle {\mathcal {S}}}$의 원소이다.
• 임의의 집합 ${\displaystyle S}$에 대하여, 만약 ${\displaystyle S}$의 모든 유한 부분 집합이 ${\displaystyle {\mathcal {S}}}$의 원소라면, ${\displaystyle S\in {\mathcal {S}}}$이다.

체르멜로-프렝켈 집합론을 가정하면, 선택 공리는 수많은 동치 명제들을 가지며, 다음과 같다. 즉,

${\displaystyle {\mathsf {ZF}}\vdash {\mathsf {AC}}\iff A}$

인 명제 ${\displaystyle A}$의 예는 다음을 들 수 있다.

• 공집합을 포함하지 않는 집합족 ${\displaystyle {\mathcal {S}}}$에 대하여, ${\displaystyle \prod {\mathcal {S}}\neq \varnothing }$이다.
• 초른 보조정리
• 정렬 정리
• 티호노프 정리
• (타르스키 정리, 영어: Tarski theorem) 임의의 무한 기수 ${\displaystyle \kappa }$에 대하여, ${\displaystyle \kappa =\kappa ^{2}}$이다.^[1]
• (기수의 비교 가능성) 임의의 두 기수 ${\displaystyle \kappa _{1}}$, ${\displaystyle \kappa _{2}}$에 대하여, ${\displaystyle \kappa _{1}=\kappa _{2}}$이거나, ${\displaystyle \kappa _{1}<\kappa _{2}}$이거나, ${\displaystyle \kappa _{1}>\kappa _{2}}$이다.
• (타이히뮐러-투키 보조정리, 영어: Teichmüller–Tukey lemma) 공집합이 아닌 모든 유한 지표 집합족은 (${\displaystyle \subseteq }$에 따른) 극대 원소를 갖는다.
• 모든 벡터 공간은 기저를 갖는다.
• 자명환이 아닌 (단위원을 갖는) 환은 극대 아이디얼을 갖는다.
• 망각 함자 ${\displaystyle \operatorname {Grp} \to \operatorname {Set} }$의 상은 공집합이 아닌 모든 집합의 모임이다.
• (무한군에 대한) 라그랑주 정리 (군론)
• 모든 연결 그래프는 생성나무를 갖는다.

선택 공리로부터 함의되는 명제

만약 체르멜로-프렝켈 집합론이 일관적이라면 체르멜로-프렝켈 집합론으로 다음 정리들을 증명할 수 없지만, 선택 공리를 추가하면 증명할 수 있다.

• 괴델의 완전성 정리
• 모든 체는 대수적 폐포를 갖는다.
• ${\displaystyle \mathbb {R} }$와 ${\displaystyle \mathbb {C} }$는 덧셈군으로서 서로 동형이다.
• (닐센-슈라이어 정리) 자유군의 모든 부분군은 자유군이다.
• 한-바나흐 정리
• 베르 범주 정리
• 바나흐-타르스키 역설
• 르베그 가측 집합이 아닌 실수 집합이 존재한다.

그러나 선택 공리를 의존적 선택 공리(또는 가산 선택 공리)로 약화시킨다면, 이들 가운데 상당수는 증명 불가능하다. 예를 들어, 의존적 선택 공리는 르베그 가측 집합이 아닌 실수 집합의 존재를 증명할 수 없다.

가산 선택 공리만으로 대부분의 해석학을 전개할 수 있다.^[2]

역사

공식적인 형식화가 없었음에도 불구하고 19세기 말까지 선택 공리는 암묵적으로 수학자들 사이에서 사용되어 왔다. 예를 들어, 집합 ${\displaystyle X}$가 공집합이 아닌 집합만을 포함한다고 했을 때, 수학자들은 종종 “모든 ${\displaystyle X}$에 포함된 (집합) ${\displaystyle s}$에 대해, ${\displaystyle F(s)}$를 ${\displaystyle s}$의 원소라고 하자” 라고 기술하곤 했다. 일반적으로 (함수) ${\displaystyle F}$ 가 선택 공리 없이 존재할 수 있음을 증명하기란 불가능했고, 그로 인해 체르멜로 이전까지는 이를 심각한 문제로 여기지 않았다.

한편, 모든 함수가 선택 공리를 필요로 하지는 않는다. 유한 집합 ${\displaystyle X}$의 경우, 선택 공리는 다른 집합론의 공리들로부터 도출될 수 있다. 각각에 적어도 하나의 물건이 담긴 (유한한) 여러 개의 상자들을 상상 해 보자. 이때 우리는 각 상자에서 정확히 하나의 물건을 선택할 수 있다. 예를 들자면 이런 식이다. 첫 번째 상자에서 물건 한 개를 선택하고, 두 번째 상자로 옮겨 여기서도 물건 한 개를 선택한다. 그 후 세 번째 상자에서도 물건을 하나 선택하고, 이런 방식을 유한한 횟수로 반복해서, 마지막 상자에서 물건을 하나 선택하는 것으로 이 과정을 마칠 수 있다. 이 때, 각 상자에서 하나 씩의 물건을 선택함으로써 보여지는 상자-물건의 관계를 선택 함수에 해당한다고 할 수 있다. 그러나 이런 방법은 공집합이 아닌 집합의 모든 가산 집합족에 대해서도 선택 함수가 존재한다는, 가산 선택 공리를 증명하는 데에는 사용될 수 없다. 같은 방법이 공집합이 아닌 집합들의 무한열에 적용될 경우, 각각의 유한한 단계에서는 함수가 정의되나 전체 집합족에 대한 함수가 정의되는 단계가 존재하지 않게 된다. 결과적으로 체르멜로-프렝켈 집합론의 체계 아래서 선택 공리 없이는 어떤 “극한” 선택 함수도 구성할 수 없게 되는 것이다.

게오르크 칸토어는 선택 공리와 동치인 정렬 정리가 증명이 필요 없을 정도로 자명한 "사고 법칙"(독일어: Denkgesetz 뎅크게제츠^[*])이라고 여겼다. 그러나 다른 수학자들은 이 "사고 법칙"에 대하여 회의적이었다. 1904년에 헝가리의 수학자 쾨니그 줄러(헝가리어: Kőnig Gyula)는 정렬 정리를 반증하였다고 발표하였다. 그러나 몇 주 뒤 펠릭스 하우스도르프가 이 "반증"의 오류를 지적하였다.

1904년에 에른스트 체르멜로는 정렬 정리를 보다 더 자명한 원리로부터 유도하기 위하여 선택 공리를 도입하였고, 이를 통해 정렬 정리를 증명하였다.^[3]

1923년에 다비트 힐베르트는 일종의 선택 연산을 포함한 논리 체계를 제시하였다.^[4][5] 힐베르트는 이 기호를 ${\displaystyle \epsilon }$이라고 표기하였다. 예를 들어, 술어 ${\displaystyle P(x)}$에 대하여 ${\displaystyle \epsilon (P)}$는 (만약 ${\displaystyle \exists xP(x)}$라면) ${\displaystyle P(\epsilon (P))}$를 만족시키는 집합이다. 이와 유사하게, 니콜라 부르바키는 1954년에 집합론 교재에서 선택 연산 ${\displaystyle \tau }$를 사용하였다.^[6]

1924년에 알프레트 타르스키는 타르스키 정리(선택 공리가 모든 무한 집합 ${\displaystyle X}$에 대하여 ${\displaystyle |X|=|X^{2}|}$인 것과 동치)를 프랑스의 한 유명 저널에 출판하려 하였는데, 이때 원고를 심사한 모리스 르네 프레셰는 "자명하게 참인 두 명제의 동치는 출판될 가치가 없다"고 답변하였고, 반면 같은 원고를 심사한 앙리 르베그는 "자명하게 거짓인 두 명제의 동치는 출판될 가치가 없다"고 답변하였다고 한다.^[7]:209 타르스키는 결국 논문을 타 저널에 출판하였다.^[1]

1938년에 쿠르트 괴델은 내부 모형 이론을 사용하여, 선택 공리가 체르멜로-프렝켈 집합론과 일관적임을 보였다.^[8][9] 구체적으로, 구성 가능 전체 ${\displaystyle L}$은 체르멜로-프렝켈 집합론의 모형이며, 이 모형에서는 선택 공리가 성립한다. 폴 코언은 강제법을 사용하여 선택 공리의 부정이 체르멜로-프렝켈 집합론과 일관적임을 보였다.

의존적 선택 공리는 1942년에 파울 베르나이스가 도입하였다.^[10]

현재까지도, 많은 수학자들은 선택 공리에 대하여 회의적인 입장을 보인다. 미국의 수학자 제리 로이드 보나(영어: Jerry Lloyd Bona, 1945~)는 1977년에 이에 대하여 다음과 같이 농담하였다.

“	선택 공리는 당연히 참이고, 정렬 정리는 당연히 거짓이고, 초른 보조정리는 글쎄……? The Axiom of Choice is obviously true; the Well Ordering principle is obviously false; and who can tell about Zorn’s lemma?	”
	— [11]:145, §6.21

이는 위 세 명제가 체르멜로-프렝켈 집합론 아래 서로 동치이지만 직관적으로는 그 참·거짓 여부가 모순되게 보인다는 것에 대한 농담이다.