# Examples of proofs that use a cycle of implications to prove equivalence

I'm looking for some examples of proofs where it's easier to prove 'cyclical implications' $A\implies B\implies C\implies A$ than to prove $A\iff B$ directly.

I can think of some (relatively) advanced examples — but I'm looking for examples accessible to (ordinary) high-school students.

• My linear algebra textbook does a lot of that. But I bet that's the advanced example you don't want. Jan 9, 2015 at 1:58
• An example from graph theory is to prove the equivalence of various definitions of trees: en.wikipedia.org/wiki/Tree_%28graph_theory%29#Definitions. This is done in Harary's book: books.google.com/books/about/Graph_Theory.html?id=9nOljWrLzAAC Jan 9, 2015 at 2:43
• Are linear systems and matrices a part of high school curricula where you teach? If so, the usual set of equivalent conditions for a matrix being invertible might be a good example. Jan 10, 2015 at 0:39
• If they know about complex numbers, maybe you could use something along the lines of $x-a$ divides $p(x)$ if $p(a) = 0$ if $p(a^*) =0$ if $x-a^*$ divides $p(x)$? Jan 10, 2015 at 18:50
• What mathematical background do you want to assume of your ordinary high school student?
– KCd
Jan 14, 2015 at 9:34

Proving equivalent the below characterizations of squarefree naturals is quite elementary employing cyclic inferences (assuming one knows the existence and uniqueness of prime factorizations).

Theorem $\$ The following are equivalent for a natural number $\,q > 1$

$(1)\qquad\quad n^2\!\nmid q\,\$ for all naturals $\,n > 1$

$(2)\qquad\quad p^2\!\nmid q\ \$ for all primes $\,p$

$(3)\qquad\quad q\,$ is a product of distinct primes

$(4)\qquad\quad q\mid n^k\Rightarrow\, q\mid n\,\$ for all naturals $\,n,k$

Proof $\$ All $\,(n)\Rightarrow (n\!+\!1)$ are obvious. $\,(4)\,\Rightarrow\,(1)\,$ may be proved as follows

$\qquad\ \$ If $\ q = an^2\,$ then $\ q\mid (an)^2\,\overset{ (4)}\Rightarrow\ q\mid an\,\Rightarrow\,an^2\mid n\,\Rightarrow\,n=1$

Remark $\$ For further characterizations see here, which includes the little known $\, q^q\!\mid n^n\Rightarrow\, q\mid n$

• very nice — and exactly on the level I had in mind. thank you! Jan 27, 2015 at 19:15

## Geometry

The following two theorems came from Sonoma.

If a line intersects two lines then the following conditions are equivalent.

1. The alternate interior angles are the same size.
2. The corresponding angles are the same size.
3. The opposite interior angles are supplementary.

If two lines are crossed by a third, then the following conditions are equivalent.

1. The alternate interior angles are the same size.
2. The corresponding angles are the same size.
3. The opposite interior angles are supplementary.
4. The two lines are parallel.

## Algebra

I am not sure what to think of the difficult of this one but it could be explainable.

Let $p\geq 2$ be an integer. Then the following conditions are equivalent.

1. $p$ is prime.
2. For any $a\neq 0\in\mathbb{Z}_p$, the equation $ax=1$ has a solution in $\mathbb{Z}_p$.
3. Whenever $ab=0$ in $\mathbb{Z}_p$, then $a=0$ or $b=0$ in $\mathbb{Z}_p$.

Let $\mathbf{A}$ be an $n\times n$ matrix. Then the following are equivalent. (Note you could make this for only $2\times 2$ matrices so it isn't over the head of the students.)
1. $\mathbf{A}$ is row equivalent to $\mathbb{I}$
2. $\mathbf{A}$ is a product of elementary matrices
3. $\mathbf{A}$ is invertible
4. The system $\mathbf{Ax}=\mathbf{0}$ has only the trivial solution
5. For any $n$ dimensional vector $\mathbf{b}$, the system $\mathbf{Ax}=\mathbf{b}$ has a unique solutions.