How Does a Chain of Implications Prove Conditions Equivalent?

A list of statements is not automatically a list of equivalent statements just because you can prove implications between some of them. To prove equivalence, you need to show that each condition implies the others. A convenient way is to arrange the implications in a cycle.

This article explains how to check such a chain and illustrates the method with three conditions on an integer.

The basic criterion

Suppose the conditions are $P_1,P_2,\ldots,P_n$. They are equivalent if, for every pair $i,j$, both implications hold:

$$P_i\Rightarrow P_j \quad\text{and}\quad P_j\Rightarrow P_i.$$

You do not have to prove every pair separately. It is enough to establish a cycle such as

$$P_1\Rightarrow P_2\Rightarrow P_3\Rightarrow\cdots\Rightarrow P_n\Rightarrow P_1.$$

By transitivity, you can follow the arrows from any condition to any other. For example, in a three-condition cycle, $P_2\Rightarrow P_3\Rightarrow P_1$, so $P_2\Rightarrow P_1$. The cycle also provides the reverse route, $P_1\Rightarrow P_2$, proving $P_1\Leftrightarrow P_2$. The same reasoning applies to every pair.

The order of the conditions does not matter. What matters is that the arrows really do form a route from each condition to each other one. A simple cycle is one easy way to guarantee this.

A worked example

For an integer $n$, consider these conditions:

• $P$: $n$ is even.
• $Q$: $n^2$ is even.
• $R$: $n^2$ is divisible by $4$.

We will prove the cycle $P\Rightarrow R\Rightarrow Q\Rightarrow P$.

First, prove $P\Rightarrow R$. If $n$ is even, then $n=2k$ for some integer $k$. Therefore

$$n^2=(2k)^2=4k^2,$$

so $n^2$ is divisible by $4$. Thus $P\Rightarrow R$.

Next, prove $R\Rightarrow Q$. If $n^2$ is divisible by $4$, then $n^2=4m$ for some integer $m$. In particular, $n^2=2(2m)$ is even. Thus $R\Rightarrow Q$.

Finally, prove $Q\Rightarrow P$. Suppose $n^2$ is even. If $n$ were odd, it would have the form $n=2k+1$, and then

$$n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1,$$

which is odd. That contradicts the assumption that $n^2$ is even. So $n$ must be even, proving $Q\Rightarrow P$.

Together, the implications form the cycle

$$P\Rightarrow R\Rightarrow Q\Rightarrow P.$$

Therefore all three conditions are equivalent: $n$ is even if and only if $n^2$ is even if and only if $n^2$ is divisible by $4$.

How to organize your own proof

1. List the conditions precisely. Give each one a short label, and note any assumptions that apply to all of them. For example, “$n$ is an integer” matters in the example above.
2. Choose an order for the implications. Look for a route that uses definitions or familiar results naturally. The strongest-looking condition may be easiest to use first, but there is no required order.
3. Prove each arrow on its own. For every implication, start by assuming its left-hand condition and derive its right-hand condition. Keep track of where each assumption is used.
4. Check that the arrows close. If the last condition does not lead back to the first, you have not yet established a cycle. You may need an additional implication or a different route.
5. Write the equivalence explicitly. Once the cycle is proved, state that all the conditions are equivalent. Do not leave the reader to infer which statements the argument connects.

You can also prove equivalence by fixing one condition, say $P_1$, and proving both directions between it and each other condition: $P_1\Rightarrow P_i$ and $P_i\Rightarrow P_1$ for every $i$. That method may be clearer when a cycle would require awkward intermediate steps.

Common mistakes

• Stopping after a one-way chain. From $P\Rightarrow Q\Rightarrow R$, you can conclude $P\Rightarrow R$, but not that the three conditions are equivalent. You still need implications back to $P$ (or another proof connecting the conditions in both directions).
• Reversing an implication without proof. Knowing $P\Rightarrow Q$ does not show $Q\Rightarrow P$. The reverse implication is a separate claim and may be false.
• Using circular reasoning. Each arrow needs a justification that does not assume the equivalence you are trying to prove. Using a previously established equivalent condition is valid only if that result was proved independently and its assumptions apply.
• Forgetting the domain. A statement can be true for integers and false for real numbers, or vice versa. Include the domain in the setup and use it when applying definitions.
• Confusing a chain with a cycle. A chain has a beginning and an end; a cycle includes a route back. Equivalence requires enough implications to connect every condition in both directions.