On the approximation of reduction classes of RPC by decidable classes

S. A. Norgela

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part VII, Tome 60 (1976), pp. 103-108

Résumé

Prenex formulas of RPC are examined; all formulas obtained one from the other by renamings of objective and predicate variables and by deletion of fictitious quantifiers are reckoned to be alike. The number of occurrences of atomic formulas is called the length of a formula; $|M^{(n)}|$ denotes the number of formulas in a set $M$, having length $n$. $M$ is said to be approximatable by deducibility if an algorithmexists which for each positive $\varepsilon$ yields a solvable set $N$ of formulas and a number $n_0$ such that for all $n>n_0|N^{(n)}|/|M^{(n)}|>1-\varepsilon$. The number $\alpha$ is called the deducibility number of the class $A$ of formulas if the sequence $$ \frac{|\widetilde A^{(n)}|}{|A^{(n)}|},\quad n=1,2,3,\dots, $$ where $\widetilde A$ is the set of deducible formulas from $A$, effectively converges to $\alpha$. The deducibility number is found, or, at least, approximatability is proved, for a number of known reduction classes in RPC. Two items of literature are cited.