End extensions of models of fragments of PA

Abstract

In this paper, we prove results concerning the existence of proper end extensions of arbitrary models of fragments of Peano arithmetic (PA). In particular, we give alternative proofs that concern (a) a result of Clote (Fundam Math 127(2):163–170, 1986); (Fundam Math 158(3):301–302, 1998), on the end extendability of arbitrary models of $\Sigma _n$-induction, for $n{\ge } 2$, and (b) the fact that every model of $\Sigma _1$-induction has a proper end extension satisfying $\Delta _0$-induction; although this fact was not explicitly stated before, it follows by earlier results of Enayat and Wong (Ann Pure Appl Log 168:1247–1252, 2017) and Wong (Proc Am Math Soc 144:4021–4024, 2016).

1 Introduction

We work with subsystems of Peano arithmetic (PA) in the usual first-order language of arithmetic LA. As usual, for $n\in {{\mathbb {N}}}$, $I\Sigma _n$ (respectively, $I\Pi _n$) denotes the induction schema for $\Sigma _n$ (respectively, $\Pi _n$) formulas (plus the well-known base theory $PA^-$), $B\Sigma _n$ denotes $I\Delta _0$ plus the collection schema for $\Sigma _n$ formulas and exp denotes the axiom expressing “exponentiation is total” (recall that there is a $\Delta _0$ formula representing the graph of the function $2^x$). As usual, we will identify formulas, proofs etc. with their Gödel numbers. For details, the reader can consult [11] or [12].

Since the mid 1970’s, two of the main aims of research work on fragments of PA have been (1) to study relationships among the various fragments and (2) to produce miniaturizations of significant results concerning PA, such as the so-called “MacDowell–Specker theorem”, i.e., the following result.

Theorem 1

[14] Every model of PA has a proper elementary end extension.

One of the first, ground-breaking papers devoted to these aims was [16]; the first two of the main results contained in this paper can be summarized as follows.

Theorem 2

 

• (a) For all $n\in {{\mathbb {N}}}$,

  $$\begin{aligned} I\Sigma _{n+1} \Rightarrow B\Sigma _{n+1} \Rightarrow I\Sigma _n, \end{aligned}$$

  and the converse implications do not hold.

• (b) For any $n\ge 2$ and any countable structure M,

  $$\begin{aligned} M\models B\Sigma _n \Leftrightarrow M\hbox { has a proper }\Sigma _n\hbox {-elementary end extension } K\models I\Delta _0. \end{aligned}$$

  Furthermore, for any M as above, if M has a proper $\Sigma _1$-elementary end extension satisfying $I\Delta _0$, then $M\models B\Sigma _2$ (and hence M has a proper $\Sigma _2$-elementary end extension satisfying $I\Delta _0$).

Remarks 1

 

• (1) In fact, part (a) of Theorem 2 was more comprehensive, in the sense that it referred to relationships among many more than two fragments of PA, but we have restricted our attention to the ones that are relevant to our subsequent work.

• (2) As noted in [16], the proof of implication ($\Leftarrow$) in part (b) of Theorem 2 does not rely on the countability of the model M.

In view of the fact that the MacDowell–Specker theorem holds for any model of PA, it was natural to wonder whether Theorem 2(b) could be generalized. Indeed, one reads in [3]:

The Kirby–Paris construction used very strongly the countability of the model. In view of the cardinality-free statement of the MacDowell–Specker Theorem, we might expect the conclusion of Theorem 1 to hold for models of any cardinality. Such a possibility was first suggested by A. Wilkie.

In [3], Clote claimed he had proved such a generalization, i.e., that he had proved the implication $\Rightarrow$ of Theorem 2(b) for arbitrary models of $B\Sigma _n$, $n\ge 2$, but it turned out much later that his claim was incorrect. The correct result was stated by the same author in [4] and is as follows.

Theorem 3

For any $n\ge 2$, every model of $I\Sigma _n$ has a proper $\Sigma _n$-elementary end extension satisfying $I\Delta _0$.

Remark 2

The main tool used by Clote was the same as that used in [16], i.e., the construction of a restricted ultrapower of the initial model M.

Given Theorem 3, one of the questions remaining to be answered was whether or not this result holds for $n=0,1$. Let us consider first the case when $n=1$, i.e. the following question.

Question 1

Does every model of $I\Sigma _1$ have a proper $\Sigma _1$-elementary end extension satisfying $I\Delta _0$?

It is easy to see that this problem has a negative solution. Indeed, if every model of $I\Sigma _1$ had a proper $\Sigma _1$-elementary end extension satisfying $I\Delta _0$, then, by Theorem 2(b), every model of $I\Sigma _1$ would satisfy $B\Sigma _2$, which is impossible, since, by Theorem 2(a), there exists a model of $I\Sigma _1+\lnot B\Sigma _2$.

Given this negative answer to Question 1, let us become less ambitious and ask an apparently “easier” question.

Question 2

Does every model of $I\Sigma _1$ have a proper $\Delta _0$-elementary end extension satisfying $I\Delta _0$?

Recalling that, for any structures M, K for LA, if $M\subset _e K\models I\Delta _0$, then $M<_0 K$ (see Theorem 2.7, page 24, in [12]), the new problem can be equivalently stated in the following form.

Problem 1

Does every model of $I\Sigma _1$ have a proper end extension satisfying $I\Delta _0$?

Using Theorem 2(a), it is easy to see that the question whether Theorem  3 holds for $n=0$ has a negative answer, too. Indeed, suppose that every model of $I\Delta _0$ had a proper $\Delta _0$-elementary end extension satisfying $I\Delta _0$. Now recall that, for any structures M, K for LA, if $M\subset _e K\models I\Delta _0$, then $M\models B\Sigma _1$ (see, e.g., Theorem 1 in [18]). Hence, every model of $I\Delta _0$ would satisfy $B\Sigma _1$, which is impossible, since, by Theorem 2(a), there exists a model of $I\Delta _0+\lnot B\Sigma _1$.

In Sect. 2 of the present paper, we provide an alternative proof of Clote’s result, i.e., Theorem 3. By modifying this proof, in the third section, we show that Problem 1 has a positive solution. The final section of the paper is devoted to some remarks and related problems.

Concerning the main result of Sect. 3, our attention has been recently called to the fact that it was implicit in earlier work of A. Enayat and T.L. Wong. Indeed, this result follows by either the proof of Theorem 1 in [19] or combining Corollary 4.2 in [8] and Theorem 3.1 in [10]. Nevertheless, we feel our proof, which involves definable elements, is worth presenting, as it could be of use in resolving related problems.

Before we proceed to the main part of the paper, we note that the guiding principle for the proofs that will follow in the sequel has been to use a single argument (modulo necessary modifications), whose essence can be described in short as follows:

• (i) starting with a consistent theory $T_0$ in a suitable extension of LA, we extend it to a maximal consistent theory T, using a lemma concerning the possibility of witnessing certain bounded existential quantifiers with appropriate constants, and

• (ii) taking as the required extension of the initial model M a structure K with universe an appropriate set of elements definable in a model of the theory T.

For the proof of part (i), the main tool needed is a technical lemma, which concerns the construction, via induction, of a suitable branch in an infinite tree in M (whose nodes are appropriate formulas of the extended language). The proof of part (ii) essentially relies on a combination of well-known facts concerning definable elements in fragments of PA.

2 A proof of Clote’s result

Our main aim in this section is to expand our sketch in the last part of [7] to obtain a full proof of Theorem 3. Our approach is reminiscent of the one taken for the proof of the MacDowell–Specker theorem given by Gaifman in [9] (see also Section 8.2 in [12]). Let us now proceed to the proof.

Proof

Let M be a model of $I\Sigma _n$, $n\ge 2$. LA(M) denotes the language obtained from LA by adding a set of new constant symbols $\{c_a: a\in M\}$ and LA(M, c) the language obtained from LA(M) by adding the new constant symbol c. For convenience, we will often identify the structure M with the structure $M^*$ for LA(M) defined by $M^* = \langle M, \{a: a\in M\}\rangle$.

Let $(\theta _i(x,\vec {v}))_{i\in {\mathbb {N}}}$ be an enumeration of all $\Sigma _{n-1}$ formulas. Note that we may assume each $\theta _i$ is of the form $\exists y{\le }v_{k+1}\eta _i(y,x,v_1,\ldots ,v_{k+1})$ (indeed, we can use dummy variables to introduce an extra bounded existential quantifier at the front). We will need the next lemma, in the proof of which, for every $i\in {{\mathbb {N}}}$ and $w\in M$, we will be working with an enumeration in M, in increasing order, of all (codes of) LA(M) formulas obtained from the LA formula $\theta _i(x,\vec {v})$, if we replace the variables $\vec {v}$ by constant symbols from the set $\{c_a: a\le w\}$. Clearly, we may assume that this enumeration is made in a canonical manner, i.e., we first enumerate all formulas involving constants from the set $\{c_0\}$, then all formulas involving constants from the set $\{c_0,c_1\}$, at least one of which is $c_1$, $\ldots$ and finally all formulas involving constants from the set $\{c_0,c_1,\ldots ,c_w\}$, at least one of which is $c_w$; the idea is that, for each $w\in M$, the enumeration of formulas involving constants from $\{c_0,\ldots ,c_w\}$ will be a “proper initial segment” of the enumeration of all formulas involving the constant $c_{w+1}$. For each $i\in {{\mathbb {N}}}$ and $w\in M$, we call the sequence of LA(M) formulas enumerated as above “canonical (i, w) sequence”.

To make the enumeration more intuitive, we give the following description: We construct a countable sequence of “blocks”, corresponding to the formulas $(\theta _i)_{i\in {{\mathbb {N}}}}$ mentioned above. For each i, the $(i{+}1)$-th block will consist of a sequence of “floors”, corresponding to the elements of M that may be used to replace the variables $\vec {v}$ appearing in the formula $\theta _i$. The canonicity of the enumeration can be depicted as in Fig. 1.

Fig. 1

Enumeration

In the next lemma, given a canonical (i, w) sequence of formulas $(\theta _i^j)_{j\le lh(i,w)}$, where lh(i, w) denotes the length of this sequence, we construct another sequence of formulas $(\theta _i^j)^*, j \le lh(i,w)$, as follows: $(\theta _i^j)^*$ is either the $(j{+}1)$-th formula of the canonical (i, w) sequence, i.e., a formula of the form $\exists y\le c_{a_{k+1}}\eta _i(y,x,c_{a_1},\ldots ,c_{a_{k+1}})$, or the tautology 0 = 0.

Let us now proceed with the exact statement and proof of the lemma. $\square$

Lemma 4

For every $k\in {{\mathbb {N}}}$,

$$\begin{aligned}&M\models \forall w \exists t_0\ldots \exists t_k \exists s_0\ldots \exists s_k \left\{ \bigwedge _{i=0}^{k} lh(t_i)=lh(s_i) \wedge \bigwedge _{i=0}^{k} ``t_i \text { codes the } \right. \\&\quad \text { sequence of all formulas of the form } \theta _i(x,\vec {c}) \text { with the indices of } \vec {c} {\le } w{{''}}\wedge \\&\quad \bigwedge _{i=0}^{k} \forall p{<}lh(s_i) \left[ [\forall z \exists x{>}z Sat_{n{-}1}(S_{i-1} {\wedge } \bigwedge _{j=0}^{p-1} (s_i)_j {\wedge } \theta _i^p(x,\vec {c}),x) \wedge (s_i)_p{=} \theta _i^p(x,\vec {c})] \right. \\&\quad \left. \left. {\vee } [\lnot \forall z \exists x{>}z Sat_{n-1}(S_{i-1} {\wedge } \bigwedge _{j=0}^{p-1} (s_i)_j {\wedge } \theta _i^p(x,\vec {c}),x) \wedge (s_i)_p = (0{=}0)] \right] \right\} \end{aligned}$$

where (i) $Sat_{n-1}$ denotes a complete $\Sigma _{n-1}$ formula and $(s)_p$ denotes the p-th term of (the sequence coded by) s and (ii) $S_{i-1}$ denotes $\bigwedge _{m=0}^{i-1} \bigwedge _{j=0}^{lh(s_m)-1} (s_m)_j$, i.e. the conjunction of the set of formulas obtained by having considered all the layers of all blocks corresponding to the canonical (m, w) sequences, for $0\, {\le }\, m \,{\le }\, i{-}1$ (we note also that, when $i = 0$, $S_{i-1}$ denotes any tautology).

Proof

We will use induction in the metalanguage. So, we suppose that all $m{<}k$ have the property and show that k also has the property; we may assume $k{\ne }0$, since the argument for the case $k = 0$ is essentially similar to the one that follows. In other words, we suppose that

(1)

and prove that

(2)

Note that, for any $i\in {{\mathbb {N}}}$ and $w\in M$,

• (a) there exists a unique element $t_i$ of M coding, in increasing order, all formulas obtained from $\theta _i$ as we described before. In fact, this element lies below an exponential bound, depending on the Gödel number of $\theta _i$ and on w; for example, $t_i$ can be bounded by $(\ulcorner \theta _i \urcorner )^{w^2}$.

• (b) as in (a) above, a similar exponential bound can be put on $s_i$; for simplicity, we will use the same bound as for $t_i$.

It follows that (2) is equivalent to

(3)

Now notice that $\forall b\left[ \ldots \right]$ is a $\Sigma _0(\Sigma _n)$ formula, since it has been constructed by using connectives, bounded quantification and instances of the $\Pi _n$ formula $\forall z \exists x{>}z Sat_{n-1}(\ldots )$ (for the exact definition of the class $\Sigma _0(\Sigma _n)$, see, e.g., Definition 2.2, page 62, of [11]). But it is well-known that $I\Sigma _n$ implies $I\Sigma _0(\Sigma _n)$, for all $n\in {{\mathbb {N}}}$ (see, e.g. Lemma 2.14, page 65, in [11]). Therefore, we may use induction in M to prove (3) or, equivalently, (2).

Since the case $w{=}0$ is similar to the general inductive step, it suffices to show that, for any $a\in M$, if a satisfies $\forall b\left[ \ldots \right]$, then $a{+}1$ also satisfies this formula. So, assuming that, for $b{=}(max\{\ulcorner \theta _0\urcorner , \ldots , \ulcorner \theta _k\urcorner \})^{a^2}$,

(4)

we will show that, for $B\,{=}\,(max\{\ulcorner \theta _0\urcorner , \ldots , \ulcorner \theta _k\urcorner \})^{(a+1)^2}$,

(5)

In what follows, let $\Theta (j,w,t_0,\ldots ,t_j,s_0,\ldots ,s_j)$ denote the formula

By (1), there exist unique elements $t_0^{a+1}, \ldots , t_{k-1}^{a+1}, s_0^{a+1}, \ldots , s_{k-1}^{a+1}$ of M such that

$$\begin{aligned} M\models \Theta \left( k{-}1, a{+}1, t_0^{a+1}, \ldots , t_{k-1}^{a+1}, s_0^{a+1}, \ldots , s_{k-1}^{a+1}\right) \end{aligned}$$

(6)

and, by (4), there exist unique elements $t_0^{a}, \ldots , t_{k}^{a}, s_0^{a}, \ldots , s_{k}^{a}$ such that

$$\begin{aligned} M\models \Theta \left( k, a, t_0^{a}, \ldots , t_{k}^{a}, s_0^{a}, \ldots , s_{k}^{a}\right) . \end{aligned}$$

(7)

Finally, it is clear that there exists a unique element $t_k^{a+1}$ of M coding the canonical $(k,a{+}1)$ sequence of formulas (obtained from $\theta _k$).

Note that, by the canonicity of the construction of the $t_i$’s and the induced canonicity of the construction of the $s_i$’s, we have that

• (i) for any $0{\le }i{\le }k$, $t_i^a$ is an initial segment of $t_i^{a+1}$

• (ii) for any $0{\le }i{\le }k{-}1$, $s_i^a$ is an initial segment of $s_i^{a+1}$.

Now let $\theta _k^0, \ldots , \theta _k^L$ be the formulas coded by $t_k^{a+1}$, that is, the formulas (in increasing order) in the $(k+{1})$-th block of LA(M) formulas described before the Lemma. We claim that

$$\begin{aligned} M\models \forall l\le & {} L \exists S \left\{ lh(S){=}l{+}1 \wedge \forall p \le l \right. \nonumber \\&\left[ \left[ \forall z \exists x{>}z Sat_{n{-}1}\left( \bigwedge _{i=0}^{k-1} s_{i}^{a+1} {\wedge } \bigwedge _{j=0}^{p-1} (S)_j {\wedge } \theta _k^p(x,\vec {c}),x\right) \wedge (S)_p= \theta _k^p(x,\vec {c})\right] \vee \right. \nonumber \\&\left. \left. \left[ \lnot \forall z \exists x{>}z Sat_{n-1}\left( \bigwedge _{i=0}^{k-1} s_{i}^{a+1} \wedge \bigwedge _{j=0}^{p-1} (S)_j \wedge \theta _k^p(x,\vec {c}),x\right) {\wedge } (S)_p= (0{=}0)\right] \right] \right\} ,\nonumber \\ \end{aligned}$$

(8)

where, for the sake of technical simplicity, we identify codes of sequences, e.g., $s_i^{a+1}$, with the corresponding sequences of terms (i.e., formulas). Note that, for each $i\,{\le }\,k{-}1$, $s_i^{a+1}$ is a sequence of formulas corresponding to the canonical $(i,a{+}1)$ sequence of formulas and S corresponds to a sequence of formulas obtained from the canonical $(k,a{+}1)$ sequence.

To prove (8), we use induction on l; note that the formula after $\forall l{\le }L$ in (8) is (equivalent to) a $\Sigma _0(\Sigma _n)$ formula, so we may use induction in M as before. For simplicity, we will deal with the case $l=0$ only.

First note that, by the construction of the sequences $s_0^{a+1}, \ldots , s_{k-1}^{a+1}$, we have that

$$\begin{aligned} M\models \forall z \exists x{>}z Sat_{n{-}1}\left( \bigwedge _{i=0}^{k-1} s_{i}^{a+1}\right) . \end{aligned}$$

(9)

Since, clearly,

$$\begin{aligned}&M\models \forall z \exists x{>}z Sat_{n{-}1}\left( \bigwedge _{i=0}^{k-1} s_{i}^{a+1} \wedge \theta _k^0(x,\vec {c}),x\right) \\&\vee \lnot \forall z \exists x{>}z Sat_{n{-}1}\left( \bigwedge _{i=0}^{k-1} s_{i}^{a+1} \wedge \theta _k^0(x,\vec {c}),x\right) \end{aligned}$$

and hence that $M\models \exists S \Gamma (S)$, where $\Gamma (S)$ denotes the formula in $\{\ldots \}$ in (8).

Having proved our claim, we let $s_k^{a+1}$ be the unique S satisfying the formula $\{\ldots \}$ in (8) for $l=L$. It is not difficult to check that $s_k^a$ is a proper initial segment of $s_k^{a+1}$ and that

$$\begin{aligned} M\models \Theta (k, a{+}1, t_0^{a+1}, \ldots , t_{k}^{a+1}, s_0^{a+1}, \ldots , s_{k}^{a+1}), \end{aligned}$$

which finishes the proof of the Lemma. $\square$

We continue with a lemma, which concerns a nice property of the sequence $(\theta _i^j)^*$, $j\,{\le }\,lh(i,w)$, constructed according to the procedure stated in Lemma 4. This property can be named “witness property” and can be described in short as follows: if a formula of the form $\exists y\,{\le }\,c_{a_{k+1}}\eta (y,x,c_{a_1},\ldots ,c_{a_{k+1}})$ becomes a member of the sequence corresponding to $\exists y\,{\le }\,v_{a_{k+1}}\eta (y,x,\vec {v})$, then there exists $b{\le }a_{k+1}$ such that the formula $\eta (c_b,x,c_{a_1},\ldots ,c_{a_{k+1}})$ becomes a member of the sequence corresponding to the formula $\eta (y,x,\vec {v})$. The exact statement and proof of this fact are given below.

Lemma 5

Suppose that $\exists y{\le }v_{k+1}\eta (y,x,\vec {v})$ and $\eta (y,x,\vec {v})$ appear as $\theta _m$ and $\theta _l$, respectively, in the enumeration $(\theta _i(x,\vec {v}))_{i\in {\mathbb {N}}}$ of $\Sigma _{n-1}$ formulas, where $m{>}l$. Then, for any elements $\vec {a}$ of M,

(if $l{>}m$, a similar statement holds, which can be proved in the same way)

Proof

Assume $b{\ge }\vec {a}, d_0, \ldots , d_m, e_0, \ldots , e_m$ and f are elements of M such that the formula

$$\begin{aligned} \bigwedge _{i=0}^m lh(t_i){=}\,lh(s_i)\wedge \ldots \wedge f{<}lh(s_m)\wedge (s_m)_f{=} \exists y{\le } c_{a_{k+1}}\eta (y,x,\vec {c}) \end{aligned}$$

is satisfied in M when we replace w by b, $t_i$ by $d_i$ and $s_i$ by $e_i$, for all $0{\le }i{\le }m$, and r by f. It follows that

$$\begin{aligned} M\models \forall z \exists x{>}z Sat_{n-1}(S_{m-1}\wedge \bigwedge _{j=0}^{f-1} (s_m)_j\wedge \exists y{\le }c_{a_{k+1}} \eta (y,x,\vec {c}),x). \end{aligned}$$

By well-known properties of the formula $Sat_{n-1}$, we deduce that

$$\begin{aligned} M\models \forall z \exists x{>}z \exists y{\le }a_{k+1} Sat_{n-1}\left( S_{m-1}\wedge \bigwedge _{j=0}^{f-1} (s_m)_j\wedge \eta (c_y,x,\vec {c}),x\right) . \end{aligned}$$

(10)

But this implies that

$$\begin{aligned} M\models \exists y{\le } a_{k+1} \forall z \exists x{>}z Sat_{n-1}\left( S_{m-1}\wedge \bigwedge _{j=0}^{f-1} (s_m)_j\wedge \eta (c_y,x,\vec {c}),x\right) . \end{aligned}$$

(11)

Indeed, if (11) failed, then we would have

$$\begin{aligned} M\models \forall y{\le } a_{k+1} \exists z \forall x{>}z \lnot Sat_{n-1}\left( S_{m-1}\wedge \bigwedge _{j=0}^{f-1} (s_m)_j\wedge \eta (c_y,x,\vec {c}),x\right) , \end{aligned}$$

which, by the fact that M satisfies $\Sigma _n$ collection, would give

$$\begin{aligned} M\models \exists t \forall y{\le } a_{k+1} \exists z{<}t \forall x{>}z \lnot Sat_{n-1}\left( S_{m-1}\wedge \bigwedge _{j=0}^{f-1} (s_m)_j\wedge \eta (c_y,x,\vec {c}),x\right) . \end{aligned}$$

But then there exists $T{\in }M$ such that

$$\begin{aligned} M\models \forall y{\le } a_{k+1} \forall x{>}T \lnot Sat_{n-1}\left( S_{m-1}\wedge \bigwedge _{j=0}^{f-1} (s_m)_j\wedge \eta (c_y,x,\vec {c}),x\right) , \end{aligned}$$

which contradicts (10).

Therefore, (11) holds and so there exists $g{\in }M$, $g{\le }a_{k+1}$ such that

$$\begin{aligned} M\models \forall z \exists x{>}z Sat_{n-1}\left( S_{m-1}\wedge \bigwedge _{j=0}^{f-1} (s_m)_j \wedge \eta (c_g,x,\vec {c}),x\right) . \end{aligned}$$

(12)

Let now h be an element of M such that $M\models h{<}lh(t_l)\wedge (t_l)_h=\eta (x,c_g,\vec {c})$. If $M\models (s_l)_h= (0=0)$, then it would be the case that

$$\begin{aligned} M\models \lnot \forall z \exists x{>}z Sat_{n-1}\left( S_{l-1}\wedge \bigwedge _{j=0}^{h-1} (s_l)_j \wedge \eta (c_g,x,\vec {c}),x\right) , \end{aligned}$$

which would contradict (12). It follows that $M \models (s_l)_h = \eta (c_g,x,\vec {c})$, as required. $\square$

Let us now consider the following theory in the language LA(M, c)

$$\begin{aligned} T=Th(M)+c{>}M+\Theta , \end{aligned}$$

where Th(M) denotes, as usual, the elementary diagram of M, $c{>}M$ denotes the set $\{c{>} c_a: a{\in } M\}$ and $\Theta$ denotes the set $\bigcup _{i\in {{\mathbb {N}}}}\{(\theta _i^j)^*: j\in M\}$, where $(\theta _i^j)^*$ is the formula $\theta _i(c,\vec {c})$ or $0{=}0$, depending on the term $(s_{i,w})_j$ of (the sequence coded by) $s_{i,w}$, for some $w{\in }M$, or, equivalently, for any $w{\in }M$ such that the indices of $\vec {c}$ are below w; note that, once $(\theta _i^j)^*$ enters the enumeration at a level, it will stay there “to the end” (of the enumeration).

Observe that T is a consistent set of sentences of LA(M, c); indeed, every finite subset $T^\prime$ of this set is satisfied in the structure for LA(M, c) obtained from M by interpreting each constant $c_a$ as the corresponding element of M and c as a suitably large element of M. Let J be a model of (a maximal consistent extension $\Sigma$ of) T and let $K^{n-1}(J)$ be the substructure of J whose universe is the set of $\Sigma _{n-1}$ definable elements in J. Clearly, we may identify $K^{n-1}(J)$ with the substructure K of $J\upharpoonright LA$ (i.e., the reduct of J to LA), whose universe is the set of elements $\Sigma _{n-1}$ definable in $J{\upharpoonright } LA$ using parameters from the set $\{c_a^J: a{\in } M\}\cup \{c^J\}$ (for the precise definition, see, e.g., p. 130 in [12]). To complete the proof of Theorem 3, it suffices to prove the following result.

Lemma 6

M is (isomorphic to) a proper $\Sigma _n$-elementary initial segment of K and $K\models I\Delta _0$.

Proof

Let $f: M\rightarrow K$ be the function defined by $f(a) = c_a^J$, for each $a{\in }M$. Clearly, f maps M isomorphically onto a substructure L of K and so it suffices to show that K is a proper $\Sigma _n$-elementary end extension of L.

First, note that $K<_{n-1} J{\upharpoonright } LA$, by Theorem 10.1, p. 131, in [12]. It follows that $K^*\models \Pi _n(M)$, where $\Pi _n(M)$ denotes the set of $\Pi _n$ sentences of LA(M) which are true in $M^*$, i.e., the natural expansion of M to a structure for LA(M). Therefore, $L<_n K$.

Since, clearly, K is a proper extension of L, it remains to show that $L\subset _e K$. So let $a\in M$ and $d\in K$ such that $K\models d<c_a^J$ or, equivalently, $J\models d<c_a^J$. By the definition of K, there exist a $\Sigma _{n-1}$ formula $\varphi (y,x,\vec {v})$ and $\vec {a}\in M$ such that $\varphi (y,c,\vec {c})$ defines d in J. Then $J\models \exists y{\le }c_a^J \varphi (y,c,\vec {c})$ and hence $\exists y{\le }c_a \varphi (y,c,\vec {c})\in T$; indeed, if $\exists y{\le }c_a \varphi (y,c,\vec {c})\notin T$ held, we would have that $M{\models } \, \exists z \forall x{>}z\lnot \exists y{\le }c_a\varphi (y,x,\vec {c})$, i.e., $M\models \forall x{>}c_{a^*}\forall y{\le }c_a\lnot \varphi (y,x,\vec {c})$ for some $a^*{\in } M$, which, given that $c{>}c_{a^*}{\in } T$, would imply that $J\models \forall y{\le }c_a^J\lnot \varphi (y,c,\vec {c})$. By Lemma 5, there exists $b{\in }M$ such that $M\models b{<}a$ and $\varphi (c_b,c,\vec {c}) {\in } T$. Therefore, $J\models \varphi (c_b,c,\vec {c})$ and hence $d = c_b^J$, as required.

Finally, note that $K\models I\Delta _0$, since $K{<}_{n-1}J{\upharpoonright } LA$ and $J{\upharpoonright } LA\models I\Delta _0$. $\square$

The proof of Theorem 3 is now complete. $\square$

Remark 3

It is easy to see that, in Theorem 3, the model K obtained satisfies a theory strictly stronger than $I\Delta _0$. Indeed, by Theorem 0.2 in [13], for $n{\ge }2$, $I\Sigma _n\Rightarrow I\Pi _n^-$, where $I\Pi _n^-$ denotes the theory of induction for $\Pi _n$ parameter free formulas. But, clearly, $I\Pi _n^-$ holds in M and $I\Pi _n^-$ is a set of $\Sigma _{n+1}$ sentences (recall Theorem 0.6 in [13]). Therefore, $K\models I\Pi _n^-$. Now recall that $I\Pi _n^-$ is strictly stronger than $I\Delta _0$; indeed, by Proposition 1.10 in [13], ($B\Sigma _1$ and hence) $I\Delta _0$ does not prove $I\Pi _1^-$. It is probably known that the model K satisfies a theory strictly stronger than $I\Pi _n^-$, but we will not pursue this question further, as it lies outside our area of interest in the present paper.

3 End extending models of $\Sigma _1$-induction

In this section, we show that it is possible to modify the proof of Theorem 3 to prove that Problem 1 has a positive solution, i.e. to prove the next result.

Theorem 7

Every model of $I\Sigma _1$ has a proper end extension satisfying $I\Delta _0$.

The main difference between the proof of Theorem 3 in Section 2 and the modification we are about to use to prove Theorem 7 is that in the latter we have to use a consistency statement instead of the formula concerning satisfiability of formulas that was used in the former. Note that

• (i) it would not be possible to work with formulas of the form $\forall z \exists x{>}z$ $Sat_0(\ldots )$ here, as this would require the use of $I\Sigma _2$, while we only have that $M\models I\Sigma _1$. So we have to follow an alternative approach, namely one that employs the use of a formal consistency statement, by means of which the problematic quantifier complexity induced by the expression $\forall z \exists x{>}z$ is “absorbed” within this statement; actually, the appearance of the expression $\forall z \exists x{>}z$ can be avoided altogether, since the same role can be played, essentially, by the constant c, through including the condition $c{>}M$ in the theory whose consistency is being considered.

• (ii) it is not necessary to work with a formula expressing semantic tableau consistency, as we did in [6]. Indeed, in that paper, we had to work with the restricted notion of consistency $Tabcon(\ldots )$, since the model under consideration there satisfied a theory strictly weaker than $I\Sigma _1$; here $I\Sigma _1$ is satisfied in the model and hence the usual formula $Con(\ldots )$ may be employed - recall the well-known fact that the notions of (usual) consistency and semantic tableau consistency are equivalent in models in which superexponentiation is total and hence in models satisfying $I\Sigma _1$.

Let us proceed now to proving Theorem 7.

Proof

Let M be an arbitrary model of $I\Sigma _1$ and LA(M), LA(M, c) be the extensions of LA defined at the beginning of the proof of Theorem 3.

We first mention a result which is well-known, but we recall it for the sake of completeness. $\square$

Lemma 8

$M\models Con (I\Delta _0+\Delta +c{>}M)$, where $\Delta$ denotes the $\Delta _0$-diagram of M.

Proof

This is essentially a variant of the proof of Lemma 8.10 in [17]. Note that working with the formula $Con(\ldots )$ does not differ essentially from working with the formula $Tabcon(\ldots )$ in [17], since M satisfies $I\Sigma _1$. $\square$

Now we proceed to a result similar to Lemma 4, in the proof of which we will be working with (a) an enumeration $(\theta _i(c,\vec {v}))_{i\in {\mathbb {N}}}$ of all $\Sigma _1$ formulas (as in the previous section, we may assume that each $\theta _i$ is of the form $\exists y{\le }v_{k+1} \eta _i(y,c,v_1,\ldots ,v_{k+1})$, where $\eta _i$ is a $\Sigma _1$ formula) and (b) an enumeration in M, in increasing order, of the set of all (codes of) LA(M, c) formulas obtained from the LA(c) formula $\theta _i(c,\vec {v})$, if we replace the variables $\vec {v}$ by constant symbols from the set $\{c_a: a{\le } w\}$. As before, we will assume that this enumeration is made in a “canonical manner” (see explanation before Lemma 4).

Lemma 9

For every $k\in {{\mathbb {N}}}$,

where $T_0$ denotes $I\Delta _0{+}\Delta {+}c{>}M$ and $S_{i-1}$ denotes $\bigwedge _{m=0}^{i{-}1} \bigwedge _{j=0}^{lh(s_m)-1} (s_m)_j$ (note, as before, that $S_{i-1}$ denotes any tautology, when $i = 0$).

Proof

The proof is essentially identical with that of Lemma 4, the only difference being that the formula $Con(\ldots )$ is used instead of the formula $Sat_{n-1}(\ldots )$ to extend the initial theory $T_0$. $\square$

Next comes a lemma concerning a witnessing property analogous to the one stated in Lemma 5.

Lemma 10

Suppose that $\exists y{\le }v_{k+1}\eta (y,c,\vec {v})$ and $\eta (y,c,\vec {v})$ appear as $\theta _m$ and $\theta _l$, respectively, in the enumeration $(\theta _i(c,\vec {v}))_{i\in {\mathbb {N}}}$ of $\Sigma _1$ formulas, where $m{>}l$. Then, for any elements $\vec {a}$ of M,

(if $l{>}m$, a similar statement holds, which can be proved in the same way)

Proof

Assume $b{\ge }\vec {a}, d_0, \ldots , d_m, e_0, \ldots , e_m$ and f are elements of M such that the formula

$$\begin{aligned} \bigwedge _{i=0}^m lh(t_i) = lh(s_i)\wedge \cdots \wedge r{<}lh(s_m)\wedge (s_m)_r = \exists y{\le } c_{a_{k+1}}\eta (y,c,\vec {c}) \end{aligned}$$

is satisfied in M when we replace w by b, $t_i$ by $d_i$ and $s_i$ by $e_i$, for all $0{\le }i{\le }m$, and r by f. It follows that

$$\begin{aligned} M\models Con\left( T_0+S_{m-1}\wedge \bigwedge _{j=0}^{f-1} (s_m)_j\wedge \exists y{\le }c_{a_{k+1}} \eta (y,c,\vec {c})\right) . \end{aligned}$$

(13)

We claim that

$$\begin{aligned} M\models \exists y{\le } a_{k+1} Con\left( T_0{+}S_{m-1}\wedge \bigwedge _{j=0}^{f-1} (s_m)_j\wedge \eta (c_y,c,\vec {c})\right) . \end{aligned}$$

(14)

Indeed, if (14) failed, then we would have

$$\begin{aligned} M\models \forall y{\le } a_{k+1} \lnot Con\left( T_0+S_{m-1}\wedge \bigwedge _{j=0}^{f-1} (s_m)_j\wedge \eta (c_y,c,\vec {c})\right) , \end{aligned}$$

that is,

Recalling now that $I\Delta _0\vdash \forall x \forall y (x{\le }y{\leftrightarrow }x{<}y\vee x{=}y)$ and that $M \models I\Sigma _1$, we can prove by induction that

Therefore, (14) holds and so there exists $g{\in }M$, $g{\le }a_{k+1}$ such that

$$\begin{aligned} M\models Con\left( T_0\wedge S_{m-1}\wedge \bigwedge _{j=0}^{f-1} (s_m)_j \wedge \eta (c_g,c,\vec {c})\right) . \end{aligned}$$

(15)

Let now h be an element of M such that $M\models h{<}lh(t_l)\wedge (t_l)_h=\eta (c_g,x,\vec {c})$. If $M\models (s_l)_h= (0=0)$, then it would be the case that

$$\begin{aligned} M\models \lnot Con\left( T_0\wedge S_{l-1}\wedge \bigwedge _{j=0}^{h-1} (s_l)_j \wedge \eta (c_g,c,\vec {c})\right) , \end{aligned}$$

which would contradict (15). It follows that $M \models (s_l)_h = \eta (c_g,c,\vec {c})$, as required. $\square$

We now consider the theory $T=I\Delta _0{+}\Delta {+}c{>}M{+}\Theta$ in the language LA(M, c), where $\Theta$ denotes the set $\bigcup _{i\in {\mathbb {N}}}\{(\theta _i^j)^*: j\in M\}$, with $(\theta _i^j)^*$ denoting the formula $\theta _i(c,\vec {c})$ or $0{=}0$, depending on the term $(s_{i,w})_j$ of (the sequence coded by) $s_{i,w}$, for any $w\in M$ large enough.

T is clearly consistent, so let J be a model of T and K denote the substructure of $J {\upharpoonright } LA$ whose universe is the set of elements $\Sigma _1$ definable in $J{\upharpoonright } LA$ using parameters from the set $\{c_a^J: a\in M\}\cup \{c^J\}$. To complete the proof of Theorem 7, it suffices to prove the following result.

Lemma 11

M is (isomorphic to) a proper initial segment of K and $K\models I\Delta _0$.

Proof

First, note that $K\models I\Delta _0$, since $J\models I\Delta _0$ and $K{<}_1 J\upharpoonright LA$ (recall Theorem 10.1 in [12]).

Now let $f:M\rightarrow K$ be the function defined by $f(a)=c_a^J$, for any $a{\in } M$. Since T contains the diagram of M, f maps M isomorphically onto a substructure L of K and so it suffices to show that K is a proper end extension of L. Clearly, K is a proper extension of L, so it remains to show that $L\subset _e K$. But this can be proved by an easy modification of the second part of the proof of Lemma 6, using Lemma 10. $\square$

The proof of Theorem 7 is now complete. $\square$

Remark 4

As we have noted before, Theorem 7 follows from earlier work of A. Enayat and T. L. Wong; indeed, this result follows by either the proof of Theorem 1 in [19] or a combination of Corollary 4.2 in [8] and Theorem 3.1 in [10]. In fact, Theorem 1 in [19] leads to a positive answer of the second part of Problem 1 in [15], i.e., the following question: is every model M of $I\Sigma _1$ properly end extendable to $K\models I\Sigma _1$ such that $M\models I\Sigma _1^*$ in K? Note that $I\Sigma _1^*$ denotes the theory, in the second-order language of arithmetic, which concerns induction for $\Sigma _1^*$ formulas, i.e., formulas of the form $\exists \vec {x_1}\forall \vec {x_2} \ldots \varphi (\vec {x_1},\vec {x_2},\ldots )$, with n alternating blocks of similar first-order quantifiers where the only quantifiers in $\varphi$ are bounded first-order.

4 Concluding remarks

In view of the negative answer to Question 1, Theorem 7 is the best possible, concerning the quantifier complexity of the formulas that are satisfied in M iff they are satisfied in its end extension. Similarly, Clote’s result, i.e. Theorem 3, is the best possible, in the sense that, for any $n\ge 2$, there exists a model of $I\Sigma _n$ which has no proper $\Sigma _{n+1}$-elementary end extension satisfying $I\Delta _0$. Indeed, if there were no such model, by implication $\Leftarrow$ of Theorem 2(b), all models of $I\Sigma _n$, $n{\ge } 2$, would satisfy $B\Sigma _{n+1}$, which is impossible, by Theorem 2(a), i.e., by the fact that $I\Sigma _n\not \Rightarrow B\Sigma _{n+1}$.

One can naturally wonder whether Theorem 3 holds if we consider the theory $B\Sigma _n$ instead of the theory $I\Sigma _n$.

Problem 2

Does every model of $B\Sigma _n$, $n{\ge } 2$, have a proper $\Sigma _n$-elementary end extension satisfying $I\Delta _0$?

Recalling that $B\Sigma _1\Leftrightarrow B\Sigma _0$ and that $I\Delta _0$ is strictly weaker than $B\Sigma _1$, the following problem also arises naturally.

Problem 3

Does every model of $B\Sigma _1$ have a proper end extension satisfying $I\Delta _0$?

Both these problems remain open, with Problem 3 being considered to be of particular interest (see “Fundamental problem F” in [5]).

Concerning Problem 2, it has a positive answer, if attention is restricted to countable models (recall implication ($\Rightarrow$) of Theorem 2(b)).

It is easy to see that the answer to Problem 2 is also positive, if we demand that the end extension is $\Sigma _{n-1}$-elementary, for $n\ge 3$; indeed, if M is a model of $B\Sigma _n$, $n\ge 3$, then M satisfies $I\Sigma _{n-1}$ and hence, by Clote’s result, it has a proper $\Sigma _{n-1}$-elementary end extension satisfying $I\Delta _0$. In view of this observation, it remains to see what happens in the case $n=2$, i.e., to determine the answer to the following question.

Question 3

Does every model of $B\Sigma _2$ have a proper $\Sigma _1$-elementary end extension satisfying $I\Delta _0$?

A more general question worth considering, in view of Theorem 7 and the negative answer to Question 1 (discussed in the first section) is as follows.

Question 4

Is there a theory T, with strength strictly between those of $I\Sigma _2$ and $I\Sigma _1$, such that every model of T has a proper $\Sigma _1$-elementary end extension satisfying $I\Delta _0$?

Problem 3 was studied extensively in [18]. In fact, Wilkie and Paris proved that it has a positive answer, if (a) attention is restricted to countable models and (b) the initial model satisfies an extra condition. Among the results proved in [18], the following is perhaps the most interesting one.

Theorem 12

[18] Every countable model of $B\Sigma _1+exp$ has a proper end extension satisfying $I\Delta _0$.

Remarks 5

 

• (1) Note that Problem 3 is considered especially interesting, since it is connected to problems in computational complexity theory (for details, see, e.g., [5]).

• (2) Problem 3 is known to have a negative answer, under an assumption concerning the collapse of the $\Delta _0$ hierarchy. Indeed, in [18] it was proved that there exists a countable model of $B\Sigma _1$ which does not have a proper end extension satisfying $I\Delta _0$, provided that the $\Delta _0$ hierarchy collapses provably in $I\Delta _0$, i.e., there exists a fixed n such that, for any $\theta \in \Delta _0$ there is $\eta \in \Delta _0$ in prenex normal form with at most n alternations of bounded quantifiers such that $I\Delta _0 \vdash \theta \leftrightarrow \eta$ (this hypothesis is usually denoted by $I\Delta _0\vdash \lnot \Delta _0 H$).

In view of the above results and comments, it is natural to wonder whether Theorem 7 or Theorem 12 can be improved; in particular, it seems worthwhile to study the following problem.

Problem 4

Does every model of $B\Sigma _1{+}exp$ have a proper end extension satisfying $I\Delta _0$?

Among attempts made towards solving Problem 4, the one deserving special mention is due to Z. Adamowicz, who extended in [1] Theorem 12 above, by proving that every model of $B\Sigma _1+exp$ that is cofinal with $\omega$ has a proper end extension satisfying $I\Delta _0$.

In connection with Problem 4, one can ask the following, apparently more difficult, question.

Problem 5

Does every countable model of $B\Sigma _1+\Omega _1$ have a proper end extension satisfying $I\Delta _0$?

Here, as usual, $\Omega _1$ denotes the axiom expressing that the function $x^{|x|}$ is total, where |x| denotes the length of the logarithmic expansion of x – recall that the strength of $\Omega _1$ was studied extensively in [17].

Let us end this section by noting that a very interesting study of Problem 5 was carried out by Z. Adamowic in [2]. One of the main results of this specific paper states that, under an assumption weaker than $I\Delta _0\vdash \lnot \Delta _0 H$, there exists a model of $B\Sigma _1+\Omega _1$ which does not have a proper end extension satisfying $I\Delta _0$.