초른 보조정리

모든 사슬이 상계를 가지면 극대 원소가 존재합니다 — 12의 약수들을 나누어떨어짐 순서로 놓고 사슬을 하나씩 비춰보세요. 선택 공리와 동치인, 대수학의 만능 열쇠입니다.

every chain has an upper bound⇒∃ maximal m\text{every chain has an upper bound} \Rightarrow \exists\, \text{maximal } m
1∣2∣4∣12,1∣3∣6∣121 \mid 2 \mid 4 \mid 12,\quad 1 \mid 3 \mid 6 \mid 12

예제

비어 있지 않은 유한 부분순서집합은 항상 극대원소를 가짐을 증명하세요 (Zorn의 보조정리의 유한 버전 — 선택 공리 불필요).

P≠∅ finite poset ⇒ ∃ m∈P maximalP \ne \varnothing\ \text{finite poset} \ \Rightarrow\ \exists\, m \in P\ \text{maximal}
사슬 C0={1,2,4,12}C_0 = \{1, 2, 4, 12\}가 강조 표시된 약수 poset: 이 유한 poset에서는 아래 증명의 "계속 올라가기"가 12에서 멈춥니다.
증명 보기
  1. PP가 비어 있지 않은 유한 부분순서집합이라 하자. 임의의 x0∈Px_0 \in P를 잡습니다. x0x_0가 극대원소이면 증명 끝입니다. 아니면 x0<x1x_0 < x_1인 x1∈Px_1 \in P가 존재합니다 (x0x_0가 극대가 아니라는 것은 정확히 이런 x1x_1이 존재한다는 뜻).
  2. 이 과정을 반복합니다: xkx_k가 극대원소가 아니면 xk<xk+1x_k < x_{k+1}인 xk+1x_{k+1}을 잡습니다. 이렇게 얻는 수열 x0<x1<x2<⋯x_0 < x_1 < x_2 < \cdots의 항들은 모두 다릅니다 (순서 관계의 반대칭성·추이성에 의해 xi<xjx_i < x_j, i<ji < j). 그런데 PP는 유한하므로 서로 다른 원소를 무한히 뽑을 수 없습니다.
  3. 따라서 이 과정은 반드시 멈춥니다 — 어떤 xkx_k가 극대원소입니다. 유한성 때문에 "무한히 올라가기"가 불가능하다는 것이 증명의 전부이며, 무한 poset에서는 이 논증이 깨지고 Zorn의 보조정리(와 선택 공리)가 필요해집니다.

약분가능성(divisibility)으로 순서가 정해진 P={1,2,3,4,6,12}P = \{1, 2, 3, 4, 6, 12\}에서, 모든 사슬이 PP 안에 상한을 가짐을 직접 확인하고, 모든 극대원소를 찾으세요.

C chain ⇒ max⁡C exists and bounds C,maximal(P)={12}C\ \text{chain} \ \Rightarrow\ \max C\ \text{exists and bounds}\ C, \qquad \text{maximal}(P) = \{12\}
사슬 C1={1,2,6,12}C_1 = \{1, 2, 6, 12\}가 강조 표시됨: 이 사슬의 상한은 {12}\{12\} 하나뿐이고, 12는 poset 전체의 유일한 극대원소입니다.
증명 보기
  1. C⊆PC \subseteq P를 임의의 사슬이라 하자. PP는 원소가 6개뿐이므로 CC도 유한하고, 유한 사슬은 최대원소 max⁡C\max C를 가집니다 (유한집합의 전순서 부분집합). c∈Cc \in C인 모든 cc에 대해 c∣max⁡Cc \mid \max C이므로, max⁡C∈P\max C \in P는 CC의 상한입니다. 즉 모든 사슬이 PP 안에 상한을 가집니다.
  2. 구체적으로 세 극대사슬에 대해: C0={1,2,4,12}C_0 = \{1,2,4,12\}의 상한은 {12}\{12\}, C1={1,2,6,12}C_1 = \{1,2,6,12\}의 상한은 {12}\{12\}, C2={1,3,6,12}C_2 = \{1,3,6,12\}의 상한은 {12}\{12\}입니다 (12를 포함하는 사슬의 상한은 12의 배수여야 하고, PP 안의 12의 배수는 12뿐). 짧은 사슬도 마찬가지입니다: 예를 들어 {1,2}\{1, 2\}의 상한은 {2,4,6,12}\{2, 4, 6, 12\}, {1,3}\{1, 3\}의 상한은 {3,6,12}\{3, 6, 12\}입니다.
  3. 극대원소: x∈Px \in P가 극대원소이려면 xx를 진짜로 나누는(약분가능성에서 xx보다 큰) PP의 원소가 없어야 합니다. 1∣21 \mid 2, 2∣42 \mid 4, 3∣63 \mid 6, 4∣124 \mid 12, 6∣126 \mid 12이므로 1,2,3,4,61, 2, 3, 4, 6은 극대원소가 아닙니다. 1212의 배수 중 PP에 속한 것은 1212뿐이므로 1212는 극대원소이고, 유일합니다. Zorn의 보조정리가 약속한 대로입니다.

Zorn의 보조정리가 선택 공리를 함의함을 증명하세요: 비어 있지 않은 집합족 (Xi)i∈I(X_i)_{i \in I}에 대해, 부분 선택함수들의 poset에 Zorn의 보조정리를 적용하세요. (역방향 AC ⇒\Rightarrow Zorn은 여기서 증명하지 않습니다 — 초한귀납법이 필요한 idea-level 논증입니다.)

P={f:dom⁡f⊆I, f(i)∈Xi},f≤g  ⟺  g extends fP = \{f : \operatorname{dom} f \subseteq I,\ f(i) \in X_i\}, \quad f \le g \iff g\ \text{extends}\ f
사슬 C2={1,3,6,12}C_2 = \{1, 3, 6, 12\}가 강조 표시됨: Zorn의 보조정리는 "모든 사슬이 상한을 가지면 극대원소가 존재한다"는 주장이고, 아래 증명은 이 주장을 선택함수 존재 문제에 그대로 적용합니다.
증명 보기
  1. 비어 있지 않은 집합족 (Xi)i∈I(X_i)_{i \in I}를 고정합니다. 부분 선택함수들의 집합 P={f:dom⁡f⊆I, f(i)∈Xi}P = \{f : \operatorname{dom} f \subseteq I,\ f(i) \in X_i\}를 확장 순서로 정렬합니다: f≤gf \le g는 dom⁡f⊆dom⁡g\operatorname{dom} f \subseteq \operatorname{dom} g이고 gg가 dom⁡f\operatorname{dom} f 위에서 ff와 일치한다는 뜻입니다. PP는 비어 있지 않습니다 (빈 함수가 원소).
  2. PP의 임의의 사슬 C\mathcal{C}에 대해 합집합 u=⋃Cu = \bigcup \mathcal{C}를 둡니다. 사슬 조건 덕분에 uu는 함수입니다: f,g∈Cf, g \in \mathcal{C}가 ii에서 모두 정의되면 둘 중 큰 쪽이 다른 쪽을 확장하므로 f(i)=g(i)f(i) = g(i)입니다. dom⁡u=⋃f∈Cdom⁡f\operatorname{dom} u = \bigcup_{f \in \mathcal{C}} \operatorname{dom} f이고 u(i)∈Xiu(i) \in X_i이므로 u∈Pu \in P이며, 모든 f∈Cf \in \mathcal{C}에 대해 f≤uf \le u — 즉 uu는 사슬의 상한입니다.
  3. Zorn의 보조정리에 의해 PP는 극대원소 mm을 가집니다. dom⁡m=I\operatorname{dom} m = I임을 보입니다: 아니라면 i0∈I∖dom⁡mi_0 \in I \setminus \operatorname{dom} m이 존재하고, Xi0≠∅X_{i_0} \ne \varnothing이므로 x0∈Xi0x_0 \in X_{i_0}를 잡아 mm을 i0↦x0i_0 \mapsto x_0으로 확장한 m′m'를 만들 수 있습니다. m<m′m < m'이므로 mm의 극대성에 모순입니다. 따라서 mm은 모든 II에서 정의된 선택함수입니다 — 선택 공리가 성립합니다.
  4. 참고: 역방향 (AC ⇒\Rightarrow Zorn)은 순서수를 이용한 초한귀납법으로 사슬을 극대사슬까지 늘리는 논증이 필요하며, 여기서는 idea-level 진술로만 남깁니다 — 위의 Zorn ⇒\Rightarrow AC 방향은 완전히 증명되었습니다.

1. 수의 체계