L&M個別オンライン教室~論理と数学とプログラミングのオンライン授業~L&M個別オンライン教室~論理と数学とプログラミングのオンライン授業~L&M個別オンライン教室~論理と数学とプログラミングのオンライン授業~

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

【証明】
すべての素数をXとする。Xの個数は有限又は無限である。
仮に有限しかないとすると、それらすべてを掛け合わせることができ、
掛け合わせた数をxとすると、xも有限である。
x+1は少なくとも一つの素数で割られる(後で証明する)ので、その素数をpとする。
Xのどの素数もx+1を割ることはできないので、pはXにはない。
これはXがすべての素数であることに反する。
したがって、素数は無数にある。 □

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

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

【メモ】
ちなみに、自然数とは1以上の整数である。
素数とは自然数nでnと1以外には割られない数である。
aがbで割られること、a=bcであること、bがaの約数であることは同値である。

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

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

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

次に、自然数nの約数をm、mの約数をlとすると、
n=km、m=k’lより、n=(kk’)lとなり、
lはnの約数となる。
つまり、自然数nの約数の約数は、nの約数でもある。

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

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

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

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

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

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

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

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

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