コラム 自然数と順序数
さて、自然数という概念を調べるために、自然数より広い概念である「順序数」という概念を導入します。
| 定義1（順序数の定義） |
| クラス\( n \)が\( \in \)に関して強整列的（strictly well-ordered）であるとは、以下が成り立つということである。 |
| (1) 任意の\( m \in n \)と任意の\( m' \in m \)に対し\( m' \in n \)が成り立つ。 |
| (2) 任意の\( m \in n \)と任意の\( m' \in n \)と任意の\( m' ' \in n \)に対し\( m \in m' \)かつ\( m' \in m'' \)ならば\( m \in m' ' \)が成り立つ。 |
| (3) 任意の\( m \in n \)と任意の\( m' \in n \)に対し\( m \notin m' \)または\( m' \notin m \)が成り立つ*1。 |
| (4) 任意の\( m \in n \)と任意の\( m' \in n \)に対し\( m \neq m' \)ならば\( m \in m' \)または\( m' \in m \)が成り立つ。 |
| (5) 任意の部分クラス\( N \subset n \)に対し、\( N \neq \emptyset \)ならばある\( m \in N \)が存在して、任意の\( m' \in N \)に対し\( m = m' \)または\( m \in m' \)が成り立つ。 |
| また\( n \)が順序数（ordinal numberまたはordinal）であるとは、\( n \)が集合でありかつ\( \in \)に関して強整列的であるということである。 |
定義が複雑なようですが、整列順序という概念を用いて表すと、順序数とは単に「\( \in \)または\( = \)」という二項関係が整列順序をなす集合であるということに他なりません。また、包含関係を用いて(1)の条件を書き直すと、次のようになります。
| (1) 任意の\( m \in n \)に対し\( m \subset n \)である。 |
集合の部分クラスが集合であることから、集合であることが分かっている\( n \)に対する(5)の条件は次のように書き直すことが出来ます。
| (5) 任意の部分集合\( N \subset n \)に対し、\( N \neq \emptyset \)ならばある\( m \in N \)が存在して、任意の\( m' \in N \)に対し\( m = m' \)または\( m \in m' \)が成り立つ。 |
この書き換えは重要で、元々の(5)は有界でない量化子を含む論理式であるためクラスに対する分出公理や数学的帰納法を適用できる論理式の必要十分条件を満たさないのですが、書き換えた結果、量化の有界な論理式になったのでクラスに対する分出公理や数学的帰納法を適用を適用することが出来ます。
さて、順序数の例を考えていきましょう。そもそも元を持たない集合である\( 0{} \)は順序数の定義を満たします。また次の命題によって、与えられた順序数から更に大きな順序数を作ることが出来ます。
| 命題2（順序数の後続が順序数であること） |
| 集合\( n \)に対し、以下は同値である。 |
| (1) \( n \)は順序数である。 |
| (2) \( n \cup \{ n \} \)は順序数である。 |
順序数の後続が順序数であることを示すために、次の補題を準備します*2。
| 補題3（順序数の正則性） |
| (1) 任意の順序数\( n \)に対し、\( n \notin n \)である。 |
| (2) 任意の順序数\( n \)と任意の\( m \in n \)に対し、\( n \notin m \)である。 |
証明
(1) \( n \notin n \)であることを背理法で示す。\( n \in n \)と仮定する。\( n \)に対する強整列性の条件(3)から、\( n \notin n \)または\( n \notin n \)、すなわち\( n \notin n \)となる。これは\( n \in n \)に反し、矛盾する。従って\( n \notin n \)である。
(2) \( n \notin m \)であることを背理法で示す。\( n \in m \)と仮定する。\( n \)に対する強整列性の条件(1)と\( n \in m \in n \)から、\( n \in n \)となる。これは(1)に反し、矛盾する。従って\( n \notin m \)である。
(1)ならば(2)を示す。\( n \)が順序数であるとする。この時\( n \cup \{ n \} \)は集合である。
\( n \cup \{ n \} \)に対する強整列性の条件(1)
\( m \in n \cup \{ n \} \)とし、\( m' \in m \)とする。\( n \cup \{ n \} \)の定義から、\( m \in n \)または\( m = n \)である。\( m \in n \)ならば、\( n \)が順序数であることから、\( m' \in n \subset n \cup \{ n \} \)である。\( m = n \)ならば、\( m' \in m = n \subset n \cup \{ n \} \)である。
\( n \cup \{ n \} \)に対する強整列性の条件(2)
\( m \in n \cup \{ n \} \)かつ\( m' \in n \cup \{ n \} \)かつ\( m' ' \in n \cup \{ n \} \)とする。\( n \cup \{ n \} \)の定義から\( m \in n \)または\( m = n \)であり、かつ\( m' \in n \)または\( m' = n \)であり、かつ\( m' ' \in n \)または\( m' ' = n \)である。
まず\( m' ' \in n \)とする。\( m' \in m'' \)かつ\( m \in m' \)より、\( n \)に対する強整列性の条件(3)から\( m' \in n \)かつ\( m \in n \)である。従って\( n \)に対する強整列性の条件(2)から\( m \in m' ' \)である。次に\( m' ' = n \)とする。\( m' \in m' ' = n \)かつ\( m \in m' \)より、\( n \)に対する強整列性の条件(2)から、\( m \in n = m' ' \)である。
\( n \cup \{ n \} \)に対する強整列性の条件(3)
\( m \in n \cup \{ n \} \)かつ\( m' \in n \cup \{ n \} \)とする。\( n \cup \{ n \} \)の定義から\( m \in n \)または\( m = n \)であり、かつ\( m' \in n \)または\( m' = n \)である。まず\( m \in n \)とする。\( m' \in n \)ならば、\( n \)に対する強整列性の条件(3)から\( m \notin m' \)または\( m' \notin m \)である。\( m' = n \)ならば、\( m \in n = m' \)なので順序数の正則性から\( m' \notin m \)である。次に\( m = n \)とする。\( m' \in n \)ならば、順序数の正則性から\( m = n \notin m' \)である。\( m' = n \)ならば、順序数の正則性から\( m = n \notin n = m' \)である。
\( n \cup \{ n \} \)に対する強整列性の条件(4)
\( m \in n \cup \{ n \} \)かつ\( m' \in n \cup \{ n \} \)とし、\( m \neq m' \)とする。\( n \cup \{ n \} \)の定義から\( m \in n \)または\( m = n \)であり、かつ\( m' \in n \)または\( m' = n \)である。まず\( m \in n \)とする。\( m' \in n \)ならば、\( n \)が順序数であることから\( m \in m' \)または\( m' \in m \)である。\( m' = n \)ならば、\( m \in n = m' \)である。次に\( m = n \)とする。この時\( m' \neq m = n \)より\( m' \in n = m \)である。
\( n \cup \{ n \} \)に対する強整列性の条件(5)
\( N \subset n \cup \{ n \} \)を\( \emptyset \)でない部分集合とする。この時、\( n \notin N \)であるか、\( n \in N \)かつ\( N \neq \{ n \} \)であるか、または\( N = \{ n \} \)である。
まず\( n \notin N \)とする。この時\( N \in (n \cup \{ n \}) \setminus \{ n \} = n \setminus \{ n \} \subset n \)より、\( n \)が順序数であることからある\( m \in N \)が存在して、任意の\( m' \in N \)に対し\( m = m' \)または\( m \in m' \)である。
次に\( n \in N \)かつ\( N \neq \{ n \} \)とする。\( N \neq \emptyset \)かつ\( N \neq \{ n \} \)より、\( N \setminus \{ n \} \neq \emptyset \)である。\( N \setminus \{ n \} = N \cap ( (n \cup \{ n \}) \setminus \{ n \}) \subset N \cap n \)より、\( N \cap n \neq \emptyset \)である。\( n \)が順序数であることから、ある\( m \in N \cap n \)が存在して、任意の\( m' \in N \cap n \)に対し\( m = m' \)または\( m \in m' \)が成り立つ。\( m' \in N \)とする。\( m' \in N \cap n \)ならば、\( m \)の選び方より\( m = m' \)または\( m \in m' \)が成り立つ。\( m' \notin N \cap n \)ならば、\( m' \in N \setminus (N \cap n) = N \setminus n \subset (n \cup \{ n \}) \setminus n \subset \{ n \} \)より\( m' = n \)であるので\( m \in N \cap n \subset n = m' \)である。
最後に\( N = \{ n \} \)とする。\( n \in \{ n \} = N \)を\( m \)と置く。\( m' \in N \)とする。\( m' \in N = \{ n \} \)より\( m' = n = m \)である。以上より、\( n \cup \{ n \} \)は順序数である。
(2)ならば(1)を示す。\( n \)は順序数\( n \cup \{ n \} \)の部分集合であるので、\( n \)に対する強整列性の条件(1)が成り立つことだけ示せば良い。
\( n \)に対する強整列性の条件(1)
\( m \in n \)とし、\( m' \in m \)とする。\( m \in n \subset n \cup \{ n \} \)であり、\( n \cup \{ n \} \)が順序数であることから、\( m' \in n \cup \{ n \} \)である。\( n \cup \{ n \} \)の定義から、\( m' \in n \)または\( m' = n \)である。
\( m' = n \)とする。この時\( m \in n \)かつ\( n = m' \in m \)である。\( m \in n \cup \{ n \} \)かつ\( n \in n \cup \{ n \} \)であるので、これは\( n \cup \{ n \} \)に対する強整列性の条件(3)に反し、矛盾する。従って、\( m' \in n \)である。以上より、\( n \)は順序数である。
順序数の後続が順序数であることから、\( 1 \)、\( 2 \)、\( 3 \)、\( 4 \)、\( 5 \)、\( 6 \)、\( 7 \)、\( 8 \)、\( 9 \)もまた順序数であることが従います。より一般に、次が成り立ちます。
| 命題4（自然数が順序数であること） |
| 任意の\( n \in \mathbb{N} \)は順序数である。 |
証明
「\( X \)は順序数である」という量化の有界な論理式を\( \Phi(X) \)と置く*4。\( \Phi(0) \)が成り立ち、かつ順序数の後続が順序数であることから、任意の\( n \in \mathbb{N} \)に対し\( \Phi(n) \)ならば\( \Phi(n \cup \{ n \}) \)である。以上より、数学的帰納法から任意の\( n \in \mathbb{N} \)に対して\( \Phi(n) \)が成り立つ。すなわち、任意の\( n \in \mathbb{N} \)は順序数である。
順序数全体のなすクラスを\( \textrm{Ord} \)と置きます*3。自然数が順序数であることから、\( \mathbb{N} \)は\( \textrm{Ord} \)の部分集合になります。従って、\( \textrm{Ord} \)について知ることは\( \mathbb{N} \)について知ることにも繋がります。
*1 この条件は、[[補遺１>補遺１ その他の公理]]で扱う[[正則性公理>正則性公理#regularity]]を課せば、任意の集合に対して常に成り立ちます。
*2 この補題は、[[補遺１>補遺１ その他の公理]]で扱う[[正則性公理>正則性公理#regularity]]を課せば、順序数とは限らない任意の集合に対しても成り立ちます。
*3 [[自然数が順序数であること>#natural]]の証明の脚注で述べましたように、「&mathjax{X};は順序数である」という文は[[量化が有界な>述語論理#bounded]][[論理式>述語論理#substitution]]ですので、[[クラスに対する分出公理>等号の定義#comprehension]]から順序数全体のなすクラスという概念が意味を持ちます。
*4 集合全体のなすクラスを&mathjax{V};と置くと、&mathjax{\Phi};は変項&mathjax{X};を含む論理式&mathjax{X \in V};かつ&mathjax{\forall m \in X, \forall m' \in m, m' \in X};かつ&mathjax{\forall m \in X, \forall m' \in X, \forall m' ' \in X, ( (m \in m') \wedge (m' \in m' ') ) \to (m \in m' ')};かつ&mathjax{\forall m \in X, \forall m' \in X, (m \notin m') \vee (m' \notin m)};かつ&mathjax{\forall m \in X, \forall m' \in X, (m \neq m') \to ( (m \in m') \vee (m' \in m) )};かつ&mathjax{\forall N \in V, ( (N \subset n) \wedge (N \neq \emptyset) ) \to (\exists m \in N, \forall m' \in N, (m \in m') \vee (m = m') )};となります。そもそも「&mathjax{X};は順序数である」という文はクラスを用いない流儀の公理的集合論の論理式としても表せるので、確かにクラスに対する分出公理が適用可能である[[量化が有界な>述語論理#bounded]][[論理式>述語論理#substitution]]であることが分かります。