80-110: The Nature of Mathematical Reasoning

Spring 1998

Class 9: 2/17/98

 

1. Characterizing Deductive Validity

We define proof to be deductively valid if for any statement in the argument, it is not possible that it be false and the previous statements are true simultaneously. Having seen several examples of "proofs," and fallacious proofs, we want a theory that characterizes deductive validity. That is, we want a theory that separates arguments into those that are deductively valid and those that are not. Here are some candidate answers:

1) Every serious mathematician agrees that it is valid.

2) Each step in the proof is as close to 100% likely as we would like it to be, given the previous steps are true.

3) A machine could verify that each step follows a form which we know is valid.

The first of these answers is sociological and pragmatic, and on the face of it removes any objectivity from whatever it is that makes a proof valid. Suppose that when you wake up tomorrow you find out that Scheines has announced that he has found two whole numbers such that their ratio is equal to the square root of two. Every mathematician at CMU and Pitt has checked his proof and agrees it is valid. What would you think? Its a practical joke? Suppose that someone else announces that he has proved that 2,000 + 2,000 = 4,001, and every mathematician in the country agrees that the proof is valid. Would you believe it, or would you wonder if someone had slipped all the mathematicians hallucinogens?

Whereas judgements about whether a piece of music is a good piece of music seem to be irreducibly subjective, one suspects that judgements about things like whether an arithmetic problem in which 10 numbers were added was solved correctly are not. Judgements about deductive validity seem closer to judements about arithmetic than to those about music. It might not be possible to practically judge whether an argument is deductively valid, but it seems like there is some fact of the matter regardless of how people judge things. Indeed, for a concept like deductive validity or musical goodness to be objective, it ought to be true or false of an object regardless of whether subjects are around to judge the matter one way or the other. For example, whether or not dinosaurs lived before the first homo sapiens is an objective fact of the world, even if we can never go and check it directly.

The second answer is equally unsatisfying, for two reasons. First, it begs the question by redefining validity. Second, it is easy to create examples in which we can prove contradictions. Suppose it were correct, and we choose 1 in a million as the odds for each step to be false given the previous steps are true. Now suppose we are visited by a hard disk salesman who claims he can prove to us that his disks will not fail you for any number of years you want. Say you want trouble free disks for at least 10 years. He argues as follows:

1) For any given minute of operation, there is lower than a 1 in million chance of the disk failing.

2) The first disk you buy will not fail in the first minute.

3) The second disk you buy will not fail in the first minute.

.

.

n+1) The nth disk you buy will not fail in the first minute.

n+2) The first disk you buy will not fail in the second minute.

.

.

Big number) The last disk will not fail in the last minute of the 10th year.

Therefore, no disk will fail at any time in the first 10 years of operation.

Ah, you say, this satisfies my desiderata for a proof, so I you buy lots of disks, one of which fails in the first week.

Reducing inference to a calculation, or a computation that a machine could check is appealing and would certainly provide the objectivity that the first criterion lacks. Yet even if we could do such a thing in theory, the previous two criteria are perhaps all we can have in actual practice.

For example, for years it was conjectured that 4 colors are always sufficient to color a map such that no two countries that share a common border have the same color. Finally, in 1976 Appel and Haken announced that they had a proof of this conjecture. Their proof was hundreds of pages, and included a strange lemma. The lemma asserted that no case in a set numbering in the billions contained a certain kind of counterexample. The rest of the proof was showing that if this lemma were true then there was no counterexample to the theorem. The lemma, however, was established by an enormous computer search that took several days of supercomputer time. Many mathematicians were aghast and some still are. How do we know the computer search was done correctly? How can we be sure that the program was bug free? How many programs (that aren't completely trivial) have you seen or heard about that are bug free? I haven't seen any, and Tony Rippey's announcement that Tex is in fact such a program (with a $100,000 reward to those who find otherwise), is the first such thing I have heard about. So in practically deciding upon whether this proof is valid, we must resort to trusting the reliability of a type of procedure that in general we have little reason to trust and great experience arguing against trusting.

In the 1700s the French mathematician Fermat posed a number theoretic quandry that he claimed to have a "simple" proof of, but that he did not write down. The problem has resisted the attempts of the best mathematical minds of almost any generation to prove or disprove, until a few years ago. Henry Wiles of Princeton announced, a few years back, that he had a proof of Fermat's Last Theorem. Unfortunately, again the proof is hundreds of turgid pages, and in this case much of it can only be understood by a handful of mathematicians. If Wiles were to transcribe the proof into a formal language that a machine could check, it would turn the proof into thousands of pages. Who would ever trust that the transcription process was done without error? The point is again that even were the ideal of machine checkable proofs realized, the practice of proof checking would still be fallible. But there is a difference between a concept being objectively checkable in theory but not in practice, and one that is not even objectively checkable in theory.

2. Theories of Proof

We want a theory that separates proofs, or arguments, into those that are deductively valid and those that are not to have three properties:

1) Expressive Power (Completeness)

2) Soundness (Consistency)

3) Objectivity (Machine checkability)

Aristotle developed a theory of logic in about 400 B.C., and it was the dominant theory for over 2,000 years. In Aristotle's theory, the world is like language, and in language, sentences have a subject and a predicate. For example, "Humans are mortal." is a sentence in which Humans are the subjects and mortal the predicate. There are also quantifiers, e.g., "All" "Some" "Not all" and "None." His logic involved arguments of the following form:

Quantifier1 A are B

Quantifier2 B are C

Quantifier3 A are C

For example,

All humans are living things

All living things are mortal

All humans are mortal.

By varying the quantifiers and order of the A, B, and C, there were many possible figures to a syllogism. Aristotle offered 14 such forms as valid.

Looking at the the first proposition of Euclid's elements, which is on page 13 of Glymour's chapter, you can see that Aristotle's theory is not expressively powerful enough. It cannot even cover the mathematics known at the time, namely Euclidean geometry.

The proposition in Euclid is:

Proposition 1: For every straight line segment, there exists an equilateral triangle having that line segment as one side.

To put this into Aristotelian form, one would have to write it as:

All straight line segments are things for which there exists an equilateral triangle having that line segment as one side.

where the boldface is the subject and italics the predicate. So to prove this with an Aristotelian syllogism, we would have to find a B such that we could justify the two premises in the argument below:

All straight line segments are B

All B are things for which there exists an equilateral triangle having that line segment as one side.

This is not at all how Euclid's proof goes. In fact the problem, which was not solved until the middle of the 19th century by Gottlob Frege, was that the only predicates Aristotle would allow were ones that dealt with a single subject. Consider the following examples:

A mouse is smaller than a tiger.

A tiger is smaller than an elephant.

------------------------------------------- therefore,

A mouse is smaller than an elephant

In Aristotelian form, where the subject is in bold and the predicate in italics, these would be:

A mouse is smaller than a tiger.

A tiger is smaller than an elephant.

------------------------------------------- therefore,

A mouse is smaller than an elephant

The problem is that the predicates: "smaller than a tiger" and "smaller than an elephant" are completely different, and in general, arguments of the following form are not valid:

All S1 are A

All S2 are B

---------------, therefore

All S1 are B

The argument is valid, however, but it doesn't appear to be so in Aristotle's logic because the connection between the sentences is hidden. A more natural way to conceive of these claims is to make smaller than the predicate, which takes two subjects in order, as below.

Predicates with one subject are said to be monadic predicates, or predicates of arity 1. Predicates with two subjects are said to binary relations, or predicates with arity 2. An example of a predicate with arity 3, or a ternary relation, is betweeness, e.g.,

Pittsbugh is inbetween New York and Chicago.


Back to Lecture Notes Index