背理法と対偶の違い

ツイートまとめ

英語での検索結果

日本語だと高校の話が大量に引っかかるので英語で探した. 案の定 mathoverflow が出てきた. 追加で Reductio ad absurdum or the contrapositive? から翻訳しつつ引用する.

まずはふだん使わないからすぐ忘れるので, 参考までに背理法と対偶の英語をメモしておく.

翻訳・引用開始

記事中段あたりに出てくる議論

このコメントが良さそう. よく混同される気分を説明してくれていそうな気がする. Twitter でもらったコメントでもある模様.

it is certainly true that every proof by contrapositive can be phrased as a proof by contradiction. Indeed, since the latter is perhaps a bit more intuitive,

We wish to show $A \implies B$. Suppose we know that $\lnot B \implies \lnot A$. Suppose further that $B$ is false. Then $\not B$ is true, so $\lnot A$ is true, so $A$ is false, contrary to our assumption.

これが対偶+背理法のよくある「わかりやすい」証明.

Suppose a proposition can be proved by contraposition. As above, there is then a standard recipe for modifying the proof to give a proof by contradiction.

上のレシピで対偶の議論が背理法のように変換されてしまう.

However, proof by contradiction is a more powerful technique in the informal sense that some proofs are more difficult to phrase using contraposition. (I don't want to say impossible, because as above, both "techniques" are simply logically valid arguments, so may be inserted in a proof at any point.)

インフォーマルな意味での背理法による証明の利点は, 対偶として綺麗にリフレーズするのが難しい場合にも雑に使えることにある.

What makes contradiction potentially more powerful? (This is a question that you have to face when you teach introduction to proofs classes, as I have. I wouldn't have had as ready an answer before.) I think it is because we get to assume two things rather than one. Namely, instead of just assuming $\lnot B$ and using that one assumption to work our way to $\lnot A$, we get to assume both $A$ and $\lnot B$ and play them off one another in order to derive a contradiction.

対偶証明と背理法の比較で背理法が強力に見えるのは 2 つ仮定できることによる. つまり対偶では $\lnot B$ しか仮定できないが, 背理法では $A$ と $\lnot B$ が仮定できて使える条件が増える. このあとによくある $\sqrt{2}$ の無理性に関して具体的な説明がある.

but in many cases that would amount to inserting a tiresome rigamarole

rigamarole という単語, はじめて見た. 「長く複雑で困惑させる手続き、一連の混乱して無意味な話」とのこと.

記録 1

Proof by contradiction (, i.e. derive $\Delta \vdash \varphi$ from $\Delta, \lnot \varphi \vdash \bot$) is not valid in intuitionistic logic. Proof by contrapositive (, i.e. derive $\Delta \vdash \psi \rightarrow \varphi$ from $\Delta \vdash \lnot \varphi \rightarrow \lnot \psi$) is neither.

はじめのツイートと同じ事案.

英語メモ

The reason is the fecundity of the proof

fecundity は繁殖力、生殖能力の意味らしい. はじめて知ったので記録.

素数の無限性メモ

For an example of a proof where we are led to false expectations in a proof by contradiction, consider Euclid's proof that there are infinitely many primes. In a common proof by contradiction, one assumes that p1, ..., pn are all the primes. It follows that since none of them divide the product-plus-one p1...pn+1, that this product-plus-one is also prime. This contradicts that the list was exhaustive. Now, many beginners falsely expect after this argument that whenever p1, ..., pn are prime, then the product-plus-one is also prime. But of course, this isn't true, and this would be a misplaced instance of attempting to extract greater information from the proof, misplaced because this is a proof by contradiction, and that conclusion relied on the assumption that p1, ..., pn were all the primes. If one organizes the proof, however, as a direct argument showing that whenever p1, ..., pn are prime, then there is yet another prime not on the list, then one is led to the true conclusion, that p1...pn+1 has merely a prime divisor not on the original list.

ユークリッドの証明で $\prod_{k=1}^n p_k + 1$ が素数であるように感じてしまう初心者がいるが, これ自体は一般には間違いだというよくある話.

証明の質

proofs by contraposition are more satisfying than proofs by contradiction, because they give you more information beyond just knowing that the desired result is true. For instance, in analysis, proofs by contraposition tend to be finitary in nature and yield effective bounds, whereas proofs by contradiction (especially when combined with compactness arguments) tend to be infinitary in nature and do not easily yield such bounds (unless one very painstakingly converts each step of the infinitary contradiction argument into a finitary contrapositive argument).

対偶で示す方が背理法で示すよりもいいという話でユークリッドの素数の無限性とも関係する. 対偶を示すのはいわばふつうの証明で, その中で示したことは正しいものの, 背理法の中で示したことは正しいとは限らない.

背理法と対偶についてふと思ったことをつらつらと書いた

この節についての

ここは上のメモを書く遥か前に書いた文章. まとめた方がよさそうなのでまとめた.

本文

2013 年の理科大の数学入試問題的なアレでこう色々と話題になった背理法だが, 例のあの HP に書いてあることが寸分の狂いもなく 社会的という訳でもないというのをふと思ったので, それについて書く.

時々, 対偶を示すべきところで背理法を使って文章を書いている人がいる. 対偶使った方が話の流れとして素直に書きやすくなると思うし, そもそも議論が見えていないということなので, 意識して直した方がいい. 実際問題, 背理法は結構扱うの難しいときがある.

名古屋の小林亮一先生だかに聞いたところによると, Poincare 予想の解決で有名な Perelman の論文は 5 段くらいの多段で背理法を使っているそうだ. 何が仮定で何を示したくて何を否定しているのか混乱してきて, 読むのが大変だったという.

あとあまり関係なく例の HP にある $\sqrt{2}$ の無理性証明だが, あれ, 私にはすごく読みづらいのだが他の人はどう思っているのだろうか. 単に慣れないだけかもしれないのだが, $\neq$ で式が繋がっていくのがすごく見づらくやりづらい.

特別何かが言いたいというわけではなく, 備忘録的に残しておく感じのアレだった.

上記内容への反応

追記

上記内容に関して次のようなコメントを頂いた.

あとあまり関係なく例の HP にある $\sqrt{2}$ の無理性証明だが, あれ, 私にはすごく読みづらいのだが他の人はどう思っているのだろうか. 単に慣れないだけかもしれないのだが, $\neq$ で式が繋がっていくのがすごく見づらくやりづらい.

私もアレはアレだと思うのでナニしてみた (http://animaleconomicus.blog106.fc2.com/blog-entry-878.html). ソレもアレだという意見は歓迎する.

コメント

そちらにつけたコメントも一応再掲しておく.

証明自体は正しいと思うのですが, 気分的にまだすっきりしていなくて, ずっとそのところを考えていました.

それはそれとして, 細かいところがいくつか気になります.

ある, 0 より大きい有理数 S があるとする. (仮定) これは仮定ではなく事実でしょう.

ある数が 0 より大きい有理数であるとき, その数は一意に素因数分解されて, もちろん言いたいことは分かりますが, 有理数に対して素因数分解という言葉, 普通は使わないでしょう.

単純に見慣れない証明だからなのか何なのか分かりませんが, 異様なくらい気分的にすっきりきません. 初等的な命題の初等的な証明でここまで腑に落ちないのがすごく面白いので もう少し考えてみます. コメントありがとうございました.

元のサイトの証明

これも引用しておく.

$\sqrt{2}$ は有理数ではないことを証明する.

ある, 0 より大きい有理数 $S$ があるとする. (仮定)

ある数が 0 より大きい有理数であるとき, その数は一意に素因数分解されて, そのすべての指数は (0 を含み, 負の整数を含む) 整数である. (正しい)

例 1) $2/3 = 2^1 \cdot 3^{-1}$ 例 2) $4/9 = 2^2 \cdot 3^{-1}$

$S$ を $\sqrt{S} \times \sqrt{S}$ と表わす. すなわち, $S = \sqrt{S} \times \sqrt{S}$ であり, $\sqrt{S} = \sqrt{S}$ である. $\sqrt{S}$ が有理数であるならば, $\sqrt{S}$ は一意に素因数分解される. ゆえに, $S$ を素因数分解した場合, おのおのの素数の指数が (0 を含めた) 偶数でなければ, $\sqrt{S}$ は有理数にならない. (正しい) ここで, 2 を素因数分解すると, 2 の指数は 1 であって偶数ではない. (正しい) ゆえに, 2 は「"二つの同一の有理数"の積」では表わせない. ゆえに, $\sqrt{S}$ は有理数ではない.

これが提示しようとしたものである. Q.E.D.

初等的な命題の初等的な証明に何故ここまで腑に落ちないものを感じるのか, それが面白い.