Mathematical-Reasoning · Unit 11 · Video 2 · Interactive Practice

Proof by Cases, Equivalences, and Existence Proofs

IKey Formulas

Formula	Method	How it is used
$P \to (Q \lor R) \equiv (P \land \neg Q) \to R$	Logical equivalency	The conclusion is an "or": assume $P$ and $\neg Q$ , then prove $R$
$(P \lor Q) \to R \equiv (P \to R) \land (Q \to R)$	Proof by cases	One conditional per case; together the cases must cover every possibility
$(\exists x)\,(P(x))$	Existence theorem	Constructive: produce $x$ and check $P(x)$ . Nonconstructive: show some $x$ must exist without naming it
$\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}} = \sqrt{2}^{\sqrt{2} \cdot \sqrt{2}} = \sqrt{2}^{2} = 2$	Power of a power, valid since $\sqrt{2} > 0$	Case 2 of the nonconstructive proof that some irrational $b$ , $c$ have $b^c$ rational

Key Insight: The first two methods trade the statement for a logically equivalent one that is easier to prove; the last two prove that an object exists, either by producing it or by showing it cannot fail to exist.

IIVisualization 1 — Assume Not $Q$ , Prove $R$

Two forms are logically equivalent exactly when their truth values agree on every row of the truth table.

Compare

P \to (Q \lor R)

with

IIIVisualization 2 — Cases Must Cover Every Possibility

A case split proves a claim about every integer only when each integer lies in at least one case.

Case split

IVVisualization 3 — A Pair Exists, but Which One?

Each case produces irrational $b$ and $c$ with $b^c$ rational, so a pair exists without the proof naming it.

Assume

Case 1: $\sqrt{2}^{\sqrt{2}}$ is rational.

Let $b = \sqrt{2}$ and $c = \sqrt{2}$ ; both are irrational.

Then $b^c = \sqrt{2}^{\sqrt{2}}$ , which is rational in this case.

Case 2: $\sqrt{2}^{\sqrt{2}}$ is irrational.

Let $b = \sqrt{2}^{\sqrt{2}}$ , irrational in this case, and $c = \sqrt{2}$ .

b^c = \left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}} = \sqrt{2}^{\sqrt{2} \cdot \sqrt{2}}

= \sqrt{2}^{2} = 2

💡 In fact $\sqrt{2}^{\sqrt{2}}$ is irrational, so Case 2 is the true one, but proving that takes the Gelfond–Schneider theorem (1934); the proof above needs no such knowledge.

VQuiz Questions

Problem 1 · Rewrite an "Or" Conclusion

Given: For all integers $a$ and $b$ , if $ab$ is even, then $a$ is even or $b$ is even. Which statement is logically equivalent to this proposition and is the form the logical-equivalency method proves?

✅ Correct! With

P

: "

ab

is even",

Q

: "

a

is even",

R

: "

b

is even", this is

(P \land \neg Q) \to R

, which is equivalent to

P \to (Q \lor R)

❌ Not quite. This assumes

Q

rather than

\neg Q

, and it is not equivalent: with

a = 2

and

b = 1

the original is true, but this statement is false.

❌ Not quite. This is the converse,

(Q \lor R) \to P

. It happens to be true for integers, but it is not logically equivalent to the original, so proving it does not prove the original.

❌ Not quite. This strengthens "or" to "and", and it is false: with

a = 2

and

b = 1

, the product

ab

is even while

b

is odd.

Show solution

Let $P$ be " $ab$ is even", $Q$ be " $a$ is even" and $R$ be " $b$ is even". The proposition has the form $P \to (Q \lor R)$ , and

P \to (Q \lor R) \equiv (P \land \neg Q) \to R.

Since $\neg Q$ is " $a$ is odd", we prove: if $ab$ is even and $a$ is odd, then $b$ is even.

A short proof of that form: assume $ab$ is even and $a$ is odd. Suppose, for contradiction, that $b$ is odd. Then $a = 2m + 1$ and $b = 2k + 1$ for some integers $m$ and $k$ , so $ab = 4mk + 2m + 2k + 1 = 2(2mk + m + k) + 1$ is odd, which contradicts the assumption that $ab$ is even. Hence $b$ is even, and the original proposition is proved.

Problem 2 · Do the Cases Cover Everything?

Given: To prove that for every integer $n$ , $n^2 \equiv 0 \pmod 4$ or $n^2 \equiv 1 \pmod 4$ , a student writes three cases, $n = 4q$ , $n = 4q + 1$ and $n = 4q + 3$ with $q \in \mathbb{Z}$ , and proves each case correctly. Which assessment is right?

✅ Correct! The Division Algorithm gives four possible remainders on division by

4

, and the remainder

2

was left out.

❌ Not quite. Containing some even integers is not enough: the even integers

2

6

and

-2

lie in none of the three cases.

❌ Not quite. Negative integers are covered by the Division Algorithm forms:

-1 = 4(-1) + 3

, for example. The missing integers are those with remainder

2

❌ Not quite. A true claim with correct cases can still have a gap: nothing written proves the claim for

n = 2

Show solution

By the Division Algorithm, every integer $n$ has exactly one of the forms $4q$ , $4q + 1$ , $4q + 2$ , $4q + 3$ with $q \in \mathbb{Z}$ . The student's cases omit $4q + 2$ , so integers such as $2 = 4(0) + 2$ , $6 = 4(1) + 2$ and $-2 = 4(-1) + 2$ lie in no case, and the proof has a gap.

The missing case is easy to supply. If $n = 4q + 2$ , then

n^2 = 16q^2 + 16q + 4 = 4(4q^2 + 4q + 1),

so $n^2 \equiv 0 \pmod 4$ . With all four cases written, the cases exhaust the possibilities and the proof is complete.

Problem 3 · Construct the Number

Given: A constructive proof that there exists a rational number between $\tfrac{2}{5}$ and $\tfrac{3}{7}$ takes their average. What number does the proof produce?

✅ Correct! The average is

\tfrac{29}{70}

, and

\tfrac{28}{70} < \tfrac{29}{70} < \tfrac{30}{70}

shows it lies between

\tfrac{2}{5}

and

\tfrac{3}{7}

❌ Not quite. The number

\tfrac{5}{12} = \tfrac{2 + 3}{5 + 7}

adds numerators and denominators. It does lie between the two fractions, but it is not their average.

❌ Not quite. The number

\tfrac{29}{35}

is the sum

\tfrac{2}{5} + \tfrac{3}{7}

, which is about

0.83

and is not between them; the average halves the sum.

❌ Not quite. The number

\tfrac{5}{24}

halves

\tfrac{2 + 3}{5 + 7}

, but fractions are not added by adding numerators and denominators; it is about

0.21

, below both fractions.

Show solution

We construct the average of the two fractions:

\frac{1}{2}\left(\frac{2}{5} + \frac{3}{7}\right) = \frac{1}{2}\left(\frac{14}{35} + \frac{15}{35}\right) = \frac{1}{2} \cdot \frac{29}{35} = \frac{29}{70}.

The number $\tfrac{29}{70}$ is a ratio of integers with nonzero denominator, so it is rational. Since $\tfrac{2}{5} = \tfrac{28}{70}$ and $\tfrac{3}{7} = \tfrac{30}{70}$ , we have $\tfrac{28}{70} < \tfrac{29}{70} < \tfrac{30}{70}$ , so it lies between them. The proof produced the number and checked it, so it is constructive.

Problem 4 · What the Nonconstructive Proof Shows

Given: The proof that there exist irrational numbers $b$ and $c$ with $b^c$ rational, using the cases " $\sqrt{2}^{\sqrt{2}}$ is rational" and " $\sqrt{2}^{\sqrt{2}}$ is irrational".

In Case 2, why is $b = \sqrt{2}^{\sqrt{2}}$ irrational?

Which statement about the whole proof is true?

✅ Correct! Case 2 gets the irrationality of

b

from its own assumption, and since the two cases exhaust the possibilities, a pair exists either way, though the proof never names it.

❌ Not quite. That general rule is false: the theorem itself shows an irrational number raised to an irrational power can be rational.

❌ Not quite. That reasoning is circular:

b^c = 2

is the conclusion of Case 2, and a rational power says nothing about whether

b

is irrational.

❌ Not quite. Only

\sqrt{2}

was proved irrational by contradiction; nothing in this proof shows

\sqrt{2}^{\sqrt{2}}

is irrational.

❌ Not quite. The proof assumes each possibility in turn and proves neither one.

❌ Not quite. The pair

b = c = \sqrt{2}

works only in Case 1, and the proof never shows that Case 1 holds, so it produces no specific pair.

❌ Not quite. The cases "rational" and "irrational" cover every possibility, so the proof is complete; deciding which case holds is unnecessary.

Show solution

The number $\sqrt{2}^{\sqrt{2}}$ is either rational or irrational, so these two cases exhaust the possibilities.

In Case 1, $\sqrt{2}^{\sqrt{2}}$ is rational, so $b = \sqrt{2}$ and $c = \sqrt{2}$ are irrational numbers with $b^c$ rational.

In Case 2, $\sqrt{2}^{\sqrt{2}}$ is irrational by assumption, so $b = \sqrt{2}^{\sqrt{2}}$ is irrational, and $c = \sqrt{2}$ is irrational. Since $\sqrt{2} > 0$ , raising a power to a power multiplies the exponents:

b^c = \left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}} = \sqrt{2}^{\sqrt{2} \cdot \sqrt{2}} = \sqrt{2}^{2} = 2,

which is rational.

In each case a suitable pair exists, so the theorem is proved. The proof does not determine which case holds, so it never says which pair works; that is what makes it nonconstructive.

Solved: 0 / 4

Proof by Cases, Equivalences, and Existence Proofs

IKey Formulas

IIVisualization 1 — Assume Not QQQ, Prove RRR

IIIVisualization 2 — Cases Must Cover Every Possibility

IVVisualization 3 — A Pair Exists, but Which One?

VQuiz Questions

IIVisualization 1 — Assume Not $Q$ , Prove $R$