A first-order theory of Ulm type

Abstract

The class of Abelian p-groups are an example of some very interesting phenomena in computable structure theory. We will give an elementary first-order theory $T_{p}$ whose models are each bi-interpretable with the disjoint union of an Abelian p-group and a pure set (and so that every Abelian p-group is bi-interpretable with a model of $T_{p}$ ) using computable infinitary formulas. This answers a question of Knight by giving an example of an elementary first-order theory of “Ulm type”: Any two models, low for $ω_{1}^{C K}$ , and with the same computable infinitary theory, are isomorphic. It also gives a new example of an elementary first-order theory whose isomorphism problem is $Σ_{1}^{1}$ -complete but not Borel complete.

Keywords

p-groups Borel reducibility computable structure theory

1. Introduction

The class of Abelian p-groups is a well-studied example in computable structure theory. A simple compactness argument shows that Abelian p-groups are not axiomatizable by an elementary first-order theory, but they are definable by the conjunction of the axioms for Abelian groups (which are first-order $\forall \exists$ sentences) and the infinitary $Π_{2}^{0}$ sentence which says that every element is torsion of order some power of p.

Abelian p-groups are classifiable by their Ulm sequences [14]. Due to this classification, Abelian p-groups are examples of some very interesting phenomena in computable structure theory and descriptive set theory. We will define a theory $T_{p}$ whose models behave like the class of Abelian p-groups, giving a first-order example of these phenomena. In particular, Theorem 1.6 below answers a question of Knight. Unfortunately, the techniques used do not seem to be able to be generalized much beyond p-groups.

1.1. Infinitary formulas

The infinitary logic $L_{ω_{1} ω}$ is the logic which allows countably infinite conjunctions and disjunctions but only finite quantification. If the conjunctions and disjunctions of a formula φ are all over computable sets of indices for formulas, then we say that φ is computable. We use $Σ_{α}^{in}$ and $Π_{α}^{in}$ to denote the classes of all infinitary $Σ_{α}$ and $Π_{α}$ formulas respectively. We will also use $Σ_{α}^{c}$ and $Π_{α}^{c}$ to denote the classes of computable $Σ_{α}$ and $Π_{α}$ formulas, where $α < ω_{1}^{C K}$ the least non-computable ordinal. See Chapter 6 of [1] for a more complete description of computable formulas.

1.2. Bi-interpretability

One way in which we will see that the models of $T_{p}$ are essentially the same as Abelian p-group is using bi-interpretations using infinitary formulas [7,8,10]. A structure $A$ is infinitary interpretable in a structure $B$ if there is an interpretation of $A$ in $B$ where the domain of the interpretation is allowed to be a subset of $B^{< ω}$ and where all of the sets in the interpretation are definable using infinitary formulas. This differs from the classical notion of interpretation, as in model theory [9, Definition 1.3.9], where the domain is required to be a subset of $B^{n}$ for some n, and the sets in the interpretation are first-order definable.

Definition 1.1.
We say that a structure $A = (A; P_{0}^{A}, P_{1}^{A}, \dots)$ (where $P_{i}^{A} \subseteq A^{a (i)}$ ) is infinitary interpretable in $B$ if there exists a sequence of relations $(D o m_{A}^{B}, \sim, R_{0}, R_{1}, \dots)$ , definable using infinitary formulas (from $L_{ω_{1} ω}$ , in the language of $B$ , without parameters), such that
$D o m_{A}^{B} \subseteq B^{< ω}$ ,

∼ is an equivalence relation on $D o m_{A}^{B}$ ,

$R_{i} \subseteq {(B^{< ω})}^{a (i)}$ is closed under ∼ within $D o m_{A}^{B}$ ,
and there exists a function $f_{A}^{B} : D o m_{A}^{B} \to A$ which induces an isomorphism: $\begin{matrix} (D o m_{A}^{B} / \sim; R_{0} / \sim, R_{1} / \sim, \dots) ≅ (A; P_{0}^{A}, P_{1}^{A}, \dots), \end{matrix}$ where $R_{i} / \sim$ stands for the ∼-collapse of $R_{i}$ .

Two structures $A$ and $B$ are infinitary bi-interpretable if they are each effectively interpretable in the other, and moreover, the composition of the interpretations – i.e., the isomorphisms which map $A$ to the copy of $A$ inside the copy of $B$ inside $A$ , and $B$ to the copy of $B$ inside the copy of $A$ inside $B$ – are definable.
Definition 1.2.
Two structures $A$ and $B$ are infinitary bi-interpretable if there are infinitary interpretations of each structure in the other as in Definition 1.1 such that the compositions $\begin{matrix} f_{B}^{A} \circ {\tilde{f}}_{A}^{B} : D o m_{B}^{(D o m_{A}^{B})} \to B and f_{A}^{B} \circ {\tilde{f}}_{B}^{A} : D o m_{A}^{(D o m_{B}^{A})} \to A \end{matrix}$ are $L_{ω_{1} ω}$ -definable in $B$ and $A$ respectively. (Here, we have $D o m_{B}^{(D o m_{A}^{B})} \subseteq {(D o m_{A}^{B})}^{< ω}$ , and ${\tilde{f}}_{A}^{B} : {(D o m_{A}^{B})}^{< ω} \to A^{< ω}$ is the obvious extension of $f_{A}^{B} : D o m_{A}^{B} \to A$ mapping $D o m_{B}^{(D o m_{A}^{B})}$ to $D o m_{B}^{A}$ .)

If we ask that the sets and relations in the interpretation (or bi-interpretation) be (uniformly) relatively intrinsically computable, i.e., definable by both a $Σ_{1}^{c}$ formula and a $Π_{1}^{c}$ formula, then we say that the interpretation (or bi-interpretation) is effective. Any two structures which are effectively bi-interpretable have all of the same computability-theoretic properties; for example, they have the same degree spectra and the same Scott rank. See [10, Lemma 5.3].

Here, we will use interpretations which use (lightface) $Δ_{2}^{c}$ formulas. It is no longer true that any two structures which are $Δ_{2}^{c}$ -bi-interpretable have all of the same computability-theoretic properties, but it is true, for example, that any two such structures either both have computable, or both have non-computable, Scott rank. Theorem 1.3.
Each Abelian p-group is effectively bi-interpretable with a model of $T_{p}$ . Each model of $T_{p}$ is $Δ_{2}^{c}$ -bi-interpretable with the disjoint union of an Abelian p-group and a pure set.
This theorem will follow from the constructions in Sections 3 and 4. Given a model $M$ of $T_{p}$ , $M$ is bi-interpretable with an Abelian p-group G and a pure set. The domain of the copy of G inside of $M$ is definable by a $Σ_{1}^{c}$ formula but not by a $Π_{1}^{c}$ formula. This is the only part of the bi-interpretation which is not effective.
1.3. Classification via Ulm sequences

Let G be an Abelian group. For any ordinal α, we can define $p^{α} G$ – the image of the multiplication-by-p map iterated α times – by transfinite induction:

$p^{0} G = G$ ;

$p^{α + 1} G = p (p^{α} G)$ ;

$p^{β} G = ⋂_{α < β} p^{α} G$ if β is a limit ordinal.

These subgroups

p^{α} G

form a filtration of G. This filtration stabilizes, and we call the smallest ordinal α such that

p^{α} G = p^{α + 1} G

the length of G. We call the intersection

p^{\infty} G

of these subgroups, which is a p-divisible group, the p-divisible part of G. Any countable p-divisible group is isomorphic to some (possibly infinite) direct product of copies of the Prüfer group

\begin{matrix} Z (p^{\infty}) = Z [1 / p, 1 / p^{2}, 1 / p^{3}, \dots] / Z . \end{matrix}

Denote by $G [p]$ the subgroup of G consisting of the p-torsion elements. The αth Ulm invariant $u_{α} (G)$ of G is the dimension of the quotient $\begin{matrix} (p^{α} G) [p] / (p^{α + 1} G) [p] \end{matrix}$ as a vector space over $Z / p Z$ .

Theorem 1.4 (Ulm’s Theorem, see [5]).

Let G and H be countable Abelian p-groups such that for every ordinal α their αth Ulm invariants are equal, and the p-divisible parts of G and H are isomorphic. Then G and H are isomorphic.

1.4. Scott rank and computable infinitary theories

Scott [13] showed that if $M$ is a countable structure, then there is a sentence φ of $L_{ω_{1} ω}$ such that $M$ is, up to isomorphism, the only countable model of φ. We call such a sentence a Scott sentence for $M$ . There are many different definitions [1, Sections 6.6 and 6.7] of the Scott rank of $M$ , which differ only slightly in the ranks they assign. The one we will use, which comes from [11], defines the Scott rank of $A$ to be the least ordinal α such that $A$ has a $Π_{α + 1}^{in}$ Scott sentence. We denote the Scott rank of a structure $A$ by $SR (A)$ . It is always the case that $SR (A) ⩽ ω_{1}^{A} + 1$ [12]. We could just as easily use any of the other definitions of Scott rank; for all of these definitions, given a computable structure $A$ :

$A$ has computable Scott rank if and only if there is a computable ordinal α such that for all tuples $\bar{a}$ in $A$ , the orbit of $\bar{a}$ is defined by a computable $Σ_{α}$ formula.

$A$ has Scott rank $ω_{1}^{C K}$ if and only if for each tuple $\bar{a}$ , the orbit is defined by a computable infinitary formula, but for each computable ordinal α, there is a tuple $\bar{a}$ whose orbit is not defined by a computable $Σ_{α}$ formula.

$A$ has Scott rank $ω_{1}^{C K} + 1$ if and only if there is a tuple $\bar{a}$ whose orbit is not defined by a computable infinitary formula.

Given a structure $M$ , define the computable infinitary theory of $M$ , ${Th}_{\infty} (M)$ , to be collection of computable $L_{ω_{1} ω}$ sentences true of $M$ . We can ask, for a given structure $M$ , whether ${Th}_{\infty} (M)$ is $ℵ_{0}$ -categorical, or whether there are other countable models of ${Th}_{\infty} (M)$ . For $M$ a hyperarithmetic structure:

If $SR (M) < ω_{1}^{C K}$ , then ${Th}_{\infty} (M)$ is $ℵ_{0}$ -categorical. Indeed, $M$ has a computable Scott sentence [12].

If $SR (M) = ω_{1}^{C K}$ , then ${Th}_{\infty} (M)$ may or may not be $ℵ_{0}$ -categorical [6].

If $SR (M) = ω_{1}^{C K} + 1$ , then ${Th}_{\infty} (M)$ is not $ℵ_{0}$ -categorical as $M$ has a non-principal type (in $L_{ω_{1} ω}$ ) which may be omitted.

In the case of Abelian p-groups, we can say something even when we replace the assumption that

M

is hyperarithmetic with the assumption that

ω_{1}^{G} = ω_{1}^{C K}

Definition 1.5 (Definition 6 of [3]).

A class of countable structures has Ulm type if for any two structures $A$ and $B$ in the class, if $ω_{1}^{A} = ω_{1}^{B} = ω_{1}^{C K}$ and ${Th}_{\infty} (A) = {Th}_{\infty} (B)$ , then $A$ and $B$ are isomorphic.

It is well-known that Abelian p-groups are of Ulm type; however, we do not know of a good reference with a complete proof, so we will give one in Section 2. We also note that there are indeed non-hyperarithmetic Abelian p-groups G with

SR (G) < ω_{1}^{C K}

Knight asked whether there was a (non-trivial) first-order theory of Ulm type. By a non-trivial example, we mean that the elementary first-order theory should have non-hyperarithmetic models which are low for $ω_{1}^{C K}$ . Our theory $T_{p}$ is such an example.

Theorem 1.6.
The class of countable models of $T_{p}$ are of Ulm type. Moreover, given $M ⊧ T_{p}$ with $ω_{1}^{C K} = ω_{1}^{M}$ and $SR (M) < ω_{1}^{C K} = ω_{1}^{M}$ , ${Th}_{\infty} (M)$ is $ℵ_{0}$ -categorical.
Proof.
Let $M$ be a model of $T_{p}$ . Now $M$ is bi-interpretable, using computable infinitary formulas, with the disjoint union of an Abelian p-group G and a pure set. Thus $M$ inherits these properties from G (see Theorem 2.1). □
Of course, there will be non-hyperarithmetic models of $T_{p}$ with Scott rank below $ω_{1}^{C K}$ .
1.5. Borel incompleteness

In their influential paper [4], Friedman and Stanley introduced Borel reductions between invariant Borel classes of structures with universe ω in a countable language. Such classes are of the form $Mod (φ)$ , the set of models of φ with universe ω, for some $φ \in L_{ω_{1} ω}$ . A Borel reduction from $Mod (φ)$ to $Mod (ψ)$ is a Borel map $Φ : Mod (φ) \to Mod (ψ)$ such that $\begin{matrix} M ≅ N ⟺ Φ (M) ≅ Φ (N) . \end{matrix}$ If such a Borel reduction exists, we say that $Mod (φ)$ is Borel reducible to $Mod (ψ)$ and write $φ ⩽_{B} ψ$ . If $φ ⩽_{B} ψ$ and $ψ ⩽_{B} φ$ , then we say that $Mod (φ)$ and $Mod (ψ)$ are Borel equivalent and write $φ \equiv_{B} ψ$ . Friedman and Stanley showed that graphs, fields, linear orders, trees, and groups are all Borel equivalent, and form a maximal class under Borel reduction.

If $Mod (φ)$ is Borel complete, then the isomorphism relation on $Mod (φ) \times Mod (φ)$ is $Σ_{1}^{1}$ -complete. The converse is not true, and the most well-known example is Abelian p-groups, whose isomorphism relation is $Σ_{1}^{1}$ -complete but not Borel complete. Until very recently, they were one of the few such examples, and there were no known examples of elementary first-order theories with similar properties. Recently, Laskowski, Rast, and Ulrich [15] gave an example of a first-order theory which is not Borel complete, but whose isomorphism relation is not Borel. Our theory $T_{p}$ is another such example.

Theorem 1.7.
The class of models of $T_{p}$ is Borel equivalent to Abelian p-groups.

Because Abelian p-groups are not Borel complete, but their isomorphism relation is $Σ_{1}^{1}$ -complete, we get:
Corollary 1.8.
The class of models of $T_{p}$ is not Borel complete but the isomorphism relation is $Σ_{1}^{1}$ -complete.

Theorem 1.7 is a specific instance of the following general question asked by Friedman:
Question 1.9.
Is it true that for every $L_{ω_{1} ω}$ sentence there is a Borel equivalent first-order theory?
2. Abelian p-groups are of Ulm type

In this section we will describe a proof of the following well-known theorem, which shows that Abelian p-groups are of Ulm type.

Theorem 2.1.
Let G be an Abelian p-group with $ω_{1}^{C K} = ω_{1}^{G}$ . Then:
G is the only countable model of ${Th}_{\infty} (G)$ with $ω_{1}^{G} = ω_{1}^{C K}$ , and

if $SR (G) < ω_{1}^{C K} = ω_{1}^{G}$ , then ${Th}_{\infty} (G)$ is $ℵ_{0}$ -categorical.

The proof of Theorem 2.1 consists essentially of expressing the Ulm invariants via computable infinitary formulas. Definition 2.2.
Let G be an Abelian p-group. For each ordinal $α < ω_{1}^{C K}$ , there is a computable infinitary sentence $ψ_{α} (x)$ which defines $p^{α} G$ inside of G:
$ψ_{0} (x)$ is just $x = x$ ;

$ψ_{α + 1} (x)$ is $(\exists y) [ψ_{α} (y) \land p y = x]$ ;

$ψ_{β} (x)$ is $⨇_{α < β} ψ_{α} (x)$ for limit ordinals β.

Definition 2.3.
For each ordinal $α < ω_{1}^{C K}$ and $n \in ω \cup {ω}$ , there is a computable infinitary sentence $φ_{α, n}$ such that, for G an Abelian p-group, $\begin{matrix} G ⊧ φ_{α, n} \Leftrightarrow u_{α} (G) = n . \end{matrix}$ For $n \in ω$ , define $φ_{α, ⩾ n}$ to say that there are $x_{1}, \dots, x_{n}$ such that:
$ψ_{α} (x_{1}) \land \dots \land ψ_{α} (x_{n})$ ,

$p x_{1} = \dots = p x_{n} = 0$ , and

for all $c_{1}, \dots, c_{n} \in Z / p Z$ not all zero, $\neg ψ_{α + 1} (c_{1} x_{1} + \dots + c_{n} x_{n})$ .
Then for $n \in ω$ , $φ_{α, n}$ is $φ_{α, ⩾ n} \land \neg φ_{α, ⩾ n + 1}$ , and $φ_{α, ω}$ is $⨇_{n \in ω} φ_{α, ⩾ n}$ .
Lemma 2.4 (Proposition 3.1 of [2] and Theorem 8.17 of [1]).

Let G be an Abelian p-group. Then:

the length of G is at most $ω_{1}^{G}$ , and

if G has length $ω_{1}^{G}$ then G is not reduced (in fact, its p-divisible part has infinite rank) and has Scott rank $ω_{1}^{G} + 1$ .

We are now ready to give the proof of Theorem 2.1.

Proof of Theorem 2.1.
Since $ω_{1}^{C K} = ω_{1}^{G}$ , G has length at most $ω_{1}^{C K}$ . Note that ${Th}_{\infty} (G)$ contains the sentences $φ_{α, u_{α} (G)}$ for $α < ω_{1}^{C K}$ . Thus any model of ${Th}_{\infty} (G)$ has the same Ulm invariants as G, for ordinals below $ω_{1}^{C K}$ .

Suppose that G has length $λ < ω_{1}^{G}$ . Then ${Th}_{\infty} (G)$ includes the computable formula $(\forall x) [ψ_{λ} (x) \leftrightarrow ψ_{λ + 1} (x)]$ , so that any countable model of ${Th}_{\infty} (G)$ has length at most λ. Note that in such a model, $ψ_{λ}$ defines the p-divisible part. Let $n \in ω \cup {ω}$ be such that $p^{\infty} G$ is isomorphic to $Z {(p^{\infty})}^{n}$ . Then, if $n \in ω$ , ${Th}_{\infty} (G)$ contains the formula which says that there are $x_{1}, \dots, x_{n}$ such that
$ψ_{λ} (x_{1}) \land \dots \land ψ_{λ} (x_{n})$ ,

for all $c_{1}, \dots, c_{n} < p$ not all zero and $k_{1}, \dots, k_{n} \in ω$ , $\begin{matrix} \frac{c_{1}}{p^{k_{1}}} x_{1} + \dots + \frac{c_{n}}{p^{k_{n}}} x_{n} \neq 0, \end{matrix}$

for all y with $ψ_{λ} (y)$ , there are $c_{1}, \dots, c_{n} < p$ and $k_{1}, \dots, k_{n} \in ω$ such that $\begin{matrix} y = \frac{c_{1}}{p^{k_{1}}} x_{1} + \dots + \frac{c_{n}}{p^{k_{n}}} x_{n} . \end{matrix}$
If $n = ω$ , then ${Th}_{\infty} (G)$ contains the formula which says that for each $m \in ω$ , there are $x_{1}, \dots, x_{m}$ such that
$ψ_{λ} (x_{1}) \land \dots \land ψ_{λ} (x_{m})$ , and

for all $c_{1}, \dots, c_{m} < p$ not all zero and $k_{1}, \dots, k_{m} \in ω$ , $\begin{matrix} \frac{c_{1}}{p^{k_{1}}} x_{1} + \dots + \frac{c_{m}}{p^{k_{m}}} x_{m} \neq 0 . \end{matrix}$
Any countable model of ${Th}_{\infty} (G)$ has p-divisible part isomorphic to $Z {(p^{\infty})}^{n}$ . So any countable model of ${Th}_{\infty} (G)$ has the same Ulm invariants and p-divisible part as G, and hence is isomorphic to G. Hence ${Th}_{\infty} (G)$ is $ℵ_{0}$ -categorical. In fact, we have shown that there is a single computable infinitary formula which defines G up to isomorphism among countable structures, and $SR (G) < ω_{1}^{C K}$ .

If G has length $ω_{1}^{G} = ω_{1}^{C K}$ , then by the previous lemma, $SR (G) = ω_{1}^{C K} + 1$ . Let H be any other countable model of ${Th}_{\infty} (G)$ with $ω_{1}^{H} = ω_{1}^{G} = ω_{1}^{C K}$ . Thus G and H both have length $ω_{1}^{C K}$ and their p-divisible parts have infinite rank. As remarked before, they have the same Ulm invariants, and so they must be isomorphic.

This argument by cases completes the proof of both (1) and (2). □

3. The theory $T_{p}$

Fix a prime p. The language $L_{p}$ of $T_{p}$ will consist of a constant 0, unary relations $R_{n}$ for $n \in ω$ , and ternary relations $P_{ℓ, m}^{n}$ for $ℓ, m \in ω$ and $n ⩽ max (ℓ, m)$ . The following transformation of an Abelian p-group into an $L_{p}$ -structure will illustrate the intended meaning of the symbols.

Definition 3.1.
Let G be an Abelian p-group. Define $M (G)$ to be the $L_{p}$ -structure with the same domain as G and the symbols of $L_{p}$ interpreted as follows:
Set $0^{M (G)}$ to be the identity element of G.

For each n, let $R_{n}^{M (G)}$ be the elements which are torsion of order exactly $p^{n}$ .

For each $ℓ, m \in ω$ and $n ⩽ max (ℓ, m)$ , and $x, y, z \in G$ , set $P_{ℓ, m}^{n, M (G)} (x, y, z)$ if and only if $x + y = z$ , $x \in R_{ℓ}^{M (G)}$ , $y \in R_{m}^{M (G)}$ , and $z \in R_{n}^{M (G)}$ .

One should think of such $L_{p}$ -structures as the canonical models of $T_{p}$ . The theory $T_{p}$ will consist of following axiom schemata:

For all $ℓ, m, n \in ω$ : $\begin{matrix} (\forall x \forall y \forall z) [P_{ℓ, m}^{n} (x, y, z) \to (R_{ℓ} (x) \land R_{m} (x) \land R_{n} (z))] . \end{matrix}$

( $R_{n}$ contains the elements which are torsion of order exactly $p^{n}$ .) $\begin{matrix} (\forall x) [R_{0} (x) \leftrightarrow x = 0] . \end{matrix}$ and, for all $n ⩾ 1$ : $\begin{matrix} (\forall x) [x \in R_{n} \leftrightarrow [x \neq 0 \land (\exists x_{2} \dots \exists x_{p}) [P_{n, n}^{n} (x, x, x_{2}) \land P_{n, n}^{n} (x, x_{2}, x_{3}) \land \dots \land P_{n, n}^{n - 1} (x, x_{p - 1}, x_{p})]]] . \end{matrix}$

(P defines a partial function.) For all $ℓ, m, n, n^{'} \in ω$ : $\begin{matrix} (\forall x \forall y \forall z \forall z^{'}) [(P_{ℓ, m}^{n} (x, y, z) \land P_{ℓ, m}^{n^{'}} (x, y, z^{'})) \to z = z^{'}] . \end{matrix}$

(P is total.) For all $ℓ, m \in ω$ : $\begin{matrix} (\forall x \forall y) [(R_{ℓ} (x) \land R_{m} (y)) \to \underset{n ⩽ max (ℓ, m)}{⋁} (\exists z) P_{ℓ, m}^{n} (x, y, z)] . \end{matrix}$

(Identity.) For all $ℓ \in ω$ : $\begin{matrix} (\forall x) [R_{ℓ} (x) \to [P_{0, ℓ}^{ℓ} (0, x, x) \land P_{ℓ, 0}^{ℓ} (x, 0, x)]] . \end{matrix}$

(Inverses.) For all $ℓ \in ω$ : $\begin{matrix} (\forall x) (\exists y) [R_{ℓ} (x) \to [P_{ℓ, ℓ}^{0} (x, y, 0) \land P_{ℓ, ℓ}^{0} (y, x, 0)]] . \end{matrix}$

(Associativity.) For all $ℓ, m, n \in ω$ : $\begin{matrix} (\forall x \forall y \forall z) [[R_{ℓ} (x) \land R_{m} (y) \land R_{n} (z)] ⟶ \\ \underset{\begin{array}{c} r ⩽ max (ℓ, m) \\ s ⩽ max (m, n) \\ t ⩽ max (r, n), max (ℓ, s) \end{array}}{⋁} (\exists u \exists v \exists w) [P_{ℓ, m}^{r} (x, y, u) \land P_{r, n}^{t} (u, z, w) \land P_{m, n}^{s} (y, z, v) \land P_{ℓ, s}^{t} (x, v, w)]] . \end{matrix}$

(Abelian.) For all $ℓ, m \in ω$ and $n ⩽ max (ℓ, m)$ : $\begin{matrix} (\forall x \forall y \forall z) [[P_{ℓ, m}^{n} (x, y, z)] \to P_{m, ℓ}^{n} (y, x, z)] . \end{matrix}$

We must now check that the definition of $T_{p}$ works as desired, that is, that if G is an Abelian p-group, then $M (G)$ is a model of $T_{p}$ .
Lemma 3.2.
If G is an Abelian p-group, then $M (G) ⊧ T_{p}$ .
Proof.
We must check that each instance of the axiom schemata of $T_{p}$ holds in $M (G)$ . The proof is straightforward and can easily be skipped.
Suppose that x, y, and z are elements of G with $P_{m, ℓ}^{n, M (G)} (x, y, z)$ . Then, by definition, $x + y = z$ , $x \in R_{ℓ}^{M (G)}$ , $y \in R_{m}^{M (G)}$ , and $z \in R_{n}^{M (G)}$ .

$R_{0}^{M (G)}$ contains the elements of G which are torsion of order $p^{0} = 1$ , so $R_{0}$ contains just the identity. For each $n > 0$ , $R_{n}^{M (G)}$ contains the elements of order exactly $p^{n}$ . An element $x \neq 0$ has order exactly $p^{n}$ if and only if $p x$ has order exactly $p^{n - 1}$ . It remains only to note that if x has order $p^{n}$ , then $x, 2 x, 3 x, \dots, (p - 1) x$ all have order exactly $p^{n}$ as well. The existential quantifier is witnessed by $x_{2} = 2 x$ , $x_{3} = 3 x$ , and so on.

If, for some x, y, z, and $z^{'}$ , $P_{ℓ, m}^{n, M (G)} (x, y, z)$ and $P_{ℓ, m}^{n^{'}, M (G)} (x, y, z^{'})$ , then $x + y = z$ and $x + y = z^{'}$ , so that $z = z^{'}$ .

Given x and y in G which are of order $p^{m}$ and $p^{ℓ}$ respectively, $x + y$ is of order $p^{n}$ for some $n ⩽ max (m, ℓ)$ , and so we have $P_{m, ℓ}^{n, M (G)} (x, y, x + y)$ .

If $x \in G$ is of order $p^{ℓ}$ , then $x + 0 = 0 + x = x$ and so we have $P_{ℓ, 0}^{ℓ, M (G)} (x, 0, x)$ .

If $x \in G$ is of order $p^{ℓ}$ , then $- x$ is also of order $p^{ℓ}$ , and $x + (- x) = 0 = (- x) + x$ . So we have $P_{ℓ, ℓ}^{0, M (G)} (x, - x, 0)$ .

Given $x, y, z \in G$ of order $p^{ℓ}$ , $p^{m}$ , and $p^{n}$ respectively, there are $r ⩽ max (ℓ, m)$ and $s ⩽ max (m, n)$ such that $x + y$ and $y + z$ are of order $p^{r}$ and $p^{s}$ respectively. Then there is t such that $x + y + z$ is of order $p^{t}$ ; $t ⩽ max (r, n)$ and $t ⩽ max (ℓ, s)$ .

Given $x, y, z \in G$ of order $p^{ℓ}$ , $p^{m}$ , and $p^{n}$ respectively, $n ⩽ max (ℓ, m)$ , and with $x + y = z$ , we have $y + x = z$ as G is Abelian.
Thus we have shown that $M (G)$ is a model of $T_{p}$ . □

Note that G and $M (G)$ are effectively bi-interpretable, proving one half of Theorem 1.3.
4. From a model of $T_{p}$ to an Abelian p-group

Given an Abelian p-group G, we have already described how to turn G into a model of $T_{p}$ . In this section we will do the reverse by turning a model of $T_{p}$ into an Abelian p-group.

Definition 4.1.
Let $M$ be a model of $T_{p}$ . Define $G (M)$ to be the group obtained as follows.
The domain of $G (M)$ will be the subset of the domain of $M$ given by $⋃_{n \in ω} R_{n}^{M}$ .

The identity element of $G (M)$ will be $0^{M}$ .

We will have $x + y = z$ in $G (M)$ if and only if, for some ℓ, m, and n, $P_{ℓ, m}^{n, M} (x, y, z)$ .

We will now check that $G (M)$ is always an Abelian p-group.
Lemma 4.2.
If $M$ is a model of $T_{p}$ , then $G (M)$ is an Abelian p-group.
Proof.
First we check that the operation + on $G (M)$ defines a total function. Given $x, y \in G (M)$ , choose ℓ and m such that $x \in R_{ℓ}^{M}$ and $y \in R_{m}^{M}$ . Then by (A3) and (A4), there is a unique $n ⩽ max (ℓ, m)$ and a unique z such that $P_{ℓ, m}^{n, M} (x, y, z)$ . Thus $x + y = z$ , and z is unique.

Second, we check that $G (M)$ is in fact a group. To see that $0^{M}$ is the identity, given $x \in G (M)$ , there is ℓ such that $x \in R_{ℓ}^{M}$ . By (A5), $P_{ℓ, 0}^{ℓ, M} (x, 0^{M}, x)$ and $P_{0, ℓ}^{ℓ, M} (0^{M}, x, 0^{M})$ . Thus $x + 0^{M} = 0^{M} + x = x$ , and $0^{M}$ is the identity of $G (M)$ . To see that $G (M)$ has inverses, given $x \in G (M)$ , there is ℓ such that $x \in R_{ℓ}^{M}$ , and by (A6) there is $y \in R_{ℓ}^{M}$ such that $P_{ℓ, ℓ}^{0, M} (x, y, 0^{M})$ and $P_{ℓ, ℓ}^{0, M} (y, x, 0^{M})$ . Thus $x + y = y + x = 0^{M}$ , and so y is the inverse of x. Finally, to see that $G (M)$ is associative, given $x, y, z \in G (M)$ , there are ℓ, m, and n such that $x \in R_{ℓ}^{M}$ , $y \in R_{m}^{M}$ , and $z \in R_{n}^{M}$ . Then by (A7) there are r, s, and t, and u, v, and w, such that $P_{ℓ, m}^{r, M} (x, y, u)$ , $P_{r, n}^{t, M} (u, z, w)$ , $P_{m, n}^{s, M} (y, z, v)$ , and $P_{ℓ, s}^{t, M} (x, v, w)$ . Thus $x + y = u$ , $u + z = w$ , $y + z = v$ , and $x + v = w$ . So $(x + y) + z = x + (y + z)$ . Thus $G (M)$ is associative.

Third, to see that $G (M)$ is Abelian, let $x, y \in G (M)$ . There are ℓ and m such that $x \in R_{ℓ}^{M}$ and $y \in R_{m}^{M}$ . Let $n ⩽ max (ℓ, m)$ be such that $z = x + y \in R_{n}^{M}$ . (Such an n and z exist by the arguments above that + is total, via (A3) and (A4).) Then $P_{ℓ, m}^{n, M} (x, y, z)$ , and so by (A8), $P_{m, ℓ}^{n, M} (y, x, z)$ . Thus $y + x = z$ and so $G (M)$ is Abelian.

Finally, we need to see that $G (M)$ is a p-group. We claim, by induction on $n ⩾ 0$ , that $R_{n}^{M}$ consists of the elements of $G (M)$ which are of order exactly $p^{n}$ . From this claim, it follows that $G (M)$ is a p-group. For $n = 0$ , the claim follows directly from (A2). Given $n > 0$ , suppose that $x \in R_{n}^{M}$ . Then the witnesses $x_{2}, x_{3}, \dots, x_{p}$ to (A2) must be $2 x, 3 x, \dots, p x$ . Note that since $P_{n, n}^{n - 1, M} (x, (p - 1) x, p x)$ , $p x \in R_{n - 1}^{M}$ . Thus $p x$ is of order exactly $p^{n - 1}$ , and so (since $x \neq 0$ ) x is of order exactly $p^{n}$ . On the other hand, if x is of order exactly $p^{n}$ , then $p x$ is of order exactly $p^{n - 1}$ and so $p x \in R_{n - 1}^{M}$ . Moreover, $x_{2} = 2 x, x_{3} = 3 x, \dots, x_{p - 1} = (p - 1) x$ are all of order exactly $p^{n}$ . So we have $P_{n, n}^{n, M} (x, x, x_{2}), P_{n, n}^{n, M} (x, x_{2}, x_{3}), \dots,, P_{n, n}^{n - 1, M} (x, x_{p - 1}, x_{p})$ . By (A2), $x \in R_{n}^{M}$ . This completes the inductive proof. □

We now have two operations, one which turns an Abelian p-group into a model of $T_{p}$ , and another which turns a model of $T_{p}$ into an Abelian p-group. These two operations are almost inverses to each other. If we begin with an Abelian p-group, turn it into a model of $T_{p}$ , and then turn that model into an Abelian p-group, we will obtain the original group. However, if we start with a $M$ model of $T_{p}$ , turn it into an Abelian p-group, and then turn that Abelian p-group into a model of $T_{p}$ , we may obtain a different model of $T_{p}$ . The problem is that the of elements of $M$ which are not in any of the sets $R_{n}^{M}$ are discarded when we transform $M$ into an Abelian p-group. However, these elements form a pure set, and so the only pertinent information is their size.
Definition 4.3.
Given a model $M$ of $T_{p}$ , the pure set size of $M$ , $# M \in ω \cup {\infty}$ , is the number of elements of M not in any relation $R_{n}$ .
Lemma 4.4.
Given an Abelian p-group G, $G (M (G)) = G$ .
Proof.
Since $# M (G) = 0$ , we see that G, $M (G)$ , and $G (M (G))$ all have the same domain. The identity of $G (M (G))$ is $0^{M (G)}$ which is the identity of G. If $x + y = z$ in G, then, for some $ℓ, m, n \in ω$ , we have $P_{ℓ, m}^{n, M (G)} (x, y, z)$ . Thus, in $G (M (G))$ , we have $x + y = z$ . So $G (M (G)) = G$ . □

We make a simple extension to $M$ as follows.
Definition 4.5.
Let G be an Abelian p-group and $m \in ω \cup {\infty}$ . Define $M (G, m)$ to be $L_{p}$ -structure with domain $G \cup {a_{1}, \dots, a_{m}}$ with the relations interpreted as in $M (G)$ . Thus, no relations hold of any of the elements $a_{1}, \dots, a_{m}$ .
Lemma 4.6.
Given a model $M$ of $T_{p}$ , $M (G (M), # M) ≅ M$ .
Proof.
We will show that if $# M = 0$ , then $M (G (M)) = M$ . From this one can easily see that $M (G (M), # M) ≅ M$ in general.

If $# M = 0$ , then $M$ , $G (M)$ , and $M (G (M))$ all share the same domain. It is clear that $0^{M} = 0^{G (M)} = 0^{M (G (M))}$ . From the proof of Lemma 4.2, we see that for each n, $R_{n}^{M}$ defines the set of elements of $G (M)$ which are torsion of order $p^{n}$ , and so $R_{n}^{M} = R_{n}^{M (G (M))}$ . Given $ℓ, m \in ω$ and $n ⩽ max (ℓ, m)$ , and x, y, and z elements of the shared domain, we have $P_{ℓ, m}^{n, M} (x, y, z)$ if and only if $\begin{matrix} x + y = z in G (M) and x \in R_{ℓ}^{M}, y \in R_{m}^{M}, and z \in R_{n}^{M} . \end{matrix}$ Since $R_{i}^{M} = R_{i}^{M (G (M))}$ for each i, this is the case if and only if $P_{ℓ, m}^{n, M (G (M))} (x, y, z)$ . Thus we have shown that $M (G (M)) = M$ . □

Note that $M$ and the disjoint union of $G (M)$ with a pure set of size $# M$ are bi-interpretable, using computable infinitary formulas, completing the proof of Theorem 1.3.
5. Borel equivalence

In this section we will prove Theorem 1.7 by showing that the class of models of $T_{p}$ and the class of Abelian p-groups are Borel equivalent. $G \mapsto G (M (G)) = G (M (G, 0))$ is a Borel reduction from isomorphism on Abelian p-groups to isomorphism on models of $T_{p}$ . However, $M \mapsto G (M)$ is not a Borel reduction in the other direction, because two non-isomorphic models of $T_{p}$ might be mapped to isomorphic groups. We need to find a way to turn $G (M)$ and $# M$ into an Abelian p-group $H (G (M), # M)$ , so that $M$ and $# M$ can be recovered from $H (G (M), # M)$ .

We will define $H (G, m)$ for any Abelian p-group H and $m \in ω \cup {\infty}$ . It is helpful to think about what this reduction will do to the Ulm invariants: The first Ulm invariant of $H (G, m)$ will be m, and for each α, then $1 + α th$ Ulm invariant of $H (G, m)$ will be the same as the αth Ulm invariant of G.

Definition 5.1.

Given an Abelian p-group G, and $m \in ω \cup {\infty}$ , define an Abelian p-group $H (G, m)$ as follows. Let $\hat{B}$ be a basis for the $Z_{p}$ -vector space $G / p G$ . Let $B \subseteq G$ be a set of representatives for $\hat{B}$ . Let $G^{*}$ be the Abelian group $⟨ G, a_{b} : b \in B ∣ p a_{b} = b ⟩$ . Then define $H (G, m) = G^{*} \oplus {(Z_{p})}^{m}$ .

To make this Borel, we can take $B$ to be the lexicographically first set of representatives for a basis. It will follow from Lemma 5.4 that the isomorphism type of $H (G, m)$ does not depend on these choices. First, we require a couple of lemmas.

Lemma 5.2.

Each element of G can be written uniquely as a (finite) linear combination $h + \sum_{b \in B} x_{b} b$ where $h \in p G$ and each $x_{b} < p$ .

Proof.

Given $g \in G$ , let $\hat{g}$ be the image of g in $G / p G$ . Then, since $\hat{B}$ is a basis for $G / p G$ , we can write $\begin{matrix} \hat{g} = \sum_{b \in B} x_{b} \hat{b} \end{matrix}$ with $x_{b} < p$ , where $\hat{b}$ is the image of b in $G / p G$ . Thus setting $\begin{matrix} h = g - \sum_{b \in B} x_{b} b \in p G \end{matrix}$ we get a representation of g as in the statement of the theorem.

To see that this representation is unique, suppose that $\begin{matrix} h + \sum_{b \in B} x_{b} b = h^{'} + \sum_{b \in B} y_{b} b . \end{matrix}$ Then, modulo $p G$ , $\begin{matrix} \sum_{b \in B} x_{b} \hat{b} = \sum_{b \in B} y_{b} \hat{b} . \end{matrix}$ Since $\hat{B}$ is a basis, $x_{b} = y_{b}$ for each $b \in B$ . Then we get that $h = h^{'}$ and the two representations are the same. □

Lemma 5.3.

Each element of $G^{*}$ can be written uniquely in the form $h + \sum_{b \in B} x_{b} a_{b}$ where $h \in G$ and each $x_{b} < p$ .

Proof.

It is clear that each element of $G^{*}$ can be written in such a way. If $\begin{matrix} h + \sum_{b \in B} x_{b} a_{b} = h^{'} + \sum_{b \in B} y_{b} a_{b} \end{matrix}$ then, in G, $\begin{matrix} p h + \sum_{b \in B} x_{b} b = p h^{'} + \sum_{b \in B} y_{b} b . \end{matrix}$ This representation is unique, so $x_{b} = y_{b}$ for each $b \in B$ , and so $h = h^{'}$ . □

Lemma 5.4.

The isomorphism type of $H (G, m)$ depends only on the isomorphism type of G, and not on the choice of $B$ .

Proof.

It suffices to show that if $C$ is another choice of representatives for a basis of $G / p G$ , then $G_{B}^{*} = G_{C}^{*}$ , where the former is constructed using $B$ , and the later is constructed using $C$ . Let $f : B \to C$ be an bijection.

Given $g \in G_{B}^{*}$ , write $g = g^{'} + \sum_{b \in B} x_{b} a_{b}$ with $g^{'} \in G$ and $0 ⩽ x_{b} < p$ . This representation of g is unique by Lemma 5.3. Define $φ (g) = g^{'} + \sum_{b \in B} x_{b} a_{f (b)}$ . It is not hard to check that φ is a homomorphism. The inverse of φ is the map ψ which is defined by $ψ (h) = h^{'} + \sum_{c \in C} y_{c} a_{f^{- 1} (c)}$ where $h = h^{'} + \sum_{c \in C} y_{c} a_{c}$ . □

The next two lemmas will be used to show that if G is not isomorphic to $G^{'}$ , or if m is not equal to $m^{'}$ , then $H (G, m)$ will not be isomorphic to $H (G^{'}, m^{'})$ .

Lemma 5.5.

$G = p G^{*}$ .

Proof.

Each element of G can be written as $g + \sum_{b \in B} x_{b} b$ with $g \in p G$ . Let $g^{'} \in G$ be such that $p g^{'} = g$ . Then $\begin{matrix} p (g^{'} + \sum_{b \in B} x_{b} a_{b}) = g + \sum_{b \in B} x_{b} b . \end{matrix}$ Hence $G \subseteq p G^{*}$ . Given $h \in G^{*}$ , write $h = g + \sum_{b \in B} x_{b} a_{b}$ . Then $p h = p g + \sum_{b \in B} x_{b} b \in G$ . So $p G^{*} \subseteq G$ , and so $G = p G^{*}$ . □

If G is a group, recall that we denote by $G [p]$ the elements of G which are torsion of order p.

Lemma 5.6.

$H (G, m) [p] / (p H (G, m)) [p] ≅ {(Z_{p})}^{m}$ .

Proof.

Note that $\begin{matrix} H (G, m) [p] / (p H (G, m)) [p] & ≅ (G^{*} [p] / (p G^{*}) [p]) \oplus ({(Z_{p})}^{m} [p] / (p {(Z_{p})}^{m}) [p]) \\ ≅ (G^{*} [p] / G [p]) \oplus {(Z_{p})}^{m} . \end{matrix}$ We will show that $(G^{*} [p] / G [p])$ is the trivial group by showing that if $g \in G^{*}$ , $p g = 0$ , then $g \in G$ . Indeed, write $g = g^{'} + \sum_{b \in B} y_{b} a_{b}$ with $g^{'} \in G$ . Then $\begin{matrix} 0 = p g = p g^{'} + \sum_{b \in B} p y_{b} a_{b} = p g^{'} + \sum_{b \in B} y_{b} b . \end{matrix}$ Since $0 \in p G$ has a unique representation (by Lemma 5.2) $0 = 0 + \sum_{b \in B} 0 b$ , we get that $y_{b} = 0$ for each $b \in B$ , and so $g = g^{'} \in G$ . □

By the previous lemma, we can recover m from $H (G, m)$ . We have $\begin{matrix} p H (G, m) = p G^{*} \oplus p {(Z_{p})}^{m} ≅ p G^{*} = G \end{matrix}$ so that we can also recover G.

Thus, using Lemma 4.6, $M \mapsto H (G (M), # M)$ gives a Borel reduction from $T_{p}$ to Abelian p-groups. This completes the proof of Theorem 1.7.

References

C.J.

Ash and

J.F.

Knight, Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, Vol. 144, North-Holland Publishing Co., Amsterdam, 2000.

Calvert,

S.S.

Goncharov and

J.F.

Knight, Computable structures of Scott rank ω₁^CK in familiar classes, in: Advances in Logic, Contemp. Math., Vol. 425, Amer. Math. Soc., Providence, RI, 2007, pp. 49–66. doi:10.1090/conm/425/08117.

Fokina,

J.F.

Knight,

Melnikov,

S.M.

Quinn and

Safranski, Classes of Ulm type and coding rank-homogeneous trees in other structures, J. Symbolic Logic76(3) (2011), 846–869. doi:10.2178/jsl/1309952523.

Friedman and

Stanley, A Borel reducibility theory for classes of countable structures, J. Symbolic Logic54(3) (1989), 894–914. doi:10.2307/2274750.

Fuchs, Infinite Abelian Groups. Vol. I, Pure and Applied Mathematics, Vol. 36, Academic Press, New York-London, 1970.

Harrison-Trainor,

Igusa and

J.F.

Knight, Some new computable structures of high rank, Proc. Amer. Math. Soc.146(7) (2018), 3097–3109. doi:10.1090/proc/13967.

Harrison-Trainor,

Miller and

Montalbán, Borel functors and infinitary interpretations, Preprint.

Harrison-Trainor,

Melnikov,

Miller and

Montalbán, Computable functors and effective interpretability, J. Symbolic Logic82(1) (2017), 77–97. doi:10.1017/jsl.2016.12.

Marker, Model Theory: An Introduction, Graduate Texts in Mathematics, Springer, 2002.

10.

Montalbán, Computability theoretic classifications for classes of structures, Proceedings of ICM 20142(2014), 79–101.

11.

Montalbán, A robuster Scott rank, Proc. Amer. Math. Soc.143(12) (2015), 5427–5436. doi:10.1090/proc/12669.

12.

Nadel, Scott sentences and admissible sets, Ann. Math. Logic7 (1974), 267–294. doi:10.1016/0003-4843(74)90017-5.

13.

Scott, Logic with denumerably long formulas and finite strings of quantifiers, in: Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), North-Holland, Amsterdam, 1965, pp. 329–341.

14.

Ulm, Zur Theorie der abzählbar-unendlichen Abelschen Gruppen, Math. Ann.107(1) (1933), 774–803. doi:10.1007/BF01448919.

15.

Ulrich,

Rast and

M.C.

Laskowski, Borel complexity and potential canonical scott sentences, Fundamenta Mathematicae239(2017), 101–147. doi:10.4064/fm326-11-2016.