Forever Undecided

by Raymond M. Smullyan

  Note: Not all liar–truth teller problems can be solved by the translation devices in this chapter. These devices work fine for problems in which we are told what the speakers say and must then deduce certain facts about them. But for the more difficult type of puzzles in which we are to design a question or a statement to do a certain job, more thought is needed. There are other systematic devices that help in many cases, but this is a topic outside the main line of thought in this book.

  ANSWERS TO EXERCISES

  1. All three are knaves.

  2. The proposition is a tautology.

  3. We leave this to the reader.

  4. P3 is a knight.

  5. Oona is not on the island (and both natives are knights).

  6. Oona is on the island (and both natives are knights).

  7. Oona is on the island (and A is a knight; B is a knave).

  • 8 •

  Logical Closure and Consistency

  INTERDEFINABILITY OF THE LOGICAL CONNECTIVES

  We are now familiar with the five basic logical connectives: ~, &, v, ⊃, and ≡. We could have started with fewer and defined the others in terms of them. This can be done in several ways, some of which will be illustrated in the following puzzles.

  1

  Suppose an intelligent man from Mars comes down to Earth and wants to learn our logic. He claims to understand the words “not” and “and,” but he does not know the meaning of the word “or.” How could we explain it to him, using only the notions of not and and?

  Let me rephrase the problem. Given any proposition p, he knows the meaning of ~p, and given any propositions p and q, he knows the meaning of p&q. What the Martian is looking for is a way of writing down an expression or formula in the letters p and q, using only the logical connectives ~ and &, such that the expression is logically equivalent to the expression pvq. How can this be done?

  2

  Now suppose a lady from the planet Venus comes here and tells us that she understands the meanings of ~ and v, but wants an explanation of &. How can we define & in terms of ~ and v? (That is, what expression in terms of p, q, ~, and v is logically equivalent to p&q?)

  3

  This time a being from Jupiter comes down who understands ~, &, and v, and wants us to define ⊃ in terms of these. How can this be done?

  4

  Next comes a being from Saturn who strangely enough understands ~ and ⊃, but does not understand either & or v. How can we explain & and v to him?

  5

  Now comes a being from Uranus who understands only the connective ⊃. It is not then possible to explain to him what & means, nor what ~ means, but it is possible to define v in terms of just the one connective ⊃. How can this be done? (The solution is not at all obvious. That it is possible to do it is part of the folklore of mathematical logic, but I have been unable to find out the logician who discovered it.)

  6

  It is obvious that ≡ can be defined in terms of ~, &, and v. Show two different ways of doing this.

  7. A Special Problem

  Suppose a being from outer space understands the meanings of ⊃ and ≡. It will not then be possible to explain to him or her the meaning of ~, but it will be possible to explain &. How can this be done? (This discovery is mine, as far as I know.)

  Two Other Connectives. We now see that the logical connectives ~, &, v, ⊃, and ≡ can all be defined from just the two connectives ~ and &, or alternatively from ~ and v, or alternatively from ~ and ⊃. Is there just one logical connective from which all five connectives can be defined? This problem was solved in 1913 by the logician Henry M. Sheffer. He defined p|q to mean that p and q are not both true. The symbol “|” is known as the “Sheffer stroke”; we can read p|q as “p and q are incompatible” (at least one is false). He showed that ~, &, v, ⊃, ≡ are all definable from the stroke symbol. Another logical connective that gives all other connectives is ; this symbol is called the symbol for joint denial. We read pq as “p and q are both false,” or “neither p nor q is true.”

  8

  How can ~, &, v, ⊃, ≡ all be defined from Sheffer’s stroke? How can they all be defined from joint denial?

  The Logical Constant ⊥. A proposition X is called logically contradictory or logically false if its negation ~X is a tautology. For example, for any proposition p, the proposition (p&~p) is logically false. So is p≡~p.

  We shall use the now standard symbol “⊥” as representing any one particular logical falsehood (which one doesn’t matter). This can be regarded as fixed for the remainder of this book—and any other books you might read in which this symbol appears. (The symbol “⊥” is pronounced “eet”; it is the symbol “T” written upside down.) For any proposition p, the proposition ⊥⊃p is a tautology (because ⊥ is logically false, so ⊥⊃p is true, regardless of whether p is true or false). Thus every proposition is a logical consequence of ⊥. (It’s a good thing that ⊥ itself isn’t true, for if it were, everything would be true and the whole world would explode!)

  Many modern formulations of propositional logic build their entire theory on just ⊃ and ⊥, because all the other logical connectives can be defined from these two (see Problem 9 below). This is the course we will adopt because it fits in best with the problems of this book. One then defines T as ⊥⊃⊥. We refer to ⊥ as logical falsehood and T as logical truth (obviously T is a tautology).

  9

  How does one define all the logical connectives from ⊃ and ⊥?

  LOGICAL CLOSURE

  A Logically Qualified Machine. To illustrate the important notion of logical closure, let us imagine a computing machine programmed to prove various propositions. Whenever the machine proves a proposition, it prints it out (more precisely, it prints out a sentence that expresses the proposition). The machine, if left to itself, will run on forever.

  We will call the machine logically qualified if it satisfies the following two conditions:

  (1) Every tautology will be proved by the machine sooner or later.

  (2) For any proposition p and q, if the machine ever proves p and proves p⊃q, then it will sooner or later prove q. (We might think of the machine as inferring q from the two propositions p and p⊃q. Of course the inference is valid.)

  Logically qualified machines have one very important property, of which the following problem illustrates some examples.

  10

  Suppose a machine is logically qualified.

  (a) If the machine proves p, will it necessarily prove ~~p?

  (b) If the machine proves p and proves q, will it necessarily prove the single proposition p&q?

  Logical Closure. There is an old rule in logic called modus ponens, which is that having proved p and having proved p⊃q, one can then infer q. A set C of propositions is said to be closed under modus ponens if for any propositions p and q, if p and p⊃q are both in the set C, so is the proposition q.

  We can now define a set C of propositions to be logically closed if the following two conditions hold:

  Condition 1. C contains all tautologies.

  Condition 2. For any propositions p and q, if p and p⊃q are both in C, so is q.

  Thus a logically closed set is a set that contains all tautologies and that is closed under modus ponens. (The reason for the term logically closed will soon be apparent.)

  To say that a machine is logically qualified is tantamount to saying that the set C of all propositions that the machine can prove is a logically closed set. However, logically closed sets also arise in situations in which no machines are involved. For example, we will be considering mathematical systems in which the set of all propositions provable in the system is a logically closed set. Also, a good part of this book will be dealing with logicians whose set of beliefs is a logically closed set.

  Logical Consequence. We have defined Y to be a logical consequence of X if the proposition X⊃Y is a tautology. We shall say that Y is a logical consequence of two propositions X1 and X2 if it is a consequence of th
e proposition X1&X2—in other words, if (X1&X2)⊃Y is a tautology, or, what is the same thing, if the proposition X1⊃(X2⊃Y) is a tautology. We define Y to be a logical consequence of X1, X2, and X3 if ((X1&X2)&X3)⊃Y is a tautology—or, what is the same thing, if X1⊃(X2⊃(X3⊃Y)) is a tautology. More generally, for any finite set of propositions X1,…, Xn, we can define Y to be a logical consequence of this set if the proposition (X1&…&Xn)⊃Y is a tautology.

  The importance of logically closed sets is that they enjoy the following property:

  Principle L (the Logical Closure Principle). If C is logically closed, then for any n proposition X1,…, Xn in C, all logical consequences of these n propositions are also in C.

  Discussion. Returning to our example of a logically qualified machine, Principle L tells us that if the machine should ever prove a proposition p, then it will sooner or later prove all logical consequences of p; if the machine should ever prove two propositions p and q, it will sooner or later prove all logical consequences of p and q—and so forth, for any finite number of propositions.

  The same applies to logicians whose set of beliefs is logically closed. If a logician ever believes p, he will sooner or later believe all logical consequences of p; if he should ever believe p and q, he will believe all logical consequences of p and q; and so on.

  11

  Why is Principle L correct?

  12

  Another important property of logically closed sets is that if C is logically closed and contains some proposition p and its negation ~p, then every proposition must be in C.

  Why is this so?

  CONSISTENCY

  The last problem brings us to the important notion of consistency. A logically closed set C will be called inconsistent if it contains ⊥ and consistent if it doesn’t contain ⊥.

  The following is another important property of logically closed sets.

  Principle C. Suppose C is logically closed. Then the following three conditions are all equivalent (any one of them implies the other two):

  (1) C is inconsistent (C contains ⊥).

  (2) C contains all propositions.

  (3) C contains some proposition p and its negation ~p.

  Note: Given a set S of propositions that is not logically closed, S is said to be inconsistent if ⊥ is a logical consequence of some finite subset X1,…, Xn of propositions in S. (This is, incidentally, equivalent to saying that every proposition is a logical consequence of some finite subset of S.) However, we will be dealing almost exclusively with sets that are logically closed.

  13

  Prove Principle C.

  SOLUTIONS

  1. To say that at least one of the propositions p and q is true is to say that it is not the case that p and q are both false; in other words, it is not the case that ~p and ~q are both true. And so pvq is equivalent to the proposition ~(~p&~q). Since the Martian understands ~ and &, then he will understand ~(~p&~q). And so you can say to the Martian: “When I say p or q, all I mean is that it is not the case that not p and not q.”

  2. To say that p and q are both true is equivalent to saying that it is not the case that either p or q is false—in other words, it is not the case that either ~p or ~q is true. And so p&q is logically equivalent to the proposition ~(~pv~q).

  3. This can be done in several ways: On the one hand, p⊃q is logically equivalent to ~pv(p&q). It is also equivalent to ~(p&~q) (it is not the case that p is true and q is false), and to ~pvq.

  4. pvq is logically equivalent to ~p⊃q. And so we can get v in terms of ~ and ⊃. Once we have ~ and v, we can get & by the solution to Problem 2 above. More directly, p&q is equivalent to ~(p⊃~q), as the reader can verify.

  5. This is tricky indeed! The proposition pvq happens to be logically equivalent to (p⊃q)⊃q, as the reader can verify by a truth table.

  6. p≡q is obviously equivalent to (p⊃q)&(q⊃p). It is also equivalent to (p&q)v(~p&~q).

  7. We have already solved this in the last chapter, in connection with the third knight-knave problem, this page; we showed that p&q is logically equivalent to p≡(p⊃q).

  8. Given Sheffer’s stroke, we can get the other connectives as follows: First of all, ~p is logically equivalent to p|p. (The proposition p|p is that at least one of the propositions p or p is false, but since the two propositions p and p are the same, this simply says that p is false.) Now that we have ~, we can define pvq to be ~(p|q). (Since p|q is the proposition that at least one of p or q is false, its negation ~(p|q) is equivalent to saying that they are not both false—i.e., that at least one is true.) Once we have ~ and v, we can get & (by Problem 2), then ⊃ and ≡ (by Problems 3 and 6). We thus get ~, &, v, ⊃, and ≡ from Sheffer’s stroke.

  If we start with joint denial , instead of Sheffer’s stroke, we proceed as follows: We first take ~p to be pp. Then we take p&q to be ~(pq). Having gotten ~ and &, we can then get all the rest in the manner we have seen.

  9. The proposition ~p is logically equivalent to p⊃⊥, and so we can get ~ from ⊃ and ⊥. Once we have ~ and ⊃, we can get v and & (by Problem 4). Then we can get ≡ from ⊃ and &.

  10. (a) Suppose the machine proves p. It will also prove p⊃~~p (since this is a tautology), hence it will print ~~p (by the second condition defining logical qualification).

  (b) Suppose the machine proves p and proves q. Now, the proposition p⊃(q⊃(p&q)) is a tautology, hence the machine will prove it. Once the machine has proved p and p⊃(q⊃(p&q)), it must prove q⊃(p&q). Once the machine has proved this, then, since it proves q, it must prove p&q.

  (Actually this problem is but a special case of the next, as the reader will see.)

  11. Let us first consider the case n = 1: Suppose X1 is in C, and Y is a logical consequence of X1. Then X1⊃Y is a tautology, hence is in C (by Condition 1). Since X1 and X1⊃Y are both in C, so is Y (by Condition 2).

  Now let us consider the case n = 2: Suppose X1 and X2 are both in C, and Y is a logical consequence of X1 and X2. Then (X1&X2)⊃Y is a tautology, hence X1⊃(X2⊃Y) is a tautology (as the reader can verify) and is therefore in C. Since X1 and X1⊃(X2⊃Y) are both in C, so is X2⊃Y (Condition 2). Since X2 and X2⊃Y are in C, so is Y (again by Condition 2).

  For the case n = 3, suppose Y is a logical consequence of X1, X2, and X3. Then X1⊃(X2⊃(X3⊃Y)) is a tautology—it is logically equivalent to (X1&X2&X3)⊃Y. Then using Condition 2 three times, we successively get X2⊃(X3⊃Y) in C, (X3⊃Y) in C, and finally Y in C.

  It should be obvious how this proof generalizes for any positive whole number n.

  Note: We have remarked that Problem 10 is but a special case of the present problem. The reason, of course, is that ~~p is a logical consequence of p, hence any logically closed set containing p must also contain ~~p. Also, p&q is a logical consequence of the two propositions p and q, so any logically closed set containing both p and q must also contain p&q.

  12. Suppose that p and its negation ~p are both in C and that C is logically closed. Let q be any proposition whatsoever. The proposition (p&~p)⊃q is a tautology (as the reader can check by a truth table, or more simply by observing that since p&~p must be false, then (p&~p)⊃q must be true). And so q is a logical consequence of the true propositions p and ~p. Then according to Principle L, the proposition q must also be in C. And so every proposition q is in C.

  13. We will show that the three conditions are all equivalent by showing that (1) implies (2), which in turn implies (3), which in turn implies (1).

  Suppose (1). Since every proposition is a logical consequence of ⊥ and ⊥ is in C, then every proposition is in C (by Principle L). Thus (2) holds.

  It is completely obvious that (2) implies (3), because if all propositions are in C, then for any proposition p, both p and ~p are in C.

  Now suppose that (3) holds—i.e., that for some p, both p and ~p are in C. Since ⊥ is a logical consequence of p and ~p, then ⊥ must be in C (by Principle L)—i.e., C must be inconsistent.

  • Part IV •

  LET’S
BE CAREFUL!

  • 9 •

  Paradoxical?

  WE NOW have the background to embark on our journey to Gödel’s consistency predicament, which we will reach in Chapter 12, encountering many interesting problems along the way. Let us start with a problem closely related to one of the variants of the Surprise Examination Paradox in Chapter 2.

  We are back on the Island of Knights and Knaves, where the following three propositions hold: (1) knights make only true statements; (2) knaves make only false ones; (3) every inhabitant is either a knight or a knave. These three propositions will be collectively referred to as the “rules of the island.”

  We recall that no inhabitant can claim that he is not a knight, since no knight would make the false statement that he isn’t a knight and no knave would make the true statement that he isn’t a knight.

  Now suppose a logician visits the island and meets a native who makes the following statement to him: “You will never know that I am a knight.”

  Do we get a paradox? Let us see. The logician starts reasoning as follows: “Suppose he is a knave. Then his statement is false, which means that at some time I will know that he is a knight, but I can’t know that he is a knight unless he really is one. So, if he is a knave, it follows that he must be a knight, which is a contradiction. Therefore he can’t be a knave; he must be a knight.”

  So far, so good—there is as yet no contradiction. But then he continues reasoning: “Now I know that he is a knight, although he said that I never would. Hence his statement was false, which means that he must be a knave. Paradox!”