過去の記事を読むには上のカテゴリーをクリックしてください。
定義
が完全 の敷居が.
主定理
- は半完全
- は有界
を満たすようなものとする。このとき、正の有理数がの元となるための必要十分条件は
- は-近似可能
- はのある項を割り切る
が成り立つことである。
Grahamの第一論文を読む ー③ - INTEGERSで次の定理を証明します:
- は半完全
- は非有界
- は有界
を満たすようなもの、 (はを満たす正整数)を
- は-近似可能
- はのある項を割り切る
を満たすような正の有理数とする。このとき、が成り立つ。
この記事では定理1から主結果を導きましょう。
まず、二つ目の仮定を次のように置き換えることができます:
- は半完全
- は有界かつなるが無数に存在する
- は有界
を満たすようなもの、 (はを満たす正整数)を
- は-近似可能
- はのある項を割り切る
を満たすような正の有理数とする。このとき、が成り立つ。
定理1を仮定した定理2の証明
正の整数 であって
を満たすようなものが存在する(二つ目の仮定から分かる)。このとき、
という順に並べて得られる新しい非有界数列をとする。正の整数に対していくらでも大きいをとってとできることに注意すれば
が成り立つことが分かる(の項を順番に有限個掛け合わせたときに、のべきはまとめて一番右端に持っていって考えればよい)。よって、が定理1の仮定を満たしていることを示せば証明が完了する。確認すべきはが有界であることであるが、
より成立する。 Q.E.D.
そして、二つ目の仮定は必要ないことが判明します:
- は半完全
- は有界
を満たすようなもの、 (はを満たす正整数)を
- は-近似可能
- はのある項を割り切る
を満たすような正の有理数とする。このとき、が成り立つ。
定理1を仮定した定理3の証明
もし、なるが有限個しか存在しないならばは有限数列となるので、は半完全ではない。従って定理1または定理2の二つ目の仮定が成立することが分かる。 Q.E.D.
- は-近似可能
- はのある項を割り切る
が成り立つ。
証明. 一つ目の条件は自明に成立する。なる仮定より、正整数が存在して
と書ける。すなわち、を得るが、とは互いに素であると仮定しているので
が成り立ち、はの項である。 Q.E.D.
以上で、定理1が証明できれば主定理が従うことが分かりました。