80-110: The Nature of Mathematical Reasoning

Spring 1998

Class 3: 1/20/98

1. Proof and Truth

As we discussed last class, the ancient Greeks (e.g., Pythagoras) set mathematics on its modern course by bringing the notion of rigorous proof to the forefront. The idea of a deductive "demonstration" was made the standard in mathematical argumentation, and it has remained so ever since.

Nevertheless, mathematicians engage in at least two distinct sorts of activities: conjecture and proof. The art of conjecturing involves seeing patterns, discovering interesting claims, articulating propositions that would be worthy of proof, etc. For example, undoubtedly many surveyors were aware, at least in a rough way, of the Pythagorean theorem: that in a right triangle, the square of the hypotenuse is equal to the sum of the squares of the sides.

Mathematicians rarely get famous for conjectures, however. Status comes with proofs of interesting theorems. As Peterson describes in the "Burden of Proof," those who have claimed to have proved a conjecture but have not are infamous.

What makes something a proof rather than a "nice try" is subtle topic we will cover in more detail later, but that aside, the history of famous problems and their proofs can be quite dramatic. Two recent episodes that Peterson doesn't cover stand out. The first is the map coloring problem. Suppose the problem is presented to you in this way:

Map Coloring Problem:

Suppose you are a map publisher, and it is 1954, and color printing presses have just come on the market. You face a decision between buying printing presses with different color capabilities: 2 color press $100,000 3 color press $500,000 4 color press $1,000,000 5 color press $2,000,000 6 color press $5,000,000

You donÕt know what maps you will be printing over the next decade or so, and you need to know how many colors are sufficient to color any map in a way that no two adjacent entities (they share a common border) will have to be given the same color, thereby making it hard to read. Call such maps Òeasily readable.Ó Obviously, the fewer colors that will work, the better. Points donÕt count as an entity.

1) My youngest daughter (Katie) conjectured that two colors is enough, and that we can get away fro $100,000. Prove she is wrong by producing a counterexample: draw a map that cannot be made Òeasily readableÓ with just two colors.

2) My middle daughter (Robin) conjectures that 3 colors is always enough. Is she right? Can you find a couterexample?

The answer to 1 is that two is not enough, as you can see from the left side of the figure below. No matter what we put in for the ?, it will border with both region 1 and 2, so it must be different from both. The right side is a counterexample to Robin's conjecture.


The general answer, as it turns out, is 4. Proved in 1976 by Appel and Haken, an interesting part of the story is that the computer played a crucial role in the proof. Taking 1200 hours of supercomputer time to verify a lemma that was proved by exhaustively searching a large but finite collection of cases, for the first time a major proof was presented that could not be entirely verified by hand in less than several millenia.

2. The Structure of Proof

A proof is a deductively valid argument. begins with statements called premises, and ends with a statement called the conclusion. Statements can be true or false, but arguments are neither true or false. Arguments can be valid, invalid, sound, deductive, inductive, etc. The statements in arguments can be true or false, but the argument as a whole is assessed not by the truth or falsity of its components, but by the relationships between its components. Consider the following example arguments , each of which begins with the premise that P is a whole number, and concludes that P2 is even:

Argument 1

Premise: The whole number P is even.

1) so there is some other whole number Q such that: P = 2Q

2) squaring both sides gives: P2 = (2Q)2

3) thus P2 = 4Q2

4) P2 = 2(2Q2)

5) Since 2Q2 is a whole number, then

Conclusion: P2 is even.

Argument 2

Premise: The whole number P is even.

1) If P = 2, then P is even and P2 = 4, which is even.

2) If P = 4, then P is even and P2 = 16, which is even

3) If P = 6 then P is even and P2 = 36, which is even

4) If P = 8, then P is even and P2 = 64, which is even

5) If P = 10, then P is even and P2 = 100, which is even

Conclusion: P2 is even.

Argument 3

Premise: The whole number P is even.

1) 7+8 = 15

2) 9*9= 81

Conclusion: P2 is even.

Each argument above contains true premises, a true conclusion, and all the steps in the argument are true. The first argument is deductively valid, the second a good inductive argument, and the third an example of an argument whose intermediate statements are true but completely irrelevant to the conclusion.

In a deductively valid argument, e.g., argument 1, there is a relationship between the premises and the conclusion such that if the premises are true, the conclusion must also be true. This should be a guarantee, not of the truth of the premises or the conclusion, but of the connection between the premises and the conclusion. In a deductively valid argument, there should be no possible way for the premises to be true and the conclusion false at the same time.

A valid deductive argument might have false premises and a false conclusion, or false premises and a true conclusion. For example, in this argument the premises and conclusion are false, but the argument is valid

Premise 1: 7=8

Premise 2: 8=9

Conclusion 7=9

If the premises were true, then the conclusion would be as well. As long as the connection between the premises and conclusion prohibits the possibility that the premises could be true and the conclusion false, the argument is valid.

In a good inductive argument, the truth of the premises and intermediate statements should make it likely that the conclusion is also true, but they do not guarantee its truth.

What is the nature of the guarantee that a deductive argument provides? Is it rooted in the structure of the world? The structure of language? Is it determined entirely by social convention, or is it rooted in something external to ourselves as knowers?


Back to Lecture Notes Index