Movatterモバイル変換

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)

Direct download(2 more)   Export citation   Bookmark   1 citation  

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)

Direct download(2 more)   Export citation   Bookmark   2 citations  

Lajevardi and Salehi, in “There may be many arithmetical Gödel sentences”, argue against the use of the definite article in the expression “the Gödel sentence”, by claiming that any unsound theory has Gödelian sentences with different truth values. We show that their Theorems 1 and 2 are special cases (modulo Löb's theorem and the first incompleteness theorem) of general observations pertaining to fixed points of any formula, and argue that the false sentences of Lajevardi and Salehi are in fact not (...) Gödel sentences. (shrink)

Direct download(4 more)   Export citation   Bookmark