素数が無限にある証明を背理法で

股関節おじさんの勉強部屋

2023.03.10

論理的に正しいと定義される推論の形式の続き「背理法」を見ていきます。

背理法
1. 定義
2. 例

背理法

定義

【背理法】
とは、ある命題 P を証明したいときに、P が偽であることを仮定して、そこから矛盾を導くことによって、P が偽であるという仮定が誤り、つまり P は真であると結論付けることである^[1]。帰謬法（きびゅうほう）とも言う。

P を仮定すると、矛盾 ⊥ が導けることにより、P の否定 ¬P を結論付けることは否定の導入などと呼ばれる^[2]。
Wikipedia

①命題を正しくないと仮定すると②矛盾する事柄が生じてしまう。③命題が偽ではないことを証明し、命題が真であることを証明するのが背理法です。
xが無理数（分数で表せる）であることを証明するには背理法が便利です。

背理法による論証が認められているのは命題の定義が真か偽以外の結論を排除しているからです。

【命題】
とは、論理学において判断を言語で表したもので、真または偽という性質(真理値)をもつもの^[1][2]。
Wikipedia

【排中律】
排中律（はいちゅうりつ、英: Law of excluded middle、仏: Principe du tiers exclu）とは、論理学において、任意の命題 P に対し”P ∨ ¬P“（P であるか、または P でない）が成り立つことを主張する法則である。これは、論理の古典的体系では基本的な属性であり、同一律、無矛盾律とともに、（古典的な）思考の三原則のひとつに数えられる。

【例】
次の命題 P について考える。

「ソクラテスは死ぬ」

この命題に対して、排中律とは、「ソクラテスは死ぬかあるいは死なないかのどちらかである」

という命題 P ∨ ¬P はつねに成立する（常に真である）、とする主張である（それ以外の第三の状態や中間の状態を取らない）。
Wikipedia

例

素数が無限個存在することを素数が有限個であると仮定しそれが誤りであることを証明し、素数が無限に存在することを証明します。

【素数】
とは、2 以上の自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。1 より大きい自然数で素数でないものは合成数と呼ばれる。
Wikipedia

物質を構成する最小単位を原始と呼ぶように、整数を構成する最小単位。
これ以上細かくできないのが素数です。

素数が有限であると仮定し、その素数を全てかけ合わせた数を考えます。
$P =p_1 × p_2 × p_3 × …p_n$
$P$を再び分解しても、元の素数の集まりにしか戻りません。素数はこれ以上分割できない数なので。
では、もしこの$P$に1を加えて$P$を構成すした素数で再び分解してみましょう。
すると、1だけが余ります。つまり、新たな最大の素数が誕生してしまい、「全ての素数を集めた」という仮定と矛盾してしまうんです。

仮定が偽であるとは有理数が無限に存在することを意味します。
これが背理法ですね。

無限に終わらない証明を省ける点では「数学的帰納法」と同じような威力を持っているのでしょうが、日常では背理法で推論を立てることってほとんどないからなのか、若干の違和感を覚えます。慣れの問題でしょうか。極限の定義と似たような「こんなんで大丈夫？」って感覚。