Self-referential correctness has one curious feature. It is possible that a system M might be self-referentially correct; yet if some of the axioms were deleted, the resulting system might no longer be self-referentially correct. For example, we might have one axiom that asserts that a second axiom is provable in the system; if this second axiom is removed, the first axiom might become false!
Some Self-Referentially Correct Systems. We recall the sentential modal systems K, , and described in Chapter 24 (they are like the systems K, K4, and G, except that the axioms are all restricted to sentences). We now aim to show that these three systems are self-referentially correct (from which, incidentally, we will be able to show that the systems K, K4, and G are self-referentially correct).
If is any of these three axiom systems K, 4, , to show that is self-referentially correct, it suffices to show that all axioms of are true for —the reason for this is a consequence of the following lemma, which has other applications as well.
Lemma A. Let be any sentential modal system whose only inference rules are modus ponens (from X and X⊃Y we can infer Y) and the necessitation rule (from X we can infer BX). Let M2 be any modal system such that all sentences provable in are provable in M2 and such that all axioms of are true for M2. Then all sentences provable in are true for M2—i.e., is correct for M2.
Corollary A1. For any sentential modal system whose only inference rules are modus ponens and necessitation, if all axioms of are true for , then is self-referentially correct.
1
Prove Lemma A. (Hint: The proof is essentially the same as the argument we gave in the last chapter to show that all provable sentences of Fergusson’s machine were true—once we established that all the axioms of the machine were true.)
Solution. Consider any sequence X1,…, Xn of sentences that constitutes a proof in the system . We will see that the first line X1 must be true for M2, then the second line X2 must be true for M2, then the third line X3, and so forth down to the last line.
The first line X1 must be an axiom, hence it is true for M2 by hypothesis. Now consider the second line X2. Either it is an axiom of (in which case it is true for M2), or it must be the sentence BX1, in which case it is certainly true for M2 since X1 has already been proved in M1, and is hence provable in M2. Now we know that the first two lines are true for M2. We now consider the third line X3. If it is either an axiom of or is of the form BY, where Y is an earlier line (X1 or X2), then X3 is true for M2 for the same reasons as before. If X3 is neither, then it must be derived from X1 and X2 by modus ponens, and since we already know that X1 and X2 are true for M2, it follows that X3 is true for M2. (Clearly, for any sentences X and Y, if X and X⊃Y are both true for M2, then Y is true for M2.) Now we know that the first three lines of the proof are all true for M2, and knowing this, the truth of X4 can be established by the same argument. Then, knowing the truth of the first four lines, we similarly get the truth of the fifth line—and so on, until we reach the last line.† This concludes the proof of Lemma A.
The self-referential correctness of the systems , , and follows from Corollary A1 and the following lemma.
Lemma B. For any modal system M:
(a) If M is of type 1, then all axioms of are true for M.
(b) If M is normal and of type 1, then all axioms of are true for M.
(c) If M is of type G, then all axioms of are true for M.
2
Why is Lemma B correct?
Solution. (a) Suppose that the set of provable sentences of M is closed under modus ponens. All tautologies are obviously true for M (they are true for any modal system whatsoever). The other axioms of are sentences of the form (BX&B(X⊃Y))⊃BY—or alternatively B(X⊃Y)⊃(BX⊃BY); it really makes no difference. To say that (BX&B(X⊃Y))⊃BY is true for M is to say that if X is provable in M and X⊃Y is provable in M, so is Y. Well, this is the case, since the provable sentences of M are closed under modus ponens.
(b) Suppose M is a normal system of type 1. Then all axioms of are true for M—by (a). The other axioms of are the sentences of the form BX⊃BBX. Well, to say that such a sentence is true for M is to say that if BX is true for M, so is BBX—in other words, if X is provable in M, so is BX. This is so, since M is normal.
(c) Suppose M is of type G. Then it is certainly of type 4, so by (b), all axioms of are true for M. The remaining axioms of are sentences of the form B(BX⊃X)⊃BX, and to say that it is true for M is to say that if BX⊃X is provable in M, so is X—in other words, that M is Löbian. Well, we proved in Chapter 19 that any system of type G is Löbian. This concludes the proof of Lemma B.
We continue to let M be any of the systems K, K4, or G. Then is respectively , , or .
Corollary B1. All axioms of are true for .
Corollary B2. All axioms of are true for M.
Proofs. Since , , and are respectively of type 1, normal and of type 1, and of type G, Corollary B1 is immediate from Lemma B. Also the systems K, K4, and G are respectively of type 1, normal and of type 1, and of type G, and so we also have Corollary B2.
From Corollary B1 and Corollary A1, we now have Theorem 1.
Theorem 1. The systems , , and are all self-referentially correct.
Corollary. The systems K, K4, and are consistent and stable.
We now have a third example of a consistent and stable system of type G—namely, the modal system (the other two systems being the machines of the last chapter). We will soon see that the modal system G is also self-referentially correct (hence also both consistent and stable).
I hope the reader now fully realizes the absurdity of doubting the consistency of a system on the mere grounds that it cannot prove its own consistency!
The Systems K, K4, and G. To establish the self-referential correctness of the systems K, K4, and G, we proceed as follows. First of all, Lemma A has another corollary.
Corollary A2. Let M be any modal system whose only inference rules are modus ponens and necessitation. Then, if all axioms of are true for M, all provable sentences of are true for M.
It follows from Corollary A2 and Corollary B2 that if M is any of the modal systems K, K4, or G, then all sentences provable in are true for M. But we are not quite done. It remains to show that if M is either of these three systems, then any sentence provable in M is also provable in (a fact that was asserted without proof at the end of Chapter 19). Once this is done, the proof of the self-referential correctness of K, K4, and G will be complete.
3
Why is it true that if a sentence is provable in M (M being either K, K4, or G), then it is provable in ?
Solution. One can see by inspection of either of these three systems that if X is an axiom of M, then if we substitute any sentences for the propositional variables in X (substituting the same sentence for different occurrences of the same variable, of course), then the resulting sentence is also an axiom of M—and hence of . We now take any one particular sentence, say T, and for any formula X, let X′ be the result of substituting T for all the propositional variables in X. Of course if X is itself a sentence, we take X′ to be X. We now note the following facts: (1) If X is an axiom of M, then X′ is an axiom of . (2) For any formulas X and Y, the sentence (X⊃Y)′ is the sentence X′⊃Y′, and therefore for any formulas X, Y, and Z, if Z is derivable from X and Y by modus ponens, then Z′ is derivable from X′ and Y′ by modus ponens. (3) For any formula X, the sentence (BX)′ (i.e., B followed by X′), and so if Y is derivable from X by the necessitation rule, then Y′ is derivable from X′ by the necessitation rule. It therefore follows that given any sequence X1,…, Xn of formulas, if this sequence constitutes a proof in the system M, then the sequence X1′, X2′,…, Xn′ constitutes a proof in . And so, if X is any formula provable in M, the sentence X′ is then provable in . If, furthermore, X happens to be a sentence, then X′ = X, and hence X itself is provable in . This proves that any sentence provable in M is provable in .
* * *
†This type of argument is known as mat
hematical induction.
• Part XI •
FINALE
• 28 •
Modal Systems, Machines, and Reasoners
IN THE next chapter we will meet up with some very strange reasoners indeed. To appreciate them fully, let us first turn to the topic of minimal reasoners.
MINIMAL REASONERS OF VARIOUS TYPES
A modal sentence X is in itself neither true nor false; it only expresses a definite proposition once the symbol “B” is given an interpretation. We have defined a sentence to be true for a modal system M if it is true when “B” is interpreted as provability in M. We have all along understood a modal sentence as being true for a reasoner if it is true when “B” is interpreted as believed by the reasoner.
To say that a sentence is true for a reasoner means something entirely different than saying that it is believed by the reasoner. For example, to say that ~B⊥ is true for a reasoner is to say that the reasoner is consistent, whereas to say that ~B⊥ is believed by a reasoner is to say that the reasoner believes that he is consistent.
A machine can easily be programmed to print out all and only those sentences provable in the modal system by giving the machine these instructions: (1) At any stage, you may print any axiom of . (2) If at any stage you have printed sentences X and (X⊃Y), you may then print Y. (3) If at any stage you have printed X, you may then print BX. (The machine can then be given further instructions that will guarantee that anything the machine can do, it sooner or later will do, and so every sentence provable in will eventually be printed by the machine.) Let us call such a machine a machine.
Now, let us imagine a reasoner with his eye constantly on the output of the machine. However, he does not interpret BX as “X is printable by the machine,” or as “X is provable in ,” but as “I believe X.” (He thinks that the machine is printing sentences about him!) He gives what we might call an egocentric interpretation of modal sentences.
Then, suppose that the reasoner has complete confidence that the machine knows what he believes, and so whenever the machine prints a sentence X, he immediately believes it (under the egocentric interpretation, of course). His belief system will then include all sentences provable in . This does not guarantee that he is of type G (he may not be normal, even though he believes he is, and he may not even be of type 1, even though he believes he is). Of course if he correctly believes all sentences provable in , then it is easy to see that he is of type G.
But now, suppose he believes all and only those sentences printable by the machine; his belief system then coincides exactly with the set of sentences provable in , and since is of type G, then he must be of type G. Such a reasoner we will call a minimal reasoner of type G. Since the system is self-referentially correct (as we showed in the last chapter), it follows that a minimal reasoner of type G must be wholly accurate in his beliefs. It further follows that any minimal reasoner of type G is both consistent and stable.
We now see that the notion of a consistent, stable reasoner of type G does not involve a logical contradiction. A reasoner of type G is not necessarily consistent (indeed, any inconsistent reasoner of even type 1 is also of type G, since he believes everything!), but a minimal reasoner of type G is both consistent and stable.
Now let us consider a reasoner who is of type G and who is keeping his eye on the output of the machine (and who interprets all the modal sentences egocentrically). Will he necessarily believe all these sentences (under the egocentric interpretation)? Well, it is easy to verify that he believes all axioms of . (In fact, in Chapter 11 we showed that any reasoner of type 4 knows that he is of type 4; hence he will believe all axioms of . A reasoner of type G also believes he is modest, which means that he will believe all sentences of the form B(BX⊃X)⊃BX, and so he believes all axioms of .) And since the machine prints nonaxioms only by using the modus ponens and necessitation rules, and the reasoner’s beliefs are closed under modus ponens, and he is normal, then he will successively believe every sentence as it gets printed. (If anyone should interrupt the process and ask the reasoner his opinion of the machine, the reasoner will answer: “This machine is truly amazing. Everything it has printed about me so far is true!”)
We now see that a reasoner of type G does indeed believe all sentences provable in .
Suppose, next, that a modal sentence X is believed by all reasoners of type G; does it follow that X is actually provable in ? The answer is yes, since if X is believed by all reasoners of type G, then it must be believed by a minimal reasoner of type G, and hence must be provable in . And so we now see that a sentence is provable in if and only if it is believed by all reasoners of type G. Put another way, given any minimal reasoner of type G, he believes those and only those sentences that are believed by all reasoners of type G.
Of course, when two different reasoners look at the same modal sentence, they interpret it differently—each one interprets “B” as referring to his own beliefs (just as the word “I” has different references when used by different people). And so when we speak of a modal sentence being believed by all reasoners of type G, we mean believed by each one according to his own egocentric interpretation.
Of course everything we have said about the modal system and reasoners of type G also holds for the modal system and reasoners of type 4: A sentence is provable in if and only if it is believed by all reasoners of type 4. Likewise, a sentence is provable in if and only if it is believed by all reasoners of type 3.
MORE ON MODAL SYSTEMS AND REASONERS
The results of the problems in the remainder of this chapter are not necessary for the understanding of the next two chapters, but are independently interesting.
1
Suppose a reasoner’s beliefs are closed under modus ponens and that for any axiom X of , the reasoner believes X and also believes that he believes X. Will he necessarily believe all sentences that are believed by all reasoners of type 4? (Remember, he may not be normal!) The answer is given following Problem 2.
2
Now, substitute in place of K4. Will the reasoner above necessarily believe all sentences that are believed by all reasoners of type G?
The answer to the above problems is given by a well-known theorem about the modal systems K4 and G (and which also applies to and ), which we are about to state and whose proof we will sketch.
Let M be any modal system whose only inference rules are modus ponens and necessitation. We let M′ be that modal system whose axioms are the axioms of M together with all formulas BX, where X is an axiom of M, and whose only inference rule is modus ponens. It is obvious that everything provable in M′ is provable in M (because for any axiom X of M, BX is also provable in M, and so all axioms of M′ are provable in M), but in general it is not true that everything provable in M is provable in M′. However, we have the following interesting result:
Theorem 1. If all axioms of K4 are provable in M, then it is true that everything provable in M is provable in M′ (and hence the systems M and M′ prove exactly the same formulas).
Can the reader see how to prove Theorem 1?
(Hint: First show that if X is provable in M, then BX is provable in M′. Do this by showing that for any proof X1,…, Xn in M, all of the formulas BX1,…, BXn are successively provable in M′.)
More Detailed Proof. Since modus ponens is a rule of M′ and all tautologies are among the axioms of M′, then M′ is of course of type 1. Also the following three conditions hold for M′:
(1) If BX and B(X⊃Y) are provable in M′, so is BY—because B(X⊃Y)⊃(BX⊃BY) is an axiom of M′ and M′ is of type 1.
(2) If BX is provable in M′, so is BBX—because BX⊃BBX is an axiom of M′ and M′ is of type 1.
(3) If X is an axiom of M, then BX is provable in M′—because it is even an axiom of M′.
Now, suppose a sequence X1,…, Xn of formulas constitutes a proof in M. Each line of the proof either comes from two earlier lines by modus ponens, or from one earlier line by the necessitation rule, or is
itself an axiom of M. Using facts (1), (2), and (3) above, it easily follows that BX1 must be provable in M′, then that BX2 is provable in M′, then that BX3 is provable in M′, and so forth down to BXn. We leave the verification of this to the reader.
Now we know that if X is provable in M, then BX is provable in M′. Therefore, if X is provable in M′, then BX is provable in M′ (because if X is provable in M′, it is also provable in M). And so we see that M′ is normal (even though the necessitation rule is not initially given for M′). Then, given any proof X1,…, Xn in M, it is easy to see that each of the lines X1,…, Xn itself can be successively proved in M′. (We leave the verification of this to the reader.)
Corollary. The provable formulas of K4 and K4′ are the same. The provable formulas of G and G′ are the same.
The following theorem and its corollary can be proved by a similar argument.
Theorem Ī. For any sentential modal system in which all axioms of are provable, and in which modus ponens and necessitation are the only inference rules, the provable sentences of are the same as the provable sentences of .
Corollary. The provable sentences of are the same as those of . The provable sentences of are the same as those of .
Of course the above corollary gives an affirmative answer to Problems 1 and 2.
We see by virtue of the corollary to Theorem 1 that the modal systems K4 and G can be alternatively axiomatized using systems whose only inference rule is modus ponens.
Forever Undecided Page 19