Uniform Gödelization
Raymond M. Smullyan · 1993
Abstract We conclude this volume with some pretty applications of recursion and double recursion theorems and some variants of Shepherdson’s arguments. We obtain a substantial strengthening of Shepherdson’s theorem as well as some new results on uniform incompletability, which we now define. Given a consistent axiomatizable system S, we let Sn be that system whose axioms are those of S together with all formulas whose Godel number is in ωn. [We might refer to Sn as the nth extension of S.] We call S uniformly incompletable if there is a formula H(v1) such that for any n for which Sn is consistent, H(n̅) is an undecidable sentence of Sn. [In a sense, for each n for which Sn is consistent, H(n̅) can be thought of as asserting its oωn non-provability in Sn— or more accurately that it is not provable in Sn before it is refutable in Sn.] Marian Pour-El [1968] proved that every consistent axiomatizable extension of (R) is uniformly incompletable (a part of her argument is a variant of the proof of the Putnam-Smullyan theorem). We have been independently working on this problem along entirely different lines which reveal that such systems possess some interesting properties apparently stronger than uniform incompletability. It is to these stronger properties that we first turn. We shall say that S has the sentential recursion property if for every r.e. relation R(x,y) there is a number h such that x : R(x,h) is represented in S by a formula H(v1) whose Godel number is h. Using the weak recursion theorem, we will prove a result that implies that every consistent axiomatizable extension of (R) has the sentential recursion property.