真である全ての命題は、背理法を使って証明できる？

19

命題: P=NP
(�@) P≠0ならば両辺を0で割ればN=1のときのみ成立することがわかる
(�A) P=0ならば任意のNについて成立する

こんな問題もわからねーの？

>>108
(i)がどうにも納得し難いな

>>109
禿同
｢両辺を0で割れば〜｣って…

命題Aを証明しますた
背理法を使って証明するには
命題Aが成り立たないとかていすると
命題Aがなりたたないので
公理に反する
■

◆オナニーランド　無料です◆
http://endou.kir.jp/akira/linkvp.html

あれだろ

あれだな

なんだろ
あれか？

　　　　 。。 　
　　　。　 　　　。　+ 　 ヽヽ　　なに言ってんだよ
゜　。・　。　+゜　　｡･ﾟ　(;ﾟ｀Дﾌ。　うわぁぁぁん
　　　　　　　　　　　　ノ(　/
　　　　　 　 　 　　　　/ >

命題: P=NP
P(N-1)=0であるので、零因子が無いとすればP=0であるかN=1でなければならない。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　∩　　　　　　　.'　　，
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　⊂､⌒ヽ　　　.∴　'
　　　　　　　　　　　　　　　　 ＿＿＿＿＿＿＿＿＿＿＿＿__ 　　　　　　　　　　　　　　　　　⊂（　｡▽｡）つ←>>117
はっはっは・・・　　　　　　/ヘ;;;;;────　/ ,──ヽ-─-- ヽ 　　　　　　　　　　　　　　　　　　Ｖ　Ｖ
見ろ！　　　　　　　　　,／';=r=‐ﾘ　　　 　 //　　　　 ||　　　|| ヽヽ 　　　 　　　　　　　　　　 ';*;∵
人がゴミのようだ　,／　　ヽ二/　　　　 //　　　　　 || 　　 ||　 ヽヽ 　　　　　　　　　　　 ・.;,;ヾ∵..:
　　　　　　　　＿_∠_＿⊆⌒⊆___）＿_//　ニ）＿＿_||＿＿||＿ノ　ゝ__　　　　　　　　 :,.∴　'
　　　　　　／　　　　　￣￣￣_　＿／　　　|　　　　　　|　　　　　　|　　　 ヽ　　　∴　';*;∵; ζ。∴
　　　　／/ ＿＿Ｃ＿＿　　 ／￣ ﾉ　　　　|　　　⊂⊃|　　⊂⊃ /　　ロ /| 　　　　　　.∴'　
　　　/ /-/＝＝＝＝／-／＿_ ﾉ＿＿　　|　　　　　　|　　 　　 /____＿/__|_ 　　　 _　　　　 :,　.∴
　　 |￣　└[と2003]┘　 ￣￣ 　 ／;;;;;;;ヽ |　 ￣￣￣|￣￣ ／;;;;;;;;ヽ 　　 ﾉ 三三三三:,　.
　　 |二)　 └──┘ (二二)__|＿|:（∴）:|__|＿＿＿___|_＿＿|:（∴）:|____ﾉ三三三　:,　.
　　 ￣￣ゞゝ;;;;ノ￣￣￣￣　　 ゞ_ゝ:＿ノ　　　　ゞ;;;;;;ノ 　　 ゞゝ:＿ノ 　　　三三
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣

>117 でどっちなんだ？

>>119
なにが？

>>120
P=0 か N=1 かってことだろう。
で、Pは Polynomial 、N は NOn-deterministic だから共に成立
しない。よって P=NP は成立しない、が結論。
もともと、2つの命題の同値性の問題だから、P≡NP って式を解く
べきだろう、ってんでどうだ。

＞もともと、2つの命題の
命題ちゃうで

http://homepage.mac.com/hiroyuki44/jaz04.html

>>122
うーん、確かにちゃうな、
∀n(P(n) ≡ NP(n)) こうか?
そうすると関数方程式とみて、 P = NP でいいか?

　　　 　∧＿∧　 ∧＿∧
ﾋﾟｭ.ｰ　（　 ・３・） (　　＾＾ ） ＜これからも僕たちを応援して下さいね（＾＾）。
　　＝〔~∪￣￣￣∪￣￣〕
　　＝ ◎――――――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉&ぼるじょあ

おれには行列の問題に見えるが、、、

　　　 (⌒V⌒)
　　　│ ＾ ＾ │＜これからも僕を応援して下さいね（＾＾）。
　　⊂|　　　　|つ
　　　（＿）（＿）　　　　　　　　　　　　　　　　　　　　　　山崎パン

8

そもそも、背理法という証明法そのものは正確なのですか？
つまり偽である命題を背理法で真であると証明しようとしたとき、
矛盾は絶対に見つからないのでしょうか？
また、そのことは証明されているのでしょうか？

＃ここまで書いて気づいたのですが、「偽である命題を背理法で証明しようとして
　矛盾が見つかれば背理法が正しくない」というのも背理法に基づくものですね。
　何となくパラドックスの予感。

久しぶりにブルーバックスから出ている現代数学小辞典を見た。

ブラウエルの直観主義（背理法を使わない）では、Wierstrass の最大値
最小値定理を断念しないといけなくなる、って書かれていた。

背理法を使わない立場で、数学はどの辺まで進めることが出来るの？

小学生の頃、クラスにＷさんという女子がいた。彼女は先天的な病で体がただれていて、声もうまく発声できなかった。
大人しい子でいつも本を読んでいた。
男子の友人はいなかったが、女子の友人は不思議と多いようだった。

修学旅行で旅館に泊まった時、友人が女子の部屋に遊びに行こうと言い出した。
俺も同意して、どうせだからこっそり行って驚かせてやろうってことになった。
そしてクラスで一番人気のあった女子のいる部屋に行く事となった。
こっそりドアを開けると（どのように鍵を開けたかは忘れた）恐ろしい光景が。

体育座りで座り込むＷさんを円になって囲むようにクラスの女子全員が立っていた。
そして、Ｗさんに対して「豚」「焼けど野郎」などと罵声を浴びせていた。
さらにクラスで最もかわいかった子が「じゃあ、カツラはずしまーす」と笑いながら言ってＷさんの頭に手を伸ばした。

次の瞬間、Ｗさんの髪の毛が全部その女の手にあった。Ｗさんは頭皮も病気で、髪の毛が生えないためカツラをしていたのだ。
男子は誰もそれを知らなかった。ショックで何が何だかわからない俺の前で女子はＷさんを蹴飛ばしたりカツラをライターであぶったり。
Ｗさんはかすれた声でうめく。助けを呼びたくても呼べないのだ。
俺と友人は無性に怖くなって見つからないように逃げた。

次の日、Ｗさんもクラスの女子も何事も無かったように京都を観光していた。
それが一番怖かった。

時がたって同窓会が開かれた。Ｗさんはすでに亡くなっていた。
俺は思い切って女達に修学旅行でのことを聞いてみた。
すると例の一番かわいかった女の子が「あんなの別に死んだっていいじゃん」といった。

このスレの趣旨とはちょっと違うかもしれないが、これが俺の経験した最も怖い話です。

>>129
「つまり・・・」以下が良く分からないが、
排中律から出るんじゃないの？

背理法はある強い（一般には複数の）前提条件と生贄とする
（否定したい）命題Xを仮定すると強い前提条件の否定が出てくる
ので、Xを拒否する方法。
例えば√２が有理数であるという命題をPとし、有理数は既約分数で
表されるということと既約分数には互いに素であるという２つの命題
をA,Bとすると、P&A&B＝＞~Bが出てくるのでpが拒否されるということに
なる。この時~Pは強い命題（定理）の仲間に入れる。こうして定理を
増やしていくプロセスが背理法。ある意味、仲間外れ法かも知れない。
強い命題をＱ、否定を証明したい命題をＰとおいた時
Ｑ＆（Ｐ＆Ｑ=>~Ｑ）＝＞~Ｐは命題論理レベルでは恒真な式であるが、
背理法を数学の証明として正当なものとする根拠となっているが。
>>131の女の子も、ある種の背理法でいじめられたのかも知れない。
となると背理法を駆使する数学というのは、女性的陰湿さとは縁が深い
のかも知れない。陰湿な背理法を使わずに済ます表現方法はある。
「任意の有理数が既約分数で表されなおかつ、√２が有理数である
ことは両立しない」というような表現を取るほうがいいのかも知れ
ない。

前提１　p　⇔　q
前提２　not q　⇔　r
目的　Ｘ　が　ｒ　であることを示す
背理法
　Ｘ　が　p　であると仮定する　ならば　矛盾
　よって　Ｘ　は　not q　∴　Ｘ　は　r　である
背理法の対偶論法
　Ｘ　が　p　でないならば　矛盾はない
　よって　Ｘ　は　not q　∴　Ｘ　は　r　である

…自明じゃ駄目？

対偶論法はちょっと違うな…。
すまん忘れてくれ…。

あほな高校生です。
「√２が無理数である」ことを証明する背理法の論法に違和感を覚えてます。
背理法とは、「結論を否定を仮定して、もとの仮定に矛盾を生じさせる論法」
すなわち、対偶命題の証明で元命題が真であることを示す論法。
と聞いているのですが「√２が無理数である」という命題のどこが仮定の部分
なのか、（ひょっとして「√２が実数であるとわかっているときに」という隠
された仮定が存在するのか←でも、論法ではこれに矛盾していない）
結論の否定を仮定して、結論に矛盾を生じるような論法を背理法というのか？
既約分数にならないからといって、約分する前の分数になる可能性はないのか？
すべての有理数は既約分数で表現できることは証明不要なのか？
どなたか教えてくださ〜い。

＞すべての有理数は既約分数で表現できることは証明不要なのか？
　
厳密にいえばこれは必要だな。
　
＞背理法とは、「結論を否定を仮定して、もとの仮定に矛盾を生じさせる論法」
＞すなわち、対偶命題の証明で元命題が真であることを示す論法。
　
これはどうだろう？オレ的には背理法とはP⇒Qを証明するためにそれと同値な
P＆notQ⇒⊥（⊥は矛盾の意)を証明することだと解釈してるけど。
｢P⇒Q｣と｢P＆notQ⇒⊥｣が同値であることはこだわるタイプのひとにとっては
結構納得しづらいかもしれない。大学はいって論理学の授業があったらそこでは
おしえてもらえるし記号論理学とかいてある教科書にはのってるので独学できないでも
ないが瑣末なもんだいなので伊藤家風にいえば｢なるものはなる｣でとりあえずあとまわし
にしとけ。

バカ院生が集まる部屋というのはここですか？

>>136
> と聞いているのですが「√２が無理数である」という命題のどこが仮定の部分なのか

アホか? 自分で「結論の否定を仮定して」と書いてる意味が分からんのか?

>>139
言葉が足りませんでした。

元命題の仮定の部分はどこですか？

という意味です。

そもそも>>136は背理法が正しいことを納得していないように思うのだがどうか

>>136
その方針でやるのは、無矛盾性の反例を出そうとするやり方。
つまり強背理法であり、その方法である命題の証明に成功したと同時に
その命題を含む体系全体の信頼性が極度に低下するのでかなり破壊的な
方法です。
数学でそれをやろうとするのはかなり勇気が必要、というか今まで成功
した奴はそう居ないでしょう。
自分で強背理法であると思っていても、実はそれはもろにそれは普通の
背理法だったりすることが殆どです。

>>137
>>142
いろいろ説明いただきありがとございます。

>>141
背理法が正しいことは納得しています。

「√２が無理数であることを証明せよ。」
という問題は、教科書の命題と集合という単元で、先に述べた
背理法の説明
「元命題の仮定を否定して、元命題の仮定に矛盾を生じさせる論法」
の後に載っています。
そこで、この問題（命題）の仮定の部分を考えたのですが、
よくわからないので変だと思いました。

数学やそれを対抗的基礎にしている古典論理では、古
い時期に確信された命題の否定を生じさせた場合、自
動的に新しい命題が棄却されるという推論システムを
取っているわけで、
>元命題（証明すべき新しい命題）の仮定を否定して
>元命題の仮定に矛盾を生じさせる
というのは、新しい命題が自己矛盾をしている
というのを示す意味に取れるんだが、これは違う。これは
背理法でも何でもない。
背理法は新しい命題と古い命題が両立しないので、古く
信頼出来る命題を残して新しい命題を棄却するという原理

有理数でないなら無理数である

無理数でないなら有理数である

有理数であるなら無理数でない

無理数であるなら有理数でない

>>143
納得していないのとはちょっと違うのかな。
教科書の説明が一般性を欠いていると思う。
背理法による命題Pの証明とは
「命題Pが偽とすると矛盾が出るから、Pは真である｣
というもので、その教科書の説明はPがQ⇒Rの形の場合にあたる。

一般のPも" ⇒P"と解釈すればいいといえばそうなのだが、
それじゃ逆に分かりにくいだろうね。

命題Pを否定を決定するのに、

弱い背理法：
（既に証明された）任意の真である（とされた）命題Qに対し、Q&Pが偽である
ことを示す方法。日常世界の論理はこれに近い。

強い背理法：
（既に証明された）ある真である（とされた）命題Qを用いてQ&Pが偽である
ことを示す方法。数学では一般に強い背理法が使われる。
法治国家・官僚の論理はこれに近いものがある。

矛盾法：P&(~P)が真であることを証明する。その体系に真である命題集合が存在
しようがしまいが無関係。排中律よりこの命題P自体が真偽決定不能として
排除される体系が多い。普通の数学はこの立場を取る。よって数学では矛盾法が
使われることは滅多に無い

普段やってるような形式的でない推論が無矛盾でないと仮定する。
矛盾。
よって仮定は否定され、形式的でない推論は無矛盾である。
こんな背理法は嫌だ。

>>151
ﾜﾗﾀ
それはとても嫌だ

「真である全ての命題は、背理法を使って証明できる」→偽
反例：「背理法を使って証明した事柄が正しい」ことを
　　　　背理法を使って証明するのは不適切

Q：背理法による証明が正しいことを証明せよ.

A1：まず,結論を否定してみる
「背理法による証明は正しくない」
ところが,いまやろうとしている証明は背理法を使おうとしている
ので正しくない.よって仮定である「背理法による証明は正しくない」
は正しくないことが示されたので,証明が終了する.

「真である全ての命題は、背理法を使って証明できる？」

存在そのものが矛盾です。


数学は、矛盾がでたらそれを切り捨てることから始まってます。
矛盾なので数学に含めません。

完了

15