素数が無限にあることの証明

【証明】
すべての素数をＸとする。Ｘの個数は有限又は無限である。
仮に有限しかないとすると、それらすべてを掛け合わせることができ、
掛け合わせた数をｘとすると、ｘも有限である。
ｘ＋１は少なくとも一つの素数で割られる（後で証明する）ので、その素数をｐとする。
Ｘのどの素数もｘ＋１を割ることはできないので、ｐはＸにはない。
これはＸがすべての素数であることに反する。
したがって、素数は無数にある。　□

自然数ｎは少なくとも一つの素数で割られることの証明

ｎが素数の場合には、ｎで割ればよい。
以下、ｎは素数でないとする。

【メモ】
ちなみに、自然数とは１以上の整数である。
素数とは自然数ｎでｎと１以外には割られない数である。
ａがｂで割られること、ａ＝ｂｃであること、ｂがａの約数であることは同値である。

【証明１】
自然数ｎは一意に素因数分解されるので、少なくとも一つの素数で割られる。　□

【メモ】
自然数ｎが一意に素因数分解されることは、算術の基本定理と呼ばれる。
素因数分解とは、自然数ｎと等しい素数の積を見つけることである。
一意というのは、そのような素数の組が一つに定まるということである。
よく考えると、【証明】では一意であることや素因数分解されることは使っていない。
したがって、次の証明が考えられる。

【証明２】
自然数ｎが一意に素因数分解されることを用いない。
自然数ｎにｎと１以外の約数があれば、その約数ｘを一つ取り、同様の操作Ｔを繰り返す。
操作Ｔの対象となる約数は、前操作の約数よりも小さくなる。
自然数は下に有限なため、一連の操作はｘと１以外に約数のない数を取って終了する。
そのようなｘは素数であり、ｐとする。

次に、自然数ｎの約数をｍ、ｍの約数をｌとすると、
ｎ＝ｋｍ、ｍ＝ｋ’ｌより、ｎ＝(ｋｋ’)ｌとなり、
ｌはｎの約数となる。
つまり、自然数ｎの約数の約数は、ｎの約数でもある。

操作Ｔは、自然数ｎの約数を取る操作であったので、
操作Ｔの繰り返しで取られた素数ｐもｎの約数である。
したがって、自然数ｎは少なくとも一つの素数ｐで割られる。　□

【証明】の論理構造の考察

【証明】の論理構造を考察すると、その骨格は、
命題Ａ「すべての素数は有限である」という仮定の下で、
命題Ｂ「すべての素数をＸとする」⇒命題¬Ｂ「Ｘはすべての素数でない」という矛盾を導き出している。
つまり、Ａ⇒(Ｂ⇒¬Ｂ）である。
そして、すべての素数は有限でないから無限であると結論する。
では、すべての素数が無限であれば、有限の場合と同じ操作を行っても矛盾は生じないのだろうか？
もしも、矛盾があったとしたらどうなるのか？

まず、命題Ｃ「すべての素数は有限又は無限である」について考える。
無限を「大きすぎて考えられない数」と捉えれば、有限は「大きくなくて考えられる数」であり、
つまり、すべての素数は「考えられる個数」又は「考えられない個数」かであると主張している。
では、「考えられる」とは何か、それは「全体をＸと対象化したり」「全体Ｘから一部を取り出したり」「すべてを掛け合わせたり」「＋1などの四則演算をする」ことなどである。

無限はどの操作ができてどの操作ができないのか。少なくとも無限とは「命題がその数を含むと、命題が真偽不明になる、つまり命題でなくなる場合のある数」と言える。そこで大切なのは、無限を含むどのような命題が真偽不明になるのかを明確にすることである。さらに言えば、命題を伴わない有限・無限という枠組みを一度捨てて、そのような各命題によって相対的に有限・無限を定義したり、分類したりすることもできるだろう。

今回で言えば、命題Ｄ「すべての素数は無限個である」は真としているが、命題Ｅ「無限個の素数をすべて掛け合わせた数がある」や命題Ｆ「無限個の素数をすべて掛け合わせた数＋１という数がある」は命題として扱っていない。
では仮に、命題として扱い矛盾が生じたらどうなるか。命題Ｃは有限又は無限のどちらでも矛盾するので、命題Ｃ自身が矛盾することになり、すべての素数が有限又は無限でない何かであることを示すか、さもなければ「すべての素数を対象化すること」が矛盾を抱えるので、すべての素数をまとめて扱う議論は大きな制約を受ける。
そこで、命題ＥＦを真偽不明として、命題としては扱わずに切り捨てれば矛盾も生じず、命題Ｃを前提として命題Ｄが真となる主張が保たれ、素数をまとめて扱う議論が可能となる。つまり、「全体をＸと対象化したり」「全体Ｘから一部を取り出したり」するのを可とし、「すべてを掛け合わせたり」「＋1などの四則演算をする」のは不可とするのである。

ただ、命題ＥＦを切り捨てると不完全になる。
そこで、直観的な観点から、
「無限個の1以上の数を足したり、掛け合わせれば無限になる」
「無限の四則演算を「∞＝∞＋ｎ,∞＝∞×ｎ（1≤ｎ）」とする」
これらの命題を前提とすれば、
ｘ＝∞、ｘ＋1＝∞で、
「ｘ＋１は少なくとも一つの素数で割られる」は、ｘ＋1＝∞＝∞×ｐで真であり、
「Ｘのどの素数もｘ＋１を割ることができる」ことになり、
ｐがすべての素数Ｘに入っていても矛盾を生じない。
つまり、すべての素数が無限であれば、有限の場合と同じ操作を行っても矛盾を生じなくなる。

ちなみに、「すべての素数」を対象化することなく、数学的帰納法によって素数が無限にあることを証明できる。
参照：背理法被害者の会「素数の無限性」
この場合は、「すべての素数は有限又は無限である。」という仮定も必要ない。
数学的帰納法から上記の仮定を証明（数学的帰納法は途中で終わるか終わらないかのどちらか）することができるし、おそらく、数学的帰納法を認めることと、加算無限集合の対象化とは同値なのだと思う。

公開日：2017/4/19
修正日：2017/5/5、【メモ】4行目「素因数分解されること」を追加
修正日：2017/5/15、【証明】「すると、すべての素数をＸとして、それらを」⇒「すると、すべての素数をＸとできる。それらを」
【証明】「どの素数についてもｘ＋１は割られないので」⇒「どの素数もｘ＋１を割ることはできないので」
【証明２】「素数ｐはｎの約数」⇒「素数ｐもｎの約数」
修正日：2017/5/19、最後尾に「【証明】の論理構造の考察」を追加
【証明】を有限だと矛盾を生み、無限だと矛盾が回避される論理構造が明確になるように修正
修正日：2017/5/20、「【証明】の論理構造の考察」の１段落目後半に「では、すべての素数が無限であれば、同じ操作を行っても矛盾は生じないのだろうか？もしも、矛盾があったとしたらどうなるのか？」を追加
２段落目を「ことなどである。（改行）無限はどの操作ができてどの操作ができないのか。」で段落分け
３段落目「は真偽不明であり、命題として扱っていない。」⇒「は命題として扱っていない。」
３段落目「そこで、命題ＥＦを命題として扱わずに切り捨てれば矛盾も生じず、」⇒「命題ＥＦを真偽不明として、命題としては扱わずに切り捨てれば矛盾も生じず、」
修正日：2017/5/30、最後尾に数学的帰納法による証明のリンクを追加
最終修正日：2017/5/30