We study the parameterized complexity of the problem to decide whether a given natural number n satisfies a given $\Delta _0$-formula $\varphi (x)$; the parameter is the size of $\varphi $. This parameterization focusses attention on instances where n is large compared to the size of $\varphi $. We show unconditionally that this problem does not belong to the parameterized analogue of $\mathsf {AC}^0$. From this we derive that certain natural upper bounds on the complexity of our parameterized problem imply certain separations of classical complexity classes. This connection is obtained via an analysis of a parameterized halting problem. Some of these upper bounds follow assuming that $I\Delta _0$ proves the MRDP theorem in a certain weak sense.

Wilkie proved in 1977 that every countable model ${\mathcal M}$ of Peano Arithmetic has an elementary end extension ${\mathcal N}$ such that the interstructure lattice $\operatorname {\mathrm {Lt}}({\mathcal N} / {\mathcal M})$ is the pentagon lattice ${\mathbf N}_5$. This theorem implies that every countable nonstandard ${\mathcal M}$ has an elementary cofinal extension ${\mathcal N}$ such that $\operatorname {\mathrm {Lt}}({\mathcal N} / {\mathcal M}) \cong {\mathbf N}_5$. It is proved here that whenever ${\mathcal M} \prec {\mathcal N} \models \mathsf {PA}$ and $\operatorname {\mathrm {Lt}}({\mathcal N} / {\mathcal M}) \cong {\mathbf N}_5$, then ${\mathcal N}$ must be either an end or a cofinal extension of ${\mathcal M}$. In contrast, there are ${\mathcal M}^* \prec {\mathcal N}^* \models \mathsf {PA}^*$ such that $\operatorname {\mathrm {Lt}}({\mathcal N}^* / {\mathcal M}^*) \cong {\mathbf N}_5$ and ${\mathcal N}^*$ is neither an end nor a cofinal extension of ${\mathcal M}^*$.

We introduce self-divisible ultrafilters, which we prove to be precisely those $w$ such that the weak congruence relation $\equiv _w$ introduced by Šobot is an equivalence relation on $\beta {\mathbb Z}$. We provide several examples and additional characterisations; notably we show that $w$ is self-divisible if and only if $\equiv _w$ coincides with the strong congruence relation $\mathrel {\equiv ^{\mathrm {s}}_{w}}$, if and only if the quotient $(\beta {\mathbb Z},\oplus )/\mathord {\mathrel {\equiv ^{\mathrm {s}}_{w}}}$ is a profinite group. We also construct an ultrafilter $w$ such that $\equiv _w$ fails to be symmetric, and describe the interaction between the aforementioned quotient and the profinite completion $\hat {{\mathbb Z}}$ of the integers.

We calculate the possible Scott ranks of countable models of Peano arithmetic. We show that no non-standard model can have Scott rank less than $\omega $ and that non-standard models of true arithmetic must have Scott rank greater than $\omega $. Other than that there are no restrictions. By giving a reduction via $\Delta ^{\mathrm {in}}_{1}$ bi-interpretability from the class of linear orderings to the canonical structural $\omega $-jump of models of an arbitrary completion T of $\mathrm {PA}$ we show that every countable ordinal $\alpha>\omega $ is realized as the Scott rank of a model of T.

A theory T is tight if different deductively closed extensions of T (in the same language) cannot be bi-interpretable. Many well-studied foundational theories are tight, including $\mathsf {PA}$ [39], $\mathsf {ZF}$, $\mathsf {Z}_2$, and $\mathsf {KM}$ [6]. In this article we extend Enayat’s investigations to subsystems of these latter two theories. We prove that restricting the Comprehension schema of $\mathsf {Z}_2$ and $\mathsf {KM}$ gives non-tight theories. Specifically, we show that $\mathsf {GB}$ and $\mathsf {ACA}_0$ each admit different bi-interpretable extensions, and the same holds for their extensions by adding $\Sigma ^1_k$-Comprehension, for $k \ge 1$. These results provide evidence that tightness characterizes $\mathsf {Z}_2$ and $\mathsf {KM}$ in a minimal way.

In this paper we will show that for every cut I of any countable nonstandard model $\mathcal {M}$ of $\mathrm {I}\Sigma _{1}$, each I-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}$ iff I is 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.

We study the first-order consequences of Ramsey’s Theorem for k-colourings of n-tuples, for fixed $n, k \ge 2$ , over the relatively weak second-order arithmetic theory $\mathrm {RCA}^*_0$ . Using the Chong–Mourad coding lemma, we show that in a model of $\mathrm {RCA}^*_0$ that does not satisfy $\Sigma ^0_1$ induction, $\mathrm {RT}^n_k$ is equivalent to its relativization to any proper $\Sigma ^0_1$ -definable cut, so its truth value remains unchanged in all extensions of the model with the same first-order universe.

We give a complete axiomatization of the first-order consequences of $\mathrm {RCA}^*_0 + \mathrm {RT}^n_k$ for $n \ge 3$ . We show that they form a non-finitely axiomatizable subtheory of $\mathrm {PA}$ whose $\Pi _3$ fragment coincides with $\mathrm {B} \Sigma _1 + \exp $ and whose $\Pi _{\ell +3}$ fragment for $\ell \ge 1$ lies between $\mathrm {I} \Sigma _\ell \Rightarrow \mathrm {B} \Sigma _{\ell +1}$ and $\mathrm {B} \Sigma _{\ell +1}$ . We also give a complete axiomatization of the first-order consequences of $\mathrm {RCA}^*_0 + \mathrm {RT}^2_k + \neg \mathrm {I} \Sigma _1$ . In general, we show that the first-order consequences of $\mathrm {RCA}^*_0 + \mathrm {RT}^2_k$ form a subtheory of $\mathrm {I} \Sigma _2$ whose $\Pi _3$ fragment coincides with $\mathrm {B} \Sigma _1 + \exp $ and whose $\Pi _4$ fragment is strictly weaker than $\mathrm {B} \Sigma _2$ but not contained in $\mathrm {I} \Sigma _1$ .

Additionally, we consider a principle $\Delta ^0_2$ - $\mathrm {RT}^2_2$ which is defined like $\mathrm {RT}^2_2$ but with both the $2$ -colourings and the solutions allowed to be $\Delta ^0_2$ -sets rather than just sets. We show that the behaviour of $\Delta ^0_2$ - $\mathrm {RT}^2_2$ over $\mathrm {RCA}_0 + \mathrm {B}\Sigma ^0_2$ is in many ways analogous to that of $\mathrm {RT}^2_2$ over $\mathrm {RCA}^*_0$ , and that $\mathrm {RCA}_0 + \mathrm {B} \Sigma ^0_2 + \Delta ^0_2$ - $\mathrm {RT}^2_2$ is $\Pi _4$ - but not $\Pi _5$ -conservative over $\mathrm {B} \Sigma _2$ . However, the statement we use to witness failure of $\Pi _5$ -conservativity is not provable in $\mathrm {RCA}_0 +\mathrm {RT}^2_2$ .

The current paper studies the formal properties of the Global Reflection Principle, to wit the assertion “All theorems of $\mathrm {Th}$ are true,” where $\mathrm {Th}$ is a theory in the language of arithmetic and the truth predicate satisfies the usual Tarskian inductive conditions for formulae in the language of arithmetic. We fix the gap in Kotlarski’s proof from [15], showing that the Global Reflection Principle for Peano Arithmetic is provable in the theory of compositional truth with bounded induction only ( $\mathrm {CT}_0$ ). Furthermore, we extend the above result showing that $\Sigma _1$ -uniform reflection over a theory of uniform Tarski biconditionals ( $\mathrm {UTB}^-$ ) is provable in $\mathrm {CT}_0$ , thus answering the question of Beklemishev and Pakhomov [2]. Finally, we introduce the notion of a prolongable satisfaction class and use it to study the structure of models of $\mathrm {CT}_0$ . In particular, we provide a new model-theoretical characterization of theories of finite iterations of uniform reflection and present a new proof characterizing the arithmetical consequences of $\mathrm {CT}_0$ .

The complete characterisation of order types of non-standard models of Peano arithmetic and its extensions is a famous open problem. In this paper, we consider subtheories of Peano arithmetic (both with and without induction), in particular, theories formulated in proper fragments of the full language of arithmetic. We study the order types of their non-standard models and separate all considered theories via their possible order types. We compare the theories with and without induction and observe that the theories without induction tend to have an algebraic character that allows model constructions by closing a model under the relevant algebraic operations.

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}$ .

We continue the research of the relation $\hspace {1mm}\widetilde {\mid }\hspace {1mm}$ on the set $\beta \mathbb {N}$ of ultrafilters on $\mathbb {N}$ , defined as an extension of the divisibility relation. It is a quasiorder, so we see it as an order on the set of $=_{\sim }$ -equivalence classes, where $\mathcal {F}=_{\sim }\mathcal {G}$ means that $\mathcal {F}$ and $\mathcal {G}$ are mutually $\hspace {1mm}\widetilde {\mid }$ -divisible. Here we introduce a new tool: a relation of congruence modulo an ultrafilter. We first recall the congruence of ultrafilters modulo an integer and show that $=_{\sim }$ -equivalent ultrafilters do not necessarily have the same residue modulo $m\in \mathbb {N}$ . Then we generalize this relation to congruence modulo an ultrafilter in a natural way. After that, using iterated nonstandard extensions, we introduce a stronger relation, which has nicer properties with respect to addition and multiplication of ultrafilters. Finally, we introduce a strengthening of $\hspace {1mm}\widetilde {\mid }\hspace {1mm}$ and show that it also behaves well with respect to the congruence relation.

We introduce a tool for analysing models of $\text {CT}^-$ , the compositional truth theory over Peano Arithmetic. We present a new proof of Lachlan’s theorem that the arithmetical part of models of $\text {CT}^-$ are recursively saturated. We also use this tool to provide a new proof of theorem from [8] that all models of $\text {CT}^-$ carry a partial inductive truth predicate. Finally, we construct a partial truth predicate defined for a set of formulae whose syntactic depth forms a nonstandard cut which cannot be extended to a full truth predicate satisfying $\text {CT}^-$ .

Let ${\cal T}$ be any of the three canonical truth theories CT− (compositional truth without extra induction), FS− (Friedman–Sheard truth without extra induction), or KF− (Kripke–Feferman truth without extra induction), where the base theory of ${\cal T}$ is PA (Peano arithmetic). We establish the following theorem, which implies that ${\cal T}$ has no more than polynomial speed-up over PA.

Theorem.${\cal T}$is feasibly reducible to PA, in the sense that there is a polynomial time computable function f such that for every${\cal T}$-proof π of an arithmetical sentence ϕ, f (π) is a PA-proof of ϕ.

This paper explores the relationship borne by the traditional paradoxes of set theory and semantics to formal incompleteness phenomena. A central tool is the application of the Arithmetized Completeness Theorem to systems of second-order arithmetic and set theory in which various “paradoxical notions” for first-order languages can be formalized. I will first discuss the setting in which this result was originally presented by Hilbert & Bernays (1939) and also how it was later adapted by Kreisel (1950) and Wang (1955) in order to obtain formal undecidability results. A generalization of this method will then be presented whereby Russell’s paradox, a variant of Mirimanoff’s paradox, the Liar, and the Grelling–Nelson paradox may be uniformly transformed into incompleteness theorems. Some additional observations are then framed relating these results to the unification of the set theoretic and semantic paradoxes, the intensionality of arithmetization (in the sense of Feferman, 1960), and axiomatic theories of truth.

This paper is a follow-up to [4], in which a mistake in [6] (which spread also to [9]) was corrected. We give a strenghtening of the main result on the semantical nonconservativity of the theory of PT− with internal induction for total formulae ${(\rm{P}}{{\rm{T}}^ - } + {\rm{INT}}\left( {{\rm{tot}}} \right)$, denoted by PT− in [9]). We show that if to PT− the axiom of internal induction for all arithmetical formulae is added (giving ${\rm{P}}{{\rm{T}}^ - } + {\rm{INT}}$), then this theory is semantically stronger than ${\rm{P}}{{\rm{T}}^ - } + {\rm{INT}}\left( {{\rm{tot}}} \right)$. In particular the latter is not relatively truth definable (in the sense of [11]) in the former. Last but not least, we provide an axiomatic theory of truth which meets the requirements put forward by Fischer and Horsten in [9]. The truth theory we define is based on Weak Kleene Logic instead of the Strong one.

Simpson [6] showed that every countable model ${\cal M} \models PA$ has an expansion $\left( {{\cal M},X} \right) \models P{A^{\rm{*}}}$ that is pointwise definable. A natural question is whether, in general, one can obtain expansions of a nonprime model in which the definable elements coincide with those of the underlying model. Enayat [1] showed that this is impossible by proving that there is ${\cal M} \models PA$ such that for each undefinable class X of ${\cal M}$, the expansion $\left( {{\cal M},X} \right)$ is pointwise definable. We call models with this property Enayat models. In this article, we study Enayat models and show that a model of $PA$ is Enayat if it is countable, has no proper cofinal submodels and is a conservative extension of all of its elementary cuts. We then show that, for any countable linear order γ, if there is a model ${\cal M}$ such that $Lt\left( {\cal M} \right) \cong \gamma$, then there is an Enayat model ${\cal M}$ such that $Lt\left( {\cal M} \right) \cong \gamma$.

This article bears on four topics: observational predicates and phenomenal properties, vagueness, strict finitism as a philosophy of mathematics, and the analysis of feasible computability. It is argued that reactions to strict finitism point towards a semantics for vague predicates in the form of nonstandard models of weak arithmetical theories of the sort originally introduced to characterize the notion of feasibility as understood in computational complexity theory. The approach described eschews the use of nonclassical logic and related devices like degrees of truth or supervaluation. Like epistemic approaches to vagueness, it may thus be smoothly integrated with the use of classical model theory as widely employed in natural language semantics. But unlike epistemicism, the described approach fails to imply either the existence of sharp boundaries or the failure of tolerance for soritical predicates. Applications of measurement theory (in the sense of Krantz, Luce, Suppes, & Tversky (1971)) to vagueness in the nonstandard setting are also explored.

Gödel introduced the original provability predicate in the proofs of Gödel’s incompleteness theorems, and Rosser defined a new one. They are equivalent in the standard model ${\mathbb N}$ of arithmetic or any nonstandard model of ${\rm PA} + {\rm Con_{PA}} $, but the behavior of Rosser’s provability predicate is different from the original one in nonstandard models of ${\rm PA} + \neg {\rm Con_{PA}} $. In this paper, we investigate several properties of the derivability conditions for Rosser provability predicates, and prove the existence of a Rosser provability predicate with which we can define any consistent complete extension of ${\rm PA}$ in some nonstandard model of ${\rm PA} + \neg {\rm Con_{PA}} $. We call it a universal Rosser predicate. It follows from the theorem that the true arithmetic ${\rm TA}$ can be defined as the set of theorems of ${\rm PA}$ in terms of a universal Rosser predicate in some nonstandard model of ${\rm PA} + \neg {\rm Con_{PA}} $. By using this theorem, we also give a new proof of a theorem that there is a nonstandard model M of ${\rm PA} + \neg {\rm Con_{PA}} $ such that if N is an initial segment of M which is a model of ${\rm PA} + {\rm Con_{PA}} $ then every theorem of ${\rm PA}$ in N is a theorem of $\rm PA$ in ${\mathbb N}$. In addition, we prove that there is a Rosser provability predicate such that the set of theorems of $\rm PA$ in terms of the Rosser provability predicate is inconsistent in any nonstandard model of ${\rm PA} + \neg {\rm Con_{PA}} $.

Let $\left\langle {{W_n}:n \in \omega } \right\rangle$ be a canonical enumeration of recursively enumerable sets, and suppose T is 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 on T) with the property that if${\cal M}$ is a countable model of T and for some${\cal M}$-finite set s, ${\cal M}$ satisfies ${W_e} \subseteq s$, then${\cal M}$ has an end extension${\cal N}$ that satisfies T + We = s.

Here we generalize Woodin’s theorem to all recursively enumerable extensions T of the fragment ${{\rm{I}\rm{\Sigma }}_1}$ of PA, and remove the countability restriction on ${\cal M}$ when T extends PA. We also derive model-theoretic consequences of a classic fixed-point construction of Kripke (1962) and compare them with Woodin’s theorem.

This paper addresses the structures (M, ω) and (ω, SSy(M)), where M is a nonstandard model of PA and ω is the standard cut. It is known that (ω, SSy(M)) is interpretable in (M, ω). Our main technical result is that there is an reverse interpretation of (M, ω) in (ω, SSy(M)) which is ‘local’ in the sense of Visser [11]. We also relate the model theory of (M, ω) to the study of transplendent models of PA [2].

This yields a number of model theoretic results concerning the ω-models (M, ω) and their standard systems SSy(M, ω), including the following.

• $\left( {M,\omega } \right) \prec \left( {K,\omega } \right)$ if and only if $M \prec K$ and $\left( {\omega ,{\rm{SSy}}\left( M \right)} \right) \prec \left( {\omega ,{\rm{SSy}}\left( K \right)} \right)$.

• $\left( {\omega ,{\rm{SSy}}\left( M \right)} \right) \prec \left( {\omega ,{\cal P}\left( \omega \right)} \right)$ if and only if $\left( {M,\omega } \right) \prec \left( {{M^{\rm{*}}},\omega } \right)$ for some ω-saturated M*.

• $M{ \prec _{\rm{e}}}K$ implies SSy(M, ω) = SSy(K, ω), but cofinal extensions do not necessarily preserve standard system in this sense.

• SSy(M, ω)=SSy(M) if and only if (ω, SSy(M)) satisfies the full comprehension scheme.

• If SSy(M, ω) is uniformly defined by a single formula (analogous to a β function), then (ω, SSy(M, ω)) satisfies the full comprehension scheme; and there are models M for which SSy(M, ω) is not uniformly defined in this sense.