When proving that some statements are equivalent, should one use a circular chain of implications?
If I have multiple statements and have to prove that they are all equivalent, which proof strategy should I use?
E.g. let's say I have statements A, B, C and D and need to show that they are all equivalent.
I know that I can prove equivalence by proving: $A\implies B\implies C\implies D\implies A$.
My question is do I have to use a circular pattern or can I e.g., if $A\implies C$ is easier to prove than $B\implies C$, simply prove $A\implies B$, $A\implies C$, $C\implies D$, $D\implies A$ or any other random pattern?
$\endgroup$ 24 Answers
$\begingroup$It would not be enough to show that $A\to B$, $A\to C$, $C\to D$, and $D\to A$: that would show that $A,C$, and $D$ are equivalent and that any one of them implies $B$, but it would not show that $B$ was equivalent to the other three: it might be a strictly weaker statement.
Proving any collection of implications that gives you a ‘path’ from any statement in the set to any other statement in the set is sufficient. For example, you could prove $A\leftrightarrow B$, $A\leftrightarrow C$, and $A\leftrightarrow D$.
$\endgroup$ $\begingroup$You don't need to use exactly the pattern $A\Rightarrow B \Rightarrow C \Rightarrow D \Rightarrow A$, but you do need to check that you can follow arrows from any of the statements to any other. In the example you gave, you can't get $B\Rightarrow A$ or $B\Rightarrow C$ (for instance), but if you also proved $B\Rightarrow A$ then you would be done.
$\endgroup$ $\begingroup$Suppose a,b,c,d are vertices in a directed graph.
and $(x,y)$ is an edge if you have proven $a\rightarrow b$.
Then you have proven equivalence if and only if there is a directed path from x to y for every $x,y\in {a,b,c,d}$
This is a representation of your digraph
However how can you get from point $b$ to another point?
Apparently this already has a name, see implication graph
A digraph that satisfies the desired condition is called a strongly connected digraph
$\endgroup$ 4 $\begingroup$Any pattern that satisfies the condition that you can follow the implication arrow to go from any proposition to any other proposition works.
$\endgroup$
