Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-23T14:46:12.667Z Has data issue: false hasContentIssue false

On the nonexistence of certain normal forms in the logic of provability

Published online by Cambridge University Press:  12 March 2014

George Boolos*
Affiliation:
Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Extract

G is the system of propositional modal logic whose axioms are all tautologies and all sentences □(AB) → (□A → □B) and □(□AA) → □A and whose rules are modus ponens and necessitation. For the connections between G and provability in formal systems, see [3] and [2].

A letterless sentence is a modal sentence that contains no sentence letters at all. In [1] the author showed (in effect) the existence of simple normal forms in G for letterless sentences: every letterless sentence is equivalent in G to a truth-functional compound of sentences ⋄r ⊤ (⋄0B = B; ⋄r+1B = ⋄ ⋄r+1 B. ⊤ is the 0-ary connective that is always evaluated as true; we assume that the language contains ⊤ as a primitive.)

A family of sets {Hn}n∈ω of modal sentences that contain no sentence letters other than some fixed one (say p) was introduced by Solovay in [3]: H0 = the set of sentences equivalent in G to one of p, −p, ⊤, and ⊥; Hn+x = the set of sentences equivalent in G to a truth-functional combination of sentences ⋄rB, where r ∈ ω and BHn. (This definition of the Hn's differs inessentially from the one given in [3].) Since r may = 0, HnHn+1 and thus if m ≤ n, HmHn; every modal sentence containing no letter other than p is in some Hn. It follows from the normal form theorem for letterless sentences that every letterless sentence is in H1.

In [3] Solovay stated without proof a result about the sets Hn: for every n, Hn ⊊ Hn+1; equivalently, for every n, there is a sentence containing no letter other than p not in Hn. Thus the existence of a normal form for letterless sentences is a very special feature of these sentences, for Solovay's result shows that normal forms like those obtainable for letterless sentences are not to be found in general. He takes this result to be one reason for regarding the Lindenbaum algebra in G of sentences containing no letter other than p as much more complicated than that of letterless sentences.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1982

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Boolos, G., On deciding the truth of certain statements involving the notion of consistency, this Journal, vol. 41 (1976), pp. 779781.Google Scholar
[2] Boolos, G., The unprovability of consistency: an essay in modal logic, Cambridge University Press, Cambridge, England, 1979.Google Scholar
[3] Solovay, R., Provability interpretations of modal logic, Israel Journal of Mathematics, vol. 25 (1976), pp. 287304, especially pp. 301–302.CrossRefGoogle Scholar