証明

(⇒)Xが有限集合の時は自明( Z/nZ を考えればよい)だから，Xは無限集合とする．F(X) := { x⊂X | xは有限集合 } と書くことにする． 選択公理より，|X| = |F(X)|，即ち全単射X→F(X)が存在する．

実は「任意の無限集合Xに対し |X| = |F(X)| 」は選択公理と同値である． 証明は基数の性質の定理9を参照．

よって F(X) に群構造を入れられることを示せばよい．

自然な同一視 Power(X) = 2^X で考えると F(X) = { f∈2^X | 有限個のx∈Xを除いてf(x)=0 }である．2 = {0, 1} = Z /2Z は体だから，それの直積である2^Xは自然に環となる．このとき明らかにF(X)⊂2^Xは(加法についての)部分群である．故にF(X)に群構造を入れることができた．

(←)整列可能定理を示す．X≠∅を任意の集合とする．単射λ→Xが存在しないような順序数λが存在する(基数の性質の命題の証明を参照)ので，そのようなλを1つ取っておく．簡単のため，Xは順序数を含まないとする．

仮定によりX∪λを群にすることができる．(その積を・とする．)このとき
∀x∈X∃α∈λ(x・α∈λ)
が成立する．

∃x∈X∀α∈λ￢(x・α∈λ) と仮定する．写像f:λ→Xがf(α):=x・αで定義されるが，これは積・の性質により単射となりλの取り方に矛盾する．

さて，直積λ×λに辞書式順序を入れる．するとこれは整列順序になる．そこで g: X→λ×λを
g(x) := min{ <α, β>∈λ×λ | x・α=β }
と定義すると，gは単射であり，よってXは整列可能である．