# Rich groups, weak second order logic, and applications

Olga Kharlampovich111Hunter College, CUNY; Supported by the grant 422503 from
the Simons Foundation. , Alexei Myasnikov, Mahmood Sohrabi 222Stevens
Institute of Technology.

###### Abstract

In this paper we initiate a study of first-order rich groups, i.e., groups
where the first-order logic has the same power as the weak second order logic.
Surprisingly, there are quite a lot of finitely generated rich groups, they
are somewhere in between hyperbolic and nilpotent groups (these ones are not
rich). We provide some methods to prove that groups (and other structures) are
rich and describe some of their properties. As corollaries we look at Malcev’s
problems in various groups.

###### Contents

  1. 1 Introduction
  2. 2 Interpretability and bi-iterpretagbility
    1. 2.1 Interpretability
    2. 2.2 Properties preserved under interpretations
    3. 2.3 Bi-interpretability
  3. 3 Weak second order logic
    1. 3.1 Hereditary finite and list superstructures
    2. 3.2 The weak second order logic as a fragment of $L_{\omega_{1},\omega}$
  4. 4 Definitions and basic properties of rich structures
  5. 5 First-order rigidity, quasi-finite axiomatizability, primality, and homogeneity
    1. 5.1 Primality and homogeneity
    2. 5.2 First-order rigidity and quasi-finite axiomatizability
  6. 6 Properties definable in rich groups
    1. 6.1 Malcev’s problem
    2. 6.2 Properties of subgroups
  7. 7 Rich existentially closed structures
  8. 8 Rich rings
  9. 9 Algebras
  10. 10 Rich monoids
  11. 11 Classical groups and lattices
  12. 12 Nilpotent and Polycyclic Groups
  13. 13 Metabelian groups: examples and open problems
    1. 13.1 Metabelian Baumslag-Solitar groups and the wreath product ${\mathbb{Z}}wr{\mathbb{Z}}$
    2. 13.2 Open problems for solvable groups
  14. 14 Free metabelian groups
    1. 14.1 Preliminaries for metabelian groups
      1. 14.1.1 Centralizers.
      2. 14.1.2 A homomorphism on commutators.
      3. 14.1.3 An exponentiation formula.
      4. 14.1.4 A characterization of the identity.
      5. 14.1.5 Normal forms in ${\mathbb{Z}}\bar{G}$-module $G^{\prime}$.
    2. 14.2 ${\mathbb{Z}}$ is absolutely interpretable in $G$
    3. 14.3 Interpretation of ${\mathbb{Z}}$-exponentiation on $G$
    4. 14.4 Interpretation of ${\mathbb{Z}}[a_{1},a_{1}^{-1},\ldots,a_{n},a_{n}^{-1}]$ in ${\mathbb{Z}}$
    5. 14.5 Interpretation of ${\mathbb{Z}}\bar{G}$-module $G^{\prime}$ in $G$
      1. 14.5.1 Discrimination of ${\mathbb{Z}}[a_{1},\ldots,a_{n}]$ by ${\mathbb{Z}}$.
      2. 14.5.2 Definability of $(G^{\prime})^{I_{\bar{\alpha}}}$ in $G$.
      3. 14.5.3 Interpretation of the action of ${\mathbb{Z}}[a_{1},\ldots,a_{n}]$ on $G^{\prime}$.
    6. 14.6 Proof of Theorem 30
    7. 14.7 Applications and open problems

##  1 Introduction

The study of efficiency of the first-order logic goes back to Hilbert and
Godel, and later, where algebra concerns, to Tarski and Malcev. For a group
(or a ring, or any structure) $A$ the first-order theory $Th(A)$ is the set of
all sentences in group (ring, etc.) language that are true in $A$, so $Th(A)$
is all the possible information about $A$ expressible in the first-order logic
of group theory. Two groups (rings, etc.) $A$ and $B$ are called elementarily
equivalent ($A\equiv B$) if $Th(A)=Th(B)$, i.e., they are indistinguishable in
the first-order logic. Tarski and Malcev pushed forward a problem of
describing groups and rings (in some natural classes) that are elementarily
equivalent. If $A$ and $B$ are isomorphic then, obviously, $A\equiv B$. The
most interesting question here is if $A\equiv B$ then how close to being
isomorphic $A$ and $B$ could be, i.e., how good the description by $Th(A)$ of
$A$ is? It was soon understood (Löwenheim-Skolem theorem) that for any
infinite structure $A$ there is a structure $B$ such that $A\equiv B$ and they
have different cardinalities, so in the question above one may want to assume
that $A$ and $B$ have the same cardinality. This leads to the notion of
categoricity, and stability, and some other important developments in modern
model theory. But categoricity is a rather rare phenomenon. The following
seems to be the general picture. Given a finitely generated group (or a ring
or a structure) $A$ there is in general little hope to characterize all
arbitrary countable groups $B$ with $A\equiv B$. But, rather often there is a
decent chance to describe such $B$ if it is assumed to be finitely generated.
Algebraically, it makes sense to consider finitely generated objects, rather
then countable ones. In the opposite direction (towards uncountable objects)
one can start with a group or a ring $A$ and “complete” it by adding to $A$
solutions to various classes of equations until it is algebraically complete
(with respect to some theory). The typical picture here is arithmetic, i.e.,
the ring of integers $\mathbb{Z}$: for every finitely generated ring $B$ if
$\mathbb{Z}\equiv B$ then $\mathbb{Z}\cong B$; there are countable non-
isomorphic such $B$ (“non-standard models” of arithmetic); towards uncountable
models one can go from $\mathbb{Z}$ to $\mathbb{Q}$ and then to completions
${\mathbb{C}}$, or $\mathbb{R}$, or $\mathbb{Q}_{p}$, which are tame from the
view-point of the first-order logic. Since Tarski and Malcev there has been
many interesting results about elementary equivalence of finitely generated
groups and rings. A question dominating research in this area has been if and
when elementary equivalence between finitely generated groups (rings) implies
isomorphism. Recently, Avni et. al. [3] coined the term first-order rigidity:
a finitely generated group (ring) $A$ is first-order rigid if any other
finitely generated group (ring) elementarily equivalent to $A$ is isomorphic
to $A$.

In another direction Malcev proposed to test the expressive power of the
first-order logic by studying definable subgroups of a given group. A subgroup
$K$ of a group $A$ is definable in $A$ if there is a first-order formula
$\phi(x)$ without parameters such that $K$ consists precisely of those
elements in $A$ that make $\phi(x)$ true. The main general question here is
how rich are definable subsets in a group or algebra. In particular, in 1965
Malcev asked which subgroups of free groups $F$ are definable in the first-
order logic. This problem was solved in [25] and [43]. It turned out that
among proper subgroups of $F$ only cyclic ones are definable. The same holds
in arbitrary non-elementary torsion-free hyperbolic groups. It follows that
the first-order theory is not quite adequate in describing subgroups in these
groups. On the other hand there are groups which have interesting definable
subgroups (nilpotent, metabelian, etc.). However, till now there were no known
infinite groups where all subgroups were uniformly definable, i.e., groups $G$
where for each natural $n$ there is a formula $\Phi_{n}(x_{1},\ldots,x_{n},y)$
which holds in $G$ on elements $a_{1},\ldots,a_{n},b$ if and only if $b$
belongs to the subgroup generated by $a_{1},\ldots,a_{n}$. This is a very
strong definability property which is not amenable to any known algebraic
techniques.

We intend to address the first-order rigidity and Malcev’s question on
definability of subgroups in a wide class of groups and rings. This approach
allows one to show that the language of the first-order logic in various
classical groups and algebras has the same expressive power as the language of
the weak second-order logic. Such groups include
$GL_{n}(\mathbb{Z}),SL_{n}(\mathbb{Z}),T_{n}(\mathbb{Z}),n\geq 3$ [37],
various finitely generated metabelian groups (for example, the free nonabelian
ones), many polycyclic groups, free associative algebras, free group algebras
over infinite fields, and many others. To prove this we show that the group
(ring) $G$ in question is bi-interpretable with $HF(G)$ — the superstructure
of the hereditary finite sets over $G$. In this case the weak second-order
logic over $G$ is interpretable in $G$. We term such a group (or any such
structure) $G$ rich. In fact, to show that $G$ is rich it suffices to bi-
interpret it with any rich structure. Notice, that the arithmetic $\mathbb{Z}$
is rich, so to prove that $G$ is rich it suffices to show that it is bi-
interpretable with the ring $\mathbb{Z}$.

Many objects associated to a rich group (or ring) $G$, such as finitely
generated subgroups (subrings, ideals), the geometry of its Cayley graph, as
well as many others are uniformly definable in it. We observe, that rich
groups are first-order rigid. Furthermore, finitely generated rich structures
are completely characterized by a single axiom. Interestingly, as we mentioned
above free and torsion-free hyperbolic groups are not rich. Actually they are
very far from being rich, however, their group algebras over infinite fields
are rich [22]. This shows how much more expressive is the first order ring
language of a group algebra of a free group compared with the first order
language of the group.

There are many examples of first-order rigid groups and algebras. For
instance, Avni, Lubotzky and Meiri [3] showed that non-uniform higher
dimensional lattices are first-order rigid, as well as finitely generated
profinite groups [30]. Lasserre showed that under some natural conditions
polycyclic groups [28] are also first-order rigid, etc. Some of these groups
are rich and some not. It turns out that studying richness or lack there of is
also very useful in studying arbitrary groups (rings) elementarily equivalent
to a given one. For example, when a finitely generated group $G$ is bi-
interpretable with ${\mathbb{Z}}$, in many cases arbitrary groups that are
elementarily equivalent to $G$ seem to have a very particular structure, they
are kind of “completions” or “closures” of $G$ with respect to a ring $R$
elementarily equivalent to ${\mathbb{Z}}$. When dealing with classical groups
or algebras such notions of completion or closure coincide with the classical
ones, where completions have the same “algebraic scheme”, but the points are
over the ring $R$ as above. The typical example is the group
$G=\textrm{SL}_{n}({\mathbb{Z}})$, it is rich (See (1) in Theorem 26 below),
so it is first-order rigid, moreover, any other group $H$ with $G\equiv H$ is
isomorphic to $\textrm{SL}_{n}(R)$ with $R\equiv\mathbb{Z}$. On the other hand
the “extent” to which a group $G$ is not rich also often seems to affect the
structure of arbitrary groups elementarily equivalent to $G$. Again it seems
such groups are “deformations” of “exact completions” or “exact closures” of
$G$ over a ring $R$ as above. It only seems proper that these deformations can
usually be captured by cohomological data. For example, the group
$\textrm{T}_{n}(\mathcal{O})$ is not rich, if the ring $\mathcal{O}$ of
integers of a number field has an infinite group of units (though
$\textrm{T}_{n}(\mathcal{O})$ and $\mathcal{O}$ are mutually interpretable in
each other). In this case the lack of richness is modulo the infinite center,
therefore any group $H$ with $H\equiv\textrm{T}_{n}(\mathcal{O})$ is an
abelian deformation of a group $\textrm{T}_{n}(R)$ where $R\equiv\mathcal{O}$
(See (3) in Theorem 26 below). It is very interesting to study groups which
are rich but there is no any obvious “algebraic scheme” lying around, for
example, finitely generated free metabelian groups. In this case the
completions still exist, but they are not described by any algebraic schemes,
the schemes here are more general.

##  2 Interpretability and bi-iterpretagbility

###  2.1 Interpretability

The model-theoretic technique of interpretation or definability is crucial in
our considerations. Because of that we remind here some precise definitions
and several known facts that may not be very familiar to algebraists.

A _language_ (or _a signature_) $L$ is a triple $(Fun,Pr,C)$, where
$Fun=\\{f,\ldots\\}$ is a set of functional (or operational) symbols $f$
coming together with their arities $n_{f}\in\mathbb{N}$, $Pr$ is a set of
relation (or predicate) symbols $Pr=\\{P,\ldots\\}$ coming together with their
arities $n_{P}\in\mathbb{N}$, and a set of constant symbols
$C=\\{c,\ldots\\}$. Sometimes we write $f(x_{1},\ldots,x_{n})$ or
$P(x_{1},\ldots,x_{n})$ to show that $n_{f}=n$ or $n_{P}=n$. Usually we denote
variables by small letters $x,y,z,a,b,u,v,\ldots$, while the same symbols with
bars $\bar{x},\bar{y},\ldots$ denote tuples of the corresponding variables,
say $\bar{x}=(x_{1},\ldots,x_{n})$. In this paper we always assume, if not
said otherwise, that the languages we consider are finite. The following
languages appear frequently throughout the text: the language of semigroups
$\\{\cdot\\}$, where $\cdot$ is the binary multiplication symbol; the language
of monoids $\\{\cdot,1\\}$, where 1 is the constant symbol for the identity
element; the language of groups $\\{\cdot,^{-1},1\\}$, where -1 is the symbol
of inversion; and the language of rings $\\{+,\cdot,0\\}$ with the standard
symbols for addition, multiplication, and the additive identity $0$. Sometimes
we add the constant $1$ to form the language of unitary rings (a priori, our
rings are not unitary).

An interpretation of a constant symbol $c$ in a set $A$ is an element
$c^{A}\in A$. For a functional symbol $f$ an interpretation in $A$ is a
function $f^{A}\colon A^{n_{f}}\to A$, and for a predicate $P$ it is a set
$P^{A}\subseteq A^{n_{P}}$.

A structure in the language $L$ (an $L$-structure) with the base set $A$,
sometimes denoted by ${\mathbb{A}}=\langle A;L\rangle$ or simply by
${\mathbb{A}}=\langle A;f,\ldots,P,\ldots,c,\ldots\rangle$, is the set $A$
together with interpretations $f^{A},\ldots,P^{A},\ldots,c^{A},\ldots$
Sometimes we will denote this structure also by ${\mathbb{A}}=\langle
A;f^{A},\ldots,P^{A},\ldots,c^{A},\ldots\rangle$. For a given structure
${\mathbb{A}}$ by $L({\mathbb{A}})$ we denote the language of ${\mathbb{A}}$.
When the language $L$ is clear from the context, we follow the standard
algebraic practice and denote the structure ${\mathbb{A}}=\langle A;L\rangle$
simply by $A$. For example, we refer to a field $\mathbb{F}=\langle
F;+,\cdot,0,1\rangle$ simply as $F$, or to a group $\mathbb{G}=\langle
G;\cdot,^{-1},1\rangle$ as $G$, etc. Sometimes we refer to a first-order
formula in a language $L$ as to an $L$-formula and denote by
${\mathcal{F}}_{L}$ the set of all $L$-formulas.

The graph of a constant $c$ in $A$ is the set $\\{c^{A}\\}$, the graph of a
function $f$ in $A$ is $\\{(b_{1},\ldots,b_{n_{f}},b)\in A^{n_{f}+1}\mid
f^{A}(b_{1},\ldots,b_{n_{f}})=b,b_{1},\ldots,b_{n_{f}}\in A\\}$, and the graph
of a predicate $P$ in $A$ is $P^{A}$ or $\\{(b_{1},\ldots,b_{n_{P}})\in
A^{n_{P}}\mid{\mathbb{A}}\models P^{A}(b_{1},\ldots,b_{n_{P}})\\}$.

Let ${\mathbb{B}}=\langle B;L({\mathbb{B}})\rangle$ be a structure. A subset
$A\subseteq B^{n}$ is called definable ($0$-definable, or absolutely
definable, or definable without parameters) in ${\mathbb{B}}$ if there is a
formula $\phi(x_{1},\ldots,x_{n})$ (without parameters) in $L({\mathbb{B}})$
such that $A=\\{(b_{1},\ldots,b_{n})\in
B^{n}\mid{\mathbb{B}}\models\phi(b_{1},\ldots,b_{n})\\}$. In this case we
denote $A$ by $\phi(B^{n})$ or $\phi({\mathbb{B}})$ and say that _$\phi$
defines $A$_ in ${\mathbb{B}}$. If
$\psi(x_{1},\ldots,x_{n},y_{1},\ldots,y_{k})$ is a formula in
$L({\mathbb{B}})$ and $\bar{p}=(p_{1},\ldots,p_{k})$ is a tuple of elements
from $B$, then the set $\\{(b_{1},\ldots,b_{n})\in
B^{n}\mid{\mathbb{B}}\models\psi(b_{1},\ldots,b_{n},p_{1},\ldots,p_{k})\\}$ is
called _definable_ in ${\mathbb{B}}$ _with parameters_ $\bar{p}$ and denoted
by $\psi(B^{n},\bar{p})$ or $\psi({\mathbb{B}},\bar{p})$.

Let $c$, $f$ and $P$ be a constant, an operator and a predicate from some
language $L$ (may be $L\neq L({\mathbb{B}})$) which have interpretations
$c^{A}$, $f^{A}$, $P^{A}$ on the set $A\subseteq B^{n}$. The interpretations
$c^{A}$, $f^{A}$ and $P^{A}$ are _definable_ in ${\mathbb{B}}$ if their graphs
are definable in ${\mathbb{B}}$. Sometimes in this case we say that the
constant $c$, the operator $f$ and the predicate $P$ are definable on $A$ in
${\mathbb{B}}$.

In the same vein an algebraic structure ${\mathbb{A}}=\langle
A;f,\ldots,P,\ldots,c,\ldots\rangle$ is _definable_ (or $0$-_definable_ , or
absolutely definable) in ${\mathbb{B}}$ if there is a definable subset
$A^{\ast}\subseteq B^{n}$ and interpretations $f^{A},P^{A},c^{A}$ on
$A^{\ast}$ of the symbols $f,P,c$ all definable in ${\mathbb{B}}$, such that
the structure ${\mathbb{A}}^{\ast}=\langle
A^{\ast};f^{A},\ldots,P^{A},\ldots,c^{A},\ldots\rangle$ is isomorphic to
${\mathbb{A}}$. (Notice, that constants $c,\ldots$ belong to the language of
${\mathbb{A}}$, they are not parameters.) For example, if $Z(G)$ is the center
of a group $G$ then it is definable as a group in $G$.

One can do a bit more in terms of definability. In the notation above if
$\sim$ is a definable equivalence relation on a definable subset
$A^{\ast}\subseteq B^{n}$ then we say that the quotient set $A^{\ast}/\sim$ is
interpretable in ${\mathbb{B}}$. Furthermore, interpretations
$f^{A},P^{A},c^{A}$ of symbols $f,P,c\in L$ on the quotient set
$A^{\ast}/\sim$ are interpretable in ${\mathbb{B}}$ if the full preimages of
their graphs in $A^{\ast}$ are definable in ${\mathbb{B}}$.

######  Definition 1.

An algebraic structure ${\mathbb{A}}=\langle
A;f,\ldots,P,\ldots,c,\ldots\rangle$ is absolutely interpretable (or
$0$-interpretable) in a structure ${\mathbb{B}}=\langle
B;L({\mathbb{B}})\rangle$ if there is a subset $A^{\ast}\subseteq B^{n}$
definable in ${\mathbb{B}}$, there is an equivalence relation $\sim$ on
$A^{\ast}$ definable in ${\mathbb{B}}$, and there are interpretations $f^{A}$,
$P^{A}$, $c^{A}$ of the symbols $f,P,c$ on the quotient set $A^{\ast}/{\sim}$
all interpretable in ${\mathbb{B}}$, such that the structure
${\mathbb{A}}^{\ast}=\langle
A^{\ast}/{\sim};f^{A},\ldots,P^{A},\ldots,c^{A},\ldots\rangle$ is isomorphic
to ${\mathbb{A}}$.

For example, if $N$ is a normal definable subgroup of a group $G$, then the
equivalence relation $x\sim y$ on $G$ given by $xN=yN$ is definable in $G$, so
the quotient set $G/N$ of all right cosets of $N$ is interpretable in $G$. It
is easy to see that the multiplication induced from $G$ on $G/N$ is also
interpretable in $G$. This show that the quotient group $G/N$ is interpretable
in $G$.

Now we introduce some useful notation. An interpretation of ${\mathbb{A}}$ in
${\mathbb{B}}$ is described by the following set of formulas in the language
$L({\mathbb{B}})$

$\Gamma=\\{U_{\Gamma}(\bar{x}),E_{\Gamma}(\bar{x}_{1},\bar{x}_{2}),Q_{\Gamma}(\bar{x}_{1},\ldots,\bar{x}_{t_{Q}})\mid
Q\in L({\mathbb{A}})\\}$

(here $\bar{x}$ and $\bar{x}_{i}$ are $n$-tuples of variables) which interpret
${\mathbb{A}}$ in ${\mathbb{B}}$ (as in the Definition 1 above). Namely,
$U_{\Gamma}$ defines in ${\mathbb{B}}$ a subset
$A_{\Gamma}=U_{\Gamma}(B^{n})\subseteq B^{n}$, $E_{\Gamma}$ defines an
equivalence relation $\sim_{\Gamma}$ on $A_{\Gamma}$, and the formulas
$Q_{\Gamma}$ define preimages of graphs for constants, functions, predicates
$Q\in L({\mathbb{A}})$ on the quotient set $A_{\Gamma}/\sim_{\Gamma}$ in such
a way that the structure $\Gamma({\mathbb{B}})=\langle
A_{\Gamma}/\sim_{\Gamma};L({\mathbb{A}})\rangle$ is isomorphic to
${\mathbb{A}}$. Note, that we interpret a constant $c\in L({\mathbb{A}})$ in
the structure $\Gamma({\mathbb{B}})$ by the $\sim_{\Gamma}$-equivalence class
of some tuple $\bar{b}_{c}\in A_{\Gamma}$ defined in ${\mathbb{B}}$ by the
formula $c_{\Gamma}(\bar{x})$. We refer to $\Gamma$ as an interpretation code
or just code. The number $n$ is called the dimension of $\Gamma$, denoted
$n=\dim\Gamma$. And we write ${\mathbb{A}}\simeq\Gamma({\mathbb{B}})$ if the
code $\Gamma$ interprets ${\mathbb{A}}$ in ${\mathbb{B}}$ as described above.
By $\mu_{\Gamma}$ we denote a surjective map $A_{\Gamma}\to A$ (here
${\mathbb{A}}=\langle A;L({\mathbb{A}})\rangle$) that gives rise to an
isomorphism $\bar{\mu}_{\Gamma}\colon\Gamma({\mathbb{B}})\to{\mathbb{A}}$. We
refer to this map $\mu_{\Gamma}$ as the _coordinate map_ of the interpretation
$\Gamma$. Sometimes we call the relation $\sim_{\Gamma}$ the _kernel_ of the
coordinate map $\mu_{\Gamma}$ and denote it by $\ker(\mu_{\Gamma})$. Finally,
notation $\mu\colon{\mathbb{B}}\rightsquigarrow{\mathbb{A}}$ means that
${\mathbb{A}}$ is interpretable in ${\mathbb{B}}$ with the coordinate map
$\mu$. We use this notation throughout the paper.

More generally, the formulas that interpret ${\mathbb{A}}$ in ${\mathbb{B}}$
may contain elements from ${\mathbb{B}}$ that are not in the language
$L({\mathbb{B}})$, i.e., some parameters, say $p_{1},\ldots,p_{k}\in B$. In
this case we assume that all the formulas from the code $\Gamma$ have a tuple
of extra variables $\bar{y}=(y_{1},\ldots,y_{k})$ for parameters in
${\mathbb{B}}$:

$\Gamma=\\{U_{\Gamma}(\bar{x},\bar{y}),E_{\Gamma}(\bar{x}_{1},\bar{x}_{2},\bar{y}),Q_{\Gamma}(\bar{x}_{1},\ldots,\bar{x}_{t_{Q}},\bar{y})\mid
Q\in L({\mathbb{A}})\\}$ (1)

so that after the assignment $y_{1}\to p_{1},\ldots,y_{k}\to p_{k}$ the code
$\Gamma$ interprets ${\mathbb{A}}$ in ${\mathbb{B}}$. In this event we write
${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\bar{p})$ (here
$\bar{p}=(p_{1},\ldots,p_{k})$), and say that ${\mathbb{A}}$ is interpretable
in ${\mathbb{B}}$ by the code $\Gamma$ with parameters $\bar{p}$. We refer to
$k$ as the parameter dimension of $\Gamma$ and denote it by
$\dim_{par}\Gamma$. In the case when $\bar{p}=\emptyset$ one gets again the
absolute interpretability. The coordinate map
$U_{\Gamma}({\mathbb{B}},\bar{p})\to{\mathbb{A}}$ we will also denote by
$\mu_{\Gamma,\bar{p}}$, if needed, and will write
$\mu_{\Gamma,\bar{p}}\colon{\mathbb{B}}\rightsquigarrow{\mathbb{A}}$ to
emphasize that ${\mathbb{A}}$ is interpretable in ${\mathbb{B}}$ with the code
$\Gamma$, parameters $\bar{p}$ and coordinate map $\mu_{\Gamma,\bar{p}}$.
Sometimes we will also write
${\mathbb{A}}\simeq_{\mu_{\Gamma,\bar{p}}}\Gamma({\mathbb{B}},\bar{p})$ (or
${\mathbb{A}}\simeq_{\mu_{\Gamma}}\Gamma({\mathbb{B}},\bar{p})$, or
${\mathbb{A}}\simeq_{\mu}\Gamma({\mathbb{B}},\bar{p})$) in this case.

Often together with a map $\mu\colon U_{\Gamma}\to A$ we will consider
$\mu^{m}\colon U^{m}_{\Gamma}\to A^{m}$ the Cartesian power of $\mu$. When it
is clear from the context we will omit $m$ in the notation $\mu^{m}$.

We will say that a subset $D\subseteq A_{\Gamma}/\sim_{\Gamma}$ is definable
in ${\mathbb{B}}$ if its full preimage in $A_{\Gamma}$ is definable in
${\mathbb{B}}$. More generally, a subset
$D\subseteq(A_{\Gamma}/\sim_{\Gamma})^{m}$ is definable in ${\mathbb{B}}$ if
its full preimage in $A_{\Gamma}^{m}$ under the natural projection
$A_{\Gamma}^{m}\to(A_{\Gamma}/\sim_{\Gamma})^{m}$ is definable in
${\mathbb{B}}$.

We say that a structure ${\mathbb{A}}$ is interpreted in a given structure
${\mathbb{B}}$ _uniformly_ with respect to a subset $D\subseteq B^{k}$ if
there is a code $\Gamma$ such that
${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\bar{p})$ for every tuple of parameters
$\bar{p}\in D$. If ${\mathbb{A}}$ is interpreted in ${\mathbb{B}}$ uniformly
with respect to a $0$-definable subset $D\subseteq B^{k}$ then we say that
${\mathbb{A}}$ is _regularly interpretable_ in ${\mathbb{B}}$ and write in
this case ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\phi)$, provided $D$ is
defined by $\phi$ in ${\mathbb{B}}$. Note that the absolute interpretability
is a particular case of the regular interpretability where the set $D$ is
empty.

We need one more uniformity condition. Absolute interpretation of
${\mathbb{A}}$ in a class of structures $\mathcal{C}$ in a language $L_{C}$ is
uniform if there is an interpretation code $\Gamma$ without parameters such
that ${\mathbb{A}}\simeq\Gamma({\mathbb{B}})$ for every structure
${\mathbb{B}}$ from $\mathcal{C}$. Similarly, one defines uniform regular
interpretation of ${\mathbb{A}}$ in $\mathcal{C}$ if there is a code $\Gamma$
and a formula $\phi$ in the language $L_{C}$ such that
${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\phi)$ for every
${\mathbb{B}}\in\mathcal{C}$.

Note that we may consider the code $\Gamma$ from (1) as a special set of
$L({\mathbb{B}})$-formulas without requiring that ${\mathbb{A}}$ is
interpretable in ${\mathbb{B}}$. Let us define the translation or reduction
$\psi\to\psi_{\Gamma}$ for formulas in the language $L({\mathbb{A}})$ into
formulas in the language $L({\mathbb{B}})$ depending on the code $\Gamma$.
Take a formula $\psi(x_{1},\ldots,x_{m})$ in $L({\mathbb{A}})$ with free
variables $x_{1},\ldots,x_{m}$. For our purposes it is enough to define the
translation on formulas $\psi$ that is obtained from unnested atomic formulas
by logical connectives and quantifires and written in prenex normal form as
usual. Here by an unnested atomic formula we understand formulas either of the
type $P(x_{1},\ldots,x_{n_{P}})$ or $f(x_{1},\ldots,x_{n_{f}})=x_{0}$,
$x_{i}=x_{j}$, $x=c$, where $P$ is a predicate symbol from $L({\mathbb{A}})$,
$f$ is a functional symbol from $L({\mathbb{A}})$, $c$ is a constant from
$L({\mathbb{A}})$ and $x_{i}$ are variables. Indeed, in general every formula
can be effectively rewritten into an equivalent formula which has the form
described above. We begin by defining a map $\psi\to\psi^{\prime}$ as follows.
Firstly, we replace every variable $x_{i}$ by an $n$-tuple of variables
$\bar{x}_{i}$, where $n=\dim\Gamma$. Then we define the map
$\psi\to\psi^{\prime}$ on unnested atomic formulas as

$P(x_{1},\ldots,x_{n_{P}})\;\;\to\;\;P_{\Gamma}(\bar{x}_{1},\ldots,\bar{x}_{n_{P}},\bar{y}),$

$f(x_{1},\ldots,x_{n_{f}})=x_{0}\;\;\to\;\;f_{\Gamma}(\bar{x}_{1},\ldots,\bar{x}_{n_{f}},\bar{x}_{0},\bar{y})$

and

$x_{i}=x_{j}\;\;\to\;\;E_{\Gamma}(\bar{x}_{i},\bar{x}_{j},\bar{y}),$
$x_{i}=c\;\;\to\;\;c_{\Gamma}(\bar{x}_{i},\bar{y})$

(here $P_{\Gamma},f_{\Gamma},c_{\Gamma},E_{\Gamma}$ are formulas from the code
$\Gamma$). Furthermore, we put

$(\psi_{1}\vee\psi_{2})^{\prime}=\psi^{\prime}_{1}\vee\psi^{\prime}_{2},\ \
(\psi_{1}\wedge\psi_{2})^{\prime}=\psi^{\prime}_{1}\wedge\psi^{\prime}_{2},$
$(\psi_{1}\to\psi_{2})^{\prime}=\psi^{\prime}_{1}\to\psi^{\prime}_{2},\ \
(\neg\psi_{1})^{\prime}=\neg\psi^{\prime}_{1}.$

Now for quantifiers we define (below $\forall\bar{x}$ denotes $\forall
x_{1}\ldots\forall x_{n}$ and $\exists\bar{x}$ denotes $\exists
x_{1}\ldots\exists x_{n}$, provided $\bar{x}=(x_{1},\ldots,x_{n})$)

$\exists
x\>\psi_{0}\;\;\to\;\;\exists\bar{x}\>(U_{\Gamma}(\bar{x},\bar{y})\wedge\psi^{\prime}_{0}),\
\ \forall
x\>\psi_{0}\;\;\to\;\;\forall\bar{x}\>(U_{\Gamma}(\bar{x},\bar{y})\to\psi^{\prime}_{0}).$

And finally, we define the $\Gamma$-translation by

$\psi(x_{1},\ldots,x_{m})\;\;\to\;\;\psi_{\Gamma}(\bar{x}_{1},\ldots,\bar{x}_{m},\bar{y})=\psi^{\prime}(\bar{x}_{1},\ldots,\bar{x}_{m},\bar{y})\wedge\bigwedge\limits_{i=1}^{m}U_{\Gamma}(\bar{x}_{i},\bar{y}).$

We use the following denotation below. Assume that ${\mathbb{A}}$ is
interpretable in ${\mathbb{B}}$ with parameters $\bar{p}$ and code $\Gamma$,
and $\mu_{\Gamma}\colon U_{\Gamma}(B^{n},\bar{p})\to A$ is the coordinate map
of the interpretation $\Gamma({\mathbb{B}},\bar{p})$, where $n=\dim\Gamma$.
For any map $\psi\to\psi^{+}$ translating formulas $\psi(x_{1},\ldots,x_{m})$
in $L({\mathbb{A}})$ into formulas
$\psi^{+}(\bar{x}_{1},\ldots,\bar{x}_{m},\bar{y})$ in $L({\mathbb{B}})$ (it
could be $\Gamma$-translation or something else) we will write

${\mathbb{A}}\models\psi\Longleftrightarrow_{\mu_{\Gamma}}{\mathbb{B}}\models\psi^{+}$

to express the following statement: for any elements $a_{1},\ldots,a_{m}\in A$
and $\bar{b}_{i}\in\mu_{\Gamma}^{-1}(a_{i})$ if
${\mathbb{A}}\models\psi(a_{1},\ldots,a_{m})$ then
${\mathbb{B}}\models\psi^{+}(\bar{b}_{1},\ldots,\bar{b}_{m},\bar{p})$, and
inversely for any $\bar{b}_{1},\ldots,\bar{b}_{m}\in B^{n}$ if
${\mathbb{B}}\models\psi^{+}(\bar{b}_{1},\ldots,\bar{b}_{m},\bar{p})$ then
there are $a_{1},\ldots,a_{m}\in A$, such that
$\bar{b}_{i}\in\mu_{\Gamma}^{-1}(a_{i})$ and
${\mathbb{A}}\models\psi(a_{1},\ldots,a_{m})$.

The following is a principal result on interpretability (in various forms it
appears in the literature, see, for example [20] or [34]).

######  Lemma 1.

Let ${\mathbb{A}}$ be interpretable in ${\mathbb{B}}$ with parameters
$\bar{p}$, so ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\bar{p})$ for some code
$\Gamma$, $n=\dim\Gamma$, and $\mu_{\Gamma}$ be the corresponding coordinate
map. Then in the notations above one has:

  1. 1)

For any formula $\psi(x_{1},\ldots,x_{m})$ of $L({\mathbb{A}})$ the
translation $\psi_{\Gamma}$ is effectively constructed, and

${\mathbb{A}}\models\psi\Longleftrightarrow_{\mu_{\Gamma}}{\mathbb{B}}\models\psi_{\Gamma}.$

In particular, if ${\mathbb{A}}$ is $0$-interpretable in ${\mathbb{B}}$, then
the formula $\psi_{\Gamma}$ does not contain parameters from ${\mathbb{B}}$.

  2. 2)

If $S\subseteq A^{m}$ is a definable with parameters subset then
$\mu_{\Gamma}^{-1}(S)\subseteq B^{m\cdot n}$ is definable with parameters.
Namely, if $S\subseteq A^{m}$ defines by a formula
$\psi(x_{1},\ldots,x_{m},a_{1},\ldots,a_{q})$, where $a_{i}\in A$, then
$\mu_{\Gamma}^{-1}(S)$ defines by a formula
$\psi_{\Gamma}(\bar{x}_{1},\ldots,\bar{x}_{m},\bar{b}_{1},\ldots,\bar{b}_{q},\bar{p})$
with $\bar{b}_{i}\in\mu_{\Gamma}^{-1}(a_{i})$. In particular, if
${\mathbb{A}}$ is $0$-interpretable in ${\mathbb{B}}$ and $S\subseteq A^{m}$
is definable (without parameters), then $\mu_{\Gamma}^{-1}(S)$ is definable
(without parameters).

  3. 3)

${\mathbb{A}}\models\psi\Longleftrightarrow_{\mu_{\Gamma}}{\mathbb{B}}\models\psi^{+},$

where $\psi(x_{1},\ldots,x_{m})$ is any $\forall\exists$-formula in
$L({\mathbb{A}})$ of the type

$\forall\>t_{1}\ldots\forall\>t_{s}\;(\bigwedge\limits_{i=1}^{r}\varphi^{i}(t_{1},\ldots,t_{s},x_{1},\ldots,x_{m})\>\longrightarrow\\\
\longrightarrow\>\exists
z_{1}\ldots\exists\>z_{q}\;\bigwedge\limits_{j=1}^{d}\psi^{j}(z_{1},\ldots,z_{q},t_{1},\ldots,t_{s},x_{1},\ldots,x_{m})\,)$

and $\psi^{+}(\bar{x}_{1},\ldots,\bar{x}_{m},\bar{y})$ is an
$L({\mathbb{B}})$-formula defined by

$(\forall\>\bar{t}_{1}\ldots\forall\>\bar{t}_{s}\;(\bigwedge\limits_{i=1}^{r}\varphi^{i}_{\Gamma}(\bar{t}_{1},\ldots,\bar{t}_{s},\bar{x}_{1},\ldots,\bar{x}_{m},\bar{y})\>\longrightarrow\\\
\longrightarrow\>\exists\bar{z}_{1}\ldots\exists\>\bar{z}_{q}\;\bigwedge\limits_{j=1}^{d}{\psi^{j}_{\Gamma}(\bar{z}_{1},\ldots,\bar{z}_{q},\bar{t}_{1},\ldots,\bar{t}_{s},\bar{x}_{1},\ldots,\bar{x}_{m},\bar{y})}\,)\,)\;\wedge\\\
\;\wedge\bigwedge\limits_{i=1}^{m}U_{\Gamma}(\bar{x}_{i},\bar{y}).$

###### Proof.

The statement 1) follows by induction on construction of $\psi$ and the
definition of the interpretation, while 2), 3) follow from 1). ∎

The result above shows that every set definable in
$\Gamma({\mathbb{B}},\bar{p})$ is definable with parameters in ${\mathbb{B}}$.
However, the converse is not true in general, i.e., a subset of
$\Gamma({\mathbb{B}},\bar{p})$ definable in ${\mathbb{B}}$ may not be
definable in $\Gamma({\mathbb{B}},\bar{p})$. Following [34] we say that
interpretation ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\bar{p})$ is _pure_ if
every subset of $\Gamma({\mathbb{B}},\bar{p})$ definable in ${\mathbb{B}}$ is
definable in $\Gamma({\mathbb{B}},\bar{p})$. We will say more on pure
interpretations in Section 2.3.

Recall that a sentence in $L$ is a formula without free variables.

######  Lemma 2.

Let ${\mathbb{A}}$ be regularly interpretable in ${\mathbb{B}}$, so
${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\phi)$ for some code $\Gamma$ and
formula $\phi(\bar{y})$. Then for every sentence $\psi$ of $L({\mathbb{A}})$
one can effectively construct a sentence $\psi_{\Gamma,\phi}$ of
$L({\mathbb{B}})$ such that

${\mathbb{A}}\models\psi\iff{\mathbb{B}}\models\psi_{\Gamma,\phi}.$

###### Proof.

Let $\psi$ be a sentence in the language $L({\mathbb{A}})$. To construct
$\psi_{\Gamma,\phi}$ take the $\Gamma$-translation $\psi_{\Gamma}(\bar{y})$
and put

$\psi_{\Gamma,\phi}=\forall\bar{y}(\phi(\bar{y})\rightarrow\psi_{\Gamma}(\bar{y})).$

Also we may take
$\psi_{\Gamma,\phi}=\exists\bar{y}(\phi(\bar{y})\rightarrow\psi_{\Gamma}(\bar{y}))$.
∎

Again, we refer to the map $\psi\to\psi_{\Gamma,\phi}$ as the _translation_ or
_reduction_ with respect to the code $\Gamma$ and formula $\phi$.

Admissibility conditions for an interpretation $\Gamma$: Let
${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\bar{p})$, where $\Gamma$ is the code
(1). Then there is a set $\mathcal{AC}_{\Gamma}$ of formulas in the language
$L({\mathbb{B}})$ in variables $\bar{y}=(y_{1},\ldots,y_{k})$ (where $k$ is
the length $|\bar{p}|$ of the tuple $\bar{p}$, $k=\dim_{par}\Gamma$), such
that for any $L({\mathbb{B}})$-structure ${\mathbb{B}}^{\prime}$ and any tuple
$\bar{q}$ of elements of ${\mathbb{B}}^{\prime}$ with $|\bar{q}|=k$ which
satisfies in ${\mathbb{B}}^{\prime}$ all of the formulas in
$\mathcal{AC}_{\Gamma}$ the code $\Gamma$ with parameters $\bar{q}$ interprets
in ${\mathbb{B}}^{\prime}$ an $L({\mathbb{A}})$-structure
$\Gamma({\mathbb{B}}^{\prime},\bar{q})$. The set
$\mathcal{AC}_{\Gamma}(\bar{y})$ is called the _admissibility conditions for
$\Gamma$_. The sentences in $\mathcal{AC}_{\Gamma}$ say that:

  1. 1.

$U_{\Gamma}({\mathbb{B}}^{\prime},\bar{q})\neq\emptyset$:

$\exists\,\bar{x}\;U_{\Gamma}(\bar{x},\bar{y});$

  2. 2.

$E_{\Gamma}(\bar{x}_{1},\bar{x}_{2},\bar{q})$ defines an equivalence relation
$\sim$ on $U_{\Gamma}({\mathbb{B}}^{\prime},\bar{q})$:

$\forall\,\bar{x}\;(U_{\Gamma}(\bar{x},\bar{y})\,\longrightarrow\,E_{\Gamma}(\bar{x},\bar{x},\bar{y})),$
$\forall\,\bar{x}_{1}\forall\,\bar{x}_{2}\;(U_{\Gamma}(\bar{x}_{1},\bar{y})\wedge
U_{\Gamma}(\bar{x}_{2},\bar{y})\wedge
E_{\Gamma}(\bar{x}_{1},\bar{x}_{2},\bar{y})\,\longrightarrow\,E_{\Gamma}(\bar{x}_{2},\bar{x}_{1},\bar{y})),$
$\forall\,\bar{x}_{1}\forall\,\bar{x}_{2}\forall\,\bar{x}_{3}\;(U_{\Gamma}(\bar{x}_{1},\bar{y})\wedge
U_{\Gamma}(\bar{x}_{2},\bar{y})\wedge U_{\Gamma}(\bar{x}_{3},\bar{y})\wedge\\\
\wedge\,E_{\Gamma}(\bar{x}_{1},\bar{x}_{2},\bar{y})\wedge
E_{\Gamma}(\bar{x}_{2},\bar{x}_{3},\bar{y})\,\longrightarrow\,E_{\Gamma}(\bar{x}_{1},\bar{x}_{3},\bar{y}));$

  3. 3.

Every constant $c\in L({\mathbb{A}})$ has a correct interpretation on
$U_{\Gamma}({\mathbb{B}}^{\prime},\bar{q})/\sim$:

$\exists\,\bar{x}\;(U_{\Gamma}(\bar{x},\bar{y})\wedge
c_{\Gamma}(\bar{x},\bar{y})),$
$\forall\,\bar{x}_{1}\forall\,\bar{x}_{2}\;(U_{\Gamma}(\bar{x}_{1},\bar{y})\wedge
U_{\Gamma}(\bar{x}_{2},\bar{y})\,\wedge\,c_{\Gamma}(\bar{x}_{1},\bar{y})\,\wedge\,c_{\Gamma}(\bar{x}_{2},\bar{y})\,\longrightarrow\\\
\longrightarrow\,E_{\Gamma}(\bar{x}_{1},\bar{x}_{2},\bar{y}));$

  4. 4.

Every function $f\in L({\mathbb{A}})$ has a correct interpretation on
$U_{\Gamma}({\mathbb{B}}^{\prime},\bar{q})/\sim$:

$\forall\,\bar{x}_{1}\ldots\forall\,\bar{x}_{n_{f}}\;(\bigwedge\limits_{i=1}^{n_{f}}U_{\Gamma}(\bar{x}_{i},\bar{y})\,\longrightarrow\,\exists\,\bar{z}\;(U_{\Gamma}(\bar{z},\bar{y})\wedge
f_{\Gamma}(\bar{x}_{1},\ldots,\bar{x}_{n_{f}},\bar{z},\bar{y}))),$
$\forall\,\bar{x}_{1}\ldots\forall\,\bar{x}_{n_{f}}\forall\,\bar{x}_{1}^{\ast}\ldots\forall\,\bar{x}_{n_{f}}^{\ast}\forall\,\bar{z}\>\forall\,\bar{z}^{\ast}\;(U_{\Gamma}(\bar{z},\bar{y})\,\wedge\,U_{\Gamma}(\bar{z}^{\ast},\bar{y})\,\wedge\\\
\wedge\,\bigwedge\limits_{i=1}^{n_{f}}(U_{\Gamma}(\bar{x}_{i},\bar{y})\,\wedge\,U_{\Gamma}(\bar{x}_{i}^{\ast},\bar{y})\,\wedge\,E_{\Gamma}(\bar{x}_{i},\bar{x}_{i}^{\ast},\bar{y}))\,\wedge\,\\\
\wedge\,f_{\Gamma}(\bar{x}_{1},\ldots,\bar{x}_{n_{f}},\bar{z},\bar{y})\,\wedge\,f_{\Gamma}(\bar{x}_{1}^{\ast},\ldots,\bar{x}_{n_{f}}^{\ast},\bar{z}^{\ast},\bar{y})\,\longrightarrow\,E_{\Gamma}(\bar{z},\bar{z}^{\ast},\bar{y}));$

  5. 5.

Every predicate $P\in L({\mathbb{A}})$ has a correct interpretation on
$U_{\Gamma}({\mathbb{B}}^{\prime},\bar{q})/\sim$:

$\forall\,\bar{x}_{1}\ldots\forall\,\bar{x}_{n_{P}}\forall\,\bar{x}_{1}^{\ast}\ldots\forall\,\bar{x}_{n_{P}}^{\ast}\\\
(\bigwedge\limits_{i=1}^{n_{P}}(U_{\Gamma}(\bar{x}_{i},\bar{y})\,\wedge\,U_{\Gamma}(\bar{x}_{i}^{\ast},\bar{y})\,\wedge\,E_{\Gamma}(\bar{x}_{i},\bar{x}_{i}^{\ast},\bar{y}))\,\longrightarrow\,\\\
\,\longrightarrow\,(P_{\Gamma}(\bar{x}_{1},\ldots,\bar{x}_{n_{P}},\bar{y})\longleftrightarrow
P_{\Gamma}(\bar{x}_{1}^{\ast},\ldots,\bar{x}_{n_{P}}^{\ast},\bar{y}))).$

It is clear that if the language $L({\mathbb{A}})$ contains at least one
constant $c$ then the item 1 above can be omitted. In this way
${\mathbb{B}}^{\prime}\models\mathcal{AC}_{\Gamma}(\bar{q})$ if and only if
$L({\mathbb{A}})$-structure $\Gamma({\mathbb{B}}^{\prime},\bar{q})$ is well-
defined and it is interpreted in ${\mathbb{B}}$. (However, we cannot assert
that $\Gamma({\mathbb{B}}^{\prime},\bar{q})\simeq{\mathbb{A}}$!)

Note since the language $L({\mathbb{A}})$ is finite then the set
$\mathcal{AC}_{\Gamma}$ is also finite. In this case one can take a single
formula
$\Theta_{\Gamma}(\bar{y})=\bigwedge\\{\theta(\bar{y})\mid\theta(\bar{y})\in\mathcal{AC}_{\Gamma}\\}$,
such that for any $L({\mathbb{B}})$-structure ${\mathbb{B}}^{\prime}$ one has
${\mathbb{B}}^{\prime}\models\Theta_{\Gamma}(\bar{q})$ if and only if
$\Gamma({\mathbb{B}}^{\prime},\bar{q})$ is well-defined.

Now, let ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\phi)$ be a regular
interpretation of ${\mathbb{A}}$ in ${\mathbb{B}}$, i.e.,
${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\bar{p})$ for any tuple
$\bar{p}\in\phi({\mathbb{B}})$. Consider the set
$\mathcal{AC}_{\Gamma}=\\{\theta_{i}(\bar{y})\mid i\in I\\}$ of admissible
conditions. Then for every $i\in I$ the sentence

$\theta_{i,\phi}=\forall\,\bar{y}\>(\phi(\bar{y})\,\to\,\theta_{i}(\bar{y}))$

holds in ${\mathbb{B}}$. Let
$\mathcal{AC}_{\Gamma,\phi}=\\{\theta_{i,\phi}\mid i\in
I\\}\cup\\{\exists\bar{y}\,\phi(\bar{y})\\}$. Then for every
$L({\mathbb{B}})$-structure ${\mathbb{B}}^{\prime}$ if
${\mathbb{B}}^{\prime}\models\mathcal{AC}_{\Gamma,\phi}$ then the set
$\phi({\mathbb{B}}^{\prime})$ is not empty, and for every tuple
$q\in\phi({\mathbb{B}}^{\prime})$ the $L({\mathbb{A}})$-structure
$\Gamma({\mathbb{B}}^{\prime},\bar{q})$ is well-defined. Again, since the
language $L({\mathbb{A}})$ by our assumptions is finite then the set of
sentences $\mathcal{AC}_{\Gamma,\phi}$ is also finite. In this case the set of
admissible conditions can be described by a single sentence
$\Theta_{\Gamma,\phi}$ — the conjunction of the sentences in
$\mathcal{AC}_{\Gamma,\phi}$. We will use this in our study of quasi-finitely
axiomatizable structures.

Composition of interpretations: Let ${\mathbb{A}},{\mathbb{B}}$ and
${\mathbb{C}}$ be algebraic structures. To find out how the composition of
interpretations $\mu_{\Gamma}\colon{\mathbb{B}}\rightsquigarrow{\mathbb{A}}$
and $\mu_{\Delta}\colon{\mathbb{C}}\rightsquigarrow{\mathbb{B}}$ works, we
define previously the composition of codes. Suppose that $\Gamma$ and $\Delta$
are codes, such that $\Gamma$ is a set of $L({\mathbb{B}})$-formulas as in (1)
and $\Delta$ is a set of $L({\mathbb{C}})$-formulas:

$\Delta=\\{U_{\Delta}(\bar{x},\bar{z}),E_{\Delta}(\bar{x}_{1},\bar{x}_{2},\bar{z}),Q_{\Delta}(\bar{x}_{1},\ldots,\bar{x}_{t_{Q}},\bar{z})\mid
Q\in L({\mathbb{B}})\\},$

where $|\bar{x}|=|\bar{x}_{i}|=\dim\Delta$, $|\bar{z}|=\dim_{par}\Delta$. Then
the composition of codes $\Gamma$ and $\Delta$ is the code

$\Gamma\circ\Delta=\\{U_{\Gamma\circ\Delta},E_{\Gamma\circ\Delta},Q_{\Gamma\circ\Delta}\mid
Q\in
L({\mathbb{A}})\\}=\\{(U_{\Gamma})_{\Delta},(E_{\Gamma})_{\Delta},(Q_{\Gamma})_{\Delta}\mid
Q\in L({\mathbb{A}})\\}.$

Note that

$\displaystyle\dim\Gamma\circ\Delta=\dim\Gamma\cdot\dim\Delta,$
$\displaystyle\dim_{par}\Gamma\circ\Delta=\dim_{par}\Gamma\cdot\dim\Delta+\dim_{par}\Delta.$

The following are two important technical results about the transitivity of
interpretations, that we use throughout the paper.

######  Lemma 3.

Let ${\mathbb{A}},{\mathbb{B}}$ and ${\mathbb{C}}$ be algebraic structures.
Then the following hold:

  * 1)

If ${\mathbb{A}}$ is interpretable with parameters (absolutely interpretable)
in ${\mathbb{B}}$ and ${\mathbb{B}}$ is interpretable with parameters
(absolutely interpretable) in ${\mathbb{C}}$, then ${\mathbb{A}}$ is
interpretable with parameters (absolutely interpretable) in ${\mathbb{C}}$. In
more detail, if
$\mu_{\Gamma,\bar{p}}\colon{\mathbb{B}}\rightsquigarrow{\mathbb{A}}$ and
$\mu_{\Delta,\bar{q}}\colon{\mathbb{C}}\rightsquigarrow{\mathbb{B}}$ then
${\mathbb{A}}\simeq\Gamma\circ\Delta({\mathbb{C}},\bar{p}^{\ast})$, where
$\bar{p}^{\ast}=(\bar{p}_{0},\bar{q})$ with
$\bar{p}_{0}\in\mu_{\Delta,\bar{q}}^{-1}(\bar{p})$ (and the
$L({\mathbb{A}})$-structure $\Gamma\circ\Delta({\mathbb{C}},\bar{p}^{\ast})$
does not depend on the choice of
$\bar{p}_{0}\in\mu_{\Delta,\bar{q}}^{-1}(\bar{p})$).

  * 2)

If ${\mathbb{A}}$ is regularly interpretable in ${\mathbb{B}}$ and
${\mathbb{B}}$ is regularly interpretable in ${\mathbb{C}}$, then
${\mathbb{A}}$ is regularly interpretable in ${\mathbb{C}}$. In more detail,
if ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\phi)$ and
${\mathbb{B}}\simeq\Delta({\mathbb{C}},\psi)$ then
${\mathbb{A}}\simeq\Gamma\circ\Delta({\mathbb{C}},\phi^{\ast})$, where
$\phi^{\ast}=\phi_{\Delta}\wedge\psi$. Moreover,
$\bar{p}^{\ast}\in\phi^{\ast}({\mathbb{C}})$ if and only if there exist
$\bar{p}\in\phi({\mathbb{B}})$, $\bar{q}\in\psi({\mathbb{C}})$ (and
consequently there exists an interpretation
${\mathbb{B}}\simeq_{\mu_{\Delta,\bar{q}}}\Delta({\mathbb{C}},\bar{q})$) and
$\bar{p}_{0}\in\mu^{-1}_{\Delta,\bar{q}}(\bar{p})$ such that
$\bar{p}^{\ast}=(\bar{p}_{0},\bar{q})$.

###### Proof.

1) By Lemma 1 for any tuples $\bar{b},\bar{b}_{1},\ldots,\bar{b}_{i},\ldots,$
of length $n=\dim\Gamma$ of elements of ${\mathbb{B}}$, any their preimages
$\bar{c},\bar{c}_{1},\ldots,\bar{c}_{i},\ldots,$ under $\mu_{\Delta,\bar{q}}$
(that are tuples of length $m=\dim\Gamma\cdot\dim\Delta$ from ${\mathbb{C}}$)
and any $\bar{p}_{0}\in\mu_{\Delta,\bar{q}}^{-1}(\bar{p})$ of length
$|p|\cdot\dim\Delta$ of elements of ${\mathbb{C}}$ one has

${\mathbb{B}}\models U_{\Gamma}(\bar{b},\bar{p})\iff{\mathbb{C}}\models
U_{\Gamma\circ\Delta}(\bar{c},\bar{p}_{0},\bar{q});$ (2) ${\mathbb{B}}\models
E_{\Gamma}(\bar{b}_{1},\bar{b}_{2},\bar{p})\iff{\mathbb{C}}\models
E_{\Gamma\circ\Delta}(\bar{c}_{1},\bar{c}_{2},\bar{p}_{0},\bar{q});$ (3)
${\mathbb{B}}\models
Q_{\Gamma}(\bar{b}_{1},\ldots,\bar{b}_{t_{Q}},\bar{p})\iff{\mathbb{C}}\models
Q_{\Gamma\circ\Delta}(\bar{c}_{1},\ldots,\bar{c}_{t_{Q}},\bar{p}_{0},\bar{q}).$
(4)

Here if $\bar{c}_{i}\in C^{m}$ and the right parts of (2), (3), (4) are true,
then $\bar{c}_{i}\in\mu_{\Delta,\bar{q}}^{-1}(B^{n})$ and the left parts are
true as well.

Furthermore, all formulas from the admissibility conditions
$\mathcal{AC}_{\Gamma}$ are equivalent to $\forall\exists$-formulas of the
type that in Lemma 1. Since
${\mathbb{B}}\models\mathcal{AC}_{\Gamma}(\bar{p})$, so Lemma 1 proves that
the algebraic structure ${\mathbb{C}}$ satisfies the admissibility conditions
$\mathcal{AC}_{\Gamma\circ\Delta}$ on parameters
$\bar{p}^{\ast}=(\bar{p}_{0},\bar{q})$. Thus $L({\mathbb{A}})$-structure
$\Gamma\circ\Delta({\mathbb{C}},\bar{p}^{\ast})$ is well-defined and it does
not depend on the choice of
$\bar{p}_{0}\in\mu_{\Delta,\bar{q}}^{-1}(\bar{p})$.

Consider the map $\mu_{\Gamma\circ\Delta}\colon
U_{\Gamma\circ\Delta}({\mathbb{C}},\bar{p}^{\ast})\to A$,
$\mu_{\Gamma\circ\Delta}=\mu_{\Gamma,\bar{p}}\circ\mu_{\Delta,\bar{q}}$. As
$\mu_{\Gamma,\bar{p}}$ is surjective and (2) holds, $\mu_{\Gamma\circ\Delta}$
is well-defined and also surjective. Because $\bar{\mu}_{\Gamma,\bar{p}}\colon
U_{\Gamma}({\mathbb{B}},\bar{p})/\sim_{\Gamma}\,\to A$ is bijective and (3)
holds, $\bar{\mu}_{\Gamma\circ\Delta}\colon
U_{\Gamma\circ\Delta}({\mathbb{C}},\bar{p}^{\ast})/\sim_{\Gamma\circ\Delta}\,\to
A$ is well-defined and bijective too. Finally, since
$\bar{\mu}_{\Gamma,\bar{p}}$ is an $L({\mathbb{A}})$-isomorphism and due to
(4)
$\bar{\mu}_{\Gamma\circ\Delta}\colon\Gamma\circ\Delta({\mathbb{C}},\bar{p}^{\ast})\to{\mathbb{A}}$
is an $L({\mathbb{A}})$-isomorphism as well. Thereby, ${\mathbb{A}}$ is
interpretable in ${\mathbb{C}}$ with the code $\Gamma\circ\Delta$ and
parameters $\bar{p}^{\ast}$. It is clear that if $\bar{p}=\emptyset$ and
$\bar{q}=\emptyset$ then $\bar{p}^{\ast}=\emptyset$.

2) Suppose now that ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\phi)$ and
${\mathbb{B}}\simeq\Delta({\mathbb{C}},\psi)$. Take any tuples
$\bar{p}\in\phi({\mathbb{B}})$ and $\bar{q}\in\psi({\mathbb{C}})$. Then there
exist interpretations
${\mathbb{A}}\simeq_{\mu_{\Gamma,\bar{p}}}\Gamma({\mathbb{B}},\bar{p})$ and
${\mathbb{B}}\simeq_{\mu_{\Delta,\bar{q}}}\Delta({\mathbb{C}},\bar{q})$. Take
any $\bar{p}_{0}\in\mu^{-1}_{\Delta,\bar{q}}(\bar{p})$ and put
$\bar{p}^{\ast}=(\bar{p}_{0},\bar{q})$. We obtain that there exists an
interpretation
${\mathbb{A}}\simeq\Gamma\circ\Delta({\mathbb{C}},\bar{p}^{\ast})$, moreover,
by Lemma 1 parameters $\bar{p}^{\ast}$ belong to the definable set
$\phi^{\ast}({\mathbb{C}})$, $\phi^{\ast}=\phi_{\Delta}\,\wedge\,\psi$.
Conversely, if we take any $\bar{p}^{\ast}\in\phi^{\ast}({\mathbb{C}})$ and
write $\bar{p}^{\ast}=(\bar{p}_{0},\bar{q})$, then
$\bar{q}\in\psi({\mathbb{C}})$ and there exists an interpretation
${\mathbb{B}}\simeq_{\mu_{\Delta,\bar{q}}}\Delta({\mathbb{C}},\bar{q})$. And
since $\bar{p}_{0}\in\phi_{\Delta}({\mathbb{C}},\bar{q})$, then by Lemma 1
there exists $\bar{p}\in\phi({\mathbb{B}})$ with
$\bar{p}_{0}\in\mu^{-1}_{\Delta,\bar{q}}(\bar{p})$. Thus for any
$\bar{p}^{\ast}\in\phi^{\ast}({\mathbb{C}})$ there exists an interpretation
${\mathbb{A}}\simeq\Gamma\circ\Delta({\mathbb{C}},\bar{p}^{\ast})$, i.e.,
${\mathbb{A}}\simeq\Gamma\circ\Delta({\mathbb{C}},\phi^{\ast})$. ∎

###  2.2 Properties preserved under interpretations

Interpretations provide a useful tool to show that algebraic structures
satisfy some particular properties, that are inherited under interpretations.
We say that a property $P$ is _preserved (or inherited) under interpretations_
if for any structures ${\mathbb{A}}$ and ${\mathbb{B}}$ such that
${\mathbb{A}}$ is interpreted in ${\mathbb{B}}$ if $P$ holds in ${\mathbb{B}}$
then $P$ holds in ${\mathbb{A}}$. Some of such properties $P$ are preserved
only under absolute or regular interpretations, while others are preserved
under interpretations with parameters. In this section we mention some of
these properties that we use in the sequel.

######  Lemma 4.

  * The following holds:

  * 1)

Let ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\phi)$ for some code $\Gamma$ and a
formula $\phi$, i.e., ${\mathbb{A}}$ is regularly interpretable in
${\mathbb{B}}$. Then if the first-order theory $Th({\mathbb{B}})$ is decidable
then $Th({\mathbb{A}})$ is also decidable.

  * 2)

Let ${\mathbb{A}}_{1},{\mathbb{A}}_{2}$ be $L({\mathbb{A}})$-structures and
${\mathbb{B}}_{1},{\mathbb{B}}_{2}$ be $L({\mathbb{B}})$-structures. If
${\mathbb{A}}_{i}=\Gamma({\mathbb{B}}_{i},\phi)$, $i=1,2$, for some code
$\Gamma$ and a formula $\phi$, then ${\mathbb{B}}_{1}\equiv{\mathbb{B}}_{2}$
implies ${\mathbb{A}}_{1}\equiv{\mathbb{A}}_{2}$.

  * 3)

If ${\mathbb{A}}=\Gamma({\mathbb{B}},\bar{p})$ and
${\mathbb{B}}\preceq{\mathbb{B}}_{1}$ is an elementary extension of
${\mathbb{B}}$ then ${\mathbb{B}}_{1}$ satisfies the admissibility conditions
$\mathcal{AC}_{\Gamma}$ on the tuple $\bar{p}$, $\Gamma({\mathbb{B}},\bar{p})$
is a substructure of ${\mathbb{A}}_{1}=\Gamma({\mathbb{B}}_{1},\bar{p})$ and
${\mathbb{A}}\preceq{\mathbb{A}}_{1}$ is an elementary extension of
${\mathbb{A}}$.

###### Proof.

If ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\phi)$ for some code $\Gamma$ and a
formula $\phi$, then by Lemma 2 there is an algorithm that for any sentence
$\psi$ in the language $L({\mathbb{A}})$ constructs a sentence
$\psi_{\Gamma,\phi}$ in the language $L({\mathbb{B}})$ such that

${\mathbb{A}}\models\psi\Longleftrightarrow{\mathbb{B}}\models\psi_{\Gamma,\phi}.$

Therefore, if $Th({\mathbb{B}})$ is decidable then $Th({\mathbb{A}})$ is
decidable. This proves 1).

Almost the same argument works for 2), here one only need to notice that the
sentence $\psi_{\Gamma,\phi}$ depends only on $\psi,\Gamma$, and $\phi$.

3) Since ${\mathbb{B}}_{1}$ is an elementary extension of ${\mathbb{B}}$ the
admissibility condition $\mathcal{AC}_{\Gamma}$ holds in ${\mathbb{B}}_{1}$ on
the tuple $\bar{p}$. Hence $(\Gamma,\bar{p})$ interprets in ${\mathbb{B}}_{1}$
an $L({\mathbb{A}})$-structure $\Gamma({\mathbb{B}}_{1},\bar{p})$, which has
$\Gamma({\mathbb{B}},\bar{p})$ as a substructure. Let
$\psi(x_{1},\ldots,x_{m})$ be a formula in $L({\mathbb{A}})$ and
$\psi_{\Gamma}(\bar{x}_{1},\ldots,\bar{x}_{m},\bar{y})$ its
$\Gamma$-translation. Now take a tuple of elements
$\bar{a}=(a_{1},\ldots,a_{m})$ from the structure
$\Gamma({\mathbb{B}},\bar{p})$. We intend to show that $\psi(\bar{a})$ holds
in $\Gamma({\mathbb{B}},\bar{p})$ if and only if it holds in
$\Gamma({\mathbb{B}}_{1},\bar{p})$. Consider a tuple
$\bar{b}=(b_{1},\ldots,b_{m})$, where $b_{i}$ is a tuple from
$A_{\Gamma}=U_{\Gamma}(B^{n})$ such that $a_{i}$ is the
$\sim_{\Gamma}$-equivalence class of $b_{i}$, $i=1,\ldots,m$. Then by Lemma 1
$\psi(\bar{a})$ holds in ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\bar{p})$ if
and only if $\psi_{\Gamma}(\bar{b},\bar{p})$ holds in ${\mathbb{B}}$. Since
${\mathbb{B}}\preceq{\mathbb{B}}_{1}$ the formula
$\psi_{\Gamma}(\bar{b},\bar{p})$ holds in ${\mathbb{B}}$ if and only if it
holds in ${\mathbb{B}}_{1}$. Then, again by Lemma 1
$\psi_{\Gamma}(\bar{b},\bar{p})$ holds in ${\mathbb{B}}_{1}$ if and only if
$\psi(\bar{a})$ holds in $\Gamma({\mathbb{B}}_{1},\bar{p})$. Hence
$\Gamma({\mathbb{B}}_{1},\bar{p})$ is an elementary extension of
$\Gamma({\mathbb{B}},\bar{p})$, as claimed. This proves the lemma. ∎

We also mention the following basic result. Let ${\mathbb{N}}$ be the set of
natural numbers. Then ${\mathbb{N}}=\langle{\mathbb{N}};+,\cdot,0,1\rangle$ is
called the _arithmetic_ or the _standard arithmetic_. The Gödel first
incompleteness theorem (more precisely, the Gödel’s argument there) implies
that the first-order theory $Th({\mathbb{N}})$ of ${\mathbb{N}}$ is
undecidable. We state this in the form of the following result.

######  Lemma 5.

[54, 16] If the arithmetic ${\mathbb{N}}$ is interpretable (with parameters)
in a structure ${\mathbb{B}}$ then the first-order theory $Th({\mathbb{B}})$
is undecidable.

Note that ${\mathbb{N}}$ is $0$-interpretable in the ring of integers
${\mathbb{Z}}=\langle{\mathbb{Z}};+,\cdot,0,1\rangle$. Indeed, by Lagrange’s
Four Squares Theorem every integer is a sum of four squares, so the formula

$\exists x_{1}\exists x_{2}\exists x_{3}\exists
x_{4}(y=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2})$

defines ${\mathbb{N}}$ in ${\mathbb{Z}}$. Hence, if ${\mathbb{Z}}$ is
interpretable (with parameters) in ${\mathbb{A}}$ then $Th({\mathbb{A}})$ is
undecidable. The following theorem, due to J. Robinson, shows this result can
be extended to arbitrary rings of algebraic integers or algebraic number
fields.

######  Theorem 1.

[45] The following holds:

  * 1)

The ring ${\mathbb{Z}}$ is $0$-definable in any ring of algebraic integers
$\mathcal{O}$.

  * 2)

The ring of algebraic integers $\mathcal{O}$ is $0$-definable in its field of
fractions.

  * 3)

It follows from 1) and 2) that the ring ${\mathbb{Z}}$ is $0$-definable in any
algebraic number field $F$.

Scanlon extended the result above as follows.

######  Theorem 2.

[51] The ring ${\mathbb{Z}}$ is interpretable in any finitely generated
infinite field $F$.

######  Corollary 1.

If any of the rings $\mathcal{O}$ or $F$ from Theorems 1 and 2 are
interpretable in a structure ${\mathbb{A}}$ then the first-order theory
$Th({\mathbb{A}})$ is undecidable.

At present, there are known many rings, groups, and monoids $R$ where the
arithmetic ${\mathbb{N}}$ is interpretable (see, for instance, the Sections
6-14 below), so for all of them Corollary 1 holds when $\mathcal{O}$ or $F$ is
replaced by $R$. However, the rings $\mathcal{O}$ and $F$ above most often
appear as interpretable in other structures, especially, the rings of
algebraic integers $\mathcal{O}$ typically occur via interpretations in
finitely-generated groups (see, for example, [17, 18, 19], where the rings
$\mathcal{O}$ are interpreted in groups and rings by means of equations). In
this direction we would like to mention the following general result.

######  Theorem 3 (Noskov [40]).

Let $G$ be a finitely generated soluble group. Then if $G$ is non-virtually
abelian then ${\mathbb{Z}}$ is interpretable in $G$.

There are many properties that are preserved under interpretations:
$\lambda$-stability, being $\lambda$-saturation, $\omega$-categoricity,
independence property, and finite Morley rank, to mention a few (for the proof
about Morley rank we refer to [9], the others are rather easy to prove using
the translation $\phi\to\phi_{\Gamma}$ above).

###  2.3 Bi-interpretability

In this section we discuss a very strong version of mutual interpretability of
two structures, so-called bi-interpretability.

######  Definition 2.

Two algebraic structures ${\mathbb{A}}$ and ${\mathbb{B}}$ are called bi-
interpretable (with parameters) in each other if the following conditions
hold:

  * 1)

${\mathbb{A}}$ and ${\mathbb{B}}$ are interpretable (with parameters) in each
other, so ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\bar{p})$ and
${\mathbb{B}}\simeq\Delta({\mathbb{A}},\bar{q})$ for some codes $\Gamma$ and
$\Delta$ and tuples of parameters $\bar{p},\bar{q}$. By transitivity
${\mathbb{A}}$, as well as ${\mathbb{B}}$, is interpretable (with parameters)
in itself, so
${\mathbb{A}}\simeq\Gamma\circ\Delta({\mathbb{A}},\bar{p}^{\ast})$ and
${\mathbb{B}}\simeq\Delta\circ\Gamma({\mathbb{B}},\bar{q}^{\ast})$, where
$\circ$ denotes composition of interpretations and $\bar{p}^{\ast}$,
$\bar{q}^{\ast}$ the corresponding parameters.

  * 2)

There is a formula $\theta_{\mathbb{A}}(\bar{u},x,\bar{s})$ in the language
$L({\mathbb{A}})$ such that $\theta_{\mathbb{A}}(\bar{u},x,\bar{p}^{\ast})$
defines in ${\mathbb{A}}$ an isomorphism
$\bar{\mu}_{\mathbb{A}}\colon\Gamma\circ\Delta({\mathbb{A}},\bar{p}^{\ast})\to{\mathbb{A}}$
(more precisely, it defines the coordinate map $\mu_{\mathbb{A}}\colon
A_{\Gamma\circ\Delta}\to A$). Similarly, there is a formula
$\theta_{\mathbb{B}}(\bar{v},x,\bar{t})$ in the language $L({\mathbb{B}})$
such that $\theta_{\mathbb{B}}(\bar{v},x,\bar{q}^{\ast})$ defines in
${\mathbb{B}}$ an isomorphism
$\bar{\mu}_{\mathbb{B}}\colon\Delta\circ\Gamma({\mathbb{B}},\bar{q}^{\ast})\to{\mathbb{B}}$
(more precisely, it defines the coordinate map $\mu_{\mathbb{B}}\colon
B_{\Delta\circ\Gamma}\to B$).

Here
$|\bar{p}^{\ast}|=\dim_{par}\Gamma\circ\Delta=|\bar{p}|\cdot\dim\Delta+|\bar{q}|$,
$|\bar{q}^{\ast}|=\dim_{par}\Delta\circ\Gamma=|\bar{q}|\cdot\dim\Gamma+|\bar{p}|$
and
$|\bar{u}|=|\bar{v}|=\dim\Delta\circ\Gamma=\dim\Gamma\circ\Delta=\dim\Gamma\cdot\dim\Delta$.

######  Remark 1.

On the definition of bi-interpretability:

  * a)

In the Definition 2 the parameters $\bar{p}^{\ast}$ and $\bar{q}^{\ast}$ can
be explicitly expressed from $\bar{p}$ and $\bar{q}$ using the coordinate maps
$\mu_{\Gamma}\colon A_{\Gamma}\to A$ and $\mu_{\Delta}\colon B_{\Delta}\to B$
of the interpretations ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\bar{p})$ and
${\mathbb{B}}\simeq\Delta({\mathbb{A}},\bar{q})$. Indeed, following the
construction of the compositions $\Gamma\circ\Delta$ and $\Delta\circ\Gamma$
one can see that $\bar{p}^{\ast}=(\bar{p}_{0},\bar{q})$ and
$\bar{q}^{\ast}=(\bar{q}_{0},\bar{p})$, where
$\bar{p}_{0}\in\mu^{-1}_{\Delta}(\bar{p})$ and
$\bar{q}_{0}\in\mu^{-1}_{\Gamma}(\bar{q})$ (see Lemma 3).

  * b)

Note that the tuples $\bar{p}_{0},\bar{q}_{0}$ (and consequently
$\bar{p}^{\ast},\bar{q}^{\ast}$) from above are not unique, they are defined
up to the equivalence relations $\sim_{\Delta}$ and $\sim_{\Gamma}$.
Nevertheless, all these tuples define the same interpretations
$\Gamma\circ\Delta({\mathbb{A}},\bar{p}^{\ast})$ and
$\Delta\circ\Gamma({\mathbb{B}},\bar{q}^{\ast})$ (see Lemma 3).

  * c)

The requirement in 2) that the formula
$\theta_{\mathbb{A}}(\bar{u},x,\bar{p}^{\ast})$ defines in ${\mathbb{A}}$ a
coordinate map $\mu_{\mathbb{A}}\colon A_{\Gamma\circ\Delta}\to A$ can be
strengthened to the requirement that it defines the composition
$\mu_{\Gamma\circ\Delta}=\mu_{\Gamma}\circ\mu_{\Delta}$. Indeed, we can
redefine the isomorphism
$\bar{\mu}_{\Gamma}\colon\Gamma({\mathbb{B}},\bar{p})\to{\mathbb{A}}$ by
taking $\alpha\circ\bar{\mu}_{\Gamma}$, where
$\alpha=\bar{\mu}_{\mathbb{A}}\circ\bar{\mu}^{-1}_{\Gamma\circ\Delta}$ is the
automorphism of ${\mathbb{A}}$. So we can always assume, adjusting
$\bar{\mu}_{\Gamma}$ if necessary, that
$\theta_{\mathbb{A}}(\bar{u},x,\bar{p}^{\ast})$ defines in ${\mathbb{A}}$ the
isomorphism $\bar{\mu}_{\Gamma\circ\Delta}$.

In the case when the formula $\theta_{\mathbb{A}}$ above defines the
coordinate map $\mu_{\Gamma\circ\Delta}\colon A_{\Gamma\circ\Delta}\to A$, we
will refer to the isomorphism
$\bar{\mu}_{\Gamma}\colon\Gamma({\mathbb{B}},\bar{p})\to{\mathbb{A}}$ and its
coordinate map $\mu_{\Gamma}\colon A_{\Gamma}\to A$ as compatible with the
formula $\theta_{\mathbb{A}}(\bar{u},x,\bar{p}^{\ast})$. Item c) in Remark 1
tells that such isomorphism always exists.

Usually in examples of bi-interpretable algebraic structures one has the
coordinate map $\mu_{\Gamma}$ compatible with the formula
$\theta_{\mathbb{A}}$ and simultaneously the coordinate map $\mu_{\Delta}$
compatible with the formula $\theta_{\mathbb{B}}$. In this instance the
formula $\theta_{\mathbb{A}}$ defines the composition
$\mu_{\Gamma}\circ\mu_{\Delta}$ and $\theta_{\mathbb{B}}$ defines
$\mu_{\Delta}\circ\mu_{\Gamma}$.

######  Lemma 6.

Let ${\mathbb{A}}$ and ${\mathbb{B}}$ be bi-interpretable (with parameters) in
each other with respect to interpretations
${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\bar{p})$ and
${\mathbb{B}}\simeq\Delta({\mathbb{A}},\bar{q})$ for some codes $\Gamma$ and
$\Delta$ and tuples of parameters $\bar{p},\bar{q}$. Then the following holds:

  * 1)

There is a formula $\sigma_{\mathbb{A}}(\bar{y},\bar{z})$ in the language
$L({\mathbb{A}})$ with $|\bar{y}|=|\bar{p}|\cdot\dim\Delta$,
$|\bar{z}|=|\bar{q}|$, which defines in ${\mathbb{A}}$ a non-empty set of
tuples $D_{\sigma_{\mathbb{A}}}$ such that in the notation in Definition 2 and
Remark 1 $\bar{p}^{\ast}=(\bar{p}_{0},\bar{q})\in D_{\sigma_{\mathbb{A}}}$ and
for any tuple $\bar{a}=(\bar{a}_{0},\bar{c})$ over ${\mathbb{A}}$ with
$|\bar{a}_{0}|=|\bar{y}|,|\bar{c}|=|\bar{z}|$ if $\bar{a}\in
D_{\sigma_{\mathbb{A}}}$ then:

    * –

the $L({\mathbb{A}})$-structure $\Delta({\mathbb{A}},\bar{c})$ is well-defined
and $\bar{a}_{0}\in\Delta({\mathbb{A}},\bar{c})$ (more precisely,
$\bar{a}_{0}\in U_{\Delta}({\mathbb{A}},\bar{c})$);

    * –

the $L({\mathbb{A}})$-structure $\Gamma\circ\Delta({\mathbb{A}},\bar{a})$ is
well-defined;

    * –

the formula $\theta_{\mathbb{A}}(\bar{u},x,\bar{a})$ defines in ${\mathbb{A}}$
an isomorphism
$\bar{\mu}\colon\Gamma\circ\Delta({\mathbb{A}},\bar{a})\to{\mathbb{A}}$ (more
precisely, a coordinate map $\mu\colon
U_{\Gamma\circ\Delta}({\mathbb{A}},\bar{a})\to A$).

  * 2)

Similarly, there is a formula $\sigma_{\mathbb{B}}(\bar{s},\bar{t})$ in the
language $L({\mathbb{B}})$ with $|\bar{s}|=|\bar{q}|\cdot\dim\Gamma$,
$|\bar{t}|=|\bar{p}|$, which defines in ${\mathbb{B}}$ a non-empty set of
tuples $D_{\sigma_{\mathbb{B}}}$ such that
$\bar{q}^{\ast}=(\bar{q}_{0},\bar{p})$ is in $D_{\sigma_{\mathbb{B}}}$ and for
any tuple $\bar{b}=(\bar{b}_{0},\bar{d})\in D_{\sigma_{\mathbb{B}}}$,
$|\bar{b}_{0}|=|\bar{s}|,|\bar{d}|=|\bar{t}|$, the
$L({\mathbb{B}})$-structures $\Gamma({\mathbb{B}},\bar{d})$ and
$\Delta\circ\Gamma({\mathbb{B}},\bar{b})$ are well-defined,
$\bar{b}_{0}\in\Gamma({\mathbb{B}},\bar{d})$, and the formula
$\theta_{\mathbb{B}}(\bar{v},x,\bar{b})$ defines an isomorphism
$\Delta\circ\Gamma({\mathbb{B}},\bar{b})\to{\mathbb{B}}$.

###### Proof.

We use notation from Definition 2 and Remark 1.

It suffices to prove 1). To construct the required formula
$\sigma_{\mathbb{A}}(\bar{y},\bar{z})$ we will use the formulas
$\Theta_{\Delta}(\bar{z})$ (that says that $\bar{c}$ satisfies in
${\mathbb{A}}$ the admissibility conditions $\mathcal{AC}_{\Delta}(\bar{z})$)
and $\Theta_{\Gamma\circ\Delta}(\bar{y},\bar{z})$ (that says that $\bar{a}$
satisfies in ${\mathbb{A}}$ the admissibility conditions
$\mathcal{AC}_{\Gamma\circ\Delta}(\bar{y},\bar{z})$). Thus
${\mathbb{A}}\models\Theta_{\Delta}(\bar{c})\wedge\Theta_{\Gamma\circ\Delta}(\bar{a})$
if and only if the $L({\mathbb{A}})$-structures $\Delta({\mathbb{A}},\bar{c})$
and $\Gamma\circ\Delta({\mathbb{A}},\bar{a})$ are well-defined, in
particularly, when $\bar{a}=\bar{p}^{\ast}$. Note that if
$\bar{a}\in\Theta_{\Gamma\circ\Delta}({\mathbb{A}})$ then there exists
$\bar{x}$ such that ${\mathcal{A}}\models
U_{\Gamma\circ\Delta}(\bar{x},\bar{a})$, and since $U_{\Gamma\circ\Delta}$ is
the $\Delta$-translation of the formula $U_{\Gamma}$, so $\bar{a}_{0}\in
U_{\Delta}({\mathbb{A}},\bar{c})$ (see the algorithm of $\Delta$-translation
for details).

Assume now that the $L({\mathbb{A}})$-structure
$\Gamma\circ\Delta({\mathbb{A}},\bar{a})$ is well-defined. The formula
$\theta_{\mathbb{A}}(\bar{u},x,\bar{a})$ defines in ${\mathbb{A}}$ an
isomorphism $\Gamma\circ\Delta({\mathbb{A}},\bar{a})\to{\mathbb{A}}$ if
$\bar{a}=\bar{p}^{\ast}$. We are going to impose restrictions on $\bar{a}$
such that $\theta_{\mathbb{A}}(\bar{u},x,\bar{a})$ defines an isomorphism for
all $\bar{a}\in D_{\sigma_{\mathbb{A}}}$. Let us write the following formulas
to say that

  1. (i)

a morphism $\mu\colon U_{\Gamma\circ\Delta}({\mathbb{A}},\bar{a})\to A$
exists:

$\theta_{1}(\bar{y},\bar{z})\>=\>\forall\,\bar{u}\;(U_{\Gamma\circ\Delta}(\bar{u},\bar{y},\bar{z})\>\longleftrightarrow\>\exists\,x\;\theta_{\mathbb{A}}(\bar{u},x,\bar{y},\bar{z}));$

  2. (ii)

the morphism $\mu$ is well-defined and the morphism $\bar{\mu}$ is injective:

$\theta_{2}(\bar{y},\bar{z})\>=\>\forall\,\bar{u}_{1}\>\forall\,\bar{u}_{2}\>\forall\,x_{1}\>\forall\,x_{2}\;(U_{\Gamma\circ\Delta}(\bar{u}_{1},\bar{y},\bar{z})\,\wedge\,U_{\Gamma\circ\Delta}(\bar{u}_{2},\bar{y},\bar{z})\,\wedge\\\
\wedge\,\theta_{\mathbb{A}}(\bar{u}_{1},x_{1},\bar{y},\bar{z})\,\wedge\,\theta_{\mathbb{A}}(\bar{u}_{2},x_{2},\bar{y},\bar{z})\>\longrightarrow\\\
\longrightarrow\>(E_{\Gamma\circ\Delta}(\bar{u}_{1},\bar{u}_{2},\bar{y},\bar{z})\,\longleftrightarrow\,(x_{1}=x_{2})\,)\,);$

  3. (iii)

the morphism $\mu$ is surjective:

$\theta_{3}(\bar{y},\bar{z})\>=\>\forall\,x\>\exists\,\bar{u}\;\theta_{\mathbb{A}}(\bar{u},x,\bar{y},\bar{z});$

  4. (iv)

the morphism $\mu$ preserves constants form $L({\mathbb{A}})$: for each $c\in
L({\mathbb{A}})$

$\theta_{c}(\bar{y},\bar{z})\>=\>\forall\,\bar{u}\;(c_{\Gamma\circ\Delta}(\bar{u},\bar{y},\bar{z})\,\longrightarrow\,\theta_{\mathbb{A}}(\bar{u},c,\bar{y},\bar{z}));$

  5. (v)

the morphism $\mu$ preserves functions form $L({\mathbb{A}})$: for each $f\in
L({\mathbb{A}})$

$\theta_{f}(\bar{y},\bar{z})\>=\>\forall\,\bar{u}_{0}\>\forall\,\bar{u}_{1}\ldots\forall\,\bar{u}_{n_{f}}\>\forall\,x_{0}\>\forall\,x_{1}\ldots\forall\,x_{n_{f}}\;(\bigwedge\limits_{i=0}^{n_{f}}\theta_{\mathbb{A}}(\bar{u}_{i},x_{i},\bar{y},\bar{z})\,\wedge\\\
\wedge\,f_{\Gamma\circ\Delta}(\bar{u}_{1},\ldots,\bar{u}_{n_{f}},\bar{u}_{0},\bar{y},\bar{z})\,\longrightarrow\,(f(x_{1},\ldots,x_{n_{f}})=x_{0})\,);$

  6. (vi)

the morphism $\mu$ preserves predicates form $L({\mathbb{A}})$: for each $P\in
L({\mathbb{A}})$

$\theta_{P}(\bar{y},\bar{z})\>=\>\forall\,\bar{u}_{1}\ldots\forall\,\bar{u}_{n_{P}}\>\forall\,x_{1}\ldots\forall\,x_{n_{P}}\;(\bigwedge\limits_{i=1}^{n_{P}}\theta_{\mathbb{A}}(\bar{u}_{i},x_{i},\bar{y},\bar{z})\,\longrightarrow\\\
\longrightarrow\,(P_{\Gamma\circ\Delta}(\bar{u}_{1},\ldots,\bar{u}_{n_{P}},\bar{y},\bar{z})\,\longleftrightarrow\,P(x_{1},\ldots,x_{n_{P}})\,)\,).$

Now, to write down the formula $\sigma_{\mathbb{A}}(\bar{y},\bar{z})$ from 1)
it suffices to take conjunction of the formulas $\Theta_{\Delta}(\bar{z})$,
$\Theta_{\Gamma\circ\Delta}(\bar{y},\bar{z})$, $\theta_{1}(\bar{y},\bar{z})$,
$\theta_{2}(\bar{y},\bar{z})$, $\theta_{3}(\bar{y},\bar{z})$,
$\theta_{c}(\bar{y},\bar{z})$, $\theta_{f}(\bar{y},\bar{z})$,
$\theta_{P}(\bar{y},\bar{z})$ for all $c,f,P\in L({\mathbb{A}})$. This proves
1) and the lemma. ∎

######  Corollary 2.

Let ${\mathbb{A}}$ and ${\mathbb{B}}$ be bi-interpretable (with parameters) in
each other with respect to interpretations
${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\bar{p})$ and
${\mathbb{B}}\simeq\Delta({\mathbb{A}},\bar{q})$ for some codes $\Gamma$ and
$\Delta$ and tuples of parameters $\bar{p},\bar{q}$. Then in the notation of
Lemma 6 the interpretation $\Gamma\circ\Delta$ together with the formula
$\sigma_{\mathbb{A}}$ regularly interprets ${\mathbb{A}}$ in ${\mathbb{A}}$,
i.e., ${\mathbb{A}}\simeq\Gamma\circ\Delta({\mathbb{A}},\sigma_{\mathbb{A}})$.
Furthermore, for any tuples $\bar{a}_{1}$ and $\bar{a}_{2}$ which satisfy
$\sigma_{\mathbb{A}}$ in ${\mathbb{A}}$ the formula
$\Theta_{\bar{a}_{1},\bar{a}_{2}}(\bar{u}_{1},\bar{u}_{2})=\exists\,x\>(\theta_{\mathbb{A}}(\bar{u}_{1},x,\bar{a}_{1})\wedge\theta_{\mathbb{A}}(\bar{u}_{2},x,\bar{a}_{2}))$
defines an isomorphism
$\lambda_{\bar{a}_{1},\bar{a}_{2}}\colon\Gamma\circ\Delta({\mathbb{A}},\bar{a}_{1})\to\Gamma\circ\Delta({\mathbb{A}},\bar{a}_{2})$
such that
${\lambda_{\bar{a}_{1},\bar{a}_{2}}(\bar{u}_{1}/\sim_{(\Gamma\circ\Delta,\bar{a}_{1})})}=\bar{u}_{2}/\sim_{(\Gamma\circ\Delta,\bar{a}_{2})}$.
A similar statement holds for the interpretation $\Delta\circ\Gamma$.

Algebraic structures ${\mathbb{A}}$ and ${\mathbb{B}}$ are called $0$-bi-
interpretable or absolulutely bi-interpretable in each other if in the
definition above the tuples of parameters $\bar{p}$ and $\bar{q}$ are empty.

Unfortunately, $0$-bi-interpretability is rather rare. Indeed, the following
result puts quite strong restrictions on such structures.

######  Lemma 7.

[20, Section 5.4, Ex. 8 (b)] If ${\mathbb{A}}$ and ${\mathbb{B}}$ are $0$-bi-
interpretable in each other then their groups of automorphisms are isomorphic.

Fortunately, there is a notion of regular bi-interpretability, which is less
restrictive, occurs more often, and which enjoys many properties of $0$-bi-
interpretability.

######  Definition 3.

Two algebraic structures ${\mathbb{A}}$ and ${\mathbb{B}}$ are called
regularly bi-interpretable in each other if the following conditions hold:

  * 1)

${\mathbb{A}}$ and ${\mathbb{B}}$ are regularly interpretable in each other,
so ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\phi)$ and
${\mathbb{B}}\simeq\Delta({\mathbb{A}},\psi)$ for some codes $\Gamma$ and
$\Delta$ and the corresponding formulas $\phi,\psi$ (without parameters). By
transitivity ${\mathbb{A}}$, as well as ${\mathbb{B}}$, is regularly
interpretable in itself, so
${\mathbb{A}}\simeq\Gamma\circ\Delta({\mathbb{A}},\phi^{\ast})$ and
${\mathbb{B}}\simeq\Delta\circ\Gamma({\mathbb{B}},\psi^{\ast})$, where $\circ$
denotes composition of interpretations and
$\phi^{\ast}=\phi_{\Delta}\,\wedge\,\psi$,
$\psi^{\ast}=\psi_{\Gamma}\,\wedge\,\phi$ (see Lemma 3).

  * 2)

There is a formula $\theta_{\mathbb{A}}(\bar{u},x,\bar{s})$ in the language of
${\mathbb{A}}$ such that for every tuple $\bar{p}^{\ast}$ satisfying
$\phi^{\ast}(\bar{s})$ in ${\mathbb{A}}$ the formula
$\theta_{\mathbb{A}}(\bar{u},x,\bar{p}^{\ast})$ defines in ${\mathbb{A}}$ an
isomorphism
$\bar{\mu}_{{\mathbb{A}},\bar{p}^{\ast}}\colon\Gamma\circ\Delta({\mathbb{A}},\bar{p}^{\ast})\to{\mathbb{A}}$
and there is a formula $\theta_{\mathbb{B}}(\bar{v},x,\bar{t})$ in the
language of ${\mathbb{B}}$ such that for every tuple $\bar{q}^{\ast}$
satisfying $\psi^{\ast}(\bar{t})$ in ${\mathbb{B}}$ the formula
$\theta_{\mathbb{B}}(\bar{v},x,\bar{q}^{\ast})$ defines in ${\mathbb{B}}$ an
isomorphism
$\bar{\mu}_{{\mathbb{B}},\bar{q}^{\ast}}\colon\Delta\circ\Gamma({\mathbb{B}},\bar{q}^{\ast})\to{\mathbb{B}}$.

Here
$|\bar{s}|=\dim_{par}\Gamma\circ\Delta=\dim_{par}\Gamma\cdot\dim\Delta+\dim_{par}\Delta$,
$|\bar{t}|=\dim_{par}\Delta\circ\Gamma=\dim_{par}\Delta\cdot\dim\Gamma+\dim_{par}\Gamma$
and
$|\bar{u}|=|\bar{v}|=\dim\Delta\circ\Gamma=\dim\Gamma\circ\Delta=\dim\Gamma\cdot\dim\Delta$.

Suppose that in the notation above for any tuple
$\bar{q}\in\psi({\mathbb{A}})$ the coordinate map $\mu_{\Delta,\bar{q}}\colon
B_{\Delta,\bar{q}}\to B$ is fixed, and then for any tuples
$\bar{p}\in\phi({\mathbb{B}})$ and
$\bar{p}_{0}\in\mu^{-1}_{\Delta,\bar{q}}(\bar{p})$ the coordinate map
$\mu_{\Gamma,\bar{p}^{\ast}}\colon A_{\Gamma,\bar{p}}\to A$ that is compatible
with the formula $\theta_{\mathbb{A}}(\bar{u},x,\bar{p}^{\ast})$ is also
fixed, where $\bar{p}^{\ast}=(\bar{p}_{0},\bar{q})$. In this case we will say
that the coordinate maps $\mu_{\Gamma,\bar{p}^{\ast}}$ (and isomorphisms
$\bar{\mu}_{\Gamma,\bar{p}^{\ast}}$) are uniformly compatible with the formula
$\theta_{\mathbb{A}}$. In our applications in most cases one has precisely
that the isomorphisms $\bar{\mu}_{\Gamma,\bar{p}^{\ast}}$ are uniformly
compatible with the formula $\theta_{\mathbb{A}}$.

######  Lemma 8.

Let ${\mathbb{A}}$ and ${\mathbb{B}}$ be structures bi-interpretable with
parameters with respect to interpretations
${\mathbb{A}}\simeq_{\mu_{\Gamma}}\Gamma({\mathbb{B}},\bar{p})$ and
${\mathbb{B}}\simeq_{\mu_{\Delta}}\Delta({\mathbb{A}},\bar{q})$ for some codes
$\Gamma$ and $\Delta$ and tuples of parameters $\bar{p},\bar{q}$. Suppose that
the coordinate map $\mu_{\Gamma}$ is compatible with the formula
$\theta_{\mathbb{A}}(\bar{u},x,\bar{p}^{\ast})$ defining an isomorphism
$\Gamma\circ\Delta({\mathbb{A}},\bar{p}^{\ast})\to{\mathbb{A}}$,
$\bar{p}^{\ast}=(\bar{p}_{0},\bar{q})$,
$\bar{p}_{0}\in\mu^{-1}_{\Delta}(\bar{p})$. Then for any subset $S\subseteq
A^{m}$ one has that $S$ is definable with parameters in ${\mathbb{A}}$ if and
only if $\mu_{\Gamma}^{-1}(S)$ is definable with parameters in ${\mathbb{B}}$.

Moreover, if ${\mathbb{A}}$ and ${\mathbb{B}}$ are absolutely bi-interpretable
in each other then $S\subseteq A^{m}$ is definable in ${\mathbb{A}}$ without
parameters if and only if $\mu_{\Gamma}^{-1}(S)$ is definable in
${\mathbb{B}}$ without parameters.

###### Proof.

In the proof we use notation from Definition 2 and Remark 1.

Suppose that $S$ is definable with parameters in ${\mathbb{A}}$ then by Lemma
1 it is definable with parameters in ${\mathbb{B}}$. In particularly, if
$\bar{p}=\emptyset$ and $S$ is definable without parameters then
$\mu^{-1}_{\Gamma}(S)$ is definable without parameters.

To show the converse suppose that $\mu_{\Gamma}^{-1}(S)$ is definable in
${\mathbb{B}}$ by a formula $\Sigma(\bar{z},\bar{r})$ with parameters
$\bar{r}$ from ${\mathbb{B}}$, $|\bar{z}|=m\cdot\dim\Gamma$. By Lemma 1

${\mathbb{B}}\models\Sigma(\bar{b},\bar{r})\Longleftrightarrow{\mathbb{A}}\models\Sigma_{\Delta}(\mu_{\Delta}^{-1}(\bar{b}),\bar{r}_{0},\bar{q}),\quad\bar{r}_{0}\in\mu_{\Delta}^{-1}(\bar{r}).$

Here by $\mu_{\Delta}^{-1}(\bar{b})$ in the formula above we mean any element
from the set $\mu_{\Delta}^{-1}(\bar{b})$. This shows that the set
$S_{\bar{q}}=\mu_{\Delta}^{-1}(\mu_{\Gamma}^{-1}(S))$, $S_{\bar{q}}\subseteq
A^{m\cdot\dim\Gamma\cdot\dim\Delta}$, is definable in ${\mathbb{A}}$ by the
formula $\psi_{\Delta}$ and parameters $(\bar{r}_{0},\bar{q})$. Hence a tuple
$\bar{a}$ of elements from ${\mathbb{A}}$ belongs to $S$ if and only if there
is a tuple $\bar{c}$ in $S_{\bar{q}}$ such that
$\bar{a}=\mu_{\Gamma}\circ\mu_{\Delta}(\bar{c})$. Since the set $S_{\bar{q}}$
and the map $\mu_{\Gamma}\circ\mu_{\Delta}$ are definable in ${\mathbb{A}}$ it
follows that the set $S$ is also definable with parameters in ${\mathbb{A}}$
by the formula

$\sigma(x_{1},\ldots,x_{m},\bar{p}_{0},\bar{r}_{0},\bar{q})\;=\;\exists\,\bar{c}_{1}\ldots\exists\,\bar{c}_{m}\;(\bigwedge\limits_{i=1}^{m}\theta_{\mathbb{A}}(\bar{c}_{i},x_{i},\bar{p}^{\ast})\>\wedge\>\Sigma_{\Delta}(\bar{c}_{1},\ldots,\bar{c}_{m},\bar{r}_{0},\bar{q}))$

with parameters $(\bar{p}_{0},\bar{r}_{0},\bar{q})$. Here
$|\bar{c}_{i}|=\dim\Gamma\circ\Delta$.

At the same time, if $\bar{p}=\bar{q}=\bar{r}=\emptyset$ then $S$ is definable
without parameters. This proves the lemma. ∎

######  Lemma 9.

Let two structures ${\mathbb{A}}$ and ${\mathbb{B}}$ are regularly bi-
interpretable in each other, so ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\phi)$
and ${\mathbb{B}}\simeq\Delta({\mathbb{A}},\psi)$, while
$\theta_{\mathbb{A}}(\bar{u},x,\bar{s})$ is an $L({\mathbb{A}})$-formula, such
that $\theta_{\mathbb{A}}(\bar{u},x,\bar{p}^{\ast})$ defines an isomorphisms
$\Gamma\circ\Delta({\mathbb{A}},\bar{p}^{\ast})\to{\mathbb{A}}$ for all tuples
$\bar{p}^{\ast}\in\phi^{\ast}({\mathbb{A}})$,
$\phi^{\ast}=\phi_{\Delta}\,\wedge\,\psi$. Suppose also that the coordinate
maps $\mu_{\Gamma,\bar{p}^{\ast}}$ are uniformly compatible with the formula
$\theta_{\mathbb{A}}$. Take an arbitrary subset $S\subseteq A^{m}$, such that
for all tuples $\bar{p}^{\ast}\in\phi^{\ast}({\mathbb{A}})$ the preimages
$\mu^{-1}_{\Gamma,\bar{p}^{\ast}}(S)$ coincide, denote these preimages by
$\mu^{-1}_{\Gamma}(S)$. Then the set $S$ is $0$-definable in ${\mathbb{A}}$ if
and only if $\mu^{-1}_{\Gamma}(S)$ is $0$-definable in ${\mathbb{B}}$.

###### Proof.

If $S\subseteq A^{m}$ is $0$-definable, i.e., $S=\varphi(A^{m})$ for an
$L({\mathbb{A}})$-formula $\varphi$, then by Lemma 1
$\mu^{-1}_{\Gamma}(S)=\Sigma({\mathbb{B}})$, where

$\Sigma(\bar{z})=\exists\,\bar{y}\;(\phi(\bar{y})\,\wedge\,\varphi_{\Gamma}(\bar{z},\bar{y})),$

and $|\bar{z}|=m\cdot\dim\Gamma$. Thus $\mu^{-1}_{\Gamma}(S)$ is
$0$-definable.

To prove converse statement suppose that $\mu^{-1}_{\Gamma}(S)$ is definable
by an $L({\mathbb{B}})$-formula $\Sigma(\bar{z})$ without parameters with
$|\bar{z}|=m\cdot\dim\Gamma$. And consider the $L({\mathbb{A}})$-formula

$\varphi(x_{1},\ldots,x_{m})\;=\;\forall\,\bar{q}\>\forall\,\bar{p}_{0}\;(\psi(\bar{q})\,\wedge\,\phi_{\Delta}(\bar{p}_{0},\bar{q})\,\longrightarrow\\\
\longrightarrow\,\exists\,\bar{c}_{1}\ldots\exists\,\bar{c}_{m}\;(\bigwedge\limits_{i=1}^{m}\theta_{\mathbb{A}}(\bar{c}_{i},x_{i},\bar{p}_{0},\bar{q})\>\wedge\>\Sigma_{\Delta}(\bar{c}_{1},\ldots,\bar{c}_{m},\bar{q})\,)\,),$

where $|\bar{q}|=\dim_{par}\Delta$,
$|\bar{p}_{0}|=\dim_{par}\Gamma\cdot\dim\Delta$,
$|\bar{c}_{i}|=\dim\Gamma\circ\Delta$. We state that
$S=\varphi({\mathbb{A}})$. Indeed, let $\bar{a}$ be a tuple form $S$. For any
tuple $\bar{p}^{\ast}\in\phi^{\ast}({\mathbb{A}})$ one gets that the set
$\mu^{-1}_{\Gamma,\bar{p}^{\ast}}(S)$ is defined by $\Sigma(\bar{z})$,
therefore, by Lemma 8 ${\mathbb{A}}\models\sigma(\bar{a},\bar{p}^{\ast})$,
where $\sigma$ is the formula from the proof of Lemma 8 with
$\bar{r}_{0}=\emptyset$. Thus $\bar{a}$ is in the set $\varphi({\mathbb{A}})$.
Conversely, let $\bar{a}\in\varphi({\mathbb{A}})$. Chose a tuple
$\bar{p}^{\ast}=(\bar{p}_{0},\bar{q})\in\phi^{\ast}({\mathbb{A}})$. We obtain
that ${\mathbb{A}}\models\sigma(\bar{a},\bar{p}^{\ast})$, and by Lemma 8,
$\bar{a}$ is in $S$, as claimed. ∎

The following is a particular case of Lemma 9.

######  Corollary 3.

Let two structures ${\mathbb{A}}$ and ${\mathbb{B}}$ are regularly bi-
interpretable in each other in such a way that
${\mathbb{B}}\simeq\Delta({\mathbb{A}},\psi)$ and
${\mathbb{A}}\simeq\Gamma({\mathbb{B}})$ is an absolute interpretation. Assume
that $\mu_{\Gamma}$ is the coordinate map of the interpretation
${\mathbb{A}}\simeq\Gamma({\mathbb{B}})$ such that it is compatible with the
formula $\theta_{\mathbb{A}}(\bar{u},x,\bar{q})$ for all
$\bar{q}\in\psi({\mathbb{A}})$. For any set $S\subseteq A^{m}$ if the set
$\mu_{\Gamma}^{-1}(S)$ is $0$-definable in ${\mathbb{B}}$, then the set $S$ is
$0$-definable in ${\mathbb{A}}$.

######  Remark 2.

The type of regular bi-interpretability of ${\mathbb{A}}$ and ${\mathbb{B}}$
that is described in Corollary 3 will be useful in the sequel. We sometimes
refer to it as _half-absolute bi-interpretability_ of ${\mathbb{A}}$ in
${\mathbb{B}}$.

##  3 Weak second order logic

In this section we describe the weak second order logic (WSOL) over an
arbitrary structure ${\mathbb{A}}$. Informally, this logic allows one to use
three different types of variables, one is for elements in ${\mathbb{A}}$,
another — for finite subsets of ${\mathbb{A}}$, and the third one — for
natural numbers. Also, one is allowed to use all the functions and predicates
from the language of ${\mathbb{A}}$, the “membership” predicate $\in$ for
finite subsets of ${\mathbb{A}}$, and addition and multiplication for natural
numbers. Otherwise, the formulas are built like in the usual first-order
languages. This logic is much more powerful than the standard first-order
logic in ${\mathbb{A}}$, indeed, everything which is describable in finitary
set theory over ${\mathbb{A}}$ can be described in the weak second order logic
over ${\mathbb{A}}$.

Below, we describe WSOL over ${\mathbb{A}}$ in three different but equivalent
ways, each one will be useful for different purposes. Firstly, we introduce
two larger structures, containing ${\mathbb{A}}$, the superstructure
$HF({\mathbb{A}})$ of hereditary finite sets over ${\mathbb{A}}$, and the list
superstructures $S({\mathbb{N}},{\mathbb{A}})$. We show that they are bi-
interpretable in each other, so they have essentially the same expressive
power. The crucial result here is that the expressive power of the first-order
theory of $HF({\mathbb{A}})$ (or $S({\mathbb{N}},{\mathbb{A}})$) is the same
as the power of WSOL over ${\mathbb{A}}$. Secondly, we describe a particular
fragment $L_{WSOL}$ of the logic $L_{\omega_{1},\omega}$ that is equivalent
over ${\mathbb{A}}$ to the weak second order logic. More precisely, in this
fragment formulas with free variables $x_{1},\ldots,x_{n}$ express the same
things in ${\mathbb{A}}$ as formulas in the language of $HF({\mathbb{A}})$ or
$S({\mathbb{N}},{\mathbb{A}})$ which have only free variables
$x_{1},\ldots,x_{n}$ that run over ${\mathbb{A}}$. This description will be
used to show that some properties of ${\mathbb{A}}$ are definable in the WSOL.

###  3.1 Hereditary finite and list superstructures

For a set $A$ let $Pf(A)$ be the set of all finite subsets of $A$. Now we
define by induction the set $HF(A)$ of hereditary finite sets over $A$;

  * •

$HF_{0}(A)=A$,

  * •

$HF_{n+1}(A)=HF_{n}(A)\cup Pf(HF_{n}(A))$,

  * •

$HF(A)=\bigcup_{n\in\omega}HF_{n}(A).$

For a structure ${\mathbb{A}}=\langle A;L\rangle$ define a new first-order
structure as follows. Firstly, one replaces all operations in $L$ by the
corresponding predicates (the graphs of the operations) on $A$, so one may
assume from the beginning that $L$ consists only of predicate symbols.
Secondly, consider the structure

$HF({\mathbb{A}})=\langle HF(A);L,P_{A},\in\rangle,$

where $L$ is defined on the subset $A$, $P_{A}$ defines $A$ in $HF(A)$, and
$\in$ is the membership predicate on $HF(A)$. Then everything that can be
expressed in the weak second order logic in ${\mathbb{A}}$ can be expressed in
the first-order logic in $HF({\mathbb{A}})$, and vice versa. The structure
$HF({\mathbb{A}})$ appears naturally in the weak second order logic, the
theory of admissible sets, and $\Sigma$-definability, — we refer to [5, 6, 14,
15] for details.

There is another structure, termed the list superstructure
$S({\mathbb{A}},{\mathbb{N}})$ over ${\mathbb{A}}$ whose first-order theory
has the same expressive power as the weak second order logic over
${\mathbb{A}}$ and which is more convenient for us to use in this paper. To
introduce $S({\mathbb{A}},{\mathbb{N}})$ we need a few definitions. Let $S(A)$
be the set of all finite sequences (tuples) of elements from $A$. For a
structure ${\mathbb{A}}=\langle A;L\rangle$ define in the notation above a new
two-sorted structure $S({\mathbb{A}})$ as follows:

$S({\mathbb{A}})=\langle{\mathbb{A}},S(A);\frown,\in\rangle,$

where $\frown$ is the binary operation of concatenation of two sequences from
$S(A)$ and $a\in s$ for $a\in A,s\in S(A)$ is interpreted as $a$ being a
component of the tuple $s$. As customary in the formal language theory we will
denote the concatenation $s\frown t$ of two sequences $s$ and $t$ by $st$.

Now, the structure $S({\mathbb{A}},{\mathbb{N}})$ is defined as the three-
sorted structure

$S({\mathbb{A}},{\mathbb{N}})=\langle{\mathbb{A}},S(A),{\mathbb{N}};t(s,i,a),l(s),\frown,\in\rangle,$

where ${\mathbb{N}}=\langle N,+,\cdot,0,1\rangle$ is the standard arithmetic,
$l\colon S(A)\to N$ is the length function, i.e., $l(s)$ is the length $n$ of
a sequence $s=(s_{1},\ldots,s_{n})\in S(A)$, and $t(x,y,z)$ is a predicate on
$S(A)\times N\times A$ such that $t(s,i,a)$ holds in
$S({\mathbb{A}},{\mathbb{N}})$ if and only if $s=(s_{1},\ldots,s_{n})\in
S(A),i\in N,1\leq i\leq n$, and $a=s_{i}\in A$. Observe, that in this case the
predicate $\in$ is $0$-definable in $S({\mathbb{A}},{\mathbb{N}})$ (with the
use of $t(s,i,a)$), so sometimes we omit it from the language.

In the following lemma and theorem we summarize some known results [11] about
the structures $HF({\mathbb{A}}),S({\mathbb{A}})$, and
$S({\mathbb{A}},{\mathbb{N}})$.

######  Lemma 10.

[11] Let ${\mathbb{A}}$ be a structure which has at least two elements. Then
the following structures are $0$-interpretable in each other:

$S({\mathbb{A}})\rightsquigarrow S({\mathbb{A}},{\mathbb{N}})\rightsquigarrow
HF({\mathbb{A}})\rightsquigarrow S({\mathbb{A}},{\mathbb{N}})\rightsquigarrow
S({\mathbb{A}})$

uniformly in ${\mathbb{A}}$.

Using ideas from the proof of Lemma 10 above from [11] one can prove the
following result.

######  Theorem 4.

Let ${\mathbb{A}}$ be a structure that has at least two elements. Then
$HF({\mathbb{A}})$ and $S({\mathbb{A}},{\mathbb{N}})$ are absolutely bi-
interpretable in each other.

###### Proof.

$HF(\\{1,\ldots,N\\})$ is isomorphic to
$({\mathbb{N}},\\{1,\ldots,N\\},\in_{N})$, where $m\in_{N}n$ if and only if
$n>N$ and the coefficient of $2^{m}$ in the binary representation of $n-N$ is
1.

We now define the interpretation $\Gamma\colon HF({\mathbb{A}})\rightarrow
S({\mathbb{A}},{\mathbb{N}})$. A pair of elements $(S,m)$ of
$S({\mathbb{A}},{\mathbb{N}})$ will represent an element $a$ of
$HF({\mathbb{A}})$ if and only if there exists a natural number $N$ and
elements $a_{1},\ldots,a_{N}$ of $A$ such that $S=a_{1},\ldots,a_{N}$ and the
isomorphism from $({\mathbb{N}},\\{1,\ldots,N\\},\in_{N})$ to
$HF(\\{a_{1},\ldots,a_{N}\\})$ sending $i$ to $a_{i}$ for any
$i\in\\{1,\ldots,N\\}$ sends $m$ to $a$.

We say that a finite sequence of natural numbers $v_{0},\ldots,v_{k}$ is an
$N$-construction for a natural number $n$ if and only if $v_{k}=n$ and for any
natural number $i\leq k$, for any $m\in{\mathbb{N}}$ such that
$m\in_{N}v_{i}$, there is a natural number $j<i$ such that $m=v_{i}$. Let
$\sim$ be a binary relation defined by $(S,m)\sim(S^{\prime},m^{\prime})$ if
and only if there exists an $\ell(S)$ construction of $m$,
$v_{0},\ldots,v_{k}$, and an $\ell(S^{\prime})$-construction of $m^{\prime}$
with the same length $w_{0},\ldots,w_{k}$ , such that for any $i,j\leq k$,
$v_{1}\in_{\ell(S)}v_{j}$ if and only if $w_{1}\in_{\ell(S^{\prime})}w_{j}$
and for any $i\leq k$ such that $v_{i}\leq\ell(S),v_{i}=w_{i}=0$, or $v_{i}$
and $w_{i}$ are different from $0$ and $t(S,v_{i}-1,a)$,
$t(S^{\prime},w_{i}-1,a)$ for some $a\in A$. Let $R$ be the binary relation
defined by $(S,m)R(S^{\prime},m^{\prime})$ if and only if there exists $n$
such that $(S,m)\sim(S^{\prime},m^{\prime})$ and
$n\in_{\ell(S^{\prime})}m^{\prime}.$

A finite sequence of natural numbers $v_{0},\ldots,v_{k}$ can be coded by the
number ${p_{0}}^{v_{0}+1}\cdots{p_{k}}^{v_{k}+1}$ (where $p_{0},\ldots,p_{k}$
is the increasing sequence of prime numbers). The set of representatives for
finite sequences of natural numbers and the relation “$k$ is the $m$’th
element of the sequence coded by $n$”, are definable in ${\mathbb{N}}$,
therefore $\sim$ and $R$ are definable in $S({\mathbb{A}},{\mathbb{N}})$. The
set $B=\\{(S,m)|0<m\leq\ell(S)\\}$ of representatives for the set $A$ in
$HF({\mathbb{A}})$ is definable in $S({\mathbb{A}},{\mathbb{N}})$.

Define $a=\bar{t}(S,m)$ if and only if $t(S,m,a).$ Let $L^{\prime}$ be the
interpretation of $L$ in $B$ defined as follows: for any $k$-ary predicate $P$
of $L$, if $P$ is interpreted in $M$ by the relation $\tau$, $P$ is
interpreted in $B$ by the relation $\tau^{\prime}$ defined by
$\tau^{\prime}((S_{1},m_{1}),\ldots,(S_{k},m_{k}))$ if and only if
$\tau(\bar{t}(S_{1},m_{1}-1),\ldots,\bar{t}(S_{k},m_{k}-1)).$

By construction, $\sim$ is an equivalence relation compatible with
$B,L^{\prime},R$, and $HF({\mathbb{A}})$ is isomorphic to
$S({\mathbb{A}},{\mathbb{N}})=(B,S(A)\times{\mathbb{N}},L^{\prime},R)/\sim$.

Combining the constructed interpretation $\Gamma$ of $HF({\mathbb{A}})$ in
$S({\mathbb{A}},{\mathbb{N}})$ with the interpretation of
$S({\mathbb{A}},{\mathbb{N}})$ in $HF({\mathbb{A}})$ given in [11, Section
II.2] which we denote by $\Delta$, one can easily verify that the isomorphisms
${\mathcal{S}}({\mathbb{A}},{\mathbb{N}})\to(\Gamma\circ\Delta)S({\mathbb{A}},{\mathbb{N}})$
and $HF({\mathbb{A}})\to(\Delta\circ\Gamma)HF({\mathbb{A}})$ are definable.

∎

Now we define one more superstructure over ${\mathbb{A}}$, which we call the
_superstructure of finite binary predicates_ over ${\mathbb{A}}$.

Let $A$ be a set. By a finite binary predicate over $A$ we mean a finite
subset of pairs of elements from $A$. By $FBP(A)$ we denote the set of all
finite predicates over $A$. For a structure ${\mathbb{A}}=\langle A;L\rangle$
denote by $FBP({\mathbb{A}})$ the following two-sorted superstructure

$FBP({\mathbb{A}})=\langle{\mathbb{A}},FBP(A);s(x,y,z)\rangle$

where $x$ and $y$ run over $A$, $z$ runs over $FBP(A)$ and $s(a,b,H)$ holds in
$FBP({\mathbb{A}})$ on $a,b\in A,H\in FBP(A)$ if and only if $(a,b)\in H$.

######  Theorem 5.

Let ${\mathbb{A}}$ be an infinite structure. Then $HF({\mathbb{A}})$ and
$FBP({\mathbb{A}})$ are absolutely bi-interpretable in each other.

###### Proof.

The proof is long and cumbersome. The main ideas are known in the folklore. We
refer for some ideas to [2] where it is shown how to rewrite formulas
$\phi(x_{1},\ldots,x_{n})$ in the language of $HF({\mathbb{A}})$ with free
variables $x_{i}$ that run over $A$ into equivalent formulas
$\phi^{\ast}(x_{1},\ldots,x_{n})$ in the language of $FBP({\mathbb{A}})$ such
that for any $a_{1},\ldots,a_{n}\in{\mathbb{A}}$ one has

$HF({\mathbb{A}})\models\phi(a_{1},\ldots,a_{n})\Longleftrightarrow
FBP({\mathbb{A}})\models\phi^{\ast}(a_{1},\ldots,a_{n})$

∎

The following result is known, it is based on two facts: the first one is that
there are effective enumerations (codings) of the set of all tuples of natural
numbers such that the natural operations over the tuples are computable on
their codes; and the second one is that all computably enumerable predicates
over natural numbers are $0$-definable in ${\mathbb{N}}$ (see, for example,
[12, 48]).

######  Lemma 11.

The structures ${\mathbb{N}}$, ${\mathbb{Z}}$, $S({\mathbb{N}},{\mathbb{N}})$,
$S({\mathbb{Z}},{\mathbb{N}})$ are pair-wise absolutely bi-interpretable with
each other.

###  3.2 The weak second order logic as a fragment of $L_{\omega_{1},\omega}$

For a language $L$ the logic $L_{\omega_{1},\omega}$ admits a new (in
comparison with the first-order logic) rule of forming formulas: if $\Phi$ is
a countable set of formulas in $L_{\omega_{1},\omega}$ then $\bigwedge\Phi$
(conjunction of $\Phi$) and $\bigvee\Phi$ (disjunction of $\Phi$) are also
formulas in $L_{\omega_{1},\omega}$. Below, following [2], we describe a
subset $L_{WSOL}\subset L_{\omega_{1},\omega}$ which is equivalent to WSOL
over ${\mathbb{A}}$ (were $L=L({\mathbb{A}})$).

We fixed an arbitrary effective enumeration of the set ${\mathcal{F}}_{L}$ of
first-order formulas in $L$ by natural numbers, so there is an injection
$\nu\colon{\mathcal{F}}_{L}\to{\mathbb{N}}$ such that for every formula
$\phi\in{\mathcal{F}}_{L}$ one can compute the number $\nu(\phi)$ and given
the number $n\in{\mathbb{N}}$ one can decide if $n=\nu(\phi)$ for some $\phi$
and if so find the formula $\phi$. We assume that $\nu({\mathcal{F}}_{L})$ has
infinite complement so we can extend the enumeration to the fragment
$L_{WSOL}$. Similarly, we have an effective enumeration
$\mu\colon{\mathcal{F}}_{\mathbb{N}}\to{\mathbb{N}}$ of the first-order
formulas of the arithmetic. We define formulas in $L_{WSOL}$ by induction and,
simultaneously, do two other things: we extend the enumeration $\nu$ to the
the fragment $L_{WSOL}$ and define if a given formula $\phi\in L_{WSOL}$ has
complexity at most $r$, for $r\in{\mathbb{N}}$.

Recall that a formula $\phi=Q_{1}x_{1}\ldots Q_{m}x_{m}\psi$, where $Q_{i}$
are quantifiers $\forall,\exists$ and $\psi$ is quantifier-free, is in
$\Sigma_{n}$ ($\Pi_{n}$), $n>0$, if $Q_{1}=\exists$ ($Q_{1}=\forall$) and the
prefix $Q_{1}x_{1}\ldots Q_{m}x_{m}$ has at most $n-1$ alternations of
quantifiers.

We say that a set of formulas in $L_{WSOL}$ is arithmetic if the set of its
codes (Godel’s numbers) is arithmetic (definable in arithmetic).

Now we describe the fragment $L_{WSOL}$. Every first-order formula $\phi$ in
${\mathcal{F}}_{L}$ is in $L_{WSOL}$. Its complexity is at most $r$ if it is
in $\Sigma_{r}$ and $\Pi_{r}$ over $L$. If $\phi_{1},\phi_{2}\in L_{WSOL}$
then $\phi_{1}\wedge\phi_{2}$, $\phi_{1}\vee\phi_{2}$, $\phi_{1}\to\phi_{2}$
are also in $L_{WSOL}$. We extend the enumeration (in some arbitrary but fixed
way) onto these formulas and define that these formulas have complexity $\leq
r$ if both of the formulas $\phi_{1},\phi_{2}$ have complexity $\leq r$. If
$\phi\in L_{WSOL}$ then ${}^{\neg}\phi$, $\forall x_{i}\phi$ and $\exists
x_{i}\phi$ are in $L_{WSOL}$. If complexity of $\phi$ is $\leq r$ then
complexity of ${}^{\neg}\phi$ is $\leq r$. If $\phi=\forall x_{j}\psi$ and
complexity of $\psi$ is $\leq r$ then complexity of $\forall x_{i}\phi$ is
$\leq r$; if $\phi=\exists x_{j}\psi$ then complexity of $\exists x_{i}\phi$
is also $\leq r$. In all other cases complexity of $\forall x_{i}\phi$ and
$\exists x_{i}\phi$ is $\leq r+1$ where complexity of $\phi$ is $\leq r$.
Again we extend the enumeration to these formulas. Finally, if
$\Phi=\\{\phi_{i}\mid i\in I\\}$ is a set of arithmetic formulas from
$L_{WSOL}$, all of them have complexity $\leq r$ and all their free variables
are among $x_{1},\ldots,x_{m}$ for some $m$ then $\bigwedge\phi_{i}$ and
$\bigvee\phi_{i}$ are formulas from $L_{WSOL}$. We extend the enumeration to
these formulas and their codes include the code of the arithmetic set
$\nu(\Phi)\subset{\mathbb{N}}$. The complexity of these formulas are $\leq
r+1$, where $\nu(\Phi)$ is $\Pi_{r}$ set in ${\mathbb{N}}$, and each formula
$\phi$ has complexity $\leq r$. The formula $\bigwedge\phi_{i}$ is true in
${\mathbb{A}}$ if every formula $\phi$ is true in ${\mathbb{A}}$, while
$\bigvee\phi_{i}$ is true in ${\mathbb{A}}$ if some formula $\phi$ is true in
${\mathbb{A}}$.

For our applications the following will suffice.

######  Lemma 12.

Let $\\{\varphi_{i_{1}i_{2}\ldots
i_{n}}(x_{1},\ldots,x_{m})|i_{1},i_{2},\ldots,i_{n}\in{\bf N}\\}$ be a
recursively enumerable set of quantifier-free formulas of language $L$. Then

$\bigvee\limits_{i_{1}}\bigwedge\limits_{i_{2}}\bigvee\limits_{i_{3}}\ldots\bigvee\limits_{i_{n}}\varphi_{i_{1}i_{2}\ldots
i_{n}}(x_{1},\ldots,x_{m}),$

and

$\bigwedge\limits_{i_{1}}\bigvee\limits_{i_{2}}\bigwedge\limits_{i_{3}}\ldots\bigwedge\limits_{i_{n}}\varphi_{i_{1}i_{2}\ldots
i_{n}}(x_{1},\ldots,x_{m}),$

are formulas in $L_{WSOL}$.

######  Theorem 6.

[2] The following holds for every algebraic structure ${\mathbb{A}}$ of
language $L$:

  * 1)

for every formula $\phi(x_{1},\ldots,x_{n})\in L_{WSOL}$ one can construct a
formula $\phi^{\ast}(x_{1},\ldots,x_{n})$ in the language of
$HF({\mathbb{A}})$, which does not contain any free variables other then
$x_{1},\ldots,x_{n}$, and such that for any assignment of variables $x_{1}\to
a_{1},\ldots,x_{n}\to a_{n}$, where $a_{i}\in{\mathbb{A}}$ one has

${\mathbb{A}}\models\phi(a_{1},\ldots,a_{n})\Longleftrightarrow
HF({\mathbb{A}})\models\phi^{\ast}(a_{1},\ldots,a_{n}).$

  * 2)

for every formula $\psi(x_{1},\ldots,x_{n})$ in the language of
$HF({\mathbb{A}})$, which does not contain any free variables other then
$x_{1},\ldots,x_{n}$ that run over ${\mathbb{A}}$, one can construct a formula
$\psi^{\ast}(x_{1},\ldots,x_{n})\in L_{WSOL}$ such that for any assignment of
variables $x_{1}\to a_{1},\ldots,x_{n}\to a_{n}$, , where
$a_{i}\in{\mathbb{A}}$ one has

$HF(MA)\models\psi(a_{1},\ldots,a_{n})\Longleftrightarrow{\mathbb{A}}\models\psi^{\ast}(a_{1},\ldots,a_{n}).$

##  4 Definitions and basic properties of rich structures

Let ${\mathbb{A}}$ be a structure. By a WSOL formula
$\phi(x_{1},\ldots,x_{n})$ in the language $L=L({\mathbb{A}})$ we understand
loosely a formula either in the language of $HF({\mathbb{A}})$, or in
$S({\mathbb{N}},{\mathbb{A}})$, or in $L_{WSOL}$ with only free variables that
occur in the list $x_{1},\ldots,x_{n}$ and these variables run over
${\mathbb{A}}$. So $\phi$ does not have free variables that run over
hereditary finite subsets of $A$ (in the case of $HF({\mathbb{A}})$) or over
lists over ${\mathbb{A}}$, or over ${\mathbb{N}}$ (in case of
$S({\mathbb{N}},{\mathbb{A}})$).

######  Definition 4.

Let ${\mathbb{A}}=\langle A,L\rangle$ be a structure in a language $L$. The
structure ${\mathbb{A}}$ is termed:

  * 1)

rich if for every WSOL formula $\phi(x_{1},\ldots,x_{n})$ in the language
$L=L({\mathbb{A}})$ there is a first-order formula
$\phi^{\diamond}(x_{1},\ldots,x_{n},\bar{p})$ in the language $L$ with
parameters $\bar{p}$ in ${\mathbb{A}}$ such that for any
$a_{1},\ldots,a_{n}\in{\mathbb{A}}$

${\mathbb{A}}\models\phi(a_{1},\ldots,a_{n})\Longleftrightarrow{\mathbb{A}}\models\phi^{\diamond}(a_{1},\ldots,a_{n},\bar{p}).$

  * 2)

absolutely rich if for any formula $\phi(x_{1},\ldots,x_{n})$ as above the
formula $\phi^{\diamond}(x_{1},\ldots,x_{n})$ from 1) has no parameters.

  * 3)

effectively rich (absolutely and effectively rich)  if the map
$\phi\to\phi^{\diamond}$ is computable.

Let $\phi(x_{1},\ldots,x_{n},y_{1},\ldots,y_{m})$ be a formula in $L_{WSOL}$
and $p_{1},\ldots,p_{m}\in A$. Then, as usual, by
$\phi(x_{1},\ldots,x_{n},p_{1},\ldots,p_{m})$ we denote the formula $\phi$
with parameters $p_{1},\ldots,p_{m}$. Then the structure ${\mathbb{A}}$ is
rich if and only if any subset $S\subseteq A^{n}$ which is definable in
${\mathbb{A}}$ by a $L_{WSOL}$-formula with parameters in ${\mathbb{A}}$ is
definable in ${\mathbb{A}}$ by a first order formula in $L$ with parameters in
${\mathbb{A}}$.

In this case everything which is described by weak second order logic formulas
in ${\mathbb{A}}$ can be also described by first order ones in ${\mathbb{A}}$.

Examples

  * 1)

Any finite structure is absolutely rich.

  * 2)

For any structure ${\mathbb{A}}$ the structure $HF({\mathbb{A}})$ is
absolutely and effectively rich.

###### Proof.

To see 1) observe that in a finite structure ${\mathbb{A}}$ for every $n$
there are only finitely many non-equivalent over ${\mathbb{A}}$ formulas in
free variables $x_{1},\ldots,x_{n}$. So every infinite conjunction (or
disjunction) of formulas $\phi(x_{1},\ldots,x_{n}),i\in I$, is equivalent over
${\mathbb{A}}$ to a finite conjunction (or disjunction) of some of these
formulas.

To show 2) observe that for any structure ${\mathbb{A}}$ the structures
$HF(HF({\mathbb{A}}))$ is obtained from $HF({\mathbb{A}})$ by adding a new
everywhere true unary predicate. Indeed, $HF(HF(A))=HF(A)$, so
$HF(HF({\mathbb{A}}))=\langle HF(A);L,P_{A},P_{HF(A)},\in\rangle,$ where
$P_{HF(A)}$ defines the whole set $HF(A)$. For every formula
$\phi(x_{1},\ldots,x_{n})$ in the language of $HF(HF({\mathbb{A}}))$ where
each $x_{i}$ runs over $HF({\mathbb{A}})$ one can obtain an equivalent over
$HF({\mathbb{A}})$ formula by replacing each occurrence of the predicate
$P_{HF(A)}(x)$ in $\phi$ by the formula $x=x$. The new formula is equivalent
to $\phi$ over $HF({\mathbb{A}})$.

∎

The argument above also shows that $HF({\mathbb{A}})$ is absolutely bi-
interpretable with $HF(HF({\mathbb{A}}))$.

The following result and its corollaries give an easy tool to prove that a
structure is rich.

######  Theorem 7.

The following holds:

  * 1)

Any structure bi-interpretable (with parameters) with a rich structure is
rich.

  * 2)

Any structure absolutely bi-interpretable with an absolutely rich structure is
absolutely rich.

  * 3)

In the case above if one of the structures is effectively rich (effectively
absolutely rich) so is the other.

###### Proof.

Let ${\mathbb{A}}=\langle A;L({\mathbb{A}})\rangle$ and ${\mathbb{B}}=\langle
B;L({\mathbb{B}})\rangle$ be bi-interpretable (with parameters) in each other.
Suppose ${\mathbb{B}}$ is rich. Denote by
$\mu=\mu_{\Gamma}\colon{\mathbb{A}}\rightsquigarrow{\mathbb{B}}$ the
coordinate map, so ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},p)$ and $\mu\colon
U_{\Gamma}(B)\to A$. To show that ${\mathbb{A}}$ is rich consider a formula
$\phi(\bar{x})$ in the WSOL in $L({\mathbb{A}})$. We need to show that there
is a first-order formula $\phi^{FO}(\bar{x})$ in the language
$L({\mathbb{A}})$ such that for any tuple $\bar{a}$ in ${\mathbb{A}}$ one has

${\mathbb{A}}\models\phi(\bar{a})\Longleftrightarrow{\mathbb{A}}\models\phi^{FO}(\bar{a}).$

We prove this by induction on complexity of $\phi$. First, we define by
induction on complexity of $\phi$ a formula $\phi_{\Gamma}(\bar{z},\bar{y})$
of WSOL in the language $L({\mathbb{B}})$ (here the tuple of variables
$\bar{z}$ corresponds to the tuple $\bar{x}$, and $\bar{y}$ corresponds to the
tuple of parameters $p$, see Lemma 1), which we call the _$\Gamma$ translation
of $\phi$_. If $\phi(\bar{x})$ is a first-order formula in the language
$L({\mathbb{A}})$ then $\phi_{\Gamma}(\bar{z},\bar{y})$ is the $\Gamma$
translation of $\phi$ defined in Lemma 1. Let $\Phi=\\{\phi_{i}(\bar{x})\mid
i\in I\\}$ be an arithmetic set of formulas of WSOL in the language of
$L({\mathbb{A}})$ of uniformly bounded complexity and assume that
$\phi(\bar{x})=\bigvee_{\phi\in\Phi}\phi_{i}(\bar{x})$. Assume that by
induction the $\Gamma$-translations $(\phi_{i})_{\Gamma}(\bar{z},\bar{y})$ are
defined for all $\phi_{i}\in\Phi$ and satisfy the following conditions: each
$(\phi_{i})_{\Gamma}(\bar{z},\bar{y})$ has the same tuple of free variables
$\bar{z},\bar{y}$, all formulas $(\phi_{i})_{\Gamma}(\bar{z},\bar{y})$ have
uniformly bounded complexity, the set
$\Phi_{\Gamma}=\\{(\phi_{i})_{\Gamma}(\bar{z},\bar{y})\mid i\in I\\}$ is
arithmetic, and for all tuples $a$ in ${\mathbb{A}}$

${\mathbb{A}}\models\phi_{i}(\bar{a})\iff{\mathbb{B}}\models(\phi_{i})_{\Gamma}(\mu_{\Gamma}^{-1}(\bar{a}),\bar{p}).$

Put

$\phi_{\Gamma}(\bar{y})=\bigvee_{\phi_{i}\in\Phi}(\phi_{i})_{\Gamma}(\bar{z},\bar{y})$

Then $\phi_{\Gamma}(\bar{z},\bar{y})$ is in WSOL of $L({\mathbb{B}})$ and

${\mathbb{A}}\models\phi(\bar{a})\iff{\mathbb{B}}\models(\phi)_{\Gamma}(\mu_{\Gamma}^{-1}(\bar{a}),\bar{p}).$
(5)

We define similarly $\phi_{\Gamma}(\bar{z},\bar{y})$ for
$\phi=\bigwedge_{\phi\in\Phi}\phi_{i}(\bar{x})$. Assume now that
$\phi=\forall\bar{u}\phi_{0}(\bar{x},\bar{u})$, where the complexity of
$\phi_{0}$ is less then the complexity of $\phi$. Then we set
$\phi_{\Gamma}(\bar{z},\bar{y})=\forall\bar{v}(\phi_{0})_{\Gamma}(\bar{z},\bar{v},\bar{y})$,
where the tuples of variables $\bar{v}$ correspond to the tuples $\bar{u}$ in
the $\Gamma$-translation of $\phi_{0}$. Similarly we define
$\phi_{\Gamma}(\bar{z},\bar{y})$ for
$\phi=\exists\bar{u}\phi_{0}(\bar{x},\bar{u})$. In all these case
$\phi_{\Gamma}$ satisfies the condition (5). This defines $\phi_{\Gamma}$ for
every $\phi$ in WSOL of $L({\mathbb{A}})$.

Since ${\mathbb{B}}$ is rich there is a first-order formula
$\phi_{\Gamma}^{FO}(\bar{z},\bar{y})$ in $L({\mathbb{B}})$ such that for any
tuples $\bar{b}$, $\bar{c}$ over ${\mathbb{B}}$ one has

${\mathbb{B}}\models\phi_{\Gamma}(\bar{b},\bar{c})\Longleftrightarrow{\mathbb{B}}\models\phi_{\Gamma}^{FO}(\bar{b},\bar{c})$

It follows from the above and (5) that

${\mathbb{A}}\models\phi(\bar{a})\iff{\mathbb{B}}\models(\phi)_{\Gamma}(\mu_{\Gamma}^{-1}(\bar{a}),\bar{p})\iff{\mathbb{B}}\models\phi_{\Gamma}^{FO}(\mu_{\Gamma}^{-1}(\bar{a}),\bar{p}).$

By Lemma 8 there is a formula $\psi(\bar{z},\bar{u})$ in the first-order
language of $L({\mathbb{A}})$ such that

${\mathbb{B}}\models\phi_{\Gamma}^{FO}(\mu_{\Gamma}^{-1}(\bar{a}),\bar{p})\iff{\mathbb{A}}\models\psi(\bar{a},\bar{p}^{\ast}),$
(6)

where the tuple $\bar{p}^{\ast}$ described in Lemma 8.

The second and the third statement of the theorem follows by inspection from
the first one.

∎

######  Lemma 13.

For any structure ${\mathbb{A}}$ the structures $S({\mathbb{A}},{\mathbb{N}})$
and $FBP({\mathbb{A}})$ are absolutely and effectively rich.

###### Proof.

By Theorem 4 for any structure ${\mathbb{A}}$ the structures
$S({\mathbb{A}},{\mathbb{N}})$ and $HF({\mathbb{A}})$ are absolutely bi-
interpretable in each other. If ${\mathbb{A}}$ is finite then
$FBP({\mathbb{A}})$ is also finite hence absolutely rich. Otherwise by Theorem
5 $FBP({\mathbb{A}})$ and $HF({\mathbb{A}})$ are absolutely bi-interpretable
in each other. Since $HF({\mathbb{A}})$ is absolutely and effectively rich
(see the examples above) so, by Theorem 7, are the structures
$S({\mathbb{A}},{\mathbb{N}})$ and $FBP({\mathbb{A}})$. ∎

######  Lemma 14.

The structures ${\mathbb{N}}$ and ${\mathbb{Z}}$ are absolutely and
effectively rich.

###### Proof.

Indeed, it follows from Lemma 11 that ${\mathbb{N}}$, ${\mathbb{Z}}$ and
$S({\mathbb{N}},{\mathbb{N}})$ are absolutely bi-interpretable in each other.
By Lemma 13 the structure $S({\mathbb{N}},{\mathbb{N}})$ is absolutely and
effectively rich. Hence by Theorem 7 4 the structures ${\mathbb{N}}$,
${\mathbb{Z}}$ are also absolutely and effectively rich. ∎

######  Corollary 4.

Let ${\mathbb{A}}$ be a structure. Then the following holds:

  * •

If ${\mathbb{A}}$ is bi-interpretable with ${\mathbb{Z}}$ then ${\mathbb{A}}$
is rich.

  * •

If ${\mathbb{A}}$ is absolutely bi-interpretable with ${\mathbb{Z}}$ then
${\mathbb{A}}$ is absolutely and effectively rich.

######  Corollary 5.

The field of rational numbers ${\mathbb{Q}}$ is absolutely and effectively
rich.

###### Proof.

Indeed, ${\mathbb{Z}}$ and ${\mathbb{Q}}$ are absolutely bi-interpretable in
each other. ∎

The results above showed how one can use absolute bi-interpretability to prove
that a structure is absolutely rich. Now we describe a method that allows one
to prove that a structure is absolutely rich via regular bi-interpretability.

######  Lemma 15.

Let a structure ${\mathbb{A}}$ is half-absolute bi-interpretable in a
structure ${\mathbb{B}}$ (see Corollary 3). Then if ${\mathbb{B}}$ is
absolutely rich then ${\mathbb{A}}$ is also absolutely rich.

###### Proof.

By definition ${\mathbb{A}}$ is half-absolute bi-interpretable in
${\mathbb{B}}$ if they are regularly bi-interpretable in such a way that
${\mathbb{B}}\simeq\Delta({\mathbb{A}},\psi)$ and
${\mathbb{A}}\simeq\Gamma({\mathbb{B}})$ is an absolute interpretation. In our
poof we follow the argument in Theorem 7. In the notation of the theorem, let
$\phi(\bar{x})$ be a WSOL formula in the language of ${\mathbb{A}}$. Consider
the WSOL formula $(\phi)_{\Gamma}$ in thje language of ${\mathbb{B}}$
constructed Theorem 7. It was shown in (5) that

${\mathbb{A}}\models\phi(\bar{a})\iff{\mathbb{B}}\models(\phi)_{\Gamma}(\mu_{\Gamma}^{-1}(\bar{a})).$

Since ${\mathbb{B}}$ is absolutely rich there is a first-order formula
$\phi^{FO}$ in the language of ${\mathbb{B}}$ which is equivalent to
$(\phi)_{\Gamma}$ on ${\mathbb{B}}$. So if $S$ is the true-set of the formula
$\phi$ in ${\mathbb{A}}$ then $\mu_{\Gamma}^{-1}(S)$ is defined in
${\mathbb{B}}$ by the formula $\phi^{FO}$ (without parameters). By Corollary 3
the set $S$ is defined by some first-order formula (without parameters) in
$MA$. This shows that ${\mathbb{A}}$ is absolutely rich. ∎

######  Remark 3.

The situation of the Lemma 15 is typical when there is a regular bi-
interpretability of a structure ${\mathbb{A}}$ with ${\mathbb{N}}$ or
${\mathbb{Z}}$. Indeed, in this case, since every element of ${\mathbb{N}}$
(or ${\mathbb{Z}}$) is $0$-definable in ${\mathbb{N}}$ (or ${\mathbb{Z}}$)
every interpretation (with parameters) of ${\mathbb{A}}$ in ${\mathbb{N}}$ (or
in ${\mathbb{Z}}$) is $0$-interpretation, so the regular bi-interpretation of
${\mathbb{A}}$ and ${\mathbb{Z}}$ becomes half-absolute. Moreover, as we
mentioned above, the structures ${\mathbb{N}}$ and ${\mathbb{Z}}$ are
absolutely rich.

The results above show that it is helpful to have a large collection of rich
structures to show that some other structures are rich.

##  5 First-order rigidity, quasi-finite axiomatizability, primality, and
homogeneity

In this section we discuss the properties mentioned in the title above and
their relationship with bi-interpretability.

###  5.1 Primality and homogeneity

We begin by recalling some model-theoretic definitions (we refer to books [34,
20] for details). For the remainder of this section $L$ is a countable
language and $T$ is a complete $L$-theory with infinite models.

A model $M$ of $T$ is a _prime_ model of $T$ if it embeds elementarily in any
model of $T$. A model $M$ of $T$ is _atomic_ if every type realized in $M$ is
principal. A model is $M$ is _homogeneous_ if for every two tuples
$\bar{a},\bar{b}\in M^{n}$ ($n\in{\mathbb{N}}$) that realise the same types in
$M$ there is an automorphism of $M$ that maps $\bar{a}$ onto $\bar{b}$. It is
known that a model $M$ of $T$ is prime if and only if it is countable and
atomic. Furthermore, if $M$ is atomic then it is homogeneous.

It is easy to see that ${\mathbb{N}}=\langle N;+,\cdot,<,0,1\rangle$ is a
prime model of $Th({\mathbb{N}})$ and ${\mathbb{Z}}=\langle
Z;+,\cdot,<,0,1\rangle$ is a prime model of $Th({\mathbb{Z}})$.

The following result is useful.

######  Lemma 16.

Let ${\mathbb{A}}$ and ${\mathbb{B}}$ be infinite $L$-structures bi-
interpretable (with parameters) in each other. If ${\mathbb{A}}$ is prime in
$Th({\mathbb{A}})$ then ${\mathbb{B}}$ is also prime in $Th({\mathbb{B}})$.

###### Proof.

Follows from Lemma 4. ∎

######  Corollary 6.

If an infinite structure ${\mathbb{A}}$ is bi-interpretable with
${\mathbb{Z}}$ then ${\mathbb{A}}$ is prime in $Th({\mathbb{A}})$, hence it is
atomic and homogeneous.

The following result is often useful when proving that a finitely generated
structure is homogeneous. To state it we need to recall a few notions and
definitions.

An $L$-structure ${\mathbb{A}}$ is called _Hopfian_ if every epimorphism
${\mathbb{A}}\to{\mathbb{A}}$ is an automorphism. ${\mathbb{A}}$ is
_equationally Noetherian_ if for every $n\in{\mathbb{N}}$ every system of
equations in variables $\\{x_{1},\ldots,x_{n}\\}$ and coefficients from
${\mathbb{A}}$ is equivalent over ${\mathbb{A}}$ to a finite subsystem. A
finitely generated structure ${\mathbb{A}}$ has _definable $n$-generation_ for
a given $n\in{\mathbb{N}}$ if there is a first-order $L$-formula
$\phi(x_{1},\ldots,x_{n})$ such that there is a generating $n$-tuple
$\bar{a}=(a_{1},\ldots,a_{n})$ of ${\mathbb{A}}$ such that
${\mathbb{A}}\models\phi(a_{1},\ldots,a_{n})$ and for any $n$-tuple
$\bar{b}=(b_{1},\ldots,b_{n})$ of elements of ${\mathbb{A}}$ if
${\mathbb{A}}\models\phi(b_{1},\ldots,b_{n})$ then the tuple $b$ generates
${\mathbb{A}}$.

######  Theorem 8.

Let ${\mathbb{A}}$ be a finitely generated $L$-structure which satisfies the
following conditions:

  * •

${\mathbb{A}}$ is either finitely presented or equationally Noetherian,

  * •

${\mathbb{A}}$ is Hopfian,

  * •

${\mathbb{A}}$ has definable generation for some $n\in{\mathbb{N}}$.

Then ${\mathbb{A}}$ is prime.

###### Proof.

We will prove the theorem for groups, leaving the general case to the reader.

The structure ${\mathbb{A}}$ has definable $n$-generation for some
$n\in{\mathbb{N}}$, so there is a first-order $L$-formula
$\phi(x_{1},\ldots,x_{n})$ and a generating $n$-tuple
$\bar{a}=(a_{1},\ldots,a_{n})$ in ${\mathbb{A}}$ such that
${\mathbb{A}}\models\phi(\bar{a})$ and for any $n$-tuple
$\bar{b}=(b_{1},\ldots,b_{n})$ of elements of ${\mathbb{A}}$ if
${\mathbb{A}}\models\phi(\bar{b})$, then the tuple $\bar{b}$ generates
${\mathbb{A}}$. Now we describe a first-order $L$-formula
$R(x_{1},\ldots,x_{n})$ in variables $\bar{x}=(x_{1},\ldots,x_{n})$.

Case 1. Suppose ${\mathbb{A}}$ is finitely presented and

${\mathbb{A}}=\langle a_{1},\ldots,a_{n}\mid
r_{1}=s_{1},\ldots,r_{k}=s_{k}\rangle,$

where $r_{i},s_{i}$ are $L$-terms in $a_{1},\ldots,a_{n}$, is a finite
presentation. Then we put

$R(\bar{x})=\bigwedge_{i=1}^{m}(r_{i}(\bar{x})=s_{i}(\bar{x})).$ (7)

Case 2. Suppose ${\mathbb{A}}$ is equationally Noetherian. Consider an
$L$-system $S$ of all equations $r(x_{1},\ldots,x_{n})=s(x_{1},\ldots,x_{n})$
without coefficients which are true for $x_{1}=a_{1},\ldots,x_{n}=a_{n}$.
Since ${\mathbb{A}}$ is equationally Noetherian the system $S$ is equivalent
over ${\mathbb{A}}$ to a finite subsystem $r_{1}=s_{1},\ldots,r_{k}=s_{k}$.
Again we put $R(\bar{x})$ as in (7). Clearly, in both cases the tuple
$\bar{a}$ satisfies $R(\bar{x})$ in ${\mathbb{A}}$.

Let $c=(c_{1},\ldots,c_{m})$ be an arbitrary tuple of elements of
${\mathbb{A}}$. Then there are $L$-terms $t_{1},\ldots,t_{m}$ in variables
$\bar{x}=(x_{1},\ldots,x_{n})$ such that $c_{i}=t_{i}(\bar{a}),i=1,\ldots,m.$
Then the tuple $c$ satisfies the following first-order formula

$\psi_{c}(y_{1},\ldots
y_{m})=\exists\bar{x}\left(\bigwedge_{i=1}^{m}(y_{i}=t_{i}(\bar{x}))\wedge\phi(\bar{x})\wedge
R(\bar{x})\right).$

Suppose now that a tuple $d=(d_{1},\ldots,d_{m})$ satisfies the formula
$\psi_{c}$ in ${\mathbb{A}}$. Then there is a tuple $\bar{b}$ in
${\mathbb{A}}$ such that ${\mathbb{A}}\models\phi(\bar{b})$,
${\mathbb{A}}\models R(\bar{b})$, and $d_{i}=t_{i}(\bar{b}),i=1,\ldots,m$. It
follows that $\bar{b}$ is a generating tuple of ${\mathbb{A}}$, which
satisfies all the relations in the formula $R(\bar{x})$. It also follows that
the map $a_{1}\to b_{1},\ldots,a_{n}\to b_{n}$ extends to a homomorphism
$\alpha\colon{\mathbb{A}}\to{\mathbb{A}}$ which is onto. Since the structure
${\mathbb{A}}$ is Hopfian the homomorphism $\alpha$ is an automorphism of
${\mathbb{A}}$ that maps $c$ to $d$. This shows that ${\mathbb{A}}$ is
homogeneous. Moreover, we claim that the type $tp(c)$ of $c$ in ${\mathbb{A}}$
is principal (isolated) and is generated by the formula $\psi_{c}$. Indeed, if
not, then there is a model ${\mathbb{B}}$ of the first-order theory of
${\mathbb{A}}$ which omits $tp(c)$, so there is a formula
$\theta(x_{1},\ldots,x_{m})\in tp(c)$ and a tuple $e$ in ${\mathbb{B}}$ such
that ${\mathbb{B}}\models\psi_{c}(e)\wedge\neg\theta(e)$. Then the formula
$\exists
x_{1},\ldots,x_{m}(\psi_{c}(x_{1},\ldots,x_{m})\wedge\neg\theta(x_{1},\ldots,x_{m}))$
holds in ${\mathbb{B}}$, hence in ${\mathbb{A}}$. Therefore, there is a tuple
$e^{\prime}$ in ${\mathbb{A}}$ such that
${\mathbb{A}}\models\psi_{c}(e^{\prime})\wedge\neg\theta(e^{\prime})$. This
implies that there is an automorphism $\alpha\in Aut({\mathbb{A}})$ such that
$\alpha(c)=e^{\prime}$ — contradiction, because $c$ satisfies the formula
$\theta$ in ${\mathbb{A}}$, but $e^{\prime}$ does not. This proves that the
type $tp(c)$ is principal. Since $c$ is an arbitrary tuple in ${\mathbb{A}}$
the structure ${\mathbb{A}}$ is atomic, hence prime.

This proves the theorem

∎

###  5.2 First-order rigidity and quasi-finite axiomatizability

######  Definition 5.

A finitely generated $L$-structure ${\mathbb{A}}$ is called _first-order
rigid_ if for any finitely generated $L$-structure ${\mathbb{B}}$ first-order
equivalence ${\mathbb{A}}\equiv{\mathbb{B}}$ implies isomorphism
${\mathbb{A}}\simeq{\mathbb{B}}$.

######  Definition 6.

Fix a finite signature. An infinite finitely generated structure is Quasi
Finitely Axiomatizable (QFA) if there exists a first-order sentence $\phi$ of
the signature such that

  * •

${\mathbb{A}}\models\phi$

  * •

If ${\mathbb{B}}$ is a finitely generated structure in the same signature and
${\mathbb{B}}\models\phi$ then ${\mathbb{A}}\cong{\mathbb{B}}$.

Recall that if $X$ is a subset of an $L$-structure ${\mathbb{A}}$ then the
_diagram_ of $X$ in ${\mathbb{A}}$ (denoted $D_{X}({\mathbb{A}})$) is the set
of all atomic sentences in the language $L$ with constants from $X$ and their
negations that hold in ${\mathbb{A}}$. If $G$ is a group and $X\subseteq G$
then $D_{X}(G)$ describes the multiplication table of the subgroup of $G$
generated by $X$.

A countable $L$-structure ${\mathbb{A}}=\langle A,L\rangle$ is called
_arithmetic_ if the set of the Godel’s numbers of the diagram
$D_{A}({\mathbb{A}})$ of ${\mathbb{A}}$ is an arithmetic subset of
${\mathbb{N}}$. If the structure ${\mathbb{A}}$ is generated by a finite set
$S$ then it suffices to consider effective enumerations of ${\mathbb{A}}$ via
the terms of the language $L$ with constants from $S$, in this case
${\mathbb{A}}$ is arithmetic if the diagram $D_{S}({\mathbb{A}})$ is an
arithmetic subset of ${\mathbb{N}}$. In particular, a group $G$ generated by a
finite set $S$ is arithmetic if and only if the word problem $W(G,S)$ of $G$
relative to the set $S$ is arithmetic. Here $W(G,S)$ is the set of all group
words in the generators $S$ which are equal to 1 in $G$. $W(G,S)$ is
arithmetic if there is an effective enumeration $\nu\colon
M_{X}\to{\mathbb{N}}$ of all words in the alphabet $S\cup S^{-1}$ such that
the set $\nu(W(G,S))$ is arithmetic.

######  Lemma 17.

Let ${\mathbb{A}}$ be a structure interpretable in ${\mathbb{Z}}$ or
${\mathbb{N}}$. Then ${\mathbb{A}}$ is arithmetic.

###### Proof.

Let ${\mathbb{A}}=\Gamma({\mathbb{N}},\bar{p})$. Then there is
$k\in{\mathbb{N}}$, a definable in ${\mathbb{N}}$ subset $A^{\ast}\subseteq
N^{k}$ and a definable in ${\mathbb{N}}$ equivalence relation $=_{\Gamma}$
such that $A^{\ast}/=_{\Gamma}$ is the universe of
$\Gamma({\mathbb{N}},\bar{p})$. One can effectively enumerate tuples in
$N^{k}$, then effectively enumerate tuples in $A^{\ast}$, and then effectively
enumerate some set of representatives of the equivalence classes of
$A^{\ast}/=_{\Gamma}$. Since the basic operations and predicates in
$\Gamma({\mathbb{N}},\bar{p})$ are definable in ${\mathbb{N}}$ the diagram of
$\Gamma({\mathbb{N}},\bar{p})$ with respect to the enumeration of chosen set
of representatives is arithmetic in ${\mathbb{N}}$. This proves the lemma. ∎

######  Theorem 9.

Let ${\mathbb{A}}$ be a rich structure in a finite signature. If
${\mathbb{A}}$ is generated by a finite set $S$ with an arithmetic diagram
$D_{S}({\mathbb{A}})$ then ${\mathbb{A}}$ is QFA.

We prove the theorem in three steps, starting with the following lemmas.

Let ${\mathbb{A}}=\langle A;L\rangle$ be an $L$-structure in a finite language
$L$. Recall that by $S({\mathbb{A}})$ we denote the two-sorted structure

$S({\mathbb{A}})=\langle{\mathbb{A}},S(A);\frown,\in\rangle,$

where $S(A)$ is the set of all finite sequences (tuples) of elements from $A$,
$\frown$ is the binary operation of concatenation of two sequences from $S(A)$
and $a\in s$ for $a\in A,s\in S(A)$ means that $a$ is a component of the tuple
$s$. The superstructure $S({\mathbb{A}},{\mathbb{N}})$ is defined as the
three-sorted structure

$S({\mathbb{A}},{\mathbb{N}})=\langle{\mathbb{A}},S(A),{\mathbb{N}};t(s,i,a),l(s),\frown,\in\rangle,$

where ${\mathbb{N}}=\langle N,+,\cdot,0,1\rangle$ is the standard arithmetic,
$l\colon S(A)\to N$ is the length function, i.e., $l(s)$ is the length of the
tuple $s$ and $t(x,y,z)$ is a predicate on $S(A)\times N\times A$ such that
$t(s,i,a)$ holds in $S({\mathbb{A}},{\mathbb{N}})$ if and only if
$s=(s_{1},\ldots,s_{n})\in S(A),i\in N,1\leq i\leq n$, and $a=s_{i}\in A$. By
$L_{list}$ we denote the language of the three-sorted structure
$S({\mathbb{A}},{\mathbb{N}})$ (one can represent
$S({\mathbb{A}},{\mathbb{N}})$ as a standard one-sorted structure, taking
union of $A,S(A)$ and $N$ as a new universe and introducing unary predicates
defining $A,S(A)$ and $N$ in the union). Observe that the operation $\frown$
and the predicate $\in$ are $0$-definable in $S({\mathbb{A}},{\mathbb{N}})$
(with the use of $t(s,i,a)$), so sometimes we omit them from the language.
Now, we are ready to state a lemma.

######  Lemma 18.

let $L$ be a finite language, ${\mathbb{A}}$ an $L$-structure, and
$S({\mathbb{A}},{\mathbb{N}})$ the list superstructure over ${\mathbb{A}}$.
Then there is a sentence $\Sigma$ in the language $L_{list}$ such that
$S({\mathbb{A}},{\mathbb{N}})\models\Sigma$, and for any three-sorted
$L_{list}$-structure $T=\langle A_{T},S_{T},N_{T}\rangle$ if $T\models\Sigma$,
then the following holds:

  * 1)

$A_{T}$ is an $L$-structure.

  * 2)

$N_{T}$ is a model of arithmetic where ${\mathbb{N}}$ is the initial segment
of the ordered set $\langle N_{T};\leq\rangle$, with respect to the standard
ordering $\leq$ of $N_{T}$. In this case ${\mathbb{N}}$ is an elementary
substructure of $N_{T}$.

  * 3)

Let $S_{\omega}=\\{s\in S_{T}\mid l(s)\in{\mathbb{N}}\\}$. Then $\langle
S_{\omega};\frown,\in\rangle$ is a substructure of $S_{T}=\langle
S_{T};\frown,\in\rangle$, which is isomorphic to $\langle
S(A_{T});\frown,\in\rangle$.

  * 4)

$\langle A_{T},S_{\omega},{\mathbb{N}}\rangle$ is a substructure of $T=\langle
A_{T},S_{T},N_{T}\rangle$.

###### Proof.

One can take $\Sigma$ as a conjunction of the following conditions:

  * 1)

The symbols in $L_{list}$ that correspond to operations in $L$,
$S({\mathbb{A}})$, ${\mathbb{N}}$, and $({\mathbb{A}},{\mathbb{N}})$ define in
$T$ correspondingly, operations on $A_{T}$, $S_{T}$, $N_{T}$, and $T=\langle
A_{T},S_{T},N_{T}\rangle$. Since there only finitely many such operations this
condition can be written by a first-order sentence in $L_{list}$.

  * 2)

Since Robinson arithmetic $\mathcal{Q}$ is finitely axiomatizable, one can
write a sentence in arithmetic (hence in $L_{list}$) that makes sure that
$\langle N_{T};+,\cdot,1\rangle$ is a model of $Th({\mathbb{N}})$. It is known
that in this case ${\mathbb{N}}$ is an in initial segment of $\langle
N_{T};\leq\rangle$ and it is an elementary substructure of $N_{T}$.

  * 3)

If $S_{\omega}=\\{s\in S_{T}\mid l(s)\in{\mathbb{N}}\\}$, then $\langle
S_{\omega};\frown,\in\rangle$ is a substructure of $S_{T}=\langle
S_{T};\frown,\in\rangle$, since concatenation of two tuples with length in
${\mathbb{N}}$ is again a tuple of length in ${\mathbb{N}}$. Now we need to
write down by an $L_{list}$-sentence some conditions that ensure that the
structure $S_{\omega}$ with operations $\frown$ and $\in$ induced from $S_{T}$
is isomorphic to the structure $S(A_{T});\frown,\in\rangle$.

    * 3.1)

The first condition makes sure that the every element $s\in S_{T}$ is uniquely
determined by it’s length $l(s)$ and all its components:

$\forall s,r\in S_{T}\left(l(s)=l(r)\wedge\forall i\in N_{T},\forall x\in
A_{T}(t(s,i,x)\leftrightarrow t(r,i,x))\to s=r\right)$

    * 3.2)

The second condition states that for any $n\in{\mathbb{N}}$, for any $1\leq
i\leq n$, and for any $a_{i}\in A_{T}$ there is $s\in S_{T}$ with $l(s)=n$ and
for which $t(s,i,a_{i})$ holds for any such $i$. To do this it suffices to
write down that for any $a\in A_{T}$ there is $s_{a}$ of length 1 ($l(s)=1$)
such that $a$ is the only component of $s_{a}$, i.e., $t(s_{a},1,a)$ holds.
This ensures that the tuple $s$ with the properties described above exists in
$S_{T}$. Indeed, the tuple $s$ has finite length hence it is a finite
concatenation of the 1-tuples $s_{a_{1}},\ldots,s_{a_{n}}$. It is left to
write down a sentence which expresses that concatenation of any two tuples
$s,r\in S_{T}$ exists and gives precisely what it is supposed to. Namely, for
any $r,s\in S_{T}$ there is $u\in S_{T}$ such that for any $x\in A_{T}$ and
any $i\leq l(r)$ one has $t(r,i,x)\leftrightarrow t(u,i,x)$ (this condition
makes sure that $r$ is a prefix of $u$) and for any $j\leq l(s)$ one has
$t(s,j,x)\leftrightarrow t(u,l(r)+j,x)$.

We claim that if the conditions 3.1) and 3.2) are satisfied then there is an
isomorphism $\lambda\colon\langle S_{\omega};\frown,\in\rangle\to\langle
S(A_{T});\frown,\in\rangle$. For $s\in S_{\omega}$ put $\lambda(s)$ to be the
unique tuple $(a_{1},\ldots,a_{l(s))}$ such that for any $i\leq l(s)$ the
condition $t(s,i,a_{i})$ holds. Then 3.1) tells one that $\lambda$ is
injective, while 3.2) makes sure that $\lambda$ is onto. Obviously, $\lambda$
preserves the operation $\frown$ and the predicate $\in$.

Now 4) follows from 1)-3). Indeed, by construction $\langle
A_{T},S_{\omega},{\mathbb{N}}\rangle$ is a substructure of $T=\langle
A_{T},S_{T},N_{T}\rangle$. ∎

Let $X=\\{x_{i}\mid i\in{\mathbb{N}}\\}$ be a countable set of variables, and
$T_{L}(X)$ be the set of all terms in the language $L$ in variables $X$. If
the language $L$ is finite or countable, then there is a function $\nu\colon
T_{L}(X)\to{\mathbb{N}}$ such that $\nu$ is injective (we may also assume that
$\nu$ is surjective, if needed), the subset $\nu(T_{L}(X))$ of ${\mathbb{N}}$
is computable, and the functions $\nu$ and its inverse
$\nu^{-1}\colon\nu(T_{L}(X))\to T_{L}(X)$ are computable.

######  Lemma 19.

Let $L$ be a language with finite signature, ${\mathbb{A}}$ a finitely
generated $L$-structure, and $S({\mathbb{A}},{\mathbb{N}})$ its list
superstructure. Then the following holds:

  * 1)

for any $n\in{\mathbb{N}}$ there is a formula
$\Phi_{n}(x_{1},\ldots,x_{n},y,z)$ in the language $L_{list}$ (where
$x_{1},\ldots,x_{n},y$ are variables of the sort ${\mathbb{A}}$ and $z$ is a
variable of the sort ${\mathbb{N}}$) such that for any
$g_{1},\ldots,g_{n},h\in{\mathbb{A}}$ and $m\in{\mathbb{N}}$

$S({\mathbb{A}},{\mathbb{N}})\models\Phi_{n}(g_{1},\ldots,g_{n},h,m)$

if and only if there exists a term $t=t(x_{1},\ldots,x_{n})$ in the language
$L$ such that $h=t(g_{1},\ldots,g_{n})$ and $\nu(t)=m$ with respect to some
fixed effective enumeration $\nu\colon T_{L}(X)\to{\mathbb{N}}$ of all terms
$t$ in the language $L$.

  * 2)

There is a formula $\Psi(u,y,z)$ in the language of $L_{list}$ (where $u$ is a
variable of the sort $S({\mathbb{A}})$, $y$ is a variable of the sort
${\mathbb{A}}$ and $z$ is a variable of the sort ${\mathbb{N}}$) such that for
any $s=(a_{1},\ldots,a_{n})\in S({\mathbb{A}})$, $h\in{\mathbb{A}}$,
$m\in{\mathbb{N}}$

$S({\mathbb{A}},{\mathbb{N}})\models\Psi(s,h,m)$

if and only if there exists a term $t=t(x_{1},\ldots,x_{n})$ in the language
$L$ such that $h=t(a_{1},\ldots,a_{n})$ and $\nu(t)=m$ with respect to some
fixed effective enumeration $\nu\colon T_{L}(X)\to{\mathbb{N}}$ of all terms
$t$ in the language $L$.

###### Proof.

We prove this lemma for the language $L$ of group theory (the same argument
works for the language of rings), leaving the general case to the reader.
Thus, ${\mathbb{A}}$ is a group. We prove 2) first and then derive 1) from 2).

Let $X=\\{x_{i}\mid i\in{\mathbb{N}}\\}$ be an infinite countable set of
variables. $X^{-1}=\\{x_{i}^{-1}\mid x\in X\\}$ the set of formal inverses of
elements of $X$ and $M_{X}$ the set of all finite words in the alphabet
$X^{\pm 1}=X\cup X^{-1}$ (called _group words_ in $X$) viewed as a free monoid
on $X\cup X^{-1}$, where multiplication is concatenation. A word $w\in M_{X}$
can be represented as $w=x_{k_{1}}^{\varepsilon_{1}}\ldots
x_{k_{\ell}}^{\varepsilon_{\ell}}$, where $x_{k_{i}}\in X^{\pm 1}$,
$\varepsilon_{i}\in\\{-1,1\\}$, $\ell\in{\mathbb{N}}$. With the word $w$ we
associate a unique tuple $m_{w}\in{\mathbb{N}}^{2\ell}$:

$m_{w}=(k_{1},\varepsilon_{1}+1,k_{2},\varepsilon_{2}+1,\ldots,k_{\ell},\varepsilon_{\ell}+1)$

(here we use $\varepsilon_{i}+1$ instead of $\varepsilon_{i}$ to have numbers
in ${\mathbb{N}}$).

Let $\nu\colon\bigcup_{\ell>0}{\mathbb{N}}^{\ell}\to{\mathbb{N}}$ be a
bijection such that $\nu$ and $\nu^{-1}$ are computable. Here $\nu^{-1}$ is
computable when for every $m\in{\mathbb{N}}$ the length $\ell=|\nu^{-1}(m)|$
of the tuple $\nu^{-1}(m)=(a_{1},\ldots,a_{\ell})$ is computable and there is
a computable function $f(m,i)$ such that for any $m\in{\mathbb{N}}$ and any
$i,1\leq i\leq\ell$ one has $f(m,i)=a_{i}$. There are many such bijections, we
fix one of them, defined by

$\nu(a_{1},\ldots,a_{\ell})=2^{a_{1}}+2^{a_{1}+a_{2}+1}+\ldots+2^{a_{1}+\ldots+a_{\ell}+\ell-1}-1.$

To find $\nu^{-1}(m)$ for a given $m\in{\mathbb{N}}$ one can use the unique
binary representation of $m-1$ and find unique integers $0\leq
b_{1}<b_{2}<\ldots<b_{\ell}$ such that $m-1=2^{b_{1}}+\ldots 2^{b_{\ell}}$ and
then find the numbers $a_{1},\ldots,a_{\ell}$.

The subset $W=\\{\nu(m_{w})\mid w\in M_{X}\\}$ is definable in ${\mathbb{N}}$
by a first-order formula, since the functions $m\to|\nu^{-1}(m)|$ and $f(m,i)$
above are computable, hence definable in arithmetic. Observe that the map
$w\to\nu(m_{w})$ gives an effective enumeration of all group words in $M_{X}$.

Fix $n\in{\mathbb{N}}$ and put $X_{n}=\\{x_{1},\ldots,x_{n}\\}\subset X$. Let
$M_{X_{n}}$ be the subset (submonoid) of $M_{X}$, consisting of all group
words in variables $X_{n}^{\pm 1}$. Then the subset $W_{n}=\\{\nu(m_{w})\mid
w\in M_{X_{n}}\\}$ is also definable in ${\mathbb{N}}$. Indeed, it suffices to
add a conjunct to the formula defining $W$ that says that all odd components
of $m_{w}$ are less or equal to $n$.

With a tuple $r=(r_{1},\ldots,r_{n})\in S({\mathbb{A}})$ of length $n$ and a
word $w=x_{k_{1}}^{\varepsilon_{1}}\ldots x_{k_{\ell}}^{\varepsilon_{\ell}}\in
M_{X_{n}}$ (here $x_{k_{j}}\in X_{n}$ for any $j$) we associate a unique tuple
$s_{r,w}\in S({\mathbb{A}})$ defined as follows:

$s_{r,w}=(r_{k_{1}}^{\varepsilon_{1}},r_{k_{1}}^{\varepsilon_{1}}r_{k_{2}}^{\varepsilon_{2}},\ldots,r_{k_{1}}^{\varepsilon_{1}}\ldots
r_{k_{\ell}}^{\varepsilon_{\ell}})$

so the last component of $s_{r,w}$ is equal to
$w(r_{1},\ldots,r_{n})\in{\mathbb{A}}$.

Claim. The subset $P=\\{(r,s_{r,w},\nu(m_{w}))\mid r\in S({\mathbb{A}}),w\in
M_{X_{|r|}}\\}$ of $S({\mathbb{A}})\times S({\mathbb{A}})\times{\mathbb{N}}$
is definable in $S({\mathbb{A}},{\mathbb{N}})$.

Indeed, a triple $(r,s,m)\in S({\mathbb{A}})\times
S({\mathbb{A}})\times{\mathbb{N}}$ belongs to $P$ if the following conditions
hold:

1) $|\nu^{-1}(m)|=2|s|$ and $m\in W_{|r|}$, i.e., $m=\nu(m_{w})$ for some
$w\in M_{X_{|r|}}$.

2) Let $r=(r_{1},\ldots,r_{n})$, $s=(s_{1},\ldots,s_{\ell})$ and
$\nu^{-1}(m)=(a_{1},b_{1},\ldots,a_{\ell},b_{\ell})$. Then for all $i$ such
that $1\leq i<\ell$ the following two conditions hold:

$\bigwedge_{k=1}^{n}[(a_{i+1}=k\wedge b_{i+1}=2)\to s_{i+1}=s_{i}r_{k}]$

and

$\bigwedge_{k=1}^{n}[(a_{i+1}=k\wedge b_{i+1}=0)\to s_{i+1}=s_{i}r_{k}^{-1}],$

where we assume that $s_{0}=1$. Observe, that both conditions 1) and 2) can be
described by a formula in the language $L_{list}$ in $r,s$ and $m$. Indeed,
using the predicate $t(s,i,m)$ of $S({\mathbb{A}},{\mathbb{N}})$ one can
express the conditions that $r_{i},a_{i},b_{i}$ and $s_{i}$ are the
corresponding components of $r$ and $s$. Let $\Phi_{P}(u,v,z)$ be conjunction
of the formulas that describe 1) and 2) (here the variable $u$ correspond to
$r$, the variable $v$ correspond to $s$ and $z$ corresponds to $m$). Then
$\Phi_{P}(u,v,z)$ defines $P$ in $S({\mathbb{A}},{\mathbb{N}})$ and the claim
follows.

Consider a formula

$\Psi_{P}(u,y,z)=\exists v(\Phi_{P}(u,v,z)\wedge t(v,l(v),y))$

language $L_{list}$, here $t$ and $l(v)$ are the predicate and the function
from $L_{list}$, $u$ is a variable of the sort $S({\mathbb{A}})$, $y$ is a