80-110: The Nature of Mathematical Reasoning

Spring 1998

Class 18: 3/17

 

1. Formal Methods of Proof

In the preceding classes we developed methods for determining whether arguments are valid that depend on possible worlds, truth tables, etc. Call this method the "semantic method," which consists rougly of three steps.

Semantic Method

1) Extract all the atomic sentences from the premises and conclusion.

2) Construct the truth table for the argument

3) If there is a row in which the premises are true and the conclusion false, then output "Invalid," otherwise output "Valid."

The semantic method has at least two virtues. First, the semantic method is completely objective. A truth table is machine constructible and machine evaluable. Two, for any argument expressible in the fragment of FOL we have presented so far (atomic sentences and sentential connectives), we can always construct a finite truth table for the argument, and always come up with a definite answer. Mathematicians, however, never give a truth table as a proof that their arguments are valid. Why not? The answer has at least two parts. The first is that the fragment of FOL that we are looking at is still too weak to express most mathematical claims, because it doesn’t have quantifiers or variables. When we move to the full FOL, truth tables will not generalize. Second, they are bulky and enormously wasteful in all but the simplest of arguments.

Suppose you gave me an argument with 5 premises, and altogether there were 10 atomic sentences in the premises and the conclusion. Then the truth table would have 210 rows, which is over 1,000. This would take far too long to build and work with. Plus, the number of rows goes up exponentiall as the number of atomic sentences, so things get hopelessly large very fast.

Mathematicians argue very differently, but still very systematically. Instead of using the semantic method, they use patterns of inference which they have already justified with the semantic method. For example, suppose I proved the following argument was valid with a truth table:

P -> Q

P

---------

Q

Suppose someone came along and asked me if this argument was valid:

P -> R

P

-------

R

Sure, you would say, I already checked it, except I used Q where you have R. What is someone else came along with the argument:

(A v E) -> ((B & C) & ((D v ~F) v (H & J))

(A v E)

---------------------------------------

((B & C) & ((D v ~F) v (H & J))

The truth table has 28 = 256 rows, so you don’t want to construct it. Ah, you say, it has the same pattern as the two arguments above, so it must be valid. You are right, and in fact mathematicians know that any argument of the form:

A -> B

A

---------

B

where A and B stand for any sentence, no matter how complicated or simple, is valid. The Romans recognized that inferences of this sort are valid, and called them inferences of the pattern "modus ponens."

So a whole other method for checking to see if arguments are valid involves ensuring that the steps in the argument follow patters of inference we know are valid. So know the trick is to come up with enough patterns of inference so that we can check any argument that someone using truth tables can check.

The basic set of inference rules we need give a way to use all the different sort of sentences we might see, and a way to construct them. Here is the table of inference rules for the formal proof system of natural deduction we will call ND.

The Proof System ND

The inference rules characterize patterns of argumentation. The part above the line represents patterns for the premises, and the conclusion is below the line. The rules in which the premises are boxed (conditional proof, and the two reductio rules) are a little different. The boxes represent a subproof from the top line, which say is the assumption, to the other lines in the box. Each inference rule has a name.

Conditional Proofs

Some of the inference rules have boxes around the premise or premises. The boxes represent subproofs, which are a formal representation of conditional reasoning. Focus on conditional proof, or ® Intro. The conclusion is a conditional, which says: if A, then B. To prove such a conditional sentence, we need not prove A is true, or B is true. We need only prove that B cannot be false if A is true. A subproof represents a hypothetical world in which we assume A and, if under this assumption we can prove B, then we can infer the conditional with no assumption. The box is drawn so we are not tempted to infer that statements inside the box are true outside the box. The situation with boxes is analagous to laws.

The outer box corresponds to U.S. Law. So statement Z might hold anywhere in the U.S. (e.g., it is illegal to discriminate on the basis of race). Statement X might be true in Ohio, but not in PA, and statement Y in PA but not in Ohio. The conditional: PA -> Y, which might be read, if PA law applies, then statement Y is true, is true in the U.S., because it is a conditional statement. To prove it, we imagine we are in PA, and derive Y.

The situation for the reductio rules is similar. In ~Elim, for example, we are not saying that ~A is true, we are assuming it hypothetically inside a box, or subproof, and if we can prove a contradiction from this statement, we are allowed to infer ~A must be false, i.e., A is true. The examples early on in the class, that the square root of 2 is irrational and that there are an infinite number of primes followed just this pattern. In the primes case, we assumed that the primes were finite, and then derived a contradiction. In the square root of 2 case, we assumed that it was rational, and then derived a contradiction:


Back to Lecture Notes Index