Forever Undecided
Page 8
(a) He will believe B(p⊃(q⊃r))⊃(Bp⊃(Bq⊃Br)).
(b) If he ever believes B(p⊃(q⊃r)), then he will believe Bp⊃(Bq⊃Br).
2
Show that if a reasoner of type 3 believes p⊃(q⊃r), then he will believe Bp⊃(Bq⊃Br). This fact will have many applications.
3. Regularity
In the last chapter we defined a reasoner to be of type 1* if he is of type 1 and if for any propositions p and q, if he ever believes p⊃q, he will also believe Bp⊃Bq. This second condition will be given a name—we will call a reasoner regular if his belief in p⊃q implies his belief in Bp⊃Bq.
Prove that every reasoner of type 3 is regular (and is thus of type 1*).
4
Prove that if a regular reasoner of type 1 believes p≡q, then he will believe Bp≡Bq.
5
There is an interesting connection between regularity and normality. For a regular reasoner of type 1, if there is so much as one proposition q such that he believes Bq, then he must be normal. Why is this?
6
Any reasoner of type 1 who believes p and believes q will believe p&q (which is a logical consequence of the two propositions p and q). Thus the proposition (Bp&Bq)⊃B(p&q) is true for any reasoner of type 1, hence true for any reasoner of type 3.
Prove that any reasoner of type 3 believes (Bp&Bq)⊃B(p&q). (He knows that if he should ever believe p and believe q, he will believe p&q.)
CONSISTENCY
We say that a reasoner is consistent if the set of all propositions that he believes (or has believed or will believe) is a consistent set, and we shall say that he is inconsistent if his set of beliefs is inconsistent. For any reasoner of type 1, the set of his beliefs is logically closed; hence it follows from Principle C of Chapter 8 that the following three conditions are equivalent:
(1) He is inconsistent (he believes ⊥).
(2) He believes some proposition p and its negation (~p).
(3) He believes all propositions.
We shall say that a reasoner believes he is consistent if he believes ~B⊥ (he believes that he doesn’t believe ⊥). We shall say that he believes that he is inconsistent if he believes B⊥ (he believes that he believes ⊥). A reasoner of even type 1 who is inconsistent will also believe that he is inconsistent (because he will believe everything), although a reasoner who believes that he is inconsistent is not necessarily inconsistent (although it can be shown that he must have at least one false belief).
Any reasoner of type 1 who believes some proposition p and its negation ~p will be inconsistent—he will believe ⊥—and so the proposition (Bp&B~p)⊃B⊥ is true for a reasoner of type 1.
7
Prove that any reasoner of type 3 believes the proposition (Bp&B~p)⊃B⊥.
Note: This last problem is quite crucial for the next chapter. It means that for any proposition p, a reasoner of type 3 knows that if he should ever believe p and also believe ~p, then he will be inconsistent. (Of course this also applies to a reasoner of type 4, since every reasoner of type 4 is also of type 3.)
Inconsistency and Peculiarity. We recall that a reasoner is called peculiar if he believes some proposition p and also believes that he doesn’t believe p. We have remarked that a peculiar reasoner is not necessarily inconsistent. However, any peculiar reasoner of type 3 is inconsistent, as the following problem will reveal.
8
Prove that any peculiar normal reasoner of type 1 must be inconsistent (and hence any peculiar reasoner of type 3 must be inconsistent).
Exercise 1. According to the above problem, for any proposition p, the proposition (Bp&B~Bp)⊃B⊥ is true for a reasoner of type 3, hence also true for a reasoner of type 4. Prove that any reasoner of type 4 correctly believes the proposition (Bp&B~Bp)⊃B⊥ (he knows that if he should ever be peculiar, he will be inconsistent).
9. A Little Puzzle
Suppose a reasoner of type 4 believes p≡Bq. Will he necessarily believe p⊃Bp?
AWARENESS OF SELF-AWARENESS
Reasoners of type 4 have one marvelous property not shared by reasoners of lower types—namely, that they know they are of type 4, in a sense we will precisely define. Thus, for example, a reasoner may be of type 3 without knowing it, but a reasoner cannot be of type 4 unless he knows it.
Let us say that a reasoner believes he is of type 1 if he believes all propositions of the form BX, where X is any tautology, and believes all propositions of the form (Bp&B(p⊃q))⊃Bq. If he also believes all propositions of the form B((Bp&B(p⊃q))⊃Bq), then we will say that he believes he is of type 2. If he also believes all propositions of the form Bp⊃BBp, then we will say that he believes he is of type 3. If he also believes all propositions of the form B(Bp⊃BBp), then we will say that he believes he is of type 4. For each of these types, we will say that a reasoner knows that he is of that type if he believes he is of that type and really is of that type.
It is not difficult to see that a reasoner who knows that he is of type 1 is of type 2, and that any reasoner of type 3 knows that he is of type 2 (though he doesn’t necessarily know that he is of type 3). Also a reasoner is of type 4 if and only if he knows that he is of type 3. The reader should try proving these facts as exercises.
The following problem is more interesting.
10
Prove that a reasoner of type 4 knows that he is of type 4.
This problem is interesting for several reasons. For one thing, it shows that being of type 4 constitutes a natural resting place in our hierarchy of reasoners. (It would be pointless, for example, to define a reasoner to be of type 5 if he is a reasoner of type 4 who knows that he is of type 4, since any reasoner of type 4 already knows he is of type 4, and thus we wouldn’t get anything new.)
Secondly, anything that you or I can prove about all reasoners of type 4, using just propositional logic, any reasoner of type 4 can prove about himself, since he also knows propositional logic and knows that he is of type 4.
Exercise 2. To say that a reasoner is regular is to say that for any propositions p and q, the proposition B(p⊃q)⊃B(Bp⊃Bq) is true of the reasoner. (The proposition B(p⊃q)⊃B(Bp⊃Bq) is the proposition that if the reasoner believes p⊃q, then he will believe Bp⊃Bq.) Let us say that a reasoner believes that he is regular if he believes all propositions of the form B(p⊃q)⊃B(Bp⊃Bq).
Prove that every reasoner of type 4 knows that he is regular (i.e., he is regular and believes that he is regular).
Exercise 3. Prove that if a reasoner of type 4 believes p⊃(Bp⊃q), then he will believe Bp⊃Bq. (The solution to this exercise will be given in Chapter 15; see this page.)
SOLUTIONS
1. Suppose the reasoner is of type 2. Take any propositions p, q, and r.
By Fact 1, he believes the following: (1) B(p⊃(q⊃r))⊃(Bp⊃B(q⊃r)). The reason is that for any propositions X and Y, he believes B(X⊃Y)⊃(BX⊃BY), so take p for X and (p⊃q) for Y.
Again, by Fact 1, he believes: (2) B(q⊃r)⊃(Bq⊃Br).
The following proposition is a logical consequence of (2):
(3) (Bp⊃B(q⊃r))⊃(Bp⊃(Bq⊃Br)). The reason is that, for any propositions X, Y, and Z, the proposition (X⊃Y)⊃(X⊃Z) is a logical consequence of Y⊃Z, as the reader can verify. We take Bp for X, B(q⊃r) for Y, and Bq⊃Br for Z, and we see that (3) is a logical consequence of (2).
We now know that the reasoner believes both (1) and (2), and B(p⊃(q⊃r))⊃(Bp⊃(Bq⊃Br)) is a logical consequence of (1) and (2), so the reasoner believes it. This proves (a).
(b) Suppose the reasoner believes B(p⊃(q⊃r)). By (a) he also believes B(p⊃(q⊃r))⊃(Bp⊃(Bq⊃Br)); hence he will believe Bp⊃(Bq⊃Br), since it is a logical consequence of the two propositions above.
Note: I will not give such detailed arguments in the future. By now the reader should have enough experience to follow briefer arguments and supply missing steps.
2. Consider now a reasoner of type 3 who believes p⊃(q⊃r). Since he is normal, he will believe B(p⊃(q⊃r)
). Then, by (b) of the last problem, he will believe Bp⊃(Bq⊃Br).
3. Suppose a reasoner of type 3 believes p⊃q. Since he is normal, he will then believe B(p⊃q). Then, by the corollary to Fact 1, he will believe Bp⊃Bq. This proves that he is regular.
4. Suppose a regular reasoner of type 1 believes p≡q. Then he will believe both p⊃q and q⊃p (since they are both logical consequences of p≡q). Being regular, he will then believe both Bp⊃Bq and Bq⊃Bp. Then, being of type 1, he will believe Bp≡Bq (which is a logical consequence of the last two propositions).
5. Consider a regular reasoner of type 1. Suppose q is some proposition such that the reasoner believes Bq. Now, let p be any proposition that the reasoner believes. We are to show that he will believe Bp.
The proposition p⊃(q⊃p) is a tautology (as the reader can verify), hence the reasoner believes it. He also believes p (by assumption), hence he will believe q⊃p. Then, since he is regular, he will believe Bq⊃Bp. Then, since he believes Bq, he will believe Bp. This proves that he is normal.
6. We are considering a reasoner of type 3. Now, the proposition p⊃(q⊃(p&q)) is obviously a tautology, hence the reasoner will believe it. Then, by (b) of Problem 1, he will believe Bp⊃(Bq⊃B(p&q)), hence he will believe the logically equivalent proposition (Bp&Bq)⊃B(p&q). (For any proposition X, Y, and Z, the proposition X⊃(Y⊃Z) is logically equivalent to (X&Y)⊃Z.)
7. The proposition (p&~p)⊃⊥ is a tautology, hence any reasoner of type 3 (or even of type 1) will believe it. Since a reasoner of type 3 is regular (by Problem 3), he will then believe B(p&~p)⊃B⊥. He also believes (Bp&B~p)⊃B(p&~p) (by Problem 6). Believing these last two propositions, he will believe (Bp&B~p)⊃B⊥, which is a logical consequence of them.
Remarks. For any proposition q, the proposition p⊃(~p⊃q) is a tautology. Hence by the above argument applied to q, instead of ⊥, a reasoner of type 3 will believe (Bp&B~p)⊃Bq.
8. This is pretty obvious. If a normal reasoner believes p, he will believe Bp. If he also believes ~Bp and is of type 1, he will be inconsistent. Thus if a normal reasoner of type 1 believes p and believes ~Bp, he will be inconsistent.
Solution to Exercise 1. A reasoner of type 4 believes Bp⊃BBp. He thus believes its logical consequence (Bp&B~Bp)⊃(BBp&B~Bp). He also believes (BBp&B~Bp)⊃B⊥ (by Problem 7, since ~Bp is the negation of Bp). The proposition (Bp&B~p)⊃B⊥ is a logical consequence of the last two propositions, and so the reasoner will believe it.
In other words, a reasoner of type 4 can reason thus: “Suppose I ever believe p and also believe ~Bp. Since I will believe p, I will also believe Bp, hence I will believe both Bp and ~Bp, and then I will be inconsistent. And so, if I ever believe p and ~Bp, I will be inconsistent.”
9. Suppose a reasoner of type 4 believes p≡Bq. He is regular (by Problem 3, since he is also of type 3), and so by Problem 3 he will believe Bp≡BBq. Hence he will believe BBq⊃Bp. He also believes Bq⊃BBq (since he is of type 4), hence by propositional logic he will believe Bq⊃Bp. From p≡Bq and Bq⊃Bp, he will deduce p⊃Bp. And so the answer is yes.
10. Suppose the reasoner is of type 4. He then satisfies all the conditions that define a reasoner of type 4. We are to show that he believes all these conditions.
(1a) Take any tautology X. Being of type 4 (and hence of type 1), he believes X. Then, since he is normal, he believes BX. Thus for any tautology X, he believes BX.
(1b) It follows from the fact that he is of type 2 that he believes all propositions of the form (Bp&B(p⊃q))⊃Bq.
At this point we realize that he knows that he is of type 1. (In fact, by the above argument, any normal reasoner of type 2—i.e., any reasoner of type 3—knows that he is of type 1.)
(2) Since he believes all propositions of form (Bp&B(p⊃q))⊃Bq, and he is normal, then he believes B((Bp&B(p⊃q))⊃Bq).
At this point we see that he knows he is of type 2. (In fact, any reasoner of type 3 knows that he is of type 2.)
(3) Since the reasoner is of type 4, then it is immediate that he knows all propositions of the form Bp⊃BBp—i.e., he knows that he is normal.
At this point we see that a reasoner of type 4 knows that he is of type 3. (But a reasoner of type 3 doesn’t necessarily know that he is of type 3, because he may not know that he is normal.)
(4) Since the reasoner of type 4 believes Bp⊃BBp, and he is normal, he believes B(Bp⊃BBp).
Now we see that a reasoner of type 4 knows that he is of type 4 (that is, he knows all of the propositions characterizing a reasoner of type 4).
Solution to Exercise 2. Consider a reasoner of type 4. Since he is of type 1, he believes B(p⊃q)⊃(Bp⊃Bq). Since he is regular, he then believes BB(p⊃q)⊃B(Bp⊃Bq). He also believes B(p⊃q)⊃BB(p⊃q), since he knows he is normal. From this and the last fact, it follows that he must believe B(p⊃q)⊃B(Bp⊃Bq).
• 12 •
The Consistency Predicament
NOW the stage is set, and the real show begins!
A reasoner of type 4 visits the Island of Knights and Knaves and believes the rules of the island. And so whenever a native makes a statement, the reasoner will believe that if the native is a knight, the statement is true, and its converse. Thus, if a native asserts a proposition p, then the reasoner will believe k⊃p (where k is the proposition that the native is a knight), and he will also believe p⊃k. Moreover, since the reasoner is of type 4, he is regular (as we showed in Problem 3 of the last chapter), and so if the native asserts p, the reasoner will believe not only k⊃p, but also Bk⊃Bp—that is, he will believe: “If I ever believe that he is a knight, then I will believe what he said.”
We recall from the last chapter (Problem 7) that any reasoner of type 4, or even of type 3, knows that if he should ever believe p and believe ~p, he will be inconsistent (p can be any proposition).
Let us review and label these facts.
Fact 1. Suppose a native makes a statement to a reasoner of type 4. Then, (a) The reasoner will believe that if the native is a knight, the statement must be true (and conversely, that if the statement is true, then the native must be a knight). (b) The reasoner will also believe that if he should ever believe that the native is a knight, then he will believe what the native said.
Fact 2. For any proposition p, a reasoner of type 4 knows that if he should ever believe p and also believe ~p, then he will be inconsistent.
With these facts in mind, we are ready to embark. The first big result to which we turn is the following theorem.
Theorem 1 (after Gödel’s Consistency Theorem). Suppose a native of the island says to a reasoner of type 4: “You will never believe that I am a knight.” Then if the reasoner is consistent, he can never know that he is consistent; or, stated otherwise, if the reasoner ever believes that he cannot be inconsistent, he will become inconsistent!
1
Prove Theorem 1.
Solution. Suppose the reasoner does believe that he is (and will remain) consistent. We will show that he will become inconsistent.
The reasoner reasons: “Suppose I ever believe that the native is a knight. Then I’ll believe what he said—I’ll believe that I don’t believe that he is a knight. But also, if I believe he’s a knight, then I’ll believe that I do believe he’s a knight (since I am normal). Therefore, if I ever believe that he’s a knight, then I’ll believe both that I do believe he’s a knight and that I don’t believe he’s a knight, which means I will be inconsistent. Now, I’ll never be inconsistent [sic!], hence I will never believe he’s a knight. He said that I would never believe he’s a knight, and what he said was true, hence he is a knight.”
At this point, the reasoner believes the native is a knight, and since he is normal, he will then know that he believes this. Hence the reasoner will continue: “Now I believe he is a knight. He said that I never would, hence he made a false statement, so he is not a knight.”
At this point the reasoner believes that the native is a knight and also believes that the native is not a knight, and so he i
s now inconsistent.
Discussion. The important mathematical content of the above theorem can be presented without reference to knights and knaves. The function of the knight-knave island was to provide a simple method of getting some proposition k (in this case, that the native is a knight) such that the reasoner would believe “k is true if and only if I will never believe k.” Any other method of getting such a proposition k would serve as well. Thus Theorem 1 is but a special case of the following theorem (which has nothing to do with knights and knaves).
Theorem G. If a consistent reasoner of type 4 believes some proposition of the form p≡~Bp, then the reasoner can never know that he is consistent. Stated otherwise, if a reasoner of type 4 believes p≡~Bp and believes that he is (and will remain) consistent, then he will become inconsistent.
We shall prove Theorem G in a sharper form.
Theorem G#. Suppose a normal reasoner of type 1 believes a proposition of the form p≡~Bp. Then:
(a) If he ever believes p, he will become inconsistent.
(b) If he is of type 4, then he knows that if he should ever believe p, then he will become inconsistent—i.e., he will believe the proposition Bp⊃B⊥.
(c) If he is of type 4 and believes that he cannot be inconsistent, then he will become inconsistent.
Proof. (a) Suppose he believes p. Being normal, he will then believe Bp. Also, since he believes p and believes p≡~Bp, he must believe ~Bp (since he is of type 1). And so he will then believe both Bp and ~Bp, hence he will be inconsistent.
(b) Suppose he is of type 4. Since he is of type 1 and believes p≡~Bp, he must also believe p⊃~Bp. Also, he is regular, hence he will then believe Bp⊃B~Bp. He also believes Bp⊃BBp (since he knows he is normal). Hence he will believe Bp⊃(BBp&B~Bp), which is a logical consequence of the last two propositions. He also believes (BBp&B~Bp)⊃B⊥ (by Fact 2, since for any proposition X, he believes (BX&B~X)⊃B⊥, and so he believes this in the special case where X is Bp). Once he believes both Bp⊃(BBp&B~Bp) and (BBp&B~Bp)⊃B⊥, he will have to believe Bp⊃B⊥ (since he is of type 1).