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$

$\vdots$

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_{1}a_{2}a_{3}a_{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_{1}a_{2}a_{3}a_{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_{1}a_{2}a_{3}a_{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.