整列集合に関する帰納法 整列集合に関する帰納法

整列集合に関する帰納法

定義 Aを全順序集合、aをAの元とします。 aより小さいAの元の集合{x∈A|x<a}を、Aにおけるaの切片といいます。 これをC(a)とかくことにします。 厳密には切片はaだけでなくAにも依存するのでC(a,A)などとかくべきでしょうが、通常Aは省略します。 定理1 Aは整列集合、BはAの部分集合であるとします。 任意のx∈Aに対して「C(x)⫅Bならばx∈B」がなりたつならば、A=Bです。 証明 対偶を示します。 A≠Bとします。 A-Bは空集合でないA(整列集合)の部分集合なので、最小元aをもちます。 A-Bにaより小さい元はないのでC(a)∩(A-B)=∅です。 したがってC(a)⫅Bです。 しかし、aはA-Bの元、つまりBの元ではないので、x=aととれば「C(x)⫅Bならばx∈B」が成立しないことがわかります。 別証 ※任意のx∈Aに対して「C(x)⫅Bならばx∈B」がなりたつと仮定します。 A≠Bを仮定して矛盾を導きます。 A-Bが空でないので、その元を一つとってa0とします。 a0∉Bなので、※よりC(a0)⫅Bが成立しません。 したがってa1∉Bで、a1∈C(a0)、つまりa1<a0であるようなものが存在します。 以下同様にして無限下降列a0,a1,...が構成でき、Aが整列集合であることと矛盾します。 定理2 Aは整列集合であるとします。 任意のx∈Aに対して「任意のy<xとなるAの元yに対して命題P(y)がなりたつならば、P(x)がなりたつ」ならば、任意のx∈Aに対してP(x)がなりたちます。 証明 ※任意のx∈Aに対して「任意のy<xとなるAの元yに対して命題P(y)がなりたつならば、P(x)がなりたつ」ことを仮定します。 B={x∈A|P(x)}とおきます。Bは当然Aの部分集合です。 Aの元xを適当にとります。 ※※C(x)⫅Bがなりたつと仮定します。 y<xとなるAの元をとると、切片の定義よりy∈C(x)なので、y∈Bでもあり、よってP(y)がなりたちます。 したがって仮定※より、P(x)がなりたちます。 ※※を仮定してP(x)がなりたったので、Bは定理1の条件をみたします。 したがってA=B、つまり任意のx∈Aに対してP(x)がなりたちます。