大まかに言えば、整列集合は自然数に似た性質を持つ集合である。自然数はある数の次の数が定義できる。例えば、1の次は2であるし、2の次は3である。

では、一般の集合で次の数とはどのように定められるのか。それの一種の解答が整列集合である。

整列集合

(A,≦)が整列集合であるとは、任意のAの空ではない部分集合Bに最小元が存在することを指す。

このことから、整列集合は全順序であることが言える。なぜならば、{a,b}に対して、最小元の定義より、a≦bもしくはb≦aが成り立つからである。

ここで、a∈Aの次の数について考えてみよう。

aの次の数をsuc(a)と書く。suc(a)には次のような性質が成り立っていて欲しい。

a<suc(a)(<は≦の反射簡約)で、a<b∧b<suc(a)を満たすようなbは存在しない。（存在していたら、bがaの次の元と呼ぶのに相応しいからである。）

また、suc(a)は単射であることが望ましい。

このような条件を課した時、suc(a)は次のように定義できるように思われる。

a<={b∈A|a<b}と定義する。このとき、(A,≦)は整列集合であるので、a<が空でない限り最小値min(a<)が存在する。これをsuc(a)と定義する。

b<が空になるときはどんなときだろうか。∀a∈A¬[a<b]=∀a∈A[b≦a]であるので（Aは全順序集合であるから。）aはAの最大値。Aの最大値は一意に存在するので、定義いきからmaxAを取り去れば、sucはどの元に対しても定義できていると思える。

aが最大値でなければ、suc(a)は常に存在することがわかった。

次に先ほど提示した、sucの性質を証明していこう。

・a<suc(a)(<は≦の反射簡約)で、a<b∧b<suc(a)を満たすようなbは存在しない。

・Aに最大値が存在しなければ、suc(a)は単射である

[証明]

a<suc(a)はsuc(a)がa<の元であるから示せている。また、a<b,b<suc(a)が同時に成り立つことはない。なぜなら、suc(a)がa<bとなるb達の最小元であるので、a<suc(a)≦bが成り立ち、suc(a)≦bが成り立つから。

次にsuc:A\maxA→Aが単射であることを示そう。

段階を踏んで示していく。

第一段階

suc(a)=suc(b)⇄a< = b<

[証明]

←はほとんど当たり前であるので省略する。

→を示す。suc(a)=suc(b)より、a<の最小元とb<の最小元は等しい。a<⊂b<を示せば、対称性より示せる。α∈a<であるとしよう。つまり、a<αが成り立っている。ここで、a<suc(a)≦αが成り立つ。すなわち、suc(b)=suc(a)≦αが成り立つことを示せて、さらに、b<suc(b)≦αより、b<αが示せた。

第二段階

a< = b<⇄a=b

[証明]

→を示す。a<bであれば、a< = b<より、b∈a<が成り立つが、b∈b<は成り立たないため、a<≠b<が成り立ち、b<aも同様であるので、a=bでなければならない。

←はほとんど自明であるので除く。

これらの事実から、suc:A\maxA→Aは単射であることを示せた。

また、suc(a)とsuc(b)の大小について次の定理が成り立つ。

a≦b⇄suc(a)≦suc(b)

[証明]

→を示す。a≦bとする。a=bの時、確かに、suc(a)=suc(b)より、suc(a)≦suc(b)が成り立つ。a<bの時を示す。ここで、suc(a)について考えてみると、suc(a)はaより大きいものの最小値であるので、a<suc(a)≦b<suc(b)が成り立つことがわかる。よって、suc(a)<suc(b)。

←を示す。suc(a)≦suc(b)であるとする。ここで、suc(a)=suc(b)であれば、sucの単射性から、a=bが言える。あとは、suc(a)<suc(b)の時を示せば良い。もし、a=bであれば、suc(a)=suc(b)となってしまい、矛盾する。a>bが成り立てば、先ほどの証明により、suc(a)>suc(b)が成り立ち、矛盾する。すなわち、a<bしかありえない。

よって、同値性が示せた。

suc(a)に対する理解がだいぶ深まってきた。まとめると、sucは次の性質をもつ。

sucの性質

定義域はmaxが存在する場合はA\maxAで、存在しない場合はAであり、値域はAである。

sucは先ほどの定義域と値域で単射であり、どのようなa<b∈Aに対してもa<suc(a)≦bを満たしている。

a≦b⇄suc(a)≦suc(b)

このsucの性質から系として、整列集合の性質をいくつか導くことができる。

稠密

(X,≦)を順序集合として、Y⊂Xとする。YがXで稠密であるとは、∀x,y∈X,∃z∈Y,[x<y→x<z<y]が成り立つことをいう。

つまり、どの元の間にも、Yの元が入り込んでいるということだ。すぐに証明できることだが、次の定理が成り立つ。

YがXのなかで稠密であったとする。

この時、Yは無限集合である。

[証明]

(X,≦)は順序集合で、Yはその中で稠密であるとしよう。この時、Yが有限であると仮定する。Yは有限なので、各元にNを対応させられる。この時、y(1)<y(2)<......<y(n)となるように、対応をつける。しかし、例えば、y(1)とy(2)の間にはYの稠密性より、新たなYの元kが存在するので、全てのYの元に有限な番号を対応させたにも関わらず、番号がついていないYの元が存在してしまうので、Yが有限であることが誤りであり、Yは無限であることが示された。

想像できることだが、整列集合は絶対に稠密な部分集合を持たない。稠密集合は元が順序に対して、ぎっしりと詰まっているようなイメージだが、整列集合はそれとは真逆に、一つの元とそのほかの元に整数のように隙間があるイメージだからである。

整列集合Xの部分集合Yは、稠密にはならない

[証明]

仮に、あるYが稠密であるとしよう。Yは空でないので、y=min(Y)が存在する。ここで、Yは稠密なので、無限集合であり、y以外にも元は存在する。すなわち、yはmax(X)が存在しても、max(X)とはならない。ここで、suc(y)が存在し、y<suc(y)が成り立ち、かつどのようなk∈Yもy<k<suc(y)を満たさないので、Yは稠密ではない。

この時、Yが稠密であるということに矛盾し、Yは任意であったから、どのような部分集合Yをとっても、Xで稠密にならない。