Access to the full content is only available to members of institutions that have purchased access. If you belong to such an institution, please log in or find out more about how to order.


Print

Contents

Provability logic

DOI
10.4324/9780415249126-Y052-1
DOI: 10.4324/9780415249126-Y052-1
Version: v1,  Published online: 1998
Retrieved March 28, 2024, from https://www.rep.routledge.com/articles/thematic/provability-logic/v-1

Article Summary

Central to Gödel’s second incompleteness theorem is his discovery that, in a sense, a formal system can talk about itself. Provability logic is a branch of modal logic specifically directed at exploring this phenomenon. Consider a sufficiently rich formal theory T. By Gödel’s methods we can construct a predicate in the language of T representing the predicate ‘is formally provable in T’. It turns out that T is able to prove statements of the form

  • (1) If A is provable in T, then it is provable in T that A is provable in T.

In modal logic, predicates such as ‘it is unavoidable that’ or ‘I know that’ are considered as modal operators, that is, as non-truth-functional propositional connectives. In provability logic, ‘is provable in T’ is similarly treated. We write □A for ‘A is provable in T’. This enables us to rephrase (1) as follows:

  • (1′) □A →□□A.

This is a well-known modal principle amenable to study by the methods of modal logic.

Provability logic produces manageable systems of modal logic precisely describing all modal principles for □A that T itself can prove. The language of the modal system will be different from the language of the system T under study. Thus the provability logic of T (that is, the insights T has about its own provability predicate as far as visible in the modal language) is decidable and can be studied by finitistic methods. T, in contrast, is highly undecidable. The advantages of provability logic are: (1) it yields a very perspicuous representation of certain arguments in a formal theory T about provability in T; (2) it gives us a great deal of control of the principles for provability in so far as these can be formulated in the modal language at all; (3) it gives us a direct way to compare notions such as knowledge with the notion of formal provability; and (4) it is a fully worked-out syntactic approach to necessity in the sense of Quine.

Print
Citing this article:
Visser, Albert. Provability logic, 1998, doi:10.4324/9780415249126-Y052-1. Routledge Encyclopedia of Philosophy, Taylor and Francis, https://www.rep.routledge.com/articles/thematic/provability-logic/v-1.
Copyright © 1998-2024 Routledge.

Related Searches

Topics