Mathematical-Reasoning · Unit 5 · Video 3 · Interactive Practice

One Counterexample Is Enough: Negating Conditionals and Definitions

IKey Formulas

Statement	Its negation	What disproves the statement
$(\forall x \in U)\,P(x)$	$(\exists x \in U)\,\neg P(x)$	one counterexample: an $a \in U$ with $P(a)$ false
$(\forall x \in U)\,[P(x) \to Q(x)]$	$(\exists x \in U)\,[P(x) \wedge \neg Q(x)]$	one $a$ with the hypothesis $P(a)$ true and the conclusion $Q(a)$ false
$n$ is a perfect square: $(\exists k \in \mathbb{N})(n = k^2)$	$(\forall k \in \mathbb{N})(n \neq k^2)$	$n$ is not a perfect square
$n$ is a multiple of $3$ : $(\exists k \in \mathbb{Z})(n = 3k)$	$(\forall k \in \mathbb{Z})(n \neq 3k)$	$n$ is not a multiple of $3$

Key Insight: the negation of a conditional is an and-statement, $\neg(P \to Q) \equiv P \wedge \neg Q$ , never $P \to \neg Q$ . An object that makes the hypothesis false is never a counterexample, because the conditional is true for it. In this course $\mathbb{N} = \{1, 2, 3, \ldots\}$ .

IIPassing Cases Versus One Failure

Any number of passing cases leaves a for-all claim unproved; one failing case makes it false.

Claim

💡 The expression $n^2 - n + 41$ is prime for all $80$ consecutive integers from $-39$ to $40$ , and that still does not prove the second claim.

IIIHypothesis True and Conclusion False

A counterexample to a conditional lies in the truth set of $P(x) \wedge \neg Q(x)$ : hypothesis true and conclusion false at once.

Claim Candidate x 1/4

💡 Challenge: find the largest counterexample to the first claim, and check that it really makes $2x^2 > x$ false.

IVNot Satisfying a Definition

Failing an existence definition means $n \neq k^2$ (or $n \neq 3k$ ) for every $k$ , not just for one.

Definition n 50

VQuiz Questions

Problem 1 · A Counterexample to a For-All Claim

Claim: “For each natural number $n$ , $2^n + 1$ is a prime number.” Which value of $n$ is a counterexample?

✅ Correct!

2^3 + 1 = 9 = 3 \cdot 3

is not prime, so

n = 3

makes

P(n)

false and the claim is false.

❌ Not quite. That value gives a prime (

2^1 + 1 = 3

2^2 + 1 = 5

2^4 + 1 = 17

), so it agrees with the claim. A counterexample must make

2^n + 1

fail to be prime.

Show solution

A counterexample to $(\forall n \in \mathbb{N})\,P(n)$ is one natural number $a$ with $P(a)$ false. Evaluate each option:

2^1 + 1 = 3, \qquad 2^2 + 1 = 5, \qquad 2^3 + 1 = 9, \qquad 2^4 + 1 = 17.

Here $3$ , $5$ and $17$ are prime, but $9 = 3 \cdot 3$ is not. So $n = 3$ is a counterexample, the claim is false, and its negation $(\exists n \in \mathbb{N})(2^n + 1 \text{ is not prime})$ is true. The three passing values prove nothing about the claim.

Problem 2 · Which Candidate Is a Counterexample?

Claim: “For each real number $x$ , if $x < 1$ , then $x^2 < 1$ .” Which value of $x$ is a counterexample?

✅ Correct!

-3 < 1

makes the hypothesis true, and

(-3)^2 = 9 \geq 1

makes the conclusion false.

❌ Close, but… the conclusion

x^2 < 1

does fail there, yet the hypothesis

x < 1

is false too. With a false hypothesis the conditional is true, so this value is not a counterexample.

❌ Not quite.

\tfrac{1}{2} < 1

and

\left(\tfrac{1}{2}\right)^2 = \tfrac{1}{4} < 1

: hypothesis and conclusion are both true, so the conditional holds at

x = \tfrac{1}{2}

❌ Not quite. A counterexample must make the hypothesis true and the conclusion false.

Show solution

The negation of the claim is

(\exists x \in \mathbb{R})\,[\,x < 1 \;\wedge\; x^2 \geq 1\,],

so a counterexample needs $x < 1$ and $x^2 \geq 1$ .

$x = -3$ : $-3 < 1$ is true and $(-3)^2 = 9 \geq 1$ . Counterexample.
$x = 2$ : $2 < 1$ is false. Conditional true, not a counterexample.
$x = \tfrac{1}{2}$ : $\tfrac{1}{4} < 1$ , so the conclusion is true. Not a counterexample.
$x = 1$ : $1 < 1$ is false. Conditional true, not a counterexample (even though $1^2 < 1$ is false too).

Problem 3 · Negating the Definition of a Perfect Cube

Definition: a natural number $n$ is a perfect cube provided that there exists a natural number $k$ such that $n = k^3$ .

Which statement means that $n$ is not a perfect cube?

Which number satisfies that negation?

✅ Correct!

n

is not a perfect cube exactly when

(\forall k \in \mathbb{N})(n \neq k^3)

, and

36

satisfies it:

3^3 = 27 < 36 < 64 = 4^3

❌ Close, but… this holds for every natural number. For example

8 \neq 1^3

, yet

8 = 2^3

is a perfect cube. The negation must rule out every

k

, not just one.

❌ Not quite. The quantifier switched but the equation was not negated:

\neg(\exists k \in \mathbb{N})(n = k^3) \equiv (\forall k \in \mathbb{N})\,\neg(n = k^3)

❌ Not quite.

3k

is three times

k

, not

k

cubed; this statement says

n

is not a multiple of

3

❌ Check the negation. Apply the negation theorem to

(\exists k \in \mathbb{N})(n = k^3)

❌ Check the number. That number is a perfect cube (

1 = 1^3

27 = 3^3

64 = 4^3

), so a natural number

k

with

n = k^3

exists.

Show solution

Negation. By the negation theorem,

\neg(\exists k \in \mathbb{N})(n = k^3) \equiv (\forall k \in \mathbb{N})\,\neg(n = k^3) \equiv (\forall k \in \mathbb{N})(n \neq k^3).

So $n$ is not a perfect cube provided that for every natural number $k$ , $n \neq k^3$ . The form $(\exists k \in \mathbb{N})(n \neq k^3)$ is wrong: it is true for every $n$ , including the perfect cube $8$ (take $k = 1$ ).

The number. $1 = 1^3$ , $27 = 3^3$ and $64 = 4^3$ are perfect cubes. For $36$ : $3^3 = 27 < 36 < 64 = 4^3$ . So $36$ lies strictly between the consecutive cubes $3^3$ and $4^3$ , and no natural number cubes to a value strictly between two consecutive cubes. Therefore $36 \neq k^3$ for every $k \in \mathbb{N}$ . (Note that $36 = 6^2$ is a perfect square; being a square says nothing about being a cube.)

Problem 4 · Disproving a Conditional Built From Definitions

Claim: “For each natural number $n$ , if $n$ is a multiple of $3$ , then $n$ is not a perfect square.”

Which statement is the negation of the claim?

Which natural number is a counterexample to the claim?

✅ Correct!

36 = 3 \cdot 12

and

36 = 6^2

: the hypothesis is true and the conclusion is false, so the claim is false.

❌ Close, but… this is the “if

P

then not

Q

” form. The negation of a conditional is an and-statement, and the

\forall

must become

\exists

❌ Not quite. The hypothesis must stay true in the negation:

\neg(P \to Q) \equiv P \wedge \neg Q

, with

P

unchanged.

❌ Not quite. Here

Q(n)

is “

n

is not a perfect square”, so

\neg Q(n)

is “

n

is a perfect square”; this option leaves

Q

un-negated.

❌ Check the negation. Use

\neg(\forall n)[P(n) \to Q(n)] \equiv (\exists n)[P(n) \wedge \neg Q(n)]

❌ Not quite. That number is not a multiple of

3

, so the hypothesis is false and the conditional is true for it, whatever the conclusion does.

❌ Not quite.

6 = 3 \cdot 2

is a multiple of

3

and

6

is not a perfect square (

2^2 < 6 < 3^2

), so hypothesis and conclusion are both true.

❌ Check the counterexample. It must be a multiple of

3

that is also a perfect square.

Show solution

Let $P(n)$ be “ $n$ is a multiple of $3$ ” and $Q(n)$ be “ $n$ is not a perfect square”. The claim is $(\forall n \in \mathbb{N})[P(n) \to Q(n)]$ , so

\neg(\forall n \in \mathbb{N})[P(n) \to Q(n)] \equiv (\exists n \in \mathbb{N})[P(n) \wedge \neg Q(n)],

that is, there exists a natural number $n$ that is a multiple of $3$ and a perfect square.

$n = 36$ : $36 = 3 \cdot 12$ and $36 = 6^2$ . Hypothesis true, conclusion false: a counterexample.
$n = 16$ : $16 = 4^2$ , so the conclusion is false, but $16$ is not a multiple of $3$ ( $3 \cdot 5 = 15 < 16 < 18 = 3 \cdot 6$ ), so the hypothesis is false and the conditional is true.
$n = 6$ : hypothesis true and conclusion true.
$n = 7$ : hypothesis false ( $3 \cdot 2 < 7 < 3 \cdot 3$ ), conclusion true.

One counterexample is enough; $9 = 3 \cdot 3 = 3^2$ would also do.

Solved: 0 / 4