簡単に教えろ #
一つ以上の自然数の集まりを考えると必ず最小の数が存在する。
例えば $$ \{10, \space 432534, \space 8, \space 42, \space 1, \space 99999999, \space 1 \} $$ という自然数の集まりを考えると、\(1\)がその中の最小のものである。
直感的にはまあ当たり前の話だ。
整列原理(Well-Ordering Principle) #
任意の空でない\(\natnums\)(自然数全体の集合)の部分集合\(S\)は最小元をもつというのが整列原理の主張だ。
紛らわしいので記号でも書いておく $$ S \subset \natnums \land S \neq \empty $$ であれば\(S\)は最小元をもつ。
大した違いはないがここでは\(0 \in \natnums\)であるとする。
証明 #
\(0 \in S\)であれば\(0\)は最小の自然数であり、\(\natnums\)の最小元なので\(S\)は最小元をもつ。
\(0 \leqq k \leqq n \land k \in S\)のとき\(S\)が最小元をもつと仮定する。
そのとき\(0 \leqq k \leqq n +1 \land k \in S\)であれば\(S\)が最小元をもつことを示す。
\(S\)が\(n+1\)未満の元を持たなければ、\(n+1\)が最小元である。
それ以外の場合は、\(S \neq \empty\)なので仮定より主張が成立する。
補足 #
帰納法が分かりにくかったので帰納の具体例を書いておく。
\(0 \leqq k \leqq 0 \land k \in S\)ならば\(S\)は最小元\(0\)をもつ。
つぎに\(0 \leqq k \leqq 1 \land k \in S\)の場合を考える。
\(0 \in S\)であれば\(0\)が\(S\)の最小元である。
\(0 \notin S\)であれば\(1\)が\(S\)の最小元である。
つぎに\(0 \leqq k \leqq 2 \land k \in S\)の場合を考える。
\(S\)が\(2\)未満の元を持たない場合、\(2\)が\(S\)の最小元である。
その他の場合、先程のステップで\(S\)が最小元を持つことが示されている。
これを繰り返せば\(S\)が空でなければ最小元をもちそうなことがわかる。
感想 #
重要らしいが自分のレベルが低いのでよくわからなかった。