집합론 에서 선택 공리 (選擇公理, 영어 : axiom of choice , 약자 AC)는 공집합이 아닌 집합에서 한 원소를 고를 수 있으며, 또한 이를 무한 번 반복할 수 있다는 공리 이다. 직관적으로 자연스러워 보이지만, 비직관적인 결과를 함의한다.
선택 공리의 형상화. 선택 함수는 각 집합
S
i
{\displaystyle S_{i}}
를 그 속의 원소
x
i
∈
S
i
{\displaystyle x_{i}\in S_{i}}
로 대응시킨다.
집합족
{
S
i
}
i
∈
I
{\displaystyle \{S_{i}\}_{i\in I}}
위의 선택 함수 (選擇函數, 영어 : choice function )는 다음 성질을 만족시키는 함수
f
{\displaystyle f}
이다.
f
:
I
→
⋃
i
∈
I
S
i
{\displaystyle f\colon I\to \bigcup _{i\in I}S_{i}}
∀
i
∈
I
:
f
(
i
)
∈
S
i
{\displaystyle \forall i\in I\colon f(i)\in S_{i}}
만약
∅
∈
{
S
i
}
i
∈
I
{\displaystyle \varnothing \in \{S_{i}\}_{i\in I}}
라면,
{
S
i
}
i
∈
I
{\displaystyle \{S_{i}\}_{i\in I}}
는 물론 선택 함수를 가질 수 없다. 선택 공리
A
C
{\displaystyle {\mathsf {AC}}}
에 의하면, 공집합을 포함하지 않는 모든 집합족은 선택 함수를 갖는다.
약화된 형태
임의의 기수
κ
{\displaystyle \kappa }
에 대하여,
A
C
κ
{\displaystyle {\mathsf {AC}}_{\kappa }}
는 "크기가
κ
{\displaystyle \kappa }
이하인, 공집합을 포함하지 않는 집합족은 선택 함수를 갖는다"는 명제이다. 특히,
κ
=
ω
{\displaystyle \kappa =\omega }
일 때
A
C
ω
{\displaystyle {\mathsf {AC}}_{\omega }}
를 가산 선택 공리 (可算選擇公理, 영어 : axiom of countable choice )라고 한다.
임의의 집합
S
{\displaystyle S}
및 이항 관계
R
⊆
S
2
{\displaystyle R\subseteq S^{2}}
가 주어졌고, 또한 이들이 다음 성질들을 만족시킨다고 하자.
S
≠
∅
{\displaystyle S\neq \varnothing }
임의의
s
∈
S
{\displaystyle s\in S}
에 대하여,
(
s
,
t
)
∈
R
{\displaystyle (s,t)\in R}
인
t
∈
S
{\displaystyle t\in S}
가 존재한다.
그렇다면, 의존적 선택 공리 (依存的選擇公理, 영어 : axiom of dependent choice )
D
C
{\displaystyle {\mathsf {DC}}}
에 따르면 다음 성질을 만족시키는 열
s
:
N
→
S
{\displaystyle s\colon \mathbb {N} \to S}
i
↦
s
i
{\displaystyle i\mapsto s_{i}}
이 존재한다.
임의의
i
∈
N
{\displaystyle i\in \mathbb {N} }
에 대하여,
(
s
i
,
s
i
+
1
)
∈
R
{\displaystyle (s_{i},s_{i+1})\in R}
집합족
(
X
i
)
i
∈
I
{\displaystyle (X_{i})_{i\in I}}
가 주어졌으며, 각
X
i
{\displaystyle X_{i}}
위에 정렬 순서
≤
i
{\displaystyle \leq _{i}}
가 주어졌다고 하자. 그렇다면, 선택 함수
f
:
I
→
⋃
i
∈
I
X
i
{\displaystyle f\colon I\to \bigcup _{i\in I}X_{i}}
를 다음과 같이 자명하게 정의할 수 있다.
f
(
i
)
=
min
X
i
{\displaystyle f(i)=\min X_{i}}
특히, 만약
⋃
i
∈
I
X
i
{\displaystyle \textstyle \bigcup _{i\in I}X_{i}}
위에 정렬 순서가 주어졌다면, 이는 각
X
i
{\displaystyle X_{i}}
에 대하여 제한할 수 있으며, 이에 따라 선택 함수를 정의할 수 있다.
함의 관계
체르멜로-프렝켈 집합론 아래, 임의의 자연수
n
∈
N
{\displaystyle n\in \mathbb {N} }
에 대하여
A
C
n
{\displaystyle {\mathsf {AC}}_{n}}
을 증명할 수 있다.
∀
n
∈
N
:
(
Z
F
⊢
A
C
n
)
{\displaystyle \forall n\in \mathbb {N} \colon ({\mathsf {ZF}}\vdash {\mathsf {AC}}_{n})}
즉, 체르멜로-프렝켈 집합론에서는 유한 개의 선택을 할 수 있지만, 무한 개의 선택은 (체르멜로-프렝켈 집합론이 무모순적이라면) 불가능하다.
체르멜로-프렝켈 집합론 아래, 선택 공리는 의존적 선택 공리를 함의하며, 의존적 선택 공리는 가산 선택 공리를 함의한다.
Z
F
⊢
(
A
C
⟹
D
C
⟹
A
C
ω
)
{\displaystyle {\mathsf {ZF}}\vdash \left({\mathsf {AC}}\implies {\mathsf {DC}}\implies {\mathsf {AC}}_{\omega }\right)}
증명 (
D
C
⟹
A
C
ω
{\displaystyle {\mathsf {DC}}\implies {\mathsf {AC}}_{\omega }}
):
집합족
(
X
i
)
i
∈
N
{\displaystyle (X_{i})_{i\in \mathbb {N} }}
이 주어졌다고 하자. 집합
X
=
⨆
X
i
{\displaystyle X=\bigsqcup X_{i}}
위에 다음과 같은 이항 관계
R
⊆
X
2
{\displaystyle R\subseteq X^{2}}
를 정의한다.
(
x
,
y
)
∈
R
⟺
(
∃
i
∈
N
:
x
∈
X
i
∧
y
∈
X
i
+
1
)
{\displaystyle (x,y)\in R\iff (\exists i\in \mathbb {N} \colon x\in X_{i}\land y\in X_{i+1})}
그렇다면,
D
C
{\displaystyle {\mathsf {DC}}}
에 의하여 열
(
x
i
)
i
∈
N
{\displaystyle (x_{i})_{i\in \mathbb {N} }}
∃
k
∈
N
∀
i
∈
N
:
x
i
∈
X
i
+
k
{\displaystyle \exists k\in \mathbb {N} \forall i\in \mathbb {N} \colon x_{i}\in X_{i+k}}
가 존재한다. 따라서
A
C
k
{\displaystyle {\mathsf {AC}}_{k}}
를 사용하여
y
i
∈
X
i
(
i
=
0
,
1
,
…
,
k
)
{\displaystyle y_{i}\in X_{i}\qquad (i=0,1,\dots ,k)}
를 고른 뒤
y
i
+
k
=
x
i
(
i
∈
N
)
{\displaystyle y_{i+k}=x_{i}\qquad (i\in \mathbb {N} )}
이라고 정의하면,
y
i
∈
X
i
∀
i
∈
N
{\displaystyle y_{i}\in X_{i}\forall i\in \mathbb {N} }
이다. 따라서
i
↦
y
i
{\displaystyle i\mapsto y_{i}}
는 가산 무한 집합족
(
X
i
)
i
∈
N
{\displaystyle (X_{i})_{i\in \mathbb {N} }}
의 선택 함수이다.
증명 (
A
C
⟹
D
C
{\displaystyle {\mathsf {AC}}\implies {\mathsf {DC}}}
):
집합
X
{\displaystyle X}
위의 이항 관계
R
⊆
X
2
{\displaystyle R\subseteq X^{2}}
가 주어졌다고 하고, 또한
∀
x
∈
X
∃
y
∈
X
:
(
x
,
y
)
∈
R
{\displaystyle \forall x\in X\exists y\in X\colon (x,y)\in R}
가 성립한다고 하자. 그렇다면, 선택 공리에 의하여 집합족
{
{
y
∈
X
:
(
x
,
y
)
∈
R
}
}
x
∈
X
{\displaystyle \{\{y\in X\colon (x,y)\in R\}\}_{x\in X}}
의 선택 함수
f
:
X
→
{
{
y
∈
X
:
(
x
,
y
)
∈
R
}
}
x
∈
X
{\displaystyle f\colon X\to \{\{y\in X\colon (x,y)\in R\}\}_{x\in X}}
∀
x
∈
X
:
f
(
x
)
∈
{
y
∈
X
:
(
x
,
y
)
∈
R
}
{\displaystyle \forall x\in X\colon f(x)\in \left\{y\in X\colon (x,y)\in R\right\}}
가 존재한다. 임의의 원소
x
0
∈
X
{\displaystyle x_{0}\in X}
를 고르고
x
i
=
(
f
∘
f
∘
⋯
∘
f
)
⏞
i
(
x
0
)
{\displaystyle x_{i}=\overbrace {(f\circ f\circ \cdots \circ f)} ^{i}(x_{0})}
을 정의하면, 이는 의존적 선택 공리에 등장하는 조건을 만족시킨다.
증명 이론적 성질
만약 체르멜로-프렝켈 집합론 (ZF)이 일관적이라면, 선택 공리는 체르멜로-프렝켈 집합론과 독립적이다. 즉, 다음을 보일 수 있다.
Z
F
⊢
Con
(
Z
F
)
⟺
Con
(
Z
F
C
)
{\displaystyle {\mathsf {ZF}}\vdash \operatorname {Con} ({\mathsf {ZF}})\iff \operatorname {Con} ({\mathsf {ZFC}})}
Z
F
⊢
Con
(
Z
F
)
⟺
Con
(
Z
F
¬
C
)
{\displaystyle {\mathsf {ZF}}\vdash \operatorname {Con} ({\mathsf {ZF}})\iff \operatorname {Con} ({\mathsf {ZF\lnot C}})}
모형 이론적 성질
구성 가능 전체 에서는 선택 공리가 성립한다.
Z
F
⊢
(
V
=
L
⟹
A
C
)
{\displaystyle {\mathsf {ZF}}\vdash (V=L\implies {\mathsf {AC}})}
즉, 체르멜로-프렝켈 집합론의 모형
M
{\displaystyle M}
이 주어졌을 때,
M
{\displaystyle M}
속의 구성 가능 전체
L
M
⊆
M
{\displaystyle L^{M}\subseteq M}
은 ZFC의 모형을 이룬다.
반면, 강제법 을 사용하여 선택 공리가 실패하는 모형들을 구성할 수 있다.
선택 공리를 함의하는 명제
체르멜로-프렝켈 집합론 아래, 다음 명제들은 선택 공리를 함의한다.
선택 공리와 동치인 명제
집합족
S
{\displaystyle {\mathcal {S}}}
가 다음 두 조건을 만족시키면, 유한 지표 집합족 (有限指標集合族, 영어 : family of sets of finite character )이라고 한다.
임의의
S
∈
S
{\displaystyle S\in {\mathcal {S}}}
에 대하여,
S
{\displaystyle S}
의 모든 유한 부분 집합은
S
{\displaystyle {\mathcal {S}}}
의 원소이다.
임의의 집합
S
{\displaystyle S}
에 대하여, 만약
S
{\displaystyle S}
의 모든 유한 부분 집합이
S
{\displaystyle {\mathcal {S}}}
의 원소라면,
S
∈
S
{\displaystyle S\in {\mathcal {S}}}
이다.
체르멜로-프렝켈 집합론을 가정하면, 선택 공리는 수많은 동치 명제들을 가지며, 다음과 같다. 즉,
Z
F
⊢
A
C
⟺
A
{\displaystyle {\mathsf {ZF}}\vdash {\mathsf {AC}}\iff A}
인 명제
A
{\displaystyle A}
의 예는 다음을 들 수 있다.
공집합을 포함하지 않는 집합족
S
{\displaystyle {\mathcal {S}}}
에 대하여,
∏
S
≠
∅
{\displaystyle \prod {\mathcal {S}}\neq \varnothing }
이다.
초른 보조정리
정렬 정리
티호노프 정리
(타르스키 정리 , 영어 : Tarski theorem ) 임의의 무한 기수
κ
{\displaystyle \kappa }
에 대하여,
κ
=
κ
2
{\displaystyle \kappa =\kappa ^{2}}
이다.[1]
(기수의 비교 가능성) 임의의 두 기수
κ
1
{\displaystyle \kappa _{1}}
,
κ
2
{\displaystyle \kappa _{2}}
에 대하여,
κ
1
=
κ
2
{\displaystyle \kappa _{1}=\kappa _{2}}
이거나,
κ
1
<
κ
2
{\displaystyle \kappa _{1}<\kappa _{2}}
이거나,
κ
1
>
κ
2
{\displaystyle \kappa _{1}>\kappa _{2}}
이다.
(타이히뮐러-투키 보조정리 , 영어 : Teichmüller–Tukey lemma ) 공집합이 아닌 모든 유한 지표 집합족은 (
⊆
{\displaystyle \subseteq }
에 따른) 극대 원소 를 갖는다.
모든 벡터 공간 은 기저 를 갖는다.
자명환 이 아닌 (단위원을 갖는) 환 은 극대 아이디얼 을 갖는다.
망각 함자
Grp
→
Set
{\displaystyle \operatorname {Grp} \to \operatorname {Set} }
의 상 은 공집합 이 아닌 모든 집합의 모임이다.
(무한군에 대한) 라그랑주 정리 (군론)
모든 연결 그래프 는 생성나무 를 갖는다.
선택 공리로부터 함의되는 명제
만약 체르멜로-프렝켈 집합론 이 일관적이라면 체르멜로-프렝켈 집합론 으로 다음 정리들을 증명할 수 없지만, 선택 공리를 추가하면 증명할 수 있다.
그러나 선택 공리를 의존적 선택 공리(또는 가산 선택 공리)로 약화시킨다면, 이들 가운데 상당수는 증명 불가능하다. 예를 들어, 의존적 선택 공리는 르베그 가측 집합 이 아닌 실수 집합의 존재를 증명할 수 없다.
가산 선택 공리만으로 대부분의 해석학 을 전개할 수 있다.[2]
공식적인 형식화가 없었음에도 불구하고 19세기 말까지 선택 공리는 암묵적으로 수학자들 사이에서 사용되어 왔다. 예를 들어, 집합
X
{\displaystyle X}
가 공집합이 아닌 집합만을 포함한다고 했을 때, 수학자들은 종종 “모든
X
{\displaystyle X}
에 포함된 (집합)
s
{\displaystyle s}
에 대해,
F
(
s
)
{\displaystyle F(s)}
를
s
{\displaystyle s}
의 원소라고 하자” 라고 기술하곤 했다. 일반적으로 (함수)
F
{\displaystyle F}
가 선택 공리 없이 존재할 수 있음을 증명하기란 불가능했고, 그로 인해 체르멜로 이전까지는 이를 심각한 문제로 여기지 않았다.
한편, 모든 함수가 선택 공리를 필요로 하지는 않는다. 유한 집합
X
{\displaystyle X}
의 경우, 선택 공리는 다른 집합론의 공리들로부터 도출될 수 있다. 각각에 적어도 하나의 물건이 담긴 (유한한) 여러 개의 상자들을 상상 해 보자. 이때 우리는 각 상자에서 정확히 하나의 물건을 선택할 수 있다. 예를 들자면 이런 식이다. 첫 번째 상자에서 물건 한 개를 선택하고, 두 번째 상자로 옮겨 여기서도 물건 한 개를 선택한다. 그 후 세 번째 상자에서도 물건을 하나 선택하고, 이런 방식을 유한한 횟수로 반복해서, 마지막 상자에서 물건을 하나 선택하는 것으로 이 과정을 마칠 수 있다. 이 때, 각 상자에서 하나 씩의 물건을 선택함으로써 보여지는 상자-물건의 관계를 선택 함수에 해당한다고 할 수 있다. 그러나 이런 방법은 공집합이 아닌 집합의 모든 가산 집합족에 대해서도 선택 함수가 존재한다는, 가산 선택 공리를 증명하는 데에는 사용될 수 없다. 같은 방법이 공집합이 아닌 집합들의 무한열에 적용될 경우, 각각의 유한한 단계에서는 함수가 정의되나 전체 집합족 에 대한 함수가 정의되는 단계가 존재하지 않게 된다. 결과적으로 체르멜로-프렝켈 집합론 의 체계 아래서 선택 공리 없이는 어떤 “극한” 선택 함수도 구성할 수 없게 되는 것이다.
게오르크 칸토어 는 선택 공리와 동치인 정렬 정리 가 증명이 필요 없을 정도로 자명한 "사고 법칙"(독일어 : Denkgesetz 뎅크게제츠[ * ] )이라고 여겼다. 그러나 다른 수학자들은 이 "사고 법칙"에 대하여 회의적이었다. 1904년에 헝가리의 수학자 쾨니그 줄러 (헝가리어 : Kőnig Gyula )는 정렬 정리를 반증하였다고 발표하였다. 그러나 몇 주 뒤 펠릭스 하우스도르프 가 이 "반증"의 오류를 지적하였다.
1904년에 에른스트 체르멜로 는 정렬 정리 를 보다 더 자명한 원리로부터 유도하기 위하여 선택 공리를 도입하였고, 이를 통해 정렬 정리 를 증명하였다.[3]
1923년에 다비트 힐베르트 는 일종의 선택 연산을 포함한 논리 체계를 제시하였다.[4] [5] 힐베르트는 이 기호를
ϵ
{\displaystyle \epsilon }
이라고 표기하였다. 예를 들어, 술어
P
(
x
)
{\displaystyle P(x)}
에 대하여
ϵ
(
P
)
{\displaystyle \epsilon (P)}
는 (만약
∃
x
P
(
x
)
{\displaystyle \exists xP(x)}
라면)
P
(
ϵ
(
P
)
)
{\displaystyle P(\epsilon (P))}
를 만족시키는 집합이다. 이와 유사하게, 니콜라 부르바키 는 1954년에 집합론 교재에서 선택 연산
τ
{\displaystyle \tau }
를 사용하였다.[6]
1924년에 알프레트 타르스키 는 타르스키 정리(선택 공리가 모든 무한 집합
X
{\displaystyle X}
에 대하여
|
X
|
=
|
X
2
|
{\displaystyle |X|=|X^{2}|}
인 것과 동치)를 프랑스의 한 유명 저널에 출판하려 하였는데, 이때 원고를 심사한 모리스 르네 프레셰 는 "자명하게 참인 두 명제의 동치는 출판될 가치가 없다"고 답변하였고, 반면 같은 원고를 심사한 앙리 르베그 는 "자명하게 거짓인 두 명제의 동치는 출판될 가치가 없다"고 답변하였다고 한다.[7] :209 타르스키는 결국 논문을 타 저널에 출판하였다.[1]
1938년에 쿠르트 괴델 은 내부 모형 이론을 사용하여, 선택 공리가 체르멜로-프렝켈 집합론 과 일관적임을 보였다.[8] [9] 구체적으로, 구성 가능 전체
L
{\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?
”
이는 위 세 명제가 체르멜로-프렝켈 집합론 아래 서로 동치이지만 직관적으로는 그 참·거짓 여부가 모순되게 보인다는 것에 대한 농담이다.
Bourbaki, Nicolas (1954). 《 Éléments de mathematique. Théorie des ensembles. Chapitre 1. Description de la mathématique formelle》 (프랑스어) 1판. Hermann et compagnie. Zbl 0055.27902 .
Herrlich, Horst (2006). 《 Axiom of choice》 . Lecture Notes in Mathematics (영어) 1876 . Springer. doi :10.1007/11601562 . ISBN 978-3-540-30989-5 . ISSN 0075-8434 . Zbl 1102.03049 .
Howard, Paul; Rubin, Jean E. (1998). 《 Consequences of the axiom of choice》 . Mathematical Surveys and Monographs (영어) 59 . American Mathematical Society. ISBN 978-0-8218-0977-8 . 2016년 10월 11일에 원본 문서 에서 보존된 문서. 2016년 8월 5일에 확인함 .
Rubin, Herman; Rubin, Jean E. (1985). 《 Equivalents of the axiom of choice II》 . Studies in Logic and the Foundations of Mathematics (영어) 116 . Elsevier. doi :10.1016/S0049-237X(08)70285-4 . ISBN 9780444877086 . ISSN 0049-237X .
Jech, Thomas (1973). 《 The axiom of choice》 . Studies in Logic and the Foundations of Mathematics (영어) 75 . North-Holland. ISBN 978-0-486-46624-8 . Zbl 0259.02051 .
Moore, Gregory H. (1982). 《 Zermelo’s axiom of choice: its origins, development and influence》 . Studies in the History of Mathematics and Physical Sciences (영어) 8 . Springer. doi :10.1007/978-1-4613-9478-5 . ISBN 978-1-4613-9480-8 . ISSN 0172-570X .
Martin-Löf, Per (2008). 〈 100 years of Zermelo’s axiom of choice: what was the problem with it?〉 (PDF) . Lindström, Sten; Palmgren, Erik; Segerberg, Krister; Stoltenberg-Hansen, Viggo. 《 Logicism, Intuitionism, and Formalism: What Has Become of Them?》 (영어). doi :10.1007/978-1-4020-8926-8_10 . ISBN 1-4020-8925-2 .
Maddy, Penelope (1988년 6월). “ Believing the axioms I” . 《 Journal of Symbolic Logic》 (영어) 53 (2): 481–511. doi :10.2307/2274520 . ISSN 0022-4812 . JSTOR 2274520 . MR 0947855 . Zbl 0652.03033 .
Herrlich, Horst (1997). “ Choice principles in elementary topology and analysis” (PDF) . 《 Commentationes Mathematicae Universitatis Carolinae》 (영어) 38 (3): 545–552. ISSN 0010-2628 . Zbl 0938.54007 .