Forever Undecided

by Raymond M. Smullyan

  • 29 •

  Some Strange Reasoners!

  REASONERS WHO ARE ALMOST OF TYPE G

  We shall say that a reasoner is almost of type G if he believes all sentences believed by all reasoners of type G (or, what is the same thing, if he believes all sentences provable in the modal system ) and if his beliefs are closed under modus ponens. What possibly keeps him from being a reasoner of type G is that he may not be normal.

  As we will prove, a reasoner who is almost of type G, unlike a reasoner who is of type G, can believe that he is consistent without losing his consistency. But then he must suffer from another defect—he cannot be normal!

  We will now look more closely into this.

  1

  Given a consistent reasoner who is almost of type G and who believes he is consistent, find a proposition p such that the reasoner believes p, but can never know that he believes p!

  2

  Any abnormal reasoner must fail to believe at least one true proposition, because there is a proposition p such that he believes p but fails to believe Bp, yet Bp is true (since he believes p). Therefore he fails to believe the true proposition Bp.

  It then follows from the last problem that given any consistent reasoner who is almost of type G and believes he is consistent, there must be at least one true proposition that he fails to believe. More startling is the fact that there must be at least one false proposition that he does believe!

  What false proposition must he believe?

  Exercise 1. State whether the following is true or false: Every non-normal reasoner of type 1 is consistent.

  Exercise 2. State whether the following is true or false: Every non-normal reasoner of type 1 who believes all axioms of must believe at least one false proposition.

  REASONERS WHO ARE OF TYPE G*

  As we will see, a reasoner who is almost of type G can not only believe in his own consistency without necessarily being inconsistent; he can even believe in his own accuracy without necessarily being inconsistent.

  By a reasoner of type G* we shall mean a reasoner who is almost of type G and who believes all sentences of the form BX⊃X (he believes in his own accuracy). In other words, a reasoner of type G* is a reasoner of type 1 who believes all sentences provable in G and believes all sentences of the form BX⊃X.

  Such a reasoner must, of course, also believe the sentence B⊥⊃⊥, and since he is almost of type G, then what we have proved in the solution to Problems 1 and 2 also holds good for him. And so we have established Theorem 1.

  Theorem 1. For any consistent reasoner of type G*:

  (a) He believes that he is consistent, but can never know that he believes he is consistent!

  (b) He also believes the false proposition B~B⊥⊃BB~B⊥ (i.e., he wrongly believes: “If I ever believe that I am consistent, then I will believe that I believe that I am consistent.”)

  We remind the reader that the sentence B~B⊥⊃BB~B⊥ is false for a consistent reasoner of type G*, since B~B⊥ is true (he believes he is consistent), but BB~B⊥ is false (he doesn’t believe that he believes that he is consistent).

  It of course follows from Theorem 1 that any reasoner of type G* must have at least one false belief, because if he is consistent, then he does (by Theorem 1), and if he is inconsistent, he certainly does!

  Minimal Reasoners of Type G*. By the modal system G* is meant the system whose axioms are all the provable formulas of G together with all formulas of the form BX⊃X, and whose only inference rule is modus ponens. We shall let be the system G* whose axioms are restricted to sentences—that is, the axioms of are all sentences provable in , plus all sentences of the form BX⊃X. The only inference rule of is modus ponens. (We can easily show by an argument similar to the one used in Chapter 27 that the provable sentences of are the same as the provable sentences of G*.) By a minimal reasoner of type G* we shall mean a reasoner who believes those and only those sentences provable in . It is easy to show that all reasoners of type G* must believe all sentences provable in (“believe” here falls under the egocentric interpretation, of course). Therefore a reasoner is a minimal reasoner of type G* if and only if he believes those and only those sentences that are believed by all reasoners of type G*.

  Since every reasoner of type G* has at least one false belief, so does a minimal reasoner of type G*. It hence follows that there is at least one sentence provable in that is false for (false, when “B” is interpreted as provability in G*). And so we have Theorem 2.

  Theorem 2. The modal system is not self-referentially correct.

  In light of Theorem 2, the reader may well wonder how the modal system could be of any use. Well, just because there is a provable sentence of that is false for does not mean that there isn’t some other interpretation of “B” in which all provable sentences of are true. Is there such an interpretation? Yes, there is—and a very important one.

  Theorem 3. Every sentence provable in is true for the modal system .

  This means that every sentence provable in is true if “B” is interpreted as provability in , rather than in.

  3

  Why is Theorem 3 correct?

  Theorem 4 is an easy corollary of Theorem 3.

  Theorem 4. The system is consistent.

  4

  Why is Theorem 4 a corollary of Theorem 3?

  Theorem 4, of course, implies that any minimal reasoner of type G* is consistent. And so a minimal reasoner of type G* is consistent, he believes he is consistent, but can never believe that he believes he is consistent (by Theorem 2). Stated alternatively in terms of the modal system : it is consistent, it can prove its own consistency, but can never prove that it can prove its own consistency! Also, the modal system is not normal.

  The Completeness of for . We shall now state a further result whose proof unfortunately goes beyond the scope of this book.

  Given two modal systems M1 and M2, we have defined M1 to be correct for M2 if every sentence provable in M1 is true for M2. Let us say that M1 is complete for M2 if every sentence that is true for M2 is actually provable in M1.

  Theorem 3 says that the modal system is correct for the modal system . Well, it also happens to be complete for —every sentence true for is provable in . And so the provable sentences of are precisely the sentences that are true for . Thus a sentence is provable in if and only if it is true for all reasoners of type G.

  REASONERS OF TYPE Q (QUEER REASONERS)

  By a queer reasoner—or a reasoner of type Q—we shall mean a reasoner of type G who believes that he is inconsistent. Can a queer reasoner be consistent? We will soon see that he can! Of course, every queer reasoner is normal.

  By the modal system , we shall mean the modal system with the sentence B⊥ added as an axiom. By a minimal reasoner of type Q, we mean a reasoner who believes those and only those sentences provable in the modal system —or, what is the same thing, a reasoner who believes all and only those sentences believed by all reasoners of type Q.

  Theorem 5. The modal system is not self-referentially correct, but it is consistent.

  5

  Why is Theorem 5 true?

  It of course follows from Theorem 5 that any minimal reasoner of type Q is consistent, although he believes he isn’t!

  A comparison. It is amusing and instructive to compare minimal reasoners of types G, G*, and Q.

  (1) A minimal reasoner of type G is consistent, but can never know it.

  (2) A minimal reasoner of type G* is consistent, believes he is consistent, but can never know that he believes he is consistent.

  (3) A minimal reasoner of type Q believes he is inconsistent, but he is wrong—he is actually consistent.

  SOLUTIONS

  1. One such proposition p is the proposition that the reasoner is consistent!

  We are given that he believes ~B⊥ and we are to show that if he is consistent, he cannot believe B~B⊥. Well, since he believes all sentences provable in G, he certainly believes all tautologies, and since his beliefs are clos
ed under modus ponens, he is certainly of type 1. He believes ~B⊥, so he believes B⊥⊃⊥. If he believed B~⊥, he would believe B(B⊥⊃⊥). However, he does believe B(B⊥⊃⊥)⊃B⊥ (because he believes all sentences provable in G). And so he would then believe B(B⊥⊃⊥) and believe B(B⊥⊃⊥)⊃B⊥, hence he would believe B⊥. But since he believes ~B⊥, he would be inconsistent.

  This proves that if he believes B~B⊥, he would be inconsistent. But we are given that he is consistent, hence he can never believe B~B⊥ (even though B~B⊥ is true).

  2. B~B⊥ is true, but since he doesn’t believe it, then BB~B⊥ is false—hence B~B⊥⊃BB~B⊥ is false. But he must believe this sentence (because it is of the form BX⊃BBX where X=~B⊥), hence it is an axiom of G. And so he believes the false sentence B~B⊥⊃BB~B⊥. (He wrongly believes: “If I should believe I am consistent, then I would believe that I believe that I am consistent.” This belief is wrong, since in fact he does believe he is consistent, but doesn’t—and never will—believe that he believes he is consistent.)

  Incidentally, by the same argument, any nonnormal reasoner who believes all sentences provable in K4 must have at least one false belief. There is some p such that he believes p but doesn’t believe Bp, so Bp⊃BBp is false (for such a reasoner), yet it is an axiom of K4, and the reasoner therefore believes it. This answers Exercise 2.

  Exercise 1. It is true! If he were inconsistent and of type 1, he would believe all propositions, hence there would be no proposition p such that he believes p and doesn’t believe Bp (because he believes both p and Bp, since he believes everything). Therefore every inconsistent reasoner of type 1 must be normal—or, put another way, every nonnormal reasoner of type 1 is consistent.

  3. We proved in the last chapter that G is self-referentially correct, hence:

  (1) All sentences provable in are true for .

  Also:

  (2) All sentences of the form BX⊃X are true for .

  The reason for (2) is that if BX is true for , then X is provable in (that’s what it means for BX to be true for ), and X must therefore be true for (since is self-referentially correct). And so, if BX is true for , so is X—which means that BX⊃X is true for .

  By virtue of (1) and (2), every axiom of is true for . Since the only inference rule of is modus ponens, and since the set of sentences that is true for is closed under modus ponens (if X and X⊃Y are true for , then obviously Y is true for ), it follows that every sentence provable in must be true for . Thus the system is correct for .

  4. Since is correct for , then if ⊥ were provable in , it would be true for , which is absurd. Therefore ⊥ is not provable in , and so is consistent (even though it is not self-referentially correct).

  5. The system is of type G, and therefore by (c) of Lemma B, Chapter 27 (this page), all axioms of are true for .

  Now, let us momentarily assume that the sentence B⊥ is true for . We then get the following contradiction: If B⊥ is true for , then since all the other axioms of (i.e., the axioms of ) are true for , we would have all the axioms of being true for . Then by Corollary A1 of Lemma A, Chapter 27 (this page), the system would be self-referentially correct. And so, if B⊥ is true for , then is self-referentially correct. On the other hand, to say that B⊥ is true for is to say that ⊥ is provable in , and since ⊥ is obviously false for , this would mean that is not self-referentially correct. It is therefore contradictory to assume that B⊥ is true for . Hence B⊥ is false for , which means that ⊥ is not provable in , and so must be consistent! But also B⊥ is an axiom of , hence of course provable in , and since it is false for , then is not self-referentially correct. And so we see that is consistent but not self-referentially correct.

  • 30 •

  In Retrospect

  WE BEGAN this study with introspective reasoners and have wound up in the labyrinths of modal logic. Let us summarize some of the main things we have learned on the journey.

  1. An accurate Gödelian system of type 1 cannot prove its own accuracy—i.e., it cannot prove all propositions of the form BX⊃X.

  2. Any Gödelian system of type 1 that can prove its own accuracy is not only inaccurate, but peculiar—i.e., there must be a proposition p such that p and ~Bp are both provable.

  3. Any Gödelian system of type 1* which can prove its own nonpeculiarity is peculiar.

  4. (After Gödel’s First Incompleteness Theorem.) Any normal, stable, consistent Gödelian system of type 1 must be incomplete. More specifically, if S is a normal system of type 1 and p is a proposition such that p≡~Bp is provable in S, then:

  (a) If S is consistent, p is not provable in S.

  (b) If S is consistent and stable, then ~p is also not provable in S.

  5. (After Gödel’s Second Theorem.) No consistent Gödelian system of type 4 can prove its own consistency.

  6. A Gödelian system of type 4 can even prove that if it is consistent, then it cannot prove its own consistency—i.e., it can prove the proposition ~B⊥⊃~B(~B⊥).

  7. (After Löb.) If S is a reflexive system of type 4, then for any proposition p of the system, if Bp⊃p is provable in the system, so is p.

  8. A system of type 4 is reflexive if and only if it is of type G.

  9. A system of type 4 is Löbian if and only if it is of type G.

  10. (After Kripke, de Jongh, Sambin.) Any system of type 3 in which all propositions of the form B(BX⊃X)⊃BX are provable must be of type 4 (and hence of type G).

  11. A consistent system of type G cannot prove any proposition of the form ~BX—in particular, it cannot prove its own consistency.

  12. A consistent and stable system of type G can neither prove its own consistency nor its own inconsistency.

  13. (Semantical Soundness Theorems.) For any modal formula X, if X is provable in K, then it holds in all Kripke models; if it is provable in K4, it holds in all transitive models; and if it is provable in G, then it holds in all transitive terminal models.

  14. There do exist consistent stable systems of type G—for example, the machines of Fergusson and Craig, and the modal system . These systems, though consistent, cannot prove their own consistency.

  15. The modal systems , , and are not only consistent and stable, but are self-referentially correct. The same goes for the systems K, K4, and G.

  16. Neither of the systems or is self-referentially correct, but both of them are consistent. The system is normal, but the system is not.

  17. (a) A minimal reasoner of type G is consistent, but can never know it.

  (b) A minimal reasoner of type G* is consistent and believes that he is consistent, but can never know that he believes he is consistent.

  (c) A minimal reasoner of type Q believes he is inconsistent, but is really consistent.

  This seems like a good stopping place. There are many more fascinating things about the modal system G. By far the best general reference currently in existence is Boolos’s The Unprovability of Consistency, which I heartily recommend as a follow-up to this book. To whet the reader’s appetite, let me give a sample of a beautiful result—a fixed-point theorem—whose proof can be found there.

  Consider a modal formula with only one propositional variable, say the letter p. Let us denote such a formula as A(p). For any modal sentence S, by A(S) we mean the result of substituting S for every occurrence of p in A(p). For example, if A(p) is the formula p⊃Bp, then A(S) is the sentence BS⊃S. A sentence S is called a fixed point of A(p) if the sentence S≡A(S) is provable in G. In Problem 4 of Chapter 19, we asked the reader to find a proposition p such that any reasoner of type G will believe p≡~Bp, and we found ~B⊥ to be a solution. Thus every reasoner of type G will believe ~B⊥≡~B~B⊥, hence this sentence is provable in G. This means that ~B⊥ is a fixed point of the formula ~B⊥p. The formula B~p also has a fixed point—namely, B⊥, as we found in the solution to Problem 5, Chapter 19. The reader might find it a profitable exercise to try to show that the formula Bp⊃B⊥ has a fixed point—namely, BB⊥⊃B⊥.


  Not every formula A(p) has a fixed point; for example, the formula ~p doesn’t (otherwise the system G would be inconsistent, which we know is not so). Now, a formula A(p) is called modalized in p if every occurrence of p in A(p) lies in the part of A(p) of the form BX, where X is a formula. (Examples: Bp⊃BBp is modalized in p; Bp⊃p is not, but B(Bp⊃p) is.) The logicians Claudio Bernardi and C. Smorynski have independently proved that any formula A(p) that is modalized in p does have a fixed point S—moreover, the formula B(p≡A(p))⊃B(p≡S) is provable in G. This result is known as the Bernardi-Smorynski Fixed-Point Theorem.

  Fixed points are remarkable things. By virtue of the self-referential correctness of the system G, any fixed point S of a formula A(p) is not only provable in G if and only if A(S) is provable, but is also true (for G) if and only if A(S) is true—because the provability of S≡A(S) implies its truth. Let us say that a formula A(p) applies to a sentence S if A(S) is true (for G). A fixed point of a formula can then be thought of as a sentence that asserts that the formula applies to that very sentence.

  More generally, consider a formula A(p,q) having no propositional variables other than p and q. For any formula X, by A(X,q) is meant the result of substituting X for p in A(p,q). By a fixed point of A(p,q) is meant a formula H having no variables other than q, such that the formula H≡A(H,q) is provable in G. The logicians D. H. J. de Jongh and Giovanni Sambin have proved that if A(p,q) is modalized in p (but not necessarily in q), then A(p,q) has a fixed point H; moreover, the formula B(p≡A(p,q))⊃B(p≡H) is provable in G.

  Examples are already familiar from Chapter 19. Bq is a fixed point of B(p⊃q), by Problem 6, and Bq⊃q is a fixed point of Bp⊃q, by Problem 7. Indeed, reflexivity is equivalent to there being a fixed point for Bp⊃q. The remarkable thing is that for a modal system of type 4, the existence of a fixed point for the one formula Bp⊃q is enough to guarantee fixed points for all formulas A(p,q) that are modalized in p. A proof of this can also be found in Boolos.