2.4 整列集合
実数の集合が整列 (well ordered) とは、空でない任意の部分集合が最小要素を持つことを言う。この定義を使って言い換えると、整列原理は非負整数全体の集合が整列であると主張している。他にも整列な実数の集合 (整列集合) は多くある。簡単な例として \(r > 0\) に対する \(r\mathbb{N}\) がある: つまり固定された正の実数 \(r\) と任意の \(n \in \mathbb{N}\) を使って \(rn\) と表せる実数全体の集合は整列である (理由が分かるだろうか？)。
情報科学において、整列原理は計算がいずれ停止することの証明でよく現れる。「計算の各ステップに上手く値を割り当て、計算のステップが進むたびにその値が小さくなるようにする」が基本的なアイデアとなる。もし割り当てられる値が全て整列集合の要素なら、その計算はいずれ停止する。なぜなら、もし停止しなければ、各ステップに割り当てた値全体の集合が最小要素を持たない部分集合となるからである。第 6 章では、状態機械がいずれ停止することを証明するためにこのテクニックを利用する。
最小要素を持つ集合が整列でない可能性がある点に注意してほしい。非負有理数全体の集合がその例である: この集合は最小要素 \(0\) を持つものの、最小要素を持たない非空部分集合 (例えば正の有理数全体の集合) が存在する。
整列原理を少しだけ一般化すると次の定理を得る:
任意の非負整数 \(n\) に対して、\(-n\) 以上の整数だけからなる集合は整列である。
この定理は整列原理と同程度に明らかであり、公理として受け入れても何も問題はないだろう。ただ、新しい公理を何度も追加していくといずれ議論を追うのが難しくなるので、公理として追加しようとしている命題が実際には証明できる可能性は常に考える価値がある。今回の場合、定理 2.4.1 は整列原理から簡単に証明できる:
証明 \(-n\) 以上の整数だけからなる集合を \(S\) として、\(S\) の各要素に \(n\) を加えた集合を \(S + n\) とする。\(S + n\) は非負整数の非空集合だから、整列原理より最小要素 \(m\) を持つ。このとき \(m - n\) が \(S\) の最小要素であることは容易に示せる。 ■
整列性の定義からは、整列集合の任意の非空部分集合も整列だと分かる。ここから定理 2.4.1 の有用な系が直ちに得られる。
実数の集合 \(S\) の下界 (lower bound) とは、任意の \(s \in S\) に対して \(b \leq s\) が成り立つ実数 \(b\) を言う。同様に、実数の集合 \(S\) の上界 (upper bound) とは、任意の \(s \in S\) に対して \(s \leq b\) が成り立つ実数 \(b\) を言う。
実数の集合 \(S\) の上界と下界が \(S\) に属する必要はない点に注意してほしい。
整数の集合が下界を持つなら、整列である。
証明 整数の集合 \(S\) が下界 \(b \in \mathbb{R}\) を持つとする。このとき \(n = \lfloor b \rfloor\) も \(S\) の下界である。ここで \(\lfloor b \rfloor\) は \(b\) の床 (floor) と呼ばれ、\(b\) 以下の最大の整数を表す。そのため定理 2.4.1 から \(S\) は整列だと分かる。 ■
系 2.4.3 からは、普段証明なしに使っている次の基礎的事実が証明できる:
整数の非空集合が上界を持つなら、最大要素を持つ。
証明 整数の非空集合 \(S\) が上界 \(b\) を持つとする。\(S\) の各要素に \(-1\) を乗じることで得られる集合を \(-S\) とすれば、\(-b\) は当然 \(-S\) の下界である。よって系 2.4.3 より \(-S\) は最小要素 \(-m\) を持つ。容易に分かるように、このとき \(m\) は \(S\) の最大要素である。 ■
有限集合も整列集合の典型的な例である:
実数の非空有限集合は整列である。
証明 有限集合の任意の部分集合は有限集合だから、任意の実数の非空有限集合が最小要素を持つと示せばよい。有限集合の要素数に整列原理を適用することでこれを示す。
最小要素を持たない有限集合の要素数からなる集合を \(C\) とする。矛盾を導くために \(C\) が非空だと仮定する。このとき整列原理より \(C\) は最小要素 \(m\) を持つ。
要素数が \(1\) の実数の集合は全て最小要素を持つから、\(m \geq 2\) が分かる。
\(F\) を要素数が \(m\) の実数の集合とする。これから \(F\) が最小要素を持つことを示して矛盾を導く。
\(F\) の要素を任意に取って \(r_{0}\) とする。\(m \geq 2\) より、\(F\) から \(r_{0}\) を除去した集合 \(F^{\prime}\) は要素数が \(m\) より小さい実数の非空集合である。\(m\) は \(C\) の最小要素だから、\(F^{\prime}\) は最小要素 \(r_{1}\) を持つ。しかしこのとき、\(r_{0}\) と \(r_{1}\) の小さい方が \(F\) の最小要素となる。 ■
2.4.1 別種の整列集合 [スキップ可]
\(n/(n + 1)\) の形で表せる有理数全体の集合 \(\mathbb{F}\) とする:
この \(\mathbb{F}\) は整列である。実際、\(\mathbb{F}\) の任意の非空部分集合の最小要素は、\(n/(n+1)\) の形で表したときの \(n\) の値が最も小さい要素である。
\(\mathbb{F}\) の各要素に全ての非負整数を加えると、今までに見てきたものと大きく異なる整列集合が得られる。つまり、非負整数 \(n\) と \(\mathbb{F}\) の要素 \(f\) を使って \(n + f\) と表せる実数全体の集合である。この集合を ── 読者の想像通り ── \(\mathbb{N}\) + \(\mathbb{F}\) と書く。\(\mathbb{N} + \mathbb{F}\) の任意の非空部分集合から最小要素を見つける簡単な手続きが存在するので、この集合が整列だと分かる:
\(\mathbb{N} + \mathbb{F}\) は整列である。
証明 \(\mathbb{N} + \mathbb{F}\) の任意の非空部分集合 \(S\) が与えられたとき、何らかの \(f \in \mathbb{F}\) に対して \(n + f \in S\) であるような非負整数 \(n\) 全体の集合に注目する。この集合は非負整数の非空集合だから、整列原理より最小要素が存在する。この最小要素を \(n_{S}\) とする。
\(n_{S}\) の定義より、\(n_{S} + f \in S\) となる \(f \in \mathbb{F}\) が存在する。\(n_{S} + f \in S\) を満たす \(f \in \mathbb{F}\) 全体の集合は \(\mathbb{F}\) の非空部分集合であり、\(\mathbb{F}\) は整列より最小要素を持つ。この最小要素を \(f_{S}\) とする。容易に分かる (問題 2.20) ように、\(n_{S} + f_{S}\) は \(S\) の最小要素である。 ■
集合 \(\mathbb{N} + \mathbb{F}\) はこれまでに見てきたものと大きく異なる整列集合の例であり、様々な整列集合を構築するためのヒントを提供する。以前に見た整列集合では、各要素が他の有限個の要素より大きいだけだった。しかし \(\mathbb{N} + \mathbb{F}\) では、\(1\) 以上の任意の要素から始まる任意の長さの狭義減少列が存在する。例えば、次に示す狭義減少列はどれも \(1\) から始まる:
一方で \(\mathbb{N} + \mathbb{F}\) は整列だから、当然その要素からなる無限長の減少列は存在しない: もし存在したら、その数列の要素は最小要素を持たない \(\mathbb{N} + \mathbb{F}\) の部分集合となってしまう。