背理法

2つ聞きたいことがあります、よろしくお願いします。
P→Qで
(1)背理法と命題の否定(P⊂Qの否定)が偽であることを証明することは同じことなのでしょうか？
(2)背理法で証明する場合、Q(バー)と仮定するが、P(バー)を仮定するとなぜだめなのでしょう？

よろしくお願いします。

No.3 回答者： quantum2000 回答日時： 2005/03/05 14:12

Ｐ→Ｑ の証明において，

（１）背理法と命題の否定(Ｐ⊂Ｑの否定)が偽であることを証明することは同じこと？ について

「背理法」は一般的には，
　　「Ｑでない」（Ｑの否定）から矛盾を導き出し，だから「Ｑである」
と証明する方法なわけです．

ここで正確には，
　　命題「Ｐ→Ｑ」とは，「Ｐが成り立つときは，いつでも必ず，Ｑも成り立つ．」
という意味であり、「背理法」も正確には，
　　「Ｐが成り立っているのに，Ｑが成り立っていない場合が（１つでも）あるとすると，
　　　それから矛盾が起きるから，
　　　Ｐが成り立つときは，いつでも必ず，Ｑも成り立つ．」
として，命題「Ｐ→Ｑ」を証明するものです．

これを集合で表現し直すと，
　　　Ｐ⊂Ｑ でないとすると，おかしなことが起きるから，Ｐ⊂Ｑ である
となります．

一方，質問者のdekorute1010さんが書いている，
　　命題「Ｐ→Ｑ」の“否定”が「偽」であること ・・・（Ａ）
を証明することは，集合で表現すると，
　　条件「Ｐ⊂Ｑ」の否定が「成り立っていない」こと ・・・（Ｂ）
を証明することですから，「背理法」と同じ感じになりますね！

しかし一般的には，（Ａ）や（Ｂ）を証明するのには，必ずしも「何かの矛盾を導く」必要はないので，まったく「背理法」と同じ，とは言えないのではないでしょうか？

（２）背理法で証明する場合、Ｑ(バー)と仮定するが、Ｐ(バー)を仮定するとなぜだめなの？ について

「背理法」は，「Ｑでない」としたときに，どんな矛盾でもよいからとにかく１つおかしいこと（矛盾）を示せれば，証明できたことになります．ですから極端な場合は，Ｐを仮定しなくても（「Ｐである」ことを使わなくても）矛盾が出せれば，証明はできる訳です．

ただ普通はＰを使わないと矛盾は出せませんから，「Ｐ→Ｑ」を背理法で証明するに，￢Ｑ（Ｑの否定）は仮定しますが、（Ｐは使いますから，）￢Ｐ（Ｐの否定）の方は仮定しません．（￢Ｐまで仮定してしまったら，Ｐかつ￢Ｐより，いつでもすぐに矛盾が導けてしまい，どんな命題も証明できることになってしまいますから！）

なお，￢Ｑからは結果的には￢Ｐが出てきます．（「￢Ｑ → ￢Ｐ」は，「Ｐ→Ｑ」の対偶になっていますので．）

No.2 回答者： shkwta 回答日時： 2005/03/04 21:41

No.1補足への回答です。

＞背理法と命題の否定(P⊂Qの否定)が真であることを証明することは同じことなのでしょうか？
(￢(P→Q))⇔(P∧(￢Q))ですから、「命題の否定(P⊂Qの否定)が真であることを証明する」とはPを証明し、かつ(￢Q)を証明するということと同じです。背理法の定義は((P∧(￢Q))→(￢P)) または　((P∧(￢Q))→O)を証明することですから、全く異なります。

＞証明部分がいまいちわかりません、どういうことでしょうか？
Sを適切な命題として、((￢P)→S)を証明したら(P→Q)を証明したことになるためには、
(((￢P)→S)→(P→Q))
が恒真命題(P, Qの真偽に関係なく真となる命題）になるSを見つける必要があります。ところが
(((￢P)→S)→(P→Q))
⇔((P∨S)→((￢P)∨Q))
⇔((￢(P∨S))∨((￢P)∨Q))
⇔(((￢P)∧(￢S))∨(￢P)∨Q)
⇔((￢P)∨Q)
⇔(P→Q)
となって途中でSが消え、証明するべき元の命題に戻ってしまうため、恒真命題を作れません。

同じことを、集合のベン図で考えます。
全集合Cの部分集合P,Q,Sを考えます。P,Q,Sとその捕集合から作られる共通部分
(補集合を~で表わします）は次の８つがあります。
ア P∩Q∩S
イ P∩Q∩S~
ウ P∩Q~∩S
エ P∩Q~∩S~
オ P~∩Q∩S
カ P~∩Q∩S~
キ P~∩Q~∩S
ク P~∩Q~∩S~

命題P⊂Qは、ウとエが空集合であることを主張します。一方、命題P~⊂Sは、カとクが空集合であることを主張します。両者が空集合だと主張する領域は全く重なりませんので、一方からもう一方を導くことはできません。

わかりにくい部分があれば補足してください。

No.1 回答者： shkwta 回答日時： 2005/03/04 06:55

バーを表示できないので、Pの否定を　￢P で表わします。

＞(1)背理法と命題の否定(P⊂Qの否定)が偽であることを証明することは同じことなのでしょうか？

「命題の否定(P⊂Qの否定)が偽であることを証明する」というこの文を文字通り解釈すれば、P→Q を証明する代わりに　￢￢(P→Q) を証明する　と言う意味になります。これは「元の命題 P→Q を証明する」というのと同じです。つまり、背理法を使うか使わないかに関係がないので、(1)は《背理法の説明》としてはまずいです。

証明は、ある仮定があって、そこから結論を導きます。つまり条件文 A→B が真であることを示します。これは背理法でも同じで、条件文が真であることを証明します。背理法では、元の命題P→Qの代わりにアまたはイを証明します。（∧はand, ∨はorを示します）

ア　(P∧(￢Q))→(￢P) を証明する。
イ　(P∧(￢Q))→O を証明する。Oは、公理または定理に反する命題です。

アもイも、次に示すようにP→Qと同値ですので、アまたはイを証明すればP→Qを証明したことになります。
(P∧(￢Q))→(￢P)
⇔(￢(P∧(￢Q)))∨(￢P)
⇔((￢P)∨Q)∨(￢P)
⇔(￢P)∨Q
⇔(P→Q)

(P∧(￢Q))→O
⇔(￢(P∧(￢Q)))∨O
⇔((￢P)∨Q)∨O
⇔(￢P)∨Q
⇔(P→Q)

※ （A→B)⇔((￢A)∨B), (￢(A∧B))⇔((￢A)∨(￢B)) を使っています。

(2)背理法で証明する場合、Q(バー)と仮定するが、P(バー)を仮定するとなぜだめなのでしょう？
・上でも説明したように、背理法で証明する場合はP∧(￢Q)を仮定します。
・￢Qを仮定して￢Pを導くのは対偶法です。
・￢Pを仮定して何か結論が出てきても、P→Qを証明したことにはなりません。なぜなら、(￢P)→S という形の条件文で、P→Qと同値のものは作れないからです。

この回答への補足

(1)について、背理法と命題の否定(P⊂Qの否定)が真であることを証明することは同じことなのでしょうか？
に訂正します。この場合どうなるのですか？
(2)について、できないことは、感じていましたが、図で表現しようとしてもなかなか証明できないので、質問してみました、それと、証明部分がいまいちわかりません、どういうことでしょうか？

補足日時：2005/03/04 10:29