Confused with using Proof by Smallest Counterexample

[RichardParker]

When proving by smallest counterexample, you assume an integer k>1 where it is the smallest integer for which statement S_n is false. Then you proceed to prove that S_k-1 implies S_k. Where you deduce a contradiction by which k is true.

Can't you prove this directly by assuming S_k-1 is true and showing that S_k-1 implies S_k since you will end up with a true k anyhow?

 

[RichardParker]

I think I get it now...

In mathematical induction you prove that given any k>=1, if S_k, then S_k+1. But in the proof by smallest counterexample S_k-1 is used instead.

Is that okay?

 

[HallsofIvy]

This is really just "proof by induction" isn't it?

In "proof by smallest counter example", of a statement about the positive integers, you are saying "if it were not true, then there would be a smallest counterexample, k. Since k is the smallest counter example the statement must be true for k- 1 (Of course, you would have to check that 1 is not a counterexample!). If you can show that k-1 being true implies k being true, you have a contradiction.

So you must prove (i) that the statement is true for n= 1 and (2) if it is true for k-1 then it is true for k. Yes, that is exactly "proof by induction".

 

[spamiam]

Strong induction comes from the well-ordering of the positive integers. The well-ordering principle states that every nonempty set of positive integers has a smallest element.

When trying to prove the proposition S(n) for all pos. integers n, we consider the set
$$\{n \in \mathbb{Z}^+ : S(n) \, \text{is false}\}$$

If this set is nonempty, then it has a smallest element k. Since k is the smallest element, then for all n less than k, S(n) must be true.

 

[disregardthat]

The principle of natural induction is equivalent to that every non-empty set of naturals has a least element. This is a good beginner exercise in proofs. This fact allows us to always consider the "least counter-example" if it exists.

 

[Robert1986]

I'm guessing this is for a combinatorics question, right? The technique to which you are referring is extremely popular in combinatorics, but not really in other areas of math. This is because it isn't *really* a "proof by induction". That is, you don't assume that it is false for k and true for k-1, then show that it is true for k. Instead, you assume that it is false for k and true for k-1. Then, you use this to come up with some sort of contradiction. So, you might never really prove directly that if the statement is true for k-1 then it is true for k.

So, what HallsOfIvy (and the others) have said is partially correct, and partially incorrect. If you end up showing that the statement being true for k-1 implies that it is true for k, then yes, you have just done regular induction, and you need to show that it is true for some base case.

On the other hand, if you do what is usually the case (in my, admittedly limited experience) when using a proof by smallest counter example, you show that the fact that it is true for k-1 and false (by assumption) for k there is some contradiction, somewhere. The contradiction is not necessarily that the statement is, in fact, true for k. In fact, if this is the contradiction, then it falls in the case above and it is just regular induction. Usually the contradiction is that a hypothesis in the theorem fails to hold.

 

[disregardthat]

I'm guessing this is for a combinatorics question, right? The technique to which you are referring is extremely popular in combinatorics, but not really in other areas of math. This is because it isn't *really* a "proof by induction". That is, you don't assume that it is false for k and true for k-1, then show that it is true for k. Instead, you assume that it is false for k and true for k-1. Then, you use this to come up with some sort of contradiction. So, you might never really prove directly that if the statement is true for k-1 then it is true for k.

If "k is false" implies a contradiction then by the law of excluded middle it is true for k. This process is logically equivalent to mathematical induction, it has nothing to do with the technique of proof.

 

[Robert1986]

If "k is false" implies a contradiction then by the law of excluded middle it is true for k. This process is logically equivalent to mathematical induction, it has nothing to do with the technique of proof.

True, the two things might be logically equivalent, but the actual process of working through the proofs are much different, IMO.

In one (for lack of a better term, let's call if "classical induction"), you usually use the fact that a given statement is true for k-1 to prove directly from that assumption (and from any hypothesis made in the statement of the theorem/problem) is true for k. It is never assumed that the statement is false for k, and so this assumption is not used during the proof.

Using proof by smallest counter example, you never directly prove that the truth of the statement for k-1 implies the truth of the statement for k. Instead, you use the fact that it is false for k (by assumption), and true for k-1, then you come up with some contradiction.

There are many times in combinatorics where a proof by "classical induction" is much harder than a proof by smallest counter example. Or, many times, a proof by smallest counter example sheds more light on what is actually going on than a proof by "classical induction".

 

[RichardParker]

Thanks for all your replies. :)

Especially to Robert.

 

[disregardthat]

There are many times in combinatorics where a proof by "classical induction" is much harder than a proof by smallest counter example. Or, many times, a proof by smallest counter example sheds more light on what is actually going on than a proof by "classical induction".

A proof by "classical induction" may very well assume that the statement for k is false and derive a contradiction. This doesn't change the fact that it's a proof by induction. All you stand with is: the statement is true for 0,1,...,k-1, and what you have to prove is the statement for k, in whatever manner you prefer, directly or by contradiction.

While I agree with you that a direct proof often is more instructive, it doesn't mean that a proof by contradiction isn't induction.

 

[manoguru]

Hi Richard,

If I am getting what your confusion is, then I think this is what you are confused about. In the standard induction method, we do the following:

1) Base case: P(0) true
2) Inductive hypothesis: P(n) true
3) Inductive step: If P(n) true => P(n+1) true.

However, we can make a variation in step 3, by using its contra-positive statement. That is, we show that:

2') Inductive hypothesis: P(n) false
3') Inductive step: If P(n) false => P(n-1) false.

Obviously taking step 1 and 3' together leads to a contradiction since P(0) gives a counter example.

I hope this helped.

Regards,
Sudarshan