Is a counterexample considered a rigorous proof that a property is not true?

Solution 1:

The statements that are relevant here are called universal statements (because they involve a universal quantifier). These are the statements of the form "for all foos, statement(foo) is true." Many things you will be asked to prove in mathematics are universal statements, but we are also interested in non-universal statements.

The negation of a universal statement is an existential statement (because it involves an existential quantifier). More precisely, the negation of the universal statement "for all foos, statement(foo) is true" is the existential statement "there exists a foo such that statement(foo) is false."

Disproving a universal statement means proving its negation, which is an existential statement. To prove an existential statement, it is sufficient to provide a single example. This is more or less what an existential statement means. That is, if I want to prove that there exists a foo such that statement(foo) is false, all I have to do is find one and show it to you.

Solution 2:

Yes, a single counterexample is a rigorous proof that an assertion is false. One can often say more, of course: it might be possible, for instance, to exhibit a whole class of counterexamples, or even to show exactly when the assertion is true and when it’s false. It might be possible to show that if the hypotheses are strengthened slightly, the assertion is true. But all it takes to refute the assertion is one counterexample.

Solution 3:

As an addendum to the other answers, I wanted to point out that theorems of the form

If $P(x)$, then $Q(x)$

are usually implicit universal assertions of the sort “for all $x$, if $P(x)$, then $Q(x)$”.

So, to prove an implication is not a theorem, it suffices to find a counter-example: a single object $x$ for which “if $P(x)$ then $Q(x)$” is not true, which is equivalent to saying that “$P(x)$ is true but $Q(x)$ is false”.

Solution 4:

Generally statements of the form "$2^n-1$ is always a prime" are translated to "$\forall n\in\mathbb N: 2^n-1$ is a prime".

To show that a statement of the form $\forall x\varphi(x)$ is false it is enough to show one counterexample. That is we prove the negation of the statement, which translates to $\exists x\lnot\varphi(x)$. To prove that there is some number with property $\lnot\varphi(x)$ it is enough to exhibit one which does.