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

1. 選択公理
2. 任意の集合は整列可能 (整列可能定理)．
3. 任意の集合Xに対して，ある順序数αと全単射 X→αが存在する．
4. 任意の集合Xに対して，ある順序数αと全射α→X が存在する．
5. 任意の集合Xに対して，ある順序数αと単射 X→αが存在する．

証明 (1 ⇔ 2) 整列可能定理とZornの補題で示した．

(2 ⇒ 3) 整列可能定理によりXの整列順序≦が存在する．順序数の性質により，ある順序数αと順序同型 f: (X, ≦)→αが存在する．f: X→αは勿論全単射である．

(3 ⇒ 4) 明らか．

(4 ⇒ 5) 全射 f: α→X に対して g: X→α を g(x) := min f^-1(x) で定めればgは明らかに単射である．

(5 ⇒ 2) 単射 X→α により X⊂α とみなすことによりXは整列集合である．

定理2 整列可能定理 ⇔ 選択関数を持つ集合は整列可能

証明 ⇒は明らか． ←を示す．任意の集合Xに対し，Y := { {x} | x∈X } と置けば，Yは明らかに選択関数を持つ．故にYは整列可能．よって明らかにXも整列可能．

定理3 選択公理
⇔「Xが有限集合⇔(X, ≦)が整列順序ならば(X, ≧)も整列順序」

証明 (⇒) 「Xが有限集合⇒(X, ≦)が整列順序ならば(X, ≧)も整列順序」は明らか．逆を示すため，Xが「(X, ≦)が整列順序ならば(X, ≧)も整列順序」を満たすとする．整列可能定理より整列順序(X, ≦)が存在する．(X, ≦)≅αとなる順序数(α, ≦)が存在する．(X, ≧)の整列性より(α, ≧)も整列順序．故にα∩ω⊂αは(≧に関する)最小元，即ち(≦に関する)最大元を持つ．ω≦αのときα∩ω=ωは最大元を持たないから，α<ω でなければならない．即ちXは有限集合．

(←) 整列できない無限集合Xが存在すると仮定する．このXは明らかに「(X, ≦)が整列順序ならば(X, ≧)も整列順序」を満たす．よって仮定に矛盾． 故に任意の集合は整列可能である．

定理4 次の命題は同値

1. 任意の集合は整列可能．
2. 任意の全順序集合は整列可能．
3. 集合 X が整列可能ならば冪集合 P(X) も整列可能．
4. 順序数αに対して P(α) も整列可能．

証明 (1⇒2) 自明

(2⇒3) (X, ≦)を整列順序集合とする． P(X) に二項関係 < を

A<B ⇔ ある a∈A＼B が存在して任意の b∈B＼A に対して a<b

で定める．これによって P(α) が全順序集合になることを確かめる．

(i) ￢A<A について．
A＼A= ∅ なので明らか

(ii) A<B ⇒ ￢B<A について．
A<Bとすると < の定義より，あるa₀∈A＼Bが存在して「任意の b∈B＼A に対して a₀<b 」となる．よって明らかに ￢B<A である．

(iii) A<B または A=B または B<A について．
A≠B とすると，X は整列順序集合だから a := min( (A＼B)∪(B＼A) ) が存在する．勿論 a∈A または a∈B であるが，明らかに a∈A ならば A < Bで，a∈B ならば B < A である．

(iv) (A<B かつ B<C) ⇒ A<C について．
￢A<C と仮定する．A=C だとすると A<BかつB<A となり(ii)に反するので A≠B である．故に(iii)から C<A である．A<B, B<C, C<A より

(1)　任意の b∈B＼A に対して a₀ < b
(2)　任意の c∈C＼B に対して b₀ < c
(3)　任意の a∈A＼C に対して c₀ < a

を満たすa₀∈A＼B, b₀∈B＼C, c₀∈C＼Aが存在する．a₀∈A＼Cである．

a₀ ∉ A＼C と仮定する．即ちa₀∈A^c∪Cである．a₀∈A＼Bだったから a₀ ∈ (A^c∪C)∪(A＼B) = A∪C＼B ⊂ C＼B である．よって(2)により b₀ < a₀．従って(1)から b₀ ∉ B＼A でなければならない．すると同様の議論を繰り返して a₀ < c₀ < b₀ < a₀ が導かれ，矛盾．

同様にしてb₀∈B＼A, c₀∈C＼Bである．従って(1)(2)(3)から a₀ < b₀ < c₀ < a₀ となり，矛盾する．

以上より(P(X), <)は全順序集合である．よって，仮定より整列可能である．

(3⇒4) 明らか．

(4⇒1) Xを任意の集合とすると(基礎の公理により)順序数αが存在してX⊂R(α)となる．

故にR(α)が整列可能であることを示せばよい．￢|λ|≦|R(α)|となるような順序数λが存在するので，そのようなλを一つとっておく．仮定4によりP(λ)は整列可能である．そこで(P(λ), ≦)が整列順序となるような≦を一つ取っておく．

超限帰納法により，α上の関数Fで 「任意のβ<αに対して F_β := F(β) は z(β) := { a∈R(α) |ρ(a)=β } を整列する」 を満たすものを構成する．

(i) β=0のとき．
R(0) = ∅ だから F₀ := ∅ とすればよい．

(ii) 0<β<αのとき．
帰納法の仮定により，任意のγ<βに対して(z(γ), F_γ)は整列順序である．そこで R(β) = ∪_γ<β z(γ) の二項関係 ≦_β を次のように定義する．

u≦_βv ⇔ ρ(u)<ρ(v)または「ρ(u)=ρ(v), uF_ρ(u)v」

すると (R(β), ≦_β) は整列順序である．

今 ￢|λ|≦|R(α)| であったから，勿論 ￢|λ|≦|R(β)| であり，よって |R(β)| < |λ| となる． 故にあるμ<λが一意に存在して (R(β), ≦_β) ≅ (δ, ≦) である(この同型も一意に定まることに注意する)．ここから全単射 f: P(R(β))→P(δ) が自然に定まる．δ⊂λであるから P(δ)⊂P(λ) である．よって(P(δ), ≦)は整列順序である．ここから f により R(β+1) = P(R(β)) の整列順序が定まる．それにより定まる z(β)⊂R(β+1) の整列順序を F_β と置く．

(i)(ii)により F が定まった．このとき，先と同様にして R(α) の整列順序 ≦_α を

u ≦_α v ⇔ ρ(u)<ρ(v)または「ρ(u)=ρ(v), uF_ρ(u)v」}

で定めればよい．

定理5 λは基数を表すとし，WO(X, λ)で命題

ある順序数αとα上の関数fが存在して∀β<α( |f(β)| <λ ) かつ X=∪_β<α f(β)

を表すことにする．mは2以上の整数を表すとするとき，次の命題は(ZF上)同値．

1. 整列可能定理
2(m). 任意の集合 X に対し WO(X, m)
3. ある m≧2 が存在して任意の集合 X に対し WO(X, m)
4. 任意の集合 X に対しある m≧2 が存在して WO(X, m)
5. 任意の集合 X に対し WO(X, )

証明 1⇔2(2) と 2(m)⇒3 と 3⇒4 と 4⇒5 は明らか．m≦n に対し 2(m)⇒2(n) も明らか．なので 5⇒1 を示せばよい．その為には選択公理と同値なAMCを示せばよい．

Xを集合とし， ￢ ∅ ∈X とする． 仮定5により WO(∪X, ) の条件を満たす順序数αと写像 g が存在する．x∈X に対し β(x) := min{ γ< α | x∩g(γ) ≠ ∅ } と定めて f(x) := x∩g(β(x)) と置けば，この f がAMCを満たす．

基礎の公理を仮定しないと AMC⇒選択公理 は証明できない．つまりこの 5⇒1 の証明は基礎の公理を使っていることになる．実は 5⇒1 は基礎の公理を仮定しないと証明できないことが知られている．( 5⇔AMC は基礎の公理を使わずに証明できる．)一方，4⇒1 は基礎の公理を使わなくても証明できるので，その証明を書いておく．

証明 まず Y×Y⊂Y を満たす集合 Y が整列可能であることを示す．m>1 で WO(Y, m) が成立しているとする． (この時 WO(Y, m-1) であることをこれから示す．) WO(Y, m) の条件を満たす順序数αと関数 f を取り

u(β, γ, δ) := (f(β)×f(γ))∩f(δ)　(β, γ, δ<α)

を考える．定義より u(β, γ, δ) は二項関係とみなせる． (即ち定義域 dom，値域 ran を考えることができる．) fの性質から

| dom(u(β, γ, δ)) |≦| f(β) |≦m
| ran(u(β, γ, δ)) |≦| f(γ) |≦m
| u(β, γ, δ) |≦| f(δ) |≦m

である．

(i)全てのβ<αに対し「f(β)≠∅⇒∃γ, δ<α(0< |dom(u(β, γ, δ))| <m)」の時．
f(β)≠ ∅ なるβ<αに対し，0<| dom(u(β, γ, δ)) |<mとなる組<γ, δ>のうち辞書式順序で最小のものを<λ_β, μ_β>で表す．

f(β)≠ ∅ の時　v_β := dom(u(β, λ_β, μ_β))
f(β)= ∅ の時　v_β := ∅
w_β := f(β)＼v_β

と置き，α+α上の関数gを

β<αの時　g(β) := v_β
α≦β, β＼α≅γ<αの時　g(β) := w_γ

で定義する．すると∪_β<α+α g(β) = y である．次に，定義から明らかに | v_β|<m, | w_β|<m だから | g(β) |≦m-1　(β<α+α)である．即ち，α+αとgが WO(Y, m-1) の条件を満たす．

(ii)あるβ≦αについて「f(β)≠∅かつ∀γ, δ<α(| dom(u(β, γ, δ)) |=0 or m)」の時．
このようなβのうち最小のものを取り，s∈f(β)とする．γ, δ<αがdom(u(β, γ, δ))≠∅を満たすとする．この時 | dom(u(β, γ, δ)) |=m である．| u(β, γ, δ) |≦m だったから，| u(β, γ, δ) |=m で，u(β, γ, δ)は関数でなければならない．さて，f(γ)≠ ∅ であるとすると Y×Y⊂Y より u(β, γ, δ)≠ ∅ となるδが存在するので，そのようなδのうち最小のものをδ_γと書く．

f(γ)≠ ∅ の時　v_γ := { u(β, γ, δ_γ)(s) }
f(γ)= ∅ の時　v_γ:= ∅
w_γ := f(γ)＼v_γ

と置き，α+α上の関数gを

γ<αの時　g(γ) := v_γ
α≦γ, γ＼α≅λ<αの時　g(γ) := w_λ

で定義する．すると(i)の場合と同様，α+αとgが WO(Y, m-1) の条件を満たす．

(i)(ii)より WO(Y, m-1) が成立する．仮定4. より WO(Y, m) が成立するmは存在するから，WO(Y, 1)が成立することが分かる．即ち，Y は整列可能である．

さて，X を任意の集合とする．この時

Z₀ := X, Z_n+1 := Z_n ∪(Z_n×Z_n), Y := ∪_n=0∞ Z_n

と置く．すると m<n の時 Z_m ⊂ Z_n, Z_m×Z_m ⊂ Z_n だから

よって先に述べた通り Y は整列可能であり，明らかに X⊂Y だから X も整列可能である．