Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 5.3.1

As in Boolean logic, we will say that an inference rule is sound if, whenever it is applied to a set P of statements (premises), any conclusion that it produces is entailed by P (i.e., it must be true whenever P is). Clearly we are willing to accept only rules that are sound (and all of ours are). We haven’t worked this hard to set up a system that lets us prove claims that aren’t true. Of course, we could make that happen by having very weak rules. Why go out on any limbs?

But that won’t do. We need something else as well. We’ll say that a set of inference rules R is complete if (and only if), given any set P of premises (axioms), all statements that are entailed by P can be proved by applying the rules in R. In other words, if some statement S has to be true whenever all the premises in P are true, then it must be possible, using the rules in R, to prove it. We want a set of rules powerful enough to let us prove every theorem that follows from our premises.

In fact, what we’d hope for is all three of the following things (assume that P is a set of premises, S is a statement, and R is a set of inference rules):

1. A guarantee that, if S is a theorem, given premises P, then we have the tools we need to prove it. In other words, we have a complete set R of inference rules. And, of course, R can’t “overprove”: every rule in R must be sound.

2. A guarantee that, if S is actually true in some world that we’re trying to describe, then we can come up with a set P of premises such that S is a theorem given P. In other words, all true things are theorems. Also, of course, all false things aren’t theorems.

3. An effective procedure (think computer program or algorithm) that can look at S and be guaranteed to answer correctly the question, “Is S a theorem given P?”

Okay, good news first:

• We have (1). We can’t just use truth tables, the way we did in Boolean logic. But there are rule sets that work. This was proved by the Austrian/American mathematician Kurt Gödel in 1929. (So this isn’t obvious; for example it wasn’t something that the ancient Greeks knew.) This result is called Gödel’s Completeness Theorem.

And now for the bad news:

• We don’t have (2). Kurt Gödel (the very man who proved the completeness result that we just mentioned), went on to prove aa pair of Incompleteness Theorems that tell us that there are interesting systems (think arithmetic) that have the property that there’s no set of axioms that will make all true statements theorems while at the same time avoiding inconsistencies.

Visit "http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems¹ for more on this fundamental theorem that shook the mathematical world in 1931.

• We don’t have (3) either. We know (from the Completeness Theorem) that, if S is a theorem, there’s a way to find a proof of it. But what if it isn’t? Can we assert that we tried really hard to find a proof but we failed? Does that mean that S isn’t a theorem? No it doesn’t. In some cases (in other words, given some sets of axioms) it’s possible to do this. But in some other cases, it isn’t. This claim, that there’s no effective procedure for deciding whether S is a theorem is called the undecidability of predicate logic. This claim was proved in another fundamental, ground-shaking theorem in 1936, this time by the British mathematician Alan Turing. And, by the way, Turing’s proof of this particular undecidability result laid the groundwork for a much broader set of undecidability proofs. There’s a whole class of problems that will not ever be able to be solved by any sort of computer. Speed doesn’t matter. Memory size doesn’t matter. The existence of a solution to any one of these problems creates a logical contradiction.

Big Idea

There are provable limits to what predicate logic can do for us. And there are provable limits to what we can compute. Sometimes, in trying to solve real problems, those limits bite us. Nevertheless, the logical system that we’ve just defined can serve us well when we understand it.

Nifty Aside

Alan Turing is a hero to computer scientists. He worked on the earliest computers. He developed a machine that cracked German U-boat codes during the World War II. He proved key theoretical results (like the one we just mentioned). He wrote one of the first computer chess programs. And he had a sad death when he was way too young. Visit http://www.turing.org.uk/ for more on him and his work. Also, search YouTube for videos about him.

One last thing: Do not be confused by the fact that there exists both a Completeness Theorem and an Incompleteness Theorem. The terminology is unfortunate since it is based on two different notions of completeness. The Completeness Theorem tells us that there exist rule sets that are complete (in the sense we defined at the top of this page). The Incompleteness Theorem tells us that we may always be stuck with a theorem set that is incomplete in the sense that it doesn’t completely cover the set of true statements.