Proofs Involving Conjunctions and Biconditionals

How do you prove two things at once? You prove them one at a time. The strategy for a conjunction is the simplest in this chapter, split the goal into independent sub-proofs, but it underpins every "iff" theorem in mathematics. Biconditionals $P \Leftrightarrow Q$ are conjunctions in disguise ($(P \Rightarrow Q) \wedge (Q \Rightarrow P)$), so they too split. The discipline you learn here, signposting each part, handling them independently, then concluding, is what keeps multi-part proofs from collapsing into incoherent mush, especially when each direction needs a different proof technique.

Proving a conjunction

To prove $P \wedge Q$:

1. Prove $P$.
2. Prove $Q$.
3. Conclude $P \wedge Q$. $\blacksquare$

Signpost the two parts clearly: "First, we show $P$... Next, we show $Q$..." Each sub-proof may use any strategy, direct, contrapositive, contradiction, case analysis, and the two sub-proofs are independent. The reader should never wonder which conjunct you are currently arguing.

Using a conjunctive given

If you have a given $P \wedge Q$, you may freely use both $P$ and $Q$ separately. This is the easy direction: a conjunction in the givens is a gift, two facts for the price of one. Unpack it explicitly: "from the given $P \wedge Q$ we have $P$; we also have $Q$."

Proving a biconditional

A biconditional $P \Leftrightarrow Q$ means "$P$ if and only if $Q$," equivalent to $(P \Rightarrow Q) \wedge (Q \Rightarrow P)$. So a biconditional proof is structurally two conditional proofs:

1. ($\Rightarrow$) Assume $P$, prove $Q$.
2. ($\Leftarrow$) Assume $Q$, prove $P$.
3. Conclude $P \Leftrightarrow Q$. $\blacksquare$

The two directions can use entirely different techniques. A famous example: "an integer $n$ is even iff $n^2$ is even." The forward direction ($n$ even $\Rightarrow$ $n^2$ even) is a one-line direct proof. The backward direction ($n^2$ even $\Rightarrow$ $n$ even) is cleanest by contrapositive ($n$ odd $\Rightarrow$ $n^2$ odd). Always label which direction you are doing.

Circular chains for multiple equivalences

When proving $P_1 \Leftrightarrow P_2 \Leftrightarrow P_3 \Leftrightarrow \cdots \Leftrightarrow P_n$, instead of proving $\binom{n}{2}$ pairwise equivalences, prove the circular chain:

This gives all equivalences via transitivity. For $n = 3$, you prove 3 implications instead of 6 separate iffs. Circular chains are how textbooks present "the following are equivalent" (TFAE) theorems: characterise the same condition six different ways and prove the chain once.

How to lay out a clean multi-part proof

Use whitespace, labels, and topic sentences. A two-part conjunction proof might look like:

"Proof. We show both $P$ and $Q$. Part 1 (proof of $P$): <argument>. Part 2 (proof of $Q$): <argument>. Since both parts hold, $P \wedge Q$. $\blacksquare$"

This structure is not decorative; it lets a reader scan to the part they want to check and signals to a grader (or proof assistant) that you understand the conjunctive nature of the goal.

Pause and think: To prove "an integer $n$ is divisible by 6 iff $n$ is divisible by 2 and divisible by 3," what are the two directions? Which direction needs the fact $\gcd(2, 3) = 1$?

Try it

• Predict, before writing: in the proof of "$n$ even iff $n^2$ even," which direction will you do by direct proof and which by contrapositive? Why?
• Skeleton: write the topic sentences for the two parts of a proof that "if $n$ is even, then $n^2$ is even AND $n^3$ is even."
• Spot the flaw: a student writes "Proof of $P \Leftrightarrow Q$: Assume $P$. Then $Q$. Therefore $P \Leftrightarrow Q$." What is missing?
• Circular chain practice: for an integer $n$, set $P_1$: '$n$ is even,' $P_2$: '$n + 2$ is even,' $P_3$: '$n - 4$ is even.' Sketch the three implications you would prove to establish all three equivalences.
• Distinguish: which form fits this statement, "For real $x$, $x^2 = 0$ iff $x = 0$"? Conjunction, biconditional, or both?

A trap to watch for

The single most common biconditional error is to prove only one direction and call it done. "Assume $P$. Then $Q$. So $P \Leftrightarrow Q$" is HALF a proof: you have proven $P \Rightarrow Q$. You still must show $Q \Rightarrow P$. The trap is that the forward direction often feels obvious enough that the backward direction seems implied, but logically, "$P \Rightarrow Q$" and "$Q \Rightarrow P$" are independent statements. Many false "biconditional" claims fail in exactly one direction (e.g. "$x^2 > 0$ iff $x > 0$", the forward direction is false for $x = -1$). Always do both, and label them clearly.

What you now know

You can prove a conjunction $P \wedge Q$ by independent sub-proofs of $P$ and $Q$, and you can prove a biconditional $P \Leftrightarrow Q$ by handling both implications in turn, often with different techniques. You can collapse multiple equivalences into a single circular chain, and you know how to typeset a multi-part proof so the reader (and your future self) can follow it. The remaining shapes you might meet are disjunctions and existence-with-uniqueness; both are coming up next.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §3.4.
• Hammack, R. (2018). Book of Proof (3rd ed.). Open-source textbook, ch. 7 (Biconditional).
• Solow, D. (2014). How to Read and Do Proofs (6th ed.). Wiley, ch. 8 (Iff).
• Bloch, E. D. (2011). Proofs and Fundamentals. Springer, ch. 3.
• Pierce, B. C. et al. (2018). Software Foundations, Vol. 1: Logical Foundations. Online textbook (Coq), ch. 'Logic' (iff destruct).