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