「集合と写像」3.4 整列集合,超限帰納法

この記事では,整列集合,順序の定義と,その性質について解説する.

 



 

定義

ここでは,整列集合とそれに関連する用語を定義し,議論の準備をする.

定義 3.4.1 整列集合

半順序集合 \({}(X,\leq_{{}_X})\) が整列集合である,あるいは \(\leq_{{}_X}\) が整列順序であるとは,\(X\) の空でない任意の部分集合が最小限を持つことをいう.すなわち,任意に与えた \(X\) の部分集合 \(A\) について,\(A\not=\emptyset\) ならば,ある \(a\in{}A\) が存在して任意の \(x\in{}A\) に対し \(a\leq_{{}_X}x\) が成り立つことをいう.最小元は,\(\min{A}\) で表す.

 

これ以降,誤解の恐れがなければ \({}(X,\leq_{{}_X})\) が半順序集合のときは \({}(X,\leq_{{}_X})\) を表すのにも \(X\) を用いる.どの集合における順序かは添字で表すことにする.

整列順序が全順序であることは基本的な性質であり簡単に証明できるので,ここで述べておく.

定理 3.4.2

整列順序は全順序である.

証明

\(X\) を整列集合とし,任意に \(X\) の元をふたつ与え,それらを \(x,y\) とする.\(\min{\{x,y\}}=x\) のとき \(x\leq{}y\) であり,\(\min{\{x,y\}}=y\) のとき \(y\leq{}x\) である.いずれの場合も \(x,y\) は比較可能である.以上から,整列集合の任意の二元は比較可能である.よって,全順序の定義から,整列順序は全順序である.

(証明終)

定義 3.4.3 切片

\(X\) を整列集合,\(a\in{}X\) とする.\(X\) の \(a\) 切片とは,\(a\) より小さい元の集まり,すなわち

$$\{\ x\in{}X\mid{}x\leq{}a\ かつ\ x\not=a\ \}$$

のことである.これを \(X{\langle}a{\rangle}\) であらわす.

 

例 3.4.4 \(\mathbb{N}\) の整列性

\(\mathbb{N}\) は,通常の順序について整列集合である.\(A\subset\mathbb{N}\) が空でないなら,\(A\) の元 \(n\) を任意に与えると \(\{k\in{}A\mid{}k\leq{}n\}\) は有限集合であるので最小限を持ち,その最小元が \(A\) の最小元である.

 



 

超限帰納法

\(\mathbb{N}\) に関する命題についての証明には,数学的帰納法を用いることができる.より詳しくいえば,任意の自然数 \(n\) について \(P(n)\) が成り立つ,という命題を証明するには,

  1. \(P(0)\) が成り立つ
  2. 任意の \(n\in\mathbb{N}\) について,\(P(n)\) が成り立つなら \({P(n+1)}\) も成り立つ

を証明すればよい.さらに,2番目の主張を示すかわりに,次の主張を示すだけでも充分である.

任意の \(n\in\mathbb{N}\) について,「\(k\leq{}n\) なら \(P(n)\) が成り立つ」ならば \(P(n+1)\) も成り立つ

 

この証明手法を,整列集合全てに適用できるよう一般化したものが超限帰納法である.

定理 3.4.5 超限帰納法

\(X\) を整列集合とする.その最小限を \(a\) とする.「任意の \(x\in{}X\) について \(P(x)\) が成り立つ」を証明するには,以下の二つを示せばよい.

  1. \(P(a)\) が成り立つ
  2. 任意の \(b\in{X\setminus{\{a\}}}\) について,「任意の \(x\in{}X\langle{b}\rangle\) について \(P(x)\) が成り立つ」ならば \(P(b)\) が成り立つ

証明

1,2 が示されたとする.\(C=\{x\in{}X\mid{}\neg{}P(x)\}\) とする.さらに,\(C\not=\emptyset\) とする.このとき,\(X\) の整列性から \(\min{C}\) が存在するので,\(c=\min{C}\) とおく.このとき,\(X\langle{c}\rangle\) の元は \(C\) の元でないので,任意の \(x\in{}X\langle{c}\rangle\) について \(P(x)\) が成り立つ.よって,\(\mathrm{(ii)}\) より \(P(c)\) が成り立つ.これは,\(c\in{}C\) に矛盾する.以上より,\(C=\emptyset\) である.よって,\(C\) の定め方から,任意の \(x\in{}X\) について \(P(x)\) が成り立つ.

(証明終)

 

前の記事:3.3 順序を保つ写像,順序同型

次の記事:3.5 整列集合と順序を保つ写像


参考書籍

この記事の内容を勉強するにあたり,定番で,筆者も使用している本を紹介します.(定価は2020年05月16日時点のものを表記しています.)

 

まずひとつ目は,内田 伏一著「集合と位相」,通称「内田」です.筆者は主にこちらを使用しています.

数学の基礎となっている集合論の内容と位相空間論の内容をまとめた本です1)普通,大学の数学科では「集合と位相」というタイトルで講義が開講されるので,それに合わせた内容になっています..なお,筆者が用いているのはこれの旧版で,増補改訂版では,演習問題の解答が拡充されているようです.


 

 

  ふたつ目は,松坂 和夫著「集合・位相入門」,通称「松坂」です. 内田同様,位相空間まで網羅した内容となっているほか,濃度の演算や順序数の古典的な扱いにふれられています(内田では省略されている).なお,筆者は,こちらの本も旧版を使っています.  


 

前の記事:3.3 順序を保つ写像,順序同型

次の記事:3.5 整列集合と順序を保つ写像

References   [ + ]

1. 普通,大学の数学科では「集合と位相」というタイトルで講義が開講されるので,それに合わせた内容になっています.