次の命題をPartition Principleという．

Partition Principle |x|≦^*|y| ならば |x|≦|y| である．

これは「 ～ を集合 X の同値関係とするとき |X/～|≦|X| 」と同値である．つまりPartitionを取ると集合は小さくなるという命題なのである．この命題と選択公理の関係を述べるのがこのページの目的である．

なお，定義については制限された選択公理，有限集合・無限集合の定義，順序数・濃度の簡単なまとめなども参照のこと．

定義 集合 x がidemmultiple ⇔ |x|+|x|=|x|

Weak Partition Principle |x|≦^*|y| ならば |y| < |x| でない．

Idemmultiple Partition Principle y がidemmultipleのとき， |x|≦^*|y| ならば |x|≦|y| である．

PP^- f: y→x を全射として x を整列可能， y をidemmultipleとする．任意の a∈x に対して f^-1(a) がDedekind無限であるならば |x|≦|y| である．

定理 選択公理 ⇒ Partition Principle

定理 Partition Principle ⇒ Weak Partition Principle

定理 Weak Partition Principle ⇒ Idemmultiple Partition Principle

証明 y をidemmultipleで |x|≦^*|y| とする． |x|+|y|≦^*|y|+|y|=|y| だからWeek Partition Principleにより |y| < |x|+|y| でない．故に |y|=|x|+|y| となる．従って |x|≦|y| である．

定理 Idemmultiple Partition Principle ⇒ PP^-

定理 PP^- ⇔ 任意の順序数 α に対して AC_α ．

証明 ⇐ は明らかであるから， ⇒ を示せばよい．

α に関する超限帰納法で示す． { X_β }_β<ωα を非空集合の族とする． γ < ω_α に対して C_γ := Π_β<γX_β と置く．帰納法の仮定から C_γ≠ ∅ である． Γ をHartogs関数として， γ < ω_α に関する超限帰納法で集合 D_γ と基数 λ_γ を

λ_γ := max{ |Γ(∪_δ<γD_δ)|, sup_δ<γλ_δ⁺ }
D_γ := ω×C_γ×λ_γ

と定義し， D := ∪_γ<ωαD_γ ， λ := sup_γ<ωαλ_γ と定める． f: D→λ を射影とすればこれは全射で，任意の μ < λ に対して f^-1(μ) はDedekind無限である． PP^- により単射 g: λ→D が存在する． g が単射だから，任意の β < ω_α に対して，ある β < γ < ω_α と μ < λ が存在して f(μ)∈ω×C_γ×λ_γ となる．故に g を使って { X_β }_β<ωα の選択関数を構成することができる．

定理 双対Bernsteinの定理 ⇒ Weak Partition Principle

証明 |x|≦^*|y| とする． |y| < |x| と仮定する． |y|≦^*|x| である．故に双対Bernsteinの定理から |x|=|y| となり |y| < |x| に矛盾する．従って |y| < |x| でない．

系 双対Bernsteinの定理 ⇒ 任意の順序数 α に対して AC_α．

PP' f: y→x を全射とする．任意の a∈x に対して f^-1(a) が有限またはDedekind無限であるならば |x|≦|y| である．

命題 Partition Principle ⇔ PP'

証明 ⇒ は明らかであるから， ⇐ を示せばよい．

PP' が成り立つとする．明らかに PP^- が成り立つ．よって可算選択公理( AC₀ )が成り立つから，任意の集合は有限またはDedekind無限である．故にPartition Principleが成り立つ．

定理 { X_λ }_λ∈Λ， { Y_λ }_λ∈Λ が互いに素な集合族で， λ∈Λ に対して |X_λ| = |Y_λ| ならば |∪_λ∈ΛX_λ| = |∪_λ∈ΛY_λ| である． ⇒ Partition Principle

証明 PP' を示せばよい．

f: y→x を全射として，任意の a∈x に対して f^-1(a) が有限またはDedekind無限であるとする． a∈x に対して

X_a := f^-1(a)
Y_a := n　(|X_a| = n のとき)
Y_a := X_a { 0 }　(X_a がDedekind無限のとき)

と定める．任意の a∈x に対して |X_a| = |Y_a| だから，仮定により |∪_λ∈ΛX_λ| = |∪_λ∈ΛY_λ| である．任意の a∈x に対して 0∈Y_a だから |x|≦Σ_a∈x|Y_a| = |∪_λ∈ΛY_λ| = |∪_λ∈ΛX_λ| = |y| である．