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,
“Today is Tuesday” or “It is raining”
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:
Statement 1: “The Borda Count social choice always has a plurality of the first place votes.”
Statement 2: “A zero-sum game with a saddle point has a Nash equilibrium.”
Statement 3: “There is a guaranteed winning strategy for Player 1 in Chess.”
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.
Review the options below to login to check your access.
Log in with your Cambridge Aspire website account to check access.
If you believe you should have access to this content, please contact your institutional librarian or consult our FAQ page for further information about accessing our content.