Arithmetic complexity of the predicate logics of certain complete arithmetic theories

✍ Scribed by Valery Plisko

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 137 KB
• Volume: 113
• Category: Article
• ISSN: 0168-0072
• DOI: 10.1016/s0168-0072(01)00061-6

✦ Synopsis

It is proved in this paper that the predicate logic of each complete constructive arithmetic theory T having the existential property is T 1 -complete. In this connection, the techniques of a uniform partial truth deÿnition for intuitionistic arithmetic theories is used. The main theorem is applied to the characterization of the predicate logic corresponding to certain variant of the notion of realizable predicate formula. Namely, it is shown that the set of irrefutable predicate formulas is recursively isomorphic to the complement of the set ∅ (!+1) . The notion of n-realizability is deÿned on the basis of the notion of n-function. It is proved that the predicate logic of n-realizability is !+1-hard.