There has been a recent interest in hierarchical generalizations of classic incompleteness results. This paper provides evidence that such generalizations are readily obtainable from suitably formulated hierarchical versions of the principles used in the original proofs. By collecting such principles, we prove hierarchical versions of Mostowski’s theorem on independent formulae, Kripke’s theorem on flexible formulae, Woodin’s theorem on the universal algorithm, and a few related results. As a corollary, we obtain the expected result that the formula expressing “$\mathrm {T}$is$\Sigma _n$-ill” (...) is a canonical example of a$\Sigma _{n+1}$formula that is$\Pi _{n+1}$-conservative over$\mathrm {T}$. (shrink)

Let$\left\langle {{W_n}:n \in \omega } \right\rangle$be a canonical enumeration of recursively enumerable sets, and supposeTis a recursively enumerable extension of PA (Peano Arithmetic) in the same language. Woodin (2011) showed that there exists an index$e \in \omega$(that depends onT) with the property that if${\cal M}$is a countable model ofTand for some${\cal M}$-finite sets,${\cal M}$satisfies${W_e} \subseteq s$, then${\cal M}$has an end extension${\cal N}$that satisfiesT+We=s.Here we generalize Woodin’s theorem to all recursively enumerable extensionsTof the fragment${{\rm{I}\rm{\Sigma }}_1}$of PA, and remove the countability restriction (...) on${\cal M}$whenTextends PA. We also derive model-theoretic consequences of a classic fixed-point construction of Kripke (1962) and compare them with Woodin’s theorem. (shrink)

In this paper we will show that for every cutIof any countable nonstandard model$\mathcal {M}$of$\mathrm {I}\Sigma _{1}$, eachI-small$\Sigma _{1}$-elementary submodel of$\mathcal {M}$is of the form of the set of fixed points of some proper initial self-embedding of$\mathcal {M}$iffIis a strong cut of$\mathcal {M}$. Especially, this feature will provide us with some equivalent conditions with the strongness of the standard cut in a given countable model$\mathcal {M}$of$ \mathrm {I}\Sigma _{1} $. In addition, we will find some criteria for extendability of initial (...) self-embeddings of countable nonstandard models of$ \mathrm {I}\Sigma _{1} $to larger models. (shrink)

Several problems that pertain to certain arithmetically well-behaved countable subsemirings of Λ, the semiring of isols, are discussed. This is relevant to the present volume memorializing the late John Myhill, in that Myhill was an early co-developer of the theory of Λ.