Discrete Structures: Construction Order

Margaret Fleck, University of Illinois

When teaching students to construct proofs, it's important to emphasize the distinction between

Lectures and tutorial materials should demonstrate both orders. That is, I show the stages of construction and, at the end, the final product in logical order. And I show explicitly the goals and scratch work that a beginner should write out to avoid getting lost.

Construction vs. logical order

For many proofs, construction order and logical order are very different. A typical direct proof is most easily constructed by working from both ends towards the middle. I write out the assumptions at the start and the desired conclusion at the end, with a gap in the middle. The gap is then gradually reduced by algebra, or put into simpler terms by substituting definitions for key concepts. At each step, I do a "compare and contrast" between the material before and after the gap. When the gap closes, we have a proof written out in logical order.

Working backwards from the goal, as well as forwards from the assumptions, is especially important when the proof contains a step where information is lost. For example, suppose that we have discovered that \(x > 10\) and then we then infer that \(x \ge 10\) or even \(x \ge 6\). Such steps are particularly common in proofs involving inequalities. But no reasonable person would write such a step without a clear model of where the proof is headed.

Write the goal at the end

It's tempting to keep the goal in your head, or perhaps say it out loud, so that you can write the proof from top to bottom. This is ok for you, because you're finding the proof easy. But CS students tend to copy your behavior. High school has trained them to think they are the top kid in the class and it's safe to cut corners. In college, they are somewhere in the middle of the class, the work is challenging, and they are much more likely to complete a proof if they write down the goal. So you must model writing down the goal when you demonstrate proof construction.

In later math courses, it's common to write the proof in one pass from top to bottom, including occasional comments about what we still need to show. However, it's easy for a beginner to misread a goal written near the top as a fact that has already been proven. This is especially true when taking exams, which are stressful even if there is plenty of time. Misreading one's own work is even more likely to happen when students abbreviate or omit connector words, as they often do. Writing the goal at the end is a habit that will help them stay organized under pressure.

So I always write the assumptions, leave a suitable amount of blank space, and then write the goal in its final position at the end.

Using scratch paper

Because high school was easy for our students, they are used to writing out each answer in one draft, perhaps making minor corrections with an eraser. This stops working when the material becomes difficult for them, which is often the Discrete Mathematics course. I explicitly model using scratch paper to do preliminary work when a significant part of the proof needs to be built backwards.

Showing that a function is onto is a classic situation where proofs are almost always constructed backwards. Consider this finished proof:

Claim: Let \(f: \mathbb{Z}^2 \rightarrow \mathbb{Z}\) such that \(f(x,y) = 2x + 3y\). Then f is onto.

Proof: Let \(k \in \mathbb{Z}\). Consider \((-k,k) \in \mathbb{Z}^2\). \(f(-k,k) = 2(-k) + 3k = k\). So (-k,k) is a pre-image of k. Since k was arbitrarily chosen, this means that every value k has a pre-image. So f is onto.

The value in the second sentence comes out of nowhere. An experienced reader of mathematics will recognize the word "consider" as a hint that the writer knows their step, although logically sound, is not motivated by the previous work in the proof. The magic value in this step came from scratch work that looked something like this:

\(f(x,y) = 2x + 3y\)

How to find x and y that will give me k as output?

It's linear. So perhaps if I find x and y that will give me 1 as an output value?

So solve \(f(x,y) = 2x + 3y = 1\)

So maybe \(x= -1\) and \(y = 1\). And then a general solution is \(x= -k\) and \(y = k\).

So I model doing the search for a pre-image on scratch paper. Having found the magic formula, I reverse the key steps in my scratch work to produce the final proof out in logical order.

A more complex example

Consider this fragment from an induction proof where \(k\) is known to be a positive integer and I need to prove that \(\frac{1}{k+1} + \frac{k}{2} + 1 \le \ \frac{k+1}{2} + 1\).

Since \(k \ge 1\), \(\frac{1}{k+1} \le \ \frac{1}{2}\).

Also \(\frac{1}{2} = \ \frac{k+1}{2} - \frac{k}{2}\).

Combining these, we have \(\frac{1}{k+1} \le \ \frac{k+1}{2} - \frac{k}{2}\).

Since \(\frac{1}{k+1} \le \ \frac{k+1}{2} - \frac{k}{2}\), we have \(\frac{1}{k+1} + \frac{k}{2} \le \ \frac{k+1}{2}\). So \(\frac{1}{k+1} + \frac{k}{2} + 1 \le \ \frac{k+1}{2} + 1\).

The first two lines aren't algebraically difficult, but they are unmotivated. They came from preliminary scratch work that was out of logical order, mostly backwards in a way that is completely unacceptable in the final proof. Something like this:

I need to end up with \(\frac{1}{k+1} + \frac{k}{2} + 1 \le \ \frac{k+1}{2} + 1 \).

Remove the common term from both sides, so as to isolate the difficult part: \(\frac{1}{k+1} + \frac{k}{2} \le \ \frac{k+1}{2} \).

Fiddle around with various things that don't work out and eventually try moving \(\frac{k}{2}\) to the other side: \(\frac{1}{k+1} \le \ \frac{k+1}{2} - \frac{k}{2} \).

\(\frac{1}{k+1} \le \ \frac{k+1}{2} - \frac{k}{2} = \frac{1}{2}\), which is obviously true because \(k \ge 1\).

Students need to be taught this process explicitly. They need to give themselves permission to work out of order on the scratch paper. But they need to be clear on the fact that the steps must be rearranged into logical order in the final version.