背理法とは？

質問

背理法について混乱してしまってるので解説をお願いします。

背理法とは命題を否定したものが成り立たないことを証明するのですよね？

ここで疑問なのが逆・対偶・裏から見る命題を否定した裏は命題との真偽が同じになることもありますよね？

それでも証明できるのは背理法と命題・逆・対偶・裏は話が別物で関係ないということですか？

回答No.9

f272 · ベストアンサー

質問者を置き去りにしていろいろと混乱させるのは本意ではないので，この辺でやめておきます。
これだけでは何なので，もう一度「背理法とは命題を否定したものが成り立たないことを証明するのですよね？」に対する回答を書いておきます。
背理法とは命題を否定したときに矛盾が生じることを証明するのです。

お礼

ありがとうございました。

回答No.8

ddtddtddt

#5，6です。

　質問者様へ。もう一回言いますが、あんまり悩まないでくださいね。それから以下のコメントは、数学オタクどうしの与太話としてあんまり見ないで下さい(^^;)。

　形式的数学の記述の構成として、三段論法と命題理論のシェマ，量化子と等号のシェマを認めれば、数学におけるすべての命題は、p⇒q の形の命題の入れ子になるはずです。ここでp，qは、明示公理などの原始命題です。

　Ａが素数全体の集合ならば、Ａの濃度は有限でない。
［証明概略］
　Ａの濃度を有限とすれば、Ａは素数全体の集合でない。何故ならＡに属さない素数がみつかるから。
［証明終］

　で［証明終］の前に、「対偶により題意は成り立つ」と書くか「よって矛盾」と書くかは、どっちでも良いじゃないですか、というのが自分の意見です。自分の応答の趣旨は、「たいがいの背理法や対偶を使った証明は、直接証明のショートカットに過ぎないのだから、あんまり気にする必要はないですよ」です。具体的な証明作業は、背理法でも対偶でも同じになりますよね？。

　ただ素数の濃度の証明は、ふつうの背理法じゃない事は自分もわかります。たぶん背理法でしか証明できない。直接証明しようと思ったら、無限個のケース分けを相手にする事になるから。似た状況が対角線論法だと思います。

お礼

ありがとうございました。

回答No.7

f272

#3です。
「√２は無理数である」の背理法による証明は結局のところ
互いに素な整数n，mで√２＝n/mと表せないならば，√２は無理数である。
の対偶をとって
√２が有理数であるならば，互いに素な整数n，mで√２＝n/mと表せる。
を証明しているのであって，これは実質的に対偶証明法であることはその通りです。
しかし，有名な素数は無限に存在するの背理法による証明は
素数は有限個しかないと仮定すると
すべての素数を掛け合わせた数に1を加えた数Nを考えると，Nはどの素数とも異なるので合成数であるが，Nはどの素数で割っても1余るので素数となる。これは矛盾している。
というものです。これを対偶証明法っぽく書き直すことは私にはできません。こういうのが純粋な背理法なのではないですか？

お礼

ありがとうございました。

回答No.6

ddtddtddt

#5です。

　すいません間違いました。
＞p et ～q 証明する事と、p ⇒ q の対偶を証明する事は同じ・・・

ではなく、
　　・(p et ～q) の否定を証明する事（矛盾を導くのと同じ）と、p ⇒ q の対偶を証明する事は同じ・・・

でした。こういうのは不要な誤解と混乱につながりますね。ごめんなさい。

　・・・というわけで、証明にかかってみればわかりますが、具体的にやる事は背理法であろうと対偶法であろうと変わりません。

お礼

ありがとうございました。

回答No.5

ddtddtddt

#2です。否定を～，またはをou，かつをetで表します。
(p et ～q) ⇔ ～(～p ou ～～q)
⇔ ～(～p ou ～(～q))
⇔ ～(～(～q) ou ～p)
⇔ ～(～q ⇒ ～p)
～(p et ～q) ⇔ (～q ⇒ ～p) ⇔ (p ⇒ q)

　p et ～q 証明する事と、p ⇒ q の対偶を証明する事は同じである事が、まさに対偶によってわかります。どこが違うんですか？。

　「√２は無理数である」の証明はけっきょく、
　　・√２ならば互いに素な整数n，mで√２＝n/mと表せない．
を証明しただけじゃないんですか？。それが無理数になるのは、無理数はそういうものだと定義したからじゃないんですか？。

　あえて言いますが、ここではそういう下らない区別はやめませんか？。確かに命題理論の中で背理法と対偶関係の立ち位置は違いますが、ここでそんな話が必要ですか？。むしろ不要な誤解や混乱を招くだけと思えますが。

　命題理論そのものの話をしてる訳じゃないんですから。

お礼

ありがとうございました。

回答No.4

kiha181-tubasa

ＰならばＱを証明するのに，この命題の対偶
　ＱでないならばＰでない
を証明するのも背理法といえます。

　しかし，「ならば」でつながれていない命題でも直接正面から証明できない場合背理法が用いられます。これは対偶ではありません。
　そのような命題の典型的な例で教科書などに出ているのでは
　「√２は無理数である」の証明があります。

　大体以下の流れです。

√２が無理数でないつまり有理数だとすると
√２=n/m （m, nは互いに素(１以外の公約数を持たない)な正の整数）
と表せる。この両辺を平方すると
２=n^2/m^2
2m^2=n^2
これからn^2は２の倍数である。nが奇数とするとn^2も奇数となってしまうので，nは偶数である。つまり２の倍数。
よって n=2k (kは正の整数)と表せる。
ゆえに
2m^2=4k^2
m^2=2k^2
これからm^2が２の倍数なので，mも２の倍数となる。
よって，m, nともに２の倍数となる。
これは，m, nは互いに素(１以外の公約数を持たない)ことに矛盾する。
ゆえに，√２=n/m （m, nは互いに素(１以外の公約数を持たない)な正の整数）
と表すことはできない。つまり，√２は無理数である。

という証明です。

お礼

ありがとうございました。

回答No.3

f272

元の命題が「PならばQ」のとき
逆は「QならばP」
裏は「￢Pならば￢Q」(￢は否定の意味です)
対偶は「￢Qならば￢P」
です。そして元の命題の真偽と対偶の真偽は一致しますし，逆の真偽と裏の真偽は一致します。元の命題の真偽と裏の真偽は一致することもありますが一致しないこともあります。
背理法と命題・逆・対偶・裏は話が別物で関係ありません。
背理法とは，元の命題の否定して矛盾を導くことで証明とする方法です。実質は対偶を利用した証明法と勘違いしている人も多くいますが，実際には違います。もちろん対偶を利用してもいいのですが，そうであるとは限りません。背理法では矛盾を示すことが目標です。
例えば，有理数p，qについてp+q√2=0ならばp=q=0であることを証明するとき，背理法では「p+q√2=0ならばp=q=0」を否定します。言い換えると「(p+q√2=0)かつ(p=q=0でない)」と仮定します。
p=q=0でないというのはq≠0の場合とp≠0かつq=0の場合に分けられますが
q≠0の場合は，p+q√2=0から√2=-p/qとなって矛盾します。
p≠0かつq=0の場合は，p+q√2=0からp=0となって矛盾します。
どちらの場合にも矛盾することが示せましたから，証明終わりです。
対偶を使った証明では「(p=q=0でない)ならば(p+q√2≠0)」を証明することになります。だいぶ違いますよね。

お礼

ありがとうございました。

回答No.2

ddtddtddt

裏と逆の定義は、あんまり注意して読んだことがないのですが、これで良いですか？。否定を「～」で表します。

逆：
　p ⇒ q の逆は、q ⇒ p。
　※ p ⇒ q が成り立っても、q ⇒ p がいつも成り立つとは限らない。

裏：
　p ⇒ q の裏は、～p ⇒ ～q。
　※ p ⇒ q が成り立っても、～p ⇒ ～q がいつも成り立つとは限らない。

　そして対偶ですが、
対偶：
　p ⇒ q の対偶は、～q ⇒ ～p。
　※ p ⇒ q が成り立てば、～q ⇒ ～p は必ず成り立つし、
　※ ～q ⇒ ～p が成り立てば、p ⇒ q は必ず成り立つ。

　それで対偶の事を、
　　(p ⇒ q) ⇔ (～q ⇒ ～p)
と書くこともあります。「⇔」は同値の意味です。
　p ⇒ q を証明したいなら、p ⇒ q を直接証明しても良いし、～q ⇒ ～p を証明して間接的に p ⇒ q を証明した事になっても良い、です。

　背理法ですが、なんかいかめしく証明が書かれちゃうのですけど、実質は対偶を利用した証明法です。

背理法：
　p ⇒ q を証明したい。
　～qを仮定する。
　すると～pを導ける。
　よって、～q ⇒ ～p を証明してしまった。
　これは、p ⇒ q を証明したのと同じ。

という論法です。背理法は多くの場合、直接証明のショ－トカットとして利用されます。例えば直接証明するには、pの場合分けが多くて面倒臭い場合です。この時、～q を仮定するだけで、pの場合分けの全部が一発でOUTになる事がわかれば、証明が省力化されますよね？(^^)。

　ちなみに p ⇒ q の裏の対偶をとってみると、
　　(～p ⇒ ～q) ⇔ (～～q ⇒ ～～p) ⇔ (q ⇒ p)
となり、p ⇒ q の裏は逆と同じです。ただし二重否定はもとに戻ると使いました。
　　http://www.geisya.or.jp/~mwm48961/kou3/gyaku.htm

　こういうのは一種の「代数」だと思って、実用的にはあまり悩まない方が良い気もします。

お礼

ありがとうございました。

回答No.1

chie65535

＞背理法とは命題を否定したものが成り立たないことを証明するのですよね？

微妙に違います。

「命題を否定したものが成り立たないことを証明する」ではなく「命題を否定すると矛盾が起きる事を利用して命題が成り立つ事を証明する」です。

＞それでも証明できるのは背理法と命題・逆・対偶・裏は話が別物で関係ないということですか？

背理法と待遇証明法は「異なる証明方法」です。混同してはいけません。

http://media.studytown.jp/contraposition-proven-method-and-reductio-ad-absurdum/

「背理法」とは「○○はPである」と言う命題があるとき「Pでない」と仮定した場合に起きる矛盾を見つけて「Pである」ことを証明する方法です。

偶証明法とは「PならばQ」を直接証明することが難しい時「対偶が真なら命題も真」であることを利用し「QでないならばPでない」ことを証明する方法です。

お礼

ありがとうございました。