「素数の個数は無限にある」を、「～ならば～～」という形にするにはどうすればいいのでしょうか？

質問

大学の課題で、↑の命題（というか定理…）を
（１）同一法
（２）対偶法
（３）転換法
の３通りで証明せよというものがだされたのですが、↑でかいたように
「～ならば～～」という形の命題でないとできませんよね…？
いったいどうすればいいのでしょうか？
各証明の始め方だけでも良いです。
返答宜しくお願いします。

回答No.5

kts2371148 · ベストアンサー

わたしは実のところ、同一法とは何か、転換法とは何かについては知りませんでした。
http://web.agr.ehime-u.ac.jp/~kishou/lecture/math2f/text/2T.pdf
（１３ページのＰＤＦファイルの１０枚目）をご覧頂ければよいかと思います。

転換法の証明は以下の通りです。
（私がまだ勘違いをしていたようで、すいません…）

(1) Ａが有限集合ではなく、かつ「任意の素数 p について p∈Ａ であり、任意の素数でない要素 q について q∈/Ａ」が成り立つならば、
　　　　Ａ＝{ p | p はすべての素数 }
(2) Ａが有限集合である、または「任意の素数 p について p∈Ａ であり、任意の素数でない要素 q について q∈/Ａ」が成り立たないならば、
　　　　Ａ≠{ p | p はすべての素数 }

ここで、
(1) の前半を p1 、後半を q1 とおく。
(2) の前半を p2 、後半を p2 とおく。

(a) 場合分け p1,p2 により、すべての場合が尽くされている。

(b)

p1→q1 を証明する。
（証明）
「任意の素数 p について p∈Ａ であり、任意の素数でない要素 q について q∈/Ａ」が成り立つことより、
Ａ＝{ p | p はすべての素数 } は自明である。
（証明終）

p2→q2 を証明する。
（証明）
（Ａが有限集合の場合）その要素を a[1],a[2],…,a[n] とおく。
a[1]×a[2]×…×a[n] + 1 が
　素数ならば、その素数はＡに属さない
　合成数ならば、素因数分解して得られる素数はＡに属さない
よって、Ａが有限集合ならば、Ａ≠{ p | p はすべての素数 } である。
（「任意の素数 p について p∈Ａ であり、任意の素数でない要素 q について q∈/Ａ」が成り立たない場合）
Ａ≠{ p | p はすべての素数 } は自明である。
よって、p2→q2 が成り立つ。
（証明終）

(c) q1,q2 は両立しない。

よって、転換法により、q1→p1 が成り立つ。
これにより、「Ａ＝{ p | p はすべての素数 } ならば Ａが有限集合ではない」が得られる。

同一法の証明は以下の通りです。

Ａ＝{ p | p はすべての素数 } とおく。
Ａの最大値が存在すると仮定し、その要素を a[1],a[2],…,a[n] とおく。
a[1]×a[2]×…×a[n] + 1 が
　素数ならば、その素数はＡより大きい。
　合成数ならば、素因数分解して得られる素数はＡより大きい。
これは矛盾であるから、Ａの最大値は存在しない。よって、Ａは有限集合ではない。

お礼

ありがとうございます。
遅れてしまい申し訳御座いません。

僕も​http://web.agr.ehime-u.ac.jp/~kishou/lecture/math2f/text/2T.pdf​
を参考にして調べていたのですが、さっぱりだったんです。

でも、おかげさまで同一法・転換法が少しわかった気がします。
ありがとうございました！

回答No.4

kts2371148

＃３です。
転換法のところで、私が勘違いしたようです。失礼しました。

(1) Ａが有限集合ではなく、かつ「任意の素数 p について、Ａ∪{p}＝Ａ」が成り立つならば、Ａ＝{ p | p はすべての素数 }
(2) Ａが有限集合である、または「任意の素数 p について、Ａ∪{p}＝Ａ」が成り立たないならば、Ａ≠{ p | p はすべての素数 }

で始めればＯＫだと思います。

お礼

ありがとうございます。
おかげさまでなんとか間に合いました。
ただ、レポートに関する話が今日は無かったので出すだけで終わってしまいましたが…。

ただ、同一法や転換法の定義にこれらがどうあてはまっているのかいまいちわかっていません…
何度も申し訳ないですが、解説していただけませんでしょうか？

回答No.3

kts2371148

提出日は明日なんですか…
ということはもう少しヒントを。

同一法は、「Ａは有限集合ではない」ことを証明するかわりに、
「Ａは整数を要素とする集合であるにもかかわらず最大値がない」ことを証明すればＯＫです。

転換法は、
「Ａは
(1) 有限集合であり、Ａ＝{ p | p はすべての素数 }
(2) 有限集合ではなく、Ａ＝{ p | p はすべての素数 }
(3) 有限集合か有限集合でないかのどちらかであり、Ａ≠{ p | p はすべての素数 }
のどれかである。」で始めればいいでしょう。
（実質的に対偶法と同じですが）

回答No.2

kts2371148

某サイトで同じ質問をされているようですね。
live-earthさんは、
「できれば自分で解きたい。
　でも手がかりすらわからないので、せめてそれだけでも知りたい。
　そして、少しずつ助けを得ながら、できる限り自分で解くようにしたい。」
という気持ちを持っておられるようにお見受けします。
もしそうであれば、某サイトには投稿せず、OKWaveにのみ投稿された方がよいかと思います。
OKWaveは双方向のやり取りが可能ですが、
某サイトは一発で答えを書かれてしまう危険性がありますから。

それを知らずに某サイトでも回答してしまいました。
原則としてOKWaveにて回答したいと思います。

「～ならば～～」の形にしたいということですが、
「集合Ａ＝{ p | p はすべての素数 } ならば、Ａは有限集合ではない」
でどうでしょうか？

問題は、それを同一法・対偶法・転換法の３通りで証明できるかどうかですが、
ネットで検索すれば、素数が無限にあることの証明は山ほど出てきます。
でも、背理法が主流のようです。
背理法をちょっといじれば対偶法の証明ができますので、
対偶法についてはノーヒントで解いてほしいところです。

お礼

ありがとうごいざいます。
おかげさまで対偶法に関してのみは解決しました。
が、やはり同一法と対偶法に関してはまったく見当が付かない状態です。
提出日は明日ですが、もう少し頑張ってみようと思います。

回答No.1

kabaokaba

一つの例．
ある集合が素数全体の集合ならば
それは無限集合である

どれにしろユークリッドの証明方法（本質的に背理法）
を採用するのでしょうね．
けど・・・同一法でどうやるんだろ・・・
命題そのものを書き直すのかな

お礼

ありがとうございます。
素数は無限個ってのの証明って正味背理法が王道ですもんね…
同一法の仕方は、解決はしていませんがおっしゃるとおり命題そのものを同値なもんに変換して証明…みたいな感じにでもしないと無理な感じがしています。