さて、任意の無限集合Sが整列できることを、選択公理を使ってどう証明するか示そう

Sの空でない部分集合の全体P(S)-{}に対してその中の要素1つを選ぶ選択関数fの存在が、選択公理によって保障される

したがって

S0＝S
s0＝f(S0)
S1＝S0-{s0}
s1＝f(S1)
S2＝S1-{s1}
s2＝f(S2)
・・・
Sω＝S-{so|o＜ω}
sω＝f(Sω)
・・・

という形で要素を取り出しつづけることができ
Sが集合であるならば、ある順序数oが存在して、
So＝{}となることが示せる
（逆にそのような集合が存在しないのであれば、Sは集合でないことになる）

したがってSは整列できる

ここで重要なのは
「Sの空でない部分集合の全体P(S)-{}に対してその中の要素1つを選ぶ選択関数f」
というところ

したがって、もしSが無限であるがその濃度が不明であり
また選択関数fを具体的に構成できない場合、
可算選択公理だけでは、Sの整列順序の存在は示せない

なぜなら・・・P(S)-{}は必ず非可算濃度だからである