1 Limit-determination and modulus

An $(n+1)$ -place number-theoretic function f limit-determines an n-place relation R iff for all $i_1, \ldots ,i_n$ ,

$$ \begin{align*} R(i_1, \ldots, i_n)\text{ iff }\lim_{y \rightarrow \infty} f(i_1,\ldots,i_n,y) &= 1\\ \lnot R(_1, \ldots, i_n)\text{ iff }\lim_{y \rightarrow \infty} f(i_1,\ldots,i_n,y) &= 0.\end{align*} $$

The Limit Lemma, a standard result of recursion theory originally due to Shoenfield [Reference Shoenfield11], states that a relation is $\Delta _2^0$ iff there is a recursive function that limit-determines it (see Odifreddi [Reference Odifreddi8, p. 373]).

A function f is k-trial iff, for all $i_1, \ldots ,i_n$ , $f(i_1, \ldots ,i_n,y)$ changes value at most k times as y increases. Putnam introduced this notion in [Reference Putnam10], and showed that a relation is $\Sigma _1^*$ iff for some k there is a recursive k-trial function that limit-determines it. This result is used below in the “if” direction. The proof is straightforward, and perhaps best presented by an example. Suppose $g(i,j,y)$ is a 2-trial function that limit-determines a relation $R(i,j)$ . Then $R(i,j)$ can be specified thus: there are two numbers y at which $g(i,j,y)$ changes value, and at the greater of them the value is 1; or there aren’t two numbers y such that $g(i,j,y)$ changes value at y but there is one number y at which $g(i,j,y)$ changes value, and then its value is 1, or there is no number y at which $g(i,j,y)$ changes value, and $g(i,j,0)$ is 1. Each of these clauses expresses either an r.e. relation or a co-r.e. relation.

Let f be a recursive function that limit-determines a relation. For any i, an i-modulus for f is a number b such that

$$ \begin{align*}f(i_1, \ldots, i_n,b) = f(i_1, \ldots, i_n,y)\end{align*} $$

whenever $i_1, \ldots , i_n \leq i$ and $b \leq y$ . For every i there are cofinitely many integers b that are i-moduli. The notion of an i-modulus is not, in general, recursive. The following is a recursive notion that approximates it and yields an i-modulus in the limit. An r-seeming i-modulus for f is a number $b \leq r$ such that

$$ \begin{align*}f(i_1, \ldots, i_n,b) = f(i_1, \ldots, i_n,y)\end{align*} $$

whenever $i_1, \ldots , i_n \leq i$ and $b \leq y \leq r$ . Note that if b is an i-modulus for f, then b is also an r-seeming i-modulus for f for every $r \geq b$ ; and if b is not an i-modulus for f, then b fails to be an r-seeming i-modulus for f for cofinitely many r.

2 Proof for sentences without identity

Let F be a satisfiable sentence of first-order predicate logic without identity. As noted above, there exists a model $\mathfrak {M}$ for it with universe $\mathbb {N}$ in which the predicates are interpreted as $\Delta _2^0$ relations. By the Limit Lemma, for each predicate P of F there exists a recursive function $f_P$ that limit-determines $P^{\mathfrak {M}}$ . We call an integer b an i-modulus (simpliciter) iff it is an i-modulus for every function $f_P$ , and an r-seeming i-modulus (simpliciter) iff it is an r-seeming i-modulus for every function $f_P$ .

Let $\langle. , .\rangle $ be a standard primitive recursive bijective pairing function. Define $\varphi : \mathbb {N} \rightarrow \mathbb {N}$ by

$$\begin{align*}\varphi(p) = \left\{\begin{array}{@{}ll} i & \mbox{if }p = \langle i,b \rangle\text{ and }b\text{ is an }i\text{-modulus} \\ 0 & \text{otherwise.} \end{array} \right. \end{align*}$$

Clearly $\varphi $ is onto. Now let $\mathfrak {N}$ be the structure with universe $\mathbb {N}$ such that, for each n-adic predicate P of F and all $p_1, \ldots ,p_n$ ,

$$ \begin{align*}\mathfrak{N} \models Pp_1 \ldots p_n \,\, \mathrm{{iff}} \,\, \mathfrak{M} \models P\varphi(p_1) \ldots \varphi(p_n).\end{align*} $$

Since F does not contain identity and $\varphi $ is onto, it follows that $\mathfrak {N} \models F$ . (This is a general model-theoretic fact: if a structure $\mathfrak {N}$ is the preimage of a relational structure $\mathfrak {M}$ under a function from the universe of $\mathfrak {N}$ onto the universe of $\mathfrak {M}$ , then $\mathfrak {M}$ and $\mathfrak {N}$ model the same sentences of predicate logic without identity.)

We now show that the relations of the structure $\mathfrak {N}$ are $\Sigma _{1}^*$ by constructing k-trial recursive functions that limit-determine them. For each r define $\varphi _r$ by

$$\begin{align*}\varphi_r(p) = \left\{\begin{array}{@{}ll} i & \text{if }p = \langle i,b \rangle\text{ and }b\text{ is an }r\text{-seeming }i\text{-modulus, or if }r<b \\ 0 & \text{otherwise.} \end{array} \right. \end{align*}$$

Let $p = \langle i,b \rangle $ . If b is an i-modulus, then $\varphi _r(p) = i$ for all r. If b is not an i-modulus, then $\varphi _r(p) = i$ for r up to some point, but = 0 for all greater r. Thus for any fixed p, the value of $\varphi _r(p)$ can change at most once as r increases, and the eventual value of $\varphi _r(p)$ is $\varphi (p)$ for all sufficiently large r.

Let P be any predicate of F, say P is n-place, let $p_1, \ldots , p_n$ be any numbers, with $p_k = \langle i_k,b_k \rangle $ for $1 \leq k \leq n$ , and let $b_0$ be a 0-modulus. We define

$$ \begin{align*}g_P(p_1, \ldots p_n,r) = f_P(\varphi_r(p_1), \ldots, \varphi_r(p_n),b),\end{align*} $$

where b is the maximum of $b_0, b_1, \ldots , b_n$ .

It is easy to see that, for each n-ary predicate P and all $p_1, \ldots ,p_n$ ,

$$ \begin{align*}\lim_{y \rightarrow \infty} g_P(p_1, \dots p_n,y) = \lim_{y \rightarrow \infty} f_P(\varphi(p_1),\ldots,\varphi(p_n), y)\end{align*} $$

since there will be a q such that $g_P(p_1, \dots , p_n,r) = f_P(\varphi (p_1), \ldots , \varphi (p_n),b)$ for all $r \geq q$ , and b is an i-modulus for i such that $\varphi (p_1), \ldots , \varphi (p_n) \leq i$ . Hence each function $g_P$ limit-determines $P^{\mathfrak {N}}$ .

If P is n-adic, $g_P$ is an n-trial function. For as noted above as r increases, a value $\varphi _r(p)$ can change only once, from a nonzero value to 0. This implies that as r increases $g_P(p_1, \dots p_n,r)$ can change value at most n times.

This proof generalizes without difficulty to recursive sets of sentences without identity, provided that there are finitely many predicates in the sentences, since the basic Hilbert–Bernays $\Delta _2^0$ result so generalizes.

3 Proof with identity: Specification of the model

The mapping $\varphi $ in the proof just given is not injective, and hence the preimage does not preserve identity. This makes the proof inapplicable to sentences containing “=”. To obtain a suitable mapping that is injective as well, Hensel and Putnam’s strategy is to start with a $\Delta _2^0$ model that contains infinitely many indiscernibles. These indiscernibles provide distinct objects to be the images of distinct arguments. In order to be injective the mapping $\varphi $ can take $\langle i,b \rangle $ to i for at most one b. To insure this, a minimality condition needs to be put on b. This requires much more fine-grained information about the approximation procedure than was needed in Section 2.

Let T be a recursive set of sentences of first-order predicate logic with identity containing a finite number of predicates. Let $T^S$ be the Skolemization of T. Let Eq be the (purely universal) axioms of identity (that is, reflexivity and substitutivity) for the language of $T^S$ . Let $a_0, \ldots , a_k, \ldots $ be distinct constants foreign to $T^S$ , and let In be the set of axioms asserting that these a-constants are order-indiscernible, with respect to the atomic formulas of $T^S$ , i.e., axioms

$$ \begin{align*}F(a_{i_1}, \ldots, a_{i_n}) \leftrightarrow F(a_{j_1}, \ldots, a_{j_n})\end{align*} $$

whenever $F(x_1,\ldots ,x_n)$ is an atomic formula of $\mathcal {L}(T^S)$ , $i_1 < \cdots < i_n$ and $j_1 < \cdots < j_n$ .

Finally, let $T^+$ be the theory $T^S \cup {\textsf {Eq}} \cup {\textsf {In}} \cup \lbrace a_1 \neq a_2 \rbrace $ . An argument using Ramsey’s Theorem shows that if T has an infinite model then $T^+$ has a model (see Chang and Keisler [Reference Chang and Jerome Keisler1, pp. 147–148]). Note that $T^+$ implies $a_i \neq a_j$ whenever $i \neq j$ .

Let D be the set of terms that can be built from the function signs and constants appearing in formulas in $T^+$ . We assume a standard gödelization of D, and let $\tau (1), \tau (3), \ldots , \tau (2i+1), \ldots $ be a listing in order of increasing gödel numbers of the members of D that are not a-constants, while  $\tau (2i) = a_i$ for each i. Thus $\tau $ is a bijection between $\mathbb {N}$ and D. We assume that if $\tau (i)$ is a proper subterm of $\tau (j)$ then $i<j$ .

Since $T^+$ has a model, every conjunction of substitution instances of members of $T^+$ over D is consistent. Compactness then yields the consistency of the set of all such instances, and by König’s Lemma (as in Gödel’s completeness proof) this immediately yields a quasi-model $\mathfrak {M_0}$ of $T^+$ with universe D. “Quasi-model” here means a structure in which all the axioms of $T^+$ hold, but the interpretation of the identity sign “=” may not be true identity. Due to the inclusion of the axioms Eq, however, “=” will be interpreted in $\mathfrak {M_0}$ as a congruence relation relative to the other predicates and the function signs of $T^+$ .

Let $\mathfrak {M}$ be the isomorphic copy with universe $\mathbb {N}$ of $\mathfrak {M_0}$ , via the bijection $\tau $ . The interpretations in $\mathfrak {M}$ of the predicates of $T^+$ can be taken to be $\Delta _2^0$ . Hence for each predicate P of $T^+$ there is a recursive function $f_P$ that limit-determines $P^{\mathfrak {M}}$ . As before, we say an integer b is an i-modulus iff it is an i-modulus for each function $f_P$ , and similarly for “r-seeming i-modulus”.

By the definition of $\tau $ , the even numbers are the indiscernibles of $\mathfrak {M}$ . Indeed, the reason we started with the Skolemization of T and built up the quasi-model $\mathfrak {M_0}$ over universe D was to insure not only that the predicates were $\Delta _2^0$ but also that the indiscernibles comprised a recursive set.

Let $(i_1,\ldots ,i_n)$ be an n-tuple of integers, and let i be the largest odd integer among the $i_k$ , if there is one, and let $i= 0$ if all the $i_k$ are even. An n-tuple $(j_1,\ldots ,j_n)$ is similar to $(i_1,\ldots ,i_n)$ iff:

1) for each k if $i_k \leq i$ then $j_k = i_k$ ;

2) the tuples obtained from the two n-tuples by eliminating all entries $\leq i$ are order-isomorphic.

Note that if $i_k$ is an even integer $>i$ , then the a-constant $\tau (i_k)$ does not occur in any term $\tau (i_j)$ for $i_j \leq i$ . Consequently, the axioms In imply the following: if P is an n-place predicate and $( i_1,\ldots ,i_n)$ and $(j_1,\ldots ,j_n)$ are similar, then

$$ \begin{align*}\mathfrak{M} \models Pi_1\ldots i_n \leftrightarrow Pj_1 \ldots j_n.\end{align*} $$

We now introduce a different pairing function. Let $\pi (i,b) = i + \frac {1}{2}b (b+1)$ . $\pi $ is a bijection between $\mathbb {N}$ and pairs $(i,b)$ such that $i \leq b$ . $\pi $ is monotonic in each argument. Moreover, if $\pi (j,c) < \pi (i,b)$ , where $j \leq c$ and $i \leq b$ , then $c \leq b$ . This “ordering property” will be crucial for the proof of Lemma 3(iii) in Section 4.

A pair $(i,b)$ is ideal iff i is odd and b is the smallest number $\geq i$ such that:

(i) b is an $(i + 2n_0)$ -modulus, where $n_0$ is the largest adicity of any predicate letter of T;

(ii) for all $j < i, f_=(j,i,b) = 0$ .

Note that if $(i,b)$ is ideal, then i will be the smallest member of its $=^{\mathfrak {M}}$ -equivalence class.

Now define $\varphi : \mathbb {N} \rightarrow \mathbb {N}$ by $\varphi (p) = i$ if $p = \pi (i,b)$ for an ideal pair $(i,b)$ ; and otherwise $\varphi (p)$ is the least even number not among $\varphi (0), \ldots , \varphi (p-1)$ . Since for every i there is at most one b such that $(i,b)$ is ideal, it follows that $\varphi $ is injective and its range includes all even numbers.

Now let $\mathfrak {N}$ be the structure with universe $\mathbb {N}$ such that, for each n-place predicate P of $\mathcal {L}(T)$ and all $p_1, \ldots ,p_n$ ,

$$ \begin{align*}\mathfrak{N} \models Pp_1 \ldots p_n \leftrightarrow \mathfrak{M} \models P\varphi(p_1) \ldots \varphi(p_n).\end{align*} $$

Thus $\varphi $ is an isomorphism between $\mathfrak {N}$ and the substructure of $\mathfrak {M}$ whose universe is the range of $\varphi $ . From Lemma 1 it follows that $=^{\mathfrak {N}}$ is the identity relation, and that $\mathfrak {N}$ is a model of T.

4 The predicates of $\mathfrak {N}$ are $\Sigma _{1}^*$

As in Section 2, we define recursive functions that approximate those used in the specification of $\mathfrak {N}$ . A pair $(i,b)$ is r-ideal iff i is odd and b is the smallest number $\geq i$ such that:

(i) b is an r-seeming $(i + 2n_0)$ -modulus;

(ii) for all $j < i, f_=(j,i,b) = 0$ .

For each r, if $p = \pi (i,b)$ for an r-ideal pair $(i,b)$ , let $\varphi _r(p) = i$ ; otherwise let $\varphi _r(p)$ be the earliest even number not among $\varphi _r(0), \ldots , \varphi _r(p-1)$ . Note that $\varphi _r(p)$ is recursive in both arguments.

Because r-seeming moduli are either moduli for cofinitely many r or non-moduli for cofinitely many r, for every m there is a number $\rho (m)$ with the following property: for every $r \geq \rho (m)$ and all pairs $(i,b)$ with $i \leq b$ such that $\pi (i,b) \leq m$ , b is an r-seeming $(i+2n_0)$ -modulus iff b is an $(i+2n_0)$ -modulus. Hence for every $r \geq \rho (m)$ and every $p \leq m$ , $\varphi _r(p) = \varphi (p)$ .

For any n-tuple $(i_1, \ldots , i_n)$ let $[\![ i_1, \ldots , i_n ]\!] $ be the earliest n-tuple similar to $(i_1, \ldots , i_n)$ . Let P be any predicate of T, say P is n-adic, let $p_1, \ldots , p_n$ be any numbers, with $p_k = \pi (i_k,b_k)$ with $i_k \leq b_k$ for $1 \leq k \leq n$ , and let $b_0$ be a $2n_0$ -modulus. We define

$$ \begin{align*}g_P(p_1, \ldots, p_n,r) = f_P([\![ \varphi_r(p_1), \ldots, \varphi_r(p_n)]\!],b),\end{align*} $$

where b is the maximum of $b_0, b_1, \ldots b_n$ . Note that each $g_P$ is recursive.

Proof It is enough to show, for each predicate P and all $p_1,\ldots ,p_n$ , that

$$ \begin{align*}\lim_{y \rightarrow \infty} g_P(p_1, \dots, p_n,y) = \lim_{y \rightarrow \infty} f_P([\![ \varphi(p_1),\ldots,\varphi(p_n) ]\!], y).\end{align*} $$

Let m be the largest of $p_1, \ldots , p_n$ . Then for any $r \geq \rho (m)$ , $g_P(p_1, \ldots , p_n,r) = f_P([\![ \varphi (p_1), \ldots , \varphi (p_n) ]\!] ,b),$ where b is chosen as above. Hence

$$ \begin{align*}\lim_{y \rightarrow \infty} g_P(p_1, \dots, p_n,y) = f_P([\![ \varphi(p_1), \ldots, \varphi(p_n) ]\!],b)\end{align*} $$

for this b.

What remains to be established is that

$$ \begin{align*}f_P([\![ \varphi(p_1), \ldots, \varphi(p_n) ]\!],b) = \lim_{y \rightarrow \infty} f_P([\![ \varphi(p_1),\ldots,\varphi(p_n) ]\!], y).\end{align*} $$

Let q be the largest integer in the n-tuple $[\![ \varphi (p_1),\ldots ,\varphi (p_n) ]\!] $ ; it suffices to show that b is a q-modulus. If all the $\varphi (p_j)$ are even, then $[\![ \varphi (p_1), \ldots , \varphi (p_n) ]\!] $ will contain only even numbers $\leq 2n_0$ . Since b is a $2n_0$ -modulus, it is indeed a q-modulus. Otherwise, let $\varphi (p_j)$ be the largest odd number among $\varphi (p_1), \ldots , \varphi (p_n)$ . Then $[\![ \varphi (p_1), \ldots , \varphi (p_n) ]\!] $ will contain only numbers $\leq \varphi (p_j) + 2n_0$ , that is, $q \leq \varphi (p_j) + 2n_0$ . But $(\varphi (p_j),b')$ is ideal for some $b' \leq b$ , so that b is a $(\varphi (p_j) + 2n_0)$ -modulus.

Proof The supposition on b implies that for some predicate P and some $i_1, \ldots , i_n \leq i$ ,

$$ \begin{align*}f_P(i_1, \ldots ,i_n,r) \neq f_P(i_1, \ldots ,i_n,r+1).\end{align*} $$

The existence of such $i_1, \ldots , i_n$ implies that c is not an $(r+1)$ -seeming j-modulus, so long as $c \leq r$ and $j \geq i$ .

Lemmas 2 and 5 show that each $P^{\mathfrak {N}}$ is $\Sigma _{1}^*$ , and so conclude the proof.

The proof shows that, for each predicate P, the complexity of $P^{\mathfrak {N}}$ depends only on the adicity P, and not on any quantificational structure of T, where by complexity we mean the number of r.e. and co-r.e. sets whose Boolean combination defines $P^{\mathfrak {N}}$ . No upper bound is put on this complexity. However, there are many different techniques for encoding polyadic predicates of high adicity by dyadic or triadic predicates. Most of these involve additional quantifiers, so their applicability in this context would have to be very delicate. But the question remains: is there an upper bound on the Boolean complexity needed even for predicates of arbitrarily large adicity.Footnote ²