2.1 整列原理を使った証明の例

実は、以前に示した \(\sqrt{2}\) の無理数性の証明では整列原理が当たり前の事実として使われている。定理 1.8.1 の証明では、任意の正整数 \(m\), \(n\) に対して分数 \(m/n\) を既約分数にできる、つまり公約数を持たない整数 \(m^{\prime}\), \(n^{\prime}\) を使って \(m^{\prime} / n^{\prime}\) と書けると仮定していた。これが可能なのはどうしてだろうか？ 背理法と整列原理を使うと示せる:

証明 分数 \(m/n\) が既約分数で表現できないような正整数 \(m\), \(n\) の存在を仮定する。\(m/n\) に等しい分数の分子であるような正整数を全て集めた集合を \(C\) とすると、\(m \in C\) より \(C\) が非空だと分かる。よって整列原理より、\(C\) は最小要素 \(m_{0}\) を持つ。\(C\) の定義より、次の条件を満たす正整数 \(n_{0} > 0\) が存在する:

これは \(m_{0}\) と \(n_{0}\) が共通の素因数 \(p > 1\) を持つことを意味する。一方で次の等式が成り立つ:

この等式の左辺を既約分数で表現できれば、それは右辺に等しい既約分数でもある。よって次が分かる:

よって \(C\) の定義より、分子 \(m_{0}/p\) は \(C\) に属する。一方 \(m_{0}/p < m_{0}\) であり、これは \(m_{0}\) が \(C\) の最小要素である事実と矛盾する。

\(C\) が非空という仮定から矛盾が得られたので、\(C\) は空でなくてはならない。つまり既約分数で表現できない分数の分子は存在せず、既約分数で表現できない分数も存在しないと証明できた。 ■

これまでにも整列原理は密かに使われていた！