証明

α := { β:順序数 | |β|≦|X| } と置く．αは集合である．

W:= { R⊂X×X | RはXのある部分集合を整列する } と定義する．Wは集合である．よって「Wに現れる整列順序と同型な順序数全体」も集合である．この集合はαと一致する．

順序数の推移的な集合は順序数だから，αも順序数である．α∉αだから￢|α|≦|X|．よって，αの定義から := |α| はHartogs numberである．

証明

(1 ⇒ 2) XとYを任意の集合とする．選択公理と同値な整列可能定理により，この2つを整列する．すると整列順序の性質から |X|≦|Y| または |Y|≦|X| が分かる．

(2 ⇒ 3) は明らか．

(3 ⇒ 1) まず |Y|≦*|X| ⇒ |Y|≦|P(X)| であることに注意する．

f: X→Yを全射だとすると b∈Y に f^{-1}(b)∈P(X) を対応させる写像は単射である．

整列可能定理を示す．Xを集合とする． をXのHartogs numberとすると￢≦|P(X)|．よって先の注意より￢≦*|X| である．従って仮定3. から |X|≦* となる． = |α| となる順序数αと全射 f: α→X を取る．すると g(a) := min f^{-1}(a) として単射 g: X→α が得られる．よってXは整列可能である．

証明

無限順序数αに対し |α×α|=|α| を示せばよい．

(i) α=ω のときは明らか．

(ii) α=β+1 のとき，明らかに|α|=|β|なので |α|=|β|=|β×β|=|α×α|．

(iii) αが極限順序数のとき．
あるβ<αに対し |β|=|α| となるときは(ii)と同様 |α|=|α×α| となる．なので全てのβ<αに対し |β|<|α| であるとする．

α×α=∪_{β<α}β×βである．α×αに順序Rを

と定める．このRは整列順序である．また，β<αに対しβ×β⊂α×αはinitial R-sectionとなる．

順序数ψ(β)を ψ(β) ≅ (β×β, R)で定める．β<αのとき
|ψ(β)| = |β×β| = ( |β| or 有限 ) < |α|
故にψ(β)<αである．よって
α×α=∪_{β<α}β×β≅∪_{β<α}ψ(β)≦α
従って|α×α|≦|α|である．

証明

κ=|X|, λ=|Y|, X∩Y = ∅ となる集合を取る．a≠bとなるa, b∈X，s≠tとなるs, t∈Yを取る．φ: X∪Y→X×Y を
x∈X のとき φ(x) := <x, s>
y∈Y, y≠s のとき φ(y) := <a, y>
φ(s) := <b, t>
と定めればφは単射である．

証明

κ=|X|, λ=|Y|, μ=|Z| となる集合X, Y, Zと =|W| となる整列順序集合Wを取る．Y∩Z = ∅ としてよい．仮定より単射 f: X×W→Y∪Z が存在する．U := f^{-1}(Y), V := f^{-1}(Z) とすれば |U|=|Y|=λ, |V|=|Z|=μ, X×W=U∪V (disjoint union) である．

(i) {x}×W⊂U となる x∈X が存在するとき．
= |W| = |{x}×W|≦|U| = λである．

(ii)どの x∈X についても ￢{x}×W⊂U となるとき．
w_x := min{ w∈W | <x, w> ∈V } と書けば
κ= |X| = | { <x, w_x> | x∈X } |≦|V| =μ.

証明

κ=|X|, λ=|Y| となる集合X, Yと=|W| となる整列順序集合Wを取る．単射 f: W→X×Y が存在する．π_X, π_Yをそれぞれ X×Y から X, Y への射影として U := π_X(f(W))⊂X, V := π_Y(f(W))⊂Y と置く．Wの整列順序を使って，U, Vは整列可能である．またf(W)⊂U×Vである．このとき補題3 を使って
= |W|≦|U×V| = |U|×|V| = max{ |U|, |V| }．
故に ≦|U| または ≦|V| であるが，それぞれ ≦κ, ≦λを導く．

証明

' ≦ だとすると

≦+'
≦・'　(補題4 による)
≦・
= 　(補題3 による)
= max{ , ' }

証明

(1 ⇒ 2) 整列可能定理により，全ての無限基数は なので補題3 より明らか．

(2 ⇒ 3) κ+λ= (κ+λ)^2 = κ^2+2・κ・λ+λ^2≧κ・λ≧κ+λ

(3 ⇒ 1) 整列可能定理を示す．Xを集合としてκ:=|X| と置く． をXのHartogs numberとする．仮定(3)よりκ+ =κ・ となる．Hartogs numberの定義より ￢≦κだから，補題5よりκ≦ となる．故にXは整列可能である．

(1 ⇒ 4) 整列可能定理により，全ての無限基数は なので補題7 より明らか．

(4 ⇒ 1) κ+λ=κのとき明らかにλ≦κ．同様にκ+λ=λからκ≦λが従う．故に，選択公理と同値な定理1 の(2)が成立することが分かる．

(1 ⇔ 5) は (1 ⇔ 4) と同様．

証明

(⇒) f: →F(X) を f(<a_1, …, a_n>) := {a_1, …, a_n} で定める．これは明らかに全射なので |F(X)|≦*||．よって選択公理より |F(X)|≦||．故に選択公理に気をつけると

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

証明

(⇒) 定理8 の(4)より明らか．

(←) 選択公理が成立しないと仮定すると，定理1 により￢|X|≦|Y| かつ ￢|Y|≦|X| となるような集合X, Yが存在する．明らかに |X|≦|X∪Y| かつ |Y|≦|X∪Y| である．X∪Y は無限集合だから |X| = |X∪Y| または |Y| = |X∪Y| でなければならない．しかし |X| = |X∪Y| なら |Y|≦|X∪Y| = |X|，|Y| = |X∪Y| なら |X|≦|X∪Y| = |Y| となり矛盾する．

証明

(⇒) 「Xが有限集合⇒(X, ≦)が整列順序ならば(X, ≧)も整列順序」は明らか．逆を示すため，Xが「(X, ≦)が整列順序ならば(X, ≧)も整列順序」を満たすとする．整列可能定理より整列順序(X, ≦)が存在する．(X, ≦)≅αとなる順序数(α, ≦)が存在する．(X, ≧)の整列性より(α, ≧)も整列順序．よって明らかにα<ω，即ちXは有限集合．

(←) 対偶を示す．選択公理が成立しないとすると，整列できない無限集合Xが存在する．このXは明らかに「(X, ≦)が整列順序ならば(X, ≧)も整列順序」を満たす．

証明

(1 ⇒ その他) 整列可能定理により，全ての無限基数は である．よって補題7 より 2～16 が従う．17は定理1より分かる．

後は逆を示せばよいので，各条件の下で選択公理と同値な整列可能定理を示す．その為には，Xを任意の無限集合，κ:= |X| としてκ≦ となる の存在を示せばよい．特に明記しない限り， はXのHartogs numberとする．( ￢≦κに注意しておく．)

(2 ⇒ 1) 仮定2. より，κ+=λ^2 となるλが存在する．≦κ+=λ^2 である．よって補題6 より≦λとなる．従って補題2 によりλ=+μとなるμが取れる．このとき
κ+ = λ^2 = (+μ)^2 = ^2+2・・μ+μ^2 ≧ ・μ.
よって補題5 から ≦κまたはμ≦ が分かる．￢≦κなのでμ≦，従ってλ= +μ≦ + = ．故にλ= である．よってκ≦κ+ =λ^2 = ^2 = ．

(3 ⇒ 1) λ :=κ^{}と置くとκ≦λかつλ^2=κ^(2・)=κ^()=λ．故にλ =|Y|として をYのHartogs numberとすれば(λ +)^2=λ^2+2・λ・ +^2≧λ・．また
(λ +)^2
=λ^2+2・λ・ +^2
=λ+2・λ・ +
≦λ・ +2・λ・　(補題4 より)
=λ・ 3・
=λ・
だから，(λ +)^2=λ・ となる．よって(λ +)^2=λ・ =λ^2・^2=(λ・)^2が成立．従って仮定3 よりλ + =λ・が分かる．補題5 から≦λまたはλ≦となる，\not≦λだからκ≦λ≦．

(4 ⇒ 1) λ :=・κと置くとκ≦λかつ2・λ=2・・κ=・κ=λである．λ=|Y|としてをYのHartogs numberとする．λ<λ +かつ <λ +と仮定すると仮定4 よりλ + <(λ + )+(λ + )=2・λ +2・ =λ +となって矛盾する．故にλ=λ+ または =λ+ である．￢≦λなので =λ +でなければならない．即ちκ≦λ≦．

(5 ⇒ 1)は(4 ⇒ 1)と同様．

(6 ⇒ 1) ￢κ≦と仮定する． <κ+ である．故に + = <κ +だから仮定6 より<κ，よって矛盾．

(7 ⇒ 1)は(6 ⇒ 1)と同様．

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

(9 ⇒ 1)を示すには(9 ⇒ 8)を示せばよいが，それは明らか．

(10 ⇒ 1) ≦κ +だから，仮定10 よりκ + =・μとなるμが存在する．従ってμ・α≦κ + なので補題5 より ≦κまたはμ≦． はXのHartogs numberだったから￢≦ |X|=κ，即ちμ≦ である．よって補題7 よりκ + =・μ =となる．故にκ≦．

(11 ⇒ 1)を示すには(11 ⇒ 10)を示せばよいが，それは明らか．

(12 ⇒ 1)を示すには(12 ⇒ 11)を示せばよいが，それは明らか．

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

(14 ⇒ 1) +=≦+κである．+<+κだとすると仮定14 から<κとなり矛盾するので =+κ．故にκ≦である．

(15 ⇒ 1)を示すには (15 ⇒ 9) を示せば良い．κ<λとする．補題2 よりλ=κ+μとなるμが存在する．仮定15 よりλ =μとなる，即ちμは一意に決まる．よってλ-κ=λである．

(16 ⇒ 1) κ≦κ・, ≦κ・なので，仮定16 よりκ=κ・ または =κ・ である．￢≦κだったから =κ・，従ってκ≦ となる．

(17 ⇒ 1) μ:= 2^(κ^) と置く．μ=|Y|としてをYのHartogs numberとする．μ^κ= (2^(κ^))^κ= 2^(κ^(+1))=2^(κ^) =μ≦μ^．μ^κ=μ^だとすると≦μ^=μ^κ=μとなり矛盾するから，μ^κ<μ^である．故に仮定17 よりκ<．