Proof Differences

How do we teach proof techniques to students who have not had any exposure to proofs before? There are (at least) two things to emphasise, I think:

  1. A proof is a piece of literature.
  2. Proofs of the same fact will look differently, depending on the audience.

To illustrate this, consider the following example from algebra.

Let $S$ be a set and $\cdot$ be an operation on $S$, i.e., $\cdot: S \times S \rightarrow S$. Then the pair $(S, \cdot)$ is called a semigroup if and only if $\cdot$ is associative, i.e., we have for all $a$, $b$, and $c \in S$:

\begin{equation} a\cdot(b\cdot c)= (a\cdot b)\cdot c. \end{equation}

If $(S, \cdot)$ is a semigroup, then an element $e \in S$ is called a neutral element if and only if for all $a \in S$, we have

\begin{align} a \cdot e &= a; \qquad(1)\\
e \cdot a &= a. \qquad(2) \end{align}

Lemma 1. Let $(S, \cdot)$ be a semigroup. Then $(S, \cdot)$ has at most one neutral element.

Note that this formulation syntactically separates the premiss from the conclusion by introducing the premiss with “Let” and the conclusion with “Then”. However, it is also common to find Lemma 1 written like this:

Lemma 1a. Any semigroup has at most one neutral element.

There is something to be said for this formulation because the precise formulation of the semigroup as “$(S, \cdot)$” doesn’t matter: it is introduced once in the premiss and used verbatim, once, in the conclusion. Therefore it can be left out. I like the first form, especially for beginners, since it gives them something to hold on to during their proof, already giving the set and the operation a name and thus saving them from having to introduce symbols themselves.

A proof that you find in many algebra textbooks might go like this (this one is from Karpfinger, Meyerberg, Algebra, 4th edition, Springer Verlag, 2017; translation mine):

Proof 1. If $e$ and $e’$ are two neutral elements, we have:

\begin{align} e &= e \cdot e’ &\text{(since $e’$ is neutral)}\\
&= e’ \qquad &\text{(since $e$ is neutral)}. \end{align}

I guess that a beginner in proving things will find this very confusing. Where do $e$ and $e’$ come from? Why is the proof just two lines and what exactly has been proved at the end?

So for a beginner, I suggest to expand the proof, for example like this:

Proof 1a. The proof is by contradiction. Assume therefore that $(S, \cdot)$ is a semigroup that has not at most one neutral element. This must mean that it has more than one neutral element, which means that it must have two or more such elements. That means that there are $e_1, e_2 \in S$ with $e_1 \ne e_2$, such that equations (1) and (2) hold when we replace $e$ by $e_1$ and $e_2$, respectively. For all $a \in S$, we therefore have:

\begin{align} a \cdot e_1 &= a\qquad(3), & a \cdot e_2 &= a;\qquad(4)\\
e_1 \cdot a &= a\qquad(5), & e_2 \cdot a &= a.\qquad(6) \end{align}

Since these equations hold for all $a \in S$, it must be true therefore that equation (3) holds for $a = e_2$:

\begin{equation} e_2 \cdot e_1 = e_2.\qquad(7) \end{equation}

Likewise, equation (6) must be true for $a = e_1$:

\begin{equation} e_2 \cdot e_1 = e_1.\qquad(8) \end{equation}

We can now put equations (7) and (8) together. Reading equation (7) backwards, we get:

\begin{equation} e_2 = e_2 \cdot e_1 = e_1.\qquad(9) \end{equation}

We have thus established that $e_1 = e_2$. But this is a contradiction because we had assumed that $e_1 \ne e_2$ above. This means that the assumption that $(S, \cdot)$ has two or more neutral elements cannot be sustained, and therefore that $(S, \cdot)$ can have only zero or one neutral elements. QED.

First, a small detail: this proof has not used the fact that $\cdot$ is associative. That means that neutral elements are unique even when the operation is not associative. This seems to me to be a possible generalisation.

Next, you can now see how much detail Proof 1 left out! Of course, for someone who is reasonably well versed in proof techniques, Proof 1 is to be preferred over Proof 1a, but for beginners (such as those students that come to my employer) that second form is probably much more understandable.

Note also that Proof 1a takes care to present a continuing narrative. This proof is a text, not just some formulas. It tries to explain something to the reader instead of asking them to figure it out themselves. Punctuation is meticulously inserted into formulas to make them part of the text. I think this is important.

Following up on this, I would then ask questions that test boundary cases, just like in coding. Such a questions could be:

  • If $S$ is the empty set and $\cdot$ the empty operation, is $(S, \cdot)$ a semigroup?
  • If $(S, \cdot)$ is a semigroup with neutral element, what can you say about $|S|$?
  • If $(S, \cdot)$ and $(T, \cdot)$ are semigroups with neutral elements $e_S$ and $e_T$, respectively, and if $T \subseteq S$, is there a relationship between $e_S$ and $e_T$?

The latter is a lemma in its own right.

Finally, if I were teaching this, I would emphasise the engineering aspect of these proofs: how do we get the correct idea for a proof? If we have an idea, how do we know whether it is correct? If it turns out not to be quite correct, can we fix it? And so on. I would also show some good examples of proofs, of the “1a” type. Then I would teach them first to write “1a”-type proofs and then later the more abbreviated form. As always, you can’t write well if you don’t write a lot (much of which will be crap, especially at first), and you can’t write well if you don’t also read a lot.