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 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 means roughly that its internal interpretations of the weak theory are initial in all interpretations of .
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 , the category in which two interpretations and of in are the same iff there is a -definable, -verifiable isomorphism between and . The second is , the category in which two interpretations and of in are the same iff, for all -sentences , we have . 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 will be called -rigid. The -rigid theories will also be called interpretation categorical. The -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 will be called -invertible. We note that the invertible interpretations in are bi-interpretations and that the invertible interpretations in are sentential congruences (also: elementary congruences).
All self-interpretations are initial. The property of initiality will be introduced in Section 5. Roughly, is initial iff, for all interpretations of the weak theory in , there is an interpretation of in 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 is below . 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 -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 -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 -rigidity implies -rigidity and that -rigidity implies -invertibility. The concept of -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 -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 -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 -complete. In Section 4, we prove that -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 -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 and will play a special role in this paper. The theory was introduced by Sam Buss in [1]. See also [4]. Buss’ theory is a weak theory that is mutually interpretable with such theories as and . On the other hand, it is an ideal basis for the arithmetisation of metamathematics. The theory was introduced in [11]. Since, we will see some actual reasoning in , we reproduce its axioms here. For we have:
R1.
R2.
R3. (if )
R4.
R5.
In the Tarski-Mostowski-Robinson book, the relation 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 is based on a translation of languages.
We write for: is an interpretation of in , and for: there is an interpretation .
We will diverge a bit from the usual practice by also using with as meaning: there is an interpretation with underlying translation . 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 and . Then is the disjunctive interpretation that coincides with if and with if .
Suppose and are theories in the same language and the theorems of are contained in the theorems of . We write for the interpretation based on the identical translation.
Suppose . An interpretation is -restricted iff there is a -formula , such that, for all , we have . Here the numerals come from . The interpretation is restricted iff it is -restricted, for some . The present notion is weaker than the notion of bounded interpretation from [13]. We provide a stronger version in Section 5. We write , for restricted interpretability. We have:
Theorem 2.1.
If , then .
If , then .
We leave the simple verification to the reader. Let
.
Here means consistency from the axioms with Gödel numbers where only formulas of depth-of-quantifier complexity are allowed in the proofs. We have:
Theorem 2.2 (Interpretation Existence Lemma). We have: .
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 for . The first category is . In this category, two interpretations are the same if there is an -definable, -verifiable isomorphism between and . Isomorphism of theories in this category is bi-interpretation. The second is . In this category, two interpretations are the same if, for all -sentences , we have . 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 is sequential. Then, for any , there is an . 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 is of the form and is of the form . We define:
.
.
.
.
Krajíček-Theories
The c.e. theory is a Krajíček-theory iff, for every , there is a such that . 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 is a Krajíček-theory and is an -retract of . Then, is a Krajíček-theory.
Proof. Let and and, for all -sentences , . Suppose . It follows that . So, for some , we have . Thus, . We may conclude .
Using we can transform a -proof of inconsistency into a -proof of inconsistency. We note that the translated proof from the translated -axioms can be executed in p-time. This leads to a verification in . Moreover, the translation only adds a standard constant to the complexity of the formulas. Finally, we have only to worry about standardly many -axioms. It follows that , for some standard .
The following result is a bit messy, but it does deliver the desired goods.
Theorem 3.2. Suppose is a sub-theory of (qua theorems, in the same language) and . Suppose further that for every , there is an such that . Then, 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 . Suppose . Then, for some with , we have . Let . It follows that, for some , and, thus, . Suppose the -axioms needed to prove the -axioms are all and let . Then, .
Corollary 3.3. Let be a sub-theory of and suppose is Krajíček. Then, is Krajíček.
Extension to a Krajíček-Theory
In this subsection we show that if is finitely axiomatized, then we can locally interpret a Krajíček theory extending in . 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 be finitely axiomised. We write for the depth-of-quantifier-alternations complexity of and for the maximum of the -complexities of the formulas involved in the indwelling translation of . The standard constant 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 .
Theorem 3.4. Suppose and . Then, we have .
With Theorem 3.4 in hand, we prove the following theorem.
Theorem 3.5. Let be finitely axiomatized. Then, a c.e. theory is locally interpretable in . Here enumerates the and is some effective sequence of natural numbers. Moreover, 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 , the desired result is trivial. We take . Suppose . Let enumerate the interpretations . The indwelling translations of the are . Then, we can find sequences and such that, for every , we have: . The indwelling translations of the will be .
We produce the and in stages. At stage we produce and at stage we construct .
At stage 0, we take . We consider stage . We are given . Clearly, . By Theorem 3.4, we can effectively find an and an such that . Let the indwelling translation of be . We find that . So, it follows that:
So, we find the desired with translation . We may conclude that .
Finally, is indeed a Krajíček-theory. If , we are immediately done. If , the desired result follows from Theorem 3.2.
We note that if is an enumeration of translations of the signature or arithmetic to the signature of and if carries an interpretation of in , then we can effectively enumerate translations supporting the as . Thus our axiomatization of can be made decidable.
Remark 3.6. We note that every finitely axiomatised model-interprets in a sense a Krajíček-variant. Consider any model of . In case all interpretations of in contain , for some , the identical interpretation gives us a Krajíček-extension of . If not, there is an in in which we have . Using this we can construct an internal model of a Krajíček-extension since local interpretability in implies global interpretability in . 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 . We call these schemes , 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 but its translation to a relativised format where identity becomes an equivalence relation. We will assume relativised interpretation here.
Let be a single sentence expressing the axioms of 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 be a consistent Krajíček-theory. Suppose . Then, .
Proof. Suppose . Let be any interpretation of predicate logic in the desired signature in . Let be the indwelling translation of and let be the indwelling translation of . Consider . Clearly, supports an interpretation of . It follows that , since , for some . So, .
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 is a consistent sequential Krajíček-theory. Then, is -complete.
Proof. Since is sequential, there is an . We fix with indwelling translation .
Let be any -formula. We find a such that
Here we assume that the and the witness of are combined in one existential quantifier. We show that:
A. is true iff is true.
B. is true iff, for some , we have .
We first prove (A). The right-to-left direction is trivial. We show left-to-right. Suppose is true. Then, is true or is true. In the first case we are done. In the second case we have, , for some , by the definition of . But, by -completeness, we also have . So, would be inconsistent. Quod non.
We prove (B). Suppose is true. Then, by (A), we find that is true. So, . In the other direction, suppose , and . It follows that is true or is true. In the first case we are immediately done. In the second case, we get a contradiction via -completeness as before.3
We claim that
Suppose that is true. Let be any interpretation of predicate logic in the desired signature in with indwelling translation . We consider the translation . Clearly, supports an interpretation . It follows that, for some , we have . By (A), we have is true. So, certainly:
and, thus, .
We may conclude that .
We prove the converse. Suppose . We show that, for any , the sentence is true. By local reflexivity, there is an , such that . By , we find that
Since , it follows that, . By (B), we may conclude that 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 is -rigid iff its endomorphism monoid in is trivial, i.e., all self-interpretations of are -equal to the identity. We say that is interpretation-categorical if it is -rigid and that it is sententially interpretation-rigid if it is -rigid.
The theory is -invertible iff its endomorphism monoid in is a group. We note that is -invertible iff all its self-interpretations are bi-interpretations and that it is -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, -rigid and also a Krajíček-theory.
Let be given by:
,
,
.
Consider the models and . The interpretation yields a mapping of automorphisms. It is easy to see that is not surjective. However, if had an -inverse, would have to be an isomorphism. So, DLO is not -invertible.
The following basic result was pointed out to me by ChatGPT.
Theorem 4.2. Let be a category and suppose the endomorphism monoid of is a group. Suppose is a retract of . Then, is isomorphic to and, hence, the endomorphism monoid of is also a group.
Proof. Suppose and and . It follows that . But, by assumption, is invertible, so it must be . ❑
Thus we may conclude that properties like -rigidity and -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 be a c.e. theory and let . Suppose that the theory is consistent. Here the are the numerals provided by . Then, there is sentence such that is consistent and .
Proof. Let . By the Fixed Point Lemma, we find a with
We can assume that both the substitution function and the proof-predicate are elementary. Moreover, the graph of exponentiation can be represented by a -formula in such a way that proves uniqueness of values on standard arguments. It follows that can be written as , where is elementary. We find: if is true, then , and if is false, then .
Our first order of business is to prove that is consistent with and that is false.
Suppose . Then, (i) is true or (ii) is true.
Case i. We find, by the usual proof of -completeness and the fact that the internal witness is standard, that . This contradicts the fact that is consistent.
Case ii. We have , by the definition of . This again contradicts the fact that is consistent.
So, is consistent with and, a fortiori, is consistent with .
If were true, we would have . We have already seen that this does not hold.
Let . We show that . Since is false, we find
for all . We work in . Let be a witness of . Suppose . Then . So, and, thus, by Axiom R5, . It follows, by Axiom R4, that , and, thus, , but this contradicts . So, .
We note that can also be written as .
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 and let . Suppose is consistent and . Then, is not -invertible.
Proof. By Theorem 4.3, there is a such that is consistent and extends . Clearly, we have . Let , and witness the restricted interpretation. Let . Suppose is -invertible. Let be the promised -inverse. We take . By the Fixed Point Lemma, we find with . We have:
So, and, hence, . On the other hand, as a sentential congruence is faithful, so . But this contradicts the consistency of .
We prove our main result.
Theorem 4.6. Suppose is -invertible. Then, is a Krajíček-theory.
Proof. We prove the contraposed implication. Suppose is not a Krajíček-theory. It follows that there is an such that is consistent. By the Interpretation Existence Lemma, our Theorem 2.2, we have . By Theorem 4.5, we see that is not -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 and closed under the arithmetical operations and the smash function.
We fix a c.e. consistent sequential theory . Let iff . For , we define:
expresses that is an initial homomorphic embedding of into . Here it is intended that both the domain is downward closed under and the range is downward closed under . Also it is intended that our homomorphism commutes with the smash function.
if is an -cut, in other words, if and is the identical initial embedding on .
Let ,
iff . Moreover, iff , for some .
iff .
iff and, for all , . Moreover, iff , for some .
is initial iff, for all , there is an such that .
is strongly initial iff, for all , there is an such that .
We collect some easy facts.
Lemma 5.1. Let be a consistent c.e. sequential theory.
a. is a partial pre-order and is a strict partial order.
b. and , then , and if and , then .
c. Suppose . Then, implies .
d. Suppose is a -sentence. Then .
A fundamental insight is as follows.
Theorem 5.2 (Pudlák). Let a consistent sequential c.e. theory. The ordering is downward-directed, i.e., for all , there is a , such that and . Moreover, we can find such that and .
The proof uses the machinery of sequences to produce an isomorphic embedding of an -cut in . See [7] or [4] or [Vis13].
We will use the following consequence.
Lemma 5.3. Let and let . Suppose . Then, there is an , such that .
Proof. We can find with and . Then, .
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 with a unary predicate and a binary predicate . Let . We will pretend that 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:
is the theory in the language of extended with a unary predicate and a binary predicate given by the following set of axioms:
, where form expresses that is a -formula.
, where sub arithmetises the sub-formula relation.
, where is a (standard) -formula and the numeral is derived from .
.
The commutation conditions for restricted to -formulas in , where the code sequences.
Suppose . We have iff .
We have:
Theorem 5.4 (Interpretation Existence Lemma 2). .
See [18 Theorems 3.4 and 4.5]. Let .
A fundamental insight is cut-intersection.
Theorem 5.5 (Cut-Intersection). In , there is an -cut , such that, for every defined in the -language, we have .
We specify . Let stand for an empty string. We define:
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 to . This operation can be arithmetised. Let the Gödel number of be . So, we want something like .
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 is a -cut. We treat two cases.
Downward closure: We reason in . Suppose and . Consider any such that . (Here we treat ‘’ as an internal variable.) It follows that . By the commutation conditions, we find . Applying the commutation conditions again, we may conclude that .
Closure under Addition: We reason in . Suppose and are in and suppose . So, and . We find and, thus, .
We prove the second claim. We reason in . Suppose and . Then, . Since is standard, we find .
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 is a consistent, sequential, c.e., arithmetically grounded theory. Let be a witness of arithmetical groundedness. We have
.
For every -sentence and for every , we have .
.
Let and be -sentences and suppose . Then, .
Proof. Ad (1): By a result of Wilkie, see [4 pp. 366–371], we have . So, for some , we have . Since and can be written in -form, by downward persistence, we find that , and, thus, , since is already -provably closed under .
Ad (2): Since is sequential, it is locally essentially reflexive. This means that, for every -sentence and for every , we can find an , such that . Since , we find, by the upward persistence of -sentences, that .
Ad (3): By (2), we have . By the Interpretation Existence Lemma 2.2, we have , where we have a truth predicate for . We have . We have a truth predicate of , inside , so we can find a
liar sentence such that . So, . So, and are not elementarily equivalent and a fortiori not isomorphic. Thus, the embedding must be strictly initial. So, has a strict end-extension inside . It follows that, -verifiably, we must have by [21 Proposition 1].
Ad (4): Suppose . By the results of [20], there is a -cut such that . It follows that . So, since , we find .
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 is a consistent, sequential, c.e., arithmetically grounded theory. Suppose is a -least element. Then, there is a -sentence , such that and .
Proof. We find with . Here the witness comparison ordering applies just to the first existential quantifier of .
Our first order of business, is to show that . Suppose . For some , we have . It follows that . Quod non, by Theorem 5.8(2).
We define . We note that is identical to or, in other words, . The Löb conditions for are -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 is . We have:
By the Interpretation Existence Lemma, we find an interpretation with
Let , where ID is the identity interpretation on . So, , i.e., .
Corollary 5.10. Suppose is a consistent, sequential, arithmetically grounded theory. Then, there is a non-initial self-interpretation of .
Proof. Let witness arithmetical groundedness. Let be based on the translation of a witnessing interpretation of . Suppose we had with . It follows that . Since, according to , we have inside , by upwards persistence, it follows that . 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 for interpretations in using [2].
The Characterisation
We will prove the following characterisation of consistent c.e. Krajíček-theories.
Theorem 5.13. Let be a consistent c.e. sequential theory. The following are equivalent:
a. is a Krajíček-theory.
b. All self-interpretations of are strongly initial.
c. All self-interpretations of 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) (b): This is Lemma 5.14.
(b) (c): This is trivial.
(c) (a): Suppose is a consistent sequential c.e. theory and suppose all self-interpretations of are initial. Suppose, in order to obtain a contradiction, that is not a Krajíček-theory. This tells us that, for some , the theory is consistent. By Theorem 4.3, there is a such that is consistent and . Theorem 5.15 tells us that all self-interpretations of are initial. Moreover, by Lemma 5.16, is arithmetically grounded. But his contradicts the consistency of in the light of Corollary 5.10.
We prove Lemma 5.14.
Lemma 5.14. Let be a consistent c.e. sequential Krajíček-theory. Then any self-interpretation of is strongly initial.
Proof. We work in . Consider any . Let and . Let witness . We know that , for some . Let in be an -cut such that . It follows that , since we have inside .
We want to show that . We reason in . It suffices that every element of is in the range of . Let be an arbitrary element of and let be a witness of . It follows that is a witness of . Since , we find that . Ergo, is in the range of .
Let . We reason in . Suppose . If follows that . We have , so . Quod non.
We prove that finite extensions preserve the property that all self-interpretations are initial.
Theorem 5.15. Let be a consistent c.e. sequential theory and let be any -sentence such that is consistent. Suppose all self-interpretations of are initial. Then, all self-interpretations of are initial.
Proof. Let with indwelling translation . Let be a self-interpretation of and let . Let be the indwelling translation of and let be the indwelling translation of . Let be the self-interpretation of based on and let be the element of based on . We can find an such that . Let . Then, .
We prove the promised Lemma 5.16.
Lemma 5.16. Let be a consistent c.e. sequential theory. Suppose all self-interpretations of are initial. Suppose further that is consistent and , for some . Then, is arithmetically grounded.
Proof. We assume the conditions of the theorem. Let and let be the reduct of to the -language. We take .
We find that is initial. Consider any . Let , where . By Lemma 5.3, it follows that there is an , such that , for some . It follows that , where . Since is in the -language, it follows that (†) ,
Theorem 5.5 gives us , so (‡) .
Combining, (†) with (‡), we find that . So, is a desired least element of .
References
Appendix A. A Feferman-FGH-style Result
Axiom sets of theories are supposed to be represented by a formula over . We prove the following.
Theorem A.1. Let be c.e. and sequential. Let . Suppose is -reflexive, i.e., , for each . Then, there is a -sentence , such that and .
Proof. We find with
Here is sharply bounded. We note that we can take to be .
We show that . Suppose . For some , we have
We note that, in , it follows from and , that the promised witness of must satisfy and, thus, . Let, in the real world, . So, we will certainly have . Quod non.
Let . We define
.
, where is arithmetical.
We note that is . To increase readability, we have hidden the dependence of on .
We can easily verify the Löb Conditions for . We find, for sufficiently large , that:
We may conclude that . So, .
We note that at this point, we may drop the assumption that be sufficiently large.
Consider an effective enumeration of . Since, for each , we can find an such that , for all , we find that
By the Interpretation Existence Lemma, we find .
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]S.R. Buss. Bounded Arithmetic. Bibliopolis, Napoli, 1986.
- [2]Dick de Jongh, Mark Jumelet, and Franco Montagna. On the proof of Solovay’s theorem. Studia Logica, 50:51–70, 1991.
- [3]Mirko Engler and Benjamin Zayton. Rigid theories. arXiv preprint, arXiv:2611.16067, 2026.arxiv.org/abs/2611.16067
- [4]Petr Hájek and Pavel Pudlák. Metamathematics of First-Order Arithmetic. Perspectives in Mathematical Logic. Springer, Berlin, 1993.
- [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.
- [7]Pavel Pudlák. Cuts, consistency statements and interpretations. The Journal of Symbolic Logic, 50(2):423–441, 1985.DOI
- [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
- [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.
- [10]Craig Smoryński. Logical Number Theory I, an Introduction. Universitext. Springer, New York, 1991.DOI
- [11]Alfred Tarski, Andrzej Mostowski, and Rafael M. Robinson. Undecidable theories. North-Holland, Amsterdam, 1953.
- [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.
- [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.
- [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.
- [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.
- [17]Albert Visser. On Q. Soft Computing, 21(1):39–56, 2017.
- [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
- [19]Albert Visser. The small-is-very-small principle. Mathematical Logic Quarterly, 65(4):453–478, 2019.arxiv.org/abs/1805.01178
- [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.
- [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.