In this chapter, we digress from our study of games and elections to focus more directly on the logic of mathematical proof. Our goal is to identify some proof methods that we have seen in the first part of the text and to introduce some that we will use in Parts II and III. We begin with the idea of a mathematical statement and the basic problem of constructing proofs and finding counterexamples. We then introduce proof methods for two types of mathematical statements: conditional statements and universal statements. We conclude with an introduction to the method of proof by induction. We apply this method to prove a version of Zermelo's Theorem (Theorem 4.17) for takeaway games.

Mathematical Statements

Like a coin flip, which offers two possible outcomes – a basic branching in a game of chance – the building blocks for a mathematical theory are statements with two possible values: true or false.

Definition 10.1

A mathematical statement is a statement that, by its wording, only admits two possible interpretations. The statement is true or the statement is false.

Mathematical statements arise frequently in ordinary language. For example,

Both are statements that can only be interpreted as true or false. Of course, there may be gray areas in such phrasings. Here are some examples of mathematical statements related to our topics of study:

There is no gray area for these statements. Statements 1 is a false statement. We can quickly check, for example, that the Democratic candidate D is the Borda Count social choice for the Third-Party Candidate Election (Example 6.9), whereas the Republican candidate R has the most first-place votes.