(c) Since he believes Bp⊃B⊥ (as we have just proved), then he also believes ~B⊥⊃~Bp. Now, suppose he believes ~B⊥ (he believes he cannot be inconsistent). Since he also believes ~B⊥⊃~Bp (as we have just seen), then he will believe ~Bp. Since he also believes p≡~Bp, he will believe p, hence he will be inconsistent by (a).
The Student and His Theology Professor. Let us now turn again to the student and his theology professor who says to him: “God exists if and only if you will never believe that God exists.” If the student believes the professor, then he believes the proposition g≡~Bg, where g is the proposition that God exists. Then, according to Theorem G, the student cannot believe in his own consistency without becoming inconsistent.
We hinted at this at the end of Chapter 2, but we were not then able to state what constituted a “reasonable” set of assumptions about the student’s reasoning abilities. Now we can do this. The assumptions are simply that the student is a reasoner of type 4.
Of course the student has the option of believing in his own consistency without becoming inconsistent; he can simply refuse to believe the professor!
Exercise 1. Suppose that in Theorem 1 we are given the additional information that the rules of the island really do hold. Is the native a knight or a knave?
Exercise 2. In the example of the student and his theology professor, suppose that the student does believe the professor and also believes in his own consistency. If God really exists, then was the professor’s statement true or false? If God doesn’t exist, then was the professor’s statement true or false?
Answer to Exercise 1. By Theorem 1, the reasoner will be inconsistent, hence will believe everything. In particular, he will believe that the native is a knight. Since the native said he wouldn’t, then the native’s statement was false. Therefore, if the rules of the island really hold, the native must be a knave.
Answer to Exercise 2. Again, the student will become inconsistent and believe everything. In particular, he will believe that God exists (he will also believe that God doesn’t exist, but this is not relevant here). Letting g be the proposition that God exists, the proposition Bg is thus true, hence ~Bg is false. If God does exist, then g is true, hence g≡~Bg is false, and the professor was wrong. If God doesn’t exist, then g is false, g≡~Bg is true, and the professor was right.
Exercise 3. We have proved in earlier chapters the following three facts:
(1) If a native says to a reasoner of type 1*, “You will never believe I’m a knight,” and the reasoner believes he will never be peculiar, then he will become peculiar. (Theorem 3, Chapter 10, this page.)
(2) A peculiar reasoner of type 3 is inconsistent. (Problem 8, Chapter 11, this page.)
(3) A reasoner of type 4 believes that if he should become peculiar, he will be inconsistent. (Exercise 1, Chapter 11, this page.)
Using these three facts, one can give a much swifter proof of Theorem 1 of this chapter (this page) than the one we have given. How?
Answer to Exercise 3. Suppose the native makes this statement—“You will never believe that I am a knight”—to a reasoner of type 4 and the reasoner believes that he will never be inconsistent. Then the reasoner will believe that he cannot be peculiar (because he knows that if he is peculiar, he will be inconsistent). Then by Fact 1 above, he will become peculiar. And by Fact 2 above, he will become inconsistent.
THE DUAL OF THEOREM G
Exercise 4. Suppose that the native, instead of saying, “You will never believe I’m a knight,” says, “You will believe I’m a knave.” Assuming the reasoner is of type 4 and believes in his own consistency, does it now follow that he will become inconsistent?
Solution. The answer is yes, and this can be easily established as a corollary of Theorem G, but first I’d like to sketch a direct argument. The reasoner reasons: “Suppose he’s a knight. Then what he said is true, which means that I’ll believe he is a knave. Once I believe he’s a knave, I’ll believe the opposite of what he said—I’ll believe that I don’t believe he’s a knave. But if I believe he’s a knave, I’ll also believe that I do believe he’s a knave (because I’m normal), and hence I’ll be inconsistent. Since I will never be inconsistent, he can’t be a knight after all; he must be a knave. Now I believe he’s a knave. He said I would, and so he’s a knight.”
At this point the reasoner is inconsistent.
What we have just proved is a special case of the following “dual” of Theorem G.
Theorem G°. If a consistent reasoner of type 4 believes some proposition of the form p≡B~p, then he can never know that he is consistent.
2
Theorem G° can be proved by “dualizing” the argument for Theorem G, but it can be obtained much more simply as a corollary of Theorem G. How?
Solution. Suppose the reasoner believes p≡B~p. Then he will believe ~p≡~B~p. Let q be the proposition ~p. Then the reasoner believes q≡~Bq, and so the reasoner does believe a proposition of the form p≡~Bp (namely, q≡~Bq), and so the result follows by Theorem G.
Exercise 5. Suppose that in Exercise 4 we add the assumption that the rules of the island really hold and that the reasoner does believe in his own consistency. Is the native a knight or a knave?
Exercise 6. Suppose a theology professor says to his student of type 4: “God exists if and only if you will believe that God doesn’t exist.” Suppose the student believes the professor and also believes in his own consistency. Prove that if the professor’s statement is true, then God must exist. Prove that if the professor’s statement is false, then God doesn’t exist.
Exercise 7. Suppose a native tells a reasoner of type 4: “You will never believe I’m a knight” (or, alternatively, says: “You will believe I’m a knave”). Prove that the reasoner knows that if he should ever believe in his own consistency, he will become inconsistent. (The solution of this will follow easily from results to be proved in later chapters.)
• 13 •
Gödelian Systems
ALL THE results we have so far proved about reasoners and their beliefs are counterparts of metamathematical results about mathematical systems and the propositions provable in them. Before turning to these, let us summarize the most significant facts we have proved in the last few chapters.
Summary I. Suppose a reasoner believes the rules of the island and a native says to him: “You will never believe that I am a knight.” Or, more generally, suppose a reasoner believes some proposition of the form p≡~Bp (p is true if and only if I will never believe p). Then:
(1) For a reasoner of type 1, if he believes that he is always accurate, then he will become inaccurate; in fact, he will become peculiar.
(2) For a reasoner of type 1*, if he believes that he will never be peculiar, then he will become peculiar.
(3) For a reasoner of type 3, if he believes that he will never be peculiar, then he will become inconsistent.
(4) For a reasoner of type 4, if he believes that he will always be consistent, then he will become inconsistent.
All these facts, particularly (4), are related to important metamathematical facts, which we will discuss briefly.
The types of systems investigated by Kurt Gödel have the following features. First, there is a well-defined set of propositions expressible in the system; these will be called the propositions of the system. One of these propositions is ⊥ (logical falsehood), and for any proposition p and q of the system, the proposition (p⊃q) is also a proposition of the system. The logical connectives &, v, ~, ≡ can all be defined from ⊃ and ⊥ in the manner explained in Chapter 7.
Second, the system—call it “S”—has various axioms and logical rules making certain propositions provable in the system. We thus have a well-defined subset of the set of propositions of the system—namely, the set of provable propositions of the system.
Third, for any proposition p of the system, the proposition that p is provable in the system is itself a proposition of the system (it may be true or false, and it may be provable in th
e system, or then again it may not). We let Bp be the proposition that p is provable in the system. (The symbol “B” for “provable” was introduced by Gödel; it stands for the German word beweisbar.) By a fortunate coincidence, we have the symbol “B” used in two closely related situations. When we speak of reasoners, Bp means that the reasoner believes p; when we speak of mathematical systems, Bp means that p is provable in the system.
We now define a system S to be of type 1, 1*, 2, 3, 4, in exactly the same way as we did for reasoners: If all tautologies are provable in S, and if for any propositions p and p⊃q both provable in S, q is also provable in S—if these two conditions hold—then we say that S is of type 1. If also Bp⊃Bq is provable in S whenever p⊃q is provable in S, then we say that S is of type 1*. If also all propositions of the form (Bp&B(p⊃q))⊃Bq are provable in S, then we say that S is of type 2. If also S is normal (i.e., Bp is provable whenever p is), then we say that S is of type 3. Lastly, if all propositions of the form Bp⊃BBp are provable in S, then we say that S is of type 4. Of course, all the results of Chapter 11 that we proved for reasoners hold good also for systems (where we now reinterpret “B” to mean provable rather than believed). As for the results of Chapters 10 and 12, we need another condition to which we now turn.
Gödelian Systems. Gödel made the remarkable discovery that each of the systems which he investigated had the property that there was a proposition p such that the proposition p≡~Bp was provable in the system. Such systems we will call Gödelian systems.
The proposition p≡~Bp is a very curious one. Here we have a proposition p equivalent to its own nonprovability in the system! The proposition p can be thought of as saying, “I am not provable in the system.” How Gödel managed to find such a proposition need not concern us now, although it will be taken up in a much later chapter.
In analogy to systems, we might define a reasoner to be a Gödelian reasoner if there is at least one proposition p such that he believes the proposition p≡~Bp. Of course we have been studying Gödelian reasoners throughout the last chapter. (If a reasoner comes to the Island of Knights and Knaves and believes the rules of the island, and if a native says to him, “You will never believe that I am a knight,” then the reasoner believes the proposition k≡~Bk, hence he becomes a Gödelian reasoner.)
Let us now say that a system can prove its own accuracy if it can prove all propositions of the form Bp⊃p. We will say that it can prove its own nonpeculiarity if it can prove all propositions of the form ~(Bp&B~Bp). We will say that the system can prove its own consistency if it can prove the proposition ~B⊥.
Let us now restate our opening summary in terms of systems, rather than reasoners.
Summary I*. (1) If a Gödelian system of type 1 can prove its own accuracy, then it is inaccurate—in fact, peculiar.
(2) If a Gödelian system of type 1* can prove its own non-peculiarity, then it is peculiar.
(3) If a Gödelian system of type 3 can prove its own non-peculiarity, then it is inconsistent.
(4) If a Gödelian system of type 4 can prove its own consistency, then it is inconsistent.
Item (4) above is the really important one; it is a generalized form of Gödel’s famous Second Incompleteness Theorem.
Discussion. In Gödel’s original 1931 paper, he took a particular system (the system of Principia Mathematica of Whitehead and Russell) and showed that the system, if consistent, couldn’t prove its own consistency. He stated that his method applied not only to this particular system, but to a wide variety of systems. Indeed, the method applies to all Gödelian systems of type 4, as we have just seen.
Another important Gödelian system of type 4 is the system known as “Arithmetic” (more completely, “First-Order Peano Arithmetic”). This is formalization of the theory of the ordinary whole numbers 0, 1, 2,…Since Arithmetic is a Gödelian system of type 4, it is subject to Gödel’s Consistency Theorem; hence if Arithmetic is consistent (which it is, since only true propositions are provable in it), then it cannot prove its own consistency.
When the mathematician André Weil heard about this, he made the famous quip, “God exists, since Arithmetic is consistent; the Devil exists, since we cannot prove it.”
This quip, though delightful, is actually misleading. It’s not that we can’t prove the consistency of Arithmetic; it is that Arithmetic can’t prove the consistency of Arithmetic! We certainly can prove the consistency of Arithmetic, but our proof cannot be formalized in Arithmetic itself.
Indeed, there has been a good deal of popular misunderstanding concerning Gödel’s Second Theorem (the Consistency Theorem); this has been partly due to the irresponsibility of some science reporters and other popularizers. (I, of course, am certainly all for popularization, providing the popularization is not inaccurate.) One particular popularizer wrote: “Gödel’s theorem means that we can never know that Arithmetic is consistent.” This is sheer nonsense. To see how silly it is, suppose it had turned out that Arithmetic could prove its own consistency—or, to be more realistic, suppose we take some other system that can prove its own consistency. Would this be any guarantee of the consistency of the system? Of course not. If the system were inconsistent, then, being of type 1, it could prove anything, including its own consistency! To trust the consistency of a system on the grounds that it can prove its own consistency would be as foolish as to trust the veracity of a person on the grounds that he claims to be always truthful. No, the fact that Arithmetic can’t prove its own consistency doesn’t cast the faintest ray of doubt on the consistency of Arithmetic.
As a matter of fact, in this book we will construct several Gödelian systems of type 4, and we will prove their consistency beyond a shadow of a doubt. Then, we will show that by virtue of their very consistency, the systems will be unable to prove their own consistency.
Exercise. Consider a system S of type 4 (but not necessarily Gödelian). Recall that for any proposition p, the proposition Bp is true if and only if p is provable in S.
(a) First show that for any proposition p, the proposition (B(p≡~Bp)&B~B⊥)⊃B⊥ is true (for the system S). This is quite easy.
(b) Then show that (B(p≡~Bp)&B~B⊥)⊃B⊥ is actually provable in S. (Not so easy!)
• 14 •
More Consistency Predicaments
SOME PRELIMINARY PROBLEMS
1
Suppose a reasoner believes that he is inconsistent. Is he necessarily inconsistent? Is he necessarily inaccurate?
2
Suppose a reasoner believes that he is inaccurate. Prove that he is right!
3
Suppose a reasoner of type 1* believes that he cannot be inconsistent (he believes ~B⊥). Will he necessarily believe that he will never believe that he is inconsistent? (I.e., will he necessarily believe ~BB⊥?)
SOME MORE CONSISTENCY PREDICAMENTS
We are back to the Island of Knights and Knaves. We continue to assume that the reasoner is of type 4 and that he believes the rules of the island.
4
Suppose a native says to the reasoner, “If I am a knight, then you will believe that I’m a knave.” Prove:
(a) The reasoner will sooner or later believe himself inconsistent.
(b) If the rules of the island really hold, then the reasoner will become inconsistent!
Note: In the problems of this chapter, we are not assuming that the reasoner believes that he is consistent.
5
Suppose the native says instead, “If I am a knight, then you will never believe that I am one.” Prove:
(a) The reasoner will become inconsistent.
(b) The rules of the island don’t really hold.
Note 1: This problem holds good even if the reasoner is only of type 3.
Note 2: For a “student and his theology professor” version of the last two problems, see the discussion following the solution to Problem 5.
6
Here is a curious one. A reasoner of type 4 comes to what he believes is a knight-kn
ave island (he believes the rules of the island), and a native says to him the following two things:
(1) “You will believe that I am a knave.”
(2) “You will always be consistent.”
Prove that the reasoner will become inconsistent and that the rules of the island don’t hold.
7
This time a native makes the following two statements to a reasoner of type 4:
(1) “You will never believe I’m a knight.”
(2) “If you ever believe I’m a knight, then you will become inconsistent.”
Prove that the reasoner will become inconsistent and that the rules of the island don’t hold.
TIMID REASONERS
Let us say that a reasoner shouldn’t believe p if his believing p will lead him into an inconsistency. Let us say that a reasoner is afraid to believe p if he believes Bp⊃B⊥—i.e., if he believes that his believing p will lead him into an inconsistency. (In other words, he is afraid to believe p if he believes that he shouldn’t believe p.)
We know that any reasoner of type 4 who believes the rules of the island and is told by a native that he will never believe that he is a knight shouldn’t believe in his own consistency. In general, however, there is no reason why a reasoner of type 4 shouldn’t believe in his own consistency. But now arises a very curious thing: If for some reason, a reasoner of type 4 is afraid of believing in his own consistency, his very fear justifies it. By this I mean that any reasoner of type 4 who is afraid of believing in his own consistency, really shouldn’t believe in his own consistency. Put still another way, if a reasoner of type 4 believes that his believing in his own consistency will get him into an inconsistency, then it will!
Forever Undecided Page 9
