Forever Undecided
Page 15
• 21 •
More Indecisions!
ROSSER-TYPE REASONERS
Gödel proved a whole family of mathematical systems to be incomplete under the assumption that they were ω-consistent. J. Barkley Rosser subsequently discovered an ingenious method of showing these systems to be incomplete under the weaker assumption that they were simply consistent. The undecidable sentence constructed by Rosser is more complicated than Gödel’s, but its undecidability can be established under the mere assumption of simple consistency.
Let us return to the reasoners on a knight-knave island where the order in which the reasoner believes various propositions makes a difference. For any propositions p and q, we will say that the reasoner believes p before he believes q if there is some day on which he believes p and has not yet believed q. If the reasoner never believes q, but believes p (on some day or other), then we take it as true that he believes p before he believes q. (In other words, he doesn’t have to ever believe q in order to believe p before he believes q.) We let Bp < Bq be the proposition that the reasoner believes p before he believes q. If Bp < Bq is true, then Bq < Bp is obviously false.
We shall now define a Rosser-type reasoner as a reasoner of type 1 such that the following condition holds.
Condition R. For any propositions p and q, if the reasoner believes p on some day on which he has not yet believed q, then he will (sooner or later) believe Bp < Bq and ~(Bq < Bp).
The idea behind Condition R is that the reasoner has a perfect memory for what he has and has not believed on all past days. If he believes p before he believes q, then on the first day that he believes p, he hasn’t believed q yet (and perhaps never will, or then again he may sometime in the future), and so on any subsequent day he will remember that on the first day on which he believed p, he hadn’t yet believed q, and so he will believe Bp < Bq and ~(Bq < Bp).
1
A Rosser-type reasoner 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 I’m a knight before you believe I’m a knave.” (Rendered symbolically, the native is asserting the proposition ~(Bk < B~k).)
Prove that if the reasoner is simply consistent, then he must remain forever undecided as to whether the native is a knight or a knave.
2
Suppose the native instead said: “You will believe I’m a knave before you believe I’m a knight.” Does the same conclusion follow?
Discussion. The provable propositions of mathematical systems are provable at various stages. We might think of a mathematical system as a computer programmed to prove various propositions sequentially. We say that p is provable before p (in a given mathematical system) if p is proved at some stage at which q has not yet been proved (q might or might not be proved at some later stage). For any propositions p and q expressible in the system, the proposition Bp < Bq (p is provable before q) is also expressible in systems of the type considered by Gödel, and Rosser showed that if p is provable before q, then the proposition Bp < Bq and the proposition ~(Bq < Bp) are both provable in the system. Rosser also found a proposition p such that p≡~(Bp < B~p) is provable in the system. (Such a proposition p corresponds to the native of Problem 1 who says: “You will never believe I’m a knight before you believe I’m a knave.”) Then, by the argument of the solution of Problem 1, if p is provable, then the system is inconsistent, and if ~p is provable, then the system is again inconsistent. And so, if the system is consistent, the proposition p is undecidable in the system.
Gödel’s sentence can be paraphrased: “I am not provable at any stage.” Rosser’s more elaborate sentence can be paraphrased: “I cannot be proved at any stage, unless my negation has been proved earlier.” Gödel’s sentence, though simpler, requires the assumption of ω-consistency to make the argument go through. Rosser’s sentence, though more complicated, works under the weaker assumption of simple consistency.
A SIMPLER INCOMPLETENESS PROBLEM
We have now discussed two incompleteness proofs: Gödel’s and Rosser’s. There is another one simpler than either, which combines Gödel’s method with the use of the notion of truth—a notion introduced later by the logician Alfred Tarski. It has always been a puzzle to me why this simple proof—so well known to the experts—is so neglected in elementary textbooks.
In the problem that follows, the order in which the reasoner believes various propositions makes absolutely no difference.
3
Suppose we have a reasoner—call him Paul—who is always accurate in his beliefs (he never believes any false propositions). He doesn’t have to be of type 1, or normal, nor is it necessary that he actually visit the Island of Knights and Knaves. All we need to know about him is that he is accurate.
One day a native says about him: “Paul will never believe that I’m a knight.” It then logically follows that Paul’s belief system must be incomplete. Why is this?
4
Suppose the native instead says: “Paul will one day believe that I’m a knave.” Would it still follow that Paul’s belief system is incomplete?
A MORE SERIOUS PREDICAMENT
5
Let us now consider a consistent stable reasoner of type G. There is one very important question about which he must remain forever undecided—namely, the question of his own consistency. He can never decide whether or not he is consistent. Why is this?
A Question. Of course, the above result holds good replacing “reasoner” with “system”: A consistent stable system of type G can never prove its own consistency, nor its own inconsistency.
However, an important question arises: How do we know if there are any consistent stable systems of type G? Isn’t it possible that the very notion of a consistent stable system of type G conceals some subtle contradiction?
This matter will be fully resolved before we come to the end of this book.
SOLUTIONS
1. Since the native asserted ~(Bk < B~k), the reasoner will believe k≡~(Bk < B~k). Suppose that the reasoner is (simply) consistent. We are to show that he will never believe k and never believe ~k.
(a) Suppose he ever believes k. Since he is consistent, he will never believe ~k, hence he will believe k before he believes ~k. Hence he will believe Bk < B~k (by Condition R). But he also believes k≡~(Bk < B~k), hence he will believe ~k, and believing k, he will be inconsistent! So if he is consistent, he can never believe k.
(b) Suppose he ever believes ~k. Being consistent, he will never believe k, hence he will believe ~k before he believes k, hence by Condition R he will believe ~(Bk < B~k). But he believes k≡~(Bk < B~k), so he will then believe k and be inconsistent. And so, if he is consistent, he cannot believe ~k either.
2. The answer is yes. We leave the proof to the reader.
3. If Paul ever believes that the native is a knight, this will falsify what the native said, thus making the native a knave, and hence making Paul inaccurate in believing that the native is a knight. But we are given that Paul is accurate, hence he won’t ever believe that the native is a knight. Hence what the native said is true, so the native is in fact a knight. Then, since Paul is accurate, he will never have the wrong belief that the native is a knave. And so Paul will never know whether the native is a knight or a knave.
Discussion. The mathematical content of the above puzzle is this: In the systems investigated by Gödel, we have not only certain propositions called provable propositions, but also a larger class of propositions called the true propositions of the system. The class of true propositions of the system is faithful to the truth table rules for the logical connectives; also, for any proposition p of the system, the proposition Bp is a true proposition of the system if and only if p is a provable proposition of the system. Now, Gödel found a remarkable proposition g such that the proposition g≡~Bg was a true proposition of the system (in fact, even provable in the system, but this stronger fact is not needed for the present argument). If g were false, Bg would be true, hen
ce g would be provable, hence true, and we would have a contradiction. Therefore g is true, hence ~Bg is true, hence g is not provable in the system. So g is true but not provable in the system. Since g is true, ~g is false, hence also not provable in the system (since all the provable propositions are true). And so g is undecidable in the system.
4. The answer is yes. We leave the proof to the reader.
5. We showed in Chapter 18 that every reasoner of type G is modest, and we showed that no consistent modest reasoner of type 4 (or even type 1) can believe that he is consistent. Therefore no consistent reasoner of type G can know that he is consistent.
For the other half, any stable reasoner who believes that he is inconsistent really is inconsistent, because if he believes that he is inconsistent, then he believes B⊥, and if he is also stable, he believes ⊥, and is hence inconsistent.
Therefore, no stable consistent reasoner of type G can ever believe he is consistent or ever believe he is inconsistent. He is doomed to eternal uncertainty on this issue.
• Part IX •
POSSIBLE WORLDS
• 22 •
It Ain’t Necessarily So!
MUCH OF what we have been doing in this book ties in closely with the field known as modal logic. The amazing thing about this field is that it arose out of purely philosophical considerations, but the axiom systems that have come out of it have recently turned out to have an entirely different interpretation, which is of mathematical interest and which figures prominently today in proof theory, computer science, and artificial intelligence. We will have more to say about the mathematical interpretation in later chapters.
The fundamental concept of modal logic is that of a proposition being necessarily true rather than just true as a matter of fact. Many times we say: “Yes, it’s true that it turned out this way, but it didn’t really have to. It could have turned out otherwise.” At other times we say: “Oh, it had to turn out this way. It couldn’t have been otherwise.” And so we often make a distinction between something just happening to be true, and something being necessarily true. As an example, it happens to be a matter of fact that there are exactly nine planets in our solar system, but it is perfectly conceivable that things could have been otherwise and that there could have been more or less than nine planets. On the other hand, a proposition such as two plus two is four is not only true, but necessarily true. In no possible circumstances could it be true that two plus two is not four.
Rather than go further at this point into the philosophy of necessary truth, we will turn to some logic puzzles illustrative of what is known as Kripke semantics, which we will discuss in the next chapter. In preparation for this, let us establish our notation.
Following the modal logician C. I. Lewis, we shall use the letter N for necessarily true. (The more usual symbol today is .) Thus for any proposition p, we read Np as “p is necessarily true.” And so our notation will be like that of the last several chapters, except that we will be using the letter N instead of B. The definition of a set of propositions being of type 1, 2, 3, 4, or G is the same as before, the only difference again being that we use N in place of B.
1. A Universe of Reasoners
We now consider an entire universe of reasoners—we will call this universe U1. Given any proposition p, each reasoner either believes p or disbelieves p, but not both. (Disbelieving a proposition means believing it to be false.) Each reasoner disbelieves ⊥ and his beliefs follow the truth table rules for the logical connectives. For example, he believes p⊃q if and only if he either disbelieves p or believes q (or both). It follows from this that each reasoner believes all tautologies. Also, if a reasoner believes p and believes p⊃q, he must believe q (for if he disbelieves q, he would believe p and disbelieve q, hence would disbelieve p⊃q instead of believing p⊃q). Therefore each reasoner is of type 1. We are also given that each reasoner knows what every other reasoner believes.
Now comes the curious thing. For some reason or other, each reasoner has complete confidence in the judgment of his or her parents, and so for any proposition p, a reasoner believes that p is necessarily true if and only if his or her parents both believe p! This is known as the “fundamental rule” of the universe. It is so important that we will formally record it.
Fundamental Rule of U1. A reasoner believes Np if and only if his parents both believe p.
Remarks. There is a rumor that a song writer from our universe—an American composer, in fact—upon visiting the universe U1 and hearing the reason why the inhabitants believed a proposition to be necessarily true, shook his head skeptically, and said: “It ain’t necessarily so!” But I can’t vouch for this—I heard it only as a rumor.
A proposition p is called established (for the universe U1) if all the inhabitants believe it.
Obviously all tautologies are established, but the set of established propositions goes beyond tautologies. In fact, the set of established propositions must be of type 3—that is:
(1a) All tautologies are established.
(1b) If p and p⊃q are established, so is q.
(2) (Np&N(p⊃q))⊃Nq is established.
(3) If p is established, so is Np.
Prove that the set of established propositions is of type 3.
2. A Second Universe
We now visit another universe, which we will call U2. The conditions defining this universe are like those of U1, with one important difference. In this universe, a reasoner believes that p is necessarily true if and only if all of his ancestors believe p. (To simplify matters, we shall assume that all the inhabitants are immortal, and so all the ancestors of any person are still living.)
Let us record this fundamental fact.
Fact 2. In the universe U2, a reasoner x believes Np if and only if all ancestors of x believe p.
Now things get more interesting.
Prove that the set of established propositions of the universe U2 must be of type 4.
3. A Third Universe
So far, we have left open the question of whether or not the universe had a beginning in time. Well, we now consider a third universe U3 satisfying all the conditions that we have given for U2, plus the condition that it did have a beginning in time. This means that for each individual x, if we take an ancestor x′ of x, then an ancestor x″ of x′, and keep going backwards in this manner, we must sooner or later come to an ancestor who himself has no ancestors—and hence no parents. (To answer the question of how these parentless individuals came into existence goes beyond the scope of this book. The interested reader should consult either a book on evolution or a book on creationism, depending on his or her scientific or theological interests.)
As the reader may have anticipated, we aim to show that the established propositions of this universe form a class of type G. But before that, we must clarify a point for the reader unfamiliar with the logic of all and some.
Suppose someone says about a certain club, “All Frenchmen in this club wear berets,” and it turns out that there are no Frenchmen in the club. Should the statement then be regarded as false, true, or inapplicable? Those unfamiliar with formal logic may well have different opinions on the matter, but the convention adopted in logic, mathematics, and the natural sciences is that any statement of the form “All A’s are B’s” is to be regarded as false only if there is at least one A who is not a B. And so the only way the statement, “All Frenchmen of the club wear berets,” can be false is if there is at least one Frenchman in the club who doesn’t wear a beret. If it so happens that there are no Frenchmen in the club, then there certainly isn’t any Frenchman in the club who doesn’t wear a beret, and therefore it is then taken as true that all the Frenchmen of the club wear berets. This is the convention we shall adopt.
Applying this to our universe U3, if x is an individual with no ancestors, then anything one can say about all of his ancestors is true (because he has none!). In particular, given any proposition p, we take it as true that all of x’s ancestors believe p, and so if
x has no ancestors, then x believes Np. (The only way an individual x can fail to believe Np is if he has at least one ancestor who doesn’t believe p, which is not possible for an individual who has no ancestors at all.) Let us record this as Fact 1.
Fact 1. If x has no ancestors, then for every proposition p, x believes Np.
We are aiming to show that the set of established propositions of U3 is of type G. It certainly is of type 4 (by Problem 2, since all the conditions of U2 hold also for U3). It then remains for us to show that for any proposition p, all the inhabitants of U3 believe the proposition N(Np⊃p)⊃Np. The proof of this is very pretty; the key idea is contained in the following lemma.
Lemma 1. If x disbelieves Np, then x must have an ancestor y who both disbelieves p and believes Np.
First, prove the above lemma. Then show that the set of established propositions of U3 is of type G.
How all this ties in with Kripke semantics will be explained in the next chapter.
SOLUTIONS
1. (1) We know that conditions (1a) and (1b) are true, since each reasoner is of type 1.
(2) So next we must demonstrate that each reasoner x believes (Np&N(p⊃q))⊃Nq, or, what is the same thing, if he believes Np&N(p⊃q), then he must also believe Nq. So, suppose x believes Np&N(p⊃q). Then he believes both Np and N(p⊃q). Since he believes Np, then his parents both believe p. Since he believes N(p⊃q), then his parents both believe p⊃q. Therefore his parents both believe p and p⊃q, and being of type 1, they both believe q. Since his parents both believe q, then x believes Nq.