An issue of understanding the inductive step in proof by induction

Question

Induction step: We assume that P(k) is true and then we need to show that P(k+1) is true as well.

If k is arbitrary and we assume it's correct, then how come one can't say,

j = (k+1)

and assume p(j) is true because j is arbitrary just like k and it has the same form of p(k).

That logic sounds incorrect, but technically, if k is arbitrary, meaning any (all?) value for P(x), then why would P(k+1) be false ever if P(k) is true.

Perhaps the answer lies with your definition of arbitrary. Consider this example of arbitrary used in the rule of Universal Instantiation

Rule:

(FOR ALL x) P(x) => P(c) where c is some arbitrary element of the universe.

Here, arbitrary means c could be literally any value (in the universe of course). Assume the universe for an example of universal instantiation is all integers. Then if P(c), then P(c + 1) is also true. I don't think that can be argued here.

So why then, can P(k + 1) not automatically be assumed true by P(k)? I believe the real issue here is the meaning of arbitrary, perhaps there are two different types of arbitrary? What is wrong here?

Would you consider "k" to be arbitrary? My issue is that if you call it arbitrary, why then for the rule of UI can P(c) where c is arbitrary mean to say that c means "every" because it's arbitrary.

Answer 1

One is not assuming that $P(k)$ holds for all $k$ in proving a statement by induction. Rather we are trying to prove that if $P(k)$ happens to hold for a particular (but unspecified) $k$ then $P$ will hold for the next i.e. $k+1$ term. We cannot say "assume $P(k)$ is true for an unspecified $k$, then let this unspecified $k$ be $k+1$". Once we have assumed that $P(k)$ is true (for this $k$ only!*) this is all we know and we assume no more. It is our task to establish that $P(k)$ being true implies $P(k+1)$ is true.

*A caveat here is when one uses strong induction, thereby assuming $P$ is true for all natural numbers up to and including $k$. We still are not assuming $P(k+1)$ though, that is on us to prove given that $P$ is true for everything before $k+1$.

Answer 2

In the induction step of an induction proof, you first choose an arbitrary natural number $k$, then assume that $P(k)$. From that you derive $P(k+1)$, and then discharge the assumption. This gives you the conclusion "$P(k)$ implies $P(k+1)$". At this point, no assumption about the validity of $P(k)$ is made anymore. After this you discharge you choice of $k$ and get the conclusion "for all natural numbers $k$, $P(k)$ implies $P(k+1)$". After this, you have not even picked any particular $k$ anymore.

Answer 3

The induction schema states that if $\phi$ is a unary predicate such that $\phi(0)$ and $\phi(n)$ implies $\phi(n + 1)$, then $\phi(n)$ for all natural numbers $n$. For each unary predicate $\phi$, there is an instance of the induction schema corresponding to $\phi$. Suppose that we are demonstrating by induction that $\phi(n)$ holds for all natural numbers $n$, and we have already demonstrated that $\phi(0)$ holds. According to the induction principle for $\phi$, we have to show that $\phi(n)$ implies $\phi(n + 1)$ for all natural numbers $n$. After doing this, the induction principle for $\phi$ will give $\phi(n)$ for all $n$.

The statement we must prove has the form $\forall n (\phi (n) \rightarrow \phi(n + 1))$. This statement consists two parts. The first is the conditional $\phi(n) \rightarrow \phi(n + 1)$. The second is the universal generalization of this statement. We see that in order to prove this statement, we first have to prove the conditional statement by assuming $\phi(n)$ and demonstrating $\phi(n + 1)$, discharging the assumption $\phi(n)$ and concluding that $\phi(n) \rightarrow \phi(n + 1)$. Because $\phi(n)$ has been discharged, no open assumptions contain the variable $n$, permitting an application of the rule for universal generalization.

The important point is that we don't assume $\phi(n)$ for all $n$, only a particular $n$. The induction principle for $\phi$ doesn't permit the derivation of $\phi(n) \rightarrow \phi(n + 1)$ for all $n$. Rather, it states that if this statement is provable, then $\phi$ holds for all natural numbers $n$. I hope this was helpful.

Answer 4

This is invoking what we know as Implication Elimination. You assume that the statement is true for "a particular $k$" i.e. $\phi(k)$ is true for some $k \in \mathbb{N}$ with which you're testing if you can arrive at a conclusion for $\phi(k+1)$ given the assumption that $\phi(k)$ is true. We're not assuming anything about $\phi(k+1)$. In short, if $\phi(k) \implies \phi(k+1)$ only then you arrive at the conclusion that $\forall k\in \mathbb{N}(\phi(k) \implies \phi(k+1))$. Also your statement

If k is arbitrary and we assume it's correct, then how come one can't say, j = (k+1) and assume p(j) is true because j is arbitrary just like k and it has the same form of p(k).

You yourself are pointing out if you said that $j=k+1$, then you're again assuming that $\phi(k+1)$ is true and not proving it is true. Where is the proof?

but technically, if k is arbitrary, meaning any (all?) value for P(x), then why would P(k+1) be false ever if P(k) is true.

You're not assuming $\phi(k)$ for all $k$; you're rather only assuming it for a particular $k$ but be it any $k$. Here's where you're getting confused I believe. You can assume that it is true for ANY "ONE" $k$ but ANY "ONE" doesn't mean EVERY.

Answer 5

You can understand induction by the domino effect. Consider you have a stack of dominoes. Number them as 1,2,3...

Now P(1) represents the value of the function at n=1 P(2) at n=2 and so on. Proving that a particular value is true means that we topple that domino.

Hence in induction you show that if you topple the first domino and you observe that some random $n^{th}$ domino has fallen and you can prove that because the $n^{th}$ domino has fallen,the $(n+1)^{th}$ domino will also fall is the principle of induction.