Mathematical Proof/Methods of Proof/Counterexamples

A proof by counterexample is not technically a proof. It is merely a way of showing that a given statement cannot possibly be correct by showing an instance that contradicts a universal statement. For example, if you are trying to prove the statement "All cheesecakes are baked in Alaska." and you did not know whether to prove it by contrapositive or contradiction, all I would have to do is bake a cheesecake right in front of you here in Texas and then you would know that your efforts had been in vain.

Consider the following statement:

Every set is countable.

Of course a counterexample to this would be the interval from [0,1] \subset \mathbb{R}. To show that this interval isn't countable, we assume that it is, so then there is a bijective function f:\mathbb{N} \rightarrow \mathbb{R} since f is bijective we may write the elements of  [0,1] in a list here we write the numbers in  [0,1] in their decimal expansions.

f(1) = .b_{(1,1)} b_{(1,2)} b_{(1,3)} b_{(1,4)} \ldots

f(2) = .b_{(2,1)} b_{(2,2)} b_{(2,3)} b_{(2,4)} \ldots

f(3) = .b_{(3,1)} b_{(3,2)} b_{(3,3)} b_{(3,4)} \ldots


For the purposes of the proof, we need each real number to be uniquely defined by a decimal. This is of course true in almost all cases (take .01, for instance... it's equal to .00999999999...). In fact, the cases when it's not true are exactly the cases when the decimal ends in a string of zeros, or "terminates" (a separate proof would be needed for this, but for now accept it as true). Therefore, let the decimals all be in "nonterminating form," so that there's another bijection between the decimal expansions and the real numbers.

Now let  a_i = 0 if  b_{(i,i)} is odd and 1 if  b_{(i,i)} is even. Now I claim that  x = .a_1a_2a_3a_4 \ldots is not listed here. To show this suppose it were then for some  n \in \mathbb{Z}, f(n)=.b_{(n,1)}b_{(b,2)} \ldots b_{(n,n)} \ldots but  a_n = 0 if  b_{(n,n)} is odd and  a_n = 1 if  b_{(n,n)} , this is not possible so we conclude that  .a_1a_2a_3a_4 \ldots is not in the list, this shows we may not have a surjection from  \mathbb{N} \rightarrow \mathbb{R}

Although this is a counterexample, we still had to PROVE that it was in fact a counterexample and in doing so used both a proof by contradiction (this was the overall method of the proof) by a construction (of  x = .a_1a_2a_3a_4 ). Although there may be more then one counterexample to any given false claim, you must always provide by a proof or argument that your counterexample works.

Answers | Next section
Last modified on 5 September 2009, at 19:19