大学数学

集合.22 整列可能定理、超限帰納法

整列集合と整列可能定理

前回定義した用語を用いて、整列集合を定義します。


◆Def.SetTop.2.22.1.

X 上の順序 \leq整列順序であるとは、\leq が全順序であって、X の空でない任意の部分集合は必ず \leq に関する最小元を持つことを言う。

整列順序 \leq が定義された集合を整列集合という。


Rem.1. 定義から特に、X 自身に最小元が存在することに注意しましょう。X の最小元を x_0 とすると、これを除いた X \verb|\| \{x_0\} にも定義から最小元 x_1 が存在します。求め方から、x_1x_0 の次に小さな元です。同様のことを繰り返すと、X のすべての元は x_0 \leq x_1 \leq x_2 \leq \cdots小さいものから順に並べることができます。これが整列集合という名前の所以です。


◇Ex.SetTop.2.22.2.

自然数全体の集合 \mathbb{N} で通常の大小関係を考えたものは整列集合です。実際、任意の空でない部分集合について、それに属する最小の自然数が存在します。

一方で、\mathbb{Z} で通常の大小関係を考えたものは整列集合ではありません。しかし、例えば

0 < 1 < -1 < 2 < -2 < \cdots

のように順序を定めれば、整列集合とすることができます。


このように、うまい順序を考えてやることで整列集合とすることができるのですが、実数全体の集合 \mathbb{R} などとなってくるとさすがにうまい方法がわかりません。

しかしながら、選択公理と同値な命題である整列可能定理は、たとえ具体的に求めることができなくても、任意の集合は整列集合とすることができると言っています。


◆Thm.SetTop.2.22.3. (整列可能定理)

任意の集合は、適当な順序によって整列集合とすることができる。


超限帰納法

当ページでも何度か用いていますが、数学の命題の証明手法として数学的帰納法というものがあります。

どういうものか改めて説明しますと、自然数 n についての命題 P(n) があるとき、


1.P(0) が成り立つ
2.P(n) が成り立つならば、P(n+1) が成り立つ
3.したがって、すべての自然数 n について P(n) が成り立つ


という、あたかも帰納的に見える立派な演繹法です。2.によって最初の P(0) が成り立つという性質がドミノ倒しのように伝播していき、すべての自然数について成り立つことがわかるというわけです。

2.の部分は次の2’.に置き換えることができます。


2’.n 以下のすべての自然数 k について P(k) が成り立つならば、P(n+1) が成り立つ。


このようにすると、すべての P(k) が仮定として使えるので、より強力なものになります。

さて、数学的帰納法でポイントになるのは2.(または2’.)から3.が言えるということで、このことは自然数というものの性質に根差しています。

自然数の定義の仕方には色々ありますが、総じて n の次に n+1 がくるといったように帰納的に定義されており、実は定義そのものに数学的帰納法の手法を内包しています。ですから、自然数の定義を公理として認めるならば数学的帰納法の正しさが保証され、逆に数学的帰納法を公理として認めるならば自然数の定義が可能であるという表裏一体の関係になっています。

ところで、2.から3.が言える(直観的な)ポイントは、自然数のどの元にもすぐ次の元があって、順番にドミノ倒しが起きるということです。実はこの性質は、まさに自然数全体の集合が整列集合であるということに他なりません。

そこで、自然数の集合とは限らない整列集合 X に対しても、数学的帰納法と同様の手法を考えることができます。これを超限帰納法と言います。超限帰納法は数学的帰納法の一般化になっています。


◆Thm.SetTop.2.22.4.(超限帰納法)

X, \leq を整列集合とし、P(x)x \in X に関する命題とする。

条件A. y < x を満たすすべての y について P(y) が成り立つならば、P(x) が成り立つ

が成り立つとき、任意の x \in X について P(x) は成り立つ。


■Prf.

X が空集合のときは明らかなので、空集合でないとすると、\leq に関する最小元 x_0 \in X が存在する。

y < x_0 を満たす y は存在しないため、条件Aの仮定は無条件に成り立ち、したがって P(x_0) は成り立つ。

ある z \in X について、P(z) が成り立たないとして矛盾を示す。

次のような X の部分集合 Y を考える。

Y = \{ z \in X \mid P(z) が成り立たない \}

背理法の仮定より、Y は空集合ではない。

Y は整列集合 X の部分集合であるから、Y の最小元 y_0 が存在する。

実は y_0=x_0 である。なぜなら、もし x_0 < y_0 なら、P(y_0) が成り立たないことから、条件Aよりある y < y_0 が存在して P(y) は成り立たない。しかし、これは y_0 の最小性に反する。

よって、y_0=x_0 より P(x_0) は成り立たないが、これは P(x_0) が成り立つことに矛盾する。したがって、示された。 □


 

関連記事

  1. 大学数学

    論理記号.2 否定、かつ、または、~ならば、同値記号

    \( \lnot \) 否定\( P \) を命題とすると、\…

  2. 大学数学

    集合.7 積集合(n個の場合)

    積集合( \(n \) 個の場合)例えば、\( x,y \in…

  3. 大学数学

    集合.14 商集合

    商集合前回の話で、同値類が集合の分割を与えるので、同値類をすべ…

  4. 大学数学

    数の構成.1 自然数.1 ペアノシステムと自然数の構成

    数の構成~自然数から複素数へ~前回まで、一般的な集合や写像の性…

  5. 大学数学

    集合.23 ツォルンの補題

    ツォルンの補題代数学などにおいてよく用いられる選択公理と同値な…

  6. 大学数学

    論理記号.5 論理演算

    論理演算前回までで一通りよく使う論理記号については押さえました…

コメント

  1. この記事へのコメントはありません。

  1. この記事へのトラックバックはありません。

アーカイブ

  1. 大学数学

    集合.20 選択公理
  2. 大学数学

    集合.11 二項関係.1 順序
  3. 大学数学

    写像.6 標準的な写像の例
  4. 大学数学

    大学数学概説.1 大学数学科の一般的なカリキュラム
  5. 大学数学

    数の構成.2 自然数.2 自然数の加法.1 和の定義と数学的帰納法
PAGE TOP
error: Content is protected !!