9.0: Introduction

We’ve seen a lot of pretty sights on our cool brisk walk. We’ve caught a glimpse of the simple elegance of sets and relations, the precision of probabilistic reasoning, the recursive structure of trees, the explosive nature of combinatorics, and much more. None of these things have we plumbed to the depths, but we’ve appreciated their beauty and taken note of where they stood along our blazed trail. You’ll remember this hike when you run into such concepts again and again in future computer science and math courses, and in your career beyond academics.

Now we have one more stop to make before returning to the trailhead, and that deals with the notion of proof. As we’ve studied these various mathematical entities, I’ve pointed out certain of their properties. A free tree has one more vertex than edge, for example. The cardinality of the union of two sets is at least as big as each of their individual unions. If you flip-all-the-bits-and-add-one in a two’s complement scheme, and then perform that flip-and-add operation again, you’ll return to the original number. But with a few exceptions, we haven’t proven any of these things. I’ve just stated them, and you’ve taken them on faith.

In order to establish reliable truth, of course, professional mathematicians aren’t satisfied with unsubstantiated statements. They need to be convinced that the claims we make do truly hold, and provably so, in all circumstances. What they seek is a proof of a claim: an irrefutable sequence of logical steps that leads inescapably from our premises to our conclusion. There are several ways to construct a convincing proof, and this chapter will highlight some of them.

Most authors of discrete math texts, by the way, interweave the concept of proof throughout the entire book. I’m taking a radical departure by deferring this fundamental idea until the very end. Why did I make this choice? A couple of reasons. First, as I said at the very beginning, my target audience for this book is future practitioners, not theoretical researchers. I think most practicing computer scientists need fluency with the tools of discrete math, not the ability to devise new fundamental theorems about them. We mostly need to use, not to prove. The second reason is that I’ve found that interspersing proofs throughout the presentation often distracts the reader from the concepts at hand, since the focus shifts slightly from the concept being discussed (the function, the directed graph, what have you) to the proof about the concept. When the proof itself takes center stage, it forces the actual subject matter to share the limelight. And with technical material like this, we need all the light we can get.