For any expressions X and Y, Fergusson defined the diagonalization of X with respect to Y to be the expression (X(,)⊃Y). The symbol “d” abbreviates “diagonalization”—and for any expressions X and Y, the expression Pd(,) is a sentence expressing the proposition that the diagonalization of X with respect to Y is printable.
We shall now define what it means for an expression to be a sentence and what it means for a sentence to be true.
(1) ⊥ is a sentence and ⊥ is false.
(2) For any expression X, the expression P is a sentence and is true if and only if the expression X is printable.
(3) For any expressions X and Y, the expression Pd(,) is a sentence and is true if and only if the expression (X(,)⊃Y)—which is the diagonalization of X with respect to Y—is printable.
(4) For any sentences X and Y, the expression (X⊃Y) is a sentence and is true if and only if either X is not true or Y is true.
It is to be understood that no expression is a sentence unless its being so is a consequence of the above rules. The logical connectives ~, &, v, ≡ are defined from ⊃ and ⊥ in the manner explained in Chapter 8.
Now we give the rules for what the machine can print. The machine is programmed to print out an infinite list of sentences sequentially. Certain sentences called axioms can be printed at any stage of the process. Among the axioms are all tautologies. (Thus for any tautology X, the machine can print X whenever it likes, regardless of what it has or has not printed at any previous stage.) Next, the machine is programmed so that for any sentences X and Y, if the machine has, at a certain stage, already printed X and X⊃Y, then it can print Y. Thus the machine is of type 1 (in the sense that the class of printable sentences is of type 1). Since it is true that if X and X⊃Y are both printable, so is Y, then the sentence is true; or, what is the same thing, the sentence is true (the two sentences are logically equivalent). Well, the machine “knows” the truth of all sentences of the form and takes them all as axioms. Thus the machine is of type 2. Next, if the machine ever prints a sentence X, it “knows” that it has printed X and will sooner or later print the true sentence P. (The sentence P is true, since X has been printed.) And so the machine is normal, hence is of type 3. Since the machine is normal, then for any sentence X, the sentence is true. So the machine is initially “aware” of the truth of all such sentences and takes them all as axioms. Thus the machine is of type 4.
There is one more thing the machine can do, and this is quite crucial. For any expressions X and Y, the sentence Pd(,) is true if and only if (X(,)⊃Y) is printable, which in turn is the case if and only if the sentence is true. Therefore the following sentence is true: .
Well, the machine knows the truth of all such sentences and takes them all as axioms. These axioms are called the diagonal axioms.
Let us now systematically review all the axioms and operations of the machine:
Axioms: Group 1. All tautologies.
Group 2. All sentences of the form .
Group 3. All sentences of the form .
Group 4 (the diagonal axioms). All sentences of the form , where X and Y are any expressions (not necessarily sentences).
Operation Rules. (1) Axioms can be printed at any stage.
(2) Given sentences X and (X⊃Y) already printed, the machine can then print Y.
(3) Given a sentence X already printed, the machine can print P.
This concludes the rules governing printability by the machine. It is to be understood that the only way the machine can print a sentence X at a given stage is by following one of the above rules. That is, X is printable at a given stage only if one of the following three conditions holds: (1) X is an axiom; (2) there is a sentence Y such that Y and (Y⊃X) have both been printed at an earlier stage; (3) there is a sentence Y such that X is the sentence P and Y has been printed at an earlier stage.
Remarks. For each sentence X, let BX be the sentence P. The symbol “B” is not part of the machine language; we are using it to talk about the machine. We are using “B” as standing for the operation that assigns to each sentence X the sentence P. When we say that the machine is of type 4, we mean that it is of type 4 with reference to this Operation B. In essence, without the diagonal axioms, the axiom system of this machine is the modal system K4. We will shortly see that adding the diagonal axioms gives us all the power of the modal system G.
Provability. We have defined for each sentence what it means for the sentence to be true, and so each sentence expresses a definite proposition, which might be true or might be false. We say that the machine proves a proposition if it prints some sentence that expresses the proposition. For example, the sentence ~P2 expresses the proposition that the machine is consistent (since 2 is the Gödel number of ⊥), and so if the machine printed ~P2, it would prove its own consistency. If the machine printed P2, then it would prove its own inconsistency.
We say that the machine is accurate if all propositions provable by the machine are true. We say that the machine is consistent if it cannot prove ⊥, and that the machine is stable if for every sentence X, if P is printable, so is X.
Reflexivity. Now we turn to the proof that the machine is Gödelian—in fact, reflexive.
1. The Gödel Sentence G
Find a sentence G such that the sentence G≡~P—i.e., the sentence G≡(P⊃⊥)—is printable.
2. Reflexivity
Show that for any sentence Y, there is a sentence X such that the sentence X≡(P⊃Y) is printable.
Solutions. Problem 1 is a special case of Problem 2, so we first solve Problem 2. Let Y be any sentence. For any expression Z, the sentence is printable (because it is one of the diagonal axioms). We take for Z the expression Pd, and therefore is printable. Since the machine is of type 1, it then follows that the following sentence is printable: .
Thus the sentence X≡(P⊃Y) is printable, where X is the sentence .
Problem 1 is a special case of 2, taking ⊥ for Y. Thus the Gödel sentence G for this machine is —i.e., the sentence (Pd(16,2)⊃⊥).
Let us take a closer look at Gödel’s remarkable sentence G. First, what does the sentence Pd(16,2) say? It says that the diagonalization of the 16th expression with respect to the 2nd expression is printable. Now, the 16th expression is Pd and the 2nd expression is ⊥, and so Pd(16,2) says that the diagonalization of Pd with respect to ⊥ is printable, but this diagonalization is the sentence (Pd(16,2)⊃⊥)—i.e., the very sentence G! And so Pd(16,2) says that G is printable, hence (Pd(16,2)⊃⊥)—which is the sentence G—says that G is not printable (or, what is the same thing, that the printability of G implies falsehood). Thus G says that G is not printable; G is true if and only if G is not printable. Thus G asserts its own nonprintability. Here, in a nutshell, is Gödel’s ingenious method of achieving self-reference.
The sentence G≡~P—i.e., the sentence G≡(P⊃⊥)—is not only true, but actually printable (it is one of the diagonal axioms). Since the machine is normal and of type 1, it follows by Gödel’s First Incompleteness Theorem (Theorem I, Chapter 20, this page) that if the machine is consistent, then G is not printable, and if the machine is also stable, then ~G is also not printable. And so, if the machine is both consistent and stable, the sentence G is undecidable in the system of sentences that the machine can print.
Now, the machine is in fact of type 4, and since it is Gödelian —the sentence G≡~P is printable—it then follows from Gödel’s Second Incompleteness Theorem (Part 4 of Summary I*, Chapter 13, this page) that if the machine is consistent, then it cannot prove its own consistency—i.e., it cannot print the sentence ~P2. Also, if the machine is consistent, then the sentence ~P2 is true, and is hence another example of a true sentence that the machine cannot print.
Furthermore, the machine is reflexive (Problem 2) and being of type 4, it must be Löbian (by Löb’s Theorem), and so for any sentence X, if P⊃X is printable, so is X. It then follows by Theorem M1, Chapter 18 (this page), that the machine is of type G.
THE CORRE
CTNESS OF THE MACHINE
We have shown that if Fergusson’s machine is consistent, then it cannot prove its own consistency; but how do we know whether or not the machine is consistent? We will now prove that the machine is not only consistent, but wholly accurate—i.e., that every sentence printed by the machine is true.
We have already shown that all the axioms of the machine are true, but let us carefully review the arguments: The axioms of Group 1 are all tautologies, hence they are certainly true. As for the axioms of Group 2, to say that is true is to say that if and P are both true, so is PY—which is to say that if (X⊃Y) and X are both printable, so is Y. Well, this is obviously the case by virtue of Operation 2. Thus the axioms of Group 2 are all true. As for the axioms of Group 3, to say that is true, so is , which in turn is to say that if X is printable, so is P—and this is indeed the case, by virtue of Operation 3. As for the diagonal axioms, Pd(,) is true if and only if (X(,)⊃Y) is printable, which is the case if and only if is true. Therefore is true.
Now we know that all the axioms of the machine are true, but we need to show that all the printable sentences are true.
We recall that the machine prints sentences at various stages. We now wish to establish the following lemma, theorem, and corollary.
Lemma. If X is a sentence printed at a certain stage and all sentences printed prior to that stage are true, then X is also true.
Theorem 1. Every sentence printed by the machine is true.
Corollary. The machine is both consistent and stable.
3
How are the above lemma, theorem, and corollary proved?
Solutions. First we prove the lemma: Assume the hypothesis that all sentences previously printed are true; we are to show that X is true.
Case 1. X is an axiom. Then X is true (as we have already proved).
Case 2. There is a sentence Y such that Y and (Y⊃X) have already been printed. Then by the assumed hypothesis, Y and (Y⊃X) are both true, hence X must be true.
Case 3. X is of the form P, where Y is a sentence that has been previously printed. Since Y has been printed, then P is true—i.e., X is true.
This concludes the proof of the lemma.
Proof of Theorem 1. The machine is programmed to print all printable sentences in some definite infinite sequence X1, X2,…, Xn,…By Xn is meant the sentence printed at stage n. Now, the first sentence printed by the machine (the sentence X1) must be an axiom (since the machine hasn’t printed any other sentences yet), hence X1 must be true. If the above infinite list should contain any false sentence, then there must be a smallest number n such that Xn is false—that is, there must be a first false sentence that the machine prints. We know that n is not equal to 1 (since X1 is true), hence n is greater than 1. This means that the machine prints a false sentence at stage n but has printed only true sentences at all earlier stages. But this is contrary to the lemma. Therefore the machine can never print any false sentences.
Proof of Corollary 1. Since the machine is accurate (by Theorem 1), then ⊥ can never be printed, because ⊥ is false. Therefore the machine is consistent.
Next, suppose that P is printable. Then P is true (by Theorem 1), which means that X is printable. Therefore the machine is stable.
We now see that Fergusson’s machine is consistent, but can never prove its own consistency. Thus you and I (as well as Fergusson) know that the machine is consistent, but the poor machine doesn’t have that knowledge!
CRAIG’S VARIANT
When Inspector Craig (a good friend of Fergusson’s) heard of Fergusson’s machine, he thought of an interesting variant, which does not involve Gödel numbering. Craig’s machine used just the following six symbols:
P ⊥ ⊃ ( ) R
His definitions of sentence and true sentence are given by the following rules:
(1) ⊥ is a sentence and ⊥ is not true.
(2) For any sentences X and Y, (X⊃Y) is a sentence and is true if and only if X is not true or Y is true.
(3) For any sentence X, PX is true if and only if the machine can print X.
(4) For any sentences X and Y, the expression (XRY) is a sentence and is declared true if and only if the machine can print ((XRX)⊃Y).
At first sight it might appear that (4) is circular, since the truth of (XRY) is defined in terms of an expression involving the letter R; but this circularity is only apparent. If Craig had defined (XRY) to be true if and only if ((XRX)⊃Y) is true, the definition would have been circular, since we couldn’t know what it means for (XRY) to be true without first knowing what it means for (XRX) to be true. But Craig didn’t do that. The fact is that for any sentences X and Y, either the expression ((XRX)⊃Y) is printable or it isn’t. The symbol “R” stands for the relation that holds between X and Y when ((XRX)⊃Y) is printable. Thus Craig is not defining the relation R in terms of itself, but in terms of the symbol “R,” and this constitutes no circularity.
The first three groups of axioms of Craig’s machine are the same as those of the modal system K4 (where sentence means sentence in the machine language of Craig’s system). Thus they are like the first three groups of axioms of Fergusson’s machine, leaving out the bars over X, Y, Z. The fourth group of Craig’s axioms can be read as: (4)′ (Craig’s diagonal axioms). All sentences of the form (XRY)≡P((XRX)⊃Y).
Of course all of Craig’s diagonal axioms are true sentences.
The operation rules of Craig’s machine are the same as those of Fergusson’s machine.
4
(a) Prove that Craig’s machine is reflexive (and hence also of type G, since it is of type 4).
(b) Find a Gödel sentence for Craig’s machine (i.e., a sentence G such that G≡~PG is printable by Craig’s machine).
Solution. (a) Since for any sentences X and Y, the sentence (XRY)≡P((XRX)⊃Y) is printable (it is a diagonal axiom), then this is also the case if X happens to be the very sentence Y. Therefore (YRY)≡P((YRY)⊃Y) is printable, hence so is the sentence ((YRY⊃Y)≡(P(YRY)⊃Y)⊃Y), and thus Z≡(PZ⊃Y) is printable, where Z is the sentence ((YRY)⊃Y).
(b) Taking ⊥ for Y, we get the Gödel sentence ((⊥R⊥)⊃⊥).
Note: The axioms of Craig’s machine are also all true, and by the same reasoning we used for Fergusson’s machine, it can be seen that every sentence printable by Craig’s machine is true. Therefore Craig’s machine is also consistent and stable (and of type G).
5. McCulloch’s Observation
When Walter McCulloch (a friend of both Craig and Fergusson) was informed about Craig’s machine, he made the following interesting observation: Given any sentences X and Y in which the symbol “R” does not occur, there is a sentence Z in which “R” does not occur such that the sentence (XRY≡Z) is printable. (This implies, incidentally, that for any sentence X at all, there is a sentence X′ in which “R” does not occur such that X≡X′ is printable by Craig’s machine.)
Can you prove that McCulloch’s observation is correct?
Solution. We proved in the solution of Problem 8 of Chapter 19 that any system of type G which can prove p≡B(p⊃q) can prove p≡Bq. (We showed this for reasoners, but the same argument goes through for systems.) Now, Craig’s system is of type G, and for any sentence X, the sentence (XRX)≡P((XRX)⊃X) is printable, and so if we take (XRX) for p and X for q, it follows that (XRX)≡PX is printable. From this it follows that ((XRX)⊃Y)≡(PX⊃Y) is printable, and hence (by regularity) P((XRX)⊃Y)≡P(PX⊃Y) is printable. But also (XRY)≡P((XRX)⊃Y) is printable, hence (XRY)≡P(PX⊃Y) is printable. If now the symbol “R” doesn’t occur in either X or Y, then it doesn’t occur in P(PX⊃Y), and so we take Z to be P(PX⊃Y).
• 27 •
Modal Systems Self-Applied
INSPIRED BY the logic machines of Craig and Fergusson, I would like now to look at modal axiom systems from the viewpoint of self-referential interpretations.
We recall that by a modal sentence—more briefly, a sentence—we mean a modal formula without propositional variables
. We now define a modal sentence to be true for a modal system M if it is true when we interpret B as provable in M. Thus:
(1) ⊥ is false for M.
(2) For any modal sentences X and Y, the sentence X⊃Y is true for M if and only if either X is not true for M or Y is true for M.
(3) For any sentence X, the sentence BX is true for M if and only if X is provable in M.
Note: A sentence X can be true for a modal system M without being provable in M, and conversely. For example, the sentence ~B⊥ is true for M if and only if M is consistent. To say that ~B⊥ is provable in M is to say that M can prove its own consistency. We will soon see that the modal system G is consistent, and so the sentence ~B⊥ is true for G. But the sentence ~B⊥ is not provable in G. On the other hand, any inconsistent modal system of type 1 can prove all sentences, hence in particular the sentence ~B⊥. In this case the sentence ~B⊥ is provable in the system, but not true for the system.
Consider now a modal system M1 and a modal system M2 (possibly the same as M1 or possibly different). We shall say that M1 is correct for M2 if every sentence provable in M1 is true for M2. And we shall say that a modal system M is self-referentially correct if M is correct for M—in other words, if every sentence provable in M is true for M.
Any self-referentially correct system must be consistent (because if ⊥ were provable in the system, the system couldn’t be self-referentially correct, since ⊥ is false for the system) and must also be stable (because if BX is provable in the system and the system is self-referentially correct, then BX must be true for the system, which means that X is provable in the system). And so any self-referentially correct system is automatically both consistent and stable.
Forever Undecided Page 18