Forever Undecided
Page 12
5. The solution to this problem is somewhat simpler than the solution to Problem 4.
Step 1: Since the native said what he did, then by Lemma 3 of the last chapter, the reasoner will believe k⊃BD. Hence he will believe k⊃(k&BD). Since he also believes the Sage’s statement (k&BD)⊃D, then he will believe k⊃D. Since the native said that he will believe k⊃D, then the reasoner will believe that the native is a knight—he will believe k. And since he will believe k⊃D, then he will believe D.
Step 2: Since the reasoner will believe k⊃D, then the native is really a knight. Hence k is true and also BD is true (as we have shown). Hence k&BD is true, and since (k&BD)⊃D is true, then D is true. So again the diamond is on the island.
Now we know that the chances are 80 percent that the diamond is on the island, since it is on the island in four out of five equally probable versions. This probability should be high enough to interest the enterprising reader who wishes to search for it.
Discussion. The essential mathematical content of Problem 4 is that for any propositions k and p, if a reasoner of type 4 believes k≡(Bk⊃Bp) and believes (k&Bp)⊃p, then he will believe p. This is a strengthening of Theorem 2 of the last chapter, because if a reasoner of type 4 believes Bp⊃p, he will certainly believe (k&Bp)⊃p, and so the present hypothesis is weaker than that of Theorem 2, Chapter 15 (and we have derived the same conclusion from a weaker assumption).
Likewise, the essential mathematical content of Problem 5 is that if a reasoner of type 4 believes k≡B(k⊃p) and (k&Bp)⊃p, then he will believe p. This is stronger than Theorem 3 of the last chapter for the same reasons.
Curiously enough, Theorem 1 of the last chapter does not appear to have an analogous strengthening. If a reasoner of type 4 believes k≡(Bk⊃p) and (k&Bp)⊃p, there does not seem to be any reason to conclude that he will believe p.
• 17 •
Löb’s Island
SOMEWHERE IN the vast reaches of the ocean there is a particularly interesting knight-knave island which I shall refer to as Löb’s Island. Given any person who visits the island, and given any proposition p, there is at least one native of the island who says to the visitor: “If you ever believe that I am a knight, then p is true.”
In the problems of this chapter, a reasoner of type 4 visits the island. It is given that the rules of the island hold (knights tell the truth, knaves lie, and every native is a knight or a knave) and that the reasoner believes the rules of the island.
HENKIN’S PROBLEM
Suppose a native of Löb’s Island says to the reasoner: “You will believe that I am a knight.” On the surface it seems that there is no way to tell whether the native is a knight or a knave; it would appear that maybe the reasoner will believe that the native is a knight (in which case the native made a true statement, and therefore is a knight), or that maybe the reasoner will never believe that the native is a knight (in which case the native made a false statement and is accordingly a knave). Is there any way to decide between these two alternatives?
This problem derives from a famous problem posed by Leon Henkin and answered by M. H. Löb. The surprising thing is that it is possible to decide whether the native is a knight or a knave.
1
Under the conditions given above, is the native a knight or a knave? (Solutions are given following Problem 3.)
2
Suppose a native of Löb’s Island says to a reasoner of type 4: “You will never believe that I am a knave.” Assuming the rules of the island hold (and that the reasoner believes them), is the native a knight or a knave?
3
If a reasoner of type 4 visits Löb’s Island (and believes the rules of the island), is it possible for him to be consistent and to believe that he is consistent?
SOLUTIONS TO PROBLEMS 1, 2, AND 3
1. The solution is a bit tricky. Let P1 be the native who said: “You will believe I’m a knight.” Let k1 be the proposition that P1 is a knight. Since the reasoner believes the rules of the island and P1 said what he did, then the reasoner will believe the proposition k1 ≡BK1. From just this fact, it is not possible to determine whether k1 is true or false; but this island is Löb’s Island, hence there is a native P2 who will say to the reasoner: “If you ever believe I’m a knight, then P1 is a knight.” (Remember that for any proposition p, there is some native who says to the reasoner: “If you ever believe I’m a knight, then p.”) Let k2 be the proposition that P2 is a knight. Since P2 asserted the proposition Bk2⊃k1, then the reasoner will believe the proposition k2≡(Bk2⊃k1). He also believes Bk1≡k1, hence he believes Bk1k1, and so he believes Bk1k1 and k2≡(Bk2⊃k1). Then by Theorem 1, Chapter 15, this page (reading “k2” for “k” and “k1” for “C”), he will believe k1. Since P1 said that the reasoner would believe k1, then P1 is a knight. And so P1 is a knight and the reasoner will believe that P1 is a knight.
Note: We might remark that even without the assumption that the rules of the island really hold, we can still conclude that the reasoner will believe that P1 is a knight.
2. To avoid repetition of similar arguments, let us now note once and for all that if a reasoner of type 4 visits Löb’s Island, then for any proposition p, if he believes the proposition Bp⊃p, he will believe p. (Reason: Since this island is Löb’s Island, some native will say to him: “If you ever believe that I’m a knight, then p.” Hence the reasoner will believe k≡(Bk⊃p), where k is the proposition that the native is a knight. Then, since he believes Bp⊃p, he will believe p, by Theorem 1, Chapter 15.)
Now for the problem at hand: The native has told the reasoner, “You will never believe I’m a knave.” Then the reasoner believes k≡~B~k (k is the proposition that the native is a knight). Hence he will believe the logically equivalent proposition ~k≡B~k, hence he will believe B~k⊃~k. Therefore he will believe Bp⊃p, when p is the proposition ~k. Then, by the remarks of the last paragraph, he will believe p—i.e., he will believe ~k. And so the reasoner will believe that the native is a knave. Since the native said that the reasoner wouldn’t believe that the native is a knave, then the native in fact is a knave.
3. Suppose a reasoner of type 4 visits Löb’s Island. Then for any proposition p, there is some native who will say to him: “If you ever believe I’m a knight, then p.” In particular, this is true if we take for p the proposition ⊥ (which, we recall, stands for logical falsehood). So there is a native who says to the reasoner: “If you ever believe I’m a knight, then ⊥.” Thus the reasoner believes the proposition k≡(Bk⊃⊥). Now, Bk⊃⊥ is logically equivalent to ~Bk, hence k≡(Bk⊃⊥) is logically equivalent to k≡~Bk, hence the reasoner believes k≡~Bk. Then, according to Theorem 1, Chapter 12, this page, he cannot believe in his own consistency without becoming inconsistent.
REFLEXIVITY
Reflexive Reasoners. We shall say that a reasoner is reflexive if for every proposition q, there is at least one proposition p such that the reasoner will believe p≡(Bp⊃q).
Any reasoner who visits Löb’s Island (and believes the rules of the island) will automatically become a reflexive reasoner, since for any proposition q, there is at least one native who will say: “If you ever believe I’m a knight, then q is true,” and so the reasoner will believe k≡(Bk⊃q), where k is the proposition that the native is a knight. However, a reasoner who has never visited Löb’s Island might be a reflexive reasoner for completely different reasons (some of which we will consider in Chapter 25).
Let us note that if a reflexive reasoner of type 4 visits an ordinary knight-knave island (it doesn’t have to be Löb’s Island) and meets a native who says to him, “You will believe that I’m a knight,” then the reasoner will believe that the native is a knight. (He doesn’t need a second native to tell him, “If I’m a knight, then so is the first native.”) Also, if a reflexive reasoner of type 4 goes to an ordinary knight-knave island and is told by a native, “You will never believe I’m a knave,” the reasoner will believe that the native is a knave (as in Problem 2).
And, one more thing: Suppose a reflexive reasoner of type 4 is thinking of visiting the knight-knave island with the sulfur baths and mineral waters, and his family doctor, whom he trusts, tells him: “If you believe that the cure will work, then it will.” Then without further ado, the reasoner will believe that the cure will work (he doesn’t have to go first to the island and meet a native who tells him, “If you believe I’m a knight, then the cure will work”).
All these facts are special cases of the following theorem (which springs from Theorem 1 of Chapter 15).
Theorem A (After Löb). For any proposition q, if a reflexive reasoner of type 4 believes Bq⊃q, he will believe q.
Reflexive Systems. Let us now consider the type of mathematical systems described in Chapter 13. We recall that for any system S, for any proposition p expressible in the system, the proposition Bp (p is provable in S) is also expressible in the system. (Remember that for systems, “B” means “provable.”) When we have only one system S under discussion, the word “proposition” shall be understood to mean “proposition expressible in S.”
We now define S to be reflexive if for every proposition q (expressible in S), there is at least one proposition p (expressible in S) such that the proposition p≡(Bp⊃q) is provable in S. Theorem A above obviously holds for systems as well as reasoners: Given any reflexive system S and any expressible proposition q, if Bq⊃q is provable in S, so is q. This is Löb’s Theorem.
We shall call S a Löbian system if for every proposition p, if Bp⊃p is provable in the system, so is p. We have now established Löb’s Theorem.
Theorem L (Löb’s Theorem). Every reflexive system of type 4 is Löbian—i.e., for any reflexive system S of type 4, if Bp⊃p is provable in S, so is p.
Corollary. For any reflexive system of type 4, if p≡Bp is provable in the system, so is p.
Discussion. Gödel proved his incompleteness theorems for several systems, including the system of Arithmetic, which we have briefly mentioned. These systems are all reflexive systems of type 4, and this is what enabled Gödel’s arguments to go through. Gödel constructed a sentence g that asserted its own nonprovability in the system (the sentence g≡~Bg is provable in the system).
Later the logician Leon Henkin constructed a sentence h such that h≡Bh is provable in the system, and raised the problem whether there was any way to tell whether h was provable in the system or not. Such a sentence h can be thought of as asserting: “I am provable in the system.” (It resembles a native who says: “You will believe that I’m a knight.”) On the surface, it would appear equally possible that h is true and provable in the system, or false and not provable in the system. The problem remained open for several years, and was finally solved by Löb. We have the answer in the corollary above: If the system is reflexive and of type 4, then Henkin’s sentence h is provable in the system.
Reflexive and Gödelian Systems. We recall that a system is called Gödelian if there is some proposition p such that p≡~Bp is provable in the system.
4
Every reflexive system of type 1 is also Gödelian. Why is this? (Solutions are given following Problem 5.)
Strong Reflexivity. We will say that a system S is strongly reflexive if for every proposition q, there is a proposition p such that p≡B(p⊃q) is provable in S.
The connections between reflexivity and strong reflexivity are given in the following theorem.
Theorem R (Reflexivity Theorem). It consists of two parts:
(a) Any strongly reflexive system of type 1 is reflexive.
(b) Any reflexive system of type 1* is strongly reflexive.
5
Prove Theorem R.
SOLUTIONS TO PROBLEMS 4 AND 5
4. Suppose S is reflexive and of type 1. Then for any proposition q, there is some p such that p≡(Bp⊃q) is provable in S. We take for q the proposition ⊥ and so there is some p such that p≡(Bp⊃⊥) is provable in S. But Bp⊃⊥ is logically equivalent to ~Bp, hence p≡(Bp⊃⊥) is logically equivalent to p≡~Bp, and so p≡~Bp is provable in S, and therefore S is Gödelian. (Actually, since we are basing propositional logic on ⊃ and ⊥, the proposition ~Bp is the proposition Bp⊃⊥, and so we really didn’t even have to assume that S is of type 1.)
5. Suppose S is of type 1. Let q be any proposition.
(a) Suppose S is strongly reflexive. Then there is a proposition p such that p≡B(p⊃q) is provable in S. Since S is of type 1, it follows that (p⊃q)≡(B(p⊃q)⊃q) is provable in S. (For any propositions X, Y, and Z, the proposition (X⊃Z)≡(Y⊃Z) is a logical consequence of X≡Y. Taking p for X, B(p⊃q) for Y, and q for Z, the proposition (p⊃q)≡(B(p⊃q)⊃q) is a logical consequence of p≡B(p⊃q).) Therefore there is a proposition p′—namely, p⊃q—such that p′≡(Bp′⊃q) is provable in S. Hence S is reflexive.
(b) Suppose also that S is regular (and hence of type 1*) and that S is reflexive. Then there is a proposition p such that p≡(Bp⊃q) is provable in S. Since S is regular, it follows that Bp≡B(Bp⊃q) is provable, hence (Bp⊃q)≡(B(Bp⊃q)⊃q) is provable. We now take p′ to be the proposition Bp⊃q, and we see that p′≡(Bp′⊃q) is provable. Since there is a proposition p′ such that p′≡(Bp′⊃q) is provable in S, S is strongly reflexive.
Remarks. It of course follows from the above theorem and Löb’s Theorem that any strongly reflexive system of type 4 is Löbian. We proved this another way in Theorem 3, Chapter 15.
• Part VII •
IN DEEPER WATERS
• 18 •
Reasoners of Type G
MODEST REASONERS
We have called a reasoner conceited if for every proposition p, he believes Bp⊃p. Now, if a reasoner believes p, then there is nothing immodest about his believing Bp⊃p. (Indeed, if he believes p and is of type 1, he will also believe q⊃p for any proposition q whatsoever, since q⊃p is a logical consequence of p. In particular, he will believe Bp⊃p.)
We shall now call a reasoner modest if for every proposition p, he believes Bp⊃p only if he believes p (in other words, if he believes Bp⊃p, then he believes p). In analogy with systems, we might also call a modest reasoner a Löbian reasoner.
Löb’s Theorem states that every reflexive system of type 4 is Löbian. Stated in terms of reasoners, every reflexive reasoner of type 4 is modest.
Many results that can be proved for a given reasoner under the assumption that he is a reflexive reasoner of type 4 can be proved more swiftly from the assumption that he is a modest reasoner of type 4. For example, suppose a modest reasoner of type 4 (or even a modest reasoner of type 1) believes that he is consistent. Then he believes ~B⊥. Hence he believes the logically equivalent proposition B⊥⊃⊥. Then, being modest, he must believe ⊥, which means that he is inconsistent! And so no modest reasoner—even of type 1—can consistently believe in his own consistency. (This, of course, doesn’t mean that he necessarily is inconsistent; he might happen to be consistent, but if he is consistent—and a modest reasoner of type 1—then he cannot believe he is consistent.)
REASONERS OF TYPE G
Let us say that a reasoner is modest with respect to a given proposition p if it is the case that if he believes Bp⊃p, then he also believes p. A reasoner, then, is modest if he is modest with respect to every proposition p. We now say that a reasoner believes he is modest with respect to p if he believes the proposition B(Bp⊃p)⊃Bp—he believes that if he should ever believe that his belief in p implies p, then he will believe p. We now say that a reasoner believes he is modest if for every proposition p, he believes he is modest with respect to p—in other words, for every proposition p, he believes B(Bp⊃p)⊃Bp.
By a reasoner of type G is meant a reasoner of type 4 who believes he is modest (for every proposition p, he believes B(Bp⊃p)⊃Bp). By a system of type G is meant a system of type 4 such that for every proposition p, the proposition B(Bp⊃p)⊃Bp is provable in the system.
&nbs
p; A great deal of research has been going on in recent years about systems of type G. George Boolos has devoted an excellent book† to the subject, which we strongly recommend as a follow-up to this volume.
Several questions about reasoners of type G readily present themselves. If a reasoner of type G believes he is modest, is he necessarily modest? We will show shortly that the answer is yes; indeed, we will see that any reasoner of type 1* who believes he is modest must be modest. Now, what about a reasoner of type 4 who is modest. Does he necessarily believe he is modest? We will show that the answer is yes, and hence that any reasoner of type 4 is modest if and only if he believes he is modest—in other words if and only if he is of type G. Then we will show a surprising result discovered independently by the logicians Saul Kripke, D. H. J. de Jongh, and Giovanni Sambin—namely, that any reasoner of type 3 who believes he is modest must be of type 4 (and hence of type G).
Another question: We know that any reflexive reasoner of type 4 is modest (this is Löb’s Theorem). Is a modest reasoner of type 4 necessarily reflexive? That is, given a modest reasoner of type 4, is it necessarily true that for any proposition q, there is some proposition p such that he believes p≡(Bp⊃q)? It is not difficult to prove that the answer is yes; we will do this in the next chapter. And so by the end of the next chapter we will have proved that for any reasoner, the following four conditions are equivalent: