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

score 2 · Accepted Answer · answered Nov 01 '15 at 07:27

2

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.

answered Nov 01 '15 at 07:27

AnatolyVorobey

2,452

1

Alright great, i am talkiong in general proof that you would normally do with induction. I have no idea how the proof of irrationality of root of 2 would look like :D – Sorfosh Nov 01 '15 at 07:29
It isn't very difficult :) Suppose $\sqrt{2}=p/q$ where we already canceled everything we could in $p/q$ so it's a reduced fraction. Then, squaring both sides, $2=p^2/q^2$, therefore $2q^2=p^2$. The left side is even, so the right side must be even. But if $p^2$ is even, so is $p$, and we can write $p=2m$ for some $m$. Then $2q^2=4m^2$ and canceling $2$ we get $q^2=2*m^2$. Now the right side is even, so the left side must be, and since $q^2$ is even, so is $q$. We reached the contradiction: we deduced that both $p$ and $q$ are even so the fraction is not reduced after all. – AnatolyVorobey Nov 01 '15 at 07:52
I am talking about the proof using induction ^^. But thanks for the whole work here... – Sorfosh Nov 01 '15 at 08:20

score 1 · Answer 2 · answered Nov 01 '15 at 07:39

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.

Is Minimal counterexample proof just induction in disguise?

2 Answers2