Is Minimal counterexample proof just induction in disguise?

Question

Since basically what we do is we prove that p(k)=>p(k+2) or p(k+1)=>p(k+2) and so on by just adding a couple of base steps. Am i right here? That is what it seems to me. Please correct me if i am wrong

Answer 1

Yes, if you prove something by showing that a minimal counterexample would necessarily lead to an even smaller counterexample (and so, contradiction), that is the same thing as the induction principle.

Often the same proof can easily be framed as an induction proof or as a minimal counterexample proof. However, it does also happen that one of the two is a "natural fit", and the other would be much more awkward to write down. For example, think of the familiar proof that $\sqrt{2}$ is irrational, where you assume that $\sqrt{2} = \frac{p}{q}$ with no common factors (so, a minimal pair among all possible $p,q$), and then deduce that actually both $p$ and $q$ have to be even, so you can divide both by $2$ and the counterexample is not minimal after all. You could rewrite this proof as an induction proof, but it would look awkward and harder to understand.

Answer 2

Yes, your intuition is correct. The precise way to formulate (and prove) your claim is that the principle of induction is equivalent to the well-ordering principle or $\mathbb N$, namely that every non-empty subset of the naturals has a smallest element. The proof is not at all hard.