定理　選択公理⇒整列定理

証明
空でない集合Xの任意の空でない部分集合Yをその元∃y∈Yに対応させる写像f(Y)=yの存在が選択公理により保証される。
X上の二項関係≦を ∀Y⊂X.((Y≠{})⇒∀y∈Y.(f(Y)≦y)) で定義する。
反射律の確認：∀a∈Xについて、≦の定義を{a}に適用しa≦aを得る。
推移律の確認：∀a,b,c∈Xについて、a≦b ∧ b≦c を仮定する。≦の定義を{a,b,c}に適用しa≦cを得る。
反対称律の確認：∀a,b∈Xについて、a≦b ∧ b≦a を仮定する。≦の定義を{a,b}に適用しf({a,b})=a ∧ f({a,b})=bを得る。fは写像だからa=b。
全順序律の確認：∀a,b∈Xについて、fの定義よりf({a,b})=a ∨ f({a,b})=b。≦の定義を{a,b}に適用しa≦b ∨ b≦aを得る。
以上で≦がX上の全順序であることが確認された。
さらに、≦の定義より、Xの任意の空でない部分集合Yに最小元f(Y)が存在するから、≦はX上の整列順序である。