2

Say whether the following verification of the method of induction is valid or not?

Proof: We have to prove that if

  • $A(1)$
  • $(∀n)[A(n) ⇒ A(n + 1)]$

then $(∀n)A(n)$.

We argue by contradiction. Suppose the conclusion is false. Then there will be a natural number n such that: not $A(n)$. Let m be the least such number. By the first condition, $m > 1$, so $m = n + 1$ for some n. Since $n < m, A(n)$. Then by the second condition, $A(n + 1)$, i.e., $A(m)$. This is a contradiction, and that proves the result.

The answer to this question is that the proof is valid. But I do not understand the reasoning in the proof at: Since $n < m, A(n)$. Could someone please explain what we are considering here? Why is it $A(n)$?

maxloo
  • 151

2 Answers2

1

You are assuming that $m(=n+1)$ is the smallest natural for which $\neg A(m)$. Since $n<m$, $n$ is smaller that the smallest natural for which $\neg A(m)$, and therefore $A(n)$.

José Carlos Santos
  • 427,504
0

$A(n)$ holds by the way you chose $m$. You write "Let $m$ be the least such number." this means $m$ is the least natural number such that $\neg A(m)$, or as a formula $$ m = \min \{n : \neg A(n) \} $$ As $m$ is the least number for which $\neg A(m)$ we must have $A(n)$ for all smaller $n$, that is for all $n < m$ we have $A(n)$.

martini
  • 84,101