数学的帰納法

Last updated Unknown Edit Source

数学的帰納法

述語論理式で書けば考えることがシンプルになる（あくまで個人の意見です）

• 論理式で表すと以下のようになる
  • $\begin{dcases}P(1)\\forall n\in\Bbb{N};P(n)\implies P(n+1)\end{dcases}$
  • 第二式で$n$が束縛変数になっているのがポイント - ∀nで変数を宣言しているみたいな理解で良いのかな - そゆことです！ - ちなみに$\forall$と$\exists$はそれぞれ$\land$と$\lor$でイメージする事もできます - $\forall x; P(x)$→ $P(x_0)\land P(x_1)\land P(x_3)\land\cdots$ - $\exists x; P(x)$→ $P(x_0)\lor P(x_1)\lor P(x_3)\lor\cdots$ - $\forall$と$\exists$の解釈で迷ったときは上記のように考えてみるのも手 - ただこの解釈で詰まることもあるので注意
    • programmingでいうローカル変数と全く同じ概念
    • 高校数学ではわざわざ別の変数名を使って証明を書いていたりするが、変数のスコープさえきっちり分けていれば、同じ変数名を使い回したってかまわない
      • なるほど、なんでkを使うんだろうと気になっていた
      • この辺を学校で説明しないのほんとevilだとつくづく思います(なお述語論理を理解できる高校生の人数)
        • programmingが必修になれば、楽に教えられるようになるかもしれない
  • 証明する順番なんてないので、先に下の式を証明しちゃっておｋ
  • この論理式は数学ガールのペアノ公理

    ペアノ公理

    PA1 1は自然数である。 PA2 どんな自然数nに対しても、succ(n)は自然数である。 PA3 どんな自然数nに対しても、succ(n)≠1が成り立つ 1はどんな数字のsuccでも無い、と言っている PA4 異なる自然数は異なる後者を持つ：a ≠ b のとき suc(a) ≠ suc(b) となる。 ...

    1/3/2023

    の節でも登場しているので、参照してみるといいかもしれません

数学的帰納法の変形ver.も、この論理式から全部導出できる

• $\forall P\begin{dcases}P(1)\\forall n\in\Bbb{N};P(n)\implies P(n+1)\end{dcases}$みたく解釈するのがミソ
  • $P$が任意なので、自分の好きな論理式を何でも放り込める！
• あとは数学的帰納法を使いたい証明問題に沿うよう$P$の中身を適当に調節して放り込めばおｋ