超限帰納法抜きで選択公理から Zorn の補題を証明してみた

縫田光司

平成 23 年 12 月 8 日

概要

このノートでは、超限帰納法を使わずに選択公理から Zorn の補題を導く証明を与える（ただし、悲しいことにノートを書いてから気が付いたのだが、証明の本質的なアイデアは H. Rubin, J. E. Rubin, “Equivalents of the Axiom of Choice, II”, Second Edition, Studies in Logic and the Foundations of Mathematics vol.116, North-Holland, 1985 の定理 4.19 の証明と同じであった）。

このノートを通して、 (X, ≤) は任意の空でない半順序集合であって、どの鎖（全順序部分集合もしくは線形順序部分集合と呼ばれる場合もある） C も（≤ に関する） X における上界（つまり、 x ∈ X であって任意の c ∈ C について c ≤ x を満たすもの）を持つという性質を持つものとする。このとき Zorn の補題とは、このような X が常に（≤ に関する）極大元（つまり、 x ∈ X であって、 x < y となる y ∈ X が存在しないもの）を持つというものである。選択公理から Zorn の補題を（集合論の Zermelo–Fraenkel 公理系の下で）証明する際、「自然な」方針を採ろうとすると通常は超限帰納法のお世話になるのだが、このノートでは超限帰納法を使わない証明を紹介する。

背理法の仮定として、 X は冒頭に述べた条件を満たす半順序集合であるけれども、極大元を持たないものとする。この仮定から出発して矛盾を導く。

まず定義や用語をいくつか準備しておく。

• C ⊂ Y ⊂ X かつ C が鎖であるときに、 C が Y において有界であるとは、ある元 x ∈ Y \ C が存在して、全ての c ∈ C について c < x が成り立つことを指すものとする。

• X の鎖 C が整列されているとは、 C の任意の空でない部分集合が最小元を持つことを指すものとする。

• 鎖 C と元 c ∈ C について、部分集合 {d ∈ C | d < c} を c による C の始切片と呼び、 s_{C}(c) と記す。

X の空でない鎖全体の集合を C と記す。各 C ∈ C について、 U_{C} = {x ∈ X \ C | 全てのc ∈ C についてc < x} と定義する。ここで以下の性質を注意しておく。補題 1. 全ての C ∈ C について U_{C} ≠ ∅ が成り立つ。

Proof. Zorn の補題の前提より、 C は上界 x ∈ X を持つ。各 y ∈ U_{{x}} について、 c ≤ x < y （従って c < y）が全ての c ∈ C で成り立つことから、 y ∉ C、また y ∈ U_{C} となる。よって U_{{x}} ⊂ U_{C} であるが、一方で X が極大元を持たないという背理法の仮定から U_{{x}} ≠ ∅ となるので、結局 U_{C} ≠ ∅ が成り立つ。

集合族 {U_{C}}_{C∈C} の選択関数 f であって、後の議論に都合の良い性質を備えているものを（選択公理を用いて）構成したい。

各 C_{1}, C_{2} ∈ C について、 C_{1} ∼_{pre} C_{2} という関係を、鎖 C_{1} ∩ C_{2} が C_{1} と C_{2} のいずれにおいても有界でないという関係として定義する。このとき ∼_{pre} は C 上の対称な関係である。そして、 C 上の同値関係 ∼ を ∼_{pre} の推移閉包として定義する。即ち C_{1} ∼ C_{2} は、 C の要素の有限列 C_{1} = C′_{0}, C′_{1}, …, C′_{n} = C_{2} （n ≥ 0）であって、各 0 ≤ i ≤ n − 1 について C′_{i} ∼_{pre} C′_{i+1} を満たすことと同値である。 C_{1} ∼ C_{2} かつ C_{1} が最大元 c を持つならば、 c ∈ C_{2} であり c が C_{2} の最大元でもあることを注意しておく。ここで以下の補題が成り立つ。

補題 2. もし C_{1}, C_{2} ∈ C かつ C_{1} ∼ C_{2} であれば、 U_{C_{1}} = U_{C_{2}} が成り立つ。

Proof. C_{1} ∼_{pre} C_{2} のときに U_{C_{1}} ⊂ U_{C_{2}} が成り立つことを示せば充分である。 x ∈ U_{C_{1}} とする。もし x ∈ C_{2} であるとすると、 x ∈ C_{2} \ (C_{1} ∩ C_{2}) であって x は C_{1} の、従って C_{1} ∩ C_{2} の上界であるため、 C_{1} ∩ C_{2} が C_{2} において有界となり、 C_{1} ∼_{pre} C_{2} という前提に矛盾する。よって x ∉ C_{2} が成り立つ。また、もしある c ∈ C_{2} について c ≮ x であるとすると、 C_{1} ∩ C_{2} が C_{2} において有界でないという前提から、 c ≤ d ≮ x を満たすような元 d ∈ C_{1} ∩ C_{2} が存在する。特に d ∈ C_{1} かつ d ≮ x となるが、これは x ∈ U_{C_{1}} という x の選び方に矛盾する。以上より全ての c ∈ C_{2} について c < x となり、 x ∈ U_{C_{2}} が成り立つ。

同値関係 ∼ による同値類 E の各々について、 U_{E} ⊂ X を U_{E} = U_{C} ただし C ∈ E、と定義すると、補題 2 より U_{E} は C ∈ E の選び方に依らずきちんと定まる。\underline{選択公理を用いて}、集合族 \{U_{E}\}_{E∈X/∼} の選択関数 f を得る。さらに、表記の簡略化のため、各 C ∈ C について f(C) = f([C]) （ただし [C] は C の ∼-同値類）と記す。すると各 C ∈ C について f(C) ∈ U_{C} であり、また C_{1}, C_{2} ∈ C かつ C_{1} ∼ C_{2} であれば f(C_{1}) = f(C_{2}) が成り立つ。

以下、元 x_{0} ∈ X を一つ固定する。ここで以下の定義を導入する。

• 鎖 C ∈ C が f-継続的であるとは、 C が整列されており、 x_{0} が C の最小元であり、さらに全ての c ∈ C \ {x_{0}} について f(s_{C}(c)) = c が成り立つことを指すものとする。

f-継続的な鎖に関するいくつかの性質を述べる。補題 3. 鎖 C ∈ C が f-継続的であり、 C の空でない部分集合 C′ が C において有界であるとする。このとき、 C \ C′ に属する C′ の上界全体の集合の最小元を d とすると、 f(C′) = d が成り立つ。

Proof. C′ ∈ C であることを注意しておく。また、 C が整列されており C′ が C において有界であることから、主張にあるような元 d は確かに存在することを注意しておく。ここで s_{C}(d) ∼ C′ を示すことができれば、 f の定義と C が f-継続的であることから f(C′) = f(s_{C}(d)) = d となるため、 s_{C}(d) ∼ C′ を示せば充分である。まず、 C′ ⊂ s_{C}(d) であるから、 s_{C}(d) ∩ C′ = C′ は C′ において有界でない。一方、 x ∈ s_{C}(d) \ C′ のとき、 d の最小性より x は C′ の上界ではあり得ない。よって C′ は s_{C}(d) において有界でない。従って s_{C}(d) ∼ C′ が成り立つ。

補題 4. C_{1}, C_{2} ∈ C が f-継続的な鎖であるとき、以下の三つの条件のうちちょうど一つが成り立つ。

1. C_{1} = C_{2}

2. C_{1} は C_{2} の始切片である

3. C_{2} は C_{1} の始切片である

Proof. 二つ以上の条件が同時に成り立たないことは明らかである。

まず、各 i ∈ {1, 2} について、 x ∈ C_{1}∩C_{2} かつ y ∈ s_{C_{i}}(x) ならば y ∈ C_{1}∩C_{2} が成り立つことを示す。背理法を使うために、このようなある x について反例となる y が存在すると仮定して、最小の反例を y と記す（C_{i} は整列されているため、そのような y は確かに存在する）。 x_{0} ∈ C_{1} ∩ C_{2} なので s_{C_{i}}(y) ≠ ∅ である。 y の選び方より、 s_{C_{i}}(y) ⊂ C_{3−i} かつ y ∉ C_{3−i} が成り立つ。 C_{i} は f-継続的なので f(s_{C_{i}}(y)) = y である。一方、 x ∈ C_{1} ∩ C_{2} かつ y < x なので C_{3−i} の部分集合 s_{C_{i}}(y) は C_{3−i} において有界であり、従って補題 3 より f(s_{C_{i}}(y)) ∈ C_{3−i} が成り立つ。しかし、これは性質 y ∉ C_{3−i} と矛盾する。従ってこの段落の冒頭の主張が成り立つ。さらに、 C_{1} と C_{2} はともに整列されているため、上の事実は各 i ∈ {1, 2} について C_{1} ∩ C_{2} が C_{i} と一致するかもしくは C_{i} の始切片であることを導く（C_{1} ∩C_{2} ≠ C_{i} のとき、 C_{i} \(C_{1} ∩C_{2}) の最小元を考えればよい）。

後は C_{1} ∩ C_{2} が C_{1} または C_{2} と一致することを示せば充分である。そうでないと仮定して矛盾を導く。このとき C_{1} ∩ C_{2} は C_{1} と C_{2} 両方の始切片であり、 C_{1} と C_{2} は f-継続的なので、 f(C_{1} ∩ C_{2}) ∈ C_{1} ∩ C_{2} が成り立つ。しかし、一方で f の定義より f(C_{1} ∩ C_{2}) ∉ C_{1} ∩ C_{2} なので、矛盾である。以上より主張が成り立つ。

f-継続的な鎖全ての和集合を C_{0} と記す（{x_{0}} ∈ C が f-継続的なので、 f-継続的な鎖が少なくとも一つ存在することを注意しておく）。このとき補題 4 より C_{0} ∈ C が成り立つ（x, y ∈ C_{0} のとき、 f-継続的な鎖 C と C′ でそれぞれ x と y を含むものが存在し、件の補題より x ∈ C ⊂ C′ もしくは y ∈ C′ ⊂ C である）。ここで以下の補題を準備しておく。

補題 5. 各 c ∈ C_{0} について、 C が c を含む f-継続的な鎖ならば s_{C_{0}}(c) = s_{C}(c) が成り立つ。

Proof. まず、 C_{0} の定義より C ⊂ C_{0} なので s_{C}(c) ⊂ s_{C_{0}}(c) であることを注意しておく。後は各 d ∈ s_{C_{0}}(c) について d ∈ C となることを示せばよい。 C_{0} の定義より、 d ∈ C′ となる f-継続的な鎖 C′ が存在する。ここで、 C′ = C′ もしくは C′ が C の始切片である場合には d ∈ C′ ⊂ C が成り立つ。また、 C が C′ の始切片である場合には、 c ∈ C、 d ∈ C′ かつ d < c なので、やはり d ∈ C が成り立つ。従って補題 4 より d ∈ C が成り立つ。

以下、 C_{0} 自体が f-継続的であることを証明していく。 x_{0} が C_{0} の最小元であることは明らかである。

補題 6. C_{0} は整列されている。

Proof. A を C_{0} の空でない任意の部分集合とする。 a ∈ A を一つ選んでおき、 a を含む f-継続的な鎖 C を取る（これは C_{0} の定義より存在する）。 C は整列されているため、 A ∩ C は最小元を持つ。それを a_{0} と記す。このとき、もし a′ ∈ A かつ a′ < a_{0} であるとすると、補題 5 より a′ ∈ s_{C_{0}}(a_{0}) = s_{C}(a_{0}) が成り立ち、即ち a′ ∈ A ∩ C かつ a′ < a_{0} となるが、これは a_{0} の選び方に矛盾する。従って全ての a′ ∈ A について a′ ≥ a_{0} となり、 a_{0} は A の最小元である。

補題 7. 全ての c ∈ C_{0} \ {x_{0}} について f(s_{C_{0}}(c)) = c が成り立つ。

Proof. c を含む f-継続的な鎖 C を取る（これは C_{0} の定義より存在する）。このとき補題 5 より s_{C_{0}}(c) = s_{C}(c) が成り立つ。 C は f-継続的なので、 f(s_{C_{0}}(c)) = f(s_{C}(c)) = c となる。

補題 6 と補題 7 より、 C_{0} は確かに f-継続的である。さて、このとき C_{0} ∪ {f(C_{0})} もまた f-継続的な鎖となるが、これは C_{0} の部分集合ではないため、 C_{0} の定義と矛盾する。従って背理法により、 X は極大元を持つ。以上で Zorn の補題が証明された。

おまけ：超限帰納法を用いた証明

このおまけでは、比較参考として、超限帰納法を用いて選択公理から Zorn の補題を導く証明を与える。最初に、超限再帰的定義に関する原理を述べておく（例えばケネス・キューネン著、藤田博司訳『集合論 独立性証明への案内』（日本評論社、 2008 年、原題： SET THEORY, An Introduction to Independence Proofs）第 I 章定理 9.3 を参照）。

定理 1. φ(x, y) を（Zermelo–Fraenkel 集合論における）式で自由変数 x と y を持ち、 ∀x∃!yφ(x, y) を満たすものとする。このとき、自由変数 x と y を持つ式 Φ(x, y) で以下の二つの条件を満たすものが存在する。

1. ∀x((x ∈ ON → ∃!yΦ(x, y)) ∧ (¬x ∈ ON → ¬∃yφ(x, y)))

2. ∀x(x ∈ ON → ∀y, z(y = Φ↾_{x} ∧φ(y, z) → Φ(x, z)))

ただし、「x ∈ ON」は「x は順序数」の略記とし、「Φ↾_{x}」は集合 {⟨a, b⟩ | a ∈ x ∧ Φ(a, b)} （⟨a, b⟩ は a と b の順序対）の略記とする。

この定理の直感的な意味は以下の通りである。即ち、順序数全体（これは集合をなさないのであるが）で定義される「関数」 Φ を定義したいとき、順序数 α における値を α より小さな順序数における値から定める方法を指定すれば、その条件を満たす「関数」 Φ が確かに存在する。この定理は ZF 集合論における定理であり、選択公理は用いていないことを注意しておく。

定理 1 （と超限帰納法）を用いて、選択公理から Zorn の補題を証明する。 X ≠ 0 を、 Zorn の補題の主張に現れる半順序集合とする。背理法の仮定として、 X は極大元を持たないと仮定する。すると、 X の空でない部分集合 C であってある順序数と同型（特に全順序集合）なものの各々について、 \underline{選択公理を用いて}C の上界 b_{C} ∈ X \ C を一つずつ選ぶことができる。

定理 1 を適用すべく、まず X の元 a を一つ固定しておき、式 φ(x, y) を以下の要領で定義する。

• x = 0 （= ∅）のとき、 φ(x, y) は y = a を意味するように定める。

• x がある順序数 α > 0 から X への関数であって像 Im(x) への（半順序集合としての）同型写像であるとき、 φ(x, y) は y = b_{Im(x)} を意味するように定める（Im(x) は空でない順序数 α と同型なので、 b_{Im(x)} が確かに定義されることに注意）。

• それ以外のとき、 φ(x, y) は y = 0 を意味するように定める。

この式 φ(x, y) は定理 1 の前提を満たすので、定理の主張にあるような式 Φ(x, y) が存在する。ここで以下の補題が成り立つ。

補題 8. x を順序数とし、 x′ を Φ(x, x′) が成り立つ唯一の元とする。

1. このとき x′ ∈ X が成り立つ。

2. このとき、 y < x かつ Φ(y, y′) が成り立つならば X において y′ < x′ である。 Proof. x に関する超限帰納法を用いて証明する。まず、 x = 0 のときは、 φ の定義より x′ = a となるので、件の条件が成り立つ。次に x > 0 のときを考える。超限帰納法の仮定より、定理 1 の主張に現れる集合 Φ ↾_{x} は x から X のある部分集合 C への同型写像となる（x は全順序集合であることに注意）。このとき Φ と φ の定義より x′ = b_{C} となり、従って件の条件は x に関しても成り立つ（二つ目の条件については、 b_{C} ∈ X \ C が C の上界であることから導かれる）。以上より主張が成り立つ。

補題 8 の二つ目の性質より、各 v ∈ X について、 Φ(x, v) を満たす順序数 x は高々一つしか存在しない。 X の部分集合 X′ を、ある（一意に定まる）順序数 x について Φ(x, v) が成り立つような v ∈ X 全体の集合として定める。置換公理を集合 X′ と式 Φ′(x, y) := Φ(y, x) に適用すると、順序数 y のうち、 Φ(y, y′) を満たす唯一の y′ が X′ に属するような y を全て要素に持つ集合 Y の存在が示される。ここで補題 8 の一つ目の性質より、この集合 Y は全ての順序数を要素に持つことになる。しかし、これは Burali–Forti の逆理（即ち、全ての順序数を要素に持つ集合は存在しないという定理）に矛盾する。従って背理法により、 X は極大元を持つ。以上で Zorn の補題が証明された。