背理法と対偶って違うの？

背理法と対偶って違うの？ (117ﾚｽ)
上下前次1-新
通常表示 512ﾊﾞｲﾄ分割ﾚｽ栞
抽出解除必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞あぼーん

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

49: １３２人目の素数さん [sage] 2024/11/28(木) 15:44:20.86 ID:XCAq3thN

メモ
<chiebukuro.yahoo>背理法
（なお　az1********さんにほぼ賛成。hat********さんの 回答は首肯できる部分は多いが 同意できない箇所も多くある。）
detail.chiebukuro.yahoo.co.jp/qa/question_detail/q14224170274
質問
jcg********さん 2020/5/2
対偶を用いた証明と背理法は本質的に同じものなのに、高校数学ではなぜこれらを区別して教えるのでしょうか。
A⇒Bにおいて、対偶では￢Ｂ⇒￢Ａが、背理法では￢(Ａ⋀￢Ｂ)が真であることを示すとよく言われます(?)が、￢Ｂ⇒￢Ａで示すことはＡ⋀￢Ｂ⇒Ａ⋀￢Ａ⇔Ｆ∴(Ａ⇒Ｂ)⇔￢(Ａ⋀￢Ｂ)⇔Ｔで背理法で示しているのと同じことです。しばしば⇒の無い証明では対偶をもちいて証明できないので背理法を使うとされますが、十分条件が恒真命題であるだけで本質的に区別されるものではないと思います。インターネット上にはこれら2つの証明の違いを分かりやすく解説することを銘打ったサイトがたくさんありますが、言葉の上で「対偶を取って」とか「仮に〜とすると〜矛盾する」とかいう定型句を挙げて分かった気にさせているものしかありません。私が誤解している可能性も否定できませんが、高校数学を教えている人のほとんどが論理を理解していない気がします

回答（7件（うち2件抜粋））
az1********さん
2020/5/2
「対偶を用いた証明と背理法は本質的に同じもの」というのは理解できませんが
本質的にどうかという話ではありません。本質ではなく実用の話です。初学者が
数学の証明を獲得していく過程で出会うものです。教育の話です。

p→qという命題を証明するのに
(1) 直接p→qを証明する。pを仮定しqを示す。
(2) 対偶による証明 ￢q→￢pを示す。￢qを仮定し￢pを示す。
(3) 背理法 p⋀￢q→φ pと￢qを仮定し矛盾を出す。

(1)なら使えるのはpだけ、(2)なら使えるのは￢qだけ、(3)なら使えるのはpと￢q
単純に言えば(3)なら使えることが多いから普通は楽でしょということです。
もちろん使えることが多いとわけわからなくなるとかもありますが。

背理法と言えばこれというような古典的な例を出します。
x^2=2ならxは無理数である。
普通に勉強した高校生ならこれを背理法で証明するのはできるでしょう。
これを対偶を使って証明できる高校生はあまりいないと思います。

(1)でうまくいかなかったら(2)や(3)もありますよ。
いろいろやってみて下さい。難しそうな問題は(3)かな。
というようなことだと私は思っています。

hat********さん
2020/5/3 13:01
対偶による証明と背理法による証明は異なります。
その違いは「二重否定の除去」を認めるか否かにあります。

二重否定の除去を認める、古典論理の体系では、対偶と背理法はどちらも利用でき、論理的には等価です。
二重否定の除去を認めない、直観主義論理の体系では、対偶は使えません。また、私たちが「背理法」と呼んでいるものは実は2種類あるのですが、直観主義論理では、片方の背理法だけが使え、もう片方の背理法は使えません。

つづく

http://rio2016.5ch.net/test/read.cgi/math/1730979839/49

50: １３２人目の素数さん [sage] 2024/11/28(木) 15:44:44.36 ID:XCAq3thN

つづき

論理の体系について簡単に説明します。

・命題A,B,C,…という概念があります。
高校数学や大学の初等数学では「命題：真偽がはっきりしているもの」と教わりますが、この定義は不満足です。命題とは何かをまだ定義していないのに、真偽とは何かを定義できるはずがないからです。
難しい話は避けますが、ここでは「命題：数学記号や日本語が正しい文法で書かれていて、
自己言及（「この文章は偽です」など）といったやっかいな問題をはらんでいない文章」としましょう。

・論理記号として、⇒、⇔、∧、∨の記号が定義されており、
A∧B ⇔ B∧A
A∨B ⇔ B∨A
(A⇒B)∧(B⇒A) ⇔ (A⇔B)
A∧(A⇒B) ⇒ B
(A⇒B)∧(B⇒C) ⇒ (A⇒C)
などといった性質が成り立つものと定義されています（上が全てではありません。詳しくは省略）。

・命題A,B,C,…と同列の概念で、「矛盾」という命題⊥が存在します。
⊥はA,B,C,…同様に、上の⇒、⇔、∧、∨の性質に当てはめて使うことができます。
また、⊥だけにしかない性質として、
⊥⇒A（Aは任意の命題）
が成り立つものと定義されています。矛盾からは何でも導けるってやつです。

・矛盾を定義したあとで、ようやく「否定」を定義します。
Aの否定¬Aを、「A⇒⊥」の省略表記として定義します。
証明は省略しますが、次の定理が成り立ちます。
?A∧¬A ⇒ ⊥
?(A⇒B) ⇔ ¬A∨B

なお、上のように¬記号を定義することを、「否定導入」といいます。

「否定導入」は「狭義の背理法」とも呼ばれます。
「ある命題Aが成り立つと仮定して、いろいろ式変形してみたら、B∧¬B（Bは何か別の命題）が証明されちゃった。
よって A ⇒ B∧¬B ⇒ ⊥であり、A⇒⊥が証明された。
これは¬Aの定義なので、¬Aが証明された。」
という形で、私たちがよく「背理法」と呼んでいた証明が正当化されるのです。
ただし、後で述べるように、これは2種類ある背理法うちの1種にすぎません。

ここまでは直観主義論理でも古典論理でも同じです。

さて、次の主張は、ここまでの定義や定理を使っても証明できません。

・二重否定の除去
?¬¬A ⇔ A

日常世界では誰もが当たり前のように使っている「否定の否定＝肯定」ですが、論理学の中では自明なことではないのです。
これを認めるか認めないか（公理に入れるか入れないか）によって、立場が別れます。
直観主義論理では二重否定の除去を認めず、古典論理では二重否定の除去を認めます。

つづく

http://rio2016.5ch.net/test/read.cgi/math/1730979839/50

51: １３２人目の素数さん [sage] 2024/11/28(木) 15:45:09.56 ID:XCAq3thN

つづき

対偶について説明します。
略す

2種類ある「背理法」とはなんぞや、について説明します。
「A⇒⊥である。よって¬Aが成り立つ」これは「否定導入」または「狭義の背理法」といい、どちらの論理体系でも使えるのでした。
一方で、
「¬A⇒⊥である。よってAが成り立つ」これはどうでしょう？
この方法は「否定導入」に加えて「二重否定の除去」を利用する必要があるため、一般に直観主義論理の立場では使えません。こちらを「広義の背理法」といいます。
高校数学は当然古典論理の立場なので、2種類の背理法を区別する必要はなく、どちらも単に「背理法」と呼んでいました。
しかし論理学の中では、使い分けに注意が必要です。論理学の中で単に「背理法」と言った場合、「否定導入」のみを指すのか、「広義の背理法」も含めるのか、予め断っておかないと誤解を招く可能性があります。いっそ「背理法」という言葉自体使わないことにして「否定導入」や「二重否定の除去」だけで用語を統一するのも手です。

まとめると、次のようになります。
古典論理→否定導入（狭義の背理法）、広義の背理法、対偶、全部OK。
直観主義論理→否定導入（狭義の背理法）のみOKで、広義の背理法や対偶はNG。

ここで例題。高校数学の有名な問題に、「√2が無理数であること」の「背理法」による証明がありますね。
「有理数だと仮定したら、「整数aが2を素因数に持つ」「整数aが2を素因数に持たない」の両方が成り立つ、よって矛盾」というやつです。
この証明はどっちの「背理法」でしょうか？

答は「狭義の背理法」すなわち「否定導入」です。
そもそも無理数であることの定義が「有理数でない」すなわち¬「有理数である」という形です。
「有理数である」と仮定して矛盾を導き、よって¬「有理数である」と結論づけるのは、否定導入です。二重否定の除去は使っていません

略す

以下、コメント返し。

> A⇒Bにおいて、（中略）背理法では￢(Ａ⋀￢Ｂ)が真であることを示すとよく言われます

これは広義の背理法です。
「￢(Ａ⋀￢Ｂ)が成り立つ。よってA⇒B（すなわち¬A∨B）も成り立つ」という論証は、二重否定の除去を前提としています。
略す

(引用終り)
以上

http://rio2016.5ch.net/test/read.cgi/math/1730979839/51

52: １３２人目の素数さん [sage] 2024/11/28(木) 15:56:21.99 ID:XCAq3thN

メモ 追加
<chiebukuro.yahoo>背理法
（ ベストアンサー 数ちゃんさん 分かり易い）
detail.chiebukuro.yahoo.co.jp/qa/question_detail/q14241558964
1149769776さん
2021/4/10
背理法は「正しい」と言えるのか？
十数年前、高校生だった時に、塾で数学を教えていたアルバイト講師から、
「論理学でめちゃくちゃ凄い先生がいて、その先生いわく、背理法による証明は厳密には正しいとは言えないらしい」という雑談を聞きました。
当時は聞き流す程度でしたが、年月が経ってもその言葉が気になり、忘れることができません。
今思うと、会話のつなぎのために講師が聞きかじった噂話をしただけかもしれません。
背理法が、厳密には正しくないという議論は存在するのでしょうか？
数学に詳しい方、ご回答いただけると幸いです。

ベストアンサー
数ちゃんさん
2021/4/10
んー講師さんの言ってる意味がよくわからないですね。背理法は別に間違ってないです。厳密には正しくないというのは初耳です。
論理学でめちゃくちゃ凄い先生なのにそんなこと言うとは全然思えないので講師さんが勘違いしたのでしょうか...。
一応仕組みを説明すると以下の公理(証明なしで使う命題)を使います。
公理「排中律:全ての命題には真か偽が決まり、そのどちらかでないといけない。どちらでもある、どちらでもないはありえない。」
公理「否定導入:Pを仮定して矛盾(ある命題Qが真でもあり、偽でもある、が成り立つこと)が生じたら、notPが結論できる。」
公理「二重除去:notPでない、からPである、が結論できる。」

【背理法とは】
実は二つあります。
1:Pを仮定して矛盾したらnotPを結論すること。
2:notPを仮定して矛盾したらPを結論すること。
1はそのまま否定導入です。
2は否定導入と二重除去か、否定導入と排中律で証明できます。二重除去から排中律が、排中律から二重除去が導出できますのでどっちかを採用すれば十分だったりします。
狭義には2のことを背理法と言うのですが広義にはどちらも背理法と言います。2つは全然性質が違うのですがね....。

【原理】
ある命題Pを証明したいとき、notPを仮定する。ここである命題Qが矛盾する、つまり命題Qが真かつ偽である、が証明できたら、否定の導入からnot notPが結論できる。二重除去または排中律よりPが結論できる。

勘違いするところなんてないに等しいので本当によくわからないのですが、もしかしたら「狭義の背理法を認めない数学がある(直感主義論理)」と言うのを勘違いしたのかもしれません。

http://rio2016.5ch.net/test/read.cgi/math/1730979839/52

53: １３２人目の素数さん [sage] 2024/11/28(木) 16:46:57.55 ID:XCAq3thN

追加
・ラッセルのパラドックス＝数学の危機
・ラッセルのパラドックスとは、簡単に言えば”（このカッコに書いてある文はウソです）”というような
　自己言及で、自己否定をいう文です。
　それを、集合論で 「それ自身を要素として含まない集合」を 作ると矛盾（下記）
・ラッセルのパラドックスから、数学の危機が認識され、当時の数学者たちが努力した
　大きく３つの解決法が提案された
　１）一つは、ラッセル自身の提案の型理論
　２）もう一つは、ヒルベルトを中心とする 公理的集合論
　３）３つめが、ブラウワーの直観主義
・さて、そもそも ブラウワーの直観主義は、「排中律」や「二重否定の除去」を認めないとか言われますが
　それは、主に ”ラッセルのパラドックス＝数学の危機”のためであって、単に古典論理を否定したい ためではありませんｗ ；ｐ）
・そして、ブラウワーの直観主義は、現代の構成主義（コンピュータ論理）や 量子論理（量子力学の世界の論理）に繋がっています

(参考)
ja.wikipedia.org/wiki/%E3%83%A9%E3%83%83%E3%82%BB%E3%83%AB%E3%81%AE%E3%83%91%E3%83%A9%E3%83%89%E3%83%83%E3%82%AF%E3%82%B9
ラッセルのパラドックス（英: Russell's paradox）とは、素朴集合論において、自身を要素として持たない集合全体からなる集合の存在を認めると矛盾が導かれるというパラドックス
ラッセルの型理論（階型理論）の目的のひとつは、このパラドックスを解消することにあった[5]。

概要
「それ自身を要素として含まない集合」を「M集合」とし、「すべてのM集合を成分とする集合R」を作ってみる
そうすると、「任意の集合X」に関しては、「XはRに含まれる」⇔「XはXに含まれない」という定式が成り立つ
そして特にX=Rとすれば、「RはRに含まれる」⇔「RはRに含まれない」となり、
パラドックスが明示される。

集合論が形式化されていないことが矛盾の原因なのではなく、このパラドックスは、古典述語論理上の理論として形式化された無制限の内包公理を持つ素朴集合論や、直観主義論理上の素朴集合論においても生じる。したがって論理を古典論理から直観主義論理に変更してもラッセルのパラドックスは回避できない。パラドックスの回避については、様々な方法が提案されている。詳細は矛盾の解消を参照。

矛盾の解消
公理的集合論によって何をもって集合とするかについての形式的な整備が進められ、素朴（だが超越的）な
Rの構成を許容しない体系が構築された。

集合論の公理は通常の数学を集合論の上で展開するために十分なだけの集合の存在を保証しつつ、パラドックスを発生させる集合は構成できないように慎重に設定する必要がある。

1.公理的集合論による解消[注 1]
　略す（注：普通のZFCが代表例）

2.単純型理論による解消[注 2]
項に型と呼ばれる自然数 0, 1, 2,… を割り当て、述語記号 ∈ を (n階の項)∈(n+1階の項) の形でのみ許容する（すなわち論理式の文法を制限する）ことで矛盾を回避する。単純型理論は階型毎に無制限の内包公理を持つが、無矛盾である。

3.部分構造論理による解消[注 3]
en.wikipedia.org/wiki/Russell%27s_paradox
Russell's paradox

つづく

http://rio2016.5ch.net/test/read.cgi/math/1730979839/53

55: １３２人目の素数さん [sage] 2024/11/28(木) 16:47:48.68 ID:XCAq3thN

つづき

ja.wikipedia.org/wiki/%E7%9B%B4%E8%A6%B3%E4%B8%BB%E7%BE%A9_(%E6%95%B0%E5%AD%A6%E3%81%AE%E5%93%B2%E5%AD%A6)
直観主義 (数学の哲学)
en.wikipedia.org/wiki/Intuitionism
Intuitionism (直観主義)
(google訳)
歴史
直観主義の歴史は、19 世紀の数学における 2 つの論争にまで遡ることができます。

最初のものは、ゲオルク・カントールによる超限算術の発明と、その後の彼の師であり確固たる有限主義者であったレオポルド・クロネッカーを含む多くの著名な数学者によるその否定であった。

2 つ目は、ゴットロープ・フレーゲが集合論を通じて数学全体を論理的定式化しようとした試みと、ラッセルのパラドックスを発見した若きバートランド・ラッセルによるその試みの挫折である。フレーゲは 3 巻からなる決定的な著作を計画していたが、ちょうど第 2 巻が印刷されようとしていたとき、ラッセルはフレーゲに手紙を送り、フレーゲの自己言及の規則の 1 つが自己矛盾であることを証明した彼のパラドックスの概要を説明した。第 2 巻の付録で、フレーゲは彼の体系の公理の 1 つが実際にラッセルのパラドックスにつながることを認めた。[ 4 ]

これらの論争は密接に結びついています。カントールが超限算術の結果を証明するために使用した論理的手法は、ラッセルがパラドックスを構築するために使用した手法と本質的に同じだからです。したがって、ラッセルのパラドックスを解決する方法の選択は、カントールの超限算術に与えられる地位に直接影響を及ぼします。

20世紀初頭、LEJ ブラウワーは直観主義の立場を、ダヴィド ヒルベルトは形式主義の立場を代表した(ファン ハイエノールト参照)。クルト ゲーデルはプラトン主義と呼ばれる意見を述べた(ゲーデルに関するさまざまな情報源を参照)。アラン チューリングは「証明のすべてのステップが機械的ではなく、一部は直観的な、非構成的論理体系」とみなしている。 [ 5 ]その後、スティーブン コール クリーネは、メタ数学入門(1952)で、直観主義についてより合理的な考察を行った。 [ 6 ]

ニコラ・ギシンは直観主義数学を採用して量子不確定性、情報理論、時間の物理学を再解釈している。[ 7 ]

ja.wikipedia.org/wiki/%E4%BA%8C%E9%87%8D%E5%90%A6%E5%AE%9A%E3%81%AE%E9%99%A4%E5%8E%BB
二重否定の除去（にじゅうひていのじょきょ、英: double negation elimination）および二重否定の導入（にじゅうひていのどうにゅう、英: double negation introduction）は、いずれも推論の種類の一つである

素朴集合論でも、補集合が同様の性質を持つ。集合 A と集合 (A^C)^C は等価である（ここで、A^C は A の補集合を意味する）
(引用終り)
以上

http://rio2016.5ch.net/test/read.cgi/math/1730979839/55

上下前次1-新書関写板覧索設栞歴

ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 0.017s