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

背理法と対偶って違うの？ (117ﾚｽ)
上下前次 1-新
通常表示 512ﾊﾞｲﾄ分割ﾚｽ栞

39: １３２人目の素数さん [sage] 2024/11/13(水) 12:08:38.82 ID:0yIDnyuw

下記は、かなり荒っぽい説明ですが
ゆえに分かり易い説明で、参考になります

『集合論のパラドックスです。例えばXを自分自身を元として含まない集合の集合としましょう。さてX∈Xでしょうか。X∈XとするとXの定義からXの元ではありません。一方X∈Xではないとすると、X∈Xのはずです。いずれにしても矛盾が導かれます。』

これに対する直観主義（構成主義）は
『排中律（任意の命題Pについて「PであるかPでないかどちらかである」とする主張)を否定する』です

note.com/yoriyuki/n/n456e260e4b1f
数学基礎論論争は結局どうなったか 筆の滑り 2020年5月17日
数学に関心のある人なら、20世紀の初めに「数学基礎論論争」があったことをぼんやりとは聞いたことがあると思います。数学基礎論論争が結局どうなったかについて書きます。

目次
数学基礎論論争とは
論理主義
形式主義
直観主義（構成主義）
その後どうなったか

数学基礎論論争とは
19世紀を通じて数学は厳密化の道をたどってきました。たとえばフーリエ級数の収束については多くの誤った「証明」がなされ、最終的に「測度0上の除外点を除いて収束する」という条件にたどりついたのは20世紀になってからです。そして「測度」という概念を定式化するには集合論が不可欠です。

そこで集合論を厳密に公理的に取り扱う試みが行われましたが、ここで表面化したのが集合論のパラドックスです。例えばXを自分自身を元として含まない集合の集合としましょう。さてX∈Xでしょうか。X∈XとするとXの定義からXの元ではありません。一方X∈Xではないとすると、X∈Xのはずです。いずれにしても矛盾が導かれます。

このようなパラドックスにどう対応するかという問題を契機にして、数学をどのように行うべきか関する論争が行われました。これを数学基礎論論争といいます。数学の危機とも呼ばれます。

ただし、この「危機」の最中にも数学は普通に発展していました。したがって「危機」というのは誇張だという考えもあります。また、現代から見ると何を論争しているかよくわからないところがあります。個人的な誤解にもとづく争いであったと考える人もいるようです（ファン・ダーレンとか）。また、単に集合論のパラドックスの解決を目指したものではなく、無矛盾性や数学の確実性を担保することだけがゴールでもありませんでした。

形式主義
形式主義はヒルベルトが唱えた立場とされています。
略
形式主義は失敗したということになっています。ゲーデルの不完全性定理より、Tの中に含まれる手段ではTの無矛盾性を示すことはできません。有限的な理論がTに含まれていると考えれば、Tの無矛盾性を有限的に示すことはできません。
ただ、個人的にはこの結論は性急だと思っています。Tに含まれない有限的な原理を想定することが可能だからです。例えば、順序数解析では自然数上のある種の順序について帰納法が可能であることから、いろいろな数学体系の無矛盾性を示しています。

つづく

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

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

57: 現代数学の系譜 雑談 ◆yH25M02vWFhP  [sage] 2024/11/29(金) 14:57:26.62 ID:v+dxUrg+

追加参考

https://ja.wikipedia.org/wiki/%E5%8F%A4%E5%85%B8%E8%AB%96%E7%90%86
古典論理（こてんろんり、英: classical logic）は形式論理の部類で、最も研究され最も広く使われている論理である。標準論理（英: standard logic）とも呼ばれる[1][2]。

特徴
以下に示す性質が特徴である:[3]

1.排中律の採用及び、二重否定の除去;
2.無矛盾律と、矛盾からはいかなることも導ける（en:Principle of explosion）とすること（矛盾許容論理も参照）;
(3〜5 略す)

以上の諸条件からは、古典論理は命題論理と一階論理に必ずしも限られないが、普通はそれらに議論を限定する[4][5]。

意味論
略す

古典論理の例
略す

https://en.wikipedia.org/wiki/Classical_logic
Classical logic (or standard logic)[1][2] or Frege–Russell logic[3] is the intensively studied and most widely used class of deductive logic.[4] Classical logic has had much influence on analytic philosophy.

History
Main article: History of logic
Classical logic is a 19th and 20th-century innovation. The name does not refer to classical antiquity, which used the term logic of Aristotle. Classical logic was the reconciliation of Aristotle's logic, which dominated most of the last 2000 years, with the propositional Stoic logic. The two were sometimes seen as irreconcilable.
以下略す

https://en.wikipedia.org/wiki/History_of_logic
History of logic
略す

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

76: １３２人目の素数さん [sage] 2024/11/30(土) 08:44:42.75 ID:9Sqq12HI

>>74 追加

数研出版
数研通信 3号
背理法の定義について 塩見浩三 愛媛県西条高等学校
より

(引用開始)
数研出版の｢数学I」の教科書では106頁に，√2
が無理数であることの証明を例にして

背理法”とは「ある事柄を証明するのに，まず
その事柄が成り立たないと仮定して矛盾を導き，
それによって事柄の成り立つことを証明する方
法」である．
と書いています．

また，他の参考書には，”背理法〃とは｢証明すべ
き結論を否定して論理を進めていき，与えられた条
件と対立する結論を導き出して矛盾（不合理）を示
す一つの証明方法である」と書いています．

対偶については，186頁に
１命題の真偽は，その対偶の真偽と一致する．
２命題 p→qが真であることを示すために，
　その対偶q^- → p^-が真であることを示し
　てもよい．
と書いています．
（注： p^-は、pの否定を表す。テキストではpの上にバーがある。q^-も同様）

背理法の中に対偶法も含めているのがほとんどの
教科書，参考書の書き方である．上の数研出版の教
科書の説明も同じである．
しかし，参考書は，対偶法の説明を背理法と考え
ている．
どちらも間違いではないが，定義がどうもあいま
いで，生徒にとって（先生自身にとっても）すっき
りしない説明に終わっているのが現状ではないだろ
うか？

背理法とは,AもB^-も仮定として用いて理論
を進め，他の真理（公理，定理，定義）に矛盾する
ことを引き出す証明法であり，対偶法とはB^-のみ
を仮定として理論を進めて,A^-を導く証明法であ
る．
(引用終り)

思うに、塩見浩三氏が書いているように
”背理法の中に対偶法も含めているのがほとんどの
教科書，参考書の書き方である”
”参考書は，対偶法の説明を背理法と考え
ている．”

で、 ”定義がどうもあいま
いで，生徒にとって（先生自身にとっても）すっき
りしない説明に終わっているのが現状ではないだろ
うか？”（塩見）でしょうｗ ；ｐ）

だから>>1 "背理法と対偶って違うの？
同じじゃないの？"
となるのだろう

やれやれ
そこから間違いを正していかないとなると
大変だよ〜ｗｗ ；ｐ）

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

77: １３２人目の素数さん [sage] 2024/11/30(土) 09:47:46.38 ID:9Sqq12HI

>>66 タイポ訂正

背理法は、
・命題の論理で 「Q ＆ Pの否定 → 矛盾」です
　↓
背理法は、
・命題の論理で 「P ＆ Qの否定 → 矛盾」です

さて
>>76 つづき

数研通信 3号
背理法の定義について 塩見浩三 愛媛県西条高等学校
より
（当時の）数研出版の｢数学I」の教科書で
対偶については，186頁に
１命題の真偽は，その対偶の真偽と一致する．
２命題 p→qが真であることを示すために，
　その対偶q^- → p^-が真であることを示し
　てもよい．
と書いています．
（注： p^-は、pの否定を表す。テキストではpの上にバーがある。q^-も同様）
(引用終り)

つまり
1）命題 p→q ベン図ではP ⊂ Q
　対偶 q^- → p^-  ベン図では Q^c ⊂ P^c （P^c 、Q^c は補集合を表す）
　と教えている
2）そう教えるならば、その流れで
　背理法 qの否定(q^-) ＆ p → 矛盾(あり得ない) ベン図では P∩Q^c＝Φ（空集合）
　とするべき
　「証明すべき結論(上記のq)を否定して論理を進めていき」とするのが正
　「ある事柄を証明するのに，まず その事柄が成り立たないと仮定して」は誤
　”その事柄が成り立たない”などと、あいまい表現がよくない
　”命題 p→q ”としたら、命題の否定とは 結論qの否定とすべき

さて、√2が無理数であることの証明の背理法の構造
命題 p→q に当て嵌めすると
p：√2は、x^2=2となる 正の実数
q：x=√2 は 無理数

さて、愚直に p→q を考えるとすると
簡単にいえば
これは、pから出発して 三段論法で ギャップなく qに到達すること
しかし、”q：√2 は、無理数”が曖昧だ。そこで 背理法の出番になる

分かり易く 背理法の前に、対偶法を考えよう
q^- ：x=√2 は 有理数
p^-：x^2=2 以外の (正の)実数
と書ける
ここで、”x^2=2 以外の (正の)実数”が数学的には使いづらいので
対偶 q^- → p^-
の背理法で
q^-(x=√2 は 有理数) かつ p(√2は、x^2=2となる 正の実数) →矛盾(あり得ない)
を導くことが閃く
（これは、元の命題の背理法 ”qの否定(q^-) ＆ p”と同じであることを注意しておく）

つまり、”x^2=2 以外の (正の)実数” よりも ”√2は、x^2=2となる (正の)実数”
が、圧倒的に使いやすい

そうやって、q^- ：x=√2 は 有理数
から、x=a/b (既約分数)とおけて
あとは、ご存知の通り →矛盾(あり得ない) が導ければ
背理法証明の完成です

”あり得ない”が、集合で空集合Φ に対応している

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

81: １３２人目の素数さん [sage] 2024/12/01(日) 09:32:35.32 ID:akzgVyU5

全くの蛇足ですが

1）>>76 数研出版 数研通信 3号
　背理法の定義について 塩見浩三 愛媛県西条高等学校
　より『背理法の中に対偶法も含めているのがほとんどの
　教科書，参考書の書き方である．上の数研出版の教
　科書の説明も同じである．』
　と記されている
2）しかしながら、>>77に記したように
　・命題 p→q ベン図ではP ⊂ Q
　・対偶 q^- → p^- ベン図では Q^c ⊂ P^c （P^c 、Q^c は補集合を表す）
　・背理法 qの否定(q^-) ＆ p → 矛盾(あり得ない) ベン図では P∩Q^c＝Φ（空集合）
　とすべき
3）『√2が無理数であることの証明の背理法の構造
　命題 p→q に当て嵌めすると
　p：√2は、x^2=2となる 正の実数
　q：x=√2 は 無理数』
　『対偶 q^- → p^-
　の背理法で
　q^-(x=√2 は 有理数) かつ p(√2は、x^2=2となる 正の実数) →矛盾(あり得ない)
　を導くことが閃く
（これは、元の命題の背理法 ”qの否定(q^-) ＆ p”と同じであることを注意しておく）』
　『そうやって、q^- ：x=√2 は 有理数
　から、x=a/b (既約分数)とおけて
　あとは、ご存知の通り →矛盾(あり得ない) が導ければ
　背理法証明の完成です』
4）さて、証明論として
　a)直接法：p→q ベン図ではP ⊂ Q
　b)間接法の対偶法 q^- → p^- ベン図では Q^c ⊂ P^c （P^c 、Q^c は補集合を表す）
　c)間接法の背理法 qの否定(q^-) ＆ p → 矛盾(あり得ない) ベン図では P∩Q^c＝Φ（空集合）
　となるが
　学部レベルの簡単な定理では、このa)〜c) が当てはまる場合が多い
　しかし、難しい定理 あるいは xx予想 と呼ばれる命題は、こういう単純パターンに乗らないものがある
　例えば、”√2が無理数であることの証明”で、循環する無限連分数で表現できることを使える（下記）
（なお、ja.wikipedia 2の平方根もご参照）

(参考)
ja.wikipedia.org/wiki/%E9%80%A3%E5%88%86%E6%95%B0
連分数
様々な数の連分数展開
下線部はそれぞれの循環節。
2の平方根
（√2は、循環する無限連分数）

つづく

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

85: １３２人目の素数さん [] 2024/12/08(日) 23:49:49.89 ID:ynttxdFV

>>84
違うよ >>11より再録
Q 背理法と対偶って違うの？
A 違います
<説明>
・下記の進研ゼミ包含関係 ベン図 「図1より，「 p ⇒q 」が真である，ということは，P⊂Qであるということ」
・いま、否定記号 ￢p, ￢q , 補集合を P^-, Q^- とします
　対偶は、”「￢q→￢p」が真である，ということは，Q^- ⊂ P^-であるということ”となります
　つまり、補集合Q^- と P^-をとると 包含関係が逆向きで、 命題否定関係も矢印が 逆向きです（ここまでは高校範囲）
・では、背理法は？ (qの否定(￢q)) ・ p ⇒ 矛盾 （空集合Φ、 ”・”は積です）
　つまり ベン図で P∩Q^- ＝Φ（空集合）
です
・背理法の利点は、証明に使える条件が増えていること
　つまり、p ⇒q の証明は、pのみを使って q を導くのに対して
　背理法では、pに加えて qの否定(￢q)も使えて、矛盾 （空集合Φ）を導けば良いってことです。この方が楽な場合があるってこと
（例 √2が無理数の証明で、背理法では”√2が無理数”の否定 → ”√2が有理数”と仮定する が使えるってこと）

なお、私は 10年くらいまえに ここ 当時2ch で 下記の ”背理法被害者の会”のことを教えてもらって、そのときに考えたことです
なお、下記もご参照ください

(参考)
https://kou.benesse.co.jp/nigate/math/a14m0119.html
進研ゼミ 高校講座
高校生の苦手解決Q&A
【数と式】「pならばq 」が真のとき，集合Pが集合Qに含まれる理由
Q
「pならばq 」が真のとき，集合Pが集合Qに含まれる理由
条件pを満たすもの全体の集合をP ，条件q を満たすもの全体の集合Qとするとき，「 p ⇒q 」が真であるときに P⊂Qが成り立つのか，P⊃Qが成り立つのかわかりません。
A
≪命題の真偽をベン図に表す≫
「 p ⇒q 」が真，つまり「 p ⇒q 」が成り立つ，ということをベン図に表してみましょう。
条件pを満たすもの全体の集合をP，条件qを満たすもの全体の集合をQとすると，Pに含まれているものx は，条件pを満たしています。今，「 p ⇒q 」が成り立っているのですから，xは条件qも満たしているということになり，xはQに含まれるのです。
つまり，Pに含まれているものはすべて，Qに含まれることになり，このことを集合のベン図で表すと，図１のようになります。
略
≪包含関係をベン図で表す≫
よって，図1より，「 p ⇒q 」が真である，ということは，P⊂Qであるということそのものであることがわかります。

★まとめ★
条件pを満たすもの全体の集合をP，条件qを満たすもの全体の集合Qとするとき，
「 p ⇒q 」が真⇔P⊂Q
となります。

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

86: １３２人目の素数さん [] 2024/12/09(月) 00:13:42.57 ID:b+51aIH5

>>85 補足

・今の話は、古典論理（下記）の中
・直観主義では、背理法は許容されない。
・なお対偶の一部 ”「AならばB」から「BでないならばAでない」は、直観主義論理においても導出可能である”
　が、”from ¬Q→¬P to P→Q, requires the law of the excluded middle or an equivalent axiom.”なので 証明法としての対偶証明はダメ（英文ご参照）

ja.wikipedia.org/wiki/%E5%8F%A4%E5%85%B8%E8%AB%96%E7%90%86
古典論理（こてんろんり、英: classical logic）は形式論理の部類で、最も研究され最も広く使われている論理である。標準論理（英: standard logic）とも呼ばれる[1][2]。

特徴
以下に示す性質が特徴である:[3]
1.排中律の採用及び、二重否定の除去;
以下略す

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)
直観主義 (数学の哲学)
来歴と評価
ブラウワーは、数学的概念とは数学者の精神の産物であり、その存在はその構成によって示されるべきだという立場から、無限集合において背理法によって非存在の矛盾から存在を示す証明を認めなかった。それゆえ、無限集合において「排中律」、すなわちある命題は真であるか偽であるかのどちらかであるという推論法則を捨てるべきだと主張し、ヒルベルトとの間に有名な論争を引き起こした。 ヒルベルトの形式主義は、直接的にはブラウワーからの批判的主張に対し排中律を守り、数学の無矛盾性を示すためのものと考えることができる[1]。

ja.wikipedia.org/wiki/%E5%AF%BE%E5%81%B6_(%E8%AB%96%E7%90%86%E5%AD%A6)
対偶 (論理学)
対偶（たいぐう、英: Contraposition）とは、「AならばB」という形式の命題に対して、その命題の仮定と結論をそれぞれその否定に置き換えた上で両者を入れ替えた命題のことをいう。
定義
略す
通常の数学では古典論理を用いるため、命題「AならばB」とその対偶「BでないならばAでない」の真偽および証明可能性は必ず一致する (すなわち真理値が等しい）。

直観主義論理における扱い
上述の対偶の性質は古典論理におけるそれであり、非古典論理においては成立しない場合がある。例えば直観主義論理においては、必ずしも「AならばB」とその対偶「BでないならばAでない」の真偽は一致しない。

直観主義論理の特徴として、排中律の不成立（あるいは二重否定の除去の制限）があげられるが、対偶の性質はこの制限の影響を受け成立しない。なお「AならばB」から「BでないならばAでない」は、直観主義論理においても導出可能である。

en.wikipedia.org/wiki/Contraposition
Contraposition
In nonclassical logics
Intuitionistic logic
In intuitionistic logic, the statement
P→Q cannot be proven to be equivalent to
¬Q→¬P.
We can prove that
P→Q implies
¬Q→¬P (see below), but the reverse implication,
from ¬Q→¬P to P→Q, requires the law of the excluded middle or an equivalent axiom.

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

107: 現代数学の系譜 雑談 ◆yH25M02vWFhP  [] 2024/12/09(月) 20:31:40.47 ID:b+51aIH5

ふっふ、ほっほ

>>93より 訂正再投稿
1）古典論理において、厳然と証明手法として
　背理法と対偶法は、存在する
　そして、この二つの手法は別もの
　この事実を認めましょうね
2）これを、いつもの例題 √2が無理数であることの証明で示す
　命題：実数 x^2=2→xは無理数である
　p：実数 x^2=2、q：xは無理数
　さて
　対偶法：xは有理数→x^2≠2
　背理法：{実数 x^2=2}∩{xは有理数}＝Φ（空集合）（Φは矛盾を示してあり得ないことをいう）
3）具体的な背理法証明は、頻出なので略す
　ここで、q：xは無理数 を考えるより、￢q：xは有理数 とする方が圧倒的に有利で分かり易い
　また、対偶法の ￢p：x^2≠2 を考えるより、p：x^2＝2 とする方が圧倒的に有利で分かり易い
　背理法とは、このように ロジックとしては等価だが
　p,q をマトモニ考えるよりも、その否定 ￢p,￢q を考える方が、証明戦略として楽な場合があるってことですよ
　対偶法も同様のことです

どの組合せが良いか？
それは、具体的な証明すべき命題で決まる

>>100について
訂正再投稿
証明手法として
1)普通の証明（P→Q）(直接法)
2)対偶法
3)背理法
補足
対偶法と背理法とは、間接証明とかいうそうですね

(参考)
www.jstage.jst.go.jp/article/jasme/24/2/24_25/_pdf/-char/ja
全国数学教育学会誌 数学教育学研究第24巻第2号2018 pp.25〜36
間接証明の構造の理解に関する研究 −理解の様相を捉える枠組みの構成一
広島大学大学院 教育学研究科 院生 浦山大貴

＜ちょっと妖しいが・・ｗ (＾＾；＞
exam-strategy.jp/archives/1321
敬天塾 2024年8月27日
背理法と対偶命題の証明法は、どのように使い分けるのか

背理法と対偶命題の証明法の使い分けは（基本編）
では、やっとですが背理法と対偶命題の証明法の使い分けに行きましょう。
基本的には、
断定型の命題を否定しながら証明する時は、背理法
推論型の命題を否定しながら証明する時は、対偶命題の証明法
と使い分けます。

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

109: １３２人目の素数さん [] 2024/12/10(火) 10:52:05.50 ID:ytuvmVUS

>>108
>背理法と対偶法は思考のロジックとして
>ほぼほぼ同じ内容です>>96

あんまり、数学に向いていない 雑な思考をしますねｗ ；ｐ）

>>107より
証明手法として
1)普通の証明（P→Q）(直接法)
2)対偶法 (間接法)
3)背理法 (間接法)
となります

対偶法と背理法とは、同じ間接法に分類されます
古典論理で
１）直接法 P→Q
２）対偶法 ￢Q→￢P
３）背理法 ￢Q⋀P→空(矛盾) (集合では￢Q ⋂ P＝Φ(空集合))

少し補足しましょうね >>107より
いつもの例題 √2が無理数であることの証明で示す
命題：実数 x^2=2→xは無理数である
p：実数 x^2=2、q：xは無理数

これを、直接法 p→q を示そうとするとき
出発点で使える条件は、”x^2=2” のみ
なので、直接法で、「√2が無理数であること」を直施示すには、大理論を持ちだすしかない
典型例が、連分数の理論です

連分数の理論で、√2が無限に循環する連分数表示を持つことが分かる（下記）
よって、√2は無理数である （”無限連分数が無理数である”ことは、既知として）■

一方、背理法ならば ￢q⋀p→空(矛盾) を示せばいいので
￢q：xは有理数 x＝a/b (a/bは既約分数)
p： x^2=2

つまり、二つの条件 x＝a/b と x^2=2 とが使える利点があります （頻出なので、後は略す）

さて、対偶法です
￢q：x＝a/b → p： x^2≠2
となります
￢q → p： x^2≠2
を示すときに、”x^2≠2”がこのままでは まずい
よって、この対偶命題に 背理法を適用します

そうすると (￢q：x＝a/b) ⋀ (p：x^2=2)→空(矛盾)
とできて、これは 最初の命題 P→Q に対する背理法と 一致します！ （＾＾

なので、”√2が無理数であることの証明”では、背理法が一番簡単
直接法は、連分数の理論など大理論が必要
対偶法は、結局は 背理法 に持ち込むことになるでしょう

これが結論ですｗ

(参考)
https://ja.wikipedia.org/wiki/%E9%80%A3%E5%88%86%E6%95%B0
連分数（れんぶんすう、英: continued fraction）とは、分母に更に分数が含まれているような分数のことを指す
二次無理数（整数係数二次方程式の根である無理数）の正則連分数展開は必ず循環することが知られている。
逆に、正則連分数展開が循環する数は二次無理数である。

様々な数の連分数展開
下線部はそれぞれの循環節。

2の平方根
√2＝略す

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

112: １３２人目の素数さん [] 2024/12/10(火) 11:42:27.20 ID:ytuvmVUS

>>21 より 背理法の説明再録しておきますね
(引用開始)
・では、背理法は？ (qの否定(￢q)) ・ p ⇒ 矛盾 （空集合Φ、 ”・”は積です）
　つまり ベン図で P∩Q^- ＝Φ（空集合）
です
・背理法の利点は、証明に使える条件が増えていること
　つまり、p ⇒q の証明は、pのみを使って q を導くのに対して
　背理法では、pに加えて qの否定(￢q)も使えて、矛盾 （空集合Φ）を導けば良いってことです。この方が楽な場合があるってこと
(引用終り)

下記2点に詳しい説明がある
（下記 Dr. Valerie Hower youtu.be 百回見てねｗ （＾＾）

(参考)
https://math.libretexts.org/Courses/SUNY_Schenectady_County_Community_College/Discrete_Structures/05%3A_Set_Theory/5.02%3A_Proving_Set_Relationships
LibreTexts
Disjoint Sets
This is an instance where proving the contrapositive or using a proof by contradiction could be reasonable approaches. To illustrate these methods, let us assume the proposition we are trying to prove is of the following form:
If P , then T=∅ .
If we choose to prove the contrapositive or use a proof by contradiction, we will assume that T≠∅
. These methods can be outlined as follows:
The contrapositive of “If P , then T=∅ ” is, “If T≠∅ , then ┐P .”
So in this case, we would assume T≠∅ and try to prove ┐P .
Using a proof by contradiction, we would assume P and assume that T≠∅ .
From these two assumptions, we would attempt to derive a contradiction.
One advantage of these methods is that when we assume that T≠∅ , then we know that there exists an element in the set T .
We can then use that element in the rest of the proof.
We will prove one of th the conditional statements for Proposition 5.14 by proving its contrapositive.
The proof of the other conditional statement associated with Proposition 5.14 is Exercise (10).
Proposition 5.14
Let A and B be subsets of some universal set. Then A⊆B if and only if A∩Bc=∅ .
Proof
略

https://youtu.be/KmAyZOQSp0k?t=1143
Proof by Contradiction (full lecture)
Dr. Valerie Hower
2020/11/08
コメント
@monraet
5 か月前
Thanks Dr. However for all your math videos, they are the best

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

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

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

ぬこの手ぬこTOP 0.013s