定義 濃度 κ, λ が比較可能 ⇔ κ≦λ または λ≦κ

定理1 次の命題は( ZF 上)同値

1. 選択公理
2. 任意の濃度 κ, λ は比較可能
3. ₀≦κ, λ ならば κ, λ は比較可能
4. 任意の濃度 κ, λ について， κ≦^*λ または λ≦^*κ ．
5. ₀≦κ, λ ならば κ≦^*λ または λ≦^*κ ．

証明 (1 ⇒ 2) X と Y を任意の集合とする．整列可能定理により X, Y を整列する．すると整列順序の性質から | X |≦| Y | または | Y |≦| X | が分かる．

2 ⇒ 3と3 ⇒ 5と2 ⇒ 4と4 ⇒ 5は明らか．

(5 ⇒ 1)整列可能定理を示す． X を任意の集合として Y := X∪N とする．「 |A|≦^*|B| ならば |A|≦|P(B)| 」であることに注意すると， |Γ(P(Y))||P(Y)| より |Γ(P(Y))|^*| Y | が分かる．従って仮定4から |Y|≦^*|Γ(P(Y))| となる．よって全射 f: Γ(P(Y))→Y が存在する． Γ(P(Y)) は順序数だから， g(a) := min f^-1(a) として単射 g: Y→Γ(P(Y)) が得られる．よって Y は整列可能であり， X⊂Y だから X も整列可能である．

濃度の比較可能性に制限を加えた，次の命題を考える．

命題2 任意の濃度 μ に対して「 μ≦κ₀≦2^μ, μ≦κ₁≦2^μ なる濃度 κ₀, κ₁ は比較可能」である．

補題3 命題2 ⇒ 無限順序数 α に対して |Γ(α)|≦|P(α)|

証明 α を無限順序数として κ := |P(α)| と置く． ₀≦κ だから κ+1=κ である．また κ²=(2^|α|)²=2^2|α|=2^|α|=κ である．ここで κ^† を考える． κ^† の性質により κ < κ^†≦2^κ2 だから κ≦κ^†≦2^κ が分かる．一方 |Γ(α)|≦2^2|α|2=2^2|α|=2^κ であるから κ≦κ+|Γ(α)|≦2^κ+2^κ=2^κ+1=2^κ となる．故に仮定から κ^† と κ+|Γ(α)| は比較可能である．

(i) κ^†≦κ+|Γ(α)| のとき
κ < κ^†=2^κ≦|Γ(α)| である．

κ=|P(α)| で， |Γ(α)| はアレフだから P(α) は整列可能である． |P(α)|| α | だから Γ(α) の最小性により |Γ(α)|≦|P(α)| となる．

(ii) κ+|Γ(α)|≦κ^† のとき
|Γ(α)|≦κ^† である． κ^†=|K(P(α))| だったから， W⊂K(P(α)) で |W| = |Γ(α)| となるものが取れる． K の定義より，各 f∈W はある順序数から P(α) への単射である． W は整列可能なので X := ∪_f∈WIm(f) (⊂P(α)) も整列可能となる． =|X| と置く． X⊂P(α) だから Γ(X)≦Γ(P(α)) である．また X の定義より W⊂K(X) であり， | W |≦|K(X)| となる．ここで Γ(α)≦Γ(P(α)) であるが，もし Γ(α) < Γ(P(α)) ならば Γ(P(α)) の最小性より |Γ(α)|≦|P(α)| となるから， Γ(α)=Γ(P(α)) としてよい．このとき

< ^*=|Γ(X)|≦|Γ(P(α))|=|Γ(α)|

となる．よって Γ(α) の最小性から ≦|α| なので

|Γ(α)|=|W|≦|K(X)|=^†=2≦2^|α|=|P(α)|

である．

定理4 選択公理 ⇔ 命題2

証明 ⇒ は定理1より明らか． ⇐ を示す．その為には整列可能定理と同値な「順序数 α に対して P(α) は整列可能」を示せばよい．

α を順序数とする． α は無限順序数としてよい．順序数 Γ(α) に補題3を適用して | Γ(Γ(α)) |≦| P(Γ(α)) | を得る．よって | Γ(α) |≦| Γ(Γ(α)) |≦| P(Γ(α)) |=2^{| Γ(α) |} となる． | α |≦| Γ(α) | だから | Γ(α) |≦| Γ(α) |+2^{| α |}≦2^{| Γ(α) |}+2^{| Γ(α) |}=2^{| Γ(α) |} である．従って仮定により | Γ(Γ(α)) | と | Γ(α) |+2^{| α |} は比較可能である．

| Γ(Γ(α)) |≦| Γ(α) |+2^{| α |} と仮定すると| Γ(Γ(α)) |≦| Γ(α) | または | Γ(Γ(α)) |≦2^{| α |} でなければならないが，どちらも成立せず，矛盾する．よって | P(α) |=2^{| α |}≦| Γ(α) |+2^{| α |}≦| Γ(Γ(α)) | となり P(α) は整列可能である．

系 一般連続体仮説( κ≦μ≦2^κ ならば μ=κ または μ=2^κ ) ⇒ 選択公理

定理5 次の命題は( ZF 上)同値

1. 選択公理
2. μ < 2^κ ならば κ と μ は比較可能である．
3. < 2^κ ならば κ と は比較可能である．

証明 1 ⇒ 2と2 ⇒ 3は明らか．

(3 ⇒ 1)整列可能定理を示す． X を任意の集合として κ := | X | と置く．κ^*≦2^22κ である． κ^* はアレフだから，もし κ^*=2^22κ ならば κ≦2^22κ=κ^* より X は整列可能である．そこで κ^* < 2^22κ だとすると仮定3により κ^* と 2^2κ は比較可能である．もし 2^2κ≦κ^* ならば κ≦2^2κ≦κ^* となり X は整列可能である．そこで κ^* < 2^2κ だとすると再び仮定3により κ^* と 2^κ は比較可能である．もし 2^κ≦κ^* ならば κ≦2^κ≦κ^* となり X は整列可能である．そこで κ^* < 2^κ だとすると再び仮定3により κ^* と κ は比較可能である．このとき κ^* の定義から κ≦κ^* となり， X は整列可能である．

補題6 κ+1=κ ならば 2^κ-κ=2^κ

証明 κ=|X| となる集合 X を取る． X∋x |→ { x } ∈P(X) により X⊂P(X) とみなしたとき | P(X) |≦| P(X)＼X | を示せばよい．

X に含まれない元 ∞ を一つ取り Y := X∪{ ∞ } と置く． f: P(X)→P(Y)＼Y を f(Y) := Y∪{ ∞ } で定める．これは明らかに単射だから | P(X) |≦| P(Y)＼Y | である．ここで κ+1=κ だから | Y |=| X | であり，よって | P(Y)＼Y |=| P(X)＼X | となる．従って | P(X) |≦| P(X)＼X | ．

定理 選択公理
⇔ κ₀, κ₁≧₀ とする．次の条件を満たすとき κ₀ と κ₁ は比較可能である． ある μ≧κ₀, κ₁ が存在して，任意の ν₀, ν₁ に対して「 κ₀+ν₀=κ₁+ν₁=μ⇒ν₀=ν₁ 」

証明 ( ⇒ )明らか

( ⇐ )定理の条件3を示す． κ₀, κ₁ を ₀≦κ₀, κ₁ なる濃度とする． μ:=2^κ₀+κ₁ と置けば μ≧κ₀, κ₁ である． κ₀+ν₀=μ とすると補題6より明らかに ν₀=μ である． κ₁ についても同様だから，「 κ₀+ν₀=κ₁+ν₁=μ⇒ν₀=ν₁ 」が成立する．よって κ₀, κ₁ は比較可能である．

定理7 次の命題は( ZF 上)同値

1. 選択公理
2. 任意の x, y に対して | P_fin(x) | と | P_fin(y) | は比較可能である．
3. 任意の x, y に対して | x | と | P_fin(y) | は比較可能である．
4. 任意の x, y に対して | x |≦| P_fin(y) | または | y |≦| P_fin(x) | である．

証明 1 ⇒ 2と1 ⇒ 3は明らか．

(2 ⇒ 4) | P_fin(x) |≦| P_fin(y) | ならば | x |≦| P_fin(x) |≦| P_fin(y) | であり， | P_fin(y) |≦| P_fin(x) | ならば | y |≦| P_fin(y) |≦| P_fin(x) | である．

(3 ⇒ 4) | x |≦| P_fin(y) | ならばよい． | P_fin(y) |≦| x | ならば | y |≦| P_fin(y) |≦| x |≦| P_fin(x) | である．

(4 ⇒ 1)整列可能定理を示す． x を集合として y:=Γ(P_fin(x)) と置く．仮定4より | x |≦| P_fin(y) | または | y |≦| P_fin(x) | である． y の定義により | y || P_fin(x) | だから | x |≦| P_fin(y) | となる． y は順序数だから| y |=| P_fin(y) | である．

故に | x |≦| y | である．よって x は整列可能である．