Counterexamples and If and Only If

Watch a single counterexample demolish a universal claim, tested on four false claims — every prime is odd,

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

, sums of irrationals are irrational,

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

. Slide

n

and flip the hypothesis and conclusion lights until

\lnot(\forall x\, P(x)) = \exists x\, \lnot P(x)

feels mechanical. The mirror skill — proving each arrow of

P \iff Q

separately — is carried out in the problems.

Examples & Exercises

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\,(4 \mid n^2 \Rightarrow 4 \mid n)$ and its negation $\exists n\,(4 \mid n^2 \text{ and } 4 \nmid n)$ explicitly, and explain why a single witness settles the matter.

\forall n\,(4 \mid n^2 \Rightarrow 4 \mid n),\qquad \lnot\Big(\forall n\,P(n)\Big) = \exists n\,\lnot P(n)

n = 2:\quad n^2 = 4,\; 4 \mid 4,\; \text{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

The claim is a universal statement: $\forall n\,(4 \mid n^2 \Rightarrow 4 \mid n)$ . By the basic rules of logic its negation is the existential statement $\exists n\,\lnot(4 \mid n^2 \Rightarrow 4 \mid n)$ , which by $\lnot(P \Rightarrow Q) = P \wedge \lnot Q$ equals $\exists n\,(4 \mid n^2 \wedge 4 \nmid n)$ . So it suffices to exhibit one $n$ 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 \nmid 2\ \text{false}\ \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 — since $|x| = |y|$ is equivalent to $x^2 = y^2$ , 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.