Discussion. Knowledge of these modal systems provides information about the more usual systems of mathematics. The modal system K holds good for any mathematical system S of type 3 (if we interpret BX as “X is provable in S”). Similarly, the axiom system K4 holds good for any system S of type 4, and the axiom system G holds for any system S of type G. Thus these modal axiom systems give useful information about provability in the more common types of mathematical systems (which are nonmodal). Computer scientists today are also interested in modal axiom systems for the following reason. Imagine a computer programmed to print out various sentences, some of which are assertions about what the computer can and cannot print. The interpretation of BX then becomes: “The computer can print X.” Such computers are, so to speak, “self-referential,” and are accordingly of interest to those working in artificial intelligence. We will consider such systems in a later chapter.
In much of this book we have been treating “belief” as a modality. We started out using “B” for “believed” (by a reasoner of appropriate type). Modal logic enables one to give a unified treatment of reasoners who believe propositions, computers that can print propositions (or rather, sentences that express them), and mathematical systems that can prove propositions.
Sentential Modal Systems. By a modal sentence we shall mean a modal formula in which none of the propositional variables p, q, r,…occur—expressions such as B⊥⊃⊥, B(⊥⊃B⊥). Thus modal sentences are all built from the five symbols B, ⊥, ⊃, (,). By a sentential modal system, we shall mean a modal system whose axioms are all sentences (from which it easily follows that only sentences are provable). For any modal system M, we shall let be that system whose axioms consist of all sentences that are axioms of M, and whose rules of inference are the same as those of M (usually they will be modus ponens and necessitation). We will be particularly interested in the sentential modal systems , , and . It is not difficult to show that if M is either of these three systems, then any sentence provable in M is also provable in . (The reader might try this now as an exercise—the solution will be given later—Chapter 27—when we need to use this fact.)
We will return to the study of modal systems after treating the fascinating topic of self-reference—to which we turn in the following chapter.
• Part X •
THE HEART OF THE MATTER
• 25 •
A Gödelized Universe
LET US now turn to what can be called the heart of the matter—namely, self-reference. We have not yet given the reader any idea of how Gödel managed to construct a self-referential sentence—a sentence that asserted its own nonprovability in the system under consideration. He did this by inventing an extremely ingenious device known as diagonalization. In this chapter and the next, we will consider Gödel’s diagonal argument in several forms.
A GÖDELIZED UNIVERSE
Let us contemplate a universe with infinitely many reasoners in it. There are also infinitely many propositions about this universe. More specifically:
(1) ⊥ is one of these propositions (and, of course, is false).
(2) For any one of these propositions p and any reasoner R, the proposition that R believes p is one of these propositions.
(3) For any propositions p and q about the universe, p⊃q is again a proposition about the universe and is true if and only if either p is false or q is true.
We henceforth use the word “proposition” to mean a proposition about the universe. We define the logical connectives ~, &, v, ≡ from ⊃ and ⊥ in the manner of Chapter 8.
For any reasoner R and any proposition p, we let Rp be the proposition that R believes p. For any reasoners R and S and any proposition p, RSp is the proposition that R believes that S believes p. If we throw in another reasoner K, KRSp is the proposition that K believes that R believes that S believes p—and similarly if we add more reasoners.
The reasoners had great fun reasoning about these propositions, but things were rather chaotic until a certain logician from another universe visited their universe and put things in order. The first thing he noticed was that the reasoners had no names, and so he assigned to each reasoner a number (a positive whole number, that is) known as the Gödel number of the reasoner. No two reasoners had the same number and every number was the number of some reasoner. Now the reasoners had names: R1 is the reasoner whose number is 1, R2 is the reasoner whose number is 2, and for each n, Rn is the reasoner whose number is n.
Next, the logician arranged all the propositions about the universe in a certain infinite sequence p1, p2,…, pn,…For each n, the number n was known as the Gödel number of the proposition pn. After having done these things, the logician left and went back to his home universe.
Shortly after the logician’s departure, the more clever of the inhabitants realized the following curious fact.
Fact 1. For each reasoner R, there was a reasoner R* such that for any proposition pi, the reasoner R* believed pi if and only if the reasoner R believed that Ri believed pi. (Thus for any reasoner R, there was a reasoner R* such that for every number i, the proposition R*pi≡RRipi is true.)
This fact has some interesting consequences, as the following problems will reveal.
1. The Diagonal Principle
Prove that for any reasoner R, there is at least one proposition p such that p≡Rp is true (in other words, p is true if and only if R believes p).
2. Inept Reasoners
A reasoner of this universe is called totally inept if he believes all false propositions and doesn’t believe any true ones.
Prove that no reasoner of this universe is totally inept.
Another important fact about this universe was realized soon after the logician’s departure.
Fact 2. For any reasoner R and any proposition q, there is some reasoner S such that for any proposition p, S believes p if and only if R believes p⊃q. (Thus Sp≡R(p⊃q) is true.)
3. A Tarskian Principle
A reasoner of this universe is called perfect if he believes all true propositions and doesn’t believe any false ones. (He is the diametric opposite of a totally inept reasoner.)
For years the reasoners of this universe were in search of a perfect reasoner (of their own universe), but couldn’t find one. Why were they unable to find one?
The next important things to be discovered about this universe are that certain propositions are called established and that there is a reasoner E who believes those and only those propositions that are established.
4
Assuming that all the established propositions are true, prove that the set of established propositions is incomplete—i.e., there must be at least one proposition p such that neither p nor ~p is established. (This means also that the reasoner E can never believe p and can never believe ~p. He must remain forever undecided as to whether or not p is true.)
Next, the following two facts were revealed.
Fact I. For any reasoner R, there is a reasoner R* such that for every number i, the proposition R*pi≡RRipi is established. (This differs from Fact 1 in that we now say established instead of true.)
Fact II. For any reasoner R and any proposition q, there is a reasoner S such that for every number i, Spi≡R(pi⊃q) is established. (This differs from Fact 2 in that we say established instead of true.)
5
Prove that for any reasoner R, there is a proposition p such that the proposition p≡Rp is established.
6
Suppose that the set of established propositions is of type 1.
(a) Show that for every reasoner R and every proposition q, there is a proposition p such that the proposition p≡R(p⊃q) is established.
(b) Show that for every reasoner R and every proposition q, there is a proposition p such that the proposition p≡(Rp⊃q) is established.
Finally, the following fact was realized.
Fact III. The reasoner E was of type 4 (and hence the set of established propositions was of type 4).
7
&n
bsp; Prove that the set of established propositions is of type G.
We now see that the set of established propositions of this universe is of type G, and hence, if this set is consistent, the fact that it is consistent, though true, is not one of the established propositions of the universe. Equivalently, if the reasoner E is consistent, he can never know that he is consistent.
RELATION TO MATHEMATICAL SYSTEMS
The reader might wonder what all this has to do with the theory of mathematical systems. Well, suppose we have a mathematical system S with all its propositions arranged in some infinite sequence p1, p2,…, pn,…Now, instead of reasoners, we will consider certain properties of propositions; these properties are also arranged in some infinite sequence R1, R2,…, Rn,…For any property Ri and any proposition pj, we now let Ripj be the proposition that the property Ri holds for the proposition pj. Suppose also that the property—call it E—of being a provable proposition of the system is one of the properties of the above list and suppose that Facts I, II, and III hold replacing the words “reasoner” by “property” and “established” by “provable” (provable in S, that is). Then by a mere change of terminology, the preceding arguments of this chapter show that the system S must be of type G.
Actually, the systems investigated by Gödel did not start out with properties of propositions, but with properties of numbers. However, by the device of Gödel-numbering the propositions, any property of numbers then corresponds to a certain property of propositions—namely, for any property A of numbers, we let A′ be the property which holds for just those propositions pi such that A holds for the number i. A concrete illustration of this will be given in the next chapter.
Self-reference can also be achieved without Gödel numbering, as is indicated by the exercise below.
Exercise 1. There is another universe of reasoners in which it makes no difference whether the number of reasoners is finite or infinite. Some of the reasoners are immortal, but no reasoner knows which of the reasoners are immortal and which ones are mortal. In fact, no reasoner knows whether he himself is mortal or not. For every reasoner R, we let be the proposition that R is immortal. For any reasoners R and S, we let R be the proposition that R believes that S is immortal; for any three reasoners R, S, and K, we let RS& be the proposition that R believes that S believes that K is immortal—and so forth (if there are more reasoners involved).
In place of Fact 1 of the last universe, we have the following fact for this universe: For any reasoner R, there is a reasoner R* such that for every reasoner S, the reasoner R* believes that S is immortal if and only if R believes that S believes himself to be immortal (thus R* is true if and only if RS& is true).
Given a reasoner R, find a proposition p such that p is true if and only if R believes p.
Note: This method of achieving self-reference without Gödel numbering is borrowed from the field known as combinatory logic. A host of related self-referential problems in this field can be found in my book To Mock a Mockingbird.
SOLUTIONS
1. Take any reasoner R. By Fact 1, there is a reasoner R* such that for every number i, the reasoner R* believes pi if and only if R believes the proposition Ripi. Now, R* has some Gödel number h, and so R* is the reasoner Rh. Thus for any number i, the following is true:
(1) Rh believes pi if and only if R believes that Ri believes pi.
Since this is true for every number i, it is also true when i is the number h. We thus have:
(2) Rh believes ph if and only if R believes that Rh believes ph.
We thus take p to be the proposition that Rh believes ph, and we see that p is true if and only if R believes p.
2. We have just seen that for any reasoner R, there is a proposition p such that p is true if and only if R believes p. This means that one of the following two cases must hold: (1) p is true and R believes p; (2) p is false and R doesn’t believe p. If (1) holds, then R believes at least one true proposition—namely, p—and hence R is not totally inept. If (2) holds, then there is at least one false proposition—namely, p—such that R doesn’t believe p, hence R doesn’t believe all false propositions, and so again R is not totally inept.
3. Using Fact 2, we take for q the proposition ⊥. Then for any reasoner R, there is a reasoner R′ (called “S,” in Fact 2) who believes those and only those propositions p such that R believes p⊃⊥. (Such a reasoner R′ might be said to oppose R.)
Now, suppose R were perfect. Then for any proposition p, R believes p⊃⊥ if and only if p⊃⊥ is true, which in turn is the case if and only if p is false. Therefore R believes p⊃⊥ if and only if p is false. Also, R′ believes p if and only if R believes p⊃⊥. Putting these last two facts together, R′ believes p if and only if p is false. This means that R′ is totally inept.
We thus see that if the universe contains a perfect reasoner R, then it must also contain a totally inept reasoner R′. But we have proved in Problem 2 that the universe contains no totally inept reasoner. Therefore the universe contains no perfect reasoner.
4. Let us call a reasoner accurate if he believes no false propositions. Consider now any accurate reasoner R. We saw in Problem 3 that none of the reasoners is perfect, hence R is also imperfect. This means that R either believes some false proposition, or he fails to believe some true proposition. Since R is accurate, he doesn’t believe any false proposition, hence it must be that R fails to believe some true proposition. This proves that for any accurate reasoner R, there is at least one true proposition p that R fails to believe. Since p is true, ~p is false, hence R, being accurate, doesn’t believe ~p either. Therefore, for every accurate reasoner R, his belief system is incomplete. There is at least one proposition p such that R neither believes p nor believes ~p—he must remain forever undecided as to whether p is true or false.
Assuming that all the established propositions are true, the reasoner E is accurate (because he believes all the established propositions and no others). Therefore there is a proposition p such that E neither believes p nor believes ~p, hence neither p nor ~p is established.
5. The proof is essentially that of Problem 1 using Fact I in place of Fact 1.
Given a reasoner R, there is a reasoner Rh (called R*) such that for any number i, the proposition Rhpi≡RRipi is established. Hence Rhph≡RRhph is established. Thus p≡Rp is established, where p is the proposition Rhph.
6. Suppose the set of established propositions is of type 1.
(a) Take any reasoner R and any proposition q. By Fact 2, there is a reasoner S such that for every p, the proposition Sp≡R(p⊃q) is established. Also by Problem 5 (reading S for R), there is a proposition p such that p≡Sp is established. It then follows that p≡R(p⊃q) is established (since it is a logical consequence of the last two propositions).
(b) Again take any reasoner R and any proposition q. By (a), there is a proposition—call it p1—such that p1≡R(p1⊃q) is established. Hence (p1⊃q)≡(R(p1⊃q)⊃q) is established (a trick we have used before), and so p≡(Rp⊃q) is established, where p is the proposition p1⊃q.
7. We are now given that E is of type 4, hence he is certainly of type 1. Then by (b) of the last problem, for any proposition q, there is a proposition p such that the proposition p≡(Ep⊃q) is established—thus the set of established propositions is reflexive. And we know from Chapter 19 that any reflexive system of type 4 is of type G.
• 26 •
Some Remarkable Logic Machines
FERGUSSON’S LATEST MACHINE
The logician Malcolm Fergusson of my book The Lady or the Tiger? was fond of constructing logic machines to illustrate important principles in logic and proof theory. One of his machines was described in that book. In Fergusson’s later years, when he heard about Gödel’s and Löb’s theorems, he straightaway set out to construct a second machine, which he delighted in demonstrating to his friends. He proved to their satisfaction that the machine was a consistent and stable machine of type G, and he took particular delight in demonstrating that t
he machine, though consistent, could never prove its own consistency! The machine illustrates in a very simple and instructive manner the essential ideas behind Gödel’s First and Second Incompleteness theorems as well as Löb’s Theorem. I am accordingly happy to communicate the details to the reader.
The machine prints out various sentences built from seventeen symbols. The first seven symbols are the following:
Underneath each of these seven symbols, I have written its Gödel number. The remaining ten symbols are the familiar digits 1, 2, 3, 4, 5, 6, 7, 8, 9, 0. These digits are assigned Gödel numbers as follows: The Gödel number of 1 is 89 (8 followed by one 9); the Gödel number of 2 is 899 (8 followed by two 9’s); and so on, until 0, whose Gödel number is 89999999999 (8 followed by ten 9’s). Thus each of the seventeen symbols has a Gödel number. Given a complex expression, one finds its Gödel number by replacing each symbol with its Gödel number—for example, the Gödel number of (P⊥⊃⊥) is 412325. As another example, the Gödel number of P35 is 18999899999. For any expression E, by we shall mean the Gödel number of E (written as a string of the digits 1, 2,…, 0). Not every number is the Gödel number of an expression (for example, 88 is not the Gödel number of any expression). If n is the Gödel number of an expression, we shall sometimes refer to the expression as the nth expression. (For example, pd is the 16th expression; ⊥ is the 2nd expression.)
The machine is self-referential in that the sentences printed by the machine express propositions about what the machine can and cannot print. An expression is called printable if the machine can print it. The symbol “P” means “printable,” and for any expression E built from the seventeen symbols, if we want to write down a sentence that asserts that E is printable, we don’t write down PE, but P (i.e., P followed by the Gödel number of E). For example, a sentence that asserts that (P⊥⊃⊥) is printable is —i.e., P412325.
Forever Undecided Page 17