数学的帰納法は帰納か演繹か
数学的帰納法は帰納か演繹か
https://gyazo.com/466cfd8e5d4bf9b310eae145ba5f4daf
図を描いたnishio.icon
4のステップで確実に正しい結論が導けるのかどうかは3で「すべてのnの集合」を取り尽くすことができるかどうかに掛かっている
例えばnが有理数だったりすると確実と言えなくなる
自然数に関しては数百年の間、本当は確実だとする根拠が足りないのに確実だと考えられて使われてきた(3ですべての自然数を取り尽くせている保証がなかった)
直感的には取り尽くせるけどこの直感が全く役に立たないのがこの辺りの数学なんだよなあ…基素.icon
1891年に「3ですべて取り尽くせてるってことに決めましょう」となった(ペアノの公理) ペアノの公理以降、数学的帰納法のステップ全体を一つの確実な結論を導く演繹ステップとみなせるようになった
ちょっと混乱するやつ
そうなのかsta.icon
n=1の場合、n=2の場合、みたいに具体的な例から攻めてるから帰納だと思っていた
これはややこしい例nishio.icon
具体的な例から結論を導いてるという点に関してはもちろん帰納である
その「具体的な事実に関してTrueだと確認すること」を「最初と、kがtrueである場合のk+1」にだけやれば「すべての具体的な事実に対する検証ができる」
「だから、確実な結論を導くことができるよね」というロジックのところが演繹的
なぜか
具体的な事象から導き出してるわけではなく、仮定から導き出しているため、演繹法
違う、ここの部分は帰納nishio.icon
仮定って言い方が悪かった?。公理と呼ぶべきだった？biwa.icon
や、そこの問題ではなさそう
何が違うのか説明してほしいbiwa.icon
A(1)がTrueなのは仮定ではないnishio.icon
仮定として指してるのはA(1)ではなく、以下に書いている公理のことを指していたbiwa.icon
仮定(公理)として、任意の命題Aについて、A(1) かつ(A(k) ならば A(k+1))のとき、A(n)である というものが存在していて、そこから(具体的な命題Aを適用して)導き出されるため
公理 数学的帰納法: $ \forall A. A(1) \land \forall k. \{A(k) \rightarrow A(k+1)\} \rightarrow \forall n. A(n)
Aは命題
n, kは整数
数学的帰納法を使用するとき、上の前提のAに具体的な命題を当てはめているに過ぎない。
なるほどsta.icon
帰納自体は例から仮説を導く雑なものだが、それを数学でやろうとすると（数学は厳密なので）前提ベースでやるしかなく演繹になっていると理解sta.icon ずれてる感じがするtakker.icon
そもそも数学的帰納法を帰納のイメージで捉えられないんじゃないかな
帰納はある性質Aを満たすサンプルkをたくさん集めることで、一般にAが成り立つ確率が高いことを示す
物理法則はすべてこれ
数学的帰納法はある性質Aを満たすサンプルkをたくさん集めるだけでは適用できない
以下を満たしたサンプルでないと使えない
サンプルに順番がある
前のサンプルから後ろのサンプルが性質Aを満たすことを示せる($ \forall \{k.A(k) \rightarrow A(k+1)\})
ドミノ倒しは数学的帰納法を説明するときに用いられることがあるたとえ 1と1+nで全ての例が証明されるから具体例を全部述べているよ、だから演繹的手続きと言えますという理解でいたcFQ2f7LRuLYP.icon
合ってるか不安。もっかい上を読もうかな
間違ってた、具体例から結論を導いている点が帰納で、この論の導出プロセスが演繹的手続き
帰納 or 演繹のどちらか片方だけを当てはめるという白黒ではなく、両方混ざってるパターンもあるということかsta.icon
takker.iconの理解
次の3つの論理式を用意する
$ P(1)
$ \forall n\in\N;(P(n)\implies P(n+1))
$ \forall P;\left(P(1)\land\forall n\in\N;(P(n)\implies P(n+1))\implies \forall n\in\N;P(n)\right)
これは一体…？cFQ2f7LRuLYP.icon
切れ目がほしいわね
括弧の対応がわからなくなるのはつらみかもtakker.icon
玉ねぎを剥くようにしてく必要がありますね(意味不明なたとえ)cFQ2f7LRuLYP.icon
中括弧を使ってみました！いかがですか！takker.icon
$ \forall P;\left(\begin{dcases}P(1)\\\forall n\in\N;(P(n)\implies P(n+1))\end{dcases}\implies \forall n\in\N;P(n)\right)
わかりやすくなりましたわね(わかったとは言ってない)cFQ2f7LRuLYP.icon
フム…なるほど…
全てのPは以下の条件を満たすよ
P(1)だよ(????)cFQ2f7LRuLYP.icon
以下の条件を満たす命題Pについて、全ての自然数nについて、P(n)が成立するよbiwa.icon
P(1)が成立する
全ての自然数nについて、P(n)が成立するときP(n+1)も成立する
翻訳感謝cFQ2f7LRuLYP.icon
具体例を示すbiwa.icon
命題Pとして、$ P(n): n = n というものを考える(雑)
$ P(1): 1 = 1は真
$ \forall n. (n = n) \to (n+1 = n+1) も真
$ Pは、前提を満たす
よって、$ Pは、任意の自然数について真と言える、みたいな？
そゆことtakker.icon
なお数学的帰納法の発明や命名はペアノの公理よりも前のはずですねnishio.icon
後付けで公理にしたことによって、数学的帰納法は論理的な正しさが保証される「演繹」になった
それまではきちんとした基礎付けはされていなかった
ですですtakker.icon
歴史的な経緯はすっ飛ばして書いちゃった
この3つに含意除去を適用することで$ \forall n\in\N;P(n)が示される 含意除去：「$ P」と「$ P\implies Q」から「$ Q」を導く操作のこと これ$ Pと P\implies QからQに見えて混乱したcFQ2f7LRuLYP.icon
「」をつけてみた。わかりやすくなったかな？takker.icon
知識不足でした。ごめんなさい
全称除去も演繹の一種では？biwa.icon
(このあと三段論法を付け足した)
準備
「$ aは死ぬ」を$ D(a)とする
人は必ず死ぬ：$ \forall h\in\text{humen};D(h)ー①
ソクラテスは人である：$ \text{Socrates}\in\text{humen}ー②
推論
1. ①に全称除去を適用して$ \text{Socrates}\in\text{humen}\implies D(\text{Socrates})(これを③とする)を導く
2. ③と②に含意除去を適用して$ D(\text{Socrates})を導く
3. おわり
こんな細かい事は、元記事の文脈では重要でないだろうし
三段論法では？biwa.icon
三段論法は$ P\implies Qと$ Q\implies Rから$ P\implies Rを導くことなので違いますtakker.icon
あっ違ったみたい
三段論法っていろんな種類があったのか
ソクラテスが言った三段論法は4つくらい型があった気がするので、takker.iconさんその1つっぽい だったようです……takker.icon
論理学だと仮言三段論法しかでてこないので気づかなかった(言い訳) 論理学関連の知識、形式論理学と(哲学的な)論理学の2つの文脈が存在するので、ちょっとややこしい biwa.iconの理解
公理として、$ \forall A. A(1) \land \forall k. \{A(k) \rightarrow A(k+1)\} \rightarrow \forall n. A(n) が存在しているため、数学的帰納法(の適用は)はただの演繹にすぎない
数学的帰納法は公理とせずとも、別の公理から導出可能な命題だった気もする
$ \forall A\in 2^\N\setminus\{\varnothing\}\exist m\in A\forall n\in A;m\le n
まあ、公理でなくても、真な命題として存在してれば良い
「公理として存在してるから演繹」と「数学的帰納法は演繹なのに帰納って名前に入ってる」は両立しないnishio.icon
「数学的帰納法」が命名されたタイミングではまだ公理に入ってなかったので時間軸がおかしい
命名のタイミングに注目するなら「公理として存在する」がFalse
公理に入った以降に注目するならその期間に命名はされてない
$ \forall A.の$ .や$ \forall n\in A;の$ ;はただの区切り文字。なくてもいい
$ :を使うこともある
$ \toと$ \impliesは、ここではどちらも同じ意味「ならば」で使用している
$ \begin{dcases}P\\Q\end{dcases}は$ P\land Qと同じ
書き方を変えただけ
数式が出てきた！cFQ2f7LRuLYP.icon
数式を読める人をみるとすげーって思うけど自分がくずし字を(ちょっと)読めるのと同じでただ読めるので読めるということなのかもしれない
自分がくずし字を(ちょっと)読めるのと同じこのたとえは別のとこでも出てきたtakker.icon
つなげたい
(ある人Aに)できないことが(ある人Bに)楽にできるとしたらそりゃあ僥倖だなあ
AにまかせてBは自分ができることにタスクを振れば良い
流儀が変わると一気に読めなくなるtakker.icon
スッと読めることはない
常に自分が理解できる流儀に書き換えてから理解しています
（自分は∀とか∈とかの意味すら怪しい素人なので読み飛ばすことしかできないが……）
この資料は知らなかったtakker.icon
読んでみました。おすすめできます