過去の記事を読むには上のカテゴリーをクリックしてください。
- は半完全
- は非有界
- は有界
を満たすようなもの、 (はを満たす正整数)を
- は-近似可能
- はのある項を割り切る
を満たすような正の有理数とする。このとき、が成り立つ。
証明.
1.1 は有界という仮定から、或るが存在して
が成り立つ。
1.2 正の整数を固定する。
1.3 と表す。.
1.4 正整数を
となるように選ぶ(が非有界という仮定から存在が分かる)。
1.5 正整数であって
を満たすようなものが存在する。
1.6 をの敷居とする。は半完全という仮定より有限確定値を取る。
1.7 正整数を、を満たすように選ぶ(は非有界なので存在する)。
1.8 はのある項を割り切るという仮定から、或る正整数が存在して
が成り立つ。
1.9 正整数、非負整数およびの項であってを満たすものが存在して、
が成り立つ。
理由: は-近似可能なので、Grahamの第一論文を読む -① - INTEGERSで示した補題をとして適用する(は狭義単調増加数列であり、が非有界であることから補題の仮定が満たされることが分かる)。
と書けることは1.8より分かる。
1.10 ならば証明は完了するため、と仮定する。
1.11 が非有界なので
を満たすような整数が存在する。
1.12 が半完全であり、がその敷居なので(1.6)、
を満たすような正整数が存在する。
1.13 整数をを満たすように選ぶ(非有界より存在)。
2.1 と整数を定義する。
2.2 (1.11)より が成り立つ。
2.3 (2,1)、(1.9)より
よって、が成り立つ( (1.13)より)。
2.4 (2.2)、(2.3)より
が成立する。
3.1 と仮定する。このとき、正整数およびであって
および
を満たすようなものが存在する(の定義)。
3.2
とすると、(3.1)よりおよび
が成り立つ。
3.3 (2.3)、(1.9)より
なので、
が成り立つ。
3.4 (1.9)、(3.2)より
が成り立ち、(3.3)よりは相異なるの元である。故に
3.5 よって、
を示すことに帰着された。
4.1 をの生成する自由半群とする(積はで表す)。の元からなる有限列を次のように定める。
4.2 .
4.3 と仮定する。このとき、となるような最大のをとって、
と定める。ただし、やのときはが端っこにくる。
4.4 のとき(ただし、)、
と定める(1.13より。のときは)。
4.5 (4.3)、(4.4)を繰り返して、となるまで続ける。
例) の場合
5.1 に対して、を
と定義する。
5.2 正整数からなる狭義単調増大有限数列を次のように定める。
5.3 .
5.4 まで決まっているとき、を、 (或るに対して)が成り立つような最小正整数として定める(そのようながなければそので終わりでとする。また、そうのようなが複数ある場合は最小のものを取る)。
5.5 4節におけるの定義および上記 の定義より、に対してである。
5.6 (4.3)のについては
が成立する(1.1より)。
5.7 (4.4)のについては
が成立する(1.13より)。
5.8 つまり、任意のについて
が成り立つ。
5.9 任意のに対して
が成り立つ。
理由:とする()。このとき、が存在してと書ける。なら(5.8)よりOK。なら、の定義よりなので、(5.8)より
5.10 定義より次が成り立つ:
6.1 (2.4)、(5.10)、(1.4)より
6.2 と仮定する。このとき、(1.3)よりが狭義単調増加であることと(ただしの可能性はある)、(5.10)より
よって、(1.12)、(1.13)よりが言えて、(3.5)より証明が完了する。
6.3 以下、と仮定する。
6.4 (1.4)、(5.9)より
なので、に対して
が成り立つ。
6.5 (6.3)、(6.1)より
なので、なる正整数となる整数が存在して
が成り立つ。
理由:存在しなかったと仮定する。このとき、
より、(6.4)からが言え、
より、(6.4)からが言え、終いにはとなって(6.1)に矛盾する。
6.6 そのようなで最大のものを、そのときのをとする。
6.7 と仮定する。このとき、が成り立つ。
理由:と仮定する。このとき、
が成り立つ。というのも、ならば
となっての最大性に反するからである(と仮定している)。
同じ議論を繰り返すと、
が得られる。(1.4)、(5.9)より
なので、が成り立つ。よって、
が成立。これを出発点にして先ほどと同じ議論を行っていくと
に辿り着く。(1.4)、(5.9)より
なので、が成り立ち、
が得られる。そうして、が成立。
これを最後まで繰り返すと、遂には
に到達し、(6.1)に矛盾する。
6.8 (2.2)、(6.7)、(5.10)より
が成り立つので、(1.12)より
となって、(3.5)より証明が完了する。
6.9 よって、と仮定する。
6.10 正整数が存在して、
が成り立つと仮定する。
6.11 (1.2)で定めたは任意性があったので、ととって良い(仮定(6.10)が成立する場合、はのみから決まる)。
6.12
を考える。
6.13 (6.9)、(6.11)よりなので、(6.10)より
が成り立つ。よって、(6.6)より
6.14 を
なる最小の整数とする。(6.6)よりなので、このようなは必ず存在する。つまり、
このとき、
が成り立つ。
6.15 一方、である。
理由:(5.10)、(1.7)よりであり、(1.3)よりなので
6.16 すなわち、
が示された。すると、
であり、(6.14)から
が成り立つ。
6.17 を示せばよい。
理由:(1.5)よりならばはに一切現れない。今、(1.7)よりであった。しかし、はの幾つかの積として構成されている。また、はの相異なる元である(1.3)。すると、
はそれぞれがの幾つかの積であり、どれも相異なることがわかる( (6.5)+(6.6)よりであることに注意)。よって、
であることが分かる。また、(6.16)より
なので、が示されれば、とかぶることはない。すなわち、
となって、(3.5)より証明が完了する。
6.18 (6.16)、(6.1)より
が成り立つ。この後、(6.1)に戻って、の代わりにについて同様の議論を行うことになる(があれば同じ議論が出来る)。が、とりあえず(6.19)へ進む。
6.19 次に、任意の正整数に対して正整数が存在して、
であると仮定する。
6.20 このとき、は完全である。
理由:正整数でなるものが存在したと仮定する。すると、に対して
が成り立つ(背理法(対偶)で簡単に確認出来る)。しかし、(6.19)より
であるから、
がで成立する。すなわち、に属さない正整数が無数に存在することになって、が半完全であるという仮定に矛盾する。
6.21 よって、である。
6.22
を考えよう。
6.23 (6.20)よりは完全なので、Brownの判定法より、
が任意の非負整数に対して成立する。
6.24 (6.23)より
が成り立つ。
6.25 整数 ()を
なる最小の整数としてとる( (6.6)から分かるより、なのでこのようなは存在する)。
6.26 のとき。(6.24)より
が成り立つ。よって、
から、について(3.5)を示すには
を示せばよいことが、(6.17)と同様に示される。
6.27 (6.26)、(6.1)よりなので、(6.1)に戻ってに対して同じ議論を行う。
6.28 のとき。
である(6.25)。よって、(6.25)と合わせて
が成り立つ。
なので、について(3.5)を示すには
を示せばよいことが、(6.17)と同様に示される。
6.29 (6.28)、(6.1)よりなので、(6.1)に戻ってに対して同じ議論を行う
ことができる。
6.30 こうして、(6.18)、(6.27)、(6.29)とどのケースでも(6.1)に戻ってに対して同様の議論を行うことができる。すると、と何度でも(6.1)にループすることになるが、実際には
とが減少していくので、が非負整数であることからこのループは有限回で必ず停止し、(1.12)、(1.13)、(3.5)によって証明が完全に完了する。
Q.E.D.
これで、第一論文は読み終わりました。