今回は整列集合と切片、超限帰納法について説明します。
まず、一見自明に見える下の定理を証明します。
（定理）
正の整数全体の集合Nの任意の空でない部分集合は最小元を持つ。（順序は実数の大小）
（証明）
MをNの任意の空でない部分集合とする。下の命題( ❇︎ )をnによる帰納法で示す。
( ❇︎ )Mがn以下の整数を元として持てばminMは存在する。
①n=1のとき
明らかにminM=1である。
②n=kのとき(❇︎)が成立すると仮定してn=k+1のときについて考える。
Mがk以下の元を含む場合 帰納法の仮定よりminMは存在する。
Mがk以下の元を含まない場合 n=k+1としているのでMはk+1以下の元を含む。つまりk+1∈M
よってminM=k+1である。
以上より全ての正の整数nについて( ❇︎ )が成立する。
Mは空でないのである元n*を持つ。( ❇︎ )にn*を適用することによってminMが存在することがわかる。(証明終)
定理より正の整数全体の集合は、空でない部分集合が最小元を持つことがわかります。この概念を拡大したのが整列集合です。
(定義)
順序集合Wが下の２つの条件を満たすとき、Wは整列集合である、という。
①Wは全順序集合である。
②Wの任意の空でない部分集合が最小元を持つ。
例
正の整数全体の集合(順序は実数の大小)は整列集合である。
W自身はWの空でない部分集合であるからminWが存在します。
次に、切片と超限帰納法について説明します。
(定義)
Wを1つの整列集合とする。a∈Wとする。Wの元でaより小さいものの集合すなわち
W<a>={x∈W|x<a}
をWのaによる切片という。
練習問題１
Wを整列集合とする。次の２つの条件が同値であることを示せ。
①a=minW
②W<a>=∅
整列集合に関する重要な主張を紹介します。
(主張)
Wを整列集合とする。W*をWの部分集合で下の条件を満たす。このときW=W*である。
(条件)a∈Wを任意の元とする。このとき、W<a>⊆W*⇒a∈W*が成立する。
(証明)
W≠W*とする。W-W*はWの部分集合で空でない。Wは整列集合なのでmin(W-W*)=aが存在する。
このときW<a>∩ (W-W*)=∅が成立する。…(※)
よってW<a>⊆W*であるからW*の満たす条件よりa∈W*が成立する。
またa=min(W-W*)よりa∈W-W*となる。これはa∈W*に矛盾する。
したがってW=W*が成立する。(証明終)
(※)についてb∈W<a>∩ (W-W*)だとするとb<aとb=W-W*を得ますがこれはaの最小性に矛盾します。
上の主張を言い換えると下の系が得られます。これは超限帰納法と呼ばれる有名な主張です。
系(超限帰納法)
整列集合Wの元xに関するある命題P(x)が存在してそれについて次の( ❇︎ )が成立したと仮定する。
( ❇︎ )a∈Wを任意の元とする。
「x<aであるような任意の元xについてP(x)が成立する。⇒P(a)が成立する。」が成立する。
このとき任意の元a∈WについてP(a)が成立する。
(証明)
W*={x∈W|命題P(x)が成立する。}とおく。
系の( ❇︎ )は(ア)に言い換えられる。
(ア)aを任意の元とする。このとき、「W<a>⊆W*⇒a∈W*」が成立する。
これは上の主張の条件と一致するのでW=W*
つまり、任意の元a∈WについてP(a)が成立する。(証明終)
練習問題２
超限帰納法は数学的帰納法の一般化である。この理由を述べよ。
次回は切片の性質について詳しく見ていきます。
では、源義経に感謝。
