Degrees of categoricity above limit ordinals

Abstract

A computable structure $A$ has degree of categoricity d if d is exactly the degree of difficulty of computing isomorphisms between isomorphic computable copies of $A$ . Fokina, Kalimullin, and Miller showed that every degree d.c.e. in and above $0^{(n)}$ , for any $n < ω$ , and also the degree $0^{(ω)}$ , are degrees of categoricity. Later, Csima, Franklin, and Shore showed that every degree $0^{(α)}$ for any computable ordinal α, and every degree d.c.e. in and above $0^{(α)}$ for any successor ordinal α, is a degree of categoricity. We show that every degree c.e. in and above $0^{(α)}$ , for α a limit ordinal, is a degree of categoricity. We also show that every degree c.e. in and above $0^{(ω)}$ is the degree of categoricity of a prime model, making progress towards a question of Bazhenov and Marchuk.

Keywords

Degrees of categoricity limit ordinals

1. Introduction

Isomorphisms of the vector space $Q^{N}$ are easy to understand: given two presentations of this vector space, one chooses a basis of each and then bijectively identifies basis elements from one presentation with basis elements from the other, in any manner one likes. Finally, the map is extended linearly to produce the full isomorphism. This classical method is straightforward, but could a computer be given this task and create such an isomorphism? That is, if the presentations of $Q^{N}$ are computable – so the computer knows simple facts about each copy – could we write a program that would provide an effective isomorphism, outputting the corresponding element in the second copy when given some element in the first copy as input?

The answer is no. It has long been known that there are two computable presentations of $Q^{N}$ , one with a computable basis, and the other without a computable basis. Certainly there can be no computable isomorphism between these presentations, as the image of the computable basis from the first presentation would be a computable basis in the second presentation. Indeed the problem of building an isomorphism between two computable presentations of $Q^{N}$ amounts to computing bases for each of them, since the process of matching bases and extending linearly is effective; a computer could easily be given an algorithm explaining how to do this. To give a basis of a computable presentation of $Q^{N}$ requires only the ability to answer single quantifier questions: Is the next potential basis member a linear combination of what we have already included? The Turing degree of the Halting set, denoted $0^{'}$ , is able to answer such questions. We say that $Q^{N}$ is $0^{'}$ -computably categorical because we can compute, using $0^{'}$ , an isomorphism between any two computable presentations. More generally:

Definition 1.1.
Let d be a Turing degree. A computable structure $A$ is d-computably categorical if, for every computable copy $B$ of $A$ , there is a d-computable isomorphism between $A$ and $B$ .

For many structures $A$ , there is a least degree d such that $A$ is d-computably categorical. In the case of $Q^{N}$ , there are actually two computable presentations of $Q^{N}$ such that any isomorphism between the two computes $0^{'}$ . So $0^{'}$ is exactly the difficulty of computing isomorphisms between copies of $Q^{N}$ . This natural idea was formalized by Fokina, Kalimullin, and Miller [6].
Definition 1.2 (Fokina, Kalimullin, and Miller [6]).

A Turing degree d is said to be the degree of categoricity of a computable structure $A$ if d is the least degree such that $A$ is d-computably categorical.

The Turing degree $0^{'}$ , the level of complexity of the Halting set, is arguably the most natural Turing degree after $0$ , the degree of the computable sets. The jump operator in computability theory takes a set A to the halting set relative to A, denoted $A^{'}$ , and gives rise to a corresponding operator on Turing degrees. Iterating the jump operator n times on $0$ is called the n-th jump of $0$ , denoted $0^{(n)}$ . Taking unions at limit ordinals, one can define $0^{(α)}$ for any computable ordinal α. It turns out that these definitions are very robust, see Ash and Knight [1]. These Turing degrees are very natural. Just as $0^{'}$ is able to answer single-quantifier questions, $0^{(n)}$ can answer questions expressible with n alternating quantifiers.

Fokina, Kalimullin, and Miller showed that every degree that can be realized as a difference of computably enumerable (d.c.e.) sets in and above $0^{(n)}$ , for any $n < ω$ , and also the degree $0^{(ω)}$ , are degrees of categoricity. Later, Csima, Franklin, and Shore [4] showed that every degree $0^{(α)}$ for any computable ordinal α, and every degree d.c.e. in and above $0^{(α)}$ for any successor ordinal α, is a degree of categoricity. Csima and Ng have announced a proof that every $Δ_{2}^{0}$ degree is a degree of categoricity.

It is often the case when trying to prove some property $P (α)$ for ordinals α that things get tricky at limit ordinals. Roughly speaking, if α is a successor ordinal and we know something must happen before α, we can safely say it has happened by $α - 1$ . For α a limit ordinal, in such a situation there is no canonical choice of earlier ordinal to look at. This is why the methods of [4] did not work above limit ordinals.

Our main result in this paper is:

Theorem 1.3.
Let α be a computable limit ordinal and d a degree c.e. in and above $0^{(α)}$ . There is a computable structure with (strong) degree of categoricity d .

This fills in a gap that was missing from [4] above limit ordinals, making further progress towards Question 5.1 of that paper.

We have not yet explained what a strong degree of categoricity is. For a long time, all of the known examples had the following property: If $A$ had degree of categoricity d, then there is a copy $B$ of $A$ such that every isomorphism between $A$ and $B$ computes d. Thus, we can witness with just two computable copies the fact that d is the least degree such that $A$ is d-computably categorical. In this case, we say that $A$ has strong degree of categoricity d. Recently, Bazhenov, Kalimullin, and Yamaleev [3] have shown that there is a c.e. degree d and a structure $A$ with degree of categoricity d, but d is not a strong degree of categoricity for $A$ . Csima and Stephenson [5] have shown that there is a structure of finite computable dimension that has a degree of categoricity but no strong degree of categoricity.

Recall that the theory of a structure is the set of first order sentences true in the structure, and that models of the same theory need not be isomorphic. The type of a tuple in a structure is the set of formulas (with the appropriate number of free variables) that the tuple satisfies in the structure. The types of a theory are the types that are realized by models of the theory. A type is called principal if there is one formula from which the rest follow. A model of a theory is prime if it elementarily embeds into all other models of the theory, and when everything is countable, this is the same as saying that the model only realizes principal types. In a sense, prime structures are the most basic or natural structures. Our second result gives progress towards a question of Bazhenov and Marchuk.
Question (Bazhenov and Marchuk [2]).

What can be the degrees of categoricity of computable prime models?

A computable prime model – in fact, as [2] shows, a computable homogeneous model – is always $0^{(ω + 1)}$ -categorical, as we can ask $0^{(ω + 1)}$ if two tuples satisfy the same type. Bazhenov and Marchuk construct a computable homogeneous model with degree of categoricity $0^{(ω + 1)}$ . The complexity here is in the structure itself, rather than in the theory. To build a prime model with degree of categoricity $0^{(ω + 1)}$ , the complexity must be in the theory: If $A$ is a computable prime model of a theory T, then $A$ is $T^{'} \oplus 0^{(ω)}$ -categorical as $T^{'}$ can decide whether a formula is complete, and $0^{(ω)}$ can decide whether a formula holds of a tuple in $A$ . We build a computable prime model with degree of categoricity $0^{(ω + 1)}$ (or any other degree c.e. in and above $0^{(ω)}$ ), showing that the bound cannot be lowered.

Theorem 1.4.
Let d be a degree c.e. in and above $0^{(ω)}$ . There is a computable prime model $A$ with strong degree of categoricity d .

Bazhenov and Marchuk stated in [2] that a careful examination of the structures constructed in [6] shows they are prime models, so that all degrees d.c.e. in and above $0^{(n)}$ for a finite n, as well as $0^{(ω)}$ , are strong degrees of categoricity of prime models. Along the way to proving Theorem 1.4 we verify in Lemma 3.3 that the building blocks used by Csima, Franklin and Shore for their examples in [4] are prime. This is enough to see that their structures realizing degrees of categoricity less than or equal to $0^{(ω)}$ are prime. However, the structure in [4] with degree of categoricity $0^{(ω + 1)}$ is not prime. With Theorem 1.4, we see that all known degrees of categoricity less than or equal to the $0^{(ω + 1)}$ bound can be realized by a prime model.
2. Categoricity relative to decidable models

As a warm-up to illustrate the methods used to prove these two theorems, we give a simple proof of a result of Goncharov [7] that for every c.e. degree d, there is a decidable prime model with degree of categoricity d with respect to decidable copies. Recall that a structure is said to be decidable if its full elementary diagram is computable. In [7], Goncharov made the following definitions:

Definition 2.1.
Let d be a Turing degree and $A$ a decidable structure. Then $A$ is d-categorical with respect to decidable copies if for every decidable copy $B$ of $A$ , d computes an isomorphism between $A$ and $B$ .
Definition 2.2.
Let d be a Turing degree and $A$ a decidable structure. Then d is the degree of categoricity of $A$ with respect to decidable copies if:
$A$ is d-categorical with respect to decidable copies, and

whenever $A$ is c-categorical with respect to decidable copies, $c ⩾ d$ .

It is not hard to see that between any two decidable copies of a prime model, there is a $0^{'}$ -computable isomorphism. Goncharov showed that any c.e. degree can be the degree of categoricity with respect to decidable copies of a prime model. We give a different proof, which we think is simpler, and which demonstrates some of the techniques that we will use later. Theorem 2.3 (Goncharov [7, Theorem 3]).

Let d be a c.e. degree. Then there is a decidable prime model $M$ which has strong degree of categoricity d with respect to decidable models.

Proof.
Let $D \in d$ be a c.e. set. We will construct the structures $M$ and $N$ . They are the disjoint union of infinitely many structures $M_{n}$ and $N_{n}$ , with $M_{n}$ and $N_{n}$ picked out by unary relations $R_{n}$ . The nth sort will code whether $n \in D$ . Fix n. $M_{n}$ will have infinitely many elements ${(a_{i})}_{i \in ω}$ . There will be infinitely many unary relations ${(U_{ℓ})}_{ℓ \in ω}$ defined on $M_{n}$ so that: $\begin{matrix} a_{0} \in U_{s} ⟺ n \in D_{at s} \end{matrix}$ where $n \in D_{at s}$ means that n enters D at exactly stage s, and $\begin{matrix} a_{i} \notin U_{s} for i > 0 and all s . \end{matrix}$ Similarly, $N_{n}$ will have infinitely many elements ${(b_{i})}_{i \in ω}$ with the unary relations defined so that: $\begin{matrix} b_{i} \in U_{s} ⟺ i = s and n \in D_{at s} . \end{matrix}$ It is easy to see that we can build computable copies of $M$ and $N$ . These copies are in fact decidable. Claim 1.
$M$ and $N$ are decidable.
Proof.
Given a formula $φ (x_{1}, \dots, x_{n})$ with k quantifiers and $a_{i_{1}}, \dots, a_{i_{n}} \in M$ , it is not hard to see that $M ⊧ φ (a_{i_{1}}, \dots, a_{i_{n}})$ if and only if the finite substructure $M^{'}$ of $M$ whose domain consists of $a_{0}, \dots, a_{k + n}$ and $a_{i_{1}}, \dots, a_{i_{n}}$ also has $M^{'} ⊧ φ (a_{i_{1}}, \dots, a_{i_{n}})$ . Thus $M$ is decidable.

For $N$ , suppose we have a formula $φ (x_{1}, \dots, x_{n})$ with at most k quantifiers and which uses only some subset of the relations $U_{0}, \dots, U_{k}$ . Let $b_{i_{1}}, \dots, b_{i_{n}}$ be elements of $N$ . Then $N ⊧ φ (b_{i_{1}}, \dots, b_{i_{n}})$ if and only if the finite substructure $N^{'}$ of $M$ whose domain consists of $b_{0}, \dots, b_{k + n}$ and $b_{i_{1}}, \dots, b_{i_{n}}$ also has $N^{'} ⊧ φ (b_{i_{1}}, \dots, b_{i_{n}})$ . Thus $N$ is decidable. □
Claim 2.
$M$ and $N$ are isomorphic.
Proof.
It suffices to show that for each n, $M_{n}$ and $N_{n}$ are isomorphic. If $n \notin D$ , then $a_{i} \mapsto b_{i}$ induces an isomorphism between $M_{n}$ and $N_{n}$ . If $n \in D_{at s}$ , then the map $\begin{array}{l} a_{0} & \mapsto b_{s}, \\ a_{i} & \mapsto b_{i - 1} & when 0 < i ⩽ s, \\ a_{i} & \mapsto b_{i} & when i > s \end{array}$ is an isomorphism between $M_{n}$ and $N_{n}$ . □
Claim 3.
$M$ and $N$ are prime.
Proof.
It suffices to show that each $M_{n}$ and $N_{n}$ are prime, since these structures are determined inside $M$ and $N$ uniquely by the relation $R_{n}$ . It is not hard to see that $M_{n}$ and $N_{n}$ are models of an $ℵ_{0}$ -categorical theory, and hence are prime. □
Claim 4.
Any isomorphism between $M$ and $N$ can compute D.
Proof.
Let g be an isomorphism between $M$ and $N$ . For each n, let ${(a_{i})}_{i \in ω}$ and ${(b_{i})}_{i \in ω}$ be the elements in the definition of $M_{n}$ and $N_{n}$ . Let s be such that $g (a_{0}) = b_{s}$ . Then $n \in D$ if and only if $n \in D_{s}$ . □
Claim 5.
Given a computable copy $\tilde{M}$ of $M$ , D can compute an isomorphism between $M$ and $\tilde{M}$ .
Proof.
For each n, let ${\tilde{M}}_{n}$ be the structure with domain $R_{n}$ in $\tilde{M}$ . It suffices to compute an isomorphism g between $M_{n}$ and ${\tilde{M}}_{n}$ for each n. Let ${(c_{i})}_{i \in ω}$ be the elements of ${\tilde{M}}_{n}$ . If $n \notin D$ , no relation $U_{j}$ holds of any of the elements ${(a_{i})}_{i \in ω}$ or ${(c_{i})}_{i \in ω}$ . So $a_{i} \mapsto c_{i}$ is an isomorphism. On the other hand, if $n \in D$ , then for some unique s, $a_{0} \in U_{s}$ . We can look for $c_{k}$ such that $c_{k} \in U_{s}$ . Map $a_{0}$ to $c_{k}$ ; map each other $a_{i}$ to some other $c_{i}$ . □

These claims complete the proof of the theorem. □

3. Back-and-forth trees

Fix a path through O. We will identify computable ordinals with their notation on this path. We will always first fix a limit ordinal α and work below it. Recall that one can decide effectively whether a given computable ordinal is a limit ordinal or a successor ordinal. For each limit ordinal $β < α$ , fix a fundamental sequence for β, that is, an increasing sequence of successor ordinals whose limit is β.

Hirschfeldt and White defined, for each successor ordinal β, a pair of trees $A_{β}$ and $E_{β}$ which can be differentiated exactly by β jumps. These trees are called back-and-forth trees.

Definition 3.1 ([9, Definition 3.1]).

Back-and-forth trees are defined recursively in β. We view these as structures in the language of graphs with the root node distinguished.

We take $A_{1}$ to be the tree with just a root node and no children, and we take $E_{1}$ to be the tree where the root node has infinitely many children, none of which have children. See Fig. 1. We say that these trees have back-and-forth rank 1.

Suppose β is a successor ordinal. Define $A_{β + 1}$ as a root node with infinitely many children, each the root of a copy of $E_{β}$ , and define $E_{β + 1}$ as a root node with infinitely many children, each the root of a copy of $A_{β}$ , and also infinitely many other children, each the root of a copy of $E_{β}$ . See Fig. 2. These trees have back-and-forth rank $β + 1$ .

Now suppose β is a non-zero limit ordinal, and let $β_{0}, β_{1}, \dots$ be a fundamental sequence of successor ordinals for β, that is, a sequence of successor ordinals below β with limit β. We first define a family of helper trees $L_{β, k}$ where $k \in ω \cup {\infty}$ . Define $L_{β, \infty}$ to consist of a root node whose children are root nodes of copies of $A_{β_{i}}$ , and such that each copy appears exactly once as a child. For $k \in ω$ , $L_{β, k}$ has a root node whose children are root nodes of copies of $A_{β_{0}}, \dots, A_{β_{k}}, E_{β_{k + 1}}, E_{β_{k + 2}}, \dots$ where again each copy appears exactly once as a child. Such trees are shown in Fig. 3. We say these trees have back-and-forth rank β.

We can now define $A_{β + 1}$ and $E_{β + 1}$ for the non-zero limit ordinal β. For $A_{β + 1}$ , we have a root node with infinitely many children, each the root node of a copy of $L_{β, k}$ such that for each $k \in ω$ , $L_{β, k}$ appears infinitely many times. The definition of $E_{β + 1}$ is similar, except k is drawn from $ω \cup {\infty}$ . See Fig. 4. These trees have back-and-forth rank $β + 1$ .

Figure 1.

$A_{1}$ and $E_{1}$ .

Figure 2.

$A_{β + 1}$ and $E_{β + 1}$ when β is a successor ordinal.

Figure 3.

Helper trees $L_{β, \infty}$ and $L_{β, k}$ for $k \in ω$ for the non-zero limit ordinal β.

Figure 4.

$A_{β + 1}$ and $E_{β + 1}$ for the non-zero limit ordinal β.

The next two lemmas piece together the facts that we will need about the back-and-forth trees, first for arbitrary β, and second some additional properties for finite β in particular. These facts come from [9] and [4].

Lemma 3.2.

Let α be a computable ordinal. For a successor ordinal $β < α$ , the structures $A_{β}$ and $E_{β}$ satisfy the following properties:

Uniformly in β and an index for a $Σ_{β}^{0}$ set S, there is a computable sequence of structures $C_{x}$ such that $\begin{matrix} x \in S ⟺ C_{x} ≅ E_{β} and x \notin S ⟺ C_{x} ≅ A_{β} . \end{matrix}$

Uniformly in β, there is a $Σ_{β}^{0}$ sentence φ such that $E_{β} ⊧ φ$ and $A_{β} ⊭ φ$ .

$A_{β}$ and $E_{β}$ are uniformly $0^{(β)}$ -categorical.

Proof.

For (1), take ${(C_{x})}_{x}$ to be the computable sequence of trees given by Proposition 3.2 in [9].

For (2), take φ to be the sentence given by evaluating the formula guaranteed by Lemma 3.5 in [9] for $B = E_{β}$ at its own root node. The complexity of φ is the natural complexity of $E_{β}$ , which is $Σ_{β}$ . This lemma says that for any tree $T$ , $T ⊧ φ$ if and only if $T ≅ E_{β}$ .

Finally, for (3), we use a result from Csima, Franklin, and Shore [4] about back-and-forth trees. We will consider $A_{β}$ ; the case for $E_{β}$ is identical. We have that $A_{β}$ is a back-and-forth tree, and hence if $C$ is a computable structure isomorphic to $A_{β}$ , then it is also a computable back-and-forth tree. Corollary 2.6 in [4] allows $\emptyset^{(γ)}$ to uniformly compute an isomorphism between these two trees when the back-and-forth rank of the trees is at most γ. Since the rank of $A_{β}$ is β by construction, the isomorphism is uniformly computable in $0^{(β)}$ . □

Now for finite ordinals β (and writing n for β), we have some additional properties. We will state the lemma in full, including properties that were covered by the previous lemma. We think that these facts are well-known, but we do not know of a reference in print.

Lemma 3.3.

For $0 < n < ω$ , the structures $A_{n}$ and $E_{n}$ satisfy the properties:

Uniformly in n and an index for a $Σ_{n}^{0}$ set S, there is a computable sequence of structures $C_{x}$ such that $\begin{matrix} x \in S ⟺ C_{x} ≅ E_{n} and x \notin S ⟺ C_{x} ≅ A_{n} . \end{matrix}$

For each n, there is an elementary first-order $\exists_{n}$ sentence $φ_{n}$ , computable uniformly in n, such that $E_{n} ⊧ φ$ and $A_{n} ⊭ φ$ .

$A_{n}$ and $E_{n}$ are prime.

$A_{n}$ and $E_{n}$ are $0^{(n)}$ -categorical uniformly in n.

Proof.

(1) and (4) are the same as in the previous lemma. We show using induction on n that these sequences satisfy (2) and (3) as well. It is easy to see that $A_{1}$ and $E_{1}$ are prime models of their theories and that they are distinguishable (in the sense of (2) in the statement of the lemma) by the existential sentence $φ_{1} : = \exists x \exists y (x \neq y)$ . Assume now that $A_{n}$ and $E_{n}$ are prime and distinguishable by a first-order $\exists_{n}$ sentence $φ_{n}$ (in the sense that $E_{n} ⊧ φ_{n}$ but $A_{n} ⊭ φ_{n}$ ). We show that $A_{n + 1}$ and $E_{n + 1}$ are prime and distinguishable by a first-order $\exists_{n + 1}$ sentence $φ_{n + 1}$ .

It is not hard to see that we can take $φ_{n + 1}$ to be the sentence $\exists x \neg φ_{n} [⪯ x] \land (x is a child of the root node)$ where x is a new variable not appearing in $φ_{n}$ and $φ_{n} [⪯ x]$ is the formula obtained from $φ_{n}$ by bounding every quantifier to the subtree below x. (Note that in a tree of rank n, if z is a descendant of x, i.e. there is a path from x to z, the length of the path is at most n, and so this is first-order definable and does not change the quantifier rank.) $E_{n + 1} ⊧ φ_{n + 1}$ but $A_{n + 1} ⊭ φ_{n + 1}$ .

It remains to show that $A_{n + 1}$ and $E_{n + 1}$ are prime. The same method will work for both structures. Let $\bar{a}$ be an arbitrary tuple in $E_{n + 1}$ . We describe a formula that isolates the type of the tuple $\bar{a}$ . Let $r_{1}, \dots, r_{k}$ be the children of the root which are the roots of subtrees containing elements of $\bar{a}$ ; say that $\bar{a} = ({\bar{a}}_{1}, \dots, {\bar{a}}_{k})$ where ${\bar{a}}_{i}$ is in the subtree below $r_{i}$ . (Note that we can re-order the tuples as we like, as if the type of some permutation of $\bar{a}$ is isolated, so is $\bar{a}$ .) By the induction hypothesis, we know that the subtree with root $r_{i}$ is prime for every i. Hence for each $i = 1, \dots, k$ there is a formula which isolates the type of the tuple ${\bar{a}}_{i}$ in the subtree with root $r_{i}$ . There is also, for each $r_{i}$ , a formula (either $φ_{n}$ or $\neg φ_{n}$ ) which distinguishes between whether the subtree below $r_{i}$ is isomorphic to $A_{n}$ or $E_{n}$ . So we can isolate the type of $\bar{a}$ by saying that there are children $r_{1}, \dots, r_{k}$ of the root such that ${\bar{a}}_{i}$ satisfies the formula, in the subtree below $r_{i}$ , which isolates it, and by saying whether the subtree below each $r_{i}$ is isomorphic to $A_{n}$ or $E_{n}$ . □

Fokina, Kalimullin, and Miller [6] showed that there is a structure $A$ with strong degree of categoricity $0^{(ω)}$ . We note the well-known fact that one can also have $A$ be a prime model. Our proof follows that of [4].

Theorem 3.4.

There is a computable structure $A$ with strong degree of categoricity $0^{(ω)}$ such that $A$ is a prime model of its theory.

Proof sketch.

The structure is just the disjoint union of infinitely many copies of each $E_{n}$ for $n < ω$ . Theorem 3.1 of [4] shows that this has strong degree of categoricity $0^{(ω)}$ , and it is not hard to see using Lemma 3.3 that this structure is prime. □

4. C.E. in and above a limit ordinal

We begin this section by a short discussion of how we code a c.e. set into a structure. Consider a c.e. set C. If one knows, for each n, at what point the approximation to $C (n)$ has settled, then one can compute C. Moreover, one does not need to know exactly when C settles, but just a point after which $C (n)$ has settled. In particular, any sufficiently large function can compute C. Moreover, C itself can compute such a function. Following the terminology of Groszek and Slaman [8], we say that C has a self-modulus.

Definition 4.1 (Groszek and Slaman [8]).

Let $F : ω \to ω$ and $X \subseteq ω$ . Then:

F is a modulus (of computation) for X if every $G : ω \to ω$ that dominates F pointwise computes X.

X has a self-modulus if X computes a modulus for itself.

The self-modulus of a c.e. set C is the function $f (n) = μ s (C_{s} (n) = C (n))$ . Groszek and Slaman showed that every $Δ_{2}^{0}$ or α-CEA set has a self-modulus. In fact, the self-modulus of a c.e. set has a nice form; it has a non-decreasing computable approximation.

Definition 4.2.

A function $F : ω \to ω$ is limitwise monotonic if there is a computable approximation function $f : ω \times ω \to ω$ such that, for all n,

$F (n) = {lim}_{s \to \infty} f (n, s)$ .

For all s, $f (n, s) ⩽ f (n, s + 1)$ .

In fact, it is well-known and an easy exercise to show that the sets of c.e. degree are exactly those with limitwise monotonic self-moduli. These remarks also relativize.

The next lemma encodes a limitwise monotonic function into the isomorphisms of copies of a computable structure. Any isomorphism dominates the limitwise monotonic function; but it does not seem to be the case that dominating the limitwise monotonic function is sufficient to compute isomorphisms.

Lemma 4.3.

Let α be a computable limit ordinal. Let $f : ω \to ω$ be limitwise monotonic relative to $0^{(α)}$ . There is a structure with computable copies $M$ and $N$ such that:

Every isomorphism between $M$ and $N$ computes a function which dominates f.

$f \oplus 0^{(α)}$ computes an isomorphism between any two computable copies of $M$ and $N$ .

Proof.

Let Φ be a computable operator such that $f (n) = {lim}_{s \to \infty} Φ^{\emptyset^{(α)}} (n, s)$ and this is monotonic in s. Write $\emptyset^{(α)} = ⨁_{γ < α} \emptyset^{(γ)}$ for successor ordinals $γ < α$ . By convention, for $β < α$ , we say that $Φ^{\emptyset^{(β)}} (n, s)$ converges if the computation $Φ^{\emptyset^{(α)}} (n, s)$ halts, but the only part of the oracle $\emptyset^{(α)} = ⨁_{γ < α} \emptyset^{(γ)}$ that is read during the computation is that part with $γ ⩽ β$ . So if $Φ^{\emptyset^{(β)}} (n, s) = m$ then $Φ^{\emptyset^{(α)}} (n, s) = m$ , and because α is a limit ordinal, if $Φ^{\emptyset^{(α)}} (n, s) = m$ then $Φ^{\emptyset^{(β)}} (n, s) = m$ for some successor ordinal $β < α$ .

Let ${(A_{β})}_{β < α}$ and ${(E_{β})}_{β < α}$ be as in Lemma 3.2. We will construct the structures $M$ and $N$ . They are the disjoint union of infinitely many structures $M_{n}$ and $N_{n}$ , with $M_{n}$ and $N_{n}$ picked out by unary relations $R_{n}$ . The nth sort will code the value of $f (n)$ .

Fix n. $M_{n}$ will have infinitely many elements ${(a_{i})}_{i \in ω}$ satisfying a unary relation S. Each of these elements will be attached to, for each successor ordinal $β < α$ , a “box” $M_{i, β}$ which contains within it a copy of either $A_{β}$ or $E_{β}$ ; each of the boxes are disjoint. By this we mean that there are binary relations $T_{β}$ such that $T_{β} (a_{i}, x)$ holds for exactly those $x \in M_{i, β}$ . $M_{i, β}$ will be a structure in the language of Lemma 3.2 and will be defined so that:

$M_{0, β} ≅ A_{β}$ for all β.

$M_{i, β} ≅ E_{β}$ , $i ⩾ 1$ , if there is s such that $Φ^{\emptyset^{(β)}} (n, s) ⩾ i$ .

$M_{i, β} ≅ A_{β}$ , $i ⩾ 1$ , otherwise.

Note that the condition in (2) is

Σ_{β}^{0}

and so we can build such a structure

M_{n}

computably.

Similarly, $N_{n}$ will have infinitely many elements ${(b_{i})}_{i \in ω}$ , each of which is attached to, for each $β < α$ , a box $N_{i, β}$ which contains within it:

$N_{i, β} ≅ E_{β}$ if there is s such that $Φ^{\emptyset^{(β)}} (n, s) > i$ .

$N_{i, β} ≅ A_{β}$ otherwise.

Again, the condition in (1) is

Σ_{β}^{0}

and so we can build such a structure

N_{n}

computably. Claim 1.

Fix n.

For each $j < f (n)$ , there is $β < α$ such that:

for $γ < β$ , $M_{j + 1, γ} ≅ N_{j, γ} ≅ A_{γ}$ ,

for $γ ⩾ β$ , $M_{j + 1, γ} ≅ N_{j, γ} ≅ E_{γ}$ .

For each $j ⩾ f (n)$ and $β < α$ , $M_{j + 1, β} ≅ N_{j, β} ≅ M_{0, β} ≅ A_{β}$ .

Proof.

For (1), it is clear from the definitions of $M_{j + 1, β}$ and $N_{j, β}$ that for all $β < α$ , $M_{j + 1, β} ≅ N_{j, β}$ . Since $j < f (n)$ , there is s such that $Φ^{\emptyset^{(α)}} (n, s) = f (n) > j$ . In particular, there must be some $β < α$ such that there is s with $Φ^{\emptyset^{(β)}} (n, s) > j$ . Let β be the least such ordinal. Then for all $γ ⩾ β$ , there is s such that $Φ^{\emptyset^{(γ)}} (n, s) > j$ , and so $M_{j + 1, γ} ≅ N_{j, γ} ≅ E_{γ}$ . By choice of β, for $γ < β$ , there is no s such that $Φ^{\emptyset^{(γ)}} (n, s) > j$ , and so $M_{j + 1, γ} ≅ N_{j, γ} ≅ A_{γ}$ .

For (2), it is clear that $M_{j + 1, β} ≅ N_{j, β}$ for each $j ⩾ f (n)$ and each $β < α$ , and it is also clear that $M_{0, β} ≅ A_{β}$ for each $β < α$ . If $j ⩾ f (n)$ , then since Φ is limitwise monotonic approximation to f, $Φ^{\emptyset^{(β)}} (n, s) ⩽ f (n) ⩽ j$ for all s and β. Thus $N_{j, β} ≅ A_{β}$ for all β. □

Claim 2.

$M$ and $N$ are isomorphic.

Proof.

It suffices to show that for each n, $M_{n}$ and $N_{n}$ are isomorphic. Fix n. Using Claim 1, we see that the map $\begin{array}{l} a_{0} & \mapsto b_{f (n)}, \\ a_{i} & \mapsto b_{i - 1} & when 0 < i ⩽ f (n), \\ a_{i} & \mapsto b_{i} & when i > f (n) \end{array}$ extends to an isomorphism between $M_{n}$ and $N_{n}$ . □

Claim 3.

Any isomorphism between $M$ and $N$ can compute a function which dominates f.

Proof.

Let g be an isomorphism between $M$ and $N$ . We will compute, using g, a function $\hat{g}$ which dominates f. For each n, define $\hat{g} (n)$ as follows. Let ${(a_{i})}_{i \in ω}$ and ${(b_{i})}_{i \in ω}$ be the elements in the definition of $M_{n}$ and $N_{n}$ . Then $\hat{g} (n)$ is the number satisfying $g (a_{0}) = b_{\hat{g} (n)}$ .

To see that $\hat{g} (n) ⩾ f (n)$ , we use Claim 1. For each $β < α$ , $M_{0, β} ≅ A_{β}$ , but if $j < f (n)$ , there is $β < α$ such that $N_{j, β} ≅ E_{β}$ . Thus no isomorphism can map $a_{0}$ to $b_{j}$ for $j < f (n)$ , and so $\hat{g} (n) ⩾ f (n)$ . □

Claim 4.

Given a computable copy $\tilde{N}$ of $N$ , $f \oplus 0^{(α)}$ can compute an isomorphism between $N$ and $\tilde{N}$ .

It is more convenient for the proof to consider $N$ rather than $M$ in this claim, but as they are isomorphic it does not matter which we choose. Proof.

For each n, let ${\tilde{N}}_{n}$ be the structure with domain $R_{n}$ in $\tilde{N}$ . It suffices to compute an isomorphism g between $N_{n}$ and ${\tilde{N}}_{n}$ for each n. Inside of ${\tilde{N}}_{n}$ , let ${(c_{i})}_{i \in ω}$ list the elements x satisfying $S (x)$ . For each $c_{i}$ , let ${\tilde{N}}_{i, β}$ be the tree whose domain consists of the elements y satisfying $T_{β} (c_{i}, y)$ . To begin, we will define g on ${(b_{i})}_{i \in ω} \subseteq N_{n}$ . Compute $f (n)$ . Using $0^{(α)}$ , look for $f (n)$ elements $c_{i}$ such that, for some $β < α$ , ${\tilde{N}}_{i, β} ≅ E_{β}$ . This search is computable relative to $0^{(α)}$ by Lemma 3.2(2), and by Claim 1 we know that there are exactly $f (n)$ such elements and so the search will terminate after finding every such element. Rearranging ${(c_{i})}_{i \in ω}$ , we may assume that these elements are $c_{0}, \dots, c_{f (n) - 1}$ .

Now, for each $k < f (n)$ , find the least $β_{k}$ such that $N_{k, β_{k}} ≅ E_{β_{k}}$ , and the least $γ_{k}$ such that ${\tilde{N}}_{k, γ_{k}} ≅ E_{γ_{k}}$ . Again, this is computable in $0^{(α)}$ by Lemma 3.2(2). Note that we must ask $0^{(α)}$ to determine what $β_{k}$ and $γ_{k}$ are least. The sets ${β_{0}, \dots, β_{f (n) - 1}}$ and ${γ_{0}, \dots, γ_{f (n) - 1}}$ must be identical including multiplicity (but possibly in a different order) as ${\tilde{N}}_{n}$ and $N_{n}$ are isomorphic. So by rearranging ${(c_{i})}_{i \in ω}$ once again we may assume that $β_{k} = γ_{k}$ for each $k < f (n)$ .

We have now rearranged the list ${(c_{i})}_{i \in ω}$ so that for each i and $β < α$ , $N_{i, β} ≅ {\tilde{N}}_{i, β}$ . Define g so that $g (b_{i}) = c_{i}$ . For each i and $β < α$ , $N_{i, β} ≅ {\tilde{N}}_{i, β}$ are isomorphic to either $A_{β}$ or $E_{β}$ , which are uniformly $0^{(β)}$ -categorical (Lemma 3.2(3)), and we can compute using $0^{(α)}$ which case we are in. So we can define g on $N_{i, β}$ to be an isomorphism to ${\tilde{N}}_{i, β}$ . Thus g is an isomorphism from $N_{n}$ to ${\tilde{N}}_{n}$ . □

These claims complete the proof of the theorem. □

Using this lemma, and taking the limitwise monotonic function to be the self-modulus of a c.e. set, it is not hard to prove our main theorem.

Theorem 4.4.

Let α be a computable limit ordinal and d a degree c.e. in and above $0^{(α)}$ . There is a computable structure with strong degree of categoricity d .

Proof.

Fix α and let $D \in d$ be a set c.e. in and above $0^{(α)}$ . Since D is c.e. in and above $0^{(α)}$ , it has a self-modulus f that is limitwise monotonic relative to $0^{(α)}$ . Consider the structure $M$ constructed in Lemma 4.3 for this f. We will enrich this structure slightly to produce a new structure $S$ . Let $S_{α}$ be the computable structure with strong degree of categoricity $0^{(α)}$ constructed in Theorem 3.1 of Csima, Franklin and Shore [4]. The new structure $S$ consists of $M$ and a disjoint copy of $S_{α}$ , and a new unary relation R such that $R (x)$ holds exactly when x belongs to the copy of $S_{α}$ . We claim that $S$ has strong degree of categoricity d.

First, suppose that $T$ is some other computable copy of $S$ . We will show that there is a d-computable isomorphism between $S$ and $T$ . Using the relation R, we may identify the component of $T$ isomorphic to $S_{α}$ . Since $S_{a}$ has (strong) degree of categoricity $0^{(α)} ⩽ d$ , we can d-computably find an isomorphism between the copies of $S_{α}$ in $S$ and $T$ . We can also identify the component isomorphic to $M$ in each structure. By choice of $M$ , any two such copies have an isomorphism between them computable in $f \oplus 0^{(α)}$ , and D can compute this self-modulus f. Hence d can computably produce such an isomorphism, since it can compute $f \oplus 0^{(α)}$ . Gluing these two isomorphisms together gives us the result.

Since $S_{α}$ has strong degree of categoricity $0^{(α)}$ , there is a computable copy ${\hat{S}}_{α}$ of $S_{α}$ such that every isomorphism between the two computes $0^{(α)}$ . Let $\tilde{S}$ be a computable copy of $S$ built in the following way. Rather than using the “standard” copy $S_{α}$ , use the “hard” copy ${\hat{S}}_{α}$ of $S_{α}$ . Additionally, rather than using $M$ , instead use $N$ as built in Lemma 4.3. Any isomorphism between $S_{α}$ and ${\hat{S}}_{α}$ computes $0^{(α)}$ , and any isomorphism between $M$ and $N$ must compute a function that dominates f. Let g be any isomorphism between $S$ and $\tilde{S}$ . Then by using R, we can restrict g to an isomorphism between $S_{α}$ and ${\hat{S}}_{α}$ and hence g can compute $0^{(α)}$ . Since g can also be restricted to an isomorphism between $M$ and $N$ , it must compute a function dominating f. But f is a modulus for D computable in $0^{(α)}$ , and hence g must be able to compute D since it can compute $0^{(α)}$ and a function dominating f. Hence g can compute d. □

We now turn to prime models, working above $0^{(ω)}$ . Essentially, our work here is to check that in taking $α = ω$ in the previous theorem and lemma, the construction results in a prime model.

Lemma 4.4.

Let $f : ω \to ω$ be limitwise monotonic relative to $0^{(ω)}$ . There is a prime model with two computable copies $M$ and $N$ such that:

Every isomorphism between $M$ and $N$ computes a function which dominates f.

$f \oplus 0^{(ω)}$ computes an isomorphism between any two computable copies of $M$ and $N$ .

Proof.

The construction is exactly the same as that of Lemma 4.3 with $α = ω$ . We refer to the structures $A_{β}$ and $E_{β}$ of Lemma 3.2 as $A_{n}$ and $E_{n}$ , $n < ω$ , but of course these are the same. It remains to argue, using the properties from Lemma 3.3 which hold only for the structures $A_{n}$ and $E_{n}$ with n finite, that the resulting structure $N$ is prime.

Recall that $N$ is the disjoint union of structures $N_{n}$ , each of which satisfies the relation $R_{n}$ . So it suffices to show that the structures $N_{n}$ are prime. $N_{n}$ was defined as follows: there were infinitely many elements ${(b_{i})}_{i \in ω}$ (satisfying the unary relation S), each of which is attached to (by binary relations $T_{m}$ ), for each $m < ω$ , a box $N_{i, m}$ which contains within it:

$N_{i, m} ≅ E_{m}$ if there is s such that $Φ^{\emptyset^{(m)}} (n, s) > i$ .

$N_{i, m} ≅ A_{m}$ otherwise.

By Claim 1 of Lemma 4.3, for each i, either

i < f (n)

and there is some

m_{i} < ω

such that:

for $ℓ < m_{i}$ , $N_{i, ℓ} ≅ A_{ℓ}$ ,

for $ℓ ⩾ m_{i}$ , $N_{i, ℓ} ≅ E_{ℓ}$ ,

i ⩾ f (n)

and for all

m < ω

N_{i, m} ≅ A_{m}

. Note that the sequence

{m_{i}}_{i < f (n)}

is non-decreasing.

By Lemma 3.3(2), for $i < f (n)$ , the automorphism orbit of $b_{i}$ is determined by the first-order formula with free variable x which expresses that S holds of x, that the structure with domain $T_{m_{i}} (x, \cdot)$ satisfies $φ_{m_{i}}$ (and so is isomorphic to $E_{m_{i}}$ ), and that the structure with domain $T_{m_{i} - 1} (x, \cdot)$ satisfies $\neg φ_{m_{i} - 1}$ (and so is isomorphic to $A_{m_{i} - 1}$ ). For $i ⩾ f (n)$ , the automorphism orbit of $b_{i}$ is determined by the first-order formula with free variable x which expresses that S holds of x, and that the structure with domain $T_{m_{f (n) - 1}} (x, \cdot)$ satisfies $\neg φ_{m_{f (n) - 1}}$ (and so is isomorphic to $A_{m_{f (n) - 1}}$ ).

Fix a tuple $\bar{c}$ from $N_{n}$ . We will give a first-order formula defining the orbit of $\bar{c}$ . We may assume that whenever $\bar{c}$ contains an element of $N_{i, m}$ , $\bar{c}$ contains $b_{i}$ as well. We can break the tuple $\bar{c}$ up into finitely many elements $b_{i_{1}}, \dots, b_{i_{k}}$ and finitely many tuples ${\bar{c}}_{i, m}$ from $N_{i, m}$ . The orbit of $\bar{c}$ is determined by the orbits of $b_{i_{1}}, \dots, b_{i_{k}}$ (each of which is determined by a first-order formula as described in the previous paragraph), the fact that $T_{m} (b_{i}, y)$ holds for any $y \in {\bar{c}}_{i, m}$ , and the orbits of each of the tuples ${\bar{c}}_{i, m}$ within $N_{i, m}$ . The latter orbits are first-order definable by Lemma 3.3(3). □

Theorem 4.5.

Let d be a degree c.e. in and above $0^{(ω)}$ . There is a computable prime model $A$ with strong degree of categoricity d .

Proof.

The construction of such a model is similar to Theorem 1.3, except we replace $M$ and $N$ from Lemma 4.3 with those $M$ and $N$ from Lemma 4.4 (which are actually the same structures, if $α = ω$ ), and we also replace the “easy” and “hard” copies of $S_{α}$ with copies of the structure from Theorem 3.4 such that any isomorphism between them computes $0^{(ω)}$ . The same argument from Theorem 1.3 shows that this new structure has strong degree of categoricity d. It remains to show that such models are prime; they are the disjoint union of prime structures, distinguishable by the relation R, and hence must be prime themselves. □

Footnotes

Acknowledgements

B.F. Csima partially supported by a Canadian NSERC Discovery Grant. M. Deveau partially supported by Canadian NSERC Postgraduate Scholarship PGSD1-234567-2017. M. Harrison-Trainor supported by an NSERC Banting Fellowship.

References

C.J.

Ash and

Knight, Computable Structures and the Hyperarithmetical Hierarchy, Elsevier, 2000.

Bazhenov and

Marchuk, Degrees of categoricity for prime and homogeneous models, in: Conference on Computability in Europe, Springer, 2018, pp. 40–49.

N.A.

Bazhenov,

I.Sh.

Kalimullin and

M.M.

Yamaleev, Degrees of categoricity and spectral dimension, J. Symb. Log. 83(1) (2018), 103–116. doi:10.1017/jsl.2017.70.

B.F.

Csima,

J.N.Y.

Franklin and

R.A.

Shore, Degrees of categoricity and the hyperarithmetic hierarchy, Notre Dame J. Form. Log. 54(2) (2013), 215–231. doi:10.1215/00294527-1960479.

B.F.

Csima and

Stephenson, Finite computable dimension and degrees of categoricity, Annals of Pure and Applied Logic 170(1) (2019), 58–94. doi:10.1016/j.apal.2018.08.012.

E.B.

Fokina,

I.Sh.

Kalimullin and

Miller, Degrees of categoricity of computable structures, Arch. Math. Logic 49(1) (2010), 51–67. doi:10.1007/s00153-009-0160-4.

S.S.

Goncharov, Degrees of autostability relative to strong constructivizations, Tr. Mat. Inst. V.A. Steklova 274(Algoritmicheskie Voprosy Algebry i Logiki) (2011), 119–129. doi:10.1134/S0081543811060071.

M.J.

Groszek and

T.A.

Slaman, Moduli of computation, Talk presented at the Conference on Logic, Computability and Randomness, Buenos Aires, Argentina, 2007. https://math.berkeley.edu/~slaman/talks/buenos_aries.pdf.

D.R.

Hirschfeldt and

W.M.

White, Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures, Notre Dame J. Form. Log. 43(1) (2002), 51–64. doi:10.1305/ndjfl/1071505769.