Forever Undecided
Page 13
(1) He is a modest reasoner of type 4.
(2) He is of type G (he is of type 4 and believes he is modest).
(3) He is of type 3 and believes he is modest.
(4) He is a reflexive reasoner of type 4.
MODESTY AND BELIEF IN ONE’S MODESTY
For any proposition p, let Mp be the proposition B(Bp⊃p)⊃Bp. Thus Mp is the proposition that the reasoner is modest with respect to p. We are about to show that any reasoner of type 4 who believes he is modest really is modest. More specifically, we will show the stronger result that for any proposition p, if he believes that he is modest with respect to p (without necessarily believing that he is modest with respect to any other propositions), then he really is modest with respect to p (in fact this holds even for normal reasoners of type 1). The converse of this stronger fact is not necessarily true —i.e., if a reasoner of type 4 is modest with respect to p, then he does not necessarily believe that he is modest with respect to p. However, we will show that if a reasoner of type 4 is modest with respect to the proposition Mp, then he will believe that he is modest with respect to p (in other words, if he is modest with respect to Mp, then he will believe Mp). From this it will of course follow that if a reasoner of type 4 is modest (with respect to all propositions), then he will know that he is modest.
1
Why is it true that any normal reasoner of type 1 (and hence any reasoner of type 4) who believes he is modest with respect to p must really be modest with respect to p?
2
By virtue of the last problem, given any proposition p, the proposition B(Mp)⊃Mp is true for any reasoner of type 4. Prove that any reasoner of type 4 believes the proposition B(Mp)⊃Mp. (He knows that if he should believe that he is modest with respect to p, then he really is modest with respect to p.)
3
Using the last problem, show that any reasoner of type 4 who is modest with respect to Mp will believe that he is modest with respect to p.
It of course follows from Problem 1 that any reasoner of type 4 who believes he is modest, really is modest. And it follows from Problem 3 that if a reasoner of type 4 is modest (with respect to every proposition), then he must believe he is modest (because for every proposition p, he is modest with respect to Mp, hence according to Problem 3, he believes he is modest with respect to p). We have thus established Theorem M.
Theorem M. A reasoner of type 4 is modest if and only if he believes he is modest.
By virtue of Theorem M, a reasoner is of type G if and only if he is a modest reasoner of type 4. Stated in terms of systems rather than reasoners, we have Theorem M1.
Theorem M1. For a system of type 4, the following two conditions are equivalent:
(1) For any proposition p, if Bp⊃p is provable in the system, so is p.
(2) For any proposition p, the proposition B(Bp⊃p)⊃Bp is provable in the system.
Stated more briefly, a system of type 4 is Löbian if and only if it is of type G.
We proved in the last chapter that every reflexive system of type 4 is Löbian—this is Löb’s Theorem. Combining this with Theorem M1, we have the important Theorem M2.
Theorem M2. Every reflexive system of type 4 is of type G.
Another proof of Theorem M2 will be given in the next chapter.
THE KRIPKE, DE JONGH, SAMBIN THEOREM
We now wish to prove that any reasoner of type 3 who believes that he is modest must also believe that he is normal—and hence must be of type 4, and therefore of type G.
We will actually prove more. Let us say that a reasoner is normal with respect to a proposition p if his believing p implies that he will also believe Bp. A reasoner, then, is normal if and only if he is normal with respect to every proposition p. We will say that a reasoner believes that he is normal with respect to p if he believes the proposition Bp⊃BBp. (Of course if the reasoner is normal with respect to p, then the proposition Bp⊃BBp is true.) We will say that a reasoner believes he is normal if for every proposition p, he believes that he is normal with respect to p. A reasoner of type 4, then, is a reasoner of type 3 who believes he is normal. The Kripke, de Jongh, Sambin Theorem states that every reasoner of type 3 who believes he is modest will also believe he is normal (and hence will be of type G). We will prove the stronger result that every reasoner of type 1* who believes he is modest will also believe he is normal. But first we will prove the more elementary result that every reasoner of type 1* who is modest is also normal (this result may be new). Then we will prove sharper versions of both these results.
We recall from Chapter 10 that we are using the notation Cp for (p&BP), where we read Cp as “the reasoner correctly believes p.” The propositions Cp⊃p, Cp⊃Bp, p⊃(Bp≡Cp) are, of course, all tautologies. We first need the following lemma:
Lemma 1. Any reasoner of type 1* believes the following propositions:
(a) BCp⊃BBp
(b) p⊃(BCp⊃Cp)
4
Why is Lemma 1 true?
5
Now show that any modest reasoner of type 1* must be normal. More specifically (and this is a hint!), show that for any proposition p, if a reasoner of type 1* is modest with respect to Cp, then he must be normal with respect to p.
6
Now show that any reasoner of type 1* who believes he is modest must also believe that he is normal. More specifically, show that for any proposition p, if a reasoner of type 1* believes that he is modest with respect to Cp, then he will believe that he is normal with respect to p.
Since every reasoner of type 3 is also of type 1* (as we proved in Chapter 11), we have now established Theorem M3.
Theorem M3 (Kripke, de Jongh, Sambin). Every reasoner of type 3 who believes he is modest is of type G.
Stated for systems rather than reasoners, Theorem M3 states that for any system of type 3, if all propositions of the form B(Bp⊃p)⊃Bp are provable in the system, then all propositions of the form Bp⊃BBp are provable in the system, and hence the system must be of type G.
The following two exercises provide some curious alternative ways of characterizing reasoners of type G.
Exercise 1. Show that for any reasoner of type 4, the following two conditions are equivalent.
(a) The reasoner is of type G.
(b) And, for any propositions p and q, the reasoner believes B(q⊃p)⊃(B(Bp⊃q)⊃Bp).
Exercise 2. Prove that for any reasoner of type 4, the following two conditions are equivalent.
(a) He is of type G.
(b) For any propositions p and q, if he believes (Bp&Bq)⊃p, then he will believe Bq⊃p.
SOLUTIONS
1. By hypothesis, the reasoner believes Mp—the proposition B(Bp⊃p)⊃Bp. We are to show that he is modest with respect to p—i.e., that if he believes Bp⊃p, then he believes p. So we assume he believes Bp, and we are to show that he believes (or will believe) p.
Since he believes Bp⊃p (by assumption), he believes B(Bp⊃p) (since he is normal). Also, he believes B(Bp⊃p)⊃Bp (by hypothesis). Then, being of type 1, he believes, or will believe, Bp. He also believes Bp⊃p. Hence he believes, or will believe, p.
2. Essentially, this follows from Problem 1 and the fact that a reasoner of type 4 “knows” that he is of type 4, hence knows how he can reason. In more detail, the reasoner reasons thus:
“Suppose I ever believe Mp—that is, suppose I ever believe B(Bp⊃p)⊃Bp. I am to show that I am modest with respect to p—i.e., that if I ever believe Bp⊃p, then I will believe p. So suppose I believe Bp⊃p; it remains to show that I will believe p.
“And so I will assume that I will believe B(Bp⊃p)⊃Bp and that I will believe Bp⊃p. I must then show that I will believe p. Well, since I will believe Bp⊃p (by my second assumption), then I will believe B(Bp⊃p). Since I also believe B(Bp⊃p)⊃Bp (by my first assumption), then I will believe Bp. Once I believe Bp and Bp⊃p, then I will believe p.”
At this point the reasoner has derived Bp from the two assumptions B(Mp) and B(Bp⊃p), he will believe (
B(Mp)&B(Bp⊃p))⊃Bp, and the logically equivalent proposition B(MP)⊃(B(Bp⊃p)⊃Bp), which is the proposition B(Mp)⊃Mp.
3. If a reasoner believes B(Mp)⊃Mp and is modest with respect to Mp, then he will of course believe Mp (because for any proposition q, if he believes Bq⊃q and is modest with respect to q, he will believe q—and so this is the case if q is the proposition Mp). Now a reasoner of type 4 does believe B(Mp)⊃Mp (as we showed in the last problem), and so if he is modest with respect to Mp, he will believe Mp (which means he will believe he is modest with respect to p).
4. The reasoner is assumed to be of type 1*.
(a) Since he is of type 1, he believes the tautology Cp⊃Bp. Being regular, he will then believe BCp⊃BBp.
(b) Since he is of type 1, he believes the tautology Cp⊃p. Being regular, he then believes BCp⊃Bp. Being of type 1, he then believes (p&BCp)⊃(p&Bp), which is a logical consequence of the last proposition. Thus he believes (p&BCp)⊃Cp (because Cp is the proposition p&Bp) and hence he will believe the logically equivalent proposition p⊃(BCp⊃Cp).
5. Suppose a reasoner of type 1* is modest with respect to Cp. We are to show that he is then normal with respect to p.
Suppose he believes p. He also believes p⊃(BCp⊃Cp), according to (b) of Lemma 1, hence he will believe BCp⊃Cp. Believing this and being modest with respect to Cp, he will believe Cp. He also believes the tautology Cp⊃Bp, and since he believes Cp, he will believe Bp.
This proves that if he believes p, he will believe Bp, hence he is normal with respect to p.
6. Suppose a reasoner of type 1* believes he is modest with respect to Cp. By (b) of Lemma 1, he believes p⊃(BCp⊃Cp). Since he is regular, he then believes Bp⊃B(BCp⊃Cp). But he also believes B(BCp⊃Cp)⊃BCp, since he believes he is modest with respect to Cp. Believing these last two propositions, he will believe Bp⊃BCp. He also believes BCp⊃BBp, according to (a) of Lemma 1, and will therefore believe Bp⊃BBp—he will believe that he is normal with respect to p.
Solution to Exercise 1. (a) A reasoner of type G will reason: “Suppose B(q⊃p) and B(Bp⊃q). This means I’ll believe q⊃p and I’ll believe Bp⊃q, hence I’ll believe Bp⊃p, and since I am modest, I’ll believe p. Thus (B(q⊃p)&B(Bp⊃q))⊃Bp, or, what is logically equivalent, B(q⊃p)⊃(B(Bp⊃q)⊃Bp).”
(b) Suppose that for any proposition p and q, a reasoner of type 4 believes B(q⊃p)⊃(B(Bp⊃q)⊃Bp). Then this is also true if q and p are the same proposition, and so he believes B(p⊃p)⊃(B(Bp⊃p)⊃p). He also believes B(p⊃p)—because he believes the tautology p⊃p, and being normal, he then believes B(p⊃p)—and hence he believes B(Bp⊃p)⊃Bp. Therefore the reasoner is of type G.
Solution to Exercise 2. (a) Suppose a reasoner of type 4 believes (Bp&Bq)⊃p. Then he will reason: “(Bp&Bq)⊃p. Hence Bq⊃(Bp⊃p). I now believe Bq⊃(Bp⊃p). Now, suppose Bq. Then I’ll believe Bq, and since I believe Bq⊃(Bp⊃p), I’ll believe Bp⊃p. And therefore Bq⊃B(Bp⊃p). Also B(Bp⊃p)⊃Bp, and so Bq⊃Bp. Thus Bq⊃(Bp&Bq). And since (Bp&Bq)⊃p, then Bq⊃p.”
(b) Suppose a reasoner of type 4 is such that for any proposition p and q, if he believes (Bp&Bq)⊃p, then he believes Bq⊃p. We will show that he is modest (and hence of type G).
Suppose he believes Bp⊃p. Then for any proposition q, he certainly believes (Bp&Bq)⊃p. Hence, for any proposition q, he believes Bq⊃p. Well, take any proposition q such that he believes q (for example, take q = T). Then he believes Bq, and believing Bq⊃p, he will believe p.
* * *
†The Unprovability of Consistency (Cambridge University Press, 1979).
• 19 •
Modesty, Reflexivity, and Stability
MORE ON REASONERS OF TYPE G
1
There is something very interesting about a consistent reasoner of type G—or even a consistent modest reasoner of type 1*—namely, that there is no proposition p such that he can believe that he doesn’t believe p! (He cannot believe ~Bp!) Why is this?
2
It hence follows that if a reasoner of type G believes that he doesn’t believe p, then he will be inconsistent (even though it may be true that he doesn’t believe p). Thus for any reasoner of type G, the proposition B~Bp⊃B⊥ is true.
Prove that for any reasoner of type G and any proposition p, the proposition B~Bp⊃B⊥ is not only true, but is known to be true by the reasoner.
3
This problem is a sharpening of an earlier theorem. Let us recall how we proved that every reflexive reasoner of type 4 is of type G. We did this in two stages: We first proved that every reflexive reasoner of type 4 is Löbian (Löb’s Theorem), and then we proved that every Löbian reasoner of type 4 is of type G.
Now, let us consider a reasoner of type 4 who is not necessarily reflexive. It might be that for some proposition q, there is a proposition p such that the reasoner believes p≡(Bp⊃q), and for some other proposition q, there is no such proposition p. This much we do know: If, for a given q, there is some p such that the reasoner believes p≡(Bp⊃q), then if the reasoner believes Bq⊃q, he will also believe q (by Theorem 1, Chapter 15), and hence the proposition B(Bq⊃q)⊃Bq is true. But does that mean that the reasoner necessarily knows that it is true? The answer is the solution to this problem:
Prove that for any propositions p and q, if a reasoner of type 4 believes p≡(Bp⊃q), then he believes B(Bq⊃q)⊃Bq.
Discussion. Of course the solution to Problem 3 yields an alternative proof that any reflexive reasoner of type 4 must be of type G. I will now mention something else worth noting.
By virtue of Problem 3, given any propositions p and q, the proposition B(p≡(Bp⊃q))⊃(B(Bq⊃q)⊃Bq) is true for any reasoner of type 4. It can be shown that any reasoner of type 4 knows that the above proposition is true. The reader might try this as an exercise.
SOME FIXED-POINT PRINCIPLES†
We have now seen two different proofs that every reflexive reasoner of type 4 is of type G. We will shortly prove that every reasoner of type G is reflexive—for every q, there is some p such that he believes p≡(Bp⊃q). But first some preliminary problems.
4
I have already warned you of the dangers of believing any proposition of the form p≡~Bp. If, however, you happen to be a reasoner of type G, then I’m afraid you have no alternative!
Given a reasoner of type G, find a proposition p such that he must believe p≡~Bp.
5
It is also true that given any reasoner of type G, there is a proposition p such that he believes p≡B~p. Prove this.
6
Given a proposition q, find a proposition p (expressible in terms of q) such that any reasoner of type G will believe p≡B(p⊃q).
7
Do the same with Bp⊃q—i.e., find a proposition p such that any reasoner of type G will believe p≡(Bp⊃q).
Note: The result of the last problem is that every reasoner of type G is reflexive. We have already proved that every reflexive reasoner of type 4 is of type G, and so we now have Theorem L*.
Theorem L*. A reasoner of type 4 is of type G if and only if he is reflexive.
SOME MORE FIXED-POINT PROPERTIES
8
Given a reasoner of type G and any propositions p and q, show that if the reasoner believes p≡B(p⊃q), then he will believe p≡Bq.
9
Show that if a reasoner of type G believes p≡(Bp⊃q), then he will believe p≡(Bq⊃q).
10
A reasoner of type G goes to a knight-knave island (and believes the rules of the island), and asks a native whether he is married. The native replies: “You will believe that either I am a knight or I am married.”
Will the reasoner necessarily believe that the native is married? Will he necessarily believe that he is a knight?
STABILITY
In preparation for the next chapter, we will now introduce the notion of stability.
We will call a reasoner stable if for every proposition p, if he believes that he believes p, then he really does believe p
. We will call a reasoner unstable if he is not stable—i.e., if there is at least one proposition p such that the reasoner believes that he believes p, but he does not actually believe p. Of course every accurate reasoner is automatically stable, but stability is a much weaker condition than accuracy. An unstable reasoner is inaccurate in a very strange way; indeed, instability is as strange a psychological characteristic as peculiarity.
We note that stability is the converse of normality. If a normal reasoner believes p, then he believes Bp, whereas if a stable reasoner believes Bp, then he believes p.
We shall use the terms stable and unstable for mathematical systems as well as reasoners. We will call a mathematical system S stable if for any proposition p, if Bp is provable in S, then so is p. We shall say that a reasoner is stable with respect to a particular proposition p if the proposition BBp⊃Bp is true—i.e., if his belief that he believes p guarantees that he really does believe p. We shall say that he believes he is stable with respect to p if he believes the proposition BBp⊃Bp. Finally, we will say that he believes that he is stable if for every proposition p, he believes BBp⊃Bp (for every p, he believes that he is stable with respect to p).
11
Prove that if a modest reasoner believes that he is stable, then he is either unstable or inconsistent.