|
Zapiski Nauchnykh Seminarov LOMI, 1971, Volume 20, Pages 115–133
(Mi znsl2402)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Quantifier-free and one-quantifier systems
G. E. Mints
Abstract:
There are considered formulas of classical first order arithmetic $Z$ with primitive recursive functions. The complexity of a formula is its quantifier-depth, that is the maximal number of changes of quantifiers governing each other. So the complexity of $\&_i(\exists x_iR_i\vee\forall y_iS_i)$, $R_i,S_i$ being quantifier-free, is $0$. $Z_n$ is $n$-truncation of $Z$ (only formulas of complexity $\leq n$ are permitted in Sequenzen-deductions). It is proved that $Z_0$ is a conservative extension of PRA (primitive recursive arithmetic). The proof gives a characterization of primitive recursive functions. These are precisely function provably recursive in the arithmetical system constructed from free variable arithmetic of Kalmar-elementary function in the same way as $Z_0$ is constructed from PRA.
Citation:
G. E. Mints, “Quantifier-free and one-quantifier systems”, Studies in constructive mathematics and mathematical logic. Part IV, Zap. Nauchn. Sem. LOMI, 20, "Nauka", Leningrad. Otdel., Leningrad, 1971, 115–133
Linking options:
https://www.mathnet.ru/eng/znsl2402 https://www.mathnet.ru/eng/znsl/v20/p115
|
Statistics & downloads: |
Abstract page: | 193 | Full-text PDF : | 114 |
|