√2が無理数であることを数学的帰納法で示したい。

質問

√2が無理数であることを数学的帰納法で示したいのです。

任意の自然数p,qでp/q≠√2であることを示せばよい。
座標(p,q)の格子点で、p=1,q=1のときを示し、右上方向へのドミノ倒しをしていくかんじの、二重数学的帰納法で示そうと思いました。

p=1のとき、0<p/q≦1、1<√2<2より、p/q≠√2
p≧2,q=1のとき、2≦p/q、1<√2<2より、p/q≠√2
あとは、p/q≠√2、p/(q+1)≠√2、(p+1)/q≠√2⇒(p+1)/(q+1)≠√2を示す。
対偶の、(p+1)/(q+1)＝√2⇒p/q＝√2、または、p/(q+1)＝√2、または、(p+1)/q＝√2を示す。
つまり、p＝q√2+√2-1⇒(p/q-√2){p/(q+1)-√2}{(p+1)/q-√2}=0を示す。
p＝q√2+√2-1のとき、
(p/q-√2){p/(q+1)-√2}{(p+1)/q-√2}={(√2-1)/q}{-1/(q+1)}{√2/q}＝…

これが0になることを示せばよいのですが、うまくいきません。
どこが間違っているのでしょうか?
または、どのよう修正すればうまくいきますか？

回答No.6

stomachman · ベストアンサー

以下、p, q, n, m, a, bは全部自然数に限定、ということをいちいち書くと煩わしいので、省略します。

第１段
∀q( p=1 → (p^2)/(q^2)≠2 )
を示す。
証明：（簡単だから省略）

第2段
∀q( ∀p(p<n) → (p^2)/(q^2)≠2 )
であると仮定して
∀q( ∀p(p<n+1) → /(q^2)≠2 )
を示す。

証明：
[1]qとnがどちらも偶数である場合。
q=2a, n=2bとする。
(n^2)/(q^2)=(b^2)/(a^2), b＜n なので仮定により(b^2)/(a^2)≠2。だから
(n^2)/(q^2)≠2

[2]qが偶数(2m)でnは奇数(2s+1)であるとき。
(m^2)(n^2)/(q^2)=(m^2)((4s^2+4s+1)/4(m^2))=s(s+1)+1/4
だから(m^2)(n^2)/(q^2)は整数ではない。従って、
(m^2)((n^2)/(q^2)-2)は整数ではない。
だから(n^2)/(q^2)-2≠0つまり
(n^2)/(q^2)≠2

[3]qが奇数(2m+1)でnが偶数(2s)のとき。
2(s^2)(q^2)/(n^2)=2(4m^2+4m+1)/4 = m(m+1)/2+1/2は整数ではない。
だから、2(s^2)((q^2)/(n^2)-1/2)=2(s^2)(q^2)/(n^2)-(s^2)は整数ではない。
だから(q^2)/(n^2)-1/2≠0つまり
(n^2)/(q^2)≠2

[4]qが奇数(2m+1)でnが奇数(2s+1)であるとき。
((n^2)-2(q^2))=(4m(m+1)+1)-2(4s(s+1)+1)=4m(m+1)-2(4s(s+1)+1)+1は奇数である。
だから、((n^2)-2(q^2))は0ではない。
以上から∀((n^2)/(q^2)≠2) …★
従って、仮定により
∀q( ∀p(p<n+1) → /(q^2)≠2 )
Q.E.D.

　ほら、数学的帰納法で証明できたす。

　ここで、★は場合分け、すなわち「(A→B)と(Aでない→B)からBを結論する論法（ジレンマ）」を使っています。ジレンマは「AでありしかもAでない、ということはない（排中律）」を前提にしているからこそ成立つ論法です。そして、排中律を前提にすれば、「(Bでない→矛盾)からBを結論する論法（背理法）」も成立つ。つまり、場合分けというのは背理法を形を変えて使っているのだ、と言ってもいいでしょう。

お礼

ありがとうございます。
√2が無理数であることの証明はたくさん見てきましたが、上のような証明ははじめてみました。
ぜひ別解コレクションさせていただきたいと思いました。
偶奇に分けたり、(n^2)/(q^2)≠2の逆数を考えるところがすばらしいアイデアだと思いました。

場合分けをしている時点で、排中律・背理法を使っているということですね。

>[2]qが偶数(2m)でnは奇数(2s+1)であるとき。
>(m^2)(n^2)/(q^2)=(m^2)((4s^2+4s+1)/4(m^2))=s(s+1)+1/4
>だから(m^2)(n^2)/(q^2)は整数ではない。

♯ここも背理法ですかね。(m^2)(n^2)/(q^2)は整数と仮定すると、(整数)=(整数)+1/4となり矛盾するので、(m^2)(n^2)/(q^2)は整数ではない。

>従って、
>(m^2)((n^2)/(q^2)-2)は整数ではない。

♯ここも背理法ですかね。(m^2)((n^2)/(q^2)-2)は整数と仮定すると、(整数)=(整数でない)+(整数)となり矛盾するので、(m^2)((n^2)/(q^2)-2)は整数ではない。

>だから(n^2)/(q^2)-2≠0つまり(n^2)/(q^2)≠2

♯ここも背理法ですかね。(n^2)/(q^2)-2=0と仮定すると、(整数ではない)=(整数)となり矛盾するので、(n^2)/(q^2)-2≠0。

あと、タイプは異なりますが、「平方数ではない自然数の平方根は無理数となる」ことの証明を数学的帰納法と背理法を用いてしているものがありました。背理法を使わないと証明できないことには変わりないようです。
http://tambara.ms.u-tokyo.ac.jp/tsuboi091003.pdfの3ページ目

回答No.7

stomachman

ANo.6へのコメントについて。

　種を明かせば、ANo.6の元になってる証明方法はこれです：
「√2 が有理数であると仮定するならば、既約分数 p/q が存在して
　　(p/q)^2=2
するとp, qは共に偶数でなくてはならない。従って、p/q は既約でない。なので矛盾。」
　初めてこの証明を知ったのは確か小学校高学年の時。「有理数かどうか」という話をしているのに、議論が「既約かどうか」なんて脇道に逸れるのがどうにも気持ち悪く、今ひとつ腑に落ちない気がしたのでした。
　ANo.6の答案は、「既約」というところを「√2 と等しくないと既に分かっている有理数と等しい」に置き換えて帰納法（場合分けの[1]の部分）を使い、場合分け[2]～[4]の部分は単に「(p/q)^2=2だとすると、p, qは共に偶数でなくてはならない」の証明を、あまりあからさまな背理法には見えないような言い回しを使いつつ、いろんなバリエーションで表現してみただけ。つまり、半分冗談です。
　排中律を一切使わないという制約は非常にきついもので、非常に多くの「当たり前」が使えなくなってしまいます。その条件下で何が言えるのかきちんと考えようとすれば、数学の最も基礎の部分から逐一、しかも極めて形式的に（さもないと間違えます）証明を積み上げる地味な作業が不可欠ですから、よっぽど物好き（つまり数学好き）でなくちゃやってらんないですね。しかし、手抜きをしてもある程度のことは言えます。たとえば、
　定義：性質P(x)とは、既知の性質Q(x)を満たさないことを言う。
という定義の仕方は不可である。だから、「有理数でない実数を無理数と呼ぶ」という訳には行かなくなる。「でない」を使わずに「無理数とはどういうものか」を述べる必要があるわけですが、さて、そんなことできますかね。

回答No.5

kabaokaba

＞僕は、証明法の種類とか、別解の存在意義、といったものに興味を持っています。

それなら数学基礎論を勉強したらどうです？
そうすれば背理法がいかに根深いかよくわかるし，
背理法なしで論理を展開することがどうなるか
見えるでしょう．

ちなみに，逆数学っていう基礎論の分野があって
公理をいかに弱めてどこまでの命題が示せるのか，
ある定理を証明するのに最低限必要な公理は何か
みたいなことを「数学的帰納法」をいろいろいじってやってます．
＃いちおういっておくと，数学的帰納法ってのは
＃自然数相手だけではなくって，超限帰納法まで含める．

「ある命題が背理法なしでは証明できない」
ということを証明するには
背理法が存在しない体系からその命題が独立であることを示し
なおかつその体系に背理法を加えたときに
その命題が証明できることを示す必要があります．
逆数学の手法と類似してるかもしれません．

背理法を使わないということは排中律を使わないということで，
これは直観主義論理と呼ばれます．
昔からいろいろ研究されてますので
論理学の本を探せば見つかるとおもいます．

ちなみに・・・
主観では「2^{1/2}は無理数」を背理法なしで証明するのは
できても相当難しいとおもいます．
そもそも実数の構築を背理法なしでできるのか？ということから
考察する必要があるわけで・・・直観主義論理で実数まで構築できるのかなあ，わかんない.

回答No.4

noname#152422

知られている証明でない証明を考える態度は悪くないと思いますよ。

> 「√2が無理数であることは、背理法を用いないと証明できない」ことを「証明したい」という質問に変更します。

無理数は「有理数でない実数」として定義される以上、どうしても有理数と仮定すると矛盾という論法を使わざるをえないことになりそうです。

たとえば（方針だけ）、

√2が有理数であるとすると、連分数展開すれば有限個で止まる（ユークリッドの互除法）。

しかし、実際は1+1/(2+1/(2+1/(2+1/(…))))というように、2が無限に続いて展開が有限個で止まらないので矛盾。

お礼

ありがとうございます。

＞無理数は「有理数でない実数」として定義される

無理数とは、小数展開すると、循環しない無限(位)小数
のように定義しても、やはり、循環や有限といった概念の否定がでてきてしまいます。

そういえば、「素数は無限個」の証明も、背理法を使って矛盾を導くものしか見たことがありません。

また、そもそも最初の質問文では、数学的帰納法・対偶を用いましたが、背理法と対偶は似たようなものでした。
√2が無理数であることを証明するのに、数学的帰納法のみを用い、背理法を用いないという方針であれば、対偶も用いるべきではなかったでした。

僕は、証明法の種類とか、別解の存在意義、といったものに興味を持っています。

回答No.3

tmpname

まずこの方法では無理でしょう。
＊先ず明らかに(p+1)/(q+1)≠p/(q+1),
(p+1)/(q+1)≠(p+1)/q

＊更に(p+1)/(q+1) = p/q => p=qで、
　この時(p+1)/(q+1) = 1で明らかに√2でない。

この事から、
「(p+1)/(q+1)＝√2 ⇒ p/q＝√2、または、
p/(q+1)＝√2、または、(p+1)/q＝√2」は、
（元々矛盾から矛盾を示す命題ではあるものの）
まず示せそうにありません。

もうちょっと一般化して、
「p/q=√2なら、pよりも小さい自然数p', qよりも小さい
自然数q'があって、p'/q'=√2が成り立つ」
事を示す、という方針もありますが、こうすると従来の
良く知られた証明法と大差ありません。

回答No.2

eatern27

「任意の正の自然数nについてn≠0であること」
を数学的帰納法で示すために
1) 1≠0
2) n≠0 ⇒ n+1≠0 (または対偶の n+1=0⇒ n=0)
を証明する、って話と本質的には同じような話でしょうか。

もちろん、証明できるのならその方針で良いのですが、
証明できないのなら別の方針で考える必要があるというだけでしょう。

お礼

ありがとうございます。

2) n≠0 ⇒ n+1≠0 (または対偶の n+1=0⇒ n=0)

の対偶は、n+1=0が成り立たないので、n=0が成り立つ成り立たないに関わらず、真。

質問文も、p＝q√2+√2-1⇒(p/q-√2){p/(q+1)-√2}{(p+1)/q-√2}=0

において、p＝q√2+√2-1が成り立たないので、(p/q-√2){p/(q+1)-√2}{(p+1)/q-√2}=0
が成り立つ成り立たないに関わらず、真。
ただし、p＝q√2+√2-1が成り立たないことを言うには、背理法と同じような論述がいるのですね。

「√2が無理数であることは、背理法を用いないと証明できない」ことを「証明したい」という質問に変更します。

回答No.1

ferien

＞p＝q√2+√2-1
が、ｐが自然数であるという仮定に矛盾すると思います。

＞任意の自然数p,qでp/q≠√2であることを示せばよい。
は、ｐとｑが互いに素の条件も必要なので、
任意の自然数とするのは間違ってると思います。

どうでしょうか？（何で普通に背理法を使わないのでしょうか？）