Self-verifying theories

Self-verifying theories are consistent first-order systems of arithmetic much weaker than Peano arithmetic that are capable of proving their own consistency. Dan Willard was the first to investigate their properties, and he has described a family of such systems. According to Gödel's incompleteness theorem, these systems cannot contain the theory of Peano arithmetic, and in fact, not even the weak fragment of Robinson arithmetic; nonetheless, they can contain strong theorems.

In outline, the key to Willard's construction of his system is to formalise enough of the Gödel machinery to talk about provability internally without being able to formalise diagonalisation. Diagonalisation depends upon being able to prove that multiplication is a total function (and in the earlier versions of the result, addition also). Addition and multiplication are not function symbols of Willard's language; instead, subtraction and division are, with the addition and multiplication predicates being defined in terms of these. Here, one cannot prove the \Pi^0_2 sentence expressing totality of multiplication:

(\forall x,y)\ (\exists z)\ {\rm multiply}(x,y,z).

where {\rm multiply} is the three-place predicate which stands for z/y=x. When the operations are expressed in this way, provability of a given sentence can be encoded as an arithmetic sentence describing termination of an analytic tableau. Provability of consistency can then simply be added as an axiom. The resulting system can be proven consistent by means of a relative consistency argument with respect to ordinary arithmetic.

We can add any true \Pi^0_1 sentence of arithmetic to the theory and still remain consistent.

References

External links

This article is issued from Wikipedia - version of the 5/1/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.