Forever Undecided
Page 6
Question. Is this a genuine paradox?
Discussion. This problem bears a good deal of analysis! To begin with, the paradox (if it really is one) is what would be called a pragmatic paradox rather than a purely logical one, since it involves not only logical notions such as truth and falsity, but pragmatic notions such as knowing. To emphasize the pragmatic nature of the question, is it not possible that whether or not a paradox arises might depend on the person to whom the statement is made? It certainly is! As an extreme example, the native could surely say it to a dead person, and no paradox would arise. (He points to the corpse and says: “You will never know that I’m a knight.” Well, he is certainly right; the corpse will indeed never know that he is a knight, and so the native is in fact a knight—since what he said is true. But since the corpse will never know it, no contradiction arises.) To take a less extreme example, the native might say this to a person who is alive but deaf and hence does not hear the statement; again, no paradox would arise.
So we must assume that the visitor to the island was alive and heard the statement, but this is still not enough. We must assume a certain reasoning ability on the visitor’s part, because if the visitor has no reasoning ability, he would not go through the argument I have given. (The native would say: “You will never know that I’m a knight.” The visitor might then say: “That’s interesting,” walk away, and never think about the matter again. Hence no paradox would arise.) And so we must make explicit what reasoning abilities the logician has.
We will define an individual to be a reasoner of type I if he thoroughly understands propositional logic—that is, if the following two conditions hold:
(1) He believes all tautologies.
(2) For any propositions X and Y, if he believes X and believes X⊃Y, then he believes Y.
In the terminology of Chapter 8, the set of beliefs of a reasoner of type 1 is logically closed. It then follows by Principle L of Chapter 8, that given any finite set S of propositions that he believes, he must believe all logical consequences of S as well.
We shall now make the assumption that the visitor to the island is a reasoner of type 1. Of course this assumption is highly idealized, since there are infinitely many tautologies, hence our assumption implies something like immortality on the reasoner’s part. However, little things like that don’t bother us in the timeless realm of mathematics. We simply imagine the reasoner so programmed that (1) sooner or later he will believe every tautology; (2) if he ever believes p and ever believes p⊃q, then sooner or later he will believe q. It then follows by Principle L of Chapter 8 that given any finite set S of propositions, if the reasoner believes all the propositions in S, then for any proposition Y that is a logical consequence of S, the reasoner will sooner or later believe Y.
We still need further assumptions. For one thing we must assume a certain self-consciousness on the reasoner’s part; specifically, we must assume that if the reasoner ever knows something, then he knows that he knows it (otherwise he could never have said, “Now I know that he’s a knight,” and my argument wouldn’t go through).
Considering the problem with all these assumptions, does a genuine paradox now arise? Still not, for although I told you that the rules of the island hold (every inhabitant is either a knight or a knave; knights make only true statements; knaves make only false statements), we must make the additional assumption that the reasoner believes that the rules of the island hold. Indeed, it is perfectly reasonable that the reasoner might believe this at the outset, but after finding himself in a contradiction following the argument I gave, he would have rational grounds for doubting the rules of the island. (I imagine you and I would do just that after finding ourselves in such a predicament!) Well, to make the problem really interesting, let us make as our final assumption that the reasoner believes and continues to believe the rules of the island.
1.
Now we run into an interesting problem. Under the additional assumptions we have made, the reasoner’s argument that the native is a knight and that the native is a knave seems perfectly valid. Yet the native can’t be both a knight and a knave! So what is wrong with the reasoner’s argument?
Solution. I phrased the above problem in a very misleading way. (Occasionally I feel like being a bit sneaky!) It is not the reasoner’s argument that was wrong; it’s that the situation I described could never have arisen. If a reasoner of type 1 comes to a knight-knave island and believes the rules of the island (and hears whatever statements are made to him), then it is logically impossible that any native will say to him, “You will never know that I am a knight.”
To prove this, we don’t need one of the assumptions we have made—namely, that if the reasoner knows something, then he knows that he knows it. Even without this assumption, we can get a contradiction as follows: The reasoner reasons, “Suppose he is a knave. Then his statement is false, which means that I will know that he is a knight, which implies that he really is a knight. Therefore the assumption that he is a knave leads to a contradiction, so he must be a knight.”
Without going any further in the logician’s reasoning process, we can derive a contradiction. The logician has so far reasoned correctly and has come to the conclusion that the native is a knight. Since he has reasoned correctly, then the native really is a knight, and so the reasoner knows that the native is a knight. However, the native said he would never know that, hence the native must be a knave. Therefore the native is both a knight and a knave, which is a contradiction.
Instead of using the word “know,” we could just as well have said “correctly believe,” and our argument would still go through. We say that an individual correctly believes a proposition p if he believes p and p is true.
We have now proved Theorem I.
Theorem I. Given a knight-knave island and a reasoner of type 1 who believes the rules of the island (and who hears any statement addressed to him), it is logically impossible that any native can say to him, “You will never correctly believe that I am a knight.”
Discussion. Some critical readers might object to the proof I have given of the above theorem on the grounds that I have credited the reasoner with more abilities than I have explicitly ascribed to him —namely, that the reasoner makes assumptions and subsequently discharges them. In the specific case in hand, the reasoner started out: “Suppose he is a knave. Then—.” Well, this is really only a matter of convenience, not necessity. I could have given the reasoner’s argument in the following, more direct form: “If he is a knave, then his statement is false. If his statement is false, then I’ll correctly believe he is a knight. If I correctly believe he is a knight, then he is a knight. Putting these three facts together, if he is a knave, then he is a knight. From this last fact it logically follows that he is a knight.”
It is a common practice in logic to prove a proposition of the form p⊃q (if p then q) by supposing that p is true and then trying to derive q. If this can be done, then the proposition p⊃q is established. In other words, if assuming p as a premise leads to q as a conclusion, then the proposition p⊃q has been proved. (This technique is part of what is known as natural deduction.) The whole point is that anything that can be proved using this device can also be proved without it. (There is a well-known theorem in logic to this effect; it is called the deduction theorem.) And so we shall allow our “reasoners” to use natural deduction; a reasoner of type 1 who does this cannot prove any more facts than he can without using natural deduction, but the proofs using natural deduction are usually shorter and easier to follow. Therefore we shall continue to let our reasoners use natural deduction.
2. A Dual Problem
We continue to assume that the reasoner is of type 1, that he believes the rules of the island, and that he hears all remarks addressed to him.
Suppose the native, instead of saying, “You will never correctly believe I’m a knight,” says, “You will correctly believe I’m a knave.”
Do we then get a contradiction? (The reader
should try solving this before reading the solution.)
Solution. The reasoner reasons as follows: “Suppose he is a knight. Then his statement is true, which means that I will correctly believe he is a knave, which in turn implies that he is a knave. Hence the assumption that he is a knight leads to a contradiction, therefore he must be a knave.”
At this point the reasoner believes the native is a knave, and he has reasoned correctly, hence the native is a knave. On the other hand, since the reasoner correctly believes that the native is a knave, the native’s statement was true, which makes him a knight. So we do indeed get a contradiction.
SOME RELATED PROBLEMS
Let us now leave the Island of Knights and Knaves for a while and consider a problem related to the paradox of Chapter 3. A student asks his theology professor: “Does God really exist?” The professor gives the following curious answer: “God exists if and only if you don’t correctly believe that He does.”
3
Suppose that the student is a reasoner of type 1 and that the professor’s statement is true and that the student believes the statement. Do we then get a paradox?
Solution. Yes, we do! To begin with, even forgetting that the student is a reasoner of type 1 and that he believes the professor’s statement, it follows that God must exist, because if God didn’t exist, then the student would correctly believe that God exists, but no one can correctly believe a false proposition. Therefore God must really exist (assuming that the professor’s statement is true).
Now, the student, being a reasoner of type 1, knows propositional logic as well as you or I, hence he also is able to reason that if the professor’s statement is true, then God must exist. But he also believes the professor’s statement; therefore he must believe that God exists. And since we have proved that God exists (under the three assumptions of the problem), then the student correctly believes that God exists. But God exists if and only if the student doesn’t correctly believe that God exists. From this it follows that God doesn’t exist if and only if the student does correctly believe that God exists. (For any proposition p and q, the proposition p≡~q is logically equivalent to the proposition ~p≡q.) Since God doesn’t exist if and only if the student correctly believes that God exists, and the student does correctly believe that God exists, then it follows that God doesn’t exist. Thus the three assumptions of the problem lead to the paradox that God does exist and doesn’t exist.
Of course the same paradox would arise if the professor had instead said: “God exists if and only if you correctly believe that He doesn’t exist.” We leave the proof of this as an exercise for the reader.
It is now important for us to realize that the above paradox is essentially the same as that of Problem 1 concerning the knight-knave island, although they may appear different. The seeming differences are: (1) In the above paradox, the professor made an “if and only if” statement, whereas in Problem 1, the native did not; he said outright that the reasoner would never correctly believe that the native is a knight. (2) In the above paradox, the student believes the professor, whereas in Problem 1, the reasoner has no initial belief that the native is a knight. However, these two differences in a sense cancel each other out, as we will now see. The key to this is the translation device in Chapter 7.
In virtually all the problems that follow, we will be dealing with only two individuals—the native of the island who makes the statement, and the reasoner who hears the statement. We will consistently use the letter k for the proposition that the native in question is a knight. Then, as we saw in Chapter 7, whenever the native asserts a proposition q, the proposition k≡q is true. Now, the reasoner believes the rules of the island (he believes that knights make true statements and knaves make false ones), and we are assuming that he hears any statement made to him. Therefore, whenever the native asserts a proposition q to the reasoner, the reasoner believes the proposition k≡q. Indeed, from now on, when we say that the rules of the island hold, we need mean no more than that for any proposition q, if the native asserts q, then the proposition k≡q is true. And when we say that the reasoner believes the rules of the island (and hears all statements made to him), we need mean no more than that for any proposition q, if the native asserts q to the reasoner, then the reasoner believes the proposition k≡q.
For any proposition p, we let Bp be the proposition that the reasoner believes (or will believe) p. And we let Cp be the proposition p&Bp. We read Cp as “The reasoner correctly believes p.”
Now, in Problem 1, the native asserted the proposition ~Ck (“You will never correctly believe that I am a knight”). Since the rules of the island hold, then the proposition k≡~Ck is true. Since the reasoner believes the rules of the island, then he believes the proposition k≡~Ck. These two facts turn out to be logically incompatible, hence a paradox arises.
In Problem 3, let g be the proposition that God exists. The professor asserted outright the proposition g≡~Cg. Under the assumption that the professor makes only true statements, the proposition g≡~Cg must be true. Since the student believed the professor, then he believed the proposition g≡~Cg. Again, the truth of g≡~Cg turned out to be logically incompatible with the student believing g≡~Cg (since the student is a reasoner of type 1).
We now see exactly what the two paradoxes have in common; in both cases we have a proposition p (which is k, for Problem 1, and g for Problem 3) such that p≡~Cp is both true and believed by the reasoner—in other words, it is correctly believed by the reasoner, and this is logically impossible if the reasoner is of type 1. Thus both paradoxes (or rather their resolutions that the given conditions are logically incompatible) are special cases of the following theorem.
Theorem A. There is no proposition p such that a reasoner of type 1 can correctly believe the proposition p≡~Cp. In other words, there is no proposition such that a reasoner of type 1 can correctly believe: “The proposition is true if and only if I don’t correctly believe that it is true.”
The proof of Theorem A is little more than a repetition of the two special cases already considered, but it may help to consider it in a more general setting and to point out some of its interesting features.
To begin with, for any propositions p and q, the proposition (p≡~(p&q))≡⊃p is a tautology (as the reader can verify). In particular, the proposition (p≡~(p&Bp))⊃p is a tautology. We are letting Cp be the proposition p&Bp, and so (p≡~Cp)⊃p is a tautology. Suppose now that a reasoner of type 1 correctly believes p≡~Cp, we then get the following contradiction: Since the reasoner correctly believes p≡~Cp, then p≡~Cp must be true. Also (p≡~Cp)⊃p is true (it is a tautology), and so p must be true. Now since the reasoner is of type 1, he believes the tautology (p≡~Cp)⊃p and he also believes p≡~Cp (by assumption), and since he is of type 1, he will then believe p. And so p is true, and he believes p, so he correctly believes p. Thus Cp is true, hence ~Cp is false. But since p is true and ~Cp is false, it cannot be that p≡~Cp (since a true proposition cannot be equivalent to a false proposition), and so we get a contradiction from the assumption that a reasoner of type 1 correctly believes p≡~Cp.
There is also the following “dual” of Theorem A whose proof we leave to the reader.
Theorem A°. There is no proposition p such that a reasoner of type 1 can correctly believe p≡C(~p).
Exercise 1. Prove Theorem A°.
Exercise 2. Suppose we have a perfectly arbitrary operation B which assigns to every proposition p a certain proposition Bp. (What the proposition Bp is needn’t be specified; in this chapter, we have let Bp be the proposition that the reasoner believes p; in a later chapter, in which we will be discussing mathematical systems rather than reasoners, Bp will be the proposition that p is provable in the system. But for now, Bp will be unspecified.) We let Cp be the proposition (p&Bp).
(a) Show that one can derive a logical contradiction from the following assumptions:
(i) All propositions of the form BX, where X is a tautology.
(ii
) All propositions of the form (BX&B(X⊃Y))⊃BY.
(iii) Some proposition of the form C(p≡~Cp).
(b) Show that we also get a logical contradiction if we replace (iii) with “Some proposition of the form C(p≡C~p).”
(c) Why is Theorem A a special case of (a) above? Why is Theorem A° a special case of (b)?
• 10 •
The Problem Deepens
CONCEITED REASONERS
We are back to the Island of Knights and Knaves. Suppose, now, that the native, instead of saying: “You will never correctly believe I’m a knight,” makes the following statement: “You will never believe that I am a knight.”
The native has left out the word “correctly,” and as a result things will get far more interesting. We continue to assume that the one addressed is a reasoner of type 1 and that he believes the rules of the island (and also that he has heard the statement) and that the rules of the island really hold. And now we shall make the further assumption that the reasoner is completely accurate in his judgments; he doesn’t believe any proposition that is false. Do we still get a paradox?
Well, suppose the native is a knave. Then his statement is false, which means that the reasoner will believe he is a knight. And since the reasoner is accurate in his judgments, then the native really is a knight. Thus the assumption that the native is a knave leads to a contradiction, so the native must be a knight.
Now, the reasoner is of type 1 and knows as much logic as you and I. What is to prevent him from going through the same reasoning process that we just went through and coming to the same conclusion—namely, that the native must be a knight? Therefore the reasoner will believe that the native is a knight, which makes the native’s statement false, hence the native must be a knave. But we have already proved that the native is a knight. Paradox!