順序数の導入例 - めもめも

集合による「自然数」の定義

公理的集合論では、「集合」の概念を基礎として数学を構築することを目指しており、「自然数」の概念すらも集合を使って定義しようと試みます。もう少し柔らかく言うと、集合を使って、自然数の「代替品」となるものを用意できないかと考えます。

たとえば、何も無いことを表す空集合 $\phi$ を「0」の代替品として定義します。

　 $0 :=\phi$

次に、1 以上の数をどう定義するかですが、自然数には、大きさ順に一列に並べられる（固く言うなら、整列順序関係を持っている）という性質があるので、

・「n より小さい数（の代替品となる集合）を集めた集合」を「n」の代替品とする

というアイデアが考えられます。具体的に言うならば、1 の代替品は次になります。

　 $1 := \{0\} = \{\phi\}$

これは、「空集合を唯一の要素とする集合」であり、空集合そのものとは区別される点に注意してください。そして、2、3…の代替品は次になります。

　 $2 := \{0, 1\} = \{\phi,\{\phi\}\}$

　 $3 := \{0, 1, 2\} = \{\phi,\{\phi\},\{\phi,\{\phi\} \}\}$

　　 $\vdots$

最右辺を見ていると目がチラチラしてきますが、その1つ前の書き方を見ればアイデアは明確だと思います。ちなみに、この定義を用いれば、自然数の大小関係は、次のように定義することができます。

　 $n < m \ \Leftrightarrow\ n\in m$ --- (1-1)

これで任意の自然数 n に対して「n の代替品となる集合」が定義できましたが、これ以降は、これらの集合を「n を表す集合」と短く言い換えることにします。

そして、上記の定義は、帰納的に考えることもできます。すなわち、

・n を表す集合に対して、n 自身を要素として付け加えたものが、n+1 を表す集合になる

という性質があるので、次のように定義する事も可能です。

　 $0 := \phi$

　 $n+1 := n \cup \{n\}\ (n=0,1,\cdots)$ --- (1-2)

「n を表す集合」の性質（推移性）

前述の (1-2) をよく吟味すると、

・n は n+1 の要素であり、かつ、n+1 の部分集合でもある

というちょっと奇妙な性質が生まれることに気が付きます。

実際、 $n \cup \{n\}$ の左側を見ると、n は n+1 の部分集合であることがわかります。一方、右側を見ると、n は n+1 の要素としても含まれています。つまり、

　 $n\in n+1$

　 $n\subset n+1$

が同時に成り立つという、集合論ならではの奇妙な関係が成り立ちます。（型付けされたプログラミング言語では、とても表しようの無い世界ですね・・・）

特に部分集合の関係を帰納的に用いると、

　 $0 \subset 1 \subset 2 \subset\cdots$

となっており、自然数の大小関係が集合の包含関係に対応することがわかります。

　 $n < m \ \Rightarrow\ n\subset m$

元々のアイデアでは、自然数の大小関係は (1-1) で定義されていたので、次の公式が成り立ちます。

　 $n\in m\ \Rightarrow\ n\subset m$ --- (2-1)

ちょっとした言葉遊びですが、 $n\in m$ は「n は m の元である」と言えて、 $n\subset m$ は「n の元は m に属する」と言えるので、(2-1) の関係は、「m の元の元は、m に属する」と言うことができますので、(2-1) は、

　 $a \in b \in m\ \Rightarrow\ a \in m$ --- (2-2)

と書き直すことができます。（(2-1) と (2-2) が集合の性質として同値であることは、落ち着いて考えると、厳密に証明することができます。）

再び (1-1) を思い出すと、これは、

　 $a < b < m\ \Rightarrow\ a < m$

ということで、(1-1) で定義した大小関係は、自然数としての大小関係を正しく代替できていることになります。これは「順序数の推移性」と呼ばれるもので、順序数の根幹となる性質であることが追々わかってきます。

順序数の公理的定義

ここまで、自然数の代替物となる集合を作ってきましたが、公理的集合論ではこの代替物を「順序数」と呼びます。そして、本物の自然数の事はわすれて、集合で定義された代替物、すなわち、順序数そのものの性質を調べていくと、おどろくべきことに、順序数は、自然数だけではなくて、自然数をさらに超える「数（のようなもの）」を表現できることがわかります。

この点を正確に説明するために、一旦、自然数のことは忘れて、純粋に集合の言葉だけで順序数を定義しなおします。前述のように、推移性が順序数の根幹となる性質ですので、集合を要素とする集合 m が、

・推移性 (2-1)（もしくは (2-2)）を満たす
・任意の部分集合は、（(1-1) の意味の大小関係で）最小の要素を持つ

という条件を満たす時に、「m は順序数である」と言うことにします。2つ目の条件がちょっとわかりにくいですが、m の任意の 2 つの要素 a, b を取った時に部分集合 $\{a,b\}\subset m$ に最小要素があることから、必ず、 $a < b$ もしくは $b < a$ のどちらかが成り立ちます。つまり、この2つの条件があれば、m のすべての要素は (1-1) の大小関係で一列に並べることができて、さらに、m はそれらすべてよりも大きい数、ということになり、「m は、m より小さい数を集めた集合」という当初のアイデアが綺麗に反映されていることになります。

さらに、

・順序数 m の任意の要素 n は、（(1-1) の意味で）n より小さい要素を集めた m の部分集合に一致する

という関係を上の定義から示すことができます。

実際、n より小さい要素を集めた集合は、 $\{a\in m\mid a\in n\}$ と表せますが、推移性から $n\subset m$ となることを考えると、これは集合 n に一致します。

そして、「n より小さい要素を集めた m の部分集合」は、それ自体が順序数の定義を満たすことも容易にわかります。つまり、前述の定義から、順序数 m は、「m よりも小さい順序数を集めた集合」と言えるのです。

さらに、公理的定義の立場では、(1-2) は、「n の次に大きい順序数」を作り出す手続きと見なすことができます。n 自身が「n よりも小さい順序数の集合」ですので、これに、n 自身を要素として加えたものは、「n 以下の順序数の集合」であり、確かに、「n の次に大きい順序数」となっています。

自然数を超える「数」の存在

公理的に定義した順序数は、当初に考えた「自然数の代替物」としての性質を満たしており、実際、

　 $0 :=\phi$
　 $1 := \{0\} = \{\phi\}$
　 $2 := \{0, 1\} = \{\phi,\{\phi\}\}$
　 $3 := \{0, 1, 2\} = \{\phi,\{\phi\},\{\phi,\{\phi\} \}\}$
　　 $\vdots$

という集合はすべて順序数の定義を満たしており、この意味で、順序数は自然数を含む、ということが言えます。

ただし、重要なポイントは、「順序数に含まれる集合は自然数だけではない」という点にあります。順序数の定義から言える事は、「順序数の要素は、大小関係で一列に整列できる」という事だけであり、言い換えると、順序数は、「大小関係で一列に整列できる集合」一般を表現する「数（のようなもの）」になっているのです。

・・・どういうこと？

具体例を示しましょう。

たとえば、(1-2) によって帰納的に、すべての（順序数としての）自然数 $0, 1, 2,\cdots$ が定義されますが、これらをすべて集めた集合を考えます。

　 $\omega := \{0,1,2\cdots\}$

(1-2) の手続きを繰り返す限りでは、（有限回の操作に止まる限り）永遠に $\omega$ にたどり着くことはできませんが、無限集合として概念的に定義することは可能です。そして、この $\omega$ は順序数の定義を満たしており、任意の自然数 n よりも大きな順序数であることが容易に確認できます。つまり、順序数の世界では、

　 $0<1<2<\cdots<\omega$

という、任意の自然数よりも大きい（直感的に言えば「加算無限大」とも言える）「数」が存在するのです。

さらに、(1-2) の手続きを利用すれば、 $\omega$ の後続の順序数を帰納的に作ることもできて、

　 $0<1<2<\cdots<\omega<\omega+1<\omega+2<\cdots$

という無限列が得られます。

$\omega+1$ や $\omega+2$ が一体どんな「数」なのかと不思議に思うかも知れませんが、前述のように、順序数というのは「大小関係で一列に整列できる集合」を表現するものですので、これは、「集合の要素を一列に並べる方法」に対応すると考えると理解できます。

たとえば、可算無限個の石ころを一列にならべたものは、自然数全体を一列にならべたものと（並べ方として）同一視できますので、 $\omega$ は、このような「並べ方」を表現したものと言えます。

　 $○○○○○○○○\cdots \Leftarrow \omega$

そしてさらに、可算無限個ならべたあとに、さらに、新しい石ころを1つ加えます。これが $\omega+1$ です。

　 $○○○○○○○○\cdots○ \Leftarrow \omega+1$

「無限個の後ろってどこだ？」と思う方は、1列目に無限個並べておいて、次に、2列目に並べ始めると思えばよいでしょう。こんな感じ。

　 $\omega+1$
　 $○○○○○○○○\cdots$
　 $○$

　 $\omega+2$
　 $○○○○○○○○\cdots$
　 $○○$

そして、2列目も無限に並べ切ったものは、 $\omega+\omega$ に対応すると想像できます。さらには、縦横の両方向に無限個ならべた様子を考えたくなりますが、これは、直感的には、 $\omega\times\omega$ に対応するはずです。

このあたりは、あくまでも直感的な議論ですが、順序数に対する演算（足し算、掛け算、冪）を厳密に定義することができて、上記の議論を数学的に正当化することももちろん可能です。

なお、公理的に定義された順序数は「集合の要素を一列に並べる方法」に対応すると言いましたが、順序数そのものにも大小関係が定義されており、順序数全体も一列に並べることができる点も大切です。これにより、「順序数に関する数学的帰納法」を考えることができて、これは一般に「超限帰納法」と呼ばれる証明法になります。

整列順序について

順序数の定義をもう一度見直してみます。

・推移性 (2-1)（もしくは (2-2)）を満たす
・任意の部分集合は、最小の要素を持つ

2つ目の条件から、順序数 m の任意の異なる2要素は比較可能（つまり、 $a < b$ もしくは $a > b$ のどちらかが成り立つ）になり、m の要素を一列に並べることができると説明しました。それでは、なぜ、比較可能性を直接に要求しないのでしょうか？　実は、2つ目の条件は、一般に、「整列順序」と呼ばれる性質で、単に一列に並べられる「全順序」よりも強い性質になっています。つまり、整列順序は全順序になりますが、全順序は必ずしも整列順序にはなりません。

たとえば、整数全体を通常の大小関係で並べた場合、これは一列に並べることが可能な全順序になっていますが、部分集合 $\mathbb Z_- = \{a\mid a<0\}$ には最小要素がなく、これは整列順序にはなっていません。では、自然数のように、集合全体に最小要素があれば十分かというと、そうでもなくて、非負の実数全体は最小要素 0 を持ちますが、開区間を考えると、最小要素がなく、やはり整列順序にはなりません。感覚的言うと、「最小要素から出発して、離散的に一列に並べることができる」のが整列順序ということになります。

したがって、順序数全体というのは、可能な整列順序のすべてを代表した集まりになっており、順序数自体が整列順序になっていることから、

・整列順序の集まりは、（順序数としての大小関係によって）整列順序になる

という定理が成り立つことになります。

と言っておいて・・・順序数自体が整列順序になることは、自明でしょうか？　これは、次のように証明することができます。先に触れた「n は n+1 の要素であり、かつ、n+1 の部分集合である」という順序集合のちょっと病的（？）な性質がうまく効いて来る面白いところなので、丁寧に示してみます。

まず、順序数全体の集まりを ${\rm On}$ と表すとして、 $C$ を ${\rm On}$ の任意の要素を集めたものとします。この時、 $C$ に最小要素があることを示せばよいことになります。

$C$ の任意の1つの要素を $x$ とすると、 $x$ は順序数の1つですので、任意の部分集合に対して、最小要素が存在します。特に、部分集合 $x\cap C$ を考えて、この最小要素を $x_0$ とします。（ $x\cap C=\phi$ の場合は、 $x_0=x$ とします。）この時、 $x_0\in x$ であることから、推移性により、 $x_0\subset x$ となります。

そして、この $x_0$ が $C$ の最小要素であることが言えます。なぜなら、 $C$ の中に $x_0$ より小さい要素 $a$ 、すなわち、 $a\in x_0$ を満たすものがあったとすると、 $a\in x_0\subset x$ 、すなわち、 $a\in x$ であり、さらに、 $a$ は $C$ にも含まれるので、 $a\in x\cap C$ が言えて、 $x_0$ が $x\cap C$ の最小要素であることに矛盾します。（ $x\cap C=\phi$ の場合は、そもそもこの事実に矛盾します。）

なるほどー。

超限帰納法について

・ $C$ を ${\rm On}$ の任意の要素を集めたものとして、 $C$ に最小要素が存在する

という事実を示しましたが、実は、この事実から超限帰納法を「証明」することができます。通常の数学的帰納法は、公理のようなもので、数学的帰納法が成り立つこと自体を証明することは（普通は）ありませんが、超限帰納法はそうではないのです。（順序数には自然数も含まれているので、同じ証明法を適用すれば、通常の数学的帰納法も「証明」できることになりますが。）

論理式を使って超限帰納法を表すと、 $C$ を ${\rm On}$ の任意の要素を集めたもの、順序数 $a$ に対する任意の命題を $F(a)$ として、

　 $[\forall b \in C\, {\rm s.t.}\, b < a;\,F(b)]\ \rightarrow \ F(a)$ --- (3-1)

が成り立つならば、

　 $\forall a \in C;\, F(a)$ --- (3-2)

が成り立つ、と言うことができます。これを証明します。

今、(3-1) が成り立つものとして、(3-2) が成り立たないと仮定します。すると、 $F(a)$ を満たさない $a\in C$ が存在することになるので、そのような $a$ を集めた集合 $N$ を考えると、これは、順序数の集合（ ${\rm On}$ の任意の要素を集めたもの）なので、最小要素が存在します。これを $a_0$ とすると、 $b < a_0$ なる任意の $b\in C$ は $F(b)$ を満たします。（さもなくば、 $b \in N$ となり、 $a_0$ が $N$ の最小要素であることに矛盾します。）すると、(3-1) により、 $F(a_0)$ が成り立つことになり矛盾が生じます。したがって、(3-2) は必ず成り立つのです。

なるほどー。

超限帰納法は何が「超限」なのか？

通常の（自然数に対する）数学的帰納法では、(3-1) に相当する部分は、

　 $\forall k \in \mathbb N;[\, F(k)\ \rightarrow \ F(k+1)]$ --- (4-1)

すわなち、「 $k$ について成り立つ時、 $k$ の次の値（つまり $k+1$ ）についても成り立つ」という形で与えます。一方、値の範囲を順序数全体に拡張した超限帰納法では、このような形ではうまく行きません。なぜなら、 $k$ の値を 1 つずつ増やしていけば、任意の自然数 $n$ に到達できますが、さきほどの $\omega$ には永遠に到達することができないからです。そのため、超限帰納法を利用して、(3-2) を証明する場合は、通常の数学的帰納法よりも強い関係となる (3-1)、すなわち、「 $b < a$ である任意の $b$ について $F(b)$ が成り立つという前提で、 $F(a)$ が成り立つ」ことを証明する必要があります。これは、場合によっては、数学的帰納法よりも証明の難易度があがります。たとえば、任意の自然数 $n$ について $F(n)$ が成り立つ、という前提から、 $F(\omega)$ が成り立つことを証明する場合を想像するとよいでしょう。このように、順序数の列には、「次の値をたどっていく」だけでは永遠に到達できない「値のギャップ」が所々にあり、 $\omega$ のように、そのようなギャップの直後にある値を「極限数」と呼びます。

参考文献

・順序数（TAIKEI BOOK）
・順序数・基数（Eureka GAP）