11
$\begingroup$

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.

$\endgroup$
11
  • 3
    $\begingroup$ My linear algebra textbook does a lot of that. But I bet that's the advanced example you don't want. $\endgroup$
    – Sue VanHattum
    Jan 9, 2015 at 1:58
  • 5
    $\begingroup$ 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 $\endgroup$
    – M. Vinay
    Jan 9, 2015 at 2:43
  • 3
    $\begingroup$ 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. $\endgroup$
    – GPerez
    Jan 10, 2015 at 0:39
  • 1
    $\begingroup$ 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) $? $\endgroup$ Jan 10, 2015 at 18:50
  • 1
    $\begingroup$ What mathematical background do you want to assume of your ordinary high school student? $\endgroup$
    – KCd
    Jan 14, 2015 at 9:34

2 Answers 2

8
$\begingroup$

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$

$\endgroup$
1
  • 1
    $\begingroup$ very nice — and exactly on the level I had in mind. thank you! $\endgroup$
    – Grigory M
    Jan 27, 2015 at 19:15
2
$\begingroup$

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$.

More Advanced Option

If the class is familiar with linear systems, the following theorem could be used.

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.