1

The axiom of induction in logical symbols is: $$ \forall P[[P(0) \land \forall k \in N (P(k) \implies P(k+1))] \implies \forall n \in N[P(n)]] $$

If $P(0)$ is true and $P(k)$ is false (therefore $P(k) \implies P(k+1)$ is true), does it mean $P(n)$ is true?
I understand induction, but not implication.

kptlronyttcn
  • 391
  • In order to "cancel" your doubts, please think at modus ponens; also in this case we have the "annoying" effect of the truth-conditions of the conditional. MP says that, form $A \supset B$ and $A$ we may infer $B$; asserting $A \supset B$, we "exclude" the case $A$ true and $B$ false; when we assert also $A$, we "exclude" the two cases when $A$ is false. What is left: the case when $B$ is true, as expected. In the induction axiom, is the clause $P(0)$ that "exclude" the unwanted case when the conditional is true because its antecedent is false. 1/2 – Mauro ALLEGRANZA Mar 22 '14 at 13:23
  • The fact that both $P(0)$ and that $\forall k(P(k) \supset P(k+1))$ are true "bootsrap" the process (as explained by Henning) because the two license us to infer $P(1)$, and so on ... is a sort of "infinite chain" of modus ponens. 2/2 – Mauro ALLEGRANZA Mar 22 '14 at 13:26

1 Answers1

4

It may help to read $P(k)\Rightarrow P(k+1)$ as "it is not possible for $P(k)$ to be true while $P(k+1)$ is false".

In itself it is possible for $P(k)\Rightarrow P(k+1)$ to hold if $P(k)$ is false -- but in the specific context of induction this will not happen, because the truth of $P(k)$ is already guaranteed by $P(0)$ and the earlier instances of the induction step.

Note that $P(k)\Rightarrow P(k+1)$ has to be proved for every possible $k$, not just for a particular one.

One way to think of induction is to consider an indirect proof. Suppose that $P(0)$ and that $P(k)\Rightarrow P(k+1)$ for all $k$. Now assume for a contradiction that $P(n)$ is not true for all $n$. Then there must be a smallest $n$ such that $P(n)$ fails.

This smallest $n$ cannot be $0$, because we're explicitly assuming $P(0)$. So $n-1\ge 0$. Consider the particular instance of $P(k)\Rightarrow P(k+1)$ that has $k=n-1$. This says $P(n-1)\Rightarrow P(n)$, or in other words it is not possible for $P(n-1)$ to be true while $P(n)$ is false. But that is exactly the situation we're in here, because $n$ was the first $n$ such that $P(n)$ is false, so $P(n-1)$ is true. This is a contradiction, so our assumption that $P(n)$ is false for some $n$ must be rejected.

hmakholm left over Monica
  • 286,031
  • are you saying because P(0) is true, and k is ranging over all natural numbers (including 0), then for P(k) we are stuck by assuming it's true? – kptlronyttcn Mar 22 '14 at 12:19
  • 1
    @kptlronyttcn: I don't think it is fair to express it as "we're stuck" -- because the truth of $P$ is exactly what we're aiming to prove! What the induction step says is "if we know $P(0)$ then $P(1)$, and if we know $P(1)$ then $P(2)$, and if we know $P(2)$ then $P(3)$ and so on forever". The $\forall k$ is a way to express that we're proving all of these (infinitely many) steps at once, and the induction rule is then just a formalization of the intuitive fact that we can stick them together to establish the truth of $P(n)$ for any $n$ we'd like to. – hmakholm left over Monica Mar 22 '14 at 12:24