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.
Please correct me, if needed.
Best Answer
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.