# Logic and Principle of Induction

I started studying about the mathematical principle of induction recently and i concluded that the mathematical principle of induction applied in some set N , to prove some property p for elements greater than 0, could be summarized as saying that the following statement is true :

$$\left[p(0) \text{ and } \forall k: \left( p(k) \implies p(k+1) \right) \right]\iff \forall n: p(n)$$

To generalize about any property, we could resort to second-order logic.

My problem is with the second premisse of the left-side of the biconditional: $$( \forall k: ( p(k) \implies p(k+1) ) )$$
By propositional, FOL or Second-order-logic to show that the conditional $p(k) \implies p(k+1)$ is true, we would need to show that either the antecedent is false ( which would be inconsistent with $p(0)$) or showing that both the antecedent and the consequent is true.
But well, if we could show that the antecedent or the consequent would be true $\forall k$ then we wouldn't need mathematical induction.

So, i came to believe that there's another way decide the truth-value of a conditional , in a way that it doesn't depend primarily on the truth-value of neither the antecendent or the consequent.

I have two questions, both in which answers would be tremendously helpful :

1 - What would ( specifically ) be this another way to affirm that the truth-value of a conditional is true, without resorting to LOGIC ? I have done a bunch of examples, and i know roughly what it's all about, but i don't know exactly that I'm doing or what thing I'm doing represents.

2 - Are we stepping outside of propositional logic and FOL, here ?
In one hand, propositional logic defines the truth-value of a conditional to depend entirely on the truth-value of it's atomic formulas.
On the other hand, the principle of mathematical induction provides a way to define the truth-value of a conditional of FOL without resorting to the truth-value of it's atomic formulas. Is there some inconsistency ? Is there something I'm missing ? Are there statements that can be proven only by induction?

I'm just confused about the relation between the conditional definition in Mathematical logic, and the mathematical principle of induction.

P.S : As i started studying this subject just recently, i might have misunderstood something and might be assuming something that is extremely wrong.

• You might want to use a page like this to help your posts look better: artofproblemsolving.com/Wiki/index.php/LaTeX:Symbols Jul 5, 2013 at 1:34
• Propositional logic is not the relevant one here, since any instance of the induction scheme involves quantifiers. This was made clear in your fourth line. Jul 5, 2013 at 2:05
• Have you seen examples of induction used? You don't need to specifically prove one of $A$ or $\lnot B$ to prove $A\implies B$. Jul 5, 2013 at 2:14
• @AndréNicolas You do need more than propositional logic here, yes. However, you still need propositions, and thus you still need to keep propositional logic in mind. Jul 5, 2013 at 2:18

You seem to have misplaced a quantifier. It is true, as you said, that $p(k)\implies p(k+1)$ is logically equivalent to $(\neg p(k))\lor(p(k)\land p(k+1))$, and therefore the second premise of the induction axiom, $(\forall k)\,[p(k)\implies p(k+1)]$, is equivalent to $(\forall k)\,[(\neg p(k))\lor(p(k)\land p(k+1))]$. But then you went from this statement to $$[(\forall k)\,\neg p(k)]\lor[(\forall k)\,[p(k)\land p(k+1)].$$ This "distribution of $\forall$ over $\lor$ is not valid. The correct formula allows the possibility that $\neg p(k)$ holds for some values of $k$ and $p(k)\land p(k+1)$ holds for all the other values of $k$. The transformed formula requires the same alternative to hold for all $k$, and this is something quite different.
I take the implication '$p(k)\rightarrow p(k+1)$'. If one fails to prove $\exists{k}\colon p(k)\wedge \neg p(k+1)$ then $\forall{k}:p(k)\rightarrow p(k+1)$. In words: it has to be independent of the choice of k to start with p(k) arriving at p(k+1). Finding a proof of p(k+1), given p(k), can be very difficult. I was told that using induction is a proof of complete intimidation. Thus, choose $k_0$ at random, accept $p(k_0)$ as being true, consider then $p(k_0+1)$. Either you can prove $p(k_0+1)$ holds and then $\forall{k}\colon p(k)$ holds, or else it does not hold and then you disproved something.