Proof by induction v. Proof by smallest counter-example

Question

It seems like proof by induction and proof by smallest counter example can be used pretty interchangeably. Is this true? If so, what are some things that guide you towards one or the other?

Answer 1

These two methods are quite similar and whenever a statement can be proved by one of them then it can also be proved by the other one. But, in some cases it is simpler to make a proof by smaller counter-example than by induction. Take, for instance, the statement “every natural number can be written as a sum of distinct powers of $2$ (including $1=2^0$)”. It is possible to prove it by induction, but it is easier to prove it by smallest counterexample: if $N$ is the smallest natural number wich cannot be written as a sum of distinct powers of $2$, then $N$ is either odd or even.

• If it is odd, $N-1$ can be written as a sum of distinct powers of $2$ ($N=2^{a_1}+2^{a_2}+\cdots+2^{a_k}$), none of which can be equal to $1$ (otherwise, $N-1$ would be odd). But then $N=2^0+2^{a_1}+2^{a_2}+\cdots+2^{a_k}$.
• If it is even, then$$\frac N2=2^{a_1}+2^{a_2}+\cdots+2^{a_k}\implies N=2^{a_1+1}+2^{a_2+1}+\cdots+2^{a_k+1}.$$

Answer 2

It seems like proof by induction and proof by smallest counter example can be used pretty interchangeably. Is this true?

Yes, the two methods are logically equivalent.

For example, suppose you do a proof by smallest counter-example, and suppose that the assumption that $n$ is the smallest counter-example allows you to show that $n-1$ is a counterexample as well. Well, then you have in effect proven that:

$$\neg P(n) \to \neg P(n-1)$$

but by contraposition this is equivalent to:

$$P(n-1) \to P(n)$$

and that of course we recognize as the inductive step of 'weak' induction.

A more common situation is that assuming that $n$ is the smallest counterexample allows you to find some smaller counter-example $m < n$. However, in that case you have in effect shown that

$$\neg P(n) \to \exists m (m < n \land \neg P(m))$$

which (again by Contraposition) logically equivalent to:

$$\neg \exists m (m < n \land \neg P(m)) \to P(n)$$

and thus to:

$$\forall m (m < n \to P(m)) \to P(n)$$

which is the core component of the principle of 'strong' or complete induction:

$$\forall n (\forall m (m < n \to P(m)) \to P(n)) \to \forall n \ P(n)$$

Indeed, the same logic applies to Proof by Infinite Descent as well. In Infinite Descent you prove that no number has a certain property by proving that for any natural number with a certain property there is always a smaller number with that property. That is, we show:

$$P(n) \to \exists m (m < n \land P(m))$$

but this is equivalent to:

$$\forall m (m < n \to \neg P(m)) \to \neg P(n)$$

and thus the Proof by Infinite Descent which says:

$$\forall n (P(n) \to \exists m (m < n \land P(m))) \to \forall n \ \neg P(n)$$

is equivalent to:

$$\forall n (\forall m (m < n \to \neg P(m)) \to \neg P(n)) \to \forall n \ \neg P(n)$$

and is therefore once again equivalent to complete induction, just with the 'property' of the negation of a certain property.

Then again, sometimes the contradiction you obtain in the method of Proof by Smallest Counterexample is not so much that you can find a smaller counter-example, but you get a contradiction in some other way. JoseCarlos' example is a good example of that. However, even in that case, notice that assuming that $n$ is the smallest counterexample is making the assumption that $\forall m (m < n \to P(n))$, and so if the additional assumption of $\neg P(n)$ leads to a contradiction, then we have in effect shown that:

$$(\forall m (m < n \to P(n)) \land \neg P(n)) \to \bot$$

which is logically equivalent to:

$$\forall m (m < n \to P(n)) \to (\neg P(n)) \to \bot)$$

and thus to:

$$\forall m (m < n \to P(n)) \to P(n)$$

which, again, is the core of complete induction.

(maybe a little cleaner would be to say that the existence of a counter-example, and thus of a smallest counterexample leads to a contradiction:

$$\exists n (\forall m (m < n \to P(n)) \land \neg P(n)) \to \bot$$

and thus:

$$\neg \exists n (\forall m (m < n \to P(n)) \land \neg P(n))$$

which is:

$$\forall n (\forall m (m < n \to P(n)) \to P(n))$$

If so, what are some things that guide you towards one or the other?

As you realize, logical equivalence does not mean that they are equally easy to use given some specific problem. Indeed, in some scenarios, one method is easier, but in others, the other. Are there any guidelines that will 'guide you towards one or the other'? Well... I'm not really sure. All I will say is this: Practice will certainly do a lot in learning to get a feel for which kinds of cases which method might be easier to use.