Mathematical-Reasoning · Unit 8 · Video 1 · Interactive Practice

Why Proof by Contradiction Works and How to Negate the Claim

IKey Formulas

Statement	Name	What it says
$P \lor \neg P$ and $P \land \neg P$	A tautology and a contradiction	A statement is true or false, never both
$(\neg X \to C) \to X$ , with $C$ a contradiction	The tautology behind proof by contradiction	$\neg X \to C \equiv X$ , so proving $\neg X \to C$ proves $X$
$\neg(P \to Q) \equiv P \land \neg Q$	Negation of a conditional	Assume $P$ , and assume $\neg Q$
$\neg(\forall x)[P(x) \to Q(x)] \equiv (\exists x)[P(x) \land \neg Q(x)]$	Negation of a “for each” conditional	One $x$ with the hypothesis true and the conclusion false

Key Insight: To prove $X$ , assume $\neg X$ and reason until some $R \land \neg R$ appears. The assumption must negate the whole statement: “for each” becomes “there exists”, “if $P$ then $Q$ ” becomes “ $P$ and $\neg Q$ ”, and $\geq$ becomes $<$ .

IIThe Tautology Needs a Contradiction

The statement $(\neg X \to C) \to X$ is a tautology exactly because $C$ is false in every row.

Row 3

IIIOne Counterexample, Then a Hypothesis

One $x$ sinks “for each real $x$ , $\frac{1}{x(1-x)} \geq 4$ ”; under the hypothesis $0 < x < 1$ , those same $x$ no longer count.

Statement x 2

💡 The graph is evidence for the restricted statement, not a proof: the proof must work for every $x$ in the interval, and the next video gives one by contradiction.

IVBuild the Negation

Negating “for each $x \in \mathbb{R}$ , if $0 < x < 1$ , then $\frac{1}{x(1-x)} \geq 4$ ” changes three parts at once.

Quantifier Form Comparison

Step	Rule	Your statement
1 · Quantifier	$\neg(\forall x)\,S(x) \equiv (\exists x)\,\neg S(x)$
2 · Conditional	$\neg(P(x) \to Q(x)) \equiv P(x) \land \neg Q(x)$
3 · Comparison	$\neg(a \geq 4) \equiv a < 4$

VQuiz Questions

Problem 1 · Spot the Contradiction

Given: statements $P$ and $Q$ . Which compound statement is a contradiction, that is, false for every combination of truth values of $P$ and $Q$ ?

✅ Correct!

P \land Q

needs

P

true and

\neg P

needs

P

false, so no row makes both true. This has the form

R \land \neg R

with

R

the statement

P

❌ Not quite. When

P

is false,

P \to \neg P

has a false hypothesis, so it is true. In fact

P \to \neg P \equiv \neg P

❌ Not quite. When

P

and

Q

are both false,

P \to Q

is true and

\neg Q

is true, so the conjunction is true in that row.

❌ Not quite. When

P

is false and

Q

is true,

P \lor Q

is true and

\neg P

is true, so the conjunction is true in that row.

Show solution

A contradiction must be false in all four rows. The truth table:

$P$	$Q$	$P \to \neg P$	$(P \to Q) \land \neg Q$	$(P \land Q) \land \neg P$	$(P \lor Q) \land \neg P$
T	T	F	F	F	F
T	F	F	F	F	F
F	T	T	F	F	T
F	F	T	T	F	F

Only $(P \land Q) \land \neg P$ is false in every row, so the answer is c. Each of the others is true in at least one row.

Problem 2 · Negate a “For Each” Conditional

Given: the statement “For each real number $x$ , if $x \geq 1$ , then $x^3 \geq x$ .” Which statement does a proof by contradiction assume?

✅ Correct! The quantifier becomes “there exists”, the conditional becomes “

P(x)

and

\neg Q(x)

”, and the negation of

x^3 \geq x

x^3 < x

❌ Not quite. This keeps “for each” and keeps the “if, then”. It claims

x^3 < x

for every

x \geq 1

, a far stronger statement than the negation, which needs only one such

x

❌ Close, but… the inside is still a conditional. This statement is true for

x = 0

just because

0 \geq 1

is false, so it says nothing about numbers greater than or equal to

1

. The negation of a conditional is an “and” statement.

❌ Check the comparison. “Not

x^3 \geq x

” means

x^3 < x

; the case

x^3 = x

belongs to

x^3 \geq x

, not to its negation. This option is even true, at

x = 1

, while the negation is false.

Show solution

Let $P(x)$ be “ $x \geq 1$ ” and $Q(x)$ be “ $x^3 \geq x$ ”. The statement is $(\forall x \in \mathbb{R})[P(x) \to Q(x)]$ .

Step 1 (quantifier): $\neg(\forall x \in \mathbb{R})[P(x) \to Q(x)] \equiv (\exists x \in \mathbb{R})\,\neg[P(x) \to Q(x)]$ .

Step 2 (conditional): $\neg[P(x) \to Q(x)] \equiv P(x) \land \neg Q(x)$ .

Step 3 (comparison): $\neg(x^3 \geq x)$ is $x^3 < x$ .

(\exists x \in \mathbb{R})\,[\,x \geq 1 \land x^3 < x\,]

The answer is d.

Problem 3 · From Assumption to $R \land \neg R$

Given: the proposition “For each integer $n$ , if $n^2$ is odd, then $n$ is odd.” Use the facts that an integer that is not odd is even, and that no integer is both even and odd.

What does a proof by contradiction assume?

With $n = 2m$ , the proof gets $n^2 = 4m^2 = 2(2m^2)$ where $2m^2$ is an integer. Which pair is the contradiction?

✅ Correct! The assumption gives “

n^2

is odd” and the algebra proves “

n^2

is even”. With

R

the statement “

n^2

is odd”, that is

R \land \neg R

, so the assumption is false and the proposition is true.

❌ That is the contrapositive. The contrapositive

\neg Q \to \neg P

is logically equivalent to the proposition, so assuming it assumes what you want to prove. A proof by contradiction assumes the negation.

❌ Not quite. This negates the hypothesis and keeps the conclusion. The negation of

P \to Q

P \land \neg Q

: keep “

n^2

is odd” and negate “

n

is odd”.

❌ Close, but… this is still a conditional. The negation of a conditional is an “and” statement:

n^2

is odd and

n

is even.

❌ Not quite. Nothing in the proof shows that

n

is odd; that is the conclusion being proved. Using it here would assume the statement.

❌ Not quite. An even

n

with an even square is perfectly consistent; for example

n = 4

gives

n^2 = 16

. A contradiction needs a statement and its negation.

❌ Not quite. These two facts are both true and agree with each other. Together they prove that

n^2

is even, which is only half of the contradiction.

❌ Not quite. Negate the conditional inside the quantifier:

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

❌ Not quite. A contradiction is a statement

R

together with

\neg R

Show solution

Let $P$ be “ $n^2$ is odd” and $Q$ be “ $n$ is odd”. Assume the negation of $(\forall n \in \mathbb{Z})(P \to Q)$ : there is an integer $n$ with $P \land \neg Q$ , that is, $n^2$ is odd and $n$ is not odd. An integer that is not odd is even, so $n$ is even.

Then $n = 2m$ for some integer $m$ , so

n^2 = (2m)^2 = 4m^2 = 2(2m^2).

Since $2m^2$ is an integer, $n^2$ is even. Now $n^2$ is odd (assumed) and $n^2$ is even (proved). No integer is both even and odd, so with $R$ the statement “ $n^2$ is odd” we have $R \land \neg R$ . The assumption is false, so for each integer $n$ , if $n^2$ is odd, then $n$ is odd.

Answers: b, then a.

Problem 4 · Two Variables and an “Or”

Given: the proposition “For all real numbers $x$ and $y$ , if $x + y \geq 2$ , then $x \geq 1$ or $y \geq 1$ .”

What does a proof by contradiction assume?

Adding $x < 1$ and $y < 1$ gives a new inequality. Which pair is the contradiction?

✅ Correct! The assumption says

x + y \geq 2

and the sum of the two strict inequalities says

x + y < 2

. With

R

the statement

x + y \geq 2

, that is

R \land \neg R

❌ Not quite. This keeps “for all” and keeps the “if, then”. The negation needs only one pair

(x, y)

, and inside it the conditional becomes an “and”.

❌ Check De Morgan. The conclusion is “

x \geq 1

y \geq 1

”, and

\neg(A \lor B) \equiv \neg A \land \neg B

. Its negation is “

x < 1

and

y < 1

”.

❌ Not quite. The hypothesis is kept, not negated:

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

. Keep

x + y \geq 2

❌ Not quite. These two inequalities agree with each other; for example

x = 0

y = 0

satisfies both. A contradiction needs a statement and its negation.

❌ Not quite. Nothing proves

y \geq 1

; the assumption says

y < 1

. Adding the inequalities produces a statement about

x + y

❌ Close, but… both of these hold when

x + y = 2

, so they do not contradict each other. Adding two strict inequalities gives the strict inequality

x + y < 2

❌ Not quite. Negate the quantifier, the conditional and the “or”.

❌ Not quite. A contradiction is a statement

R

together with

\neg R

Show solution

Let $P$ be “ $x + y \geq 2$ ” and $Q$ be “ $x \geq 1$ or $y \geq 1$ ”. The negation of $(\forall x, y \in \mathbb{R})(P \to Q)$ is $(\exists x, y \in \mathbb{R})(P \land \neg Q)$ . By De Morgan, $\neg Q$ is “ $x < 1$ and $y < 1$ ”. So assume there are real numbers $x$ and $y$ with

x + y \geq 2, \quad x < 1, \quad y < 1.

Adding the last two inequalities gives $x + y < 1 + 1 = 2$ . Now $x + y \geq 2$ and $x + y < 2$ , which is $R \land \neg R$ with $R$ the statement $x + y \geq 2$ . The assumption is false, so the proposition is true.

Answers: c, then d.

Solved: 0 / 4