Proof. Let $\mathsf {T}_1$ and $\mathsf {T}_2$ be first-order theories and assume that $\mathsf {AutSpec}(\mathsf {T}_1)=\mathsf {AutSpec}(\mathsf {T}_2)$ . We are going to define a concrete isomorphism b between their model-iso-categories.

The identity element of a permutation group is always of the form $\{(a,a) : a\in A\}$ for some A; let us call this A the base of the permutation group. Let ${\mathfrak {G}},{\mathfrak {H}}$ be permutation groups, let $h:A\to B$ be a bijection between the bases of ${\mathfrak {G}}$ and ${\mathfrak {H}}$ , and define $\overline {h}(g) = h\circ g\circ h^{-1}$ for all $g\in G$ . Then it is easy to see that $\overline {h}$ is an isomorphism between ${\mathfrak {G}}$ and ${\mathfrak {H}}$ ; we say that it is the base-isomorphism induced by h. A base-isomorphism between two permutation groups ${\mathfrak {G}},{\mathfrak {H}}$ is an isomorphism between them that is induced by some h. We will also use the fact that if $h:{\mathfrak M}\to {\mathfrak {N}}$ is an isomorphism between the structures ${\mathfrak M},{\mathfrak {N}}$ , then $\overline {h}$ is a base-isomorphism between their automorphism groups.

Let $\mathcal G$ be a class of representatives for the base-isomorphism classes of permutation groups. That is, each permutation group has a base-isomorphic copy in $\mathcal G$ and the elements of $\mathcal G$ are pairwise non-base-isomorphic. For any permutation group ${\mathfrak {G}}\in \mathcal G$ choose $\nu ({\mathfrak {G}},\mathsf {T}_1)$ -many non-isomorphic models ${\mathfrak M}({\mathfrak {G}},i)$ of $\mathsf {T}_1$ , for $i<\nu ({\mathfrak {G}},\mathsf {T}_1)$ , and similarly choose $\nu ({\mathfrak {G}},\mathsf {T}_2)=\nu ({\mathfrak {G}},\mathsf {T}_1)$ non-isomorphic models ${\mathfrak M}'({\mathfrak {G}},i)$ of $\mathsf {T}_2$ , with concrete automorphism group ${\mathfrak {G}}$ . Then the models ${\mathfrak M}({\mathfrak {G}},i)$ for ${\mathfrak {G}}\in \mathcal G$ are pairwise non-isomorphic, i.e., ${\mathfrak M}({\mathfrak {G}},i)\cong {\mathfrak M}({\mathfrak {H}},j)$ for some ${\mathfrak {G}},{\mathfrak {H}},i,j$ implies ${\mathfrak {G}}={\mathfrak {H}}$ and $i=j$ . Similarly, the models ${\mathfrak {M}}'({\mathfrak {G}},i)$ are pairwise non-isomorphic.

Let ${\mathfrak {M}}\in \mathsf {Mod}(\mathsf {T}_1)$ . There is a unique ${\mathfrak {M}}({\mathfrak {G}},i)$ isomorphic to ${\mathfrak M}$ , as follows. Let ${\mathfrak {H}}$ be the concrete automorphism group of ${\mathfrak M}$ and let ${\mathfrak {G}}\in \mathcal G$ be base-isomorphic to ${\mathfrak {H}}$ via the base-isomorphism $\overline {h}:{\mathfrak {H}}\to {\mathfrak {G}}$ . Then the automorphism group of $h({\mathfrak {M}})$ is ${\mathfrak {G}}\in \mathcal G$ ; thus, $h({\mathfrak {M}})$ is isomorphic to ${\mathfrak {M}}({\mathfrak {G}},i)$ for some i, by our construction. Choose any isomorphism f mapping ${\mathfrak {M}}({\mathfrak {G}},i)$ to ${\mathfrak M}$ and let us define

$$\begin{align*}b({\mathfrak{M}}) {\ :=\ } f({\mathfrak{M}}'({\mathfrak{G}},i)) .\end{align*}$$

We show that $b({\mathfrak {M}})$ is well-defined, i.e., it does not depend on which isomorphism f we choose. Let g be any other isomorphism between ${\mathfrak {M}}({\mathfrak {G}},i)$ and ${\mathfrak M}$ ; we show that $f({\mathfrak {M}}'({\mathfrak {G}},i))=g({\mathfrak {M}}'({\mathfrak {G}},i))$ . Indeed, $g=f\circ \alpha $ for $\alpha =f^{-1}\circ g\in \mathsf {Aut}({\mathfrak {M}}({\mathfrak {G}},i))={\mathfrak {G}}$ . But $\alpha \in {\mathfrak {G}}=\mathsf {Aut}({\mathfrak {M}}'({\mathfrak {G}},i))$ , so $g({\mathfrak {M}}'({\mathfrak {G}},i))=f(\alpha ({\mathfrak {M}}'({\mathfrak {G}},i)))=f({\mathfrak {M}}'({\mathfrak {G}},i))$ .

We define b on the morphisms. Let $h:{\mathfrak {M}}\to {\mathfrak {N}}$ be an isomorphism between ${\mathfrak {M}},{\mathfrak {N}}\in \mathsf {Mod}(\mathsf {T}_1)$ . We have seen that $f:{\mathfrak {M}}({\mathfrak {G}},i)\to {\mathfrak {M}}$ for some $f,{\mathfrak {G}},i$ and so $g:{\mathfrak {M}}({\mathfrak {G}},i)\to {\mathfrak {N}}$ for $g=h\circ f$ . Thus, by definition, $b({\mathfrak {M}})=f({\mathfrak {M}}'({\mathfrak {G}},i))$ and $b({\mathfrak {N}})=g({\mathfrak {M}}'({\mathfrak {G}},i))$ . Hence, $h:b({\mathfrak {M}})\to b({\mathfrak {N}})$ is an isomorphism by $g\circ f^{-1}=h\circ f\circ f^{-1}$ . We define

$$\begin{align*}b(h) {\ :=\ } h .\end{align*}$$

We now show that b is an isomorphism between the model-iso-categories of $\mathsf {T}_1$ and $\mathsf {T}_2$ . First we show that the function $b:\mathsf {Mod}(\mathsf {T}_1)\to \mathsf {Mod}(\mathsf {T}_2)$ defined this way is a bijection between $\mathsf {Mod}(\mathsf {T}_1)$ and $\mathsf {Mod}(\mathsf { T}_2)$ . Indeed, let ${\mathfrak {M}}'\in \mathsf {Mod}(\mathsf {T}_2)$ be any model. There is a unique ${\mathfrak {M}}'({\mathfrak {G}},i)$ isomorphic to it, say via $f:{\mathfrak {M}}'({\mathfrak {G}},i)\to {\mathfrak {M}}'$ . Let ${\mathfrak {M}}=f({\mathfrak {M}}({\mathfrak {G}},i))$ , then ${\mathfrak {M}}'=b({\mathfrak {M}})$ , by the definition of b. Thus, the range of b is $\mathsf {Mod}(\mathsf {T}_2)$ . To see that b is one-to-one, let ${\mathfrak {M}},{\mathfrak {N}}\in \mathsf {Mod}(\mathsf {T}_1)$ . Assume that $b({\mathfrak {M}})=b({\mathfrak {N}})$ . By the definition of b, there are ${\mathfrak {M}}({\mathfrak {G}},i), {\mathfrak {M}}({\mathfrak {H}},j)$ and isomorphisms $f:{\mathfrak {M}}({\mathfrak {G}},i)\to {\mathfrak {M}}$ , $g:{\mathfrak {M}}({\mathfrak {H}},j)\to {\mathfrak {N}}$ such that $b({\mathfrak {M}})=f({\mathfrak {M}}'({\mathfrak {G}},i))$ and $b({\mathfrak {N}})=g({\mathfrak {M}}'({\mathfrak {H}},j))$ . By $b({\mathfrak {M}})=b({\mathfrak {N}})$ then ${\mathfrak {M}}'({\mathfrak {G}},i)$ is isomorphic to ${\mathfrak {M}}'({\mathfrak {H}},j)$ ; therefore, $({\mathfrak {G}},i)=({\mathfrak {H}},j)$ and $f({\mathfrak {M}}'({\mathfrak {G}},i))=g({\mathfrak {M}}'({\mathfrak {G}},i))$ . Thus, $f^{-1}\circ g\in \mathsf { Aut}({\mathfrak {M}}'({\mathfrak {G}},i))={\mathfrak {G}}$ . So, ${\mathfrak {M}}=f({\mathfrak {M}}({\mathfrak {G}},i))=f((f^{-1}\circ g)({\mathfrak {M}}({\mathfrak {G}},i)))=g({\mathfrak {M}}({\mathfrak {G}},i))=g({\mathfrak {M}}({\mathfrak {H}},j))={\mathfrak {N}}$ .

We turn to the proof for b being a bijection between the set of isomorphisms from ${\mathfrak M}$ to ${\mathfrak {N}}$ and the set of isomorphisms from $b({\mathfrak {M}})$ to $b({\mathfrak {N}})$ , for any ${\mathfrak {M}},{\mathfrak {N}}\in \mathsf {Mod}(\mathsf {T}_1)$ . To show surjectivity, let $h:b({\mathfrak {M}})\to b({\mathfrak {N}})$ . By the definition of $b({\mathfrak {M}})$ , we have that ${\mathfrak {M}}=f({\mathfrak {M}}({\mathfrak {G}},i))$ and $b({\mathfrak {M}})=f({\mathfrak {M}}'({\mathfrak {G}},i))$ , for some $f,{\mathfrak {G}},i$ . Thus, $f:{\mathfrak {M}}'({\mathfrak {G}},i)\to b({\mathfrak {M}})$ , and so $h\circ f:{\mathfrak {M}}'({\mathfrak {G}},i)\to b({\mathfrak {N}})$ , by $h:b({\mathfrak {M}})\to b({\mathfrak {N}})$ . Let ${\mathfrak {N}}'=f(h({\mathfrak {M}}({\mathfrak {G}},i))$ . By the definition of $b({\mathfrak {N}}')$ then $b({\mathfrak {N}}')=(h\circ f)({\mathfrak {M}}'({\mathfrak {G}},i))=b({\mathfrak {N}})$ . Thus, ${\mathfrak {N}}'={\mathfrak {N}}$ because b is one-to-one on $\mathsf {Mod}(\mathsf {T}_1)$ , i.e., ${\mathfrak {N}}=(h\circ f)({\mathfrak {M}}({\mathfrak {G}},i))=h(f({\mathfrak {M}}({\mathfrak {G}},i)))=h({\mathfrak {M}})$ . Thus, $h:{\mathfrak {M}}\to {\mathfrak {N}}$ is an isomorphism and $b(h)=h$ . By definition, it is clear that b is one-to-one on the morphisms, and also that it preserves composition of morphisms in both directions. This finishes the proof for b being a category theoretical isomorphism between the model-iso-categories of $\mathsf {T}_1$ and $\mathsf {T}_2$ . It is concrete, by its definition.

In the other direction, assume that b is a concrete isomorphism between ${\mathcal Mod}^{iso}(\mathsf {T}_1)$ and ${\mathcal Mod}^{iso}(\mathsf {T}_2)$ . Then $\mathsf {Aut}({\mathfrak {M}})=\mathsf {Aut}(b({\mathfrak {M}}))$ , and ${\mathfrak {M}}\cong {\mathfrak {N}}$ iff $b({\mathfrak {M}})\cong b({\mathfrak {N}})$ , for all ${\mathfrak {M}},{\mathfrak {N}}\in \mathsf { Mod}(\mathsf {T}_1)$ . Therefore, $\mathsf {AutSpec}(\mathsf {T}_1)=\mathsf {AutSpec}(\mathsf {T}_2)$ .

Proof. Let $\mathbb N$ denote the set of natural numbers with $0$ as constant $\mathsf {0}$ and the successor function as unary distinguished function $\mathsf {suc}$ , and let $\mathbb Z$ denote the set of integers with the successor function as unary distinguished function $\mathsf {suc}$ . Note that $\mathbb Z$ does not have $\mathsf {0}$ in its language. Any model of $\mathsf {Th}(\langle \omega ,\mathsf {0},\mathsf { suc}\rangle )$ is a disjoint union of one copy of $\mathbb N$ together with some copies of $\mathbb Z$ . When k is negative, $\mathsf {suc}^{k}(x)=y$ means $\mathsf {suc}^{-k}(y)=x$ , and we say that $\mathsf {suc}^{k}(x)$ exists when such a y exists. In models of $\mathsf {Th}(\langle \omega ,\mathsf { 0},\mathsf {suc}\rangle )$ such a y is unique when it exists. When ${\mathfrak {N}}$ is a model of $\mathsf {Th}(\langle \omega ,\mathsf {0},\mathsf {suc}\rangle )$ , by a $\mathbb Z$ -part of ${\mathfrak {N}}$ we mean a subset of N of the form $\{\mathsf {suc}^n(a) : n\in \omega \}\cup \{\mathsf {suc}^{-n}(a) : n\in \omega \}$ for some $a\in N$ . By a $\mathbb Z$ -model we mean $\mathbb Z$ together with a unary relation R and by $\langle \mathbb N,S\rangle $ we mean $\mathbb N$ expanded with S as the unary relation $\mathsf {R}$ . We are going to prove the following statement (*).

In (*) as well as later on, we will use ultraproducts [Reference Chang and Keisler11, chap. 4]. As in [Reference Chang and Keisler11], when U is an ultrafilter on the set I and $\langle {\mathfrak {M}}_i : i\in I\rangle $ is an I-sequence of similar models, $\prod _{U}\langle {\mathfrak {M}}_i : i\in I\rangle $ , or sloppily just $\prod _{U}{\mathfrak {M}}_i$ , denotes the U-ultraproduct of the models ${\mathfrak {M}}_i$ and $y_U$ denotes the equivalence-class of y in $\Pi _U{\mathfrak {M}}_i$ , for $y\in \Pi _{i\in I}M_i$ . When each ${\mathfrak {M}}_i={\mathfrak {A}}$ for some ${\mathfrak {A}}$ , we call $\prod _{U}{\mathfrak {M}}_i$ an ultrapower of ${\mathfrak {A}}$ and we denote it by $\Pi _U{\mathfrak {A}}$ .

1. (*) Assume that ${\mathfrak M}$ is a countable model of $\mathsf {T}(S)$ and U is a nonprincipal ultrafilter on a countable set I. Then $\Pi _U{\mathfrak {M}}$ is isomorphic to a disjoint union of a copy of $\langle \mathbb N,S\rangle $ with continuum many copies of each possible $\mathbb Z$ -model.

Indeed, (*) is true because each $\mathbb Z$ -model can be put together in the ultrapower from its finite parts which are patterns occurring in ${\mathfrak M}$ , and in fact, each such pattern occurs infinitely many times in ${\mathfrak M}$ . In more detail: Let $\langle \mathbb Z,R\rangle $ be any $\mathbb Z$ -model; we show that continuum many disjoint copies of it occurs in the ultrapower of ${\mathfrak M}$ . We may assume that $I=\omega $ because I is countable. For each $n>0$ let $R_n{\ :=\ }\{m\le 2n : m-n\in R\}$ . The pattern $R_n,2n+1$ occurs in S because S is irregular. In fact, each pattern occurs in an irregular set infinitely many times because each finite pattern has infinitely many different extensions to other finite patterns and each of these patterns occurs in the irregular set. Let $X_n$ be the set of xs where $R_n,2n+1$ occurs in S and let $Y_n{\ :=\ }\{x+n : x\in X_n\}$ . First we show that in $\Pi _U{\mathfrak {M}}$ each element of $\Pi _U Y_n$ lies on a copy of $\langle \mathbb Z,R\rangle $ . Indeed, let $x_n\in X_n$ and $y_n{\ :=\ } x_n+n$ for all $n\in \omega $ . Let $y{\ :=\ }\langle y_n : n\in \omega \rangle $ , and let $k\in \mathbb Z$ be arbitrary. We will show that $\mathsf {suc}^k(y_U)$ exists and $k\in R$ iff $R(\mathsf {suc}^k(y_U))$ in $\Pi _U{\mathfrak {M}}$ . By our definitions, for all n such that $2n\ge k$ we have that $k\in R$ iff $k+n\in R_n$ iff $x_n+k+n\in S$ iff $y_n+k\in S$ iff $R(\mathsf {suc}^k(y_n))$ in ${\mathfrak M}$ . Since U is nonprincipal on $I=\omega $ , this means that $R(\mathsf {suc}^k(y_U))$ in $\Pi _U{\mathfrak {M}}$ . We have seen that $y_U$ is in a copy of $\langle \mathbb Z,R\rangle $ for all $y\in \Pi _{n\in \omega } Y_n$ . Since each $Y_n$ is countably infinite, the cardinality of $\Pi _U Y_n$ is continuum (see [Reference Chang and Keisler11, proposition 4.3.9]). Since each copy of $\langle \mathbb Z,R\rangle $ is countable, this means that $\Pi _U{\mathfrak {M}}$ contains continuum many disjoint copies of $\langle \mathbb Z,R\rangle $ , and we are done with proving (*).

Proof of (i): An elementary submodel of ${\mathfrak M}$ has to be an induced subalgebra. Conversely, assume that ${\mathfrak {N}}$ is an induced subalgebra of ${\mathfrak M}$ ; we show that it is an elementary submodel. We will use the testing method in [Reference Chang and Keisler11, proposition 3.1.2]. Thus, assume that $\varphi (\bar {x},y)$ is a first-order logic formula in the language of ${\mathfrak M}$ , assume that $\bar {a}$ is an appropriate sequence of elements of ${\mathfrak {N}}$ , and ${\mathfrak {M}}\models \exists y\varphi (\bar {a},y)$ . We have to show the existence of $a'\in {\mathfrak {N}}$ such that ${\mathfrak {M}}\models \varphi (\bar {a},a')$ . We have $\Pi _U{\mathfrak {M}}\models \exists y\varphi (d(\bar {a}),y)$ since the diagonal (or natural) embedding d of a model into its ultrapower is an elementary one [Reference Chang and Keisler11, corollary 4.1.13]. Let $b\in \Pi _U{\mathfrak {M}}$ be such that $\Pi _U{\mathfrak {M}}\models \varphi (d(\bar {a}),b)$ . Now, $\Pi _U{\mathfrak {N}}$ is an induced subalgebra of $\Pi _U{\mathfrak {M}}$ , by ${\mathfrak {N}}$ being an induced subalgebra of ${\mathfrak M}$ . There are infinitely many $\mathbb Z$ -parts in $\Pi _U{\mathfrak {N}}$ that do not contain any element of $d(\bar {a})$ and that are isomorphic to the $\mathbb Z$ -part of $\Pi _U{\mathfrak {M}}$ containing b, by (*). Take an automorphism of $\Pi _U{\mathfrak {M}}$ that interchanges the $\mathbb Z$ -part of b with any of such a $\mathbb Z$ -part of $\Pi _U{\mathfrak {N}}$ and leaves anything else fixed. There is such an automorphism by the choice of the $\mathbb Z$ -part of $\Pi _U{\mathfrak {N}}$ and since ${\mathfrak {M}}\in \mathsf {Mod}\mathsf {T}(S)$ . Let c be the image of b under such an automorphism, then $\Pi _U{\mathfrak {M}}\models \varphi (d(\bar {a}),c)$ , since the automorphism leaves the elements of $d(\bar {a})$ fixed. Then ${\mathfrak {M}}\models \varphi (\bar {a},a')$ for some $a'\in {\mathfrak {N}}$ by the fundamental theorem of ultraproducts [Reference Chang and Keisler11, theorem 4.1.9(ii)] since $c\in \Pi _U{\mathfrak {N}}$ . We have shown that ${\mathfrak {N}}$ is an elementary submodel of ${\mathfrak M}$ .

Proof of (ii): Assume that ${\mathfrak {M}},{\mathfrak {N}}\in \mathsf {Mod}\mathsf {T}(S)$ ; we have to show that ${\mathfrak {N}}$ is elementarily equivalent to ${\mathfrak M}$ . We may assume that ${\mathfrak M}$ and ${\mathfrak {N}}$ are countable, by the downward Löwenheim–Skolem–Tarski theorem [Reference Chang and Keisler11, corollary 2.1.4]. Now, ${\mathfrak M}$ and ${\mathfrak {N}}$ are elementarily equivalent by (*), since they have isomorphic ultrapowers. The proof of Lemma 1 is complete.

Proof. F is a functor, since (f is an elementary embedding of ${\mathfrak M}$ into ${\mathfrak {N}}$ if and only if it is an elementary embedding of $F({\mathfrak {M}})$ into $F({\mathfrak {N}})$ ), by Lemma 1 and the construction of F. Thus F is a concrete isomorphism by its construction.

To show that F preserves ultraproducts up to isomorphism, let U be an ultrafilter on a set I and let ${\mathfrak {M}}_i\in \mathsf {Mod}(\mathsf {T}(S))$ for all $i\in I$ . We will define an isomorphism j between $F(\Pi _U{\mathfrak {M}}_i)$ and $\Pi _U F({\mathfrak {M}}_i)$ . Let ${\mathfrak {N}}_i$ denote the $\mathbb N$ -part of ${\mathfrak {M}}_i$ , for each $i\in I$ . Then each ${\mathfrak {N}}_i$ is isomorphic to $\langle \mathbb N,\{\mathsf {suc}^k(\mathsf {0}) : k\in S\}\rangle $ by ${\mathfrak {M}}_i\in \mathsf {Mod}\mathsf {T}(S)$ . Let $y{\ :=\ }\langle y_i : i\in I\rangle \in \Pi _{i\in I}M_i$ . We define

$$\begin{align*}j(y_U) {\ :=\ } y_U\quad\mbox{if}\quad \{ i\in I : y_i\notin N_i\}\in U .\end{align*}$$

To define j on the rest, assume first that U is not $\omega ^+$ -complete. Then by a straightforward modification of the proof of (*) we get that both $\Pi _U{\mathfrak {N}}_i$ and $\Pi _U F({\mathfrak {N}}_i)$ consist of one $\mathbb N$ -model together with continuum many copies of all possible $\mathbb Z$ -models. If U is $\omega ^+$ -complete, then both $\Pi _U{\mathfrak {N}}_i$ and $\Pi _U F({\mathfrak {N}}_i)$ consist of one $\mathbb N$ -model only by [Reference Chang and Keisler11, proposition 4.2.4]. In both cases, there is an isomorphism between $F(\Pi _U{\mathfrak {N}}_i)$ and $\Pi _U F({\mathfrak {N}}_i)$ . We define

$$\begin{align*}j\mbox{ be any isomorphism between }F(\Pi_U{\mathfrak{N}}_i)\mbox{ and }\Pi_U F({\mathfrak{N}}_i) \end{align*}$$

and be identity on the rest. It is not difficult to check that $j:F(\Pi _U{\mathfrak {M}}_i)\to \Pi _U F({\mathfrak {M}}_i)$ is an isomorphism. This finishes the proof of Lemma 2.

Proof. (i) follows from Lemmas 1 and 2. Each of definitional equivalence, many-sorted definitional equivalence and bi-interpretability of two theories can be specified by the use of finitely many formulas on the language of the theories (see the references given for their definitions). Therefore, a concrete theory can be definitionally equivalent to at most countably many theories on a given other similarity type. This implies that of the continuum many theories $\mathsf {T}(S)$ on the same language; there are continuum many pairwise non-equivalent theories (neither many-sorted equivalent nor bi-interpretable). This finishes the proof of Corollary 1. With this, the presentation of Example 2 is finished.

Proof. The proof follows that of [Reference van Benthem and Pearce27, theorem]. Let assume first that the languages of $\mathsf {T}_1$ and $\mathsf {T}_2$ are disjoint. Assume that we have a bijection b satisfying (i) and (ii). We define a class $\mathsf {K}$ of models in the similarity type as the union of the similarity types of $\mathsf {T}_1$ and $\mathsf {T}_2$ and we will show that the first-order logic theory of $\mathsf {K}$ is a joint definitional extension for both $\mathsf {T}_1$ and $\mathsf {T}_2$ . For a model ${\mathfrak {M}}\in \mathsf {Mod}(\mathsf {T}_1)$ , let

$$\begin{align*}\overline{{\mathfrak{M}}}=\langle {\mathfrak{M}}, b({\mathfrak{M}})\rangle\end{align*}$$

denote the model whose universe is the joint universe of ${\mathfrak M}$ and $b({\mathfrak {M}})$ , the relation and function symbols of the language of $\mathsf {T}_1$ are interpreted as in ${\mathfrak M}$ , and the relation and function symbols of the language of $\mathsf {T}_2$ are interpreted as in $b({\mathfrak {M}})$ . Let

$$\begin{align*}\mathsf{K} = \{ \langle{\mathfrak{M}},b({\mathfrak{M}})\rangle : {\mathfrak{M}}\in\mathsf{Mod}(\mathsf{T}_1) \} .\end{align*}$$

We will show that $\mathsf {K}$ is axiomatizable, i.e., $\mathsf {K}=\mathsf {Mod}\mathsf {Th}\mathsf {K}$ . We use [Reference Chang and Keisler11, corollary 6.1.16(i)], which states that a class is elementary if and only if it is closed under taking ultraproducts and isomorphic images, and the complement is closed under ultrapowers. Now, $\mathsf {K}$ is closed under ultraproducts and isomorphisms by conditions (ii) and (i), since $\mathsf {Mod}(\mathsf {T}_1)$ is elementary. Assume that ${\mathfrak {A}}=\langle {\mathfrak {M}},{\mathfrak {N}}\rangle $ is such that an ultrapower $\Pi _U{\mathfrak {A}}$ is in $\mathsf {K}$ . We have to show that ${\mathfrak {A}}\in \mathsf {K}$ . Now, $\Pi _U{\mathfrak {A}}=\langle \Pi _U {\mathfrak {M}},\Pi _U{\mathfrak {N}}\rangle $ , and then $\Pi _U{\mathfrak {A}}\in \mathsf {K}$ means that $\Pi _U {\mathfrak {N}}=b(\Pi _U {\mathfrak {M}})$ . By condition (ii) we have $b(\Pi _U{\mathfrak {M}})=\Pi _U b({\mathfrak {M}})$ . Thus we have $\Pi _U{\mathfrak {N}}=\Pi _U b({\mathfrak {M}})$ . This implies ${\mathfrak {N}}=b({\mathfrak {M}})$ since any structure ${\mathfrak {B}}$ can be recovered from $\Pi _U{\mathfrak {B}}$ . We have seen that $\mathsf {K}$ is an elementary class; let

$$\begin{align*}\mathsf{T} = \mathsf{Th}(\mathsf{K}) .\end{align*}$$

Now, we show that $\mathsf {T}$ is a definitional extension of $\mathsf {T}_1$ . When the language of $\mathsf {T}_2$ has only one non-logical symbol, this follows immediately from Beth’s definability theorem (see [Reference Chang and Keisler11, theorem 2.2.22]), since for each ${\mathfrak {M}}\in \mathsf {Mod}(\mathsf {T}_1)$ there is at most one relation satisfying $\mathsf {T}$ , namely that of $b({\mathfrak {M}})$ . However, a generalized version of Beth’s theorem is well-known as folklore: if the $\mathcal {R}$ -free reduct of each model of $\mathsf {T}$ can be extended to at most one model of $\mathsf {T}$ , then $\mathsf {T}$ explicitly defines each member of $\mathcal {R}$ by a formula on the language of the $\mathcal {R}$ -free reducts.Footnote ³ The proof that $\mathsf {T}$ is a definitional extension of $\mathsf {T}_2$ is completely analogous. Thus, $\mathsf {T}_1$ and $\mathsf {T}_2$ are definitionally equivalent theories.

Assume now that the languages of $\mathsf {T}_1$ and $\mathsf {T}_2$ are not disjoint. Rename the symbols in the language of $\mathsf {T}_2$ so that the new symbols be distinct from any one used in $\mathsf {T}_1$ and $\mathsf {T}_2$ , call the new theory $\mathsf {T}_2'$ . Now, there is a natural bijection $b_1:\mathsf {Mod}(\mathsf {T}_2)\to \mathsf {Mod}(\mathsf {T}_2')$ satisfying conditions (i) and (ii), and $b_1\circ b:\mathsf {Mod}(\mathsf {T}_1)\to \mathsf {Mod}(\mathsf {T}_2')$ also satisfies (i) and (ii). These bijections are between models of theories of disjoint languages. Apply the previous case to $b_1$ and $b_1\circ b$ , and use that definitional equivalence is a transitive relation by [Reference Lefever and Székely22].

Proof. Let $b:\mathsf {Mod}(S_0)\to \mathsf {Mod}(S_1)$ be any bijection that preserves isomorphisms between distinct models. (We note that there is such a function b [see Lemma 2].) It preserves automorphism groups also (see Remark 3). We will show that b cannot preserve all ultrapowers. By Theorem 2, this will prove that $\mathsf {T}(S_0)$ and $\mathsf {T}(S_1)$ are not definitionally equivalent.

Let ${\mathfrak {M}}=\langle \omega ,\mathsf {0},\mathsf {suc},S_0\rangle \in \mathsf {Mod}(\mathsf {T}(S_0))$ . Let $b({\mathfrak {M}})=\langle \omega ,o,F,R\rangle $ and let U be any nonprincipal ultrafilter on $\omega $ . First we show that $b(\Pi _U{\mathfrak {M}})\ne \Pi _U b({\mathfrak {M}})$ if $b({\mathfrak {M}})$ contains any copy of a $\mathbb Z$ -model. Indeed, assume that $F^k(n)$ exists for all $k\in \mathbb Z$ for some $n\in \omega $ . Let $\langle \mathbb Z,P\rangle $ be the $\mathbb Z$ -model that is isomorphic to the induced subalgebra of $b({\mathfrak {M}})$ with universe $\{ F^k(n) : k\in \mathbb Z\}$ . By (*) in the proof of Lemma 1, $\Pi _U b({\mathfrak {M}})$ contains infinitely many copies of this $\mathbb Z$ -model. Therefore, the image of the $\mathbb Z$ -model in $b({\mathfrak {M}})$ under the diagonal embedding can be interchanged with a distinct copy of this $\mathbb Z$ -model in $\Pi _U b({\mathfrak {M}})$ . On the other hand, all automorphisms of $\Pi _U{\mathfrak {M}}$ leave the diagonal embedding of ${\mathfrak M}$ unchanged. Thus $b(\Pi _U{\mathfrak {M}})$ cannot be $\Pi _Ub({\mathfrak {M}})$ since the two have different automorphism groups. Therefore, we assume in the rest

1. (1) $\omega =\{ F^n(o) : n\in \omega \}$ and thus $R=\{ F^n(o) : n\in S_1\}$ .

Next we show that $b(\Pi _U{\mathfrak {M}})\ne \Pi _U b({\mathfrak {M}})$ if $F(y)\notin \{\mathsf {suc}^k(y) : k\in \mathbb Z\}$ for some $y\in \Pi _U\omega $ . Indeed, assume the latter. Choose an automorphism of $\Pi _U{\mathfrak {M}}$ that interchanges the copy of the $\mathbb Z$ -model containing y with another copy that does not contain either y or $F(y)$ and is identity on the rest. There is such an automorphism by (*) in the proof of Lemma 1. Now, this is not an automorphism of $\Pi _Ub({\mathfrak {M}})$ since F is one-to-one in $b({\mathfrak {M}})$ (by $b({\mathfrak {M}})\in \mathsf {Mod}(\mathsf { T}(S_1))$ ). Therefore, we assume in the rest

1. (2) $F(y)\in \{\mathsf {suc}^k(y) : k\in \mathbb Z\}$ for all $y\in \Pi _U\omega $ .

Now, (2) implies that there is a bound on “how far F can jump,” i.e., there is $N_0\in \omega $ such that for all $n\in \omega $ we have

1. (2a) $F(n)=n+k$ implies $|k|<N_0$ .

Indeed, let $J{\ :=\ }\{ k\in \mathbb Z : F(n)=n+k\mbox { for some }n\in \omega \}$ and assume that J is infinite. Let $f:\omega \to J$ be a bijection; there is such a bijection because J is countably infinite. For all $j\in J$ let $n_j\in \omega $ be such that $F(n_j)=n_j+j$ and let $y_i{\ :=\ } n_{f(i)}$ for all $i\in \omega $ . Let $y {\ :=\ }\langle y_i : i\in \omega \rangle $ . Then $F(y_U)\notin \{\mathsf {suc}^k(y_U) : k\in \mathbb Z\}$ because U is nonprincipal. This contradicts (2), and thus J is finite, which implies the existence of the bound $N_0$ .

Next we show that $b(\Pi _U{\mathfrak {M}})\ne \Pi _U b({\mathfrak {M}})$ if F does not agree with $\mathsf {suc}$ on copies of $\mathbb Z$ -models in $\Pi _U{\mathfrak {M}}$ all elements of which are in $\mathsf {R}$ or no elements of which are in $\mathsf {R}$ . Indeed, assume $\mathsf {R}(\mathsf {suc}^m(y))$ in $\Pi _U{\mathfrak {M}}$ for all $m\in \mathbb Z$ . There is $k\in \mathbb Z$ such that $F(y)=\mathsf {suc}^k(y)$ , by (2). There is an automorphism $\alpha $ in $\Pi _U{\mathfrak {M}}$ that “shifts with $1$ step in $Y{\ :=\ }\{\mathsf {suc}^m(y) : m\in \mathbb Z\}$ ,” i.e., $\alpha (z)=\mathsf {suc}(z)$ for all $z\in Y$ , because $\mathsf {R}(z)$ for all $z\in Y$ . Now, if $F(z)\ne \mathsf {suc}^k(z)$ for some $z\in Y$ , then $\alpha $ is not an automorphism in $\Pi _Ub({\mathfrak {M}})$ . So, assume that $F(z)=\mathsf {suc}^k(z)$ for all $z\in Y$ . Now, if $k\notin \{1,-1\}$ , then $Y\ne \{ F^m(y) : m\in \mathbb Z\}=\{\mathsf {suc}^{mk}(y) : m\in \mathbb Z\}$ . However, there is an automorphism $\beta $ of $\Pi _Ub({\mathfrak {M}})$ that “shifts $\{ F^m(y) : m\in \mathbb Z\}$ with one step” and leaves all the other elements fixed. This $\beta $ is not an automorphism of $\Pi _U{\mathfrak {M}}$ . We show now that $F(z)=\mathsf {suc}^{-1}(z)$ for all $z\in Y$ cannot happen. Indeed, assume that $F(z)=\mathsf {suc}^{-1}(z)$ for all $z\in Y$ . Then there is an “ $N_0$ -long descending F-chain in $b({\mathfrak {M}})$ ,” i.e., there is $n\in \omega $ such that $F(k)=k-1$ for all $n-N_0\le k\le n$ in $b({\mathfrak {M}})$ . Then F has to stay below n since then on, by (2a) and F being one-to-one, i.e., $F^k(n)\le n$ for all $k\in \omega $ . This again contradicts F being one-to-one. The same argument works if $\lnot \mathsf {R}(\mathsf {suc}^m(y))$ in $\Pi _U{\mathfrak {M}}$ for all $m\in \mathbb Z$ . By the above, we assume in the rest

1. (3) $F(z)=\mathsf {suc}(z)$ for all $z\in Y{\ :=\ }\{\mathsf {suc}^k(y) : k\in \mathbb Z\}$ if $y\in \Pi _U\omega $ is such that either $\mathsf {R}(z)$ in $\Pi _U{\mathfrak {M}}$ for all $z\in Y$ or $\lnot \mathsf {R}(z)$ in $\Pi _U{\mathfrak {M}}$ for all $z\in Y$ .

Now, (3) has implications on the behavior of F on long $\mathsf {R}$ -chains or $\lnot \mathsf {R}$ -chains in ${\mathfrak M}$ , as follows. Let us say that $\langle y+k : k<n\rangle = \langle y, y+1, y+2,...,y+n-1\rangle $ is an n-long $\mathsf {R}$ -chain in ${\mathfrak M}$ beginning with y if $\mathsf {R}(y+k)$ in ${\mathfrak M}$ for all $k<n$ . The definition of a $\lnot \mathsf {R}$ -chain is analogous. First we show the existence of a bound N such that for all $\mathsf {R}$ -chains longer than $2N$ , F agrees with $\mathsf {suc}$ on the chain, except for N-long chains at the beginning and at the end of the chain, and the same holds for $\lnot \mathsf {R}$ -chains.

1. (3a) There is $N> N_0$ such that for all $\mathsf {R}$ -chains longer than $2N$ and beginning with y we have $F(\mathsf {suc}^k(y))=\mathsf {suc}^{k+1}(y)$ for all $y+N\le k\le y+n-N$ and the same holds for $\lnot \mathsf {R}$ -chains, too.

Indeed, assume that there is no such bound. Then n is not such a bound for any $n\in \omega $ , i.e., there is an m-long $\mathsf {R}$ -chain with beginning y such that $m\ge 2n$ and $F(\mathsf { suc}^{k}(y))\ne \mathsf {suc}^{k+1}(y)$ for some $y+n\le k\le y+m-n$ . For each $n\in \omega $ , let $y_{n}{\ :=\ } \mathsf {suc}^k(y)$ for such a chain and let $z=\langle y_{n}: n\in \omega \rangle $ . Then in the ultrapower $\Pi _U{\mathfrak {M}}$ we have $F(z)\ne \mathsf {suc}(z)$ , while $\mathsf {R}(\mathsf {suc}^k(z))$ for all $k\in \mathbb Z$ . This contradicts (3). The proof for the $\lnot \mathsf {R}$ -chains is analogous. This completes the proof of (3a).

From now on we assume that N is as in (3a). Next we prove that if there is an $n\ge 3N$ -long $\mathsf {R}$ -chain ending with $y-1$ and there is an $n\ge 3N$ -long $\lnot \mathsf {R}$ -chain starting with $y+1$ , then the behavior of F is rather close to that of $\mathsf {suc}$ in these chains. Namely, $F^k(o)=k$ in the interval $[y-n+N, y+n-N]$ except in $[y-N,y+N]$ , and F enumerates the elements of $[y-N,y+N]$ .

1. (3b) Assume that $n>3N$ and there is an n-long $\mathsf {R}$ -chain in ${\mathfrak M}$ ending with $y-1$ and there is an n-long $\lnot \mathsf {R}$ -chain starting with $y+1$ . Then $F^k(o)=k$ for all $y-n+N\le k\le y-N$ and $y+N\le k\le y+n-N$ . Further, $\{ F^k(o) : y-N\le k\le y+N\}=\{ k : y-N\le k\le y+N\}$ .

Indeed, assume that n and y are as in (3b). There is an $n\ge 2N$ -long $\mathsf {R}$ -chain beginning with $y-n$ , so by (3a) we have $F(y-n+k)=y-n+k+1$ for all $y-n+N\le k\le y-N$ . Let $v{\ :=\ } y-n+N$ . Then

(a) $$ \begin{align} F(v+k)=v+k+1 \text{ for all }k\le n-2N.\end{align}$$

Then $F(w)\notin \{ k : v< k \le v+n-2N\}$ for all $w<v$ since F is one-to-one by $b({\mathfrak {M}})\models \mathsf {T}(S_1)$ . By $n-2N\ge N>N_0$ and (2a) then $F(w) \le v$ for all $w<v$ and hence F enumerates $[0,v]$ , i.e.,

(b) $$ \begin{align}\{ F^k(o) : k\le v\}=\{ k : k\le v\}.\end{align} $$

There is $m\in \omega $ such that $v=F^m(o)$ , by (1). As before, by (2a) and (a) we have that $m\le v$ and then $m=v$ by (b). Thus, $F^{v}(o)=v$ and by (a) we have $F^k(o)=k$ for all $v\le k\le y-N$ . The rest of (3a) can be obtained similarly.

We are ready to show $b(\Pi _U{\mathfrak {M}})\ne \Pi _Ub({\mathfrak {M}})$ , finishing the proof of Theorem 3. Let X be the infinite set where $S_0$ and $S_1$ differ. Then X is disjoint from $S_0$ and $X\subseteq S_1$ , by definition. Let $x_n$ denote the nth member of X according to the natural ordering of $\omega $ . Then $\lnot \mathsf {R}(x_n)$ in ${\mathfrak M}$ by $x_n\notin S_0$ and the definition of $\mathsf {R}$ in ${\mathfrak M}$ . Also, $\mathsf {R}(x_n-k-1)$ and $\lnot \mathsf {R}(x_n+k)$ for all $k<n$ , because the $0,1$ -sequences between two xs are laid by alphabetical order; thus, before the nth $x\in X$ there are n many $1$ s and after it there are $n+1$ many $0$ s. Let $x{\ :=\ }\langle x_n : n\in \omega \rangle $ . Then $x_U$ is contained in $\Pi _U{\mathfrak {M}}$ in a copy of the $\mathbb Z$ -model $\langle \mathbb Z,\{k : k<0\}\rangle $ , i.e., all members of the $\mathbb Z$ -model below $x_U$ are in $\mathsf {R}$ , and no member after $x_U$ , including $x_U$ is in $\mathsf {R}$ .

How does the set $C{\ :=\ }\{\mathsf {suc}^k(x_U) : k\in \mathbb Z\}$ look like in $\Pi _Ub({\mathfrak {M}})$ ? Note that we cannot assume $F=\mathsf {suc}$ and $o=0$ in $b({\mathfrak {M}})$ . Thus, for example, we cannot infer $\mathsf {R}(x_n)$ in $b({\mathfrak {M}})$ from $x_n\in S_1$ . However, we can use our assumptions (1)–(3) and their implications. Especially, we can use (3b). Let $n\ge 3N$ , where N is the bound in (3b). We have seen in the previous paragraph that, in ${\mathfrak M}$ , the assumptions hold for $y=x_n$ . By (1), the definition of $S_1$ , and (3b) then $\mathsf {R}(F^k(o))$ for $x_n-n+N\le k\le x_n-N$ and $\lnot \mathsf {R}(F^k(o))$ for $x_n+N\le k\le x_n+n-N$ , in $b({\mathfrak {M}})$ . Also, by (3b) we get that F agrees with $\mathsf {suc}$ “below” $\mathsf {suc}^{-N}(x_U)$ and “above” $\mathsf {suc}^{N}(x_U)$ , in $\Pi _Ub({\mathfrak {M}})$ . Further, F enumerates the interval $I{\ :=\ }[\mathsf {suc}^{-N}(x_U),\mathsf {suc}^N(x_U)]$ . However, there is a difference between $\Pi _U{\mathfrak {M}}$ and $\Pi _Ub({\mathfrak {M}})$ concerning I. Namely, in $\Pi _U{\mathfrak {M}}$ exactly N elements of I are in $\mathsf {R}$ because $\lnot \mathsf { R}(x_n)$ in ${\mathfrak M}$ . At the same time, due to the definition of $S_1$ , by (1) we get $\mathsf {R}(F^w(o))$ for all $w\in X$ . Hence, exactly $N+1$ elements are in $\mathsf {R}$ in the corresponding intervals in $b({\mathfrak {M}})$ , so exactly $N+1$ elements of I are in $\mathsf {R}$ , in $\Pi _Ub({\mathfrak {M}})$ .

For all $n\in \omega $ let $y_n\in \omega $ be similar to $x_n$ in that $\lnot \mathsf {R}(y_n)$ , there is an n-long $\mathsf {R}$ -chain ending with $y_n-1$ , there is an n-long $\lnot \mathsf {R}$ -chain starting with $y_n+1$ , and such that neither $y_n$ nor any element of these chains belong to X. There are such $y_n$ s by the construction of $S_0, S_1$ . Let $y{\ :=\ }\langle y_n : n\in \omega \rangle $ . Then there is an automorphism in $\Pi _U{\mathfrak {M}}$ that interchanges $x_U$ with $y_U$ . We will show that there is no automorphism in $\Pi _Ub({\mathfrak {M}})$ that interchanges $\mathsf {suc}^{-N}(x_U)$ and $\mathsf {suc}^{-N}(y_U)$ . Indeed, such an automorphism has to be a bijection between the intervals I and J because it can be seen that F enumerates $J{\ :=\ }[\mathsf {suc}^{-N}(y_U),\mathsf {suc}^N(y_U)]$ in $\Pi _Ub({\mathfrak {M}})$ and F agrees with $\mathsf {suc}$ outside J. We have seen that there are $N+1$ elements of I that are in $\mathsf {R}$ in $\Pi _Ub({\mathfrak {M}})$ . It can be seen just the same way that there are only N elements of J because $\lnot \mathsf {R}(y_U)$ in $\Pi _Ub({\mathfrak {M}})$ . Therefore, no bijection between I and J can preserve $\mathsf {R}$ . The proof of Theorem 3 is complete.

Proof. This is just a reformulation of Theorem 2.

Proof. The reduct-formation functor $\Pi $ is a concrete functor and it always preserves isomorphisms and ultraproducts “forwards,” i.e., from $\mathsf {T}^{+}$ to $\mathsf {T}$ . It is a bijection up to isomorphism if and only if it is a bijection because the range of $\Pi $ is always closed under isomorphisms. Thus, if $\Pi $ is a category theoretical equivalence, then each model of $\mathsf {T}$ has a unique expansion in $\mathsf { Mod}(\mathsf {T}^{+})$ ; therefore, $\Pi $ preserves isomorphisms and ultraproducts also backwards. Thus, if $\Pi $ is a category theoretical equivalence, then it satisfies (i) and (ii) in Theorem 2; hence, $\mathsf {T}$ and $\mathsf {T}^+$ are definitionally equivalent. The other direction is easy.

Proof. Let $\mathsf {T}'$ denote the theory $\mathsf {T}$ where each relation symbol $R\in \mathcal {R}$ is replaced by a new relation symbol $R'$ not occurring in the language of $\mathsf {T}$ (and having the same arity). Then $\mathsf {T}\cup \mathsf {T}'\models \forall \bar {x}[R(\bar {x})\leftrightarrow R'(\bar {x})]$ for all $\mathsf {R}\in \mathcal {R}$ , since the $\mathcal {R}$ -free reduct of each model of $\mathsf {T}$ has at most one expansion to a model of $\mathsf {T}$ . Let $R\in \mathcal {R}$ be arbitrary. By the compactness theorem, there is a finite subset $\mathsf {T}_0$ of $\mathsf {T}$ such that $\mathsf {T}_0\cup \mathsf { T}_0'\models \forall \bar {x}[R(\bar {x})\leftrightarrow R'(\bar {x})]$ . Therefore, R has to occur in $\mathsf {T}_0$ , since otherwise both the empty set and the biggest relation of the same rank as R can be chosen in a model to satisfy $\mathsf {T}_0$ . Since $\mathsf {T}_0$ is finite, it contains only finitely many elements from $\mathcal {R}$ , let the set of these elements be $\mathcal {R}_0{\ :=\ }\{ R_1,\dots ,R_n\}$ , and we may assume $R_1$ is R. By the usual Beth’s theorem, there is a formula $\varphi _R$ on the language $\Sigma \cup \{ R_2,\dots , R_n\}$ which defines R in $\mathsf { T}_0$ . Now, let $\mathsf {T}_1$ be the theory we obtain from $\mathsf {T}_0$ by replacing R in it everywhere with $\varphi _R$ . Then $\mathsf {T}_1$ follows from $\mathsf {T}_0$ , only $R_2,\dots , R_n$ occur in $\mathsf {T}_1$ and $\mathsf {T}_1\cup \mathsf {T}_1'\models \forall \bar {x}[R_2(\bar {x})\leftrightarrow R_2'(\bar {x})]$ . By the usual Beth’s theorem, there is a formula $\varphi _{R1}$ on the language $\Sigma \cup \{ R_3,\dots , R_n\}$ which defines $R_1$ in $\mathsf {T}_1$ . And so on. At the end we get $\mathsf {T}_{n-1}$ on the language $\Sigma \cup \{ R_n\}$ and a formula $\varphi _{Rn}$ on the language $\Sigma $ which defines $R_n$ in $\mathsf {T}_{n-1}$ . Let $\psi _n$ be $\varphi _{Rn}$ , let $\psi _{n-1}$ be the formula we get from $\varphi _{Rn-1}$ by replacing $R_n$ in it by $\psi _n$ , etc. Then $\psi _1$ is in the language $\Sigma $ which defines R in $\mathsf {T}_0\subseteq \mathsf {T}$ .