Mathematical Induction

The name may be Mathematical Induction, but it is actually one of the methods of deduction.

When expressed in predicate logic, it becomes simpler to think about (in my personal opinion) (takker).

• When expressed in logical formulas, it looks like the following:
  • $\{\begin{array}{l}P(1)\\ \forall n\in \mathbb{N};P(n)⟹P(n+1)\end{array}$
  • The point is that $n$ is a bound variable in the second formula.
    • Is it correct to understand it as declaring a variable with $\forall n$? (blu3mo)
      • That’s right! (takker)
    • By the way, $\forall$ and $\exists$ can also be imagined as $\wedge$ and $\vee$, respectively.
      • $\forall x;P(x)$→ $P(x_0)\wedge P(x_1)\wedge P(x_3)\wedge \cdots$
      • $\exists x;P(x)$→ $P(x_0)\vee P(x_1)\vee P(x_3)\vee \cdots$
      • If you are unsure about the interpretation of $\forall$ and $\exists$, you can think of them as described above.
        • However, be careful as this interpretation can sometimes lead to confusion.
    • It is exactly the same concept as a local variable in programming.
    • In high school mathematics, they sometimes use different variable names for the proof, but as long as the variable scope is clearly defined, it is fine to reuse the same variable name.
      • I see, I was wondering why they use k (blu3mo)
      • I really think it’s evil that they don’t explain this in school (assuming there are high school students who understand predicate logic) (takker)
        • If programming becomes a required subject, it might be easier to teach.
  • There is no specific order to prove these formulas, so it’s okay to prove the lower formula first.
  • This logical formula also appears in the section on Peano Axioms in the book “Mathematical Girl,” so it might be helpful to refer to it.

The transformed version of mathematical induction can be derived from this logical formula.

• The key is to interpret it as $\forall P\{\begin{array}{l}P(1)\\ \forall n\in \mathbb{N};P(n)⟹P(n+1)\end{array}$.
  • Since $P$ is arbitrary, you can throw in any logical formula you like!
• Then, adjust the content of $P$ to suit the proof problem where you want to use mathematical induction.