命題1 任意の濃度 κ, λ について
κ≦λ ⇔ ある濃度 μ が存在して κ+μ= λ

命題2 濃度 κ, λ≧2 に対し κ+λ≦κ・λ ．

命題3 ₀≦κ ならば 2^κ-κ=2^κ ．

命題4 任意のアレフ に対して ²= ．

命題5 任意のアレフ , ' に対し ・'=+'=max { , ' } ．

命題6 濃度 κ, λ, μ とアレフ が κ・≦λ+μ を満たすとき， κ≦λまたは ≦μ．

命題7 濃度 κ, λ, μ とアレフ が κ・λ≦+μ を満たすとき， κ≦ または λ≦μ ．

命題8 濃度 κ, λ とアレフ が ≦κ・λ を満たすとき， ≦κ または ≦λ である．

命題9 P_fin(X) := { Y⊂X | Y は有限集合 } と置くと，整列可能な無限集合 X に対し |X|=|P_fin(X)| ．

命題10 Γ(X):= { α|α は順序数， |α|≦|X| } と置く．この Γ をHartogs関数という．また κ=|X| のとき κ^*:=|Γ(X)| と書く．これをHartogs numberという．Hartogs numberはアレフである．

1. Γ(X) は |α||X| となるような順序数 α のうち最小の順序数である．
2. κ^* は κ となるようなアレフ のうち最小のアレフである．
3. κ^*≦2^2κ2
4. κ^*≦2^22κ
5. 無限濃度 κ に対して κ^**=(κ+κ^*)^*
6. 無限濃度 κ に対して (κ²)^*=κ^*

定理11 κ, λ, μ, ν は無限濃度， はアレフを表すとする．次の命題は( ZF 上)同値．

1. 選択公理
2. 任意の κ に対しある が存在して κ≦ ．
3. κ≦κ^* ．
4. κ・κ^*=κ+κ^* ．
5. κ・λ=κ+λ ．
6. κ²=κ ．
7. κ+κ^*=κ^* ．
8. κ+λ=κ または κ+λ=λ ．
9. κ・κ^*=κ^* ．
10. κ・λ=κ または κ・λ=λ ．
11. 任意の κ に対しある λ が存在して κ=λ² ．
12. κ² =λ² ならば κ=λ ．
13. κ < λ かつ μ < ν ならば κ+μ < λ+ν ．
14. κ < λ かつ μ < ν ならば κ・μ < λ・ν ．
15. κ+μ < λ+μ ならば κ < λ ．
16. κ・μ < λ・μ ならば κ < λ ．
17. κ < λ ならば λ-κ が存在する．
18. κ < λ ならば λ-κ=λ ．
19. κ < λ ならばある μ が存在して λ=κ・μ
20. κ < λ ならば λ÷κ が存在する．
21. κ < λ ならば λ÷κ=λ ．
22. κ+μ=κ+ν ならば μ=ν または μ, ν < κ ．
23. κ+κ < κ+λ ならば κ < λ ．
24. μ < κ かつ ν < κ ならば μ+ν≠κ ．
25. μ < κ かつ ν < κ ならば μ・ν≠κ ．
26. μ^κ < μ^λ かつ μ≠0 ならば κ < λ ．
27. κ^*=μ^*⇒κ=μ ．
28. κ^* < μ < κ+κ^* となる μ は存在しない．
29. κ^* < μ^*⇒κ < μ ．
30. κ^* < ^*⇒κ < ．
31. κ < μ⇒κ^* < μ^* ．
32. < μ⇒^* < μ^* ．
33. κ^* < κ^*+κ⇒κ^**≦κ^*+κ ．
34. κ≦λ+μ ならば κ≦λ または κ≦μ ．
35. κ≦λ+ ならば κ≦λ または κ≦ ．
36. κ≦λ・μ ならば κ≦λ または κ≦μ ．
37. κ≦λ・ ならば κ≦λ または κ≦ ．

証明 (1 ⇒ その他)整列可能定理により，全ての無限濃度はアレフである．よって命題4等から容易に2-37が従う．(26は濃度の比較可能性により対偶が「 κ≧λ ならば μ^κ≧μ^λ または μ= 0 」なので成り立つ．)

(2 ⇒ 1)明らか．

(3 ⇒ 2) κ^* がアレフであるから明らか．

(4 ⇒ 3) κ・κ^*=κ+κ^* とすると， κ^* はアレフだから命題6より κ≦κ^* または κ^*≦κ である． κ^*κ だから κ≦κ^* となる．

(5 ⇒ 4)明らか．

(6 ⇒ 5) κ+λ=(κ+λ)²=κ²+2・κ・λ+λ²≧κ・λ≧κ+λ ．

7 ⇒ 3は明らか．

(8 ⇒ 7) κ+κ^*=κ と仮定すると κ^*≦κ となり矛盾する．故に仮定8より κ+κ^*=κ^* である．

(9 ⇒ 3)明らか．

(10 ⇒ 9) κ・κ^*=κ と仮定すると κ^*≦κ となり矛盾する．故に仮定10より κ・κ^*=κ^* である．

(11 ⇒ 7)仮定11より， κ+κ^*=λ² となる λ が存在する． κ^*≦κ+κ^*=λ² である．よって命題8より κ^*≦λ となる．従って命題1により λ=κ^*+μ となる μ が取れる．このとき

κ+κ^*=λ²=(κ^*+μ)²=(κ^*)²+2・κ^*・μ+μ²≧κ^*・μ.

よって命題6から κ^*≦κ または μ≦κ^* が分かる． κ^*κ なので μ≦κ^* ，従って λ=κ^*+μ≦κ^*+κ^*=κ^* ，故に λ=κ^* である．よって κ+κ^*=λ²=(κ^*)²=κ^* である．

(12 ⇒ 3) λ:=κ^₀ と置くと κ≦λ かつ λ²=κ^2・₀=κ^₀=λ である． (λ+λ^*)²=λ²+2・λ・λ^*+(λ^*)²≧λ・λ^* となるが，一方

(λ+λ^*)²
= λ²+2・λ・λ^*+(λ^*)²
= λ+2・λ・λ^*+λ^*
≦λ・λ^*+2・λ・λ^*　(命題2より)
= λ・(3・λ^*)
= λ・λ^*

だから， (λ+λ^*)²=λ・λ^* となる．よって (λ+λ^*)²=λ・λ^*=λ²・(λ^*)²=(λ・λ^*)² が成り立つ．従って仮定12より λ+λ^*=λ・λ^* である．故に命題6から κ≦λ≦λ^* が分かる．

(13 ⇒ 2) λ:=₀・κ と置くと κ≦λ かつ 2・λ=2・₀・κ=₀・κ=λ である． λ < λ+λ^* かつ λ^* < λ+λ^* と仮定すると仮定13より λ+λ^* < (λ+λ^*)+(λ+λ^*)=2・λ+2・λ^* =λ+λ^* となって矛盾する．故に λ=λ+λ^* または λ^*=λ+λ^* である． λ^*λ なので λ^* =λ+λ^* でなければならない．即ち κ≦λ≦λ^* である．

(14 ⇒ 2) λ:=κ^₀ として13 ⇒ 2と同様にすればよい．

(15 ⇒ 7) κ^* < κ+κ^* と仮定すると κ^*+κ^*=κ^* < κ+κ^* だから仮定15より κ^* < κ となり矛盾する．

(16 ⇒ 9)15 ⇒ 7と同様．

(17 ⇒ 7) κ^* < κ+κ^* と仮定する．仮定17より κ+κ^* =κ^* +μ となる μ が唯一つ存在する． μ=κ も μ=κ+κ^* もこの式を満たすから，一意性より κ=κ+κ^* ．従って κ^*≦κ となり矛盾．

(18 ⇒ 17)明らか．

(19 ⇒ 7) κ^* < κ+κ^* と仮定する．仮定19より κ+κ^*=κ^*・μ となる μ が存在する．従って命題6より κ^*≦κ または μ≦κ^* である． κ^*κ だったから μ≦κ^* である．よって命題5より κ+κ^*=κ^*・μ=κ^* となり矛盾する．故に κ^*=κ+κ^* である．

20 ⇒ 19と21 ⇒ 20は明らか．

(22 ⇒ 3) κ^*+κ=κ^*+(κ+κ^*) だから仮定22より κ=κ+κ^* または κ, κ+κ^* < κ^* である． κ^*κ だから κ, κ+κ^* < κ^* となる．従って κ≦κ^* である．

(23 ⇒ 7) κ^*+κ^*=κ^*≦κ^*+κ である． κ^*+κ^* < κ^*+κ だとすると仮定23から κ^* < κ となり矛盾するので κ^*=κ^*+κ である．

(24 ⇒ 18) κ < λ とする．命題1より λ=κ+μ となる μ が存在する．仮定24より λ=μ となる，即ち μ は一意に決まる．よって λ-κ=λ である．

(25 ⇒ 9) κ≦κ・κ^*, κ^*≦κ・κ^* なので，仮定25より κ=κ・κ^* または κ^*=κ・κ^* である． κ^*κ だったから κ^*=κ・κ^* となる．

(26 ⇒ 2) μ:=2^κ₀ と置く． μ^κ=(2^κ₀)^κ=2^κ₀+1=2^κ₀=μ≦μ^μ* である． μ^κ=μ^μ* だとすると μ^*≦μ^μ*=μ^κ=μ となり矛盾するから， μ^κ < μ^μ* である．故に仮定26より κ < μ^* である．

(27 ⇒ 7)命題10の3より κ^**=(κ+κ^*)^* だから仮定27により κ^*=κ+κ^* となる．

(28 ⇒ 6) (κ²)^*=κ^*≦κ+κ^*≦κ²+κ^* だから，仮定28により κ^*=κ+κ^* または κ+κ^*=κ²+κ^* である．もし κ^*=κ+κ^* ならば κ≦κ^* だから命題4により κ²=κ である．

そこで κ+κ^*=κ²+κ^* とすると κ≦κ²≦κ+κ^* となる．よって再び仮定28により κ=κ² または κ²=κ+κ^* である． κ²=κ+κ^* と仮定すると κ^*≦κ² だから命題8より κ^*≦κ となり矛盾する．故に κ=κ² である．

(29 ⇒ 30)明らか．

(30 ⇒ 3) κ^* はアレフだから， κ^* < κ^** より κ < κ^* である．

(31 ⇒ 32)明らか．

(32 ⇒ 7) κ^* < κ+κ^* と仮定する．命題10の3より κ^**=(κ+κ^*)^* だから，仮定32より κ^** < (κ+κ^*)^*=κ^** となり矛盾する．従って κ^*=κ+κ^* である．

(33 ⇒ 3) κ^**≦κ^*+κ と仮定する． κ^** はアレフだから命題4より (κ^**)²=κ^** となる．故に (κ^**)²≦κ^*+κ だから命題6より「 κ^**≦κ^* または κ^**≦κ 」となり矛盾する．従って κ^**κ^*+κ であるから，仮定33より κ^*=κ^*+κ となる．従って κ≦κ^* である．

(34 ⇒ 35)明らか

(35 ⇒ 3) κ+κ^*≦κ+κ^* だから仮定35より「 κ+κ^*≦κ または κ+κ^*≦κ^* 」となる． κ+κ^*≦κ と仮定すると κ^*≦κ となり矛盾するから κ+κ^*≦κ^* ，従って κ≦κ^* である．

(36 ⇒ 37)明らか

(37 ⇒ 3) κ・κ^*≦κκ^* だから仮定35より「 κ・κ^*≦κ または κ・κ^*≦κ^* 」となる． κ・κ^*≦κ と仮定すると κ^*≦κ となり矛盾するから κ・κ^*≦κ^* ，従って κ≦κ^* である．

※条件6「 κ²=κ 」は選択公理と同値であるが， 2・κ=κ は選択公理と同値ではない．

※条件12「 κ² =λ² ならば κ=λ 」は選択公理と同値であるが，「 2・κ=2・λ ならば κ=λ 」は ZF で成り立つ．

※条件19「 κ < λ ならばある μ が存在して λ=κ・μ 」は選択公理と同値であるが，「 κ < λ ならばある μ が存在して λ=κ+μ 」は ZF で成り立つ．(命題1)

定理12 選択公理
⇔ 無限濃度 κ, λ に対して以下が成り立つ．

「κ≦λ < 2^κ かつある μ が存在して κ=μ²」ならばある ν が存在して λ=ν².

証明 ( ⇒ )明らか．

( ⇐ )定理11の条件2を示す． κ を無限濃度として λ:=κ^₀ とおく． λ²=κ^2・₀=κ^₀=λ である．命題10の1より λ^*≦2^2λ2=2^2λ となるから 2^λ≦2^λ+λ^*≦2^λ+2^2λ=2^2λ である．

もし 2^λ+λ^*=2^2λ であれば， ₀≦λ≦2^λ だから命題3より λ^*=2^2λ となり κ≦λ≦2^2λ=λ^* である．

そこで 2^λ+λ^* < 2^2λ とする．このとき 2^λ≦2^λ+λ^* < 2^2λ かつ 2^λ=(2^λ)² だから，仮定によりある ν が存在して 2^λ+λ^*=ν² と書ける．故に命題7により ν≦λ^* または ν≦2^λ である．もし ν≦λ^* であれば

κ≦λ≦2^λ≦2^λ+λ^*=ν²≦(λ^*)²=λ^*

である．

そこで ν≦2^λ とする．このとき λ≦λ+λ^*≦2^λ+λ^*=ν²≦(2^λ)²=2^λ である．

もし λ+λ^*=2^λ (=(2^λ)²) ならば命題7により 2^λ≦λ または 2^λ≦λ^* だから κ≦λ≦2^λ≦λ^* となる．

そこで λ+λ^* < 2^λ とする．このとき λ≦λ+λ^* < 2^λ かつ λ=λ² だから仮定によりある μ が存在して λ+λ^*=μ² と書ける．故に命題7により μ≦λ または μ≦λ^* である． μ≦λ と仮定すると λ^*≦λ+λ^*=μ²≦λ²=λ となり矛盾する．故に μ≦λ^* であり κ≦λ+λ^*=μ²≦λ^* となる．

定理13 選択公理
⇔ 無限濃度 κ, λ に対して「 κ≦λ < 2^κ ならばある μ が存在して λ=κ・μ 」．

証明 ( ⇒ )明らか．

( ⇐ )定理11の条件2を示す．前定理の証明と同様である． κ を無限濃度として λ:=κ^₀ とおく． 2^λ≦2^λ+λ^*≦2^2λ である．

もし 2^λ+λ^*=2^2λ であれば κ≦λ≦2^2λ=λ^* であるから， 2^λ+λ^* < 2^2λ とする．このとき 2^λ≦2^λ+λ^* < 2^2λ だから，仮定によりある μ が存在して 2^λ+λ^*=λ・μ と書ける．故に命題7により λ≦λ^* または μ≦2^λ である．もし λ≦λ^* であれば κ≦λ≦λ^* となる．

そこで μ≦2^λ とする．このとき λ≦λ+λ^*≦2^λ+λ^*=λ・μ≦(2^λ)²=2^λ である．

もし λ+λ^*=2^λ ならば κ≦λ≦2^λ≦λ^* であるから， λ+λ^* < 2^λ とする．このとき λ≦λ+λ^* < 2^λ だから仮定によりある ν が存在して λ+λ^*=λ・ν と書ける．故に命題7により ν≦λ または λ≦λ^* である． ν≦λ と仮定すると λ^*≦λ+λ^*=λ・ν≦λ²=λ となり矛盾する．故に λ≦λ^* であり κ≦λ≦λ^* となる．

定理14 選択公理 ⇔ 無限集合 X に対し |X|=|P_fin(X)| ．

証明 ( ⇒ )命題9より明らか．

( ⇐ )定理11の条件6を示す． X を集合とするとき X×X = { <a, b> | a, b∈X } で， <a, b> = { {a}, {a, b} } が順序対の定義だったから X×X⊂P_fin(P_fin(X)) ．故に

|X|≦|X×X|≦|P_fin(P_fin(X))|=|P_fin(X)|=|X|.

定義 κ を濃度とする． κ=|X| となる X を取り e(κ):=|P_fin(X)| と定める．

命題18 κ, λ を無限濃度， をアレフとする．

1. e()= ．
2. e(κ+λ)=e(κ)・e(λ) ．
3. κ・₀=κ ならば e(κ・)=e(κ)・e() ．

証明 (1)命題9より明らか．

(2) 互いに素な無限集合 X, Y に対して f: P_fin(X)×P_fin(Y)→P_fin(X∪Y) を f(A, B):=A∪B と定めれば f は全単射である．

(3)2より e(κ・)=e(κ+) を示せばよい．命題2より κ+≦κ・ だから e(κ+)≦e(κ・) である．

逆を示す．今仮定より κ・₀=κ だから e(κ・)≦e(κ・₀+) を示せばよい． κ=|X|, =|W|, (N×X)∩W= ∅ として f: P_fin(X×W)→P_fin((N×X)∪W) を以下のように定める． A∈P_fin(X×W) とする． w∈W に対して A_w:= { x∈X|(x, w)∈A } と置けば，ある w₁, …, w_n∈W が一意に存在して

A=∪_i=1ⁿ(A_wi× { w_i } ), w₁ < w₂ < … < w_n

と書ける．このとき f(A):= { w₁, …, w_n } ∪∪_i=1ⁿ( { i } ×A_wi) と定める．この f は単射である．よって e(κ・)≦e(κ・₀+) である．

定理19 κ, λ は無限濃度， はアレフを表すとする．次の命題は( ZF 上)同値．

1. 選択公理
2. e(κ)=κ ．
3. e(κ+λ)=e(κ)+e(λ) ．
4. e(κ+)=e(κ)+e() ．
5. e(κ)=e(λ), κ≦λ⇒κ=λ ．
6. e(κ+λ)=e(κ) または e(κ+λ)=e(λ) ．
7. e(κ+e(κ)^*)=e(κ)^* ．

証明 1 ⇔ 2は定理14である．

(1 ⇒ その他)1 ⇔ 2により明らか．

(3 ⇒ 4)明らか．

(4 ⇒ 1)定理11の2を示す． e(κ)^* はアレフだから仮定4により e(κ+e(κ)^*)=e(κ)+e(e(κ)^*)=e(κ)+e(κ)^* となる．一方命題18により e(κ+e(κ)^*)=e(κ)・e(e(κ)^*)=e(κ)・e(κ)^* となる．従って e(κ)・e(κ)^*≦e(κ)+e(κ)^* だから命題6より e(κ)^*≦e(κ) または e(κ)≦e(κ)^* となる．故にHartogs numberの性質より e(κ)≦e(κ)^* となり κ≦e(κ)≦e(κ)^* が分かる．

(5 ⇒ 1)定理11の2を示す． λ:=κ・₀ とおく．命題18を使って e(λ+λ^*)=e(λ)・e(λ^*)=e(λ・λ^*) が分かる．命題2より λ+λ^*≦λ・λ^* だから仮定5より λ+λ^*=λ・λ^* となる．従って命題6とHartogs numberの性質から κ≦λ≦λ^* となる．

(6 ⇒ 7)明らか．

(7 ⇒ 1)定理11の2を示す． κ≦κ+e(κ)^*≦e(κ+e(κ)^*)=e(κ)^* ．

定理 選択公理
⇔ X を集合，{ X_i }_i=0^∞ を集合族として |X| < |∪_i=0^∞X_i| を満たすとする．このときある n∈N が存在して |X|≦|∪_i=0ⁿX_i| ．

証明 ( ⇒ )任意の n∈N に対して |X||∪_i=0ⁿX_i| と仮定する．選択公理により濃度は比較可能であるから |∪_i=0ⁿX_i| < |X| となる．よって |X_i|≦|X| であり |∪_i=0^∞X_i|≦₀・|X|=|X| となって矛盾する．

( ⇐ )整列可能定理を示す．その為 X を任意の集合とする． Y₀:=X, Y_i+1:=P(Y_i), Y:=∪_i=0^∞Γ(Y_i) と定める． Y は整列可能である．各 i∈N について標準的な単射 Γ(Y_i)→P(P(P(Y_i)))=Y_i+3 が構成できるから |Y|≦|∪_i=0^∞( { i } ×Y_i)| である．

|Y| < |∪_i=0^∞( { i } ×Y_i)| と仮定する．ある n∈N が存在して |Y|≦|∪_i=0ⁿ( { i } ×Y_i)| となる．よってある Z_i⊂Y_i が存在して |Y|=|∪_i=0ⁿ( { i } ×Z_i)| とできる． Y が整列可能だから Z_i も整列可能であり |Y|=|∪_i=0ⁿ( { i } ×Z_i)|=∪_i=0ⁿ|Z_i|=max_0≦i≦n|Z_i| となる． |Z_j|=max_0≦i≦n|Z_i| となる j を取れば |Γ(Y_j)|≦|Y|=|Z_j|≦|Y_j| となり矛盾する．

故に |Y|=|∪_i=0^∞( { i } ×Y_i)|≧|Y₀|=|X| となり， X は整列可能である．

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

1. 選択公理
2. 任意の集合 X に対してある集合 Y が存在して Y = { x⊂Y | |X||x| } ．
3. 任意の集合 X に対してある集合 Y が存在して |Y| = |{ x⊂Y | |X||x| }| ．

証明 (1 ⇒ 2) X を任意の集合とする． α := Γ(Γ(P(X))) とおき， β < α に対して

f(β) := { x⊂∪_γ<βf(γ) | |x| < |X| }

と定め， Y := ∪_β<αf(β) とする．この Y が Y = { x⊂Y | |X||x| } を満たす．

(2 ⇒ 3)明らか．

(3 ⇒ 1)整列可能定理を示す． X を任意の集合とする．仮定3よりある Y が存在して |Y| = |{ A⊂Y | |X||A| }| となる． S:= { A⊂Y | |X||A| } と置き単射 f: S→Y と ∞ ∉ Y を取る．順序数 α に対して

g(α) := f(g''α)　(g''α∈Sのとき)
g(α) := ∞　(そうでないとき).

と定める． g(α)≠∞, g(β)≠∞ で g(α)≠g(β) ならば α≠β である．故に順序数 γ で g(γ)=∞ なるものが存在する．そのような γ のうち最小の γ を取っておけば W := g''γ⊂Y で， W = g''γ ∉ S である．よって |X|≦|W| となり， W は整列可能だから X も整列可能となる．