betaFeedback

WorksMathematics

Self-Interpretations and Kraj'ı{č}ek-Theories

Abstract

We study self-interpretations of theories and their connection to Kraj'ıček-theories. Our two main results are the following. Firstly, if the self-interpretations of a theory form a group in the category INT3{\sf INT}_3 of theories and interpretations, then the theory is a Kraj'ıček-theory. Secondly, a sequential theory is a Kraj'ıček-theory iff all its self-interpretations are initial. Here initiality of the interpretation KK means roughly that its internal interpretations of the weak theory S21{\sf S}^1_2 are initial in all interpretations of S21{\sf S}^1_2.

Introduction

In this paper, we study self-interpretations of theories and their connection with Krajíček-theories. Self-interpretations can best be seen as endomorphisms in categories of theories and interpretations. In this paper, we focus on two such categories. The first is INT1\mathrm{INT}_1, the category in which two interpretations KK and MM of VV in UU are the same iff there is a UU-definable, UU-verifiable isomorphism between KK and MM. The second is INT3\mathrm{INT}_3, the category in which two interpretations KK and MM of VV in UU are the same iff, for all VV-sentences φ\varphi, we have U⊢φK↔φMU \vdash\varphi^{K} \leftrightarrow\varphi^{M}. There are three properties of the self-interpretations of a theory that we will consider.

  • All self-interpretations are equal to the identity. This means that the endomorphism monoid of the given theory trivialises. A theory that has this property in INTi\mathrm{INT}_i will be called iii_i-rigid. The i1i_1-rigid theories will also be called interpretation categorical. The i3i_3-rigid theories will also be called sententially interpretation-rigid.

  • All self-interpretations are invertible. In other words, the endomorphism monoid forms a group. A theory that has this property in INTi\mathrm{INT}_i will be called iii_i-invertible. We note that the invertible interpretations in INT1\mathrm{INT}_1 are bi-interpretations and that the invertible interpretations in INT3\mathrm{INT}_3 are sentential congruences (also: elementary congruences).

  • All self-interpretations are initial. The property of initiality will be introduced in Section 5. Roughly, K:U▹UK : U \triangleright U is initial iff, for all interpretations of the weak theory S21\mathrm{S}^{1}_{2} in UU, there is an interpretation MM of S21\mathrm{S}^{1}_{2} in UU such

Key words and phrases. interpretations, elementary equivalence, isomorphism, categoricity, invertible endomorphisms.

We are grateful to the audience of the Interpretations workshop Lugano, October 8-9, 2026 and to Mateusz Łełyk for his talk at this workshop. The interest of the audience and Mateusz’s presentation made me think about interpretation categoricity and related concepts. I thank Mateusz Łełyk and Benjamin Zayton for their interest in this project and their comments. Benjamin provided some helpful examples. that K∘MK \circ M is below NN. We will show that a sequential theory is a Krajíček-theory iff all its self-interpretations are initial. We will also introduce a notion of strong initiality and prove that a sequential theory is a Krajíček-theory iff all its self-interpretations are strongly initial.

Krajíček-theories form a broad group. The basic idea is, roughly, that a Krajíček-theory proves an instance of its own restricted inconsistency for every interpretation of a designated weak arithmetical theory. We note that, for example, all decidable theories are Krajíček-theories, since they simply do not interpret the designated weak arithmetical theory. The Krajíček-theories cannot be foundational theories like Peano Arithmetic or Zermelo-Fraenkel Set Theory because of their Σ10\Sigma^0_1-unsoundness. Still, we submit, they are very interesting theories that contribute to getting a full picture of what is possible in the presence of enough coding.

Our paper has two main results. First, in Section 4, we show that every ι3\iota_3-invertible theory is a Krajíček-theory. Then, in Section 5, we prove a characterisation of sequential Krajíček-theories in terms of the initiality of their self-interpretations. We also prove a slightly different version of the characterisation in terms of strong initiality.

One reason to be interested in invertibility is that it is implied by rigidity. We easily see that ι1\iota_1-rigidity implies ι3\iota_3-rigidity and that ι3\iota_3-rigidity implies ι3\iota_3-invertibility. The concept of ι1\iota_1-rigidity is a salient notion. It was recently studied by Mirko Engler and Benjamin Zayton in their paper [3]. Engler and Zayton provide many examples in addition to some discussion of the meaning of the concept.

An application of rigidity is the insight that, if a theory is ι1\iota_1-rigid and interpretable in a finite sub-theory, then it is finitely axiomatisable.1 See [Zoe15] and [3]. Fedor Pakhomov and Alexander Zapryagaev in [8] show that Presburger Arithmetic is ι1\iota_1-rigid. In combination with the fact that it is not finitely axiomatisable, we see that Presburger Arithmetic is not interpretable in a finite sub-theory. See [10 III.4] (especially Exercise 13) and [Zoe15] for a proof of non-finite axiomatisability. In contrast, Presburger Arithmetic is locally interpretable in a finitely axiomatised sub-theory.2

We introduce Krajíček-theories in Section 3. In this section we also present some salient earlier results. For example, we repeat a result from [12 Appendix C] that shows that the predicate logic of a c.e. Krajíček-theory is Π20\Pi^0_2-complete. In Section 4, we prove that ι3\iota_3-invertibility implies being a Krajíček-theory. Finally, in Section 5, we characterise sequential Krajíček-theories in terms of the behaviour of their self-interpretations.

AI Statement

ChatGPT and Claude diligently found typos and small mistakes in previous versions of this paper. Also, they gave helpful naming advice. ChatGPT provided Example 4.1 and it directed my attention to Theorem 4.2. All the further results of the paper are my own.

Basic Facts and Basic Definitions

In this section, we lay the groundwork for the rest of the paper. Of course, the reader can touch upon each subsection lightly, to return to it when needed. In Section 5, we will need more heavy machinery. We will introduce these further instruments in the section itself.

Theories

A theory in this paper will be a c.e. theory in predicate logic of finite signature. We will assume that the axiom sets of theories are simple, say given by a Δ1b\Delta^{b}_{1}-predicate, so that we do not have to worry that the representation of the axiom set adds extra complexity to the proof-predicate.

The theories RR and S21S_{2}^{1} will play a special role in this paper. The theory S21S_{2}^{1} was introduced by Sam Buss in [1]. See also [4]. Buss’ theory is a weak theory that is mutually interpretable with such theories as QQ and PA−\mathrm{PA}^{-}. On the other hand, it is an ideal basis for the arithmetisation of metamathematics. The theory RR was introduced in [11]. Since, we will see some actual reasoning in RR, we reproduce its axioms here. For m,n∈ωm,n \in\omega we have:

R1. m‾+n‾=m+n‾\overline{m}+\overline{n}=\overline{m+n}

R2. m‾×n‾=m×n‾\overline{m}\times\overline{n}=\overline{m\times n}

R3. m‾≠n‾\overline{m}\ne\overline{n} (if m≠nm\ne n)

R4. ∀x(x≤n‾→⋁i≤nx=i‾)\forall x\left(x\le\overline{n}\to\bigvee_{i\le n}x=\overline{i}\right)

R5. ∀x(x≤n‾∨n‾≤x)\forall x\left(x\le\overline{n}\vee\overline{n}\le x\right)

In the Tarski-Mostowski-Robinson book, the relation ≤\le is defined, but this is not really needed and we take it as primitive here.

Interpretations and Interpretability

Most of my papers contain a section describing the basics of interpretations and interpretability. See, e.g., [17 Appendix A]. We just give some highlights here.

An interpretation KK is based on a translation τ\tau of languages.

We write K:U▹VK:U\triangleright V for: KK is an interpretation of VV in UU, and U▹VU\triangleright V for: there is an interpretation K:U▹VK:U\triangleright V.

We will diverge a bit from the usual practice by also using τ:U▹V\tau:U\triangleright V with as meaning: there is an interpretation K:U▹VK:U\triangleright V with underlying translation KK. The reason we use this is to avoid having to name different interpretations with the same underlying translation.

We remind the reader of disjunctive interpretations. Suppose K:(U+φ)▹VK:(U+\varphi)\triangleright V and M:(U+¬φ)▹VM:(U+\neg\varphi)\triangleright V. Then K⟨φ⟩M:U▹VK\langle\varphi\rangle M:U\triangleright V is the disjunctive interpretation that coincides with KK if φ\varphi and with MM if ¬φ\neg\varphi.

Suppose UU and VV are theories in the same language and the theorems of VV are contained in the theorems of UU. We write EVU:U▹VE_{VU}:U\triangleright V for the interpretation based on the identical translation.

Suppose N:U▹RN:U\triangleright R. An interpretation K:U▹VK:U\triangleright V is NN-restricted iff there is a UU-formula θ(x)\theta(x), such that, for all φ\varphi, we have U⊢θ(⌜φ⌝)↔φKU\vdash\theta(\ulcorner\varphi\urcorner)\leftrightarrow\varphi^{K}. Here the numerals come from NN. The interpretation KK is restricted iff it is NN-restricted, for some NN. The present notion is weaker than the notion of bounded interpretation from [13]. We provide a stronger version in Section 5. We write K:U▹resVK:U\triangleright_{\mathrm{res}}V, for restricted interpretability. We have:

Theorem 2.1.

  • If U▹V▹resWU\triangleright V\triangleright_{\mathrm{res}}W, then U▹resWU\triangleright_{\mathrm{res}}W.

  • If U▹resV▹WU\triangleright_{\mathrm{res}}V\triangleright W, then U▹resWU\triangleright_{\mathrm{res}}W.

We leave the simple verification to the reader. Let

  • S(U):=S21+{con⁡n(U)∣n∈ω}\mathcal{S}(U) := S^1_2 + \{\operatorname{con}_n(U) \mid n \in\omega\}.

Here con⁡n\operatorname{con}_n means consistency from the axioms with Gödel numbers ≤n\leq n where only formulas of depth-of-quantifier complexity ≤n\leq n are allowed in the proofs. We have:

Theorem 2.2 (Interpretation Existence Lemma). We have: S(U)▹resU\mathcal{S}(U) \triangleright_{\mathrm{res}} U.

For a proof see [18]. See also [13]. The present formulation is a convenient version for most of our purposes, however, we can articulate much stronger versions. We will meet a stronger version in Section 5, to wit Theorem 5.4.

An interpretation is direct if it is one-dimensional, its domain is the full domain of the interpreting theory and it translates identity to identity of the interpreting theory.

There are two categories of theories and interpretations relevant for this paper. In the context of the categories, we usually write K:V→UK : V \to U for K:U▹VK : U \triangleright V. The first category is INT1\mathrm{INT}_1. In this category, two interpretations K,M:V→UK, M : V \to U are the same if there is an UU-definable, UU-verifiable isomorphism between KK and MM. Isomorphism of theories in this category is bi-interpretation. The second is INT3\mathrm{INT}_3. In this category, two interpretations K,M:V→UK, M : V \to U are the same if, for all VV-sentences ψ\psi, we have U⊢ψK↔ψMU \vdash\psi^K \leftrightarrow\psi^M. Isomorphism of theories in this category is elementary congruence or sentential congruence.

Sequentiality

A theory is sequential if it has a good theory of sequences, where sequences are sequences of all objects and where we can internally add an element to a sequence. Via a long bootstrap, we can prove that a theory is sequential iff it directly interprets the very weak set theory AS. This was first proved in its most general form in [6]. See [Vis13] for an exposition and more of the history of the result.

An important property of sequential theories is local reflexivity. Suppose UU is sequential. Then, for any nn, there is an N:U▹(S21+con⁡n(U))N : U \triangleright(S^1_2 + \operatorname{con}_n(U)). This property can be proven using the methodology of shortening cuts in combination with the existence of partial satisfaction predicates. See, e.g., [19 Section 2].

Witness Comparison

Suppose φ\varphi is of the form ∃x φ0(x)\exists x\,\varphi_0(x) and ψ\psi is of the form ∃y ψ0(y)\exists y\,\psi_0(y). We define:

  • φ≤ψ: ⁣  ⟺  ∃x (φ0(x)∧∀y<x ¬ψ0(y))\varphi\leq\psi:\!\iff\exists x\,(\varphi_0(x) \land\forall y < x\,\neg\psi_0(y)).

  • φ<ψ: ⁣  ⟺  ∃x (φ0(x)∧∀y≤x ¬ψ0(y))\varphi< \psi:\!\iff\exists x\,(\varphi_0(x) \land\forall y \leq x\,\neg\psi_0(y)).

  • (φ≤ψ)⊥: ⁣  ⟺  ψ<φ(\varphi\leq\psi)^\bot:\!\iff\psi< \varphi.

  • (φ<ψ)⊥: ⁣  ⟺  ψ≤φ(\varphi< \psi)^\bot:\!\iff\psi\leq\varphi.

Krajíček-Theories

The c.e. theory UU is a Krajíček-theory iff, for every N:U▹S21N : U \triangleright S^1_2, there is a kk such that U⊢incon⁡kN(U)U \vdash\operatorname{incon}^{N}_{k}(U). These theories are named after Jan Krajíček, who introduced the basic idea in [Kra87, Section 3]. Our notion is broader than the original one. First, we do not restrict ourselves to sequential theories and, secondly, we do not restrict ourselves to theories constructed from finitely axiomatised ones (as is done in our Section 3.1).

One of Krajíček’s results in [Kra87] implies that consistent sequential Krajíček-theories cannot be finitely axiomatisable.

We prove two basic theorems about the preservation of Krajíček-theories.

Theorem 3.1. Suppose UU is a Krajíček-theory and VV is an INT3\mathrm{INT}_{3}-retract of UU. Then, VV is a Krajíček-theory.

Proof. Let K:U▹VK: U \triangleright V and M:V▹UM: V \triangleright U and, for all VV-sentences ψ\psi, V⊢ψ↔ψMKV \vdash\psi\leftrightarrow\psi^{MK}. Suppose N:V▹S21N: V \triangleright S^{1}_{2}. It follows that K∘N:U▹S21K \circ N: U \triangleright S^{1}_{2}. So, for some kk, we have U⊢incon⁡kNK(U)U \vdash\operatorname{incon}^{NK}_{k}(U). Thus, V⊢incon⁡kNKM(U)V \vdash\operatorname{incon}^{NKM}_{k}(U). We may conclude V⊢incon⁡kN(U)V \vdash\operatorname{incon}^{N}_{k}(U).

Using MM we can transform a UU-proof of inconsistency into a VV-proof of inconsistency. We note that the translated proof from the translated UU-axioms can be executed in p-time. This leads to a verification in S21S^{1}_{2}. Moreover, the translation only adds a standard constant to the complexity of the formulas. Finally, we have only to worry about standardly many VV-axioms. It follows that V⊢incon⁡k∗N(V)V \vdash\operatorname{incon}^{N}_{k^{*}}(V), for some standard k∗k^{*}.

The following result is a bit messy, but it does deliver the desired goods.

Theorem 3.2. Suppose UU is a sub-theory of VV (qua theorems, in the same language) and U▹S21U \triangleright S^{1}_{2}. Suppose further that for every N:U▹S21N: U \triangleright S^{1}_{2}, there is an nn such that V⊢incon⁡nN(U)V \vdash\operatorname{incon}^{N}_{n}(U). Then, VV is a Krajíček-theory.

We will use translations rather than interpretations to realise the proof.

Proof. We assume the conditions of the theorem.

Let ν∗:U▹S21\nu^{*}: U \triangleright S^{1}_{2}. Suppose ν:V▹S21\nu: V \triangleright S^{1}_{2}. Then, for some φ\varphi with V⊢φV \vdash\varphi, we have ν:(U+φ)▹S21\nu: (U+\varphi) \triangleright S^{1}_{2}. Let ν∘:=ν⟨φ⟩ν∗:U▹S21\nu^{\circ}:=\nu\langle\varphi\rangle\nu^{*}: U \triangleright S^{1}_{2}. It follows that, for some nn, V⊢incon⁡nν∘(U)V \vdash\operatorname{incon}^{\nu^{\circ}}_{n}(U) and, thus, V⊢incon⁡nν(U)V \vdash\operatorname{incon}^{\nu}_{n}(U). Suppose the VV-axioms needed to prove the UU-axioms ≤n\le n are all ≤m\le m and let k:=max⁡(m,n)k:=\max(m,n). Then, V⊢incon⁡kν(V)V \vdash\operatorname{incon}^{\nu}_{k}(V).

Corollary 3.3. Let UU be a sub-theory of VV and suppose UU is Krajíček. Then, VV is Krajíček.

Extension to a Krajíček-Theory

In this subsection we show that if AA is finitely axiomatized, then we can locally interpret a Krajíček theory extending AA in AA. This result, applied to sequential theories, establishes the existence of Krajíček-theories in the sequential realm.

We first need an auxiliary result from [15], to wit a restricted version of Feferman’s Theorem on the interpretability of inconsistency for finitely axiomatised theories. Let AA be finitely axiomised. We write ρ(φ)\rho(\varphi) for the depth-of-quantifier-alternations complexity of φ\varphi and ρ(N)\rho(N) for the maximum of the ρ\rho-complexities of the formulas involved in the indwelling translation of NN. The standard constant cc just depends on details of the coding and the direct interpretation witnessing sequentiality. This tells us that the result will be preserved to finite extensions of AA.

Theorem 3.4. Suppose N:A▹S21N: A \triangleright S^{1}_{2} and n≥max⁡(ρ(A),ρ(N)+c)n \ge\max(\rho(A),\rho(N)+c). Then, we have A▹(A+incon⁡nN(A))A \triangleright(A+\operatorname{incon}^{N}_{n}(A)).

With Theorem 3.4 in hand, we prove the following theorem.

Theorem 3.5. Let AA be finitely axiomatized. Then, a c.e. theory U:=A+{incon⁡nkNk(A)∣k∈ω}U:=A+\{\operatorname{incon}^{N_k}_{n_k}(A)\mid k\in\omega\} is locally interpretable in AA. Here NkN_k enumerates the N:A▹S21N: A\triangleright S^{1}_{2} and nkn_k is some effective sequence of natural numbers. Moreover, UU is a Krajíček-theory.

We note that we prove a bit more than Krajíček in his [Kra87, Theorem 3.0], since we do not have to restrict ourselves to the sequential case. The reason for that is that Feferman’s idea of interpretability of inconsistency does not demand sequentiality.

Proof. In case A▹̸S21A \not\triangleright S_{2}^{1}, the desired result is trivial. We take U:=AU := A. Suppose A▹S21A \triangleright S_{2}^{1}. Let Nk:A▹S21N_k : A \triangleright S_{2}^{1} enumerate the interpretations N:A▹S21N : A \triangleright S_{2}^{1}. The indwelling translations of the NkN_k are νk\nu_k. Then, we can find sequences K0,K1,…K_0, K_1, \ldots and n0,n1,…n_0, n_1, \ldots such that, for every kk, we have: Kk:A▹(A+⋀i<kincon⁡niNi(A))K_k : A \triangleright(A + \bigwedge_{i<k} \operatorname{incon}_{n_i}^{N_i}(A)). The indwelling translations of the KkK_k will be κk\kappa_k.

We produce the KkK_k and nkn_k in stages. At stage kk we produce KkK_k and at stage k+1k+1 we construct nkn_k.

At stage 0, we take K0:=IDAK_0 := \mathrm{ID}_A. We consider stage k+1k+1. We are given Kk:A▹(A+⋀i<kincon⁡niNi(A))K_k : A \triangleright(A + \bigwedge_{i<k} \operatorname{incon}_{n_i}^{N_i}(A)). Clearly, κk∘νk:A▹S21\kappa_k \circ\nu_k : A \triangleright S_{2}^{1}. By Theorem 3.4, we can effectively find an nkn_k and an MM such that M:A▹(A+incon⁡nkνkκk(A))M : A \triangleright(A + \operatorname{incon}_{n_k}^{\nu_k\kappa_k}(A)). Let the indwelling translation of MM be μ\mu. We find that A⊢(⋀i<kincon⁡niνi(A))κkA \vdash(\bigwedge_{i<k} \operatorname{incon}_{n_i}^{\nu_i}(A))^{\kappa_k}. So, it follows that:

A⊢(⋀i<kincon⁡niνi(A))κkμ∧incon⁡nkνkκkμ(A)A \vdash\left(\bigwedge_{i<k} \operatorname{incon}_{n_i}^{\nu_i}(A)\right)^{\kappa_k\mu} \wedge\operatorname{incon}_{n_k}^{\nu_k\kappa_k\mu}(A)
⊢(⋀i<k+1incon⁡niνi(A))κkμ\vdash\left(\bigwedge_{i<k+1} \operatorname{incon}_{n_i}^{\nu_i}(A)\right)^{\kappa_k\mu}

So, we find the desired Kk+1K_{k+1} with translation μ∘κk\mu\circ\kappa_k. We may conclude that A▹loc(A+{incon⁡nkNk(A)∣k∈ω})A \triangleright_{\mathrm{loc}} (A + \{\operatorname{incon}_{n_k}^{N_k}(A) \mid k \in\omega\}).

Finally, UU is indeed a Krajíček-theory. If A▹̸S21A \not\triangleright S_{2}^{1}, we are immediately done. If A▹S21A \triangleright S_{2}^{1}, the desired result follows from Theorem 3.2. □\square

We note that if τi\tau_i is an enumeration of translations of the signature or arithmetic to the signature of AA and if σ\sigma carries an interpretation of S21S_{2}^{1} in AA, then we can effectively enumerate translations supporting the NiN_i as τi⟨(S21)τi⟩σ\tau_i\langle(S_{2}^{1})^{\tau_i}\rangle_{\sigma}. Thus our axiomatization of UU can be made decidable.

Remark 3.6. We note that every finitely axiomatised AA model-interprets in a sense a Krajíček-variant. Consider any model M\mathcal{M} of AA. In case all interpretations of S21S_{2}^{1} in M\mathcal{M} contain incon⁡n(A)\operatorname{incon}_n(A), for some nn, the identical interpretation gives us a Krajíček-extension of AA. If not, there is an NN in M\mathcal{M} in which we have □A\square_A. Using this we can construct an internal model of a Krajíček-extension since local interpretability in AA implies global interpretability in □A\square_A. However, in the first case, we do not always have the same theory. Moreover, these theories could fail to be c.e.

The Predicate Logic of a Krajíček-Theory

We consider the predicate logical schemes valid for all substitutions in UU. We call these schemes ΛU\Lambda_U, where we suppress the chosen signature. We could look at schemes for relativised interpretations of predicate logic but also at schemes for direct interpretations, where we do not use the original theory S21S_{2}^{1} but its translation to a relativised format where identity becomes an equivalence relation. We will assume relativised interpretation here.

Let α\alpha be a single sentence expressing the axioms of S21S_{2}^{1} including the axioms of identity. We can also use e.g. Adjunctive Set Theory, a theory with just one binary predicate.

Theorem 3.7. Let UU be a consistent Krajíček-theory. Suppose U▹S21U \triangleright S^1_2. Then, ΛU⊢α→incon⁡(U)\Lambda_U \vdash\alpha\to\operatorname{incon}(U).

Proof. Suppose N0:U▹S21N_0 : U \triangleright S^1_2. Let KK be any interpretation of predicate logic in the desired signature in UU. Let τ0\tau_0 be the indwelling translation of N0N_0 and let τ\tau be the indwelling translation of KK. Consider τ∗:=τ⟨ατ⟩τ0\tau^* := \tau\langle\alpha^\tau\rangle\tau_0. Clearly, τ∗\tau^* supports an interpretation K∗K^* of S21S^1_2. It follows that U⊢incon⁡K∗(U)U \vdash\operatorname{incon}_{K^*}(U), since U⊢incon⁡kK∗(U)U \vdash\operatorname{incon}_{k}^{K^*}(U), for some kk. So, U⊢(α→incon⁡(U))KU \vdash(\alpha\to\operatorname{incon}(U))^K.

Example 3.8. Consider predicate logic with at least a binary predicate symbol. Clearly, this is a Krajíček-theory. However, its schematic logic is simply ordinary predicate logic.

The following result is taken from [12 Appendix C]. We repeat it, since the results of the present paper give it new relevance.

Theorem 3.9. Suppose UU is a consistent sequential Krajíček-theory. Then, ΛU\Lambda_U is Π20\Pi^0_2-complete.

Proof. Since UU is sequential, there is an N0:U▹S21N_0 : U \triangleright S^1_2. We fix N0N_0 with indwelling translation τ0\tau_0.

Let σ(x)\sigma(x) be any Σ10\Sigma^0_1-formula. We find a ρ(x)\rho(x) such that

S21⊢ρ(x)↔(σ(x)≤∃Nprov⁡U(⌜(α∧ρ(x˙))N⌝)).S^1_2 \vdash\rho(x) \leftrightarrow\left(\sigma(x) \leq\exists N \operatorname{prov}_U\left(\ulcorner(\alpha\wedge\rho(\dot{x}))^N\urcorner\right)\right).

Here we assume that the ∃N\exists N and the witness of prov⁡\operatorname{prov} are combined in one existential quantifier. We show that:

A. σ(n)\sigma(n) is true iff ρ(n)\rho(n) is true.

B. σ(n)\sigma(n) is true iff, for some N:U▹S21N : U \triangleright S^1_2, we have U⊢ρN(n)U \vdash\rho^N(n).

We first prove (A). The right-to-left direction is trivial. We show left-to-right. Suppose σ(n)\sigma(n) is true. Then, ρ(n)\rho(n) is true or ρ⊥(n)\rho^\bot(n) is true. In the first case we are done. In the second case we have, U⊢ρN(n)U \vdash\rho^N(n), for some N:U▹S21N : U \triangleright S^1_2, by the definition of ρ⊥\rho^\bot. But, by Σ10\Sigma^0_1-completeness, we also have U⊢ρ⊥N(n)U \vdash\rho^{\bot N}(n). So, UU would be inconsistent. Quod non.

We prove (B). Suppose σ(n)\sigma(n) is true. Then, by (A), we find that ρ(n)\rho(n) is true. So, U⊢ρN0(n)U \vdash\rho^{N_0}(n). In the other direction, suppose N:U▹S21N : U \triangleright S^1_2, and U⊢ρN(n)U \vdash\rho^N(n). It follows that ρ(n)\rho(n) is true or ρ⊥(n)\rho^\bot(n) is true. In the first case we are immediately done. In the second case, we get a contradiction via Σ10\Sigma^0_1-completeness as before.3

We claim that

∀x σ(x) is true iff ΛU⊢α→∃y(incon⁡y(U)∧∀x≤y ρ(x)).\forall x\ \sigma(x)\text{ is true iff }\Lambda_U \vdash\alpha\to\exists y\left(\operatorname{incon}_y(U) \wedge\forall x \leq y\ \rho(x)\right).

Suppose that ∀x σ(x)\forall x\ \sigma(x) is true. Let KK be any interpretation of predicate logic in the desired signature in UU with indwelling translation τ\tau. We consider the translation τ∗:=τ⟨ατ⟩τ0\tau^* := \tau\langle\alpha^\tau\rangle\tau_0. Clearly, τ∗\tau^* supports an interpretation K∗:U▹S21K^*: U \triangleright S^1_2. It follows that, for some kk, we have U⊢incon⁡kK∗(U)U \vdash\operatorname{incon}^{K^*}_k(U). By (A), we have ∀x ρ(x)\forall x\ \rho(x) is true. So, certainly:

U⊢(incon⁡k(U)∧∀x≤k ρ(x))K∗U \vdash\left(\operatorname{incon}_k(U) \wedge\forall x \leq k\ \rho(x)\right)^{K^*}

and, thus, U⊢(∃y(incon⁡y(U)∧∀x≤y ρ(x)))K∗U \vdash\left(\exists y\left(\operatorname{incon}_y(U) \wedge\forall x \leq y\ \rho(x)\right)\right)^{K^*}.

We may conclude that U⊢(α→∃y(incon⁡y(U)∧∀x≤y ρ(x)))KU \vdash\left(\alpha\to\exists y\left(\operatorname{incon}_y(U) \wedge\forall x \leq y\ \rho(x)\right)\right)^K.

We prove the converse. Suppose (†) ΛU⊢α→∃y (incon⁡y(U)∧∀x≤y ρ(x))(\dagger)\ \Lambda_U \vdash\alpha\to\exists y\ (\operatorname{incon}_y(U) \land\forall x \leq y\ \rho(x)). We show that, for any kk, the sentence ∀x≤k σ(x)\forall x \leq k\ \sigma(x) is true. By local reflexivity, there is an N:U▹S21N : U \triangleright S^1_2, such that U⊢con⁡kN(U)U \vdash\operatorname{con}^{N}_{k}(U). By (†)(\dagger), we find that

U⊢(∃y(incon⁡y(U)∧∀x≤y ρ(x)))N.U \vdash\left(\exists y\left(\operatorname{incon}_y(U) \land\forall x \leq y\ \rho(x)\right)\right)^N.

Since U⊢((con⁡k(U)∧incon⁡y(U))→y<k)NU \vdash\left((\operatorname{con}_k(U) \land\operatorname{incon}_y(U)) \to y < k\right)^N, it follows that, U⊢(∀x≤k ρ(x))NU \vdash\left(\forall x \leq k\ \rho(x)\right)^N. By (B), we may conclude that ∀x≤k σ(x)\forall x \leq k\ \sigma(x) is true. ❑

We note that the above proof already works for locally reflexive Krajíček-theories.

Invertible Theories are Krajíček

In this section, we prove one of the two main results of this paper: invertible theories are Krajíček.

Basic Definitions

We repeat the basic definitions.

  • The theory UU is ıi\imath_i-rigid iff its endomorphism monoid in INTi\mathrm{INT}_i is trivial, i.e., all self-interpretations of UU are INTi\mathrm{INT}_i-equal to the identity. We say that UU is interpretation-categorical if it is ı1\imath_1-rigid and that it is sententially interpretation-rigid if it is ı3\imath_3-rigid.

  • The theory UU is ıi\imath_i-invertible iff its endomorphism monoid in INTi\mathrm{INT}_i is a group. We note that UU is ı1\imath_1-invertible iff all its self-interpretations are bi-interpretations and that it is ı3\imath_3-invertible iff all its self-interpretations are sentential congruences.

The following example is a modification suggested by ChatGPT of a counterexample to rigidity proposed by Benjamin Zayton.

Example 4.1. Consider the theory DLO of dense linear orderings without endpoints. This theory is complete and hence decidable. So it is, trivially, ı3\imath_3-rigid and also a Krajíček-theory.

Let K:DLO▹DLOK : \mathrm{DLO} \triangleright\mathrm{DLO} be given by:

  • δK(x,y): ⁣  ⟺  ⊤\delta_K(x,y) :\!\iff\top,

  • (x,y)=K(u,v): ⁣  ⟺  (x=u∧y=v)(x,y) =_K (u,v) :\!\iff(x=u \land y=v),

  • (x,y)≤K(u,v): ⁣  ⟺  (x<u∨(x=u∧y≤v))(x,y) \leq_K (u,v) :\!\iff(x<u \lor(x=u \land y\leq v)).

Consider the models Q\mathbb{Q} and Q×lexQ\mathbb{Q} \times_{\mathrm{lex}} \mathbb{Q}. The interpretation KK yields a mapping F:f↦λxy.(f(x),f(y))F : f \mapsto\lambda xy.(f(x),f(y)) of automorphisms. It is easy to see that FF is not surjective. However, if KK had an INT1\mathrm{INT}_1-inverse, FF would have to be an isomorphism. So, DLO is not ı1\imath_1-invertible.

The following basic result was pointed out to me by ChatGPT.

Theorem 4.2. Let CC be a category and suppose the endomorphism monoid of bb is a group. Suppose aa is a retract of bb. Then, aa is isomorphic to bb and, hence, the endomorphism monoid of aa is also a group.

Proof. Suppose f:a→bf : a \to b and g:b→ag : b \to a and g∘f=id⁡ag \circ f = \operatorname{id}_a. It follows that (f∘g)∘(f∘g)=f∘(g∘f)∘g=f∘g(f \circ g) \circ(f \circ g) = f \circ(g \circ f) \circ g = f \circ g. But, by assumption, f∘gf \circ g is invertible, so it must be id⁡b\operatorname{id}_b. ❑

Thus we may conclude that properties like ıi\imath_i-rigidity and ıi\imath_i-invertibility are preserved to retracts, since the retracts will be isomorphisms.

The Main Development

We need two theorems as preparation for the main result of this section.

Theorem 4.3. Let UU be a c.e. theory and let N:U▹RN : U \triangleright R. Suppose that the theory U⋆:=U+{φ(n)∣n∈ω}U^\star:= U+\{\varphi(n) \mid n \in\omega\} is consistent. Here the nn are the numerals provided by NN. Then, there is sentence ζ\zeta such that U+ζU+\zeta is consistent and U+ζ⊢{φ(n)∣n∈ω}U+\zeta\vdash\{\varphi(n) \mid n \in\omega\}.

Proof. Let I(x)↔δN(x)∧φ(x)I(x) \leftrightarrow\delta_N(x) \land\varphi(x). By the Fixed Point Lemma, we find a ρ\rho with

R⊢ρ↔(prov⁡U⋆(⌜¬ρI⌝)≤prov⁡U⋆(⌜ρI⌝)).R \vdash\rho\leftrightarrow\left(\operatorname{prov}_{U^\star}(\ulcorner\neg\rho^I\urcorner) \le\operatorname{prov}_{U^\star}(\ulcorner\rho^I\urcorner)\right).

We can assume that both the substitution function and the proof-predicate are elementary. Moreover, the graph of exponentiation can be represented by a Δ0\Delta_0-formula in such a way that RR proves uniqueness of values on standard arguments. It follows that ρ\rho can be written as ∃x ρ0(x)\exists x\,\rho_0(x), where ρ0\rho_0 is elementary. We find: if ρ0(n‾)\rho_0(\underline{n}) is true, then R⊢ρ0(n‾)R \vdash\rho_0(\underline{n}), and if ρ0(n‾)\rho_0(\underline{n}) is false, then R⊢¬ρ0(n‾)R \vdash\neg\rho_0(\underline{n}).

Our first order of business is to prove that ρI\rho^I is consistent with UU and that ρ\rho is false.

Suppose U⋆⊢¬ρIU^\star\vdash\neg\rho^I. Then, (i) ρ\rho is true or (ii) ρ⊥\rho^\perp is true.

Case i. We find, by the usual proof of Σ10\Sigma^0_1-completeness and the fact that the internal witness is standard, that U⋆⊢ρIU^\star\vdash\rho^I. This contradicts the fact that U⋆U^\star is consistent.

Case ii. We have U⋆⊢ρIU^\star\vdash\rho^I, by the definition of ρ⊥\rho^\perp. This again contradicts the fact that U⋆U^\star is consistent.

So, U⋆U^\star is consistent with ρI\rho^I and, a fortiori, UU is consistent with ρI\rho^I.

If ρ\rho were true, we would have U⋆⊢¬ρIU^\star\vdash\neg\rho^I. We have already seen that this does not hold.

Let ζ:=ρI\zeta:= \rho^I. We show that U+ζ⊢{φ(n)∣n∈ω}U+\zeta\vdash\{\varphi(n) \mid n \in\omega\}. Since ρ\rho is false, we find

(†)U⊢¬ρ0N(n‾),(\dagger)\quad U \vdash\neg\rho_0^N(\underline{n}),

for all nn. We work in U+ζU+\zeta. Let zz be a witness of ρI\rho^I. Suppose ¬φ(n)\neg\varphi(n). Then n∉In \notin I. So, n≰zn \not\leq z and, thus, by Axiom R5, z≤nz \leq n. It follows, by Axiom R4, that ⋁k≤nz=k\bigvee_{k\leq n} z = k, and, thus, ⋁k≤nρ0N(k)\bigvee_{k\leq n} \rho_0^N(k), but this contradicts (†)(\dagger). So, φ(n)\varphi(n). □\square

We note that ρI\rho^I can also be written as ρN↔∃y∈δN ¬φ(y)\rho^N \leftrightarrow\exists y \in\delta_N\,\neg\varphi(y).

Remark 4.4. We are not sure how original Theorem 4.3 is. Let’s say that results in the same spirit are known.

In the following theorem, the correct place where the numerals live is crucial, so we will keep track of it by adding a subscript.

Theorem 4.5. Consider a c.e. theory UU and let N:U▹RN : U \triangleright R. Suppose U⋆:=U+{φ(nN)∣n∈ω}U^\star:= U+\{\varphi(n^N) \mid n \in\omega\} is consistent and U⋆▹resUU^\star\triangleright_{\mathrm{res}} U. Then, UU is not ι3\iota_3-invertible.

Proof. By Theorem 4.3, there is a ζ\zeta such that U+ζU+\zeta is consistent and U+ζU+\zeta extends U⋆U^\star. Clearly, we have (U+ζ)▹resU(U+\zeta)\triangleright_{\mathrm{res}} U. Let K:(U+ζ)▹UK : (U+\zeta)\triangleright U, M:(U+ζ)▹RM : (U+\zeta)\triangleright R and θ(x)\theta(x) witness the restricted interpretation. Let P:=K⟨ζ⟩EU+¬ζ:U▹UP := K\langle\zeta\rangle_{E_{U+\neg\zeta}}: U \triangleright U. Suppose UU is I3\mathrm{I}_3-invertible. Let Q:U▹UQ: U \triangleright U be the promised INT3\mathrm{INT}_3-inverse. We take M′:=Q∘(M⟨ζ⟩N):U▹RM' := Q \circ(M\langle\zeta\rangle_N): U \triangleright R. By the Fixed Point Lemma, we find λ\lambda with U⊢λ↔¬θ(⌜λ⌝M′)U \vdash\lambda\leftrightarrow\neg\theta(\ulcorner\lambda\urcorner^{M'}). We have:

U+ζQ⊢θQ(⌜λ⌝M′)↔θQ(⌜λ⌝Q∘M)↔(θ(⌜λ⌝M))Q↔λKQ↔λPQ↔λ\begin{aligned} U+\zeta^Q \vdash\theta^Q(\ulcorner\lambda\urcorner^{M'}) &\leftrightarrow\theta^Q(\ulcorner\lambda\urcorner^{Q\circ M})\\ &\leftrightarrow\left(\theta(\ulcorner\lambda\urcorner^M)\right)^Q\\ &\leftrightarrow\lambda^{KQ}\\ &\leftrightarrow\lambda^{PQ}\\ &\leftrightarrow\lambda \end{aligned}

So, U+ζQ⊢λ↔¬λU+\zeta^Q\vdash\lambda\leftrightarrow\neg\lambda and, hence, U⊢(¬ζ)QU\vdash(\neg\zeta)^Q. On the other hand, QQ as a sentential congruence is faithful, so U⊢¬ζU\vdash\neg\zeta. But this contradicts the consistency of U+ζU+\zeta.

We prove our main result.

Theorem 4.6. Suppose UU is I3\mathrm{I}_3-invertible. Then, UU is a Krajíček-theory.

Proof. We prove the contraposed implication. Suppose UU is not a Krajíček-theory. It follows that there is an N:U▹S21N: U\triangleright S^1_2 such that U∗:=U+{con⁡nN(U)∣n∈ω}=U+ζN(U)U^\ast:= U+\{\operatorname{con}^N_n(U)\mid n\in\omega\}=U+\zeta^{N}(U) is consistent. By the Interpretation Existence Lemma, our Theorem 2.2, we have U∗▹resUU^\ast\triangleright_{\mathrm{res}} U. By Theorem 4.5, we see that UU is not I3\mathrm{I}_3-invertible.

Self-Interpretations of a Krajíček-Theory

We first start with some basic facts and definitions.

Basic Facts and Definitions

5.1. Basic Facts and Definitions. In this section, cuts will be downwards closed under ≤\leq and closed under the arithmetical operations and the smash function.

We fix a c.e. consistent sequential theory UU. Let N∈NUN\in\mathcal{N}_U iff N:U▹S21N: U\triangleright S^1_2. For M,N∈NUM,N\in\mathcal{N}_U, we define:

  • F:M≼NF:M\preccurlyeq N expresses that FF is an initial homomorphic embedding of MM into NN. Here it is intended that both the domain is downward closed under ≤M\leq^M and the range is downward closed under ≤N\leq^N. Also it is intended that our homomorphism commutes with the smash function.

  • M≼cutNM\preccurlyeq_{\mathrm{cut}}N if MM is an NN-cut, in other words, if F:M≼NF:M\preccurlyeq N and FF is the identical initial embedding on MM.

  • Let M,N∈NUM,N\in\mathcal{N}_U,

    • F:M≼UNF:M\preccurlyeq_U N iff U⊢F:M≼NU\vdash F:M\preccurlyeq N. Moreover, M≼UNM\preccurlyeq_U N iff F:M≼UNF:M\preccurlyeq_U N, for some FF.

    • M≼cut,UNM\preccurlyeq_{\mathrm{cut},U}N iff U⊢M≼cutNU\vdash M\preccurlyeq_{\mathrm{cut}}N.

    • F:M≺UNF:M\prec_U N iff F:M≼UNF:M\preccurlyeq_U N and, for all GG, U⊢¬G:N≼MU\vdash\neg G:N\preccurlyeq M. Moreover, M≺UNM\prec_U N iff F:M≺UNF:M\prec_U N, for some FF.

  • K:U▹UK:U\triangleright U is initial iff, for all N∈NUN\in\mathcal{N}_U, there is an M∈NUM\in\mathcal{N}_U such that (K∘M)≼UN(K\circ M)\preccurlyeq_U N.

  • K:U▹UK:U\triangleright U is strongly initial iff, for all N∈NUN\in\mathcal{N}_U, there is an M∈NUM\in\mathcal{N}_U such that (K∘M)≺UN(K\circ M)\prec_U N.

We collect some easy facts.

Lemma 5.1. Let UU be a consistent c.e. sequential theory.

  • a. ≼U\preccurlyeq_{U} is a partial pre-order and ≺U\prec_{U} is a strict partial order.

  • b. M≼UNM \preccurlyeq_{U} N and N≺UPN \prec_{U} P, then M≺UPM \prec_{U} P, and if M≺UNM \prec_{U} N and N≼UPN \preccurlyeq_{U} P, then M≺UPM \prec_{U} P.

  • c. Suppose K:U⊳UK : U \rhd U. Then, F:M≼UNF : M \preccurlyeq_{U} N implies FK:K∘M≼UK∘NF^{K} : K \circ M \preccurlyeq_{U} K \circ N.

  • d. Suppose σ\sigma is a Σ10\Sigma^{0}_{1}-sentence. Then U⊢(F:M≼N∧σM)→σNU \vdash(F : M \preccurlyeq N \land\sigma^{M}) \to\sigma^{N}.

A fundamental insight is as follows.

Theorem 5.2 (Pudlák). Let UU a consistent sequential c.e. theory. The ordering ≼U\preccurlyeq_{U} is downward-directed, i.e., for all M,N∈NUM,N \in\mathcal{N}_{U}, there is a P∈NUP \in\mathcal{N}_{U}, such that P≼UMP \preccurlyeq_{U} M and P≼UNP \preccurlyeq_{U} N. Moreover, we can find PP such that P≼cut,UMP \preccurlyeq_{\mathrm{cut},U} M and P≼UNP \preccurlyeq_{U} N.

The proof uses the machinery of sequences to produce an isomorphic embedding of an MM-cut in NN. See [7] or [4] or [Vis13].

We will use the following consequence.

Lemma 5.3. Let N,N′,M∈NUN,N',M \in\mathcal{N}_{U} and let K:U⊳UK : U \rhd U. Suppose K∘M≼UNK \circ M \preccurlyeq_{U} N. Then, there is an M′≼cut,UN′M' \preccurlyeq_{\mathrm{cut},U} N', such that K∘M′≼UNK \circ M' \preccurlyeq_{U} N.

Proof. We can find M′M' with M′≼cut,UN′M' \preccurlyeq_{\mathrm{cut},U} N' and M′≼UMM' \preccurlyeq_{U} M. Then, K∘M′≼UK∘M≼UNK \circ M' \preccurlyeq_{U} K \circ M \preccurlyeq_{U} N. □\square

In Lemma 5.16, we will need a stronger version of the Interpretation Existence Lemma. We give the relevant definitions. We extend the language of UU with a unary predicate CC and a binary predicate sat⁡\operatorname{sat}. Let N∈NUN \in\mathcal{N}_{U}. We will pretend that NN is one-dimensional leaving the modification needed for more-dimensionality and even piece-wiseness to the reader. (Since, we are considering sequential theories, we can reduce the whole discussion to one-dimensional anyway.)

We define:

  • F‾U,N\overline{F}_{U,N} is the theory in the language of UU extended with a unary predicate CC and a binary predicate sat⁡\operatorname{sat} given by the following set of axioms:

    • ∀x∈C form⁡N(x)\forall x \in C\ \operatorname{form}^{N}(x), where form expresses that xx is a UU-formula.

    • ∀x∈C ∀y (sub⁡(y,x)→y∈C)\forall x \in C\ \forall y\ (\operatorname{sub}(y,x) \to y \in C), where sub arithmetises the sub-formula relation.

    • C(⌜φ⌝)C(\ulcorner\varphi\urcorner), where φ\varphi is a (standard) UU-formula and the numeral ⌜φ⌝\ulcorner\varphi\urcorner is derived from NN.

    • ∀x ∀y (sat⁡(x,y)→y∈C)\forall x\ \forall y\ (\operatorname{sat}(x,y) \to y \in C).

    • The commutation conditions for sat⁡\operatorname{sat} restricted to UU-formulas xx in CC, where the xx code sequences.

  • Suppose M∈NVM \in\mathcal{N}_{V}. We have U⊳fres,MVU \rhd_{\mathrm{fres},M} V iff U⊳(V+F‾V,M)U \rhd(V + \overline{F}_{V,M}).

We have:

Theorem 5.4 (Interpretation Existence Lemma 2). UU⊳fresU\mathcal{U}_{U} \rhd_{\mathrm{fres}} U.

See [18 Theorems 3.4 and 4.5]. Let U+:=U+F‾U,NU^{+} := U + \overline{F}_{U,N}.

A fundamental insight is cut-intersection.

Theorem 5.5 (Cut-Intersection). In U+F‾U,NU + \overline{F}_{U,N}, there is an NN-cut I\mathcal{I}, such that, for every JJ defined in the UU-language, we have U+⊢J≼cutN→I≼cutJU^{+} \vdash J \preccurlyeq_{\mathrm{cut}} N \to\mathcal{I} \preccurlyeq_{\mathrm{cut}} J.

We specify I\mathcal{I}. Let ε\varepsilon stand for an empty string. We define:

x∈I:⟺x∈δN∧∀I(sat⁡(ε,⌜I≼cutN⌝)→sat⁡(⟨x⟩,⌜v0∈I⌝))x \in\mathcal{I} \mathrel{\vcentcolon\Longleftrightarrow} x \in\delta_{N} \land\forall I\bigl(\operatorname{sat}(\varepsilon,\ulcorner I \preccurlyeq_{\mathrm{cut}} N\urcorner) \to\operatorname{sat}(\langle x\rangle,\ulcorner v_{0} \in I\urcorner)\bigr)

Remark 5.6. We are doing things here that we did not notationally justify. Officially one would have to do something like this. We consider application of λX.cut⁡N(X)\lambda X.\operatorname{cut}_{N}(X) to λx.I(x)\lambda x.I(x). This operation can be arithmetised. Let the Gödel number of λX.cut⁡N(X)\lambda X.\operatorname{cut}_{N}(X) be qq. So, we want something like sat⁡(ε,q⋅i)\operatorname{sat}(\varepsilon,q\cdot i).

A second issue is that, in a sequential theory, sequences and singletons need not be unique. We can easily adapt the formula to take that into account.

Proof. We first prove that I\mathcal{I} is a U+U^{+}-cut. We treat two cases.

Downward closure: We reason in U+U^{+}. Suppose y≤Nxy\leq^{N}x and x∈Ix\in\mathcal{I}. Consider any I\mathcal{I} such that sat⁡(ε,⌜I≼cutN⌝)\operatorname{sat}(\varepsilon,\ulcorner\mathcal{I}\preccurlyeq_{\mathrm{cut}}N\urcorner). (Here we treat ‘I\mathcal{I}’ as an internal variable.) It follows that sat⁡(⟨x⟩,⌜v0∈I⌝)\operatorname{sat}(\langle x\rangle,\ulcorner v_{0}\in\mathcal{I}\urcorner). By the commutation conditions, we find sat⁡(ε,⌜∀u∈I ∀v≤u v∈I⌝)\operatorname{sat}(\varepsilon,\ulcorner\forall u\in\mathcal{I}\ \forall v\leq u\ v\in\mathcal{I}\urcorner). Applying the commutation conditions again, we may conclude that sat⁡(⟨y⟩,⌜v0∈I⌝)\operatorname{sat}(\langle y\rangle,\ulcorner v_{0}\in\mathcal{I}\urcorner).

Closure under Addition: We reason in U+U^{+}. Suppose xx and yy are in I\mathcal{I} and suppose sat⁡(ε,⌜I≼cutN⌝)\operatorname{sat}(\varepsilon,\ulcorner\mathcal{I}\preccurlyeq_{\mathrm{cut}}N\urcorner). So, sat⁡(⟨x⟩,⌜v0∈I⌝)\operatorname{sat}(\langle x\rangle,\ulcorner v_{0}\in\mathcal{I}\urcorner) and sat⁡(⟨y⟩,⌜v0∈I⌝)\operatorname{sat}(\langle y\rangle,\ulcorner v_{0}\in\mathcal{I}\urcorner). We find sat⁡(ε,⌜∀u∈I ∀v∈I (u+v)∈I⌝)\operatorname{sat}(\varepsilon,\ulcorner\forall u\in\mathcal{I}\ \forall v\in\mathcal{I}\ (u+v)\in\mathcal{I}\urcorner) and, thus, sat⁡(⟨x+y⟩,⌜v0∈I⌝)\operatorname{sat}(\langle x+y\rangle,\ulcorner v_{0}\in\mathcal{I}\urcorner).

We prove the second claim. We reason in U+U^{+}. Suppose J≼cutN\mathcal{J}\preccurlyeq_{\mathrm{cut}}N and x∈Ix\in\mathcal{I}. Then, sat⁡(⟨x⟩,⌜v0∈J⌝)\operatorname{sat}(\langle x\rangle,\ulcorner v_{0}\in\mathcal{J}\urcorner). Since J\mathcal{J} is standard, we find x∈Jx\in\mathcal{J}. □\square

Arithmetically Grounded Theories

In this section, we briefly note some basic facts about arithmetically grounded sequential theories. We note that these have many analogies to sequential theories with full induction. In fact, we do not know whether they are not simply sequential theories with full induction.

Open Question 5.7. Do arithmetically grounded arithmetical theories have full induction?

We can derive many analogies of arithmetically grounded sequential theories with sequential theories with full induction. Some of them are given in the next theorem.

Theorem 5.8. Suppose WW is a consistent, sequential, c.e., arithmetically grounded theory. Let PP be a witness of arithmetical groundedness. We have

  1. W⊢(IΔ0+Ω1)PW\vdash(I\Delta_{0}+\Omega_{1})^{P}.

  2. For every WW-sentence φ\varphi and for every nn, we have W⊢prov⁡W,nP(⌜φ⌝)→φW\vdash\operatorname{prov}^{P}_{W,n}(\ulcorner\varphi\urcorner)\to\varphi.

  3. W⊢(BΣ1)PW\vdash(B\Sigma_{1})^{P}.

  4. Let σ\sigma and σ′\sigma' be Σ10\Sigma^{0}_{1}-sentences and suppose EA⊢σ→σ′\mathrm{EA}\vdash\sigma\to\sigma'. Then, W⊢(σ→σ′)PW\vdash(\sigma\to\sigma')^{P}.

Proof. Ad (1): By a result of Wilkie, see [4 pp. 366–371], we have S21▹IΔ0S^{1}_{2}\triangleright I\Delta_{0}. So, for some N∈NWN\in\mathcal{N}_{W}, we have W⊢(IΔ0)NW\vdash(I\Delta_{0})^{N}. Since P≼WNP\preccurlyeq_{W}N and IΔ0I\Delta_{0} can be written in Π10\Pi^{0}_{1}-form, by downward persistence, we find that W⊢(IΔ0)PW\vdash(I\Delta_{0})^{P}, and, thus, W⊢(IΔ0+Ω1)PW\vdash(I\Delta_{0}+\Omega_{1})^{P}, since PP is already WW-provably closed under ω1\omega_{1}.

Ad (2): Since WW is sequential, it is locally essentially reflexive. This means that, for every WW-sentence φ\varphi and for every nn, we can find an N∈NWN\in\mathcal{N}_{W}, such that W⊢prov⁡W,nN(⌜φ⌝)→φW\vdash\operatorname{prov}^{N}_{W,n}(\ulcorner\varphi\urcorner)\to\varphi. Since P≼WNP\preccurlyeq_{W}N, we find, by the upward persistence of Σ10\Sigma^{0}_{1}-sentences, that W⊢prov⁡W,nP(⌜φ⌝)→φW\vdash\operatorname{prov}^{P}_{W,n}(\ulcorner\varphi\urcorner)\to\varphi.

Ad (3): By (2), we have W⊢SWPW\vdash\mathsf{S}^{P}_{W}. By the Interpretation Existence Lemma 2.2, we have H:SW▹resWH:\mathsf{S}_{W}\triangleright_{\mathrm{res}}W, where we have a truth predicate for HH. We have P≼WP∘H∘PP\preccurlyeq_{W}P\circ H\circ P. We have a truth predicate η\eta of H∘PH\circ P, inside PP, so we can find a

liar sentence λ\lambda such that U⊢λ↔¬η(⌜λP⌝)U \vdash\lambda\leftrightarrow\neg\eta(\ulcorner\lambda^{P}\urcorner). So, U⊢λP↔¬λPHPU \vdash\lambda^{P} \leftrightarrow\neg\lambda^{PHP}. So, PP and P∘H∘PP \circ H \circ P are not elementarily equivalent and a fortiori not isomorphic. Thus, the embedding must be strictly initial. So, PP has a strict end-extension inside WW. It follows that, WW-verifiably, we must have BΣ1\mathrm{B}\Sigma_{1} by [21 Proposition 1].

Ad (4): Suppose EA⊢σ→σ′\mathrm{EA} \vdash\sigma\to\sigma'. By the results of [20], there is a (IΔ0+Ω1)(\mathrm{I}\Delta_{0}+\Omega_{1})-cut JJ such that IΔ0+Ω1⊢σJ→σ′\mathrm{I}\Delta_{0}+\Omega_{1} \vdash\sigma^{J} \to\sigma'. It follows that W⊢σJP→σ′PW \vdash\sigma^{JP} \to\sigma'^{P}. So, since P≼WP∘JP \preccurlyeq_{W} P \circ J, we find W⊢(σ→σ′)PW \vdash(\sigma\to\sigma')^{P}.

We note that Theorem 5.8(2) implies some PA-lime behaviour. For example, a consistent, arithmetically grounded, sequential, c.e. theory will not be interpretable in a finite sub-theory. Also, such a theory has no consistent finitely axiomatisable extension-in-the-same-language. See also [16].

Theorem 5.9. Suppose WW is a consistent, sequential, c.e., arithmetically grounded theory. Suppose P∈NWP \in\mathcal{N}_{W} is a ≼W\preccurlyeq_{W}-least element. Then, there is a Σ10\Sigma^{0}_{1}-sentence ι\iota, such that W⊬ιPW \nvdash\iota^{P} and W▹(W+ιP)W \triangleright(W+\iota^{P}).

Proof. We find ι\iota with S12⊢ι↔∃xprov⁡W,x(⌜⊥⌝)≤prov⁡W(⌜ιP⌝)\mathrm{S}^{2}_{1} \vdash\iota\leftrightarrow\exists x\operatorname{prov}_{W,x}(\ulcorner\bot\urcorner) \leq\operatorname{prov}_{W}(\ulcorner\iota^{P}\urcorner). Here the witness comparison ordering applies just to the first existential quantifier of ∃xprov⁡W,x(⌜⊥⌝)\exists x\operatorname{prov}_{W,x}(\ulcorner\bot\urcorner).

Our first order of business, is to show that W⊬ιPW \nvdash\iota^{P}. Suppose W⊢ιPW \vdash\iota^{P}. For some pp, we have W⊢(proof⁡W(p,⌜ιP⌝))PW \vdash(\operatorname{proof}_{W}(p,\ulcorner\iota^{P}\urcorner))^{P}. It follows that W⊢prov⁡W,pP(⌜⊥⌝)W \vdash\operatorname{prov}^{P}_{W,p}(\ulcorner\bot\urcorner). Quod non, by Theorem 5.8(2).

We define prov⁡W∗(y)↔∃xprov⁡W,x(y)≤prov⁡W(⌜ιP⌝)\operatorname{prov}^{*}_{W}(y) \mathrel{\leftrightarrow} \exists x\operatorname{prov}_{W,x}(y) \leq\operatorname{prov}_{W}(\ulcorner\iota^{P}\urcorner). We note that ι\iota is identical to prov⁡W∗(⌜⊥⌝)\operatorname{prov}^{*}_{W}(\ulcorner\bot\urcorner) or, in other words, incon⁡∗(W)\operatorname{incon}^{*}(W). The Löb conditions for prov⁡W∗P\operatorname{prov}^{*P}_{W} are WW-verifiable. By Theorem 5.8(4), we do not need to worry about the third Löb Condition, since we only need it to be verifiable in EA and since prov⁡W∗\operatorname{prov}^{*}_{W} is Σ10\Sigma^{0}_{1}. We have:

W⊢con⁡∗P(W)→con⁡∗P(W+incon⁡∗P(W)).W \vdash\operatorname{con}^{*P}(W) \to\operatorname{con}^{*P}(W+\operatorname{incon}^{*P}(W)).

By the Interpretation Existence Lemma, we find an interpretation HH with

H:(W+con⁡∗P(W))▹(W+incon⁡∗P(W)).H : (W+\operatorname{con}^{*P}(W)) \triangleright(W+\operatorname{incon}^{*P}(W)).

Let K:=ID⁡⟨incon⁡∗(W)⟩HK := \operatorname{ID}\langle\operatorname{incon}^{*}(W)\rangle H, where ID is the identity interpretation on W+con⁡∗P(W)W+\operatorname{con}^{*P}(W). So, K:W▹(W+incon⁡∗P(W))K : W \triangleright(W+\operatorname{incon}^{*P}(W)), i.e., K:W▹(W+ιP)K : W \triangleright(W+\iota^{P}).

Corollary 5.10. Suppose WW is a consistent, sequential, arithmetically grounded theory. Then, there is a non-initial self-interpretation K∗K^{*} of WW.

Proof. Let PP witness arithmetical groundedness. Let K∗:W→WK^{*}: W \to W be based on the translation of a witnessing interpretation of W▹(W+ιP)W \triangleright(W+\iota^{P}). Suppose we had M∈NWM \in\mathcal{N}_{W} with K∗∘M≼PK^{*} \circ M \preccurlyeq P. It follows that K∗∘P≼PK^{*} \circ P \preccurlyeq P. Since, according to WW, we have ι\iota inside K∗∘PK^{*}\circ P, by upwards persistence, it follows that W⊢ιPW \vdash\iota^{P}. Quod non.

Remark 5.11. Theorem 5.9 is based on a combination of ideas. The first is Feferman’s Theorem of the interpretability of inconsistency. This is combined with a variation of a familiar trick to produce a provability predicate for extensions of PA where the unprovability of inconsistency is guaranteed. This trick in its turn uses a variant of the Friedman-Goldfarb-Harrington argument. The true priority for this argument goes to John Shepherdson in [9].

The alternative provability predicate produced in the case of extensions of PA is Fefermanian. This means that it can be viewed as ordinary provability with an alternative representation of the axiom set. The predicate we use here is not Fefermanian because we also employ restriction of the complexity of the formulas used in the proofs.

Arithmetical groundedness is a heavy demand. The reader may well wonder whether we cannot do better for a Feferman-FGH-style result. Indeed, with a bit more delicate work, we can prove a similar result for reflexive, c.e., sequential theories. See Appendix A.

Remark 5.12. Since we have Theorem 5.8(4), we can verify Solovay’s proof for the completeness of provability logic for prov⁡U∗N\operatorname{prov}^{*N}_{U} for interpretations in UU using [2].

The Characterisation

We will prove the following characterisation of consistent c.e. Krajíček-theories.

Theorem 5.13. Let UU be a consistent c.e. sequential theory. The following are equivalent:

a. UU is a Krajíček-theory.

b. All self-interpretations of UU are strongly initial.

c. All self-interpretations of UU are initial.

We note that the definition of a Krajíček-theory is based on a great number of very specific design choices. We have to choose, at the object-level, an appropriate syntax, a proof system, the desired notion of formula complexity, the arithmetisation. In contrast, the only conventions required for the characterisation are at the meta-level. These are the kind of choices shared by all logic. So, the characterisation goes a long way towards a ‘coordinate-free’ way of understanding being a Krajíček-theory.

We will prove a number of theorems that can be combined to a proof of Theorem 5.13. The proof below shows how Theorem 5.13 follows from these later theorems.

Proof of Theorem 5.13. (a) ⇒\Rightarrow (b): This is Lemma 5.14.

(b) ⇒\Rightarrow (c): This is trivial.

(c) ⇒\Rightarrow (a): Suppose UU is a consistent sequential c.e. theory and suppose all self-interpretations of UU are initial. Suppose, in order to obtain a contradiction, that UU is not a Krajíček-theory. This tells us that, for some N∈MUN \in\mathcal{M}_{U}, the theory U+{con⁡N(U)∣n∈ω}U + \{\operatorname{con}^{N}(U) \mid n \in\omega\} is consistent. By Theorem 4.3, there is a ζ\zeta such that U+ζU + \zeta is consistent and U+ζ⊢{con⁡nN(U)∣n∈ω}U + \zeta\vdash\{\operatorname{con}^{N}_{n}(U) \mid n \in\omega\}. Theorem 5.15 tells us that all self-interpretations of U+ζU + \zeta are initial. Moreover, by Lemma 5.16, U+ζU + \zeta is arithmetically grounded. But his contradicts the consistency of U+ζU + \zeta in the light of Corollary 5.10. □\square

We prove Lemma 5.14.

Lemma 5.14. Let UU be a consistent c.e. sequential Krajíček-theory. Then any self-interpretation KK of UU is strongly initial.

Proof. We work in UU. Consider any N∈MUN \in\mathcal{M}_U. Let P≼UNP \preccurlyeq_U N and P≼UK∘NP \preccurlyeq_U K \circ N. Let GG witness P≼UK∘NP \preccurlyeq_U K \circ N. We know that U⊢incon⁡nP(U)U \vdash\operatorname{incon}^{P}_n(U), for some nn. Let MM in MU\mathcal{M}_U be an NN-cut such that U⊢con⁡nM(U)U \vdash\operatorname{con}^{M}_n(U). It follows that U⊢con⁡nMK(U)U \vdash\operatorname{con}^{M K}_n(U), since we have UU inside KK.

We want to show that K∘M≼UP≼UNK \circ M \preccurlyeq_U P \preccurlyeq_U N. We reason in UU. It suffices that every element of K∘MK \circ M is in the range of GG. Let aa be an arbitrary element of K∘MK \circ M and let bb be a witness of incon⁡nP(U)\operatorname{incon}^{P}_n(U). It follows that G(b)G(b) is a witness of incon⁡nNK(U)\operatorname{incon}^{N K}_n(U). Since con⁡nMK(U)\operatorname{con}^{M K}_n(U), we find that a<NKG(b)a <^{N K} G(b). Ergo, aa is in the range of GG.

Let F:P≼UNF : P \preccurlyeq_U N. We reason in UU. Suppose G:N≼UK∘MG : N \preccurlyeq_U K \circ M. If follows that G∘F:P≼K∘MG \circ F : P \preccurlyeq K \circ M. We have incon⁡nP(U)\operatorname{incon}^{P}_n(U), so incon⁡nMK(U)\operatorname{incon}^{M K}_n(U). Quod non.

We prove that finite extensions preserve the property that all self-interpretations are initial.

Theorem 5.15. Let UU be a consistent c.e. sequential theory and let φ\varphi be any UU-sentence such that U+φU+\varphi is consistent. Suppose all self-interpretations of UU are initial. Then, all self-interpretations of U+φU+\varphi are initial.

Proof. Let N0∈MUN_0 \in\mathcal{M}_U with indwelling translation ν0\nu_0. Let KK be a self-interpretation of U+φU+\varphi and let N∈MU+φN \in\mathcal{M}_{U+\varphi}. Let κ\kappa be the indwelling translation of KK and let ν\nu be the indwelling translation of NN. Let K′K' be the self-interpretation of UU based on κ⟨φ⟩id\kappa\langle\varphi\rangle_{\mathrm{id}} and let N′N' be the element of MU\mathcal{M}_U based on ν⟨φ⟩ν0\nu\langle\varphi\rangle_{\nu_0}. We can find an N∘∈MUN^\circ\in\mathcal{M}_U such that F:K′∘N∘≼UN′F : K' \circ N^\circ\preccurlyeq_U N'. Let N∗:=EU(U+φ)∘N∘∈MU+φN^* := E_U(U+\varphi) \circ N^\circ\in\mathcal{M}_{U+\varphi}. Then, U+φ⊢F:K∘N∗≼NU+\varphi\vdash F : K \circ N^* \preccurlyeq N.

We prove the promised Lemma 5.16.

Lemma 5.16. Let UU be a consistent c.e. sequential theory. Suppose all self-interpretations of UU are initial. Suppose further that U+ζU+\zeta is consistent and U+ζ⊢{con⁡nN(U)∣n∈ω}U+\zeta\vdash\{\operatorname{con}^{N}_n(U) \mid n \in\omega\}, for some N∈MUN \in\mathcal{M}_U. Then, U+ζU+\zeta is arithmetically grounded.

Proof. We assume the conditions of the theorem. Let K+:(U+ζ)▹(U+FU,N)K^+ : (U+\zeta) \triangleright(U+F_{U,N}) and let KK be the reduct of K+K^+ to the UU-language. We take K∗:=K⟨ζ⟩EU(U+¬ζ):U▹UK^* := K\langle\zeta\rangle_{E_U(U+\neg\zeta)} : U \triangleright U.

We find that K∗K^* is initial. Consider any N′∈MU+ζN' \in\mathcal{M}_{U+\zeta}. Let N∗:=N′⟨ζ⟩N′′:U▹S21N^* := N'\langle\zeta\rangle_{N''} : U \triangleright S^1_2, where N′′:=EU(U+¬ζ)∘N∈MU+¬ζN'' := E_U(U+\neg\zeta) \circ N \in\mathcal{M}_{U+\neg\zeta}. By Lemma 5.3, it follows that there is an M≼cut,UNM \preccurlyeq_{\mathrm{cut},U} N, such that F:K∗∘M≼UN∗F : K^* \circ M \preccurlyeq_U N^*, for some FF. It follows that F:K+∘M′≼U+ζN′F : K^+ \circ M' \preccurlyeq_{U+\zeta} N', where M′:=EU(U+ζ)∘M∈MU+ζM' := E_U(U+\zeta) \circ M \in\mathcal{M}_{U+\zeta}. Since M′M' is in the UU-language, it follows that (†) F:K∘M′≼U+ζN′F : K \circ M' \preccurlyeq_{U+\zeta} N',

Theorem 5.5 gives us U+FU,N⊢M≼cutN→I≼cutM′U+F_{U,N} \vdash M \preccurlyeq_{\mathrm{cut}} N \to I \preccurlyeq_{\mathrm{cut}} M', so (‡) K+∘I≼cut,(U+ζ)K∘M′K^+ \circ I \preccurlyeq_{\mathrm{cut},(U+\zeta)} K \circ M'.

Combining, (†) with (‡), we find that K+∘I≼U+ζN′K^+ \circ I \preccurlyeq_{U+\zeta} N'. So, K+∘IK^+ \circ I is a desired least element of ≼U+ζ\preccurlyeq_{U+\zeta}.

References

Appendix A. A Feferman-FGH-style Result

Axiom sets of theories are supposed to be represented by a Δ1b\Delta^{b}_{1} formula over S21S^{1}_{2}. We prove the following.

Theorem A.1. Let WW be c.e. and sequential. Let N∈NWN \in\mathfrak{N}_{W}. Suppose WW is NN-reflexive, i.e., W⊢con⁡nN(W)W \vdash\operatorname{con}^{N}_{n}(W), for each nn. Then, there is a ∃Σ1b\exists\Sigma^{b}_{1}-sentence ι\iota, such that W⊬ιNW \nvdash\iota^{N} and W⋠(W+{ιM∣M∈NW})W \not\preccurlyeq(W + \{\iota^{M} \mid M \in\mathfrak{N}_{W}\}).

Proof. We find ι\iota with

S21⊢ι↔∃x(prov⁡W,x(⌜⊥⌝)∧∀y<∣x∣¬proof⁡W(y,⌜ιN⌝)).S^{1}_{2} \vdash\iota\leftrightarrow\exists x\left(\operatorname{prov}_{W,x}(\ulcorner\bot\urcorner) \land\forall y < |x| \neg\operatorname{proof}_{W}(y,\ulcorner\iota^{N}\urcorner)\right).

Here ∀y<∣x∣\forall y < |x| is sharply bounded. We note that we can take ι\iota to be ∃Σ1b\exists\Sigma^{b}_{1}.

We show that W⊬ιNW \nvdash\iota^{N}. Suppose W⊢ιNW \vdash\iota^{N}. For some pp, we have

W⊢proof⁡WN(p,⌜ιN⌝).W \vdash\operatorname{proof}^{N}_{W}(p,\ulcorner\iota^{N}\urcorner).

We note that, in WW, it follows from ιN\iota^{N} and proof⁡W(p,⌜ιN⌝)\operatorname{proof}_{W}(p,\ulcorner\iota^{N}\urcorner), that the promised witness xx of ιN\iota^{N} must satisfy ∣x∣≤p|x| \leq p and, thus, x≤22px \leq2^{2p}. Let, in the real world, q:=2pq := 2^{p}. So, we will certainly have W⊢prov⁡W,qN(⌜⊥⌝)W \vdash\operatorname{prov}^{N}_{W,q}(\ulcorner\bot\urcorner). Quod non.

Let M∈NWM \in\mathfrak{N}_{W}. We define

  • prov⁡W∗(z):↔∃x(prov⁡W,x(z)∧∀y<∣x∣¬proof⁡W(y,⌜ιN⌝))\operatorname{prov}^{*}_{W}(z) :\leftrightarrow\exists x\left(\operatorname{prov}_{W,x}(z) \land\forall y < |x|\neg\operatorname{proof}_{W}(y,\ulcorner\iota^{N}\urcorner)\right).

  • prov⁡W∘(⌜φ⌝):↔prov⁡W∗(⌜φM⌝)\operatorname{prov}^{\circ}_{W}(\ulcorner\varphi\urcorner) :\leftrightarrow\operatorname{prov}^{*}_{W}(\ulcorner\varphi^{M}\urcorner), where φ\varphi is arithmetical.

We note that ι\iota is incon⁡∗(W)\operatorname{incon}^{*}(W). To increase readability, we have hidden the dependence of prov⁡W∘\operatorname{prov}^{\circ}_{W} on MM.

We can easily verify the Löb Conditions for prov⁡W∘\operatorname{prov}^{\circ}_{W}. We find, for sufficiently large nn, that:

S21⊢prov⁡W,n(⌜con⁡∗M(W)⌝)→(prov⁡W,n(⌜con⁡∗M(W)⌝)∧prov⁡W∘(⌜con⁡∘(W)⌝))→(prov⁡W,n(⌜con⁡∗M(W)⌝)∧incon⁡∘(W))→(prov⁡W,n(⌜con⁡∗M(W)⌝)∧incon⁡∗(W))→(prov⁡W,n(⌜con⁡∗M(W)⌝)∧prov⁡W,n(⌜incon⁡∗(W)⌝))→prov⁡W,n(⌜⊥⌝)\begin{aligned} S^{1}_{2} \vdash\operatorname{prov}_{W,n}(\ulcorner\operatorname{con}^{*M}(W)\urcorner) &\to\left(\operatorname{prov}_{W,n}(\ulcorner\operatorname{con}^{*M}(W)\urcorner) \land\operatorname{prov}^{\circ}_{W}(\ulcorner\operatorname{con}^{\circ}(W)\urcorner)\right) \\ &\to\left(\operatorname{prov}_{W,n}(\ulcorner\operatorname{con}^{*M}(W)\urcorner) \land\operatorname{incon}^{\circ}(W)\right) \\ &\to\left(\operatorname{prov}_{W,n}(\ulcorner\operatorname{con}^{*M}(W)\urcorner) \land\operatorname{incon}^{*}(W)\right) \\ &\to\left(\operatorname{prov}_{W,n}(\ulcorner\operatorname{con}^{*M}(W)\urcorner) \land\operatorname{prov}_{W,n}(\ulcorner\operatorname{incon}^{*}(W)\urcorner)\right) \\ &\to\operatorname{prov}_{W,n}(\ulcorner\bot\urcorner) \end{aligned}

We may conclude that S21⊢con⁡n(W)→con⁡n(W+ιM)S^{1}_{2} \vdash\operatorname{con}_{n}(W) \to\operatorname{con}_{n}(W+\iota^{M}). So, W⊢con⁡nN(W+ιM)W \vdash\operatorname{con}^{N}_{n}(W+\iota^{M}).

We note that at this point, we may drop the assumption that nn be sufficiently large.

Consider an effective enumeration M0,M1,…M_{0}, M_{1}, \ldots of NW\mathfrak{N}_{W}. Since, for each kk, we can find an MM such that M≼WMiM \preccurlyeq_{W} M_{i}, for all i<ki < k, we find that

W⊢con⁡nN(W+ιM0+⋯+ιMk−1).W \vdash\operatorname{con}^{N}_{n}(W+\iota^{M_{0}}+\cdots+\iota^{M_{k-1}}).

By the Interpretation Existence Lemma, we find W▹(W+{ιMi∣i∈ω})W \triangleright(W+\{\iota^{M_{i}} \mid i \in\omega\}). □\Box

Philosophy, Faculty of Humanities, Utrecht University, Newton House, attn. Utrecht University, 3rd floor, Newtonlaan 201, 3584 BH Utrecht, the Netherlands

Email address: [email protected]

References

  1. [1]S.R. Buss. Bounded Arithmetic. Bibliopolis, Napoli, 1986.
  2. [2]Dick de Jongh, Mark Jumelet, and Franco Montagna. On the proof of Solovay’s theorem. Studia Logica, 50:51–70, 1991.
  3. [3]Mirko Engler and Benjamin Zayton. Rigid theories. arXiv preprint, arXiv:2611.16067, 2026.arxiv.org/abs/2611.16067
  4. [4]Petr Hájek and Pavel Pudlák. Metamathematics of First-Order Arithmetic. Perspectives in Mathematical Logic. Springer, Berlin, 1993.
  5. [6]Jan Mycielski, Pavel Pudlák, and Alan S. Stern. A lattice of chapters of mathematics (interpretations between theorems), volume 84 of Memoirs of the American Mathematical Society. AMS, Providence, Rhode Island, 1990.
  6. [7]Pavel Pudlák. Cuts, consistency statements and interpretations. The Journal of Symbolic Logic, 50(2):423–441, 1985.DOI
  7. [8]Fedor Pakhomov and Alexander Zapryagaev. Multi-dimensional interpretations of Presburger Arithmetic in itself. Journal of Logic and Computation, 30(8):1681–1693, 2020.arxiv.org/abs/2004.03404
  8. [9]John C. Shepherdson. Representability of recursively enumerable sets in formal theories. Archiv für mathematische Logik und Grundlagenforschung, 5(3-4):119–127, 1961.
  9. [10]Craig Smoryński. Logical Number Theory I, an Introduction. Universitext. Springer, New York, 1991.DOI
  10. [11]Alfred Tarski, Andrzej Mostowski, and Rafael M. Robinson. Undecidable theories. North-Holland, Amsterdam, 1953.
  11. [12]Albert Visser. Faith & Falsity: a study of faithful interpretations and false Σ^0_1-sentences. Annals of Pure and Applied Logic, 131(1–3):103–131, 2005.
  12. [13]Albert Visser. The Second Incompleteness Theorem and bounded interpretations. Studia Logica, 100(1-2):399–418, 2012. doi: 10.1007/s11225-012-9385-z.
  13. [15]Albert Visser. The interpretability of inconsistency, Feferman’s theorem and related results. Logic Group Preprint Series 318, Faculty of Humanities, Philosophy, Utrecht University, Janskerkhof 13, 3512 BL Utrecht, http://www.phil.uu.nl/preprints/lgps/, 2014.
  14. [16]Albert Visser. Peano Corto and Peano Basso: A study of local induction in the context of weak theories. Mathematical Logic Quarterly, 60(1–2):92–117, 2014.
  15. [17]Albert Visser. On Q. Soft Computing, 21(1):39–56, 2017.
  16. [18]Albert Visser. The Interpretation Existence Lemma. In Feferman on Foundations, number 13 in Outstanding Contributions to Logic, pages 101–144, New York, 2018. Springer.DOI
  17. [19]Albert Visser. The small-is-very-small principle. Mathematical Logic Quarterly, 65(4):453–478, 2019.arxiv.org/abs/1805.01178
  18. [20]Alex Wilkie and Jeff Paris. On the scheme of induction for bounded arithmetic formulas. Annals of Pure and Applied Logic, 35:261–302, 1987.
  19. [21]Alex Wilkie and Jeff Paris. On the existence of end extensions of models of bounded induction. In Logic, Methodology and Philosophy of Science VIII (Moscow 1987), pages 143–161. North Holland, 1989.

Paper details

vlnc:W_huw9dut5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT, Claude

View statement
Looking for related papers…
Contents