Logic and Principle of Induction

Question

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.

Answer 1

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.

Answer 2

It appears as if you've forgotten about the tautologies in 2-valued propositional logic. They qualify as true in 2-valued logic regardless of the truth value of their atomic components. You also don't necessarily need to work with semantical concepts like truth-values. You can start with syntactical ones, and just assume that some model exists for which your reasoning qualifies as sound. If someone objects, you just say you work in some subsystem of some part of 2-valued logic and then you just claim that you study some subset of ordinary 2-valued logic. So, you do have a notion of truth. Starting with syntactical concepts might seem too hard and fruitless, but there do exist automated reasoning programs out there to assist you in this regard.

When working with the schema of reasoning known as mathematical induction, you don't assume that a formula holds for all members of the sequence. You assume that it holds for some k of the sequence, which you do not name. Then you show that no matter what actual member of the sequence k you would choose to pick, the same property will hold for the next term S(k) (the successor of k) of the sequence. Since you work with a sequence, and you have a base case, you can then infer that since the property holds for the first member of the sequence, then it will hold for the second. Since it holds for the second it then holds for the third. Since it holds for the third it then holds for the fourth, and so on until the sequence ends if finite. For an infinite sequence, there does not exist any way to actually have a proof of the for all statement in then sense of a formal proof. However, you do have a schematic argument which no one can refute at any step of the way.

Answer 3

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.