Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-07T17:31:39.132Z Has data issue: false hasContentIssue false

Extremely undecidable sentences

Published online by Cambridge University Press:  12 March 2014

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

Extract

Let ‘ϕ’, ‘χ’, and ‘ψ’ be variables ranging over functions from the sentence letters P0, P1, … Pn, … of (propositional) modal logic to sentences of P(eano) Arithmetic), and for each sentence A of modal logic, inductively define Aϕ by

[and similarly for other nonmodal propositional connectives]; and

where Bew(x) is the standard provability predicate for PA and ⌈F⌉ is the PA numeral for the Gödel number of the formula F of PA. Then for any ϕ, (−□⊥)ϕ = −Bew(⌈⊥⌉), which is the consistency assertion for PA; a sentence S is undecidable in PA iff both and , where ϕ(p0) = S. If ψ(p0) is the undecidable sentence constructed by Gödel, then ⊬PA (−□⊥→ −□p0 & − □ − p0)ψ and ⊢PA(P0 ↔ −□⊥)ψ. However, if ψ(p0) is the undecidable sentence constructed by Rosser, then the situation is the other way around: ⊬PA(P0 ↔ −□⊥)ψ and ⊢PA (−□⊥→ −□−p0 & −□−p0)ψ. We call a sentence S of PA extremely undecidable if for all modal sentences A containing no sentence letter other than p0, if for some ψ, ⊬PAAψ, then ⊬PAAϕ, where ϕ(p0) = S. (So, roughly speaking, a sentence is extremely undecidable if it can be proved to have only those modal-logically characterizable properties that every sentence can be proved to have.) Thus extremely undecidable sentences are undecidable, but neither the Godel nor the Rosser sentence is extremely undecidable. It will follow at once from the main theorem of this paper that there are infinitely many inequivalent extremely undecidable 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

[B]Boolos, G., The unprovability of consistency, Cambridge University Press, Cambridge, England, 1979.Google Scholar
[K]Kripke, S., ‘Flexible’ predicates of formal number theory, Proceedings of the American Mathematical Society, vol. 13 (1962), pp. 647650.Google Scholar
[Sm]Smorynski, C., Applications of Kripke models, Metamathematical investigation of intuitionistic arithmetic and analysis, Springer-Verlag, Berlin and New York, 1973.Google Scholar
[So]Solovay, R., Provability interpretations of modal logic, Israel Journal of Mathematics, vol. 25 (1976), pp. 287304.CrossRefGoogle Scholar