Discrete Mathematics and Proof

Proving an if and only if

How do you prove that two statements always stand or fall together, and not just that one brings the other?

You need

BiconditionalGeometry Direct proofGrades 9 to 12

Where you are 14 in Proof techniques

Logic, proof and discrete math6

Proof techniques14

▴ 3 above Direct proof2 What may be assumed and what must be shown

Proving an if and only if

Writing a proof as prose Existence proof ▾ Show all 14 (6 more)

When you reach for it

A claim of the form “P if and only if Q”, written P \leftrightarrow Q, says that P and Q are true together and false together. Its meaning, and the words “necessary and sufficient”, are the subject of the biconditional. This lesson is about proving one.

You reach for this move whenever a claim promises two things at once: “if and only if”, “iff”, “exactly when”, “is necessary and sufficient for”, “the following are equivalent”, and also “find every x with...”, since “the solutions are exactly these” says that being a solution and being on the list are equivalent.

The procedure

Day 1: two directions

Split the claim. The biconditional P \leftrightarrow Q has the same truth table as (P \to Q) \land (Q \to P), so it is true exactly when both conditionals are true. A proof of P \leftrightarrow Q is therefore two proofs, one of each conditional. Neither alone is enough: “if an integer is divisible by 6, then it is even” is true, and “an integer is divisible by 6 if and only if it is even” is false.

Label each direction. The forward direction, marked (\Rightarrow), assumes P and must show Q. The backward direction, marked (\Leftarrow), assumes Q and must show P. The labels matter because the two halves start from different givens: inside (\Rightarrow) you may use P and never Q, and inside (\Leftarrow) the reverse. Open each half with a sentence that says what it assumes and what it must show, as in what may be assumed and what must be shown. Words work as labels too: “Suppose P...” and “Conversely, suppose Q...”.

Each direction is its own proof, with its own method. Each half is a conditional, so any way of proving a conditional will do: a direct proof, or proof by contraposition, which proves \neg P \to \neg Q in place of Q \to P (the two are equivalent, by the contrapositive equivalence). The two halves need not match, and often one takes a line while the other carries all the work.

Quantified claims. Most such claims are about every number: “for every integer n, P(n) \leftrightarrow Q(n)”. The proof fixes an arbitrary n once, and both directions are about that same n. To show such a claim is false, one value where one side is true and the other false is enough: it is a Counterexample to one direction. Say which direction it breaks, because the other direction may well be true.

Day 2: more than two statements

A cycle. “The following are equivalent: A, B, C” claims every pair is a biconditional, which is six conditionals. A cycle of three proofs is enough:

A \Rightarrow B, \qquad B \Rightarrow C, \qquad C \Rightarrow A

Any missing conditional comes from following arrows. For B \Rightarrow A: assume B; then C by the second arrow, and then A by the third. Each conditional X \Rightarrow Y is reached the same way, by walking around the cycle from X until you meet Y. With n statements a cycle takes n proofs in place of n(n - 1), and you may order the statements so that each arrow is as easy as possible. What matters is that the arrows close up: every statement must be able to reach every other one.

A chain of equivalent steps. A chain

P \iff R_1 \iff R_2 \iff Q

is three biconditionals laid end to end. Read downward it gives P \Rightarrow Q; read upward it gives Q \Rightarrow P. So a chain proves both directions at once, but only if every link really holds both ways. The write-up says why each step can be undone: adding a number is undone by subtracting it, and multiplying by a nonzero number is undone by dividing by it. Squaring cannot be undone, since 3 and -3 have the same square. A link that holds only one way is written \Longrightarrow, and then the chain proves only one direction; the other needs its own argument.

Worked examples

Example 1

Two directions, each by cases

Let x be a real number. Prove that |x - 5| < 2 if and only if 3 < x < 7.

Solution

The definition of absolute value has two cases, |a| = a when a \ge 0 and |a| = -a when a < 0, so each direction splits on the sign of x - 5.

Proof. Let x be a real number.

(\Rightarrow) Assume |x - 5| < 2. We must show 3 < x < 7. If x \ge 5, then |x - 5| = x - 5, so x - 5 < 2 and x < 7; also x \ge 5 > 3. If x < 5, then |x - 5| = 5 - x, so 5 - x < 2 and x > 3; also x < 5 < 7. In both cases 3 < x < 7.

(\Leftarrow) Assume 3 < x < 7. We must show |x - 5| < 2. If x \ge 5, then |x - 5| = x - 5 < 7 - 5 = 2. If x < 5, then |x - 5| = 5 - x < 5 - 3 = 2. Either way |x - 5| < 2.

Both directions hold, so |x - 5| < 2 \iff 3 < x < 7. \square

Figure 1The numbers less than 2 away from 5 are exactly the numbers strictly between 3 and 7. Each direction of Example 1 proves one half of “exactly”.

The two halves say different things. (\Rightarrow) says every solution of |x - 5| < 2 lies between 3 and 7; (\Leftarrow) says every number between 3 and 7 is a solution. Only together do they say the solution set is exactly the interval, which is the picture of absolute value as distance.

Example 2

A direction proved by contraposition

Let n be an integer. Prove that n is odd if and only if 7n + 4 is odd.

Solution

Proof. Let n be an integer.

(\Rightarrow) Assume n is odd; we must show 7n + 4 is odd. Write n = 2k + 1 for some integer k. Then

7n + 4 = 14k + 11 = 2(7k + 5) + 1,

and 7k + 5 is an integer, so 7n + 4 is odd.

(\Leftarrow) Assume 7n + 4 is odd; we must show n is odd. Working forward gives 7n + 4 = 2m + 1, so 7n = 2m - 3, which says something about 7n and nothing yet about n. The contrapositive is easier: if n is not odd, then 7n + 4 is not odd. Every integer is even or odd and not both (see proof with even and odd), so this reads: if n is even, then 7n + 4 is even. Write n = 2k. Then 7n + 4 = 14k + 4 = 2(7k + 2), which is even. The contrapositive is proved, so the backward direction holds.

Both directions hold. \square

Example 3

One direction is easy, the other needs work

Let x and y be real numbers. Prove that x^2 = y^2 if and only if x = y or x = -y.

Solution

Proof. Let x and y be real numbers.

(\Leftarrow) Assume x = y or x = -y; we must show x^2 = y^2. The assumption is an “or”, so there are two cases. If x = y, then x^2 = y^2 at once. If x = -y, then x^2 = (-y)^2 = y^2.

(\Rightarrow) Assume x^2 = y^2; we must show x = y or x = -y. Subtracting y^2 from both sides gives x^2 - y^2 = 0, and factoring as a difference of squares gives

(x - y)(x + y) = 0.

By the zero product property, a product of two real numbers is 0 only if one factor is 0. So x - y = 0 or x + y = 0, that is, x = y or x = -y. \square

The easy direction only substitutes. The work sits in (\Rightarrow), which must recover x from a fact about x^2, and squaring has thrown the sign away; the factoring is what brings back both possibilities. This is the reason a square root comes with \pm.

Example 4

When one direction fails

Decide whether this claim is true: for all integers a and b with a \ne 0, a \mid b if and only if a \mid 2b.

Solution

Recall that a \mid b means b = ak for some integer k (see divisibility as a relation). Test the two directions separately.

(\Leftarrow) This direction is true. Assume a \mid b, and write b = ak for an integer k. Then 2b = a(2k), and 2k is an integer, so a \mid 2b.

(\Rightarrow) This direction is false. Take a = 2, b = 1. Then 2b = 2 = 2 \cdot 1, so 2 \mid 2b and the hypothesis holds. But 2 \nmid 1, since \displaystyle \frac{1}{2} is not an integer. The conclusion fails.

So the claim is false. The precise report is: the “if” half holds for all integers, and the “only if” half has the counterexample a = 2, b = 1. It works because a = 2 divides 2b through the factor 2 alone, whatever b is. Put the same factor on both sides and the claim becomes true: a \mid b \iff 2a \mid 2b, because 2b = 2ak and b = ak say the same thing about the integer k.

Example 5

Three statements in a cycle

Let x be a nonzero real number. Prove that the following are equivalent: (a) x > 1; (b) \displaystyle 0 < \frac{1}{x} < 1; (c) x^2 > x > 0.

Solution

Six conditionals are claimed. We prove three, (a) \Rightarrow (b) \Rightarrow (c) \Rightarrow (a), using that multiplying or dividing an inequality by a positive number keeps its direction.

Proof. Let x be a nonzero real number.

(a) \Rightarrow (b). Assume x > 1. Then x > 0, so \displaystyle \frac{1}{x} > 0. Multiplying 1 < x by the positive number \displaystyle \frac{1}{x} gives \displaystyle \frac{1}{x} < 1. So \displaystyle 0 < \frac{1}{x} < 1.

(b) \Rightarrow (c). Assume \displaystyle 0 < \frac{1}{x} < 1. Since \displaystyle x \cdot \frac{1}{x} = 1 > 0, the numbers x and \displaystyle \frac{1}{x} have the same sign, so x > 0. Multiplying \displaystyle \frac{1}{x} < 1 by x gives 1 < x, and multiplying 1 < x by x gives x < x^2. So x^2 > x > 0.

The three arrows form a closed cycle, so the three statements are equivalent. \square

Figure 2Three proved arrows in a closed cycle. Following them, any statement reaches any other, so all six conditionals hold.

The other three conditionals come from walking the cycle. For (c) \Rightarrow (b), go (c) \Rightarrow (a) \Rightarrow (b); for (b) \Rightarrow (a), go (b) \Rightarrow (c) \Rightarrow (a). The part “x > 0” in (c) is needed: x = -1 has x^2 = 1 > -1 = x but not x > 1.

Example 6

A chain where every step reverses

Let a and b be positive real numbers. Prove that a < b if and only if a^2 < b^2.

Solution

Proof. Let a and b be positive real numbers. Then

\begin{aligned} a < b &\iff b - a > 0 \\ &\iff (b - a)(b + a) > 0 \\ &\iff b^2 - a^2 > 0 \\ &\iff a^2 < b^2. \end{aligned}

Each link holds both ways. The first and last subtract a number from both sides, undone by adding it back. The second multiplies by b + a, which is positive because a and b are; multiplying by a positive number keeps an inequality, and dividing by it, the reverse step, keeps it too. The third replaces (b - a)(b + a) by its expansion b^2 - a^2, the same number, so it holds both ways. Read downward, the chain proves (\Rightarrow); read upward, (\Leftarrow). \square

The standing hypothesis “positive” is outside the biconditional and serves both directions. It is used exactly once, in the second link. Without it the claim fails: a = -3, b = 1 has a < b but a^2 = 9 > 1 = b^2, and there b + a = -2 is negative.

Example 7

A step that does not reverse

Find every real number x with \displaystyle \sqrt{x + 6} = x, and prove the answer as an “if and only if”.

Solution

Square both sides and solve:

\begin{aligned} \sqrt{x + 6} = x &\Longrightarrow x + 6 = x^2 \\ &\iff x^2 - x - 6 = 0 \\ &\iff (x - 3)(x + 2) = 0 \\ &\iff x = 3 \text{ or } x = -2. \end{aligned}

The first link holds one way only. Equal numbers have equal squares, but x + 6 = x^2 also holds when \displaystyle \sqrt{x + 6} = -x. So the chain proves only: if \displaystyle \sqrt{x + 6} = x, then x = 3 or x = -2. It narrows the answer to two candidates and says nothing about whether they work. Checking them is the other direction: \displaystyle \sqrt{3 + 6} = \sqrt{9} = 3 works, while \displaystyle \sqrt{-2 + 6} = \sqrt{4} = 2, and 2 \ne -2.

Proof that \displaystyle \sqrt{x + 6} = x if and only if x = 3. (\Rightarrow) If \displaystyle \sqrt{x + 6} = x, the chain gives x = 3 or x = -2, and x = -2 is not a solution, so x = 3. (\Leftarrow) If x = 3, then \displaystyle \sqrt{x + 6} = 3 = x. \square

A square root is never negative, so keeping x \ge 0 makes the first link reversible:

\sqrt{x + 6} = x \iff x + 6 = x^2 \text{ and } x \ge 0

This one-way step is why radical equations are always checked.

Boundaries

A proof of P \to Q and of its contrapositive \neg Q \to \neg P proves one direction twice. The second direction needs Q \to P, or its contrapositive \neg P \to \neg Q.
A standing hypothesis (“let a and b be positive”) belongs to both directions and is not part of P or Q. A biconditional that is true under the hypothesis may be false without it, as in Example 6.
A counterexample breaks one direction of a quantified biconditional and so the whole claim, but it says nothing about the other direction, which may still be true (Example 4).
A chain proves both directions only if every link reverses. One link that holds a single way turns it into a one-way proof.
A list of implications proves equivalence only if every statement reaches every other along proved arrows. A \Rightarrow B \Rightarrow C without a way back from C proves neither C \Rightarrow A nor B \Rightarrow A.

Where this goes next

The same two halves prove two sets equal: A = B exactly when, for every x, x \in A \iff x \in B, and the two directions are A \subseteq B and B \subseteq A. The longest cycle most readers meet is the invertible matrix theorem of linear algebra, a dozen or more statements about a square matrix shown equivalent by a ring of implications.

Exercises

Day 1: prove both directions

Let x be a real number. For the claim “4x - 3 > 9 if and only if x > 3”, write each direction as an if-then sentence, say what it assumes and what it must show, and prove both.
Let n be an integer. Prove that n is even if and only if 3n + 8 is even.
Let x be a real number. Prove that |x + 1| \le 4 if and only if -5 \le x \le 3.
Let n be an integer. Prove that n is odd if and only if n^2 + 4n is odd.

Day 1: one direction needs the work

Let x and y be real numbers. Prove that x^3 = y^3 if and only if x = y.
Let x and y be real numbers. Prove that x^2 + y^2 = 0 if and only if x = 0 and y = 0.
Let a and b be positive integers. Prove that a \mid b and b \mid a if and only if a = b.

Day 1: prove or refute

For each claim, prove it, or prove the direction that holds and give a counterexample to the one that fails.

For all integers a and b, ab is odd if and only if a + b is even.
For every real number x, x^2 > 16 if and only if x > 4.
For all positive integers a and b, a \mid b if and only if a \le b.
For all real numbers x and y, xy > 0 if and only if x > 0 and y > 0. If it is false, state a corrected “if and only if” with the same left side.
For every integer n, 5 \mid (n + 3) if and only if 5 \mid (n - 2).

Day 1: reasoning

To prove P \leftrightarrow Q, Berk proves P \Rightarrow Q and then \neg P \Rightarrow \neg Q. Has he proved the biconditional? Explain.
To prove P \leftrightarrow Q, Ilkay proves P \Rightarrow Q and then \neg Q \Rightarrow \neg P. Has she proved the biconditional? Explain, using Exercise 9.

Day 2: cycles

Let n be an integer. Prove that the following are equivalent: (a) n is even; (b) n + 5 is odd; (c) 3n is even.
Let n be an integer. Prove that the following are equivalent: (a) 3 \mid n; (b) 3 \mid (n + 6); (c) 3 \mid 4n.
How many proofs does a cycle need to show four statements equivalent, and how many conditionals does the claim contain? Answer the same for n statements.
Someone has proved A \Rightarrow B, B \Rightarrow A, B \Rightarrow C and C \Rightarrow D. Do these show that A, B, C, D are equivalent? Which single further conditionals would finish the job?

Day 2: chains

Let x be a real number. Prove with a chain of reversible steps that 5 - 2x < 11 if and only if x > -3, giving the reason each step reverses.
Prove that x^2 + 4 \ge 4x for every real number x, using a chain that ends at a statement known to be true. Which direction of the chain does the proof use?
Find every real number x with \displaystyle \sqrt{2x + 3} = x, and say which step of your work holds only one way.
An argument reads: “x^2 = 2x \iff x = 2, dividing both sides by x.” Find the step that fails, say in which direction it fails, and give the correct solution set.

Day 2: reasoning

Explain how the cycle A \Rightarrow B \Rightarrow C \Rightarrow A gives B \Rightarrow A and C \Rightarrow B, and why the two arrows A \Rightarrow B \Rightarrow C alone do not show the three statements equivalent.
Two sets A and B are equal when they have the same elements. Explain why a proof that A = B is an “if and only if” proof, and what each of its two directions shows.

Answers

(\Rightarrow) “If 4x - 3 > 9, then x > 3”: assume 4x - 3 > 9, show x > 3. Adding 3 gives 4x > 12; dividing by 4 gives x > 3. (\Leftarrow) “If x > 3, then 4x - 3 > 9”: assume x > 3, show 4x - 3 > 9. Multiplying by 4 gives 4x > 12; subtracting 3 gives 4x - 3 > 9.
(\Rightarrow) If n = 2k, then 3n + 8 = 6k + 8 = 2(3k + 4), even. (\Leftarrow) By contraposition: if n is odd, n = 2k + 1, then 3n + 8 = 6k + 11 = 2(3k + 5) + 1, odd. So if 3n + 8 is even, n is not odd, hence even.
Split on the sign of x + 1. (\Rightarrow) If x \ge -1: x + 1 \le 4 gives x \le 3, and x \ge -1 \ge -5. If x < -1: -(x + 1) \le 4 gives x \ge -5, and x < -1 \le 3. (\Leftarrow) If x \ge -1: |x + 1| = x + 1 \le 3 + 1 = 4. If x < -1: |x + 1| = -x - 1 \le 5 - 1 = 4.
(\Rightarrow) If n = 2k + 1, then n^2 + 4n = 4k^2 + 12k + 5, which is 2(2k^2 + 6k + 2) + 1, odd. (\Leftarrow) By contraposition: if n = 2k, then n^2 + 4n = 4k^2 + 8k, which is 2(2k^2 + 4k), even.
(\Leftarrow) If x = y, cubing gives x^3 = y^3. (\Rightarrow) If x^3 = y^3, then x^3 - y^3 = 0, that is, (x - y)(x^2 + xy + y^2) = 0. So x = y or x^2 + xy + y^2 = 0. In the second case, x^2 + xy + y^2 equals \displaystyle \left(x + \frac{y}{2}\right)^2 plus \displaystyle \frac{3}{4}y^2, a sum of two squares, so both are 0: y = 0, then x = 0, and again x = y.
(\Leftarrow) 0^2 + 0^2 = 0. (\Rightarrow) By contraposition. “Not (x = 0 and y = 0)” is “x \ne 0 or y \ne 0” by De Morgan’s laws. If x \ne 0, then x^2 > 0 and y^2 \ge 0, so x^2 + y^2 > 0; the case y \ne 0 is the same.
(\Leftarrow) If a = b, then b = a \cdot 1 and a = b \cdot 1. (\Rightarrow) Write b = ak and a = bl with integers k, l. Then a = akl, and a > 0 gives kl = 1. Since a, b > 0, both k and l are positive, so k = l = 1 and b = a.
False. (\Rightarrow) holds: if ab is odd, neither factor is even (if a = 2k, then ab = 2(kb) is even, and likewise for b), so a = 2k + 1, b = 2j + 1 and a + b = 2(k + j + 1) is even. (\Leftarrow) fails: a = b = 2 gives a + b = 4, even, but ab = 4 is not odd.
False. (\Leftarrow) holds: if x > 4, then x > 0 and x^2 = x \cdot x > 4x > 16. (\Rightarrow) fails: x = -5 has x^2 = 25 > 16 but x \le 4.
False. (\Rightarrow) holds: b = ak with a, b > 0 forces k \ge 1, so b = ak \ge a. (\Leftarrow) fails: a = 2, b = 3 has 2 \le 3 but 2 \nmid 3.
False. (\Leftarrow) holds: a product of two positive numbers is positive. (\Rightarrow) fails: x = y = -1 gives xy = 1 > 0. Corrected: xy > 0 if and only if (x > 0 and y > 0) or (x < 0 and y < 0). If xy > 0, neither factor is 0, and opposite signs would make xy < 0; two negatives multiply to a positive.
True. (\Rightarrow) If n + 3 = 5k, then n - 2 = 5k - 5 = 5(k - 1). (\Leftarrow) If n - 2 = 5j, then n + 3 = 5j + 5 = 5(j + 1).
Yes. \neg P \Rightarrow \neg Q is the contrapositive of Q \Rightarrow P, so it proves the backward direction.
No. \neg Q \Rightarrow \neg P is the contrapositive of P \Rightarrow Q, so she has proved the forward direction twice. In Exercise 9, “if x > 4 then x^2 > 16” and “if x^2 \le 16 then x \le 4” are both true, yet the biconditional is false.
(a) \Rightarrow (b): n = 2k gives n + 5 = 2(k + 2) + 1. (b) \Rightarrow (c): n + 5 = 2m + 1 gives n = 2m - 4 and 3n = 2(3m - 6). (c) \Rightarrow (a) by contraposition: n = 2k + 1 gives 3n = 6k + 3 = 2(3k + 1) + 1, odd.
(a) \Rightarrow (b): n = 3k gives n + 6 = 3(k + 2). (b) \Rightarrow (c): n + 6 = 3j gives 4n = 4(3j - 6) = 3(4j - 8). (c) \Rightarrow (a): if 4n = 3m, then n = 4n - 3n = 3(m - n).
Four statements: 4 proofs in a cycle; the claim holds 4 \cdot 3 = 12 conditionals. For n statements: n proofs and n(n - 1) conditionals.
No. Nothing proved leads out of D, so D \Rightarrow A does not follow. Adding D \Rightarrow A or D \Rightarrow B finishes it (each closes a cycle through all four); D \Rightarrow C does not.
5 - 2x < 11 \iff -2x < 6 \iff x > -3. The first step subtracts 5, undone by adding 5. The second divides by -2 and reverses the inequality, undone by multiplying by -2, which reverses it back.
x^2 + 4 \ge 4x \iff x^2 - 4x + 4 \ge 0, and this holds \iff (x - 2)^2 \ge 0, each step subtracting 4x or rewriting the same number. The last statement is true because a real square is never negative. The proof reads the chain upward, from the true statement to the claim, which is why every link must reverse.
x = 3. Squaring gives 2x + 3 = x^2, so (x - 3)(x + 1) = 0 and x = 3 or x = -1. The squaring step holds one way only. Checking: \displaystyle \sqrt{9} = 3 works; \displaystyle \sqrt{1} = 1 \ne -1.
Dividing by x requires x \ne 0. The forward direction fails at x = 0, where 0^2 = 2 \cdot 0 but 0 \ne 2; the backward direction is fine. Correctly, x^2 = 2x \iff x(x - 2) = 0, so x = 0 \text{ or } x = 2.
Assume B; B \Rightarrow C gives C, and C \Rightarrow A gives A. Assume C; C \Rightarrow A gives A, and A \Rightarrow B gives B. Without C \Rightarrow A, no proved arrow leaves C, so nothing gives C \Rightarrow A or C \Rightarrow B.
A = B means: for every x, x \in A \iff x \in B. The direction x \in A \Rightarrow x \in B shows A \subseteq B, and x \in B \Rightarrow x \in A shows B \subseteq A.