11

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.

Grigory M
  • 211
  • 1
  • 9
  • 3
    My linear algebra textbook does a lot of that. But I bet that's the advanced example you don't want. – Sue VanHattum Jan 09 '15 at 01:58
  • 5
    An example from graph theory is to prove the equivalence of various definitions of trees: http://en.wikipedia.org/wiki/Tree_%28graph_theory%29#Definitions. This is done in Harary's book: http://books.google.com/books/about/Graph_Theory.html?id=9nOljWrLzAAC – M. Vinay Jan 09 '15 at 02:43
  • 3
    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. – GPerez Jan 10 '15 at 00:39
  • 1
    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) $? – Alexander Gruber Jan 10 '15 at 18:50
  • 1
    What mathematical background do you want to assume of your ordinary high school student? – KCd Jan 14 '15 at 09:34
  • @SueVanHattum Yes, I'm afraid... – Grigory M Jan 14 '15 at 09:48
  • @M.Vinay That sounds good, hank you! (I don't have access to the book, but the idea is more or less clear.) Maybe you should post this (with minimal details) as an answer? – Grigory M Jan 14 '15 at 09:49
  • @GPerez I'm afraid that's too advanced for my purposes. (But, yes, in principle linear algebra — and general topology give some examples of cycles of implications.) – Grigory M Jan 14 '15 at 09:53
  • @KCd What I actually want is '6-7 класс' — which means basically no background (so I look for something like equivalent definitions of trees). But for 'stackexchange purposes' anything that can reasonably be considered 'high school' is fine — maybe someone else will find it useful. – Grigory M Jan 14 '15 at 09:57
  • Вы преподаватель? – KCd Jan 14 '15 at 11:29
  • There's a nice example of this on the topic of regular polyhedra in Cromwell's Polyhedra, chapter 2 I think. – Marius Kempe Feb 01 '15 at 02:26

2 Answers2

8

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$

Community
  • 1
Bill Dubuque
  • 1,038
  • 1
  • 8
  • 12
2

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.
dustin
  • 245
  • 3
  • 7