Counterexamples and If and Only If

Demolish false claims with a single counterexample. Four plausible claims go on trial, one by one.

A 'for all' claim falls to one counterexample. A single failing case makes the whole claim false. An if-and-only-if claim is the opposite job. Each direction needs its own separate proof.

For example, take 'every 🧑 classmate wears glasses'. One classmate without glasses ends the claim. One person is enough.

Examples & Exercises

Counterexample

Disprove the claim "if $n^2$ is divisible by 4 then $n$ is divisible by 4" using the counterexample $n = 2$ . Write out the claim's logical form $\forall n \in \mathbb{Z}\,(4 \mid n^2 \Rightarrow 4 \mid n)$ and its negation $\exists n \in \mathbb{Z}\,(4 \mid n^2 \text{ and } 4 \nmid n)$ explicitly, and explain why a single witness settles the matter.

\forall n \in \mathbb{Z}\,(4 \mid n^2 \Rightarrow 4 \mid n),\qquad \lnot\Big(\forall n \in \mathbb{Z}\,P(n)\Big) = \exists n \in \mathbb{Z}\,\lnot P(n)

n = 2:\quad n^2 = 4,\; 4 \mid 4,\; \text{but } 4 \nmid 2

Verdict

The claim is false — $n = 2$ is a counterexample ( $4 \mid 2^2$ but $4 \nmid 2$ ).

claim

4 \mid n^2 \Rightarrow 4 \mid n

, test

n = 2

n^2 = 4

makes the hypothesis true, the conclusion

4 \mid 2

is false — counterexample confirmed.

Show proof

Counterexample and verification

The claim is a universal statement: $\forall n \in \mathbb{Z}\,(4 \mid n^2 \Rightarrow 4 \mid n)$ — the domain is $n \in \mathbb{Z}$ .
By the basic rules of logic its negation is the existential statement $\exists n \in \mathbb{Z}\,\lnot(4 \mid n^2 \Rightarrow 4 \mid n)$ , which by $\lnot(P \Rightarrow Q) = P \wedge \lnot Q$ equals $\exists n \in \mathbb{Z}\,(4 \mid n^2 \wedge 4 \nmid n)$ .
So it suffices to exhibit one $n \in \mathbb{Z}$ for which the hypothesis is true and the conclusion false — and conversely, one such $n$ is all it takes.
Take $n = 2$ .
Then $n^2 = 4$ and $4 \mid 4$ , so the hypothesis is true.
But $n = 2$ is not divisible by 4, so the conclusion $4 \mid n$ is false.
Hence $n = 2$ is a witness to $\exists n\,(4 \mid n^2 \wedge 4 \nmid n)$ , and the original universal claim is false.
$n = 2:\quad 4 \mid n^2 = 4\ \text{true},\qquad 4 \mid 2\ \text{false (i.e. } 4 \nmid 2\ \text{true)} \Rightarrow\ \text{counterexample}$
Remark: checking a hundred values of $n$ where the hypothesis trails the conclusion — e.g. $n = 4, 8, 12$ all work — never proves a universal claim.
One counterexample outweighs infinitely many supporting cases.
(The "fixed version" of this claim — $n$ is even $\iff$ $n^2$ is even — is proved in both directions in problem 2 below.)

Prove completely, in both directions, that $n$ is even if and only if $n^2$ is even. Use a direct proof for the $\Rightarrow$ direction ( $n = 2k$ gives $n^2 = 2(2k^2)$ ) and the contrapositive for the $\Leftarrow$ direction (odd $n = 2k+1$ gives odd $n^2 = 2(2k^2+2k)+1$ ), and state explicitly why the two directions are different proofs.

n\ \text{even} \iff n^2\ \text{even}

\Rightarrow:\ n = 2k \;\Rightarrow\; n^2 = 2(2k^2),\qquad \Leftarrow:\ \lnot(n\ \text{even}) \Rightarrow \lnot(n^2\ \text{even})

The scene has no preset directly testing this biconditional (only the counterexample claims), so this preset marks the smallest-counterexample position

n = 2

— this problem is proof practice.

Show proof

( $\Rightarrow$ ) Suppose $n$ is even.
Then $n = 2k$ for some integer $k$ .
Squaring gives $n^2 = 4k^2 = 2(2k^2)$ , and since $2k^2$ is an integer, $n^2$ is even.
This is a direct proof — it starts from the assumption, unfolds the definition, and reaches the conclusion.
( $\Leftarrow$ ) The reverse direction resists a direct proof: from the assumption " $n^2$ is even" there is no way to extract $n$ .
Prove the contrapositive instead: if $n$ is odd then $n^2$ is odd.
Write $n = 2k+1$ ; then $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ , and since $2k^2 + 2k$ is an integer, $n^2$ is odd.
The contrapositive holds, so the original implication " $n^2$ even $\Rightarrow$ $n$ even" holds.
$(2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\ \text{odd}$
The two directions are genuinely different proofs: $\Rightarrow$ unfolds the definition of even, $n = 2k$ , directly, while $\Leftarrow$ goes around it via the contrapositive.
Proving only one direction establishes an implication, not an equivalence.
To claim " $P \iff Q$ " both arrows are needed, and they usually require different arguments like this.

Prove that for real $x, y$ , $x^2 = y^2$ holds if and only if $x = y$ or $x = -y$ . For the $\Rightarrow$ direction use the factorization $x^2 - y^2 = (x-y)(x+y) = 0$ together with the zero-product property; for the $\Leftarrow$ direction substitute directly in each case.

x^2 = y^2 \iff (x = y\ \text{or}\ x = -y)

\Rightarrow:\ x^2 - y^2 = (x-y)(x+y) = 0,\qquad \Leftarrow:\ (-y)^2 = y^2

claim

|x| = |y| \Rightarrow x = y

, test pair

(3, -3)

|3| = |-3| = 3

but

3 \ne -3

— a counterexample to the one-directional version this problem repairs both ways.

Show proof

( $\Rightarrow$ ) Suppose $x^2 = y^2$ .
Subtracting $y^2$ from both sides gives $x^2 - y^2 = 0$ , and factoring yields $(x-y)(x+y) = 0$ .
For real numbers, a product of two numbers is 0 only if one of them is 0 (divide by whichever factor is nonzero), so $x - y = 0$ or $x + y = 0$ — i.e. $x = y$ or $x = -y$ .
( $\Leftarrow$ ) The reverse direction is checked directly in each case.
If $x = y$ then $x^2 = y^2$ is immediate, and if $x = -y$ then $x^2 = (-y)^2 = y^2$ .
In both cases $x^2 = y^2$ holds.
Remark: this biconditional explains the scene's counterexample — first prove $|x| = |y| \iff x^2 = y^2$ itself, in both directions.
$(\Rightarrow)$ If $|x| = |y|$ , squaring gives $x^2 = |x|^2 = |y|^2 = y^2$ (using $|t|^2 = t^2$ ).
$(\Leftarrow)$ If $x^2 = y^2$ then $|x|^2 = |y|^2$ ; since $|x|, |y| \ge 0$ and squaring is injective (strictly increasing) on $[0, \infty)$ , it follows that $|x| = |y|$ .
Hence $|x| = |y|$ is equivalent to $x^2 = y^2$ , so what is actually forced is not " $x = y$ " but " $x = y$ or $x = -y$ ".
The scene's pairs $(n, -n)$ are witnesses to the second alternative.
This is the classic pattern: a counterexample shows how the claim must be repaired.