FUNDAMENTALNAYA
I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

1999, VOLUME 5, NUMBER 1, PAGES 221-255

**On arithmetic complexity of the predicate logics of complete
constructive arithmetic theories**

V. E. Plisko

Abstract

View as HTML
View as gif image
View as LaTeX source

It is proved in this paper that the predicate logic of each
complete constructive arithmetic theory $T$ having the existence
property is $$P
_{1}^{T}-complete.
In this connection the techniques of uniform partial truth
definition 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 undisprovable predicate
formulas is recursively isomorphic to the complement of
the set $$Æ ^{( w
+1)}.

All articles are
published in Russian.

Location: http://mech.math.msu.su/~fpm/eng/99/991/99113h.htm

Last modified: April 27, 1999