順序数と順序集合

集合とは

集合$M$の二つの元$x$，$y$の間に関係$x \leq y$が与えられ

1. $x \leq x$
2. $x \leq y$かつ$y \leq x$なら$x = y$
3. $x \leq y$かつ$y \leq z$なら$x \leq z$

が成り立つとき，この関係を順序（order）という。 順序の与えられた集合を順序集合（ordered set）といい，任意の要素間に順序関係が成り立つ集合を，全順序集合（totally ordered set）あるいは線形順序集合（linearly ordered set）という。

順序集合$M$および$N$が与えられ$M$から$N$の1対1対応$\varphi$が存在し，この写像によって順序が保たれるとき，すなわち

のとき，$M$と$N$は順序同型である，あるいは同じ順序型（order type）を持つという。

順序集合$M$の任意の元$x$に対して，$x\leq a$を満たす$M$の元$a$を最大元（greatest element）という。 反対に任意の元$x$に対して，$a\leq x$を満たす$M$の元$a$を最小元（smallest element）という。 そして，全順列集合$M$の中で，任意の空でない部分集合が最小元を持つとき，$M$を整列集合（well-ordered set）という。

順序数

集合$M$のべき集合を考えたとき，その部分集合$A,B \in \mathfrak{B}(M)$について，$A\subset B$のとき，$A\leq B$と定義する。

空集合$\emptyset$を$0$とみなし，$0$だけを元とする集合$\{ 0 \}$を$1$とみなす。 次に，$\{ 0,1 \}=\{ 0,\{ 0 \} \}$を$2$とみなし，$\{ 0,1,2 \}=\{ 0,\{ 0 \}, \{ 0,\{ 0 \} \}\}$を$3$とみなし…と続けることで，任意の自然数$n$を$\{ 0,1,2,...,n-1 \}$によって作ることができる。 こうして作られる整列集合を順序数（ordinal number）と呼び，$n=\{0, 1,2,...,n-1\}$に同型な整列集合は，順序数$n$を持つという。 そして，$n$の次の数，後続数（successor）$S(n)$も

で定義することができる。

形式的な定義を与えると，$x$が順序数であるとは，整列順序をなしており，かつ推移的（transitive）であるという条件を満たしている集合のことをいう。 推移的であるとは

であることをいう。

この拡張として，すべての自然数からなる整列集合$\{0,1,2,...\}$を$\omega$と名付ける（ここでは自然数の定義に$0$を含めている）。 この手続きをさらにつづけ，$\omega+1=\{0,1,2,...,\omega \}$，$\omega+2=\{0,1,2,...,\omega,\omega+1 \}$…などを出来る限り作り続けることができる。

Burali-Fortiのパラドックス

最後に，ナイーブな集合の定義と，順序数の定義を組み合わせることで導かれる1つのパラドックスを紹介する。

全ての順序数の集合$\sf{On}$というものを考えてみる。 すると，$\sf{On}$もまた整列集合であり，かつ(\ref{cond:trans})の条件を満たすため，$\sf{On}$自身も順序数ということになる。 さらに，すべての順序数$a$について$a \in \sf{On}$であるため，$\sf{On}$は最も大きな順序数である。

他方，$\sf{On}$自身も順序数であるから，その後続数$S(\sf{On}) = \sf{On} \cup \{\sf{On}\} $もまた順序数ということになる。 しかし，これは$\sf{On}$が最も大きな順序数であるということと矛盾する。 こうして，全ての順序数の集合を構築できるという仮定は矛盾を生むことがわかる。 この矛盾をBurali-Fortiのパラドックスと呼ぶ。