✦ LIBER ✦
On the Difficulty of Writing Out formal Proofs in Arithmetic
✍ Scribed by Ryo Kashima; Takeshi Yamaguchi
- Publisher
- John Wiley and Sons
- Year
- 1997
- Tongue
- English
- Weight
- 266 KB
- Volume
- 43
- Category
- Article
- ISSN
- 0044-3050
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
Let ℸ be the set of Gödel numbers Gn(f) of function symbols f such that PRA ⊢ and let γ be the function such that
We prove: (1) The r. e. set ℸ is m‐complete; (2) the function γ is not primitive recursive in any class of functions {f~1~, f~2~, ⃛} so long as each f~i~ has a recursive upper bound. This implies that γ is not primitive recursive in ℸ although it is recursive in ℸ.