Forever Undecided
Page 14
Remark. The above result of course implies that no consistent stable reasoner of type G can ever know that he is stable.
SOLUTIONS
1. Suppose a modest reasoner of type 1* believes ~Bp. He also believes the tautology ⊥⊃p, hence he believes B⊥⊃Bp (because he is regular), hence he believes the logically equivalent proposition ~Bp⊃~B⊥, hence he believes ~Bp⊃(B⊥⊃⊥). Since he believes ~Bp, he then believes (B⊥⊃⊥). Then, since he is modest, he will believe ⊥, which means that he will be inconsistent. Therefore, if he is consistent (and a modest reasoner of type 1*), he will never believe ~Bp.
2. Any reasoner of type 4 (or even any normal reasoner of type 1*) will successively believe the following propositions:
(1) ⊥⊃p
(2) B⊥⊃Bp
(3) ~Bp⊃~B⊥
(4) ~B⊥⊃(B⊥⊃⊥)—this is a tautology
(5) ~Bp⊃(B⊥⊃⊥)—by (3) and (4)
(6) B~Bp⊃B(B⊥⊃⊥)
If the reasoner is of type G, he will also believe B(B⊥⊃⊥)⊃B⊥, hence he will believe B~Bp⊃B⊥.
3. Suppose a reasoner of type 4 believes p≡(Bp⊃q). We showed in Lemma 1, Chapter 15, this page, that he will then believe Bp⊃Bq. Since he is normal, he will believe that he believes p≡(Bp⊃q) and he will believe that he believes Bp⊃Bq. And so he reasons: “I believe p≡(Bp⊃q), and I believe Bp⊃Bq. Now, suppose I ever believe Bq⊃q. Then, since I believe Bp⊃Bq, I will believe Bp⊃q. And, since I believe p≡(Bp⊃q), I will believe p. Then I will believe Bp, and since I believe Bp⊃q, I will believe q. This shows that if I ever believe Bq⊃q, I will believe q.”
At this point the reasoner believes B(Bq⊃q)⊃Bq.
4 and 5. We will first solve Problem 5. Take p to be B⊥. We claim that any reasoner of type G believes B⊥≡B~B⊥ (and hence believes p≡B~p, where p is the proposition B⊥).
We showed in Problem 2 that for any proposition p, a reasoner of type G believes B~Bp⊃B⊥, hence (taking ⊥ for p) he believes B~B⊥⊃B⊥. Also, he believes the tautology ⊥⊃~B⊥, so he believes B⊥⊃B~B⊥. And since he believes B~B⊥⊃B⊥, he must believe B⊥≡B~B⊥.
Now for the solution of Problem 4. We have just shown that the reasoner believes B⊥≡B~B⊥, hence he believes ~B⊥≡~B~B⊥. And so he believes p≡~Bp, when p is now the proposition ~B⊥.
Translated into words, a reasoner of type G believes the proposition that he is consistent if and only if he doesn’t believe he is consistent. He also believes the proposition that he is inconsistent if and only if he believes that he is consistent.
6. A solution is to take p to be Bq. Let us verify that this works. The reasoner believes the tautology q⊃(Bq⊃q), and since he is regular, he then believes Bq⊃B(Bq⊃q). He also believes B(Bq⊃q)⊃Bq (since he is of type G), hence he must believe Bq≡B(Bq⊃q). Therefore he believes p≡B(p⊃q), where p is the proposition Bq.
7. We have shown that the reasoner believes Bq≡B(Bq⊃q). Then, by propositional logic, he will believe (Bq⊃q)≡B(Bq⊃q)⊃q. And so he will believe p≡(Bp⊃q), where p is now the proposition Bq⊃q. (Note: We have just duplicated the proof of Theorem R, Chapter 17, this page. According to Problem 6, the reasoner is strongly reflexive, and so by (a) of Theorem R, he is reflexive.)
8. Suppose he believes p≡B(p⊃q). Then by Lemma 3, Chapter 15, this page, he will believe p⊃Bq. He also believes the tautology q⊃(p⊃q), and being regular, he then believes Bq⊃B(p⊃q). Also, since he believes p≡B(p⊃q), he must believe B(p⊃q)⊃p. Since he believes Bq⊃B(p⊃q) and B(p⊃q)⊃p, he will believe Bq⊃p. And so he believes Bq⊃p and p⊃Bq (as we have shown), hence he must believe p≡Bq.
9. Suppose he believes p≡(Bp⊃q). Then he will believe p⊃(Bp⊃q), and also, by Lemma 1, Chapter 15, he will believe Bp⊃Bq. He believes the tautology q⊃(Bp⊃q), hence he will believe q⊃p (since he also believes p≡(Bp⊃q)). But he is regular, hence he will then believe Bq⊃Bp. Believing this, together with Bp⊃Bq, he will believe Bp≡Bq. Then, using propositional logic, he will believe (Bp⊃q)≡(Bq⊃q). Then, since he believes p≡(Bp⊃q), he will believe p≡(Bq⊃q).
10. The reasoner won’t have any idea whether the native is married or not, but he will believe that the native is a knight. We can see this as follows.
Let m be the proposition that the native is married. The native has asserted B(kvm), where k is the proposition that the native is a knight. Hence the reasoner will believe k≡B(kvm). Then he will certainly believe k⊃B(kvm). He also believes the tautology k⊃(kvm), hence he will believe Bk⊃B(kvm), since he is regular. He also believes B(kvm)⊃k, since he believes k≡B(k⊃m). Hence he will believe Bk⊃k. Then, being of type G, he will believe k.
11. Suppose he believes that he is stable. Then for every proposition p, he believes BBp⊃Bp, hence he believes BB⊥⊃B⊥. If he is modest, he will then believe B⊥ (because for any proposition q, a modest reasoner who believes Bq⊃q will believe q, and so this is true in particular if q is the proposition B⊥). Since he believes B⊥, then if he is stable, he will believe ⊥ and thus be inconsistent. This proves that if he believes BB⊥⊃B⊥, he cannot be modest, stable, and consistent. Therefore, if he is modest, stable, and consistent, he can never believe BB⊥⊃B⊥, and so he cannot know that he is stable with respect to ⊥.
* * *
†These are special cases of a remarkable fact discussed in the final chapter.
• Part VIII •
CAN’T DECIDE!
• 20 •
Forever Undecided
WE HAVE discussed Gödel’s Second Incompleteness Theorem (no consistent Gödelian system of type 4 can prove its own consistency), but we have not yet discussed his First Incompleteness Theorem. We now turn to this—first in the context of a reasoner on a knight-knave island.
We recall from the last chapter that a reasoner is called stable if for every proposition p, if he believes Bp, then he believes p.
AN INCOMPLETENESS PROBLEM
We shall say that a reasoner’s belief system is incomplete if there is at least one proposition p such that the reasoner will never believe p and never believe ~p (he will be forever undecided as to whether p is true or false).
The following problem is modeled after Gödel’s First Incompleteness Theorem.
1
A normal reasoner of type 1 comes to the Island of Knights and Knaves and believes the rules of the island. (Whether the rules really hold or not is immaterial.) He meets a native who says: “You will never believe that I am a knight.”
Prove that if the reasoner is both consistent and stable, then his belief system is incomplete. More specifically, find a proposition p such that the following two conditions hold:
(a) If the reasoner is consistent, then he will never believe p.
(b) If the reasoner is both consistent and stable, then he will never believe ~p.
2. A Dual of 1
Suppose that the native had instead said: “You will believe that I’m a knave.” Now find a proposition p such that the conclusions (a) and (b) of Problem I hold.
The same reasoning used in the solution of Problem 1, when applied to mathematical systems rather than reasoners, establishes the following form of Gödel’s First Incompleteness Theorem.
Theorem 1. Any consistent, normal, stable Gödelian system of type 1 must be incomplete. More specifically, if S is a normal system of type 1 and if p is a proposition such that p≡~Bp is provable in S, then if S is consistent, p is not provable in S, and if S is also stable, then ~p is also not provable in S.
A proposition p is said to be undecidable in a system S if neither it nor its negation ~p is provable in S. Thus Gödel’s First Incompleteness Theorem tells us that given any consistent, normal, stable Gödelian system S, there must always be at least one proposition p which, though expressible in the language of S, is not decidable in S—it can neither be proved nor disproved in S.
3. A Variant of 1
Suppose the native instead says: “You will believe that you will
never believe that I’m a knight.” Now find a proposition p satisfying conclusions (a) and (b) of Problem 1.
ω-CONSISTENCY
A natural number is by definition either 0 or a positive whole number 1, 2, 3,…. We will henceforth use the word “number” to mean “natural number.” Now, consider a property P of (natural) numbers. For any number n, we write P(n) to mean that n has the property P. For example, if P is the property of being an even number, then P(n) means that n is an even number, in which case P(0), P(2), P(4),…are all true propositions; P(1), P(3), P(5),…are all false propositions. On the other hand, if P is the property of being an odd number, then P(0), P(2), P(4)…are all false propositions, whereas P(1), P(3), P(5),…are true ones.
The standard symbol in logic for “there exists” is the symbol “,” which is technically known as the existential quantifier. For any property P of numbers, the proposition that there exists at least one number n having the property P is written: nP(n). Now, suppose we have a mathematical system and a property P such that the proposition nP(n) is provable in the system, yet for each particular n, the proposition ~P(n) is provable—that is, all the infinitely many propositions ~P(0), ~P(1), ~P(2),…, ~P(n)…are provable. This means that on the one hand, the system can prove the general statement that some number has the property P, yet each particular number can be proved not to have the property! Something is clearly wrong with the system, because if nP(n) is true, it is impossible that all the propositions ~P(0), ~P(1),…, ~P(n),…are also true. Yet, such a system is not necessarily inconsistent—one cannot necessarily derive a formal contradiction from all these propositions. There is, however, a name for such systems. They are called ω-inconsistent. (The symbol “ω” is sometimes used to mean the set of natural numbers.)
Let us consider the following analogous situation. Suppose someone gives you a check that says, “Payable at some bank.” Assuming that there are only finitely many banks in the world, you can in a finite length of time verify whether the check is good or bad; you simply try cashing it at every bank. If at least one bank accepts it, then you know that the check is good; if every bank rejects it, then you have positive proof that the check is bad. But now suppose you are living in a universe in which there are infinitely many banks, each bank being numbered with a natural number. There is Bank 0, Bank 1, Bank 2,…, and so forth. Let us also assume that you are immortal, so that you have infinitely many days ahead of you in which to try to cash the check. Now suppose that in fact no bank will ever cash the check. Then the check was in fact a bad one, yet at no finite time can you prove it! You might try the first hundred billion banks and they all refuse the check. You can’t offer this as evidence that the one who gave you the check is dishonest; he can always say, “Wait, don’t call me dishonest; you haven’t tried all the banks yet!” And so, you can never get an actual inconsistency; all you have is an ω-inconsistency (and even this you will never know in any finite length of time).
The notion of ω-inconsistency was once humorously characterized by the mathematician Paul Halmos, who defined an ω-inconsistent mother as one who says to her child: “There is something you can do, but you can’t do this and you can’t do that and you can’t do this other thing …” The child says: “But, Ma, isn’t there something I can do?” The mother replies: “Oh yes, but it’s not this, nor that, nor …”
A system is called ω-consistent if it is not ω-inconsistent. Thus for an ω-consistent system, if nP(n) is provable, then there is at least one number n such that the proposition ~P(n) is not provable. An inconsistent system of type 1 is also ω-inconsistent, because all propositions are provable in an inconsistent system of type 1. Stated otherwise, for systems of type 1, ω-consistency automatically implies (ordinary) consistency. When ω-consistency is being discussed, the term simple consistency is sometimes used to mean consistency (this in order to prevent any possibility of confusion). And so, in these terms, any ω-consistent system of type 1 is also simply consistent.
We now go back to the study of reasoners. In all the problems we have considered so far, the order in which the reasoner has believed various propositions has played no role. In the remaining problem of this chapter, order will play a key role.
The reasoner comes to the Island of Knights and Knaves on a certain day which we will call the 0th day. The next day is called the 1st day; the day after that is called the 2nd day; and so forth. For each natural number n, we have the nth day, and we assume the reasoner to be immortal and to have infinitely many days ahead of him. For every natural number n and any proposition p, we let Bnp be the proposition that the reasoner believes p sometime during the nth day. The proposition Bp is, as usual, the proposition that the reasoner believes p on some day or other, or, what is the same thing, nBnp (there exists some n such that the reasoner believes p on the nth day). We shall call the reasoner ω-inconsistent if there is at least one proposition p such that the reasoner (sometime or other) believes Bp, yet for each particular n, he (sometime or other) believes ~Bnp. The reasoner will be called ω-consistent if he is not ω-inconsistent.
We now consider a reasoner who satisfies the following three conditions.
Condition C1. He is of type 1.
Condition C2. For any natural number n and any proposition p: (a) if the reasoner believes p on the nth day, he will (sooner or later) believe Bnp; (b) if he doesn’t believe p on the nth day, he will (sooner or later) believe ~Bnp. (The idea is that the reasoner keeps track of what propositions he has believed and has not believed on all past days.)
Condition C3. For any n and any p, the reasoner believes the proposition Bnp⊃Bp (which, of course, is a true proposition).
The following problem comes very close to Gödel’s original version of his First Incompleteness Theorem.
4. (After Gödel)
The reasoner, satisfying the three conditions above, comes to the Island of Knights and Knaves and believes the rules of the island. He meets a native who says to him, “You will never believe that I am a knight.” Prove:
(a) If the reasoner is (simply) consistent, then he will never believe that the native is a knight.
(b) If the reasoner is ω-consistent, then he will never believe that the native is a knave.
Thus if the reasoner is ω-consistent (and hence also simply consistent), then he will remain forever undecided as to whether the native is a knight or a knave.
SOLUTIONS
1. The proposition p in question is simply the proposition k—the proposition that the native is a knight.
The native has asserted ~Bk, hence the reasoner will believe k≡~Bk.
(a) Suppose the reasoner believes k. Then, being normal, he will believe Bk. He will also believe ~Bk (since he believes k and believes k≡~Bk and he is of type 1), hence he will be inconsistent. Therefore, if he is consistent, he will never believe k.
(b) Since the reasoner is of type 1 and believes k≡~Bk, he also believes ~k≡Bk. Now, suppose he ever believes ~k. Then he will believe Bk. If he is stable, he will then believe k and hence become inconsistent (since he believes ~k). Therefore, if he is both stable and consistent, he will never believe ~k.
In summary, if he is both stable and consistent, he will never believe that the native is a knight and he will never believe that the native is a knave.
2. We see from the above solution that for any proposition p (it doesn’t have to be the particular proposition k), if a normal reasoner of type 1 believes p≡~Bp, then if he is consistent, he will never believe p, and if he is also stable, he will never believe ~p. Now, in the present problem, the reasoner believes k≡B~k. Therefore (being of type 1) he believes ~k≡~B~k, and so he believes p≡~Bp, where p is the proposition ~k. Therefore, if he is consistent, he will never believe that the native is a knave, and if he is also stable, then he will never believe that the native is a knight.
3. A proposition p that now works is ~Bk, as we will show.
The reasoner believes k≡B~Bk.
(a) Suppose he believes
~Bk. Then, being normal, he will believe B~Bk, and will then believe k (since he believes k≡B~Bk and is of type 1). Believing k and being normal, he will believe Bk. Thus he will believe both Bk and ~Bk, hence he will become inconsistent. Therefore, if he remains consistent, he will never believe Bk.
(b) Suppose he believes ~~Bk. Then he will believe Bk. If he is stable, he will then believe k. Next, he will believe B~Bk (since he believes k≡B~Bk and he is of type 1). Then (under the assumption that he is stable), he will believe ~Bk. Thus he will become inconsistent (since he believes ~~Bk). This proves that if the reasoner is both consistent and stable, he will never believe ~~Bk.
4. Having solved Problem 1, the easiest way to solve this problem is to show that any reasoner satisfying Conditions 1, 2, and 3 must be normal, and if he is ω-consistent, he must also be stable.
(a) To show he is normal. Suppose he believes p. Then for some n, he believes p on the nth day. Then by (a) at Condition 2, he will believe Bnp. He also believes Bnp⊃Bp (by Condition 3), hence being of type 1 (Condition 1), he will then believe Bp. Therefore he is normal.
(b) Now, suppose he is ω-consistent. We will show that he is stable. Suppose he believes Bp. If he never believes p, then for every number n, he fails to believe p on the nth day, and hence by (b) of Condition 2, for every n he will believe ~Bnp. But since he believes Bp, he will then be ω-inconsistent. Therefore, if he is ω-consistent and believes Bp, he must believe p on some day or other. This proves that if he is ω-consistent, he must be stable (assuming he satisfies Conditions 1, 2, 3—or even just (b) of Condition 2).
Therefore, by Problem 1, he will remain forever undecided.