선택 공리

줄마다 점이 하나씩 들어 있는 표에서 하나씩 골라 봅니다. 유한할 때와 무한할 때가 왜 다른지 봅니다.

고르는 행위를 함수로 만들 수 있는지가 문제입니다. 집합이 유한하면 하나씩 직접 고르면 됩니다. 무한히 많으면 고르는 규칙 자체를 보장해야 합니다. 그 보장이 바로 선택 공리입니다.

예를 들면, 📦 상자마다 🍬 사탕이 들어 있습니다. 상자가 세 개면 손으로 하나씩 꺼내면 됩니다. 상자가 끝없이 많으면 '각 상자에서 하나'라는 규칙이 필요합니다. 눈으로 다 확인할 수 없기 때문입니다.

∀i∈I  (Xi≠∅)⇒∏i∈IXi≠∅\forall i \in I\;(X_i \ne \varnothing) \Rightarrow \prod_{i \in I} X_i \ne \varnothing
c:{Xi}i∈I→⋃iXi,c(Xi)∈Xic: \{X_i\}_{i \in I} \to \bigcup_i X_i,\quad c(X_i) \in X_i

예제

유한한 집합족에 대해서는 선택 공리가 필요 없음을 증명하세요: X1,…,XmX_1, \dots, X_m이 모두 비어 있지 않은 집합이면, 각 XiX_i에서 원소를 하나씩 뽑는 튜플 (x1,…,xm)(x_1, \dots, x_m)이 존재합니다 (mm에 대한 귀납법).

X1,…,Xm≠∅ ⇒ ∃ (x1,…,xm):xi∈XiX_1, \dots, X_m \ne \varnothing \ \Rightarrow\ \exists\,(x_1, \dots, x_m): x_i \in X_i
m=3m = 3, seed =1= 1: 세 상자에 각각 3,4,53, 4, 5개의 공이 있고, 선택된 튜플은 (2,3,4)(2, 3, 4)입니다 (0부터 센 인덱스). 상자가 유한하므로 이런 선택을 손으로 직접 만들 수 있습니다.
증명 보기

  1. m=1m = 1일 때: X1≠∅X_1 \ne \varnothing이므로 원소 x1∈X1x_1 \in X_1이 존재합니다 — 존재 명제의 인스턴스화일 뿐, 선택이 아닙니다. 튜플 (x1)(x_1)이 구하는 것입니다.

  2. 귀납 단계: X1,…,XmX_1, \dots, X_m에서 튜플 (x1,…,xm)(x_1, \dots, x_m)이 이미 뽑혔다고 가정합니다 (xi∈Xix_i \in X_i). Xm+1≠∅X_{m+1} \ne \varnothing이므로 원소 xm+1∈Xm+1x_{m+1} \in X_{m+1}이 존재하고, (x1,…,xm,xm+1)(x_1, \dots, x_m, x_{m+1})이 m+1m+1개의 집합에 대한 튜플이 됩니다.

  3. 따라서 모든 유한한 mm에 대해 튜플이 존재합니다.

    핵심은 매 단계마다 이름이 붙은 집합 하나에서만 원소를 고른다는 점입니다 — 무한히 많은 집합에서 "동시에" 고르는 일이 없어서 선택 공리가 필요 없습니다.

    무한족에서는 이 귀납법이 끝나지 않으며, 바로 그 지점에서 공리가 등장합니다.

선택 공리는 "비어 있지 않은 집합들의 곱은 항상 비어 있지 않다"는 명제와 동치임을 양방향으로 증명하세요.

AC  ⟺  (Xi≠∅ ∀i ⇒ ∏i∈IXi≠∅)\mathrm{AC} \iff \left( X_i \ne \varnothing\ \forall i \ \Rightarrow\ \prod_{i \in I} X_i \ne \varnothing \right)
m=4m = 4, seed =2= 2: 네 상자에 각각 3,5,3,53, 5, 3, 5개의 공이 있고, 선택된 튜플 (1,1,2,0)(1, 1, 2, 0)은 곱집합 X1×X2×X3×X4X_1 \times X_2 \times X_3 \times X_4의 원소 그 자체입니다.
증명 보기

  1. (⇒\Rightarrow) 선택 공리를 가정하고, 비어 있지 않은 집합족 (Xi)i∈I(X_i)_{i \in I}를 잡습니다.

    공리는 각 ii에 대해 c(i)∈Xic(i) \in X_i인 선택함수 cc를 줍니다.

    튜플 (c(i))i∈I(c(i))_{i \in I}은 정의상 곱집합 ∏i∈IXi\prod_{i \in I} X_i의 원소이므로, 곱집합은 비어 있지 않습니다.

  2. (⇐\Leftarrow) 반대로 모든 그런 곱집합이 비어 있지 않다고 가정합니다.

    임의의 비어 있지 않은 집합족 (Xi)i∈I(X_i)_{i \in I}에 대해 곱집합 ∏i∈IXi\prod_{i \in I} X_i는 비어 있지 않으므로 원소 tt를 하나 가집니다.

    이 tt는 각 ii에 ti∈Xit_i \in X_i를 대응시키는 튜플 — 즉 선택함수 그 자체입니다.

    따라서 선택 공리가 성립합니다.

선택 공리는 "모든 전사함수는 우역원을 갖는다"는 명제와 동치임을 양방향으로 증명하세요.

AC  ⟺  (f:X↠Y ⇒ ∃ g:Y→X, f(g(y))=y)\mathrm{AC} \iff \left( f: X \twoheadrightarrow Y \ \Rightarrow\ \exists\, g: Y \to X,\ f(g(y)) = y \right)
m=5m = 5, seed =5= 5: 다섯 상자에 각각 3,4,5,2,33, 4, 5, 2, 3개의 공이 있고 선택된 튜플은 (1,3,0,1,0)(1, 3, 0, 1, 0)입니다. 아래 증명의 서로소 합집합을 이 다섯 상자에 적용하면, 사영의 우역원이 바로 이 튜플이 됩니다.
증명 보기

  1. (⇒\Rightarrow) 전사함수 f:X→Yf: X \to Y를 잡습니다.

    각 y∈Yy \in Y에 대해 fiber f−1({y})={x:f(x)=y}f^{-1}(\{y\}) = \{x : f(x) = y\}는 전사성에 의해 비어 있지 않습니다.

    선택 공리를 집합족 (f−1({y}))y∈Y(f^{-1}(\{y\}))_{y \in Y}에 적용하면 각 yy에 대해 g(y)∈f−1({y})g(y) \in f^{-1}(\{y\})인 함수 g:Y→Xg: Y \to X를 얻고, 이는 f(g(y))=yf(g(y)) = y를 만족합니다 — gg는 ff의 우역원입니다.

  2. (⇐\Leftarrow) 모든 전사함수가 우역원을 갖는다고 가정하고, 비어 있지 않은 집합족 (Xi)i∈I(X_i)_{i \in I}를 잡습니다 (I=∅I = \varnothing이면 빈 함수가 선택함수이므로 자명).

    서로소 합집합 X={(i,x):i∈I, x∈Xi}X = \{(i, x) : i \in I,\ x \in X_i\}와 사영 π:X→I\pi: X \to I, π(i,x)=i\pi(i, x) = i를 둡니다.

    각 XiX_i가 비어 있지 않으므로 π\pi는 전사입니다.

  3. π\pi의 우역원 s:I→Xs: I \to X는 π(s(i))=i\pi(s(i)) = i를 만족하므로, s(i)=(i,xi)s(i) = (i, x_i) 꼴이며 xi∈Xix_i \in X_i가 유일하게 정해집니다.

    대응 i↦xii \mapsto x_i가 구하는 선택함수입니다.

    따라서 선택 공리가 성립합니다.

2. 수의 체계