Computability and categoricity of weakly ultrahomogeneous structures

Abstract

This paper investigates the effective categoricity of ultrahomogeneous structures. It is shown that any computable ultrahomogeneous structure is $Δ_{2}^{0}$ categorical. A structure $A$ is said to be weakly ultrahomogeneous if there is a finite (exceptional) set of elements $a_{1}, \dots, a_{n}$ such that $A$ becomes ultrahomogeneous when constants representing these elements are added to the language. Characterizations are obtained for weakly ultrahomogeneous linear orderings, equivalence structures, injection structures and trees, and these are compared with characterizations of the computably categorical and $Δ_{2}^{0}$ categorical structures. Index sets are used to determine the complexity of the notions of ultrahomegenous and weakly ultrahomogeneous for various families of structures.

Keywords

Computability ultrahomogeneous injections effective categoricity computable model theory

1. Introduction

Computable model theory studies the algorithmic properties of effective mathematical structures and the relationships among such structures. The effective categoricity of a computable structure $A$ measures the possible complexity of isomorphisms between $A$ and computable copies of $A$ , and is an important gauge of the complexity of $A$ .

This paper will only be concerned with countable structures, countably infinite unless otherwise stated. We say a countable structure (model) $A$ is computable if its universe A is computable and all of its functions and relations are uniformly computable. Given two computable structures, we will say they are computably isomorphic if there exists an isomorphism between them that is computable. For a single computable structure $A$ , we will say $A$ is computably categorical if every computable structure isomorphic to $A$ is in fact computably isomorphic to $A$ . More generally, we will say two computable structures are $Δ_{α}^{0}$ isomorphic if there exists an isomorphism between them that is $Δ_{α}^{0}$ and we will say a computable structure $A$ is $Δ_{α}^{0}$ categorical if every computable structure isomorphic to $A$ is $Δ_{α}^{0}$ isomorphic to $A$ and will say that a computable structure $A$ is relatively $Δ_{α}^{0}$ categorical if, for every structure $B$ isomorphic to $A$ , there is an isomorphism which is $Δ_{α}^{0}$ relative to the diagram of $B$ . More generally, an arbitrary structure $A$ is relatively $Δ_{α}^{0}$ categorical if for any structure $B$ isomorphic to $A$ there is an isomorphism which is $Δ_{α}^{0}$ relative to the diagrams of $A$ and $B$ . For computable structures, the last two notions agree.

A structure $A$ is said to be ultrahomogeneous if any isomorphism between finitely generated substructures extends to an automorphism of $A$ . Ultrahomogeneous structures were first studied by Lachlan [8] and Fraïssé [7], who defined the age of a structure to be the family of finitely generated substructures of $A$ and gave properties which characterized the age of an ultrahomogeneous structure. We define here a new notion of weakly homogeneous structures, where $A$ is weakly ultrahomogeneous if there is a finite (exceptional) set of elements $a_{1}, \dots, a_{n}$ of $A$ such that any isomorphism between finitely generated substructures $A$ becomes ultrahomogeneous when constants representing these elements are added to the language. Csima, Harizanov, Miller and Montalban [5] studied computable ages and the computability of the canonical ultrahomogeneous structures, called Fraïssé limits.

The notion of a computably homogeneous structure is defined in [5], as follows. Given a structure $A$ and a tuple $\vec{a} = (a_{1}, \dots, a_{n})$ from $A$ , let $A_{\vec{a}}$ denote the substructure of $A$ generated by $\vec{a}$ . $A$ is said to be computably homogeneous if there exists a computable process which, given a tuple $\vec{a}$ , a map $g : \vec{a} \to A$ , and $x \in A$ , returns a tuple $\vec{b}$ and $y \in A$ such that $A_{\vec{a}} \subseteq A_{\vec{b}}$ and, if g extends to an embedding of $A_{\vec{a}}$ into $A$ , then the function h, defined so that $h (x) = y$ and $h (g (a_{i})) = a_{i}$ for each i, extends to an embedding of $A_{x, g (\vec{a})}$ into $A_{\vec{b}}$ . We will say that $A$ is weakly computably homogeneous if there is a finite tuple of elements $\vec{a}$ of $A$ such that $(A, \vec{a})$ is computably homogeneous. It is shown in [5] that if a computable structure $A$ is computably homogeneous, then every isomorphism between finitely generated substructures extends to a computable automorphism of $A$ . If $A$ is locally finite and ultrahomogeneous, then $A$ is in fact computably homogeneous.

Here are some simple examples of countable ultrahomogeneous structures. See [11] for more details. The linear ordering $(Q, <)$ of the rationals is the unique ultrahomogeneous countable linear ordering. The age here is just the set of all finite linear orderings. This structure is computably categorical. An equivalence structure $(A, E)$ is ultrahomogeneous if and only if all equivalence classes have the same size k, $1 ⩽ k ⩽ ℵ_{0}$ ; then the age is the set of all finite equivalence structures with all classes of size $⩽ k$ . These structures are computably categorical.

An injection structure is a set with a single 1-1 unary function. This function induces a partition of the set into distinct orbits: finite cycles, one-way infinite orbits (ω-orbits), or two-way infinite orbits ( $Z$ -orbits). An injection structure is ultrahomogeneous if and only if it has no ω-orbits. For example, there is the injection structure with infinitely many $Z$ -orbits, where the age is the set of structures consisting of finitely many $Z$ -orbits. There is also the injection structure with exactly one orbit of size k for each finite k, where the age is the family of finite injection structures with no more than one orbit of any size k. The injection structure with infinitely many ω-orbits is in fact not computably categorical, but is $Δ_{2}^{0}$ categorical.

We observe that in the first two examples there are computable models of the countable ultrahomogeneous structure. In the third example, one can have an arbitrary number of orbits of various finite sizes and thus a structure which is not computable.

In this paper, we will closely examine the effective categoricity of ultrahomogeneous structures. In Section 2, we will prove that any computable ultrahomogeneous structure is relatively $Δ_{2}^{0}$ categorical. We also introduce the notion of weakly ultrahomogeneous structures, where $A$ is weakly ultrahomogeneous if there is a finite (exceptional) set of elements $a_{1}, \dots, a_{n}$ such that $A$ becomes ultrahomogeneous when constants representing these elements are added to the language. We show that any computable weakly ultrahomogeneous structure is relatively $Δ_{2}^{0}$ categorical.

In Section 3, we characterize the weakly ultrahomogeneous computable linear orders as those which have finitely many successivities, which is equivalent to being computably categorical. We also show that any countable weakly ultrahomogeneous linear order has a computable copy. The notion of a minimal exceptional set is introduced, and we characterize the minimal exceptional sets for weakly ultrahomogeneous linear orders.

In Section 4, we characterize the countable weakly ultrahomogeneous equivalence structures as those in which all but finitely many equivalence classes have the same size. Here again every such structure has a computable copy, and a computable equivalence structure is weakly ultrahomogeneous if and only if it is computably categorical. The minimal exceptional sets for weakly ultrahomogeneous structures contain exactly one element from each of the exceptional sized equivalence classes.

In Section 5, we characterize the weakly ultrahomogeneous injection structures as those having only finitely many ω-orbits. The minimal exceptional sets contain exactly one member from each ω-orbit. For injection structures, computable categoricity implies weak ultrahomogeneity, which implies $Δ_{2}^{0}$ categoricity, but neither implication can be reversed.

In Section 6, we consider weakly ultrahomogeneous graphs. It is shown that any countable weakly ultrahomogeneous graph is a disjoint union of graphs $H$ and $K$ , where $H$ has finitely many components, and $K$ consists of a finite or infinite number of complete graphs $K_{n}$ for a fixed $n ⩽ ℵ_{0}$ . If every vertex of $G$ has finite degree, then $G$ is weakly ultrahomogeneous if and only if there is some fixed n such that all but finitely many components of $G$ are $K_{n}$ . Since graphs are relational structures, every weakly homogeneous graph is computably categorical. However, there are computably categorical graphs which are not weakly ultrahomogeneous.

In Section 7, we consider weakly homogeneous trees, among the family of countable trees of height $⩽ ω$ . There are many formulations for the study of trees. A tree may be defined by a partial ordering, a binary infimum function, a predecessor function, or a fixed number of successor functions. Miller [13] showed that no computable tree of infinite height can be computably categorical as a partial ordering (or in the infimum framework). Lempp, McCoy, Miller and Solomon [10] characterized the computably categorical trees of finite height, in the partial ordering setting. Calvert, Knight and Millar [3] defined a notion of rank homogeneity for trees in the predecessor formulation, where trees of infinite height can be computably categorical. In the partial ordering formulation, a tree $(T, ≺)$ is ultrahomogeneous if and only if it has rank $⩽ 1$ (or equivalently height $⩽ 1$ ). $(T, ≺)$ is weakly ultrahomogeneous if and only if the set of elements of rank $⩾ 1$ is finite. We give a characterization of the exceptional sets for a weakly ultrahomogeneous tree $(T, ≺)$ . A tree $(T, f)$ equipped with a predecessor function f is ultrahomogeneous if and only if any two elements of the same height have an equal number of successors. We characterize the weakly ultrahomogeneous trees $(T, f)$ in general and illustrate this characterization for trees of height $⩽ 3$ .

In Section 8, we consider n-equivalence structures, where a set comes with several equivalence relations, and in particular nested equivalence structures, where those relations are ordered by inclusion. We show that if such a structure is ultrahomogeneous, then each individual equivalence relation is ultrahomogeneous. The converse does not hold in general, but we prove it for nested equivalence structures with all finite equivalence classes. Nested n- equivalence structures turn out to be closely related to trees of height n, as studied by Leah Marshall [12]. Given nested equivalence relations $E_{1} \supset E_{2} \supset \dots \supset E_{n}$ on a set A, let $E_{0} = A \times A$ , let $E_{n + 1}$ be equality, and define the tree $T_{A}$ to be the set of equivalence classes of A under each $E_{i}$ , ordered by reverse inclusion, so that A is the root of the tree. Marshall shows that $A$ is computably categorical if and only if $T_{A}$ is computably categorical as a partial order. We show that $A$ is ultrahomogeneous if and only if $T_{A}$ is ultrahomogeneous under predecessor and similarly for weak ultrahomogeneity.

Index sets are an important tool for finding the complexity of a notion. We define index sets for many of the structures studied here and determine the complexity of the index sets corresponding to ultrahomogeneous and to weakly ultrahomogeneous structures. For these results, we use the standard enumeration from Soare [15] of the partial computable functions as ${φ_{e} : e \in ω}$ and we let the eth computably enumerable set $W_{e}$ equal the domain of $ϕ_{e}$ . The set $W_{e}$ is defined as the union of stages $W_{e, s}$ where we assume that, for any s, there is at most one e and one n such that $n \in W_{e, s + 1} - W_{e, s}$ . A set B of natural numbers is said to be $Π_{2}^{0}$ complete if B is itself a $Π_{2}^{0}$ set and if, for any $Π_{2}^{0}$ set A, there is a computable function f such that $i \in A ⟺ f (i) \in B$ for all i; similar definitions apply for other definability classes, such as $Σ_{3}^{0}$ . Some well-known index sets are the $Π_{2}^{0}$ complete set $INF = {e : W_{e} is infinite}$ and the $Σ_{3}^{0}$ complete set $COF = {e : W_{e} is cofinite}$ . We show that the index set associated with weakly ultrahomogeneous structures of several types are $Σ_{3}^{0}$ complete; this includes linear orders, equivalence structures, and trees under predecessor.

A preliminary version of this paper appeared in [1]. New material in the present paper includes the following. In Section 2, we extend the main theorem for weakly ultrahomogeneous structures which do not have computable copies. In Section 6, we examine ultrahomogeneous injection structures without computable copies. There are two sections of new material, Section 6 on weakly ultrahomogeneous graphs and Section 7 on weakly ultrahomogeneous trees. Section 8 includes new results on weakly ultrahomogeneous n-equivalence structures. The results on index sets for (weakly) ultrahomogeneous structures are also new to this paper. The authors would like to thank the referee for very helpful comments.

2. Categoricity of ultrahomogeneous structures

In this section, we will show that any computable ultrahomogeneous structure is $Δ_{2}^{0}$ categorical. Some lemmas are needed. If $A$ is an ultrahomogeneous structure and $A ≅ B$ , by composing maps it is easy to see that $B$ is also ultrahomogeneous. We also have the following stronger fact:

Lemma 2.1.
Let $A, B$ be isomorphic ultrahomogeneous structures. Let $X, Y$ be finitely generated substructures of $A, B$ respectively. If $φ : X \to Y$ is an isomorphism, then there is an isomorphism of $A$ and $B$ extending φ.
Proof.
Let $θ : A \to B$ be an isomorphism. Then $θ^{- 1} \circ φ : X \to A$ is an isomorphism of finitely generated substructures of $A$ . So it extends to an automorphism $α : A \to A$ . Then $θ \circ α : A \to B$ is an isomorphism that extends φ. □

Let $A_{s} [x_{1}, \dots, x_{n}]$ be the terms of height s starting with the $x_{i}$ , i.e. the set obtained by starting with the elements of ${x_{1}, \dots, x_{n}}$ and applying the functions of the structure up to s-many times. Then $⟨ \vec{x} ⟩ = ⋃_{s \in ω} A_{s} [\vec{x}]$ . While the $A_{s} [\vec{x}]$ aren’t structures, we will say that $A_{s} [\vec{x}] ≅ A_{s} [\vec{y}]$ if for any terms $t_{1}, \dots, t_{m}$ of height s and any relation R, we have $R (t_{1} [\vec{x}], \dots, t_{m} [\vec{x}]) \Leftrightarrow R (t_{1} [\vec{y}], \dots, t_{m} [\vec{y}])$ .
Lemma 2.2.
$⟨ \vec{x} ⟩ ≅ ⟨ \vec{y} ⟩$ with $x_{i} \to y_{i}$ iff for all $s \in ω$ we have $A_{s} [\vec{x}] ≅ A_{s} [\vec{y}]$ . Thus, determining if two finitely generated substructures are isomorphic is $Π_{1}^{0}$ .
Proof.
For the left to right direction, it is clear that the restriction of the isomorphism to any height is an instance of the desired map. The reverse implication follows from the fact that given finitely many terms $t_{1} [\vec{x}], \dots, t_{m} [\vec{x}]$ , they occur by some finite height s. So the terms are in $A_{s} [\vec{x}]$ , hence for any relation R we have $R (t_{1} [\vec{x}], \dots, t_{m} [\vec{x}]) \Leftrightarrow R (t_{1} [\vec{y}], \dots, t_{m} [\vec{y}])$ and so the map $t [\vec{x}] \to t [\vec{y}]$ is an isomorphism. □
Theorem 2.3.
Every ultrahomogeneous structure is relatively $Δ_{2}^{0}$ categorical.
Proof.
Let $A$ and $B$ be ultrahomogeneous structures and let φ be an isomorphism from $A$ to $B$ . We want to build an isomorphism θ which is $Δ_{2}^{0}$ relative to the diagrams of $A$ and $B$ . We do this with a back-and-forth argument, building increasing partial isomorphisms $θ_{n}$ at each stage and letting $θ = ⋃ θ_{n}$ . Let $a_{0} \in A$ . Since $⟨ a_{0} ⟩ ≅ ⟨ φ (a_{0}) ⟩$ , set $θ_{0} (a_{0}) = φ (a_{0}) = b_{0}$ .

Suppose we have defined $θ_{2 n - 1}$ for ${a_{0}, \dots, a_{2 n - 1}}$ with $θ_{2 n - 1} (a_{i}) = b_{i}$ . Choose the least $a_{2 n} \in A ∖ {a_{0}, \dots, a_{2 n - 1}}$ . There exists a $b \in B$ such that $⟨ a_{0}, \dots, a_{2 n} ⟩ ≅ ⟨ b_{0}, \dots, b_{2 n - 1}, b ⟩$ and we can choose the isomorphism so it extends $θ_{2 n - 1}$ by Lemma 2.1. Now search for this b using a $Π_{1}^{0}$ -oracle to check whether $⟨ a_{0}, \dots, a_{2 n} ⟩ ≅ ⟨ b_{0}, \dots, b_{2 n - 1}, b ⟩$ , call it $b_{2 n}$ , and define $θ_{2 n} (a_{2 n}) = b_{2 n}$ .

If we have defined $θ_{2 n}$ for ${a_{0}, \dots, a_{2 n}}$ with $θ_{2 n} (a_{i}) = b_{i}$ , we can similarly use a $Π_{1}^{0}$ -oracle to find an a such that $⟨ a_{0}, \dots, a_{2 n}, a ⟩ ≅ ⟨ b_{0}, \dots, b_{2 n} ⟩$ . Call this $a_{2 n + 1}$ , and define $θ_{2 n + 1} (a_{2 n + 1}) = b_{2 n + 1}$ .

After constructing $θ : A \to B$ , we can see that θ is a bijection since we took the least $a_{i}$ and $b_{i}$ at each stage. It is also clear that it is $Δ_{2}^{0}$ relative to $A$ and $B$ , since θ is defined using an oracle which is $Π_{1}^{0}$ in $A$ and $B$ . To show that it is an isomorphism, fix an m-tuple $\vec{x} \subseteq A$ such that $θ (x_{i}) = y_{i}$ for each $x_{i}$ in $\vec{x}$ , and let $\vec{y} = θ (\vec{x})$ . Choose any relation R, and any function f of arity m. Then for some n, $\vec{x} \subseteq {a_{0}, \dots, a_{n}}$ , so $\vec{y} \subseteq {b_{0}, \dots, b_{n}}$ , and since $⟨ a_{0}, \dots, a_{n} ⟩ ≅ ⟨ b_{0}, \dots, b_{n} ⟩$ , we have $R (\vec{x}) \Leftrightarrow R (\vec{y})$ and $θ (f (\vec{x})) = f (\vec{y})$ . □

The complexity of the isomorphism constructed in the theorem is a direct result of the complexity of the problem of determining if two finitely generated substructures are isomorphic. So if this problem is computable for a structure, then that structure is relatively computably categorical. If a structure is relational, then for any finite subset X of the universe we have $⟨ X ⟩ = X$ and checking if two finite structures are isomorphic is computable. Therefore, all relational ultrahomogeneous structures are relatively computably categorical.

More generally, any ultrahomogeneous locally finite structure is relatively computably categorical, where locally finite means that every finitely generated substructure is finite. This is Proposition 4.1(3) of [5]. The converse is false: an injection structure consisting of a single $Z$ -orbit is computably categorical, but is clearly not locally finite.

Next we introduce a weak version of ultrahomogeneity. Whereas ultrahomogeneous structures have the property that ‘all points look the same’ in a very strong way, the weaker version will allow finitely many elements to look different from the others.
Definition 2.4.
A structure $A$ is weakly ultrahomogeneous if there exists a finite set ${a_{1}, a_{2}, \dots, a_{n}} \subseteq A$ such that for all tuples $\vec{x}, \vec{y}$ from A with $⟨ \vec{a}, \vec{x} ⟩ ≅ ⟨ \vec{a}, \vec{y} ⟩$ where each $a_{i}$ is fixed, this isomorphism of substructures extends to an automorphism of $A$ . Call such a set ${a_{1}, a_{2}, \dots, a_{n}}$ an exceptional set of $A$ .

Alternatively, $A$ is weakly ultrahomogeneous if there is a finite set $a_{1}, \dots, a_{n}$ of elements of $A$ such that $(A, a_{1}, \dots, a_{n})$ is ultrahomogeneous in the extended language with constants for $a_{1}, \dots, a_{n}$ . Thus we can prove the following.
Theorem 2.5.

Every weakly ultrahomogeneous structure is relatively $Δ_{2}^{0}$ categorical.

Every locally finite weakly ultrahomogeneous structure is relatively computably categorical. In particular, every weakly ultrahomogeneous relational structure is relatively computably categorical.

It is also easy to see that any locally finite weakly ultrahomogeneous structure is weakly computably homogeneous.

If $A$ is a finite structure, it is trivially weakly ultrahomogeneous since the universe can be taken to be an exceptional set. Given any exceptional set, we can add finitely many elements to it and obtain another exceptional set. But more interesting are the minimal exceptional sets and the senses in which such sets are unique. To see some instances of this definition, we will look at the weakly ultrahomogeneous analogues of the examples of ultrahomogeneous structures considered in the introduction.

In the remaining sections, we will examine specific families of structures. The goals are to characterize ultrahomogeneous, and weakly ultrahomogeneous structures, and also to compare and contrast these notions with effective categoricity.
3. Linear orders

We start with a characterization of computably categorical linear orders proved by Remmel in [14]. For a linear ordering $(A, <)$ and elements $a, b \in A$ , b is said to be the successor of a, and a the predecessor of b if $a < b$ and there is no element x with $a < x < b$ . When b is the successor of a, the pair $(a, b)$ is said to be a successor pair, and each of a and b is said to be a successivity. An element $a \in A$ is said to be a left endpoint if $a ⩽ x$ for all $x \in A$ and is said to be a right endpoint if $x ⩽ a$ for all $x \in A$ . These endpoints are unique if they exist.

Theorem 3.1 (Remmel).

For countable linear orders $A$ , the following are equivalent

$A$ is computably categorical.

$A$ is relatively computably categorical.

$A$ has finitely many successivities.

$A = L_{0} + Q + L_{1} + Q + \dots + Q + L_{n}$ where the $L_{i}$ are finite chains, $L_{0}, L_{n}$ are possibly empty and $| L_{i} | ⩾ 2$ for $1 ⩽ i ⩽ n - 1$ .

Next we give a characterization of weakly ultrahomogeneous linear orders.

Theorem 3.2.
A countable linear order $A$ is weakly ultrahomogeneous iff $A$ has finitely many successivities.
Proof.
First, suppose $A$ has infinitely many successivities. Let ${a_{1}, \dots, a_{n}}$ be a finite subset of A; we will show it cannot be an exceptional set. The successivities of $A$ occur in finite chains or in subsets of order type $ω, ω^{}$ (the reverse order of ω), or $Z$ . If there is a set C of successivities that has order type ω or $Z$ , choose elements $x_{1} < x_{2}$ and $y_{1} < y_{2} \in C$ greater than all $a_{i} \in C$ such that there are more elements between $x_{1}$ and $x_{2}$ than there are between $y_{1}$ and $y_{2}$ . Then $⟨ \vec{a}, x_{1}, x_{2} ⟩ ≅ ⟨ \vec{a}, y_{1}, y_{2} ⟩$ , but the isomorphism can’t be extended to an automorphism. If C is of order type $ω^{}$ , we can repeat the argument above by choosing the elements below all $a_{i}$ in C. Finally, if $A$ has infinitely many successivities in finite chains, choose one of these chains containing none of the $a_{i}$ and from it choose the first element x and the second element y. Then $⟨ \vec{a}, x ⟩ ≅ ⟨ \vec{a}, y ⟩$ , but the isomorphism can’t be extended to an automorphism. With infinitely many successivities one of these situations must occur, and in any case we see ${a_{1}, \dots, a_{n}}$ isn’t exceptional, so $A$ isn’t weakly ultrahomogeneous.

For the other direction, let $S = {a_{1}, \dots, a_{k}}$ be the set of successivities and endpoints of $A$ . We claim that this set is exceptional. To see this, suppose $⟨ \vec{a}, \vec{x} ⟩ ≅ ⟨ \vec{a}, \vec{y} ⟩$ with $a_{i} \to a_{i}$ for $i ⩽ k$ and $x_{j} \to y_{j}$ for $j ⩽ n$ . Also assume that $x_{j}, y_{j} \notin S$ for $j ⩽ n$ . So for each $j ⩽ n$ , $x_{j}$ and $y_{j}$ are in the same copy of $Q$ , since they bear the same relation to all elements of S. Then use the ultrahomogeneity within each copy of $Q$ containing some $x_{i}, y_{i}$ and the identity elsewhere to get an automorphism of the whole structure. □
Corollary 3.3.
A computable linear order $A$ is computably categorical iff $A$ is weakly ultrahomogeneous.
Corollary 3.4.
For any countable weakly homogeneous linear order $A$ , there is a computable structure isomorphic to $A$ .

Now we consider index sets for linear orderings. The eth computable linear order $A_{e} = (ω, <_{e})$ is given by the eth partial recursive function $ϕ_{e}$ when $ϕ_{e}$ is total and is the characteristic function of a linear ordering. It is easy to see that $LIN = {e : A_{e} is a linear ordering}$ is a $Π_{2}^{0}$ set. Let $UHL = {e : A_{e} is an ultrahomogeneous linear ordering}$ and let $WUL = {e : A_{e} is a weakly ultrahomogeneous linear ordering}$ .
Theorem 3.5.

The index set $UHL$ is $Π_{2}^{0}$ complete, and in fact $Π_{2}^{0}$ complete relative to $LIN$ .

The index set $WUL$ is $Σ_{3}^{0}$ complete, and in fact $Σ_{3}^{0}$ complete relative to $LIN$ .

Proof.
(a) $UHL$ is a $Π_{2}^{0}$ set, since $A_{e}$ is ultrahomogeneous if and only if it is isomorophic to $(Q, <)$ , that is, if and only if it is dense and without endpoints. For the completeness, we give a reduction f of the $Π_{2}^{0}$ complete set $INF$ to $UHL$ in such a way that $f (e) \in LIN$ for every e. The construction of $A_{f (e)}$ is in stages $A^{s}$ as follows (we suppress the subscripts for ease of comprehension). $A_{0} = {0}$ . After any stage s, we will have a linear order $A^{s} = {a_{0}^{s} < a_{1}^{s} < \dots < a_{s}^{s}}$ . At any stage $s + 1 = 3 t + 1$ , we ensure that $A$ will have no least element by letting $a_{0}^{s + 1} = s + 1$ and $a_{i + 1}^{s + 1} = a_{i}^{s}$ for all $i ⩽ s$ . Similarly at any stage $s + 1 = 3 t + 2$ , we ensure that $A$ will have no greatest element by letting $a_{s + 1}^{s + 1} = s + 1$ and $a_{i}^{s + 1} = a_{i}^{s}$ for all $i ⩽ s$ . Finally, at any stage $s + 1 = 3 t + 3$ , we ensure that $A$ will be densely ordered, if $W_{e}$ is infinite, as follows. There are two cases. If an element enters $W_{e}$ at stage $t + 1$ , do the following: Let $⟨ a_{j}^{s}, a_{j + 1}^{s} ⟩$ be the least code for a successor pair in $A^{s}$ and put $s + 1$ between them, so that $a_{i}^{s + 1} = a_{i}^{s}$ for $i ⩽ j$ , $a_{j + 1}^{s + 1} = s + 1$ , and $a_{i + 1}^{s + 1} = a_{i}^{s}$ for $i > j$ . If no element enters $W_{e}$ at stage $t + 1$ , then make $s + 1$ smaller than all elements from $A_{s}$ as in the case for $s + 1 = 3 t + 1$ above.

If $W_{e}$ is infinite, then it follows from the construction that $A_{f (e)}$ will be a dense linear ordering without endpoints. If $W_{e}$ is finite, then after some stage s, no new elements enter $W_{e}$ , so that the block of successors from $a_{0}^{s}$ to $a_{s}^{s}$ is preserved and $A_{f (e)}$ will be isomorphic to $Z$ .

(b) It is easy to see, by quantifying over the finite exceptional set, that $WUL$ is a $Σ_{3}^{0}$ set. For the completeness, we give a reduction g of the $Σ_{3}^{0}$ complete set $COF$ to $WUL$ in such a way that $g (e) \in LIN$ for every e. The construction of $A_{g (e)}$ is a modification of the construction in part (a). The difference is that in the case $s + 1 = 3 t + 3$ , we look for the least code $⟨ a_{j}^{s}, a_{j + 1}^{s} ⟩$ for a successor pair such that both elements have come into $W_{e}$ by stage $t + 1$ .

It follows that for any pair $a, b$ such that b is the successor of a in $A_{g (e)}$ , either a or b is not in $W_{e}$ . Thus, if $W_{e}$ is cofinite, then $A_{g (e)}$ has only finitely many successivities. On the other hand, if $a \notin W_{e}$ , then it has either a successor or a predecessor when it comes into $A_{e}$ , and by the new requirement no element is ever put in between. Thus, if $W_{e}$ is not cofinite, then $A_{g (e)}$ will have infinitely many successivities. □

Let us say that an exceptional set S for a weakly ultrahomogeneous structure is a minimal exceptional set if no proper subset of S is exceptional. Such as set must exist since exceptional sets are finite. We will try to characterize minimal exceptional sets and determine whether they are unique to a structure, or perhaps unique up to automorphism. Let us say that a is a special point of a linear order $A$ is it is either an endpoint or a successivity. Thus the set of special points of a countable weakly ultrahomogeneous linear order $A = L_{0} + Q + L_{1} + Q + \dots + Q + L_{n}$ is $L_{0} \cup L_{1} \cup \dots \cup L_{n}$ .

For a weakly ultrahomogeneous linear order, the set of all special points is an exceptional set, but this set is not necessarily minimal. A characterization of exceptional sets of special points is as follows.
Proposition 3.6.
Let $A = L_{0} + Q + L_{1} + Q + \dots + Q + L_{n}$ be a countable weakly ultrahomogeneous linear order. A set of $S = {a_{1}, \dots, a_{n}}$ of special points is exceptional iff it satisfies the following conditions:
$A ∖ S$ does not include any successor pair.

S contains each last element of $L_{0}, \dots, L_{n - 1}$ and each first element of $L_{1}, \dots, L_{n}$ .

Proof.
If (i) fails for S, let $x, y \notin S$ , with y the successor of x, so that $x, y$ belong to some $L_{i}$ . Then $⟨ \vec{a}, x ⟩ ≅ ⟨ \vec{a}, y ⟩$ , but the isomorphism can’t extend since x and y are in different positions in the finite sequence $L_{i}$ .

If (ii) fails for S, let x witness its failure and let y be an element of the copy of $Q$ adjacent to x. Then $⟨ \vec{a}, x ⟩ ≅ ⟨ \vec{a}, y ⟩$ , but the isomorphism can’t extend since x is a successivity and y isn’t.

Now suppose (i) and (ii) hold for S and suppose $⟨ \vec{a}, \vec{x} ⟩ ≅ ⟨ \vec{a}, \vec{y} ⟩$ by φ, where each $x_{i}$ and $y_{j}$ is not in S. Any $x_{j}$ which is a special point is either uniquely between two $a_{i}$ , or is the unique element greater than or less than all $a_{i}$ if it is an endpoint. Hence $y_{j} = φ (x_{j}) = x_{j}$ . Any non-special points $x_{j}, y_{j}$ must be in the same copy of $Q$ and it follows from the ultrahomogeneity of $Q$ that we can extend φ to an automorphism. □

Given an exceptional set, a (possibly) smaller exceptional set is obtained by removing all non-special points. So the above proposition says that minimal exceptional sets are sets of special points satisfying the two conditions while no proper subset satisfies them both.

As an example, consider the linear order $Q + L_{0} + Q$ where $L_{0} = {a_{1} < a_{2} < \dots < a_{5}}$ . Then both ${a_{1}, a_{3}, a_{5}}$ and ${a_{1}, a_{2}, a_{4}, a_{5}}$ are minimal exceptional sets. This shows that, while we would like the exceptional sets of a weakly ultrahomogeneous structure to be unique in some way, minimal exceptional sets aren’t necessarily unique and in fact need not even be isomorphic.

Recall that in a structure $A$ , an element $b \in A$ is definable from a set $S \subseteq A$ if ${b}$ is a subset of A definable from S. Let the definable closure of S be $D (S) = {x \in A : x is definable from S}$ . An important fact about definability we will use repeatedly is that if b is definable from S and σ is an automorphism of $A$ fixing all elements of S, then σ also fixes b. Looking at definable closures reveals a sense in which minimal exceptional sets are unique. Proposition 3.7.
Let $A$ be a weakly ultrahomogeneous linear order and let $M = {a_{1} < \dots < a_{n}}$ be a minimal exceptional set. Then $D (M)$ is the set of special points of $A$ .
Proof.
Suppose x is in one of the copies of $Q$ in $A$ . Using the ultrahomogeneity of $Q$ , there is an automorphism of $A$ moving x while fixing M. So $x \notin D (M)$ . Now let x be a special point of $A$ ; we may assume $x \notin M$ . Then x is the unique element satisfying $ϕ (y) : (y < a_{i})$ if it is a left endpoint of $A$ , similarly for right endpoints, or else it is the unique element satisfying $ϕ (y) : (a_{i} < y < a_{i + 1})$ for some $i ⩽ n$ . □

4. Equivalence structures

The effective categoricity of equivalence structures was investigated by Calvert, Cenzer, Harizanov and Morozov in [2]. The character of an equivalence structure indicates the number of equivalence classes of each size. The structure is said to have bounded character if there exists a $k \in N$ such that all finite classes have size at most k. It is proved in [2] that an equivalence structure $A$ is computably categorical iff $A$ has finitely many finite classes, or $A$ has finitely many infinite classes, bounded character, and there is at most one k such that there are infinitely many classes of size k. This condition is equivalent to saying that all but finitely many classes of $A$ have the same size. For computable equivalence structures, computable categoricity is the same as relative computable categoricity.

Theorem 4.1.
A countable equivalence structure $A$ is weakly ultrahomogeneous iff all but finitely many equivalence classes of $A$ have the same size. In this case, a minimal exceptional set contains exactly one element from each of the exceptional equivalence classes.
Proof.
For one direction, suppose that $A$ has infinitely many classes of different sizes and let ${a_{1}, \dots, a_{n}}$ be a finite subset. Then find elements $x, y$ from classes of different sizes so neither is related to any $a_{i}$ . Then $⟨ \vec{a}, x ⟩ ≅ ⟨ \vec{a}, y ⟩$ , but this can’t extend to an automorphism.

Now for the reverse implication. If all but finitely many equivalence classes of $A$ are of the same size, let ${a_{1}, \dots, a_{n}}$ contain exactly one element from each of these exceptional classes. Then suppose $⟨ \vec{a}, \vec{x} ⟩ ≅ ⟨ \vec{a}, \vec{y} ⟩$ via the isomorphism φ so $φ (x_{i}) = y_{i}$ and $φ (a_{k}) = a_{k}$ . Either each pair $x_{i}, y_{i}$ is in an equivalence class with some $a_{k}$ , or if not they are in classes of the same size. Then the isomorphism extends to an automorphism as follows.

First, we will explain how the equivalence classes are mapped, and then we will describe what happens to the elements of each class. Fix each exceptional class as well as any classes which do not contain any $x_{i}$ or $y_{i}$ . If a nonexceptional class has an $x_{i}$ , then map $x_{i}$ to $y_{i}$ and hence the class $[x_{i}]$ to the class $[y_{i}]$ . If there are nonexceptional classes with a $y_{i}$ but no $x_{i}$ , there must be the same number of nonexceptional classes with an $x_{i}$ but no $y_{i}$ . Send each class of the first kind to one of the second kind. Thus we may end up with cycles, say $[x_{1}]$ maps to $[y_{1}]$ and $y_{1} E x_{3}$ , so that $[y_{1}]$ maps to $[y_{3}]$ , and then $[y_{3}]$ maps to $[x_{1}]$ .

Within each class, do the following. For classes with no $x_{i}$ or $y_{i}$ , the class is fixed and we also fix each element of the class. For the nonexceptional classes containing some of the $x_{i}$ or $y_{i}$ , we have mapped the $x_{i}$ and $y_{i}$ above, and the remaining elements can be mapped arbitrarily. For the exceptional classes containing some of the $x_{i}$ or $y_{i}$ , it follows that $φ (x_{i}) E x_{i}$ , thus we can map those elements respecting φ using a cycle decomposition similar to that described above for the nonexceptional classes. Now the remaining elements can simply be fixed.

The claim about the minimal exceptional sets follows since the proof shows such a set is exceptional, and that a finite set disjoint from two classes of different sizes is not exceptional. □
Corollary 4.2.
A computable equivalence structure $A$ is weakly ultrahomogeneous iff $A$ is computably categorical.
Corollary 4.3.
For any countable weakly homogeneous equivalence structure $A$ , there is a computable structure isomorphic to $A$ .

With this characterization of weakly ultrahomogeneous structures and their minimal exceptional sets, we can again investigate their uniqueness properties. Given two minimal exceptional sets, there is an automorphism of the structure sending one to the other by interchanging the two elements in each exceptional class and fixing everything else. However, as opposed to linear orders we don’t have uniqueness of the definable closures.
Proposition 4.4.
Let $A = (A, E)$ be a weakly ultrahomogeneous equivalence structure and let $S = {a_{1}, \dots, a_{n}}$ a minimal exceptional set. Then $x \in A$ is definable from S iff $x \in S$ or x is in an exceptional class of size at most 2.
Proof.
If $x \in A$ isn’t in an exceptional class, there is an automorphism fixing all the exceptional classes but moving x by interchanging $[x]$ with another class of the same size. If x is in an exceptional class of size at most 2, then for some $i ⩽ n$ , either $x = a_{i}$ or ${x} = {y : y E a_{i} & y \neq a_{i}}$ . If x is in an exceptional class of size greater than 2, then $[x]$ contains $a_{i}$ for some $i ⩽ n$ and an element y distinct from x and $a_{i}$ . In this case, switching x and y and using the identity everywhere else is an automorphism of $A$ moving x and fixing S. □

Now we consider index sets for equivalence structures. The eth computable equivalence structure $A_{e} = (ω, \equiv_{e})$ is given by the eth partial recursive function $ϕ_{e}$ when $ϕ_{e}$ is total and is the characteristic function of an equivalence relation. It is easy to see that $EQ = {e : A_{e} is an equivalence structure}$ is a $Π_{2}^{0}$ set. Let $UHQ = {e : A_{e} is an ultrahomogeneous equivalence structure}$ and let $WUQ = {e : A_{e} is a weakly ultrahomogeneous equivalence structure}$ . Theorem 4.5.

The index set $UHQ$ is $Π_{2}^{0}$ complete, and in fact $Π_{2}^{0}$ complete relative to $EQ$ .

The index set $WUQ$ is $Σ_{3}^{0}$ complete, and in fact $Σ_{3}^{0}$ complete relative to $EQ$ .

Proof.
(a) It is easy to see that $UHQ$ is a $Π_{2}^{0}$ set. For the completeness, we give a reduction f of the $Π_{2}^{0}$ complete set $INF$ to $UHQ$ in such a way that $f (e) \in EQ$ for every e. The idea of the construction is to make every equivalence class have size two if $W_{e}$ is infinite, and otherwise to have finitely many classes of size two and the rest of size one. The construction of $A_{f (e)}$ is in stages $A^{s}$ as follows (we suppress the subscripts for ease of comprehension). $A^{0} = {0, 1, 2}$ with $0 \equiv 1$ . This ensures that there will always be at least one class of size two. After any stage s, we will have an equivalence structure $A^{s}$ with finite universe $A_{s} = {0, 1, \dots, 2 s + 2}$ with $n + 1 ⩽ s + 1$ classes of size two, where $n = card (W_{e, s})$ , and at least one class of size one; in particular $2 s + 2$ will make up a class of size one. We assume that, for all e and s, $W_{e, s} \subseteq {0, 1, \dots, s - 1}$ and that at most one element comes into $W_{e}$ at any stage $s + 1$ . There are two cases in the construction at stage $s + 1$ . First, suppose that a new element comes into $W_{e}$ at stage $s + 1$ , which is the $n + 1 st$ element of $W_{e}$ . In this case, we look for the least $i ⩽ 2 s$ not in a class of size two and make $2 s + 3 \equiv i$ , so that $2 s + 4$ is in a class by itself. Next, suppose that no new element comes into $W_{e}$ at stage $s + 1$ . Then we simply let $A^{s + 1} = A_{s} \cup {2 s + 3, 2 s + 4}$ without adding any pairs to the equivalence relation.

If $W_{e}$ is infinite, then it follows from the construction that every equivalence class of $A_{f (e)}$ will have size two, so that $A_{f (e)}$ is ultrahomogeneous. If $W_{e}$ is finite, then all but finitely many classes will have size one, but there will be at least one class of size two, so that $A_{f (e)}$ is not ultrahomogeneous.

(b) It is easy to see, by quantifying over the finite exceptional set, that $WUQ$ is a $Σ_{3}^{0}$ set. For the completeness, we give a reduction g of the $Σ_{3}^{0}$ complete set $COF$ to $WUQ$ in such a way that $g (e) \in EQ$ for every e.

The construction of $A_{f (e)}$ is a modification of the construction in part (a). The difference is that we make $2 n$ have a class of size 2 if and only if $n \in W_{e}$ while each odd number has a class of size 2. At stage 0, we have $A^{0} = \emptyset$ . After stage s, we have $A^{s} = {0, 1, \dots, 2 s - 1}$ so that
for all $a < 2 s$ , ${[a]}^{s}$ has size either one or two;

for all $n < s$ , ${[2 n]}^{s} = {2 n}$ if and only if $n \notin W_{e, s}$ .
At stage $s + 1$ , there are two cases.

Case I: If there is an $n ⩽ s$ such that $n \in W_{e, s + 1} ∖ W_{e, s}$ , make $2 n$ equivalent to the least odd number $2 m + 1 ⩽ 2 s + 1$ not in a class of size two. If $m < s$ , put $2 s + 1$ in a class of size 1 and if $n < s$ , put $2 s$ in a class of size one.

Case II: If $W_{e, s + 1} = W_{e, s}$ , put $2 s$ in a class of size one. If there is an odd number less than $2 s + 1$ in a class of size one, pair that number with $2 s + 1$ . If not, put $2 s + 1$ in a class of size one.

It follows from the construction that, for each n, $[2 n]$ has size two if and only if $n \in W_{e}$ and that $[2 n + 1]$ has size two for every n. If $W_{e}$ is cofinite, then all but finitely many classes have size two, and hence $A_{f (e)}$ is weakly ultrahomogeneous. If $W_{e}$ is not cofinite, then $A_{f (e)}$ has infinitely many classes of size one and infinitely many classes of size two, and hence is not weakly ultrahomogeneous. □

5. Injection structures

The effective categoricity of injection structures was studied by Cenzer, Harizanov and Remmel in [4]. It was shown that an injection structure is computably categorical if and only if it has finitely many infinite orbits, and is $Δ_{2}^{0}$ categorical if and only if it either has only finitely many orbits of type $Z$ or has only finitely many orbits of type ω. In each case, relative categoricity is the same as categoricity.

Proposition 5.1.
An injection structure is ultrahomogeneous if and only if it has no ω-orbits.
Proof.
Let $A = (ω, f)$ be an injection structure. Suppose first that $A$ has an ω-orbit and let a be the element of this orbit with no predecessor. Then the substructures $A = ⟨ a ⟩ = {f^{n} (a) : n \in ω}$ and $⟨ f (a) ⟩ = {f^{n + 1} (a) : n \in ω}$ are isomorphic but this clearly cannot be extended to an automorphism of $A$ .

For the other direction, suppose that $A$ has no ω-orbits and let ϕ be an isomorphism mapping $⟨ a_{1}, \dots, a_{n} ⟩$ to $⟨ b_{1}, \dots, b_{n} ⟩$ . If $a_{i}$ belongs to an orbit of finite size k, then the orbit of $b_{i}$ also of size k and ϕ maps $⟨ a_{i} ⟩$ to $⟨ b_{i} ⟩$ . If $a_{i}$ belongs to an orbit of type $Z$ , then so does $b_{i}$ and ϕ maps $f^{j} (a_{i})$ to $f^{j} (b_{i})$ for each j. This isomorphism can be extended to the entire orbit of $a_{i}$ by mapping $f^{- n} (a_{i})$ to $f^{- n} (b_{i})$ . Finally, this can be extended to an automorphism of $A$ by mapping a to a for elements of any orbits not among the orbits of $a_{1}, \dots, a_{n}$ . □

Next we consider weakly ultrahomogeneous injection structures.
Proposition 5.2.
A countable injection structure $A$ is weakly ultrahomogeneous iff it has finitely many ω-orbits. In this case, a minimal exceptional set contains exactly one member from each ω-orbit.
Proof.
Suppose that $A$ is an injection structure having only finitely many ω-orbits. Let ${a_{1}, \dots, a_{n}}$ contain exactly one element from each of the ω-orbits, and assume that $⟨ \vec{a}, \vec{x} ⟩ ≅ ⟨ \vec{a}, \vec{y} ⟩$ via the isomorphism φ. The isomorphism is extended to an automorphism as follows.

First, orbits not containing any $x_{i}$ or $y_{i}$ are fixed. If $x_{i}$ is in a finite orbit of size k, then $y_{i}$ is also in a finite orbit of size k, and the orbit of $x_{i}$ is mapped to the orbit of $y_{i}$ . If there are finite orbits of size k containing some $y_{j}$ but no $x_{i}$ , then there must be an equal number of orbits of size k containing some $x_{i}$ but no $y_{j}$ , and then we map each class of the first kind to one of the second kind.

If $x_{i}$ is in a $Z$ -orbit, then φ maps the sequence $(x_{i}, f (x_{i}), \dots)$ to the sequence $(y_{i}, f (y_{i}), \dots)$ and this can be extended to the entire orbits. Each ω-orbit must be fixed, since it contains one of the $a_{i}$ , and φ fixes $a_{i}$ and respects f.

Now assume $A$ has infinitely many ω-orbits, and let ${a_{1}, \dots, a_{n}}$ be a finite set. In an ω-orbit containing none of the $a_{i}$ , let $x_{0}$ be the initial element and $x_{1} = f (x_{0})$ . Then $⟨ \vec{a}, x_{0} ⟩ ≅ ⟨ \vec{a}, x_{1} ⟩$ , but the isomorphism can’t extend since $x_{1}$ is in the range of f while $x_{0}$ isn’t. Thus $A$ isn’t weakly ultrahomogeneous.

If a finite set S doesn’t include an element from each ω-orbit, we may repeat the above argument with the orbit not intersecting S to show the finite set isn’t exceptional. The claim about minimal exceptional sets follows. □

It follows that, for computable injection structures, computable categoricity implies weak ultrahomogeneity which implies $Δ_{2}^{0}$ categoricity. Neither implication can be reversed as witnessed by computable injection structures consisting of only infinitely many $Z$ -orbits, and of only infinitely many ω-orbits, respectively.

In contrast to the results for linear orders and equivalence structures, there exist ultrahomogeneous injection structures which are not isomorphic to computable structures.

The character $K (A)$ for an injection structure $A = (ω, f)$ is defined by $\begin{matrix} K (A) = {(n, k) : A has at least n orbits of size k} . \end{matrix}$ It is easy to see that K will be the character of an injection structure if and only if it is a subset of $ω \times (ω - {0})$ such that, for all natural numbers n and k, if $(n + 1, k) \in K$ then $(n, k) \in K$ .
Proposition 5.3.

For any character K, there is an ultrahomogeneous injection structure $A$ with character K and with an arbitrary finite number of orbits of type $Z$ . Furthermore, $A$ is relatively computably categorical.

For any character K, there is a weakly ultrahomogeneous injection structure $A$ with character K and with an arbitrary finite number of orbits of type $Z$ and an arbitrary finite number of orbits of type ω. Furthermore, $A$ is relatively computably categorical.

For any character K, there is an ultrahomogeneous injection structure $B$ with character K and with an infinite number of orbits of type $Z$ . Furthermore, $A$ is relatively $Δ_{2}^{0}$ categorical.

For any character K, there is a weakly ultrahomogeneous injection structure $B$ with character K and with an arbitrary number of orbits of type $Z$ and an arbitrary finite number of orbits of type ω. Furthermore, $A$ is relatively $Δ_{2}^{0}$ categorical.

Proof.
In each case, it is clear that such structures exist. The effective categoricity follows from Theorem 2.5 with an additional argument in the second case. That is, for each of the finitely many orbits of type ω, we simply identify the initial elements of each orbit and use this to define the mapping on the orbits of type ω. □

Again in contrast to linear orderings and equivalence structures, injection structures are not always locally finite. Thus it is possible for an ultrahomogeneous computable injection structure to fail to be computably homogeneous. Of course a structure with only finite orbits is locally finite, and therefore a computable injection structure with only finite orbits will be computably homogeneous. A computable structure with finitely many infinite orbits will be weakly computably homogeneous.

However, a structure with infinitely many $Z$ -orbits may or may not be computably homogeneous.
Proposition 5.4.
There is a computably homogeneous injection structure consisting of infinitely many $Z$ -orbits.
Proof.
Consider the $Z$ -chain with universe ${2 i + 1 : i \in ω}$ and function f defined so $f (4 i + 1) = 4 i + 5$ , $f (4 i + 7) = 4 i + 3$ , and $f (3) = 1$ . Now, for each n, simply multiply each element of this chain by $2^{n}$ to create infinitely many $Z$ -orbits. This structure is clearly computably homogeneous. □
Proposition 5.5.
There is a computable injection structure $A$ , consisting of infinitely many $Z$ -orbits, such that, for each e, there are infinitely many orbits which are Turing equivalent to $W_{e}$ .
Proof.
We will build $A = (A, f)$ so that the orbit of $2^{e}$ is a c.e. set which is Turing equivalent to $W_{e}$ . The function f will be constructed in uniformly computable stages $f_{s}$ for $s \in ω$ , so that $f = ⋃_{s} f_{s}$ . The orbit of an element a under f will be denoted by $O (a)$ and the orbit of a under $f_{s}$ will be denoted by $O_{s} (a)$ . $A$ will have universe ${2^{e} 3^{i} 5^{j}, 2^{e} 3^{i} 7^{j} : e, i, j, \in ω}$ . The orbit $O (2^{e})$ will consist of ${2^{e} 5^{j}, 2^{e} 7^{j} : j \in ω}$ together with ${2^{e} 3^{i + 1} 5^{j}, 2^{e} 3^{i + 1} 7^{j} : j \in ω, i \in W_{e}}$ . Thus $i \in W_{e}$ if and only if $2^{e} 3^{i + 1} \in O (2^{e})$ , so that $W_{e}$ is one-one reducible to $O (2^{e})$ . For the other direction, the orbit of $2^{e}$ as described above is clearly Turing reducible to $W_{e}$ . The construction of the mapping f is as follows. For each e, begin to build the function f by letting $f (2^{e} 5^{j + 1}) = 2^{e} 5^{j}$ and $f (2^{e} 7^{j}) = 2^{e} 7^{j + 1}$ . At the same time, build auxiliary orbits for each $2^{e} 3^{i + 1}$ by letting $f (2^{e} 3^{i + 1} 5^{j + 1}) = 2^{e} 3^{i + 1} 5^{j}$ and $f (2^{e} 3^{i + 1} 7^{j}) = 2^{e} 3^{i + 1} 7^{j + 1}$ . When an element i comes into $W_{e}$ at stage $s + 1$ , insert the partial orbit of $O_{s} (2^{e} 3^{i + 1})$ onto the end of $O_{s} (2^{e})$ . After that, we resume building $O (2^{e})$ by putting $2^{e} 7^{s + 2}$ after the inserted part, while continuing to include in $O (2^{e})$ elements of the form $2^{e} 3^{i + 1} 5^{j}$ and $2^{e} 3^{i + 1} 7^{j}$ where $i \in W_{e, s + 1}$ as the construction continues.

Details of the construction are as follows. For the sake of simplicity, we fix e and describe the construction of the orbits of $2^{e} 3^{i}$ , for all i. At stage s, we will have defined f on ${2^{e} 3^{i} 5^{j}, 2^{e} 3^{i} 7^{j} : i, j ⩽ s}$ . Thus at stage 0 we have only $f_{0} (2^{e}) = 2^{e} 7$ . After stage s, $O (2^{e})$ will have initial element $2^{e} 5^{s}$ and final element $2^{e} 7^{s + 1}$ . We will assume as usual that at any stage $s + 1$ , at most one element x enters any c.e. set $W_{e}$ and that $x ⩽ s$ . At stage $s + 1$ , extend $f_{s}$ to $f_{s + 1}$ as follows. For any $i ⩽ s$ such that $i \notin W_{e, s + 1}$ , simply map $2^{e} 3^{i + 1} 5^{s + 1}$ to $2^{e} 3^{i + 1} 5^{s}$ and map $2^{e} 3^{i + 1} 7^{s + 1}$ to $2^{e} 3^{i + 1} 7^{s + 2}$ . For the orbit of $2^{e}$ , first map $2^{e} 5^{s + 1}$ to $2^{e} 5^{s}$ . If some $i ⩽ s$ comes into $W_{e}$ at stage $s + 1$ , then insert the current orbit of $O_{s} (2^{e} 3^{i + 1})$ into $O (2^{e})$ right after $2^{e} 7^{s + 1}$ . Next let ${i_{0}, \dots, i_{k - 1}} = W_{e, s + 1}$ and, if $W_{e, s + 1}$ is not empty, extend $O (2^{e})$ by putting the sequence $2^{e} 3^{i_{0} + 1} 5^{s + 1}, 2^{e} 3^{i_{0} + 1} 7^{s + 2}, 2^{e} 3^{i_{1} + 1} 5^{s + 1}, \dots, 2^{e} 3^{i_{k - 1} + 1} 7^{s + 2}$ onto the end. Finally, put $2^{e} 7^{s + 2}$ at the very end of the orbit.

It follows from the construction that, for each $e, i, j$ , $f_{s + 1}$ is defined on ${2^{e} 3^{i} 5^{j}, 2^{e} 3^{i} 7^{j} : i, j ⩽ s}$ by stage s, so that the map $f = ⋃_{s} f_{s}$ is computable. It is clear from the construction that each orbit is of type $Z$ as described above, so that the orbit of $2^{e}$ is Turing equivalent to $W_{e}$ . □
Theorem 5.6.
There is a computable injection structure $A$ , consisting of infinitely many $Z$ -orbits, which is not weakly computably homogeneous.
Proof.
Let $A = (A, f)$ be the injection structure from Proposition 5.5. Fixing any finite number of orbits, there are still two orbits of different degree so that the isomorphism between these two orbits cannot be extended to a computable automorphism. Hence $A$ will not be weakly computably homogeneous. Note that the isomorphism between the two orbits is still partial computable. That is, if we fix elements $a_{1}$ in the first orbit and $a_{2}$ in the second orbit and map $a_{1}$ to $a_{2}$ , then given x in the orbit of $a_{1}$ , we can compute $i \in Z$ so that $x = f^{i} (a_{1})$ and then compute $f^{i} (a_{2})$ . □

Next, we consider definability from exceptional sets for injection structures.
Proposition 5.7.
Let $A$ be a weakly ultrahomogeneous injection structure with no orbits of size one, and let $S = {a_{1}, \dots, a_{n}}$ be a minimal exceptional set. Then $D (S)$ is the union of the finitely many ω-orbits of $A$ .
Proof.
Suppose that $a \in A$ is not in an ω-orbit. Then the map fixing all ω-orbits and sending $x \to f (x)$ otherwise is an automorphism fixing S but moving a. Now suppose a is in an ω-orbit with $a_{i}$ for some $i ⩽ n$ . Then for some $n \in N$ we have $f^{(n)} (a) = a_{i}$ or $f^{(n)} (a_{i}) = a$ . In either case, a is definable from S. □

If there is a unique orbit of size one, then of course this is actually definable in $A$ .

Now we consider index sets for injection structures. The eth injection structure $A_{e} = (ω, ϕ_{e})$ is given by the eth partial recursive function $ϕ_{e}$ when $ϕ_{e}$ is total and is an injection. It is easy to see that $INJ = {e : A_{e} is an injection structure}$ is a $Π_{2}^{0}$ set.

Let $UHI = {e : A_{e} is an ultrahomogeneous injection structure}$ and let $WUI = {e : A_{e} is a weakly ultrahomogeneous equivalence structure}$ . Theorem 5.8.

The index set $UHI$ is $Π_{2}^{0}$ complete, and in fact $Π_{2}^{0}$ complete relative to $INJ$ .

The index set $WUI$ is $Σ_{3}^{0}$ complete, and in fact $Σ_{3}^{0}$ complete relative to $INJ$ .

Proof.
(a) Note that $A_{e}$ is ultrahomogeneous if and only if $ϕ_{e}$ is onto. It follows easily that $UHI$ is a $Π_{2}^{0}$ set. For the completeness, we give a reduction f of the $Π_{2}^{0}$ complete set $INF$ to $UHI$ in such a way that $f (e) \in INJ$ for all e. The idea of the construction is that $A_{f (e)}$ will consist of a single infinite orbit, which will be of type $Z$ if and only if $W_{e}$ is infinite. The construction of $ϕ_{f (e)}$ is in stages $ϕ^{s}$ with domain ${0, 1, \dots, 2 s}$ and image a subset of ${0, 1, \dots, 2 s + 1}$ . At stage 0, we let $ϕ_{f (e)} (0) = 1$ . After stage s, we have defined a partial injection $ϕ^{s}$ for all $i ⩽ 2 s$ . Fix s and let a be the unique number $⩽ 2 s + 1$ not in the image of $ϕ^{s}$ and let b the unique element $⩽ 2 s + 1$ not in the domain of $ϕ^{s}$ . There are two cases in the construction at stage $s + 1$ . If no new element comes into $W_{e}$ at stage $s + 1$ , extend $ϕ^{s}$ by mapping b to $2 s + 1$ and $2 s + 1$ to $2 s + 2$ . If a new element comes into $W_{e}$ at stage $s + 1$ , then again map b to $2 s + 1$ but now map $2 s + 2$ to a.

If $W_{e}$ is infinite, then it follows from the second case of the construction that $A_{f (e)}$ will consist of a single orbit of type $Z$ , whereas if $W_{e}$ is finite, then $A_{f (e)}$ will consist of a single orbit of type ω, Thus $A_{f (e)}$ is ultrahomogeneous if and only if $W_{e}$ is infinite.

(b) It is easy to see, by quantifying over the finitely many elements not in the range of $ϕ_{e}$ , that $WUI$ is a $Σ_{3}^{0}$ set. For the completeness, we give a reduction g of the $Σ_{3}^{0}$ complete set $COF$ to $WUL$ in such a way that $g (e) \in INJ$ for every e. The idea of the construction is to build infinitely many orbits with the ith orbit consisting of ${2^{n} (2 i + 1) : n \in ω}$ , so that the universe will be $ω - {0}$ . The construction will ensure that the orbit of $2 i + 1$ is of type $Z$ if $i \in W_{e}$ and otherwise is of type ω. It follows that $A_{g (e)}$ will be weakly ultrahomogeneous if and only if $W_{e}$ is cofinite.

The mapping $ϕ = ϕ_{g (e)}$ can simply be defined as follows. For each i, there are two cases. First, suppose that $i \notin W_{e}$ . Then $ϕ (2^{n} (2 i + 1)) = 2^{n + 1} (2 i + 1)$ for all n. Next suppose that $i \in W_{e, m + 1} - W_{e, m}$ for some m. Then we let $ϕ (2^{n} (2 i + 1)) = 2^{n + 1} (2 i + 1)$ for $n < 2 m$ , we let $ϕ (2^{2 m + 1} (2 i + 1)) = 2 i + 1$ , and for all $n ⩾ 2 m$ , we let $ϕ (2^{2 n} (2 i + 1)) = 2^{2 n + 2} (2 i + 1)$ and $ϕ (2^{2 n + 3} (2 i + 1)) = 2^{2 n + 1} (2 i + 1)$ . It follows that the orbit of $2 i + 1$ is of type ω if $i \notin W_{e}$ and is of type $Z$ if $i \in W_{e}$ . To compute $ϕ_{g (e)} (2^{n} (2 i + 1))$ , we just have to check whether $i \in W_{e, n + 1}$ and then follow the algorithm above. □

6. Graphs

It is a well-known theorem proved in [9] that, up to isomorphism, the countable (both infinite or finite) ultrahomogeneous graphs are

The random graph, i.e. the Fraissé limit of the class of all finite graphs.

The $K_{n}$ -free random graph, i.e. the Fraissé limit of the class of all $K_{n}$ -free finite graphs.

$m K_{n}$ , disjoint unions of m copies of $K_{n}$ for $m, n ⩽ ℵ_{0}$ .

The $3 \times 3$ lattice graph.

The cycle on 5 vertices.

Complements of these.

Some examples of weakly ultrahomogeneous graphs which aren’t ultrahomogeneous are:

The disjoint union of an ultrahomogeneous graph and a finite graph.

(Equivalence relations) Any graph where all components are complete, there are only finitely many component sizes, and at most one size occurs infinitely often.

Proposition 6.1.
Suppose $G = (V, E)$ is a countable weakly ultrahomogeneous graph. Then $G$ is a disjoint union of $H$ and $m K_{n}$ for fixed $0 ⩽ m, n ⩽ ℵ_{0}$ where $H$ has finitely many connected components.
Proof.
We may assume that $G$ has infinitely many components. Let ${a_{1}, \dots, a_{n}} \subseteq V$ . If $G$ has infinitely many non-ultrahomogeneous components, find one with no $a_{i}$ and use the non-ultrahomogeneity of the component to get a partial isomorphism that can’t extend. If among the cofinitely many ultrahomogeneous components there are two kinds that occur infinitely often, find two non-isomorphic components containing no $a_{i}$ . Choose x from one and y from the other, so $⟨ a, x ⟩ ≅ ⟨ a, y ⟩$ but the isomorphism can’t extend. Suppose the isomorphism type of the cofinitely many ultrahomogeneous components isn’t $K_{n}$ for some n. Find two of these components containing no $a_{i}$ . Choose $x, y, z$ from these components such that $x, y$ are in the same component but don’t share an edge and so z is from the other component. Then $⟨ a, x, y ⟩ ≅ ⟨ a, x, z ⟩$ but it can’t extend. □

If for a graph $G$ , a subset of its components form a non-weakly ultrahomogeneous graph, then $G$ itself is not weakly ultrahomogeneous. So, in light of Proposition 6.1, to classify weakly ultrahomogeneous graphs it is enough to look at graphs with finitely many infinite components.

Instead of a general classification, we examine a particular class of graphs. Say that a graph is locally finite if every vertex has finite degree, and say that a graph $G$ is finitely dominated if there is a finite $F \subseteq G$ so for every $v \in G$ there is an $x \in F$ so $x G v$ . The proposition leads to a classification of locally finite weakly ultrahomogeneous graphs.
Lemma 6.2.
Let $G$ be weakly ultrahomogeneous.
$G$ can have at most one component not finitely dominated.

If $G$ has infinitely many components, every component is finitely dominated.

If C is a component of $G$ not finitely dominated, there must be a finite $F \subset C$ so every $v \in C$ has distance at most 2 from F.

Proof.

Suppose $G$ has 2 components $C_{1}$ and $C_{2}$ which are not finitely dominated. Let $A \subset G$ be exceptional. Choose $x_{1}, y \in C_{1}$ and $x_{2} \in C_{2}$ so none of them share an edge with A or with each other. Then $⟨ A, x_{1}, x_{2} ⟩ ≅ ⟨ A, x_{1}, y ⟩$ , but the isomorphism can’t extend since the component of $x_{1}$ is mapped to itself but $x_{2}$ is mapped to y.

Suppose $G$ has infinitely many components and a component C not finitely dominated. Let $A \subseteq G$ be exceptional. Choose $x_{1}, x_{2} \in C$ sharing no edge with A or with each other. Then choose y from a component of $G$ containing no element of A. Then $⟨ A, x_{1}, x_{2} ⟩ ≅ ⟨ A, x_{1}, y ⟩$ , but the isomorphism can’t extend.

Suppose there is a component C such that for every finite $F \subseteq C$ , there is $v \in C$ with distance at least 3 from F. Let $A \subseteq G$ be exceptional and let $v \in C$ have distance 3 from $A \cap C$ and $v^{'}$ have distance 2. Then $⟨ A, v ⟩ ≅ ⟨ A, v^{'} ⟩$ but the isomorphism can’t extend. Note that $A \cap C \neq \emptyset$ since A must intersect each non-ultrahomogeneous component and any connected ultrahomogeneous graph has diameter 2.
□
Proposition 6.3.
Let $G$ be a locally finite graph. Then $G$ is weakly ultrahomogeneous iff $G = H \cup m K_{n}$ where $0 ⩽ m ⩽ ω, 1 ⩽ n < ω$ and $H$ is finite.
Proof.
Clearly a graph of this form is weakly ultrahomogeneous, so assume $G$ is weakly ultrahomogeneous. If $G$ has infinitely many components, then $G = H \cup ω K_{n}$ where $n < ω$ and $H$ has finitely many components. By the lemma, every component of $H$ is finitely dominated, so $H$ is finitely dominated. But a finitely dominated, locally finite graph is finite.

Now assume that $G$ has only finitely many components. At most on component, C, isn’t finitely dominated. By the lemma there is a finite $F \subseteq C$ so every $v \in C$ has distance at most 2 from F. So C is finite, along with all the other finitely dominated components, which means that $G$ is finite. □

It follows that any locally finite, weakly ultrahomogeneous countable graph has a computable copy.

Since graphs are relational structures, every weakly ultrahomogeneous graph is computably categorical. But unlike for equivalence structures and linear orders, this containment is strict. Example 6.1.
Let $G$ be the following computable graph on ω: for each k, let vertices ${7 k + 1, 7 k + 2, 7 k + 3}$ form a $K_{3}$ and let vertices ${7 k + 4, 7 k + 5, 7 k + 6, 7 k + 7}$ form a star with center $7 k + 6$ . So the first three components are

This graph can be shown to be computably categorical using a back-and-forth argument, but is not weakly ultrahomogeneous since infinitely many components aren’t ultrahomogeneous.

7. Trees

The study of trees has played an important role in mathematical logic and computability theory. There are many ways to frame the notion of a tree. We are thinking in this paper of trees which are isomorphic to subtrees of $ω^{< ω}$ . Some terminology is necessary. For a finite string $w = (w (0), w (1), \dots, w (n - 1))$ , $| w |$ denotes the length n of w. The empty string, denoted by ε, is the unique string with length zero. Given two strings v and w, the concatenation $v^{⌢} w$ is defined by $\begin{matrix} v^{⌢} w = (v (0), v (1), \dots, v (m - 1), w (0), w (1), \dots, w (n - 1)), \end{matrix}$ where $| v | = m$ and $| w | = n$ . For $m ⩽ | w |$ , $w ↾ m$ is the string $(w (0), \dots, w (m - 1))$ . For any $X \in ω^{ω}$ and $n \in ω$ , the initial segment $X ↾ n$ is $(X (0), \dots, X (n - 1))$ . We say w is an initial segment or prefix of v (written $w ⪯ v$ ) if $v = w^{⌢} u$ for some $u \in ω^{< ω}$ . This is equivalent to saying that $w = v ↾ m$ for some $m \in N$ . For a string w and $X \in ω^{ω}$ , we say that $w ≺ X$ if $w = X ↾ n$ for $n = | w |$ .

A subset T of $ω^{< ω}$ is a tree if it is closed under initial segments. That is, if $v \in T$ and $u ≺ v$ , then $u \in T$ . For any such tree T, $X \in ω^{ω}$ is said to be an infinite path through T if $X ↾ n \in T$ for all n. We let $[T]$ denote the set of infinite paths through T. For any tree T, we say that a node $w \in T$ is extendible if there exists $X \in [T]$ such that $w ≺ X$ .

A node $u \in T$ such that $v \notin T$ for any v with $u ≺ v$ , is called a dead end or leaf of T.

More generally, trees can be formulated in terms of a natural partial ordering of ≺ described above, in terms of a binary infimum function, in terms of successor functions, or in terms of a predecessor function. In the partial ordering formulation, we consider a tree $(T, ≺)$ as a partially ordered set with least element ε such that, for every $a \in T$ , ≺ well-orders the set $T (a) = {x : x ≺ a}$ ; let the height $h t_{T} (a)$ of a in T be defined as the order type of $T (a)$ . The height of a tree T is $h t (T) = sup {h t_{T} (a) : a \in T}$ . We will only consider trees of height $⩽ ω$ , which means that $T (a)$ is finite for all a. Thus ≺ will induce a natural predecessor function f, where $f (a)$ is the supremum of $T (a)$ under ≺, so that $f (ε) = ε$ . There is also a natural meet operation ∧, defined by letting $u \land v$ be the supremum of $T (u) \cap T (v)$ .

In the predecessor formulation, we will consider a tree $(T, f)$ as a tree equipped with a unary predecessor function and possessing a unique root ε such that $f (ε) = ε$ to make f total.

For $a \in T$ , let $T [a]$ denote the tree of extensions of a, that is, $T [a] = {x : a^{⌢} x \in T}$ . The rank $r k_{T} (x)$ for $x \in T$ is defined by recursion as follows: $\begin{matrix} r k_{T} (x) = sup {r k_{T} (y) + 1 : y \in T [x]} . \end{matrix}$ In particular, for a leaf x of T, $r k_{T} (x) = 0$ . If x is an extendible node of T, then $r k_{T} (x) = \infty$ . Also, $r k (T) = r k_{T} (ε)$ .

Miller [13] showed that no computable tree of infinite height can be computably categorical as a partial ordering (or in the infimum framework). Lempp, McCoy, Miller and Solomon [10] characterized the computably categorical trees of finite height, in the partial ordering setting. Calvert, Knight and Millar [3] defined a notion of rank homogeneity for trees in the predecessor formulation, where trees of infinite height can be computably categorical. They constructed in particular a computable rank homogeneous tree of Scott rank $ω_{1}^{c k}$ . This notion was applied by Fokina, Knight, Melnikov, Quinn and Safranski [6], who showed that the class of rank homogeneous trees can be embedded into the class of torsion-free Abelian groups and also into the class of Boolean algebras.

We first consider trees of finite height, as partial orderings. Lempp, McCoy, Miller and Solomon [10] characterized the computaby categorical trees $(T, ≺)$ of finite height using the notion of finite type.

Definition 7.1.
A node a of T is of strongly finite type if the set $S [a] = {T [x] : x is a successor of a}$ satisfies the following conditions:
There are only finitely many isomorphism types in $S [a]$ .

For any successors x and y of a, if $T [x]$ embeds into $T [y]$ , then either $T [x]$ and $T [y]$ are isomorphic, or the isomorphism type of $T [y]$ appears only finitely often in $S [x]$ .

T is of strongly finite type if every node of T is of strongly finite type. The notion of finite type is given by a recursive definition as follows.
Definition 7.2.
A node a of T is of finite type if it satisfies the following: the set $S [a] = {T [x] : x is a successor of a}$ satisfies the following conditions:
There are only finitely many isomorphism types in $S [a]$ .

Each isomorphism type which appears infinitely often in $S [a]$ is of strongly finite type.

For any successors x and y of a, if $T [x]$ embeds into $T [y]$ , then either $T [x]$ and $T [y]$ are isomorphic, or the isomorphism type of $T [x]$ appears only finitely often in $S [x]$ or the isomorphism type of $T [y]$ appears only finitely often in $S [x]$ .

T is of finite type if every node in T is of finite type. Lempp et al. [10] show that $(T, ≺)$ is computably categorical if and only if $(T, ≺)$ is of finite type.

It is easy to see that a tree $(T, ≺)$ is ultrahomogeneous if and only if it has rank $⩽ 1$ , and likewise for the meet presentation. Note that this is equivalent to saying that T has height $⩽ 1$ . It follows from the result of Miller that if $(T, ≺)$ is computably categorical, then it has finite height. Since trees are locally finite, every weakly homogeneous tree must be computably categorical by Theorem 2.5, and hence any weakly homogeneous tree $(T, ≺)$ must have finite height. We give a short direct proof of this fact here.
Lemma 7.3.
If $(T, ≺)$ is weakly homogeneous, then T has finite height.
Proof.
Suppose that T has infinite height and let a finite set S be given. Then let n be the maximum height of any element of S, let b be an element of height $> n$ of rank $⩾ 1$ and let c be a successor of b. Then there is an isomorphism of $S \cup {b}$ to $S \cup {c}$ fixing S and mapping b to c, which cannot be extended to an automorphism of T. Hence T is not weakly ultrahomogeneous. □
Proposition 7.4.
$(T, ≺)$ is weakly ultrahomogeneous if and only if the set of elements which have rank $⩾ 1$ is finite.
Proof.
Suppose that T is weakly ultrahomogeneous but has infinitely many elements of rank $⩾ 1$ . It follows from Lemma 7.3 that T has finite height. Now let n be the least such that there are infinitely many elements with height n which have rank $⩾ 1$ . Now given a finite set S, choose an element b of height n and rank $⩾ 1$ , which is not in the downward closure of S and let c be a successor of b. Then there is an isomorphism of $S \cup {b}$ to $S \cup {c}$ fixing S and mapping b to c, which cannot be extended to an automorphism of T. Hence T is not weakly ultrahomogeneous.

For the other direction, suppose that all but finitely many elements of T have rank 0, that is, are leaves of T. Let S be the set of elements which have successors, and suppose that ϕ is an isomorphism from a subtree $T_{1}$ of T to a subtree $T_{2}$ of T, where $S \subseteq T_{1}$ and $S \subseteq T_{2}$ and $ϕ (u) = u$ for all $u \in S$ . For any element x of $T_{1} - S$ , x has a predecessor a in S and has no successors. Then $ϕ (x)$ must also be a successor of a and have no successors. It follows that any permutation of $S [a]$ will be an isomorphism, so that ϕ can be extended to an automorphism of T. □

It follows that every weakly ultrahomogeneous tree $(T, ≺)$ has a computable copy. That is, T has a finite subtree S of nodes which have successors and each element of this finite tree has some (possibly infinite) number of successors, which are all leaves of T and this clearly always has a computable representation.

If T has only finitely many elements of height $⩾ 1$ , then certainly it has only finitely many elements of rank $⩾ 1$ , and is therefore weakly ultrahomogeneous. The following example shows that these are not equivalent conditions.
Example 7.1.
Let $T = {ε, (0)} \cup {(0, m) : m \in ω}$ . Then only the first two elements have rank $⩾ 1$ , but infinitely many elements have height 2, and T is weakly ultrahomogeneous with exceptional set ${ε, (0)}$ .

The following result shows that the weakly ultrahomogeneous trees live well inside the class of computably categorical trees.
Proposition 7.5.
Every computable weakly ultrahomogeneous tree $(T, ≺)$ is of strongly finite type.
Proof.
Let $(T, ≺)$ be a computable weakly ultrahomogeneous tree. Every leaf node is clearly of strongly finite type, so we consider a node $a \in T$ such that all nodes with rank less than $r k (a)$ are of strongly finite type. There are only finitely many isomorphism types of $T [x]$ in the whole tree, hence only finitely many in $S [a]$ and each is of strongly finite type by assumption. Among the successors of a all but finitely many are leaf nodes, so the second condition will be satisfied. Thus a is of strongly finite type. □

We can characterize exceptional sets for weakly homogeneous trees $(T, ≺)$ as follows. For any $K \subseteq T$ , let $L_{K, T} (a) = {x \in K : x ⪯ a}$ and let $U_{K, T} (a) = {x \in K : a ⪯ x}$ .
Lemma 7.6.
For any tree $(T, ≺)$ and any $a, b \in T$ , $K \cup {a}$ is isomorphic to $K \cup {b}$ if and only if $L_{K, T} (a) = L_{K, T} (b)$ and $U_{K, T} (a) = U_{K, T} (b)$ .
Proof.
$K \cup {a}$ is isomorphic to $K \cup {b}$ if and only if, for any $x \in K$ , $x ⪯ a ⟺ x ⪯ b$ and $a ⪯ x ⟺ b ⪯ x$ , which is if and only if $L_{K, T} (a) = L_{K, T} (b)$ and $U_{K, T} (a) = U_{K, T} (b)$ . □
Proposition 7.7.
Let $(T, ≺)$ be weakly ultrahomogeneous. Then for any $K \subseteq T$ , K is an exceptional set for $(T, ≺)$ if and only if
for $a \in T$ of rank $⩾ 1$ , there exists $y \in K$ such that $a ⪯ y$ , and

for any $a, b \in T$ such that $a ≺ b$ , either $b \in K$ or there exists $z \in K$ such that $a ⪯ z$ but not $b ⪯ z$ .

Proof.
Suppose first that S does not satisfy condition (i) above, and let $a ≺ b$ where there is no element of K above a. Then $U_{K, T} (a) = U_{K, T} (b) = \emptyset$ and $L_{K, T} (a) = L_{K, T} (b)$ since $a ≺ b$ and there is no element of K above a. It follows from Lemma 7.6 that $K \cup {a}$ and $K \cup {b}$ are isomorphic. This cannot be extended to an automorphism of T since the height of a is less than the height of b. Next suppose that S does not satisfy condition (ii) and let $a ≺ b$ such that $b \notin K$ and for any $x \in K$ , if $a ≺ x$ , then $b ≺ x$ . Again it follows that $U_{K, T} (a) = U_{K, T} (b)$ and $L_{K, T} (a) = L_{K, T} (b)$ , so that $K \cup {a}$ and $K \cup {b}$ are isomorphic, but there is no extension of this isomorphism to an automorphism of T.

For the other direction, suppose that K satisfies the two conditions. We claim that for any two distinct elements a and b of rank $⩾ 1$ in T, either $U_{K, T} (a) \neq U_{K, T} (b)$ or $L_{K, T} (a) \neq L_{K, T} (b)$ . The proof of the claim is in two cases.

First, suppose that a and b are incomparable. Then by condition (i), there exists an element $x \in K$ such that $a ⪯ x$ but we cannot have $b ≺ x$ since T is a tree. Thus $U_{K, T} (a) \neq U_{K, T} (b)$ . Next, suppose without loss of generality that $a ≺ b$ . By condition (ii), there are two possibilities. We may have $b \in K$ , in which case $b \in L_{K, T} (b) ∖ L_{K, T} (a)$ . Or we have $z \in K$ such that $a ⪯ z$ but not $b ⪯ z$ . In that case, $z \in U_{K, T} (a) ∖ U_{K, T} (b)$ . This proves the claim.

Now let ϕ be an isomorphism mapping $a_{1}, \dots, a_{k}$ to $b_{1}, \dots, b_{k}$ and fixing each element of K. For each $a_{i}$ of rank $⩾ 1$ , we have some $x \in K$ such that $a_{i} ⪯ x$ and thus by the isomorphism $b_{i} ⪯ x$ . Thus $b_{i}$ also has rank $⩾ 1$ . The isomorphism ϕ shows that $K \cup {a_{i}}$ is isomorphic to $K \cup {b_{i}}$ , so that $L_{K, T} (a_{i}) = L_{K, T} (b_{i})$ and $U_{K, T} (a_{i}) = U_{K, T} (b_{i})$ . It now follows from the claim that in fact $a_{i} = b_{i}$ . Thus we may define our desired automorphism H to be the identity on K and on the subtree of nodes of rank $⩾ 1$ . To complete the definition of H, it suffices to define H on the leaves of T. Fix an element c of T with a nonempty set $L [c]$ of leaves in $S [c]$ . For any $x \in L [c] \cap K$ , let $H (x) = x$ . For the remaining elements of $L [c]$ , observe that any permutation of these elements may be used to obtain an automorphism of T. So we may use any permutation for H which agrees with $ϕ (a_{i})$ for each $a_{i} \in L [c]$ . □

Now we consider index sets for trees under the partial order presentation. The eth tree $A_{e} = (ω, ≺_{e}, ε)$ is given by the eth partial recursive function $ϕ_{e}$ when $ϕ_{e}$ is total and is the characteristic function of a tree. The usual condition for a partial ordering to be a tree is that, for any element a, ${x : x ≺_{e} a}$ is well-ordered. This would be a $Π_{1}^{1}$ condition, but it can be simplified here by first requiring that ${x : x ≺_{e} a}$ is finite, which is a $Π_{3}^{0}$ condition, and then checking to see that it is totally ordered. It follows that $TRO = {e : A_{e} is a tree}$ is a $Π_{3}^{0}$ set. Let $UHT = {e : A_{e} is an ultrahomogeneous tree}$ and let $WUT = {e : A_{e} is a weakly ultrahomogeneous tree}$ .
Theorem 7.8.

The index set $TRO$ is $Π_{3}^{0}$ complete.

The index set $UHT$ is $Π_{1}^{0}$ complete relative to $TRO$ .

The index set $WUT$ is $Σ_{2}^{0}$ complete relative to $TRO$ .

Proof.
(a) We will give a reduction h of the $Σ_{3}^{0}$ complete set $COF$ to the complement of $TRO$ as follows. The idea of the construction is to build a descending chain below $2 n + 1$ if and only if $m \in W_{e}$ for all $m ⩾ n$ . Thus if $W_{e}$ is cofinite, $T_{h (e)}$ will fail to be a tree; the construction will ensure that it is a tree otherwise. First let the root $ε = 0$ and for ease of notation let $T = T_{h (0)}$ . After stage s, we have a finite tree $T^{s} = {0, 1, \dots, 2 s}$ with $0 ≺ m + 1$ for all $m ⩽ 2 s$ and such that, for each $n < s$ , if $n, n + 1, \dots, n + k \in W_{e, s}$ for some k, then there is a finite decreasing chain $2 n + 1, 2 i_{1}, \dots, 2 i_{k}$ in $T^{s}$ . At stage $s + 1$ , we first add the elements $2 s + 1, 2 s + 2$ to $T^{s}$ and let $0 ≺ 2 s + 1, 2 s + 2$ . Next suppose that a new element m comes into $W_{e}$ such that, for some j, k and n, $n, n + 1, \dots, n + j - 1 = m - 1 \in W_{e, s}$ with a corresponding chain $2 n + 1, 2 i_{1}, \dots, 2 i_{h - 1}$ in $T^{s}$ and $m + 1 = n + j + 1, n + j + 2, \dots, n + j + k - 1 \in W_{e, s}$ with corresponding chain $2 m + 3, 2 p_{1}, \dots, 2 p_{k - 1}$ . Then we insert $2 s + 2$ between these two chains, resulting in a descending chain from $2 n + 1$ of length $j + k - 1$ . Note that if $j = 0$ , then the first chain is empty and if $k = 0$ , then the second chain is empty. It follows that if $W_{e}$ is cofinite and includes ${n, n + 1, \dots}$ , then $T_{h (e)}$ will include an infinite descending chain and hence will not be a tree. On the other hand, if $W_{e}$ is co-infinite, then for each a, ${x : x ≺ a}$ will be finite, and will be totally ordered by the construction, so that $T_{h (e)}$ will be a tree.

(b) $A_{e}$ is ultrahomogeneous if and only if there do not exist distinct a and b, both not the root, such that $a ≺_{e} b$ . It follows easily that $UHT$ is a $Π_{1}^{0}$ relative to $TRO$ . For the completeness, we define a computable function f such that $A_{f (e)}$ has an element of height 2 if and only if $W_{e}$ is nonempty. Note that ${e : W_{e} = \emptyset}$ is $Π_{1}^{0}$ complete. To define $A_{f (e)}$ , simply let 0 be the root, let $0 ≺ s$ for all s and, for $s > 0$ , let $s ≺ t$ if and only if $W_{e, t}$ is nonempty.

(c) $A_{e}$ is weakly ultrahomogeneous if and only if there is a finite set of elements of rank $⩾ 1$ and a $Σ_{2}^{0}$ formula may be given by quantifying over these finite sets. For the completeness, we define a reduction g of the $Σ_{2}^{0}$ complete set $FIN = {e : W_{e} is finite}$ to $WUT$ so that $g (e) \in TRO$ for all e. Again let 0 be the root, let $0 ≺_{g (e)} x$ for all x and let $2 s + 1 ≺_{e} 2 s + 2$ if an element comes into $W_{e}$ at stage s. It is clear that $A_{g (e)}$ is always a tree, and will have finitely many nodes of rank $⩾ 1$ if and only if $W_{e}$ is finite. □

Next we will consider trees under the predecessor formulation. The notions of ultrahomogeneity turn out to be more complicated here.

First an easy implication connecting the two formulations.
Proposition 7.9.
For any tree T, if $(T, ≺)$ is (weakly) ultrahomogeneous, then $(T, f)$ is (weakly) ultrahomogeneous. Similarly, if $(T, ≺)$ is computably categorical, then $(T, f)$ is computably categorical.
Proof.
In general, $(T, ≺)$ is relational, and $(T, f)$ is locally finite, so in either case every weakly homogeneous tree is computably categorical. Assume that $(T, ≺)$ is weakly ultrahomogeneous and let $T_{1}$ and $T_{2}$ be finite isomorphic subtrees of $(T, f)$ including some fixed finite set S. Then there is an isomorphism between $(T_{1}, ≺)$ and $(T_{2}, ≺)$ fixing S. Thus there is an automorphism of $(T, ≺)$ extending this isomorphism and this is also an automorphism of $(T, f)$ . Next assume that $(T, ≺)$ is computably categorical and that $(T, f)$ is computable, and let $(S, f)$ be a computable tree isomorphic to $(T, f)$ . Then $(S, ≺)$ is also computable, and it follows that there is a computable isomorphism mapping $(T, ≺)$ to $(S, ≺)$ which also serves as an automorphism of $(T, f)$ . □

In both cases, the converse fails to hold. For example, consider the tree $T = {0^{n} : n \in ω}$ with $f (0^{n + 1}) = 0^{n}$ ; this tree is homogeneous in the predecessor forumulation but has infinite height and is not computably categorical in the partial order presentation. It is important to note this distinction, that we will be considering trees of possibly infinite height in the predecessor formulation, whereas such trees could not be even weakly ultrahomogeneous in the partial order formulation.
Theorem 7.10.
A tree $(T, f)$ with predecessor function is ultrahomogeneous if and only if, for every n and any $a, b \in T$ of the same height, a and b have an equal number of successors.
Proof.
Suppose first that for every any $a, b \in T$ of the same height have an equal number of successors. Then it is clear that automorphism of T may be defined recursively by first permuting the elements of height 1 and then arbitrarily mapping successors of x to successors of $ϕ (x)$ for $x \in T$ of height n to define ϕ on elements of height $n + 1$ . Now given finite isomorphic subtrees $U_{1}$ and $U_{2}$ with all elements of height $⩽ n$ , the isomorphism ϕ may first be extended to an isomorphism on the elements of height $⩽ n$ , since there will always be an equal number of elements of any height which have not been mapped yet. Then the isomorphism may be recursively extended to an automorphism Φ of T by mapping a successor $x^{'}$ of x to a successor $y^{'}$ of $Φ (x)$ .

Suppose next that there is some n and some elements $a, b \in T$ of height n which have a different number of successors, where n is the least for which such elements exist. Then there is an isomorphism of the elements of height $⩽ n$ mapping a to b by the argument above. But this isomorphism cannot be extended to an automorphism of T. □

Note that under the condition of Proposition 7.10, there must be a function $β : N \to N \cup {ω}$ such that every node of height n has exactly $β (n)$ immediate successors. An equivalent condition to saying that any two nodes of height n have the same number of successors, is to say that for any n and any two nodes a and b of height n, $T [a]$ is isomorphic to $T [b]$ .
Remark.
It follows from the proof of Proposition 7.10 that if $T_{1}$ and $T_{2}$ are ultrahomogeneous with the same branching function β, then any isomorphism taking a finite subtree of $T_{1}$ to a finite subtree of $T_{2}$ can be extended to an isomorphism from $T_{1}$ to $T_{2}$ .

Given a tree T (of possibly infinite height) and a subtree U of finite height with node $a \in U$ , let $T_{U} [a] = {a} \cup T (a) \cup ⋃ {T [x] : x \in T [a] ∖ U}$ . For example, if $T = ω^{< ω}$ and $U = {x : x (0) > 1}$ , then $T_{U} [ε] = {ε} \cup {x : x (0) ⩽ 1}$ and $T_{U} [(2)] = {ε, (2)}$ . So $T_{U} [a]$ consists of the node a and its predecessors, together with all nodes in T extending successors of a which are not in U.
Theorem 7.11.
A tree $(T, f)$ in the predecessor framework is weakly ultrahomogeneous if and only if there is a finite subtree S of T such that, for every $x \in S$ , $T_{S} [x]$ is ultrahomogeneous.
Proof.
Suppose first that $(T, f)$ is weakly ultrahomogeneous and let S be a finite exceptional tree. Let $x \in S$ and let ϕ be an isomorphism between two finite subtrees $U_{1}$ and $U_{2}$ of $T_{S} [x]$ ; extend ϕ to the other elements of S (in particular the immediate successors of a which are in S), by the identity and let $T_{1} = S \cup U_{1} \cup {y : y ≺ x}$ and $T_{2} = S \cup U_{2} \cup {y : y ≺ x}$ . Then $T_{1}$ and $T_{2}$ are finite subtrees of T and, since S is an exceptional set, ϕ may be extended to an automorphism of T which fixes x. It is clear that the restriction of this automorphism to $T [x]$ is the desired automorphism of $T_{S} [x]$ .

Next suppose that S is a finite subtree as specified; we will show that S is an exceptional set. Let ϕ be an isomorphism of two finite subtrees $R_{1}$ and $R_{2}$ of T which fixes S. It follows that, for each $x \in S$ , $ϕ (x) = x$ and hence the map induced by ϕ on $T [x]$ is an isomorphism between $R_{1} [x]$ and $R_{2} [x]$ . By assumption, there exist, for each $x \in S$ , an automorphism $ϕ_{x}$ on $T [x]$ which extends the map between $R_{1} [x]$ and $R_{2} [x]$ . These can be patched together to define an automorphism H of T which preserves S and extends ϕ. That is, $H (x^{⌢} y) = ϕ_{x} (y)$ when $x^{⌢} y \notin S$ and equals $x^{⌢} y$ otherwise. □

Let us consider this further for trees of height $⩽ 3$ .
Proposition 7.12.
A tree of height $⩽ 2$ is weakly ultrahomogeneous if and only if all but finitely many nodes of height 1 have an equal number of successors.
Proof.
Given k such that all but finitely many nodes of height 1 have exactly k successors, let S be the subtree consisting of the root ε together with the set of nodes of height 1 which have a different number of successors. Then $T_{S} [ε]$ consists of ε together with all nodes of height 1 having exactly k successors and each of their k successors. Thus $T_{S} [ε]$ is ultrahomogeneous. For $x \in S$ of height 1, $T_{S} [x] = S [a]$ , that is a tree of height 1 consisting of x together with all of its successors which is trivially ultrahomogeneous.

For the other direction, suppose that T is weakly ultrahomogeneous, and let S be given by Theorem 7.11 so that $T_{S} [x]$ is ultrahomogeneous for all $x \in S$ . Then $T_{S} [ε]$ will include each node x of height 1 not in S and having no successor in S, together with all of their successors. Since $T_{S} [ε]$ is ultrahomogeneous, it follows that all nodes of height 1 not in S will have the same number of successors, as desired. □
Proposition 7.13.
A tree of height 3 is weakly ultrahomogeneous if and only if the following conditions hold:
for each node x of height 1, all but finitely many successors of x have an equal number of successors;

there are fixed h and k in $ω \cup {ω}$ such that all but finitely many nodes of height 1 have exactly h successors and each of those successors has exactly k successors.

Proof.
Assuming conditions (a) and (b), let S consist of ε together with the following: Let x be a node of height 1 which does not have exactly h successors, or which has exactly h successors but some of those successors do not have exactly k successors. Then, by (a), fix m such that all but finitely many successors of x have exactly m successors; then put x into S together with each of its successors which do not have exactly m successors. Then $T_{S} [ε]$ consists of ∅ together with all nodes x of height 1 such that x has exactly h successors and each of these has exactly k successors. Thus $T_{S} [ε]$ is ultrahomogeneous.

For $x \in S$ of height 1 such that all but finitely many successors of x have exactly m successors, $T_{S} [x]$ consists of x together with each successor which has exactly m successors, and again $T_{S} [x]$ is ultrahomogeneous.

For the other direction, suppose that T is weakly ultrahomogeneous, and let the finite subtree S be given by Theorem 7.11 so that $T_{S} [x]$ is ultrahomogeneous for all $x \in S$ . Then $T_{S} [ε]$ will contain each node x of height 1 with no extensions in S, together with all extensions of x. Since $T_{S} [ε]$ is ultrahomogeneous, it follows from Proposition 7.10 that all nodes of height 1 not in S will have the same number (h) of successors,and that each of these successors will have the same number (k) of successors. Next consider $x \in S$ of height 1. Then $T_{S} [x]$ will contain all successors y of x which are not in S, together with all extensions of y. Since $T_{S} [x]$ is ultrahomogeneous, it follows that all successors of x not in S will have an equal number of successors, as desired. □

Certainly there are computably categorical trees, in either presentation, which are not weakly ultrahomogeneous.
Example 7.2.
Let T have infinitely many nodes of height 1 with exactly 2 successors and infinitely many with exactly 3 successors, and then let each node of a pair of successors have exactly 4 successors and each node of a triple of successors have exactly 1 successor. It can be checked that this tree is of strongly finite type and is therefore computably categorical. On the other hand, T is not weakly ultrahomogeneous in either presentation.

As for injection structures, there are continuum many ultrahomogeneous trees $(T, f)$ .
Proposition 7.14.
For any function $β : ω \to ω \cup {ω}$ , there is an ultrahomogeneous tree $(T, f)$ with branching function β and furthermore $(T, f)$ is relatively computably categorical.

A tree T is said to be rank-homogeneous [3] if it satisfies the following conditions for all $n \in ω$ and all $a \in T$ of height n:

for all ordinals $σ < α = r k (a)$ , if some b of height $n + 1$ has rank $σ < α$ , then a has infinitely many successors of rank σ.

If $r k (a) = \infty$ , then a has infinitely many successors of rank ∞.

Let $R_{n} (T) = {r k (a) : height (a) = n}$ . The following results can be found in [3].
Proposition 7.15 (CKM).

Suppose T and $T^{'}$ are rank homogeneous trees such that $R_{n} (T) = R_{n} (T^{'})$ for all n. Then T and $T^{'}$ are isomorphic.

Proposition 7.16 (CKM).

If T is a rank-homogeneous tree, then for any tuples $\overline{a} = (a_{1}, \dots, a_{k})$ and $\overline{b} = (b_{1}, \dots, b_{k})$ , there is an automorphism of T taking $\overline{a}$ to $\overline{b}$ if and only if the function taking to $\overline{a}$ to $\overline{b}$ extends to a rank-preserving isomorphism from the finite subtree generated by $\overline{a}$ to the finite subtree generated by $\overline{b}$ .

Despite this close analogy with the notion of ultrahomogeneity, rank-homogeneous trees are not necessarily ultrahomogeneous. For example, consider the tree T containing all nodes $(n)$ of length 1 and such that $(2^{n} \cdot (2 m + 1))$ has exactly n immediate successors for each m and n. Then T is certainly rank homogeneous, but is not weakly ultrahomogeneous.

On the other hand, consider the tree T which has only two nodes $(0)$ and $(1)$ of height 1 and then has all possible successors of these. Then T is ultrahomogeneous but is not rank-homogeneous.

Finally we consider index sets for trees under the predecessor presentation. The eth tree $B_{e} = (ω, ϕ_{e}, ε)$ is given by the eth partial recursive function $ϕ_{e}$ when $ϕ_{e}$ is total and $ϕ_{e}$ is the predecessor function of a tree. For a tree with predecessor function f, for any element a, ${x : x ≺ a} = {f^{n} (a) : n \in ω}$ , and this set is ordered by having $f^{m} (a) ≺ f^{n} (a) ⟺ m > n$ . Hence $(ω, f)$ is a tree provided that $\begin{matrix} (\forall a) (\exists n) [f^{n} (a) = ε] & (\forall a) (\forall m \neq n) [f^{m} (a) = f^{n} (a) ⟹ f^{n} (a) = ε] . \end{matrix}$

It follows that $TRP = {e : A_{e} is a tree}$ is a $Π_{2}^{0}$ set.

Let $UHP = {e : A_{e} is an ultrahomogeneous tree}$ , and let $WUP = {e : A_{e} is a weakly ultrahomogeneous tree}$ .

Theorem 7.17.

The index set $UHP$ is $Π_{2}^{0}$ complete relative to $TRP$ .

The index set $WUP$ is $Σ_{3}^{0}$ complete relative to $TRP$ .

Proof.
(a) $B_{e}$ is ultrahomogeneous if and only any two elements of the same height have an equal number of successors. It is computable to test whether a and b have the same height, by computing $f^{n} (a)$ and $f^{n} (b)$ for $n = 1, 2, \dots$ and checking that the least n such that $f^{n} (a) = ε$ is also the least n such that $f^{n} (b) = ε$ . Now a has $⩾ k$ successors if and only if there exist k distinct elements $x_{1}, \dots, x_{k}$ such that $ϕ_{e} (x_{i}) = a$ for each i, which makes this a $Σ_{1}^{0}$ relation of $a, k$ . Next we see that a and b have an equal number of successors if and only if, for each k, a has $⩾ k$ successors if and only if b has $⩾ k$ successors, making this a $Π_{2}^{0}$ relation. Quantifiying over a and b of the same height, we obtain a $Π_{2}^{0}$ characterization of ultrahomogeneity.

For the completeness, we define a computable function g such that $B_{g (e)} = B$ is ultrahomogeneous if and only if $W_{e}$ is infinite, and is always a tree. Let 0 be the root of $B_{g (e)}$ and have immediate successors 1 and 2. Then at each stage $s + 1$ , give 1 an additional successor, and give 2 an additional successor if and only if a new element enters $W_{e}$ . Then 1 and 2 have the same height, and 1 has infinitely many immediate successors, but 2 will have infinitely many immediate successors if and only if $W_{e}$ is infinite.

(b) $B_{e}$ is weakly ultrahomogeneous if and only if there is a finite subtree T of $B$ such that $B_{T} [x]$ is ultrahomogeneous for each $x \in T$ ; this gives a $Σ_{3}^{0}$ form. For the completeness, we define a reduction h of the $Σ_{3}^{0}$ complete set $COF = {e : W_{e} is cofinite}$ to $WUT$ so that $h (e) \in TRP$ for all e. Again let 0 be the root, but now let 0 have infinitely many immediate successors, $2^{n}$ , for each n. For each n, the construction will give the node $2^{n}$ $n - 1$ immediate successors, and in addition a total of $n + k$ immediate successors if and only if $n + 1, n + 2, \dots, n + k$ all belong to $W_{e}$ . Thus if $W_{e}$ is cofinite and contains ${n + 1, n + 2, \dots}$ , then the nodes $2^{n}, 2^{n + 1}, \dots$ will all have infinitely many successors. The tree T can consist of the root together with the finitely many nodes $2^{n}$ which have only finitely many successors. Note that in $B_{T} [0]$ every immediate successor of 0 has infinitely many extensions, so that $B_{T} [0]$ is ultrahomogeneous.

If $W_{e}$ is co-infinite, then the nodes of the form $2^{n}$ all have finitely many immediate successors, but the number of successors will grow with n, so that for any finite subtree T, $B_{T} [0]$ will not be ultrahomogeneous. □

8. n-Equivalence structures

In this section, we study a generalization of equivalence structures allowing for more than one equivalence relation on the universe.

Definition 8.1.
For $n < ω$ , an n-equivalence structure is a structure $A = (A, E_{1}, \dots, E_{n})$ where each $E_{i}$ is an equivalence relation on A. An n-equivalence structure is nested if for $i < j ⩽ n$ we have $x E_{j} y \to x E_{i} y$ , i.e. $E_{j} \subseteq E_{i}$ as subsets of $A \times A$ . For $a \in A$ , we let ${[a]}_{i}$ denote the equivalence class of a under $E_{i}$ . Thus for a nested equivalence structure, $i < j ⩽ n$ implies that ${[a]}_{j} \subseteq {[a]}_{i}$ , so that the $E_{i}$ classes are partitioned by $E_{j}$ . There is an implicit equivalence relation $E_{0} = A \times A$ , so that ${[a]}_{0} = A$ for all a.

For example, consider the relation on a given family of structures defined by $A \equiv_{n} B$ if and only if $A$ and $B$ satisfy the same sentences of quantifier rank n. This plays an important role in mathematical logic.

It is easy to see that if an n-equivalence structure $A$ is ultrahomogeneous, then each individual equivalence structure $(A, E_{i})$ must be ultrahomogeneous. In general, this condition is not sufficient. It must at least be the case that for any a and b, the intersections ${[a]}_{i} \cap {[a]}_{j}$ and ${[b]}_{i} \cap {[b]}_{j}$ have the same cardinality. For example, let $A = {1, 2, 3, 4, 5, 6}$ have $E_{1}$ classes ${1, 2, 3}$ and ${4, 5, 6}$ and $E_{2}$ classes ${1, 2}$ , ${3, 4}$ and ${5, 6}$ . Then $(A, E_{1})$ and $(A, E_{2})$ are ultrahomogeneous, but $(A, E_{1}, E_{2})$ is not ultrahomogeneous since ${[1]}_{1} \cap {[1]}_{2} = {1, 2}$ but ${[4]}_{1} \cap {[4]}_{2} = {4}$ . The other direction for nested structures is considered below.

In [12], Leah Marshall describes an effective correspondence between nested n-equivalence structures and certain trees of finite height where the branching of the tree reflects the containment of equivalence classes. This correspondence allows many effective properties to be transferred between nested n-equivalence structures and trees of finite height.
Definition 8.2.
For any n-equivalence structure $A = (A, E_{1}, \dots, E_{n})$ , let $E_{0} = A \times A$ , let $E_{n + 1}$ be equality, and define the tree $T_{A}$ as follows. The universe of $T_{A}$ is the set ${{[a]}_{i} : a \in A, i = 1, \dots, n}$ and the partial ordering is inclusion. This means that for each a and $i ⩽ n$ , ${[a]}_{i}$ is the predecessor of ${[a]}_{i + 1}$ .

Marshall shows that a representation of $T_{A}$ can be computed from $A$ so that the mapping from a to $[a]$ is also computable from $A$ . Recalling the definition of trees of finite type from Section 7, here is a key result of [12].
Theorem 8.3 (Marshall [12]).

Let $A$ be a computable n-equivalence structure and $T_{A}$ its corresponding tree of finite height. Then the following are equivalent:

$A$ is computably categorical.

$A$ is relatively computably categorical.

$(T_{A}, ≺)$ is computably categorical.

$(T_{A}, ≺)$ is relatively computably categorical.

$(T_{A}, ≺)$ is of finite type.

We can characterize the ultrahomogeneous nested equivalence structures for $n < ω$ using this correspondence with trees.

Theorem 8.4.
Let $A = (A, E_{1}, \dots, E_{n})$ be a nested n-equivalence structure and let $E_{0} = A \times A$ and $E_{n + 1}$ be equality. Then the following are equivalent.
$A$ is ultrahomogeneous.

For each $i ⩽ n$ there exists $k_{i}$ such that every $E_{i}$ class is partitioned into $k_{i}$ many $E_{i + 1}$ classes.

$T_{A}$ is ultrahomogeneous in the predecessor representation.

Proof.
$(1 ⟹ 2)$ : Suppose that $A$ is ultrahomogenous but the second condition fails. Then for some $i ⩽ n$ there are two $E_{i}$ classes $C_{1}, C_{2}$ such that $C_{1}$ contains more $E_{i + 1}$ classes than $C_{2}$ . For $x \in C_{1}$ and $y \in C_{2}$ we have $⟨ x ⟩ ≅ ⟨ y ⟩$ but the isomorphism can’t extend since such an automorphism would have to send $C_{1}$ to $C_{2}$ .

$(2 ⟹ 3)$ : Assuming (2), it follows that each node ${[a]}_{i}$ of $T_{A}$ has exactly $k_{i}$ immediate successors. Thus $T_{A}$ is ultrahomogeneous by Theorem 7.10.

$(3 ⟹ 1)$ : Assume that $T_{A}$ is ultrahomogeneous and let θ be an isomorphism mapping a finite subset B of A to a finite subset C. This induces an isomorphism $\hat{θ}$ mapping the finite subtree ${{[b]}_{i} : i ⩽ n + 1}$ of $T_{A}$ to ${{[c]}_{i} : i ⩽ n +_{1}}$ such that $\hat{θ} ({[b]}_{i}) = {[θ (b)]}_{i}$ . To check that this is an isomorphism, note first that, for all $b \in B$ , ${[b]}_{n + 1} = {b}$ and $\hat{θ} ({[b]}_{n + 1}) = {[θ (b)]}_{n + 1} = {θ (b)}$ . Then for each i, ${[b]}_{i}$ is the predecessor of ${[b]}_{i + 1}$ in $T_{A}$ and ${[θ (b)]}_{i}$ is the predecessor of ${[θ (b)]}_{i + 1}$ , so that $\hat{θ}$ preserves the predecessor function on $T_{A}$ . Since $T_{A}$ is ultrahomogeneous in the predecessor framework, $\hat{θ}$ may be extended to an automorphism $\hat{ϕ}$ of $T_{A}$ . Now define the automorphism ϕ on $A$ so that, for each a, $ϕ (a) = d$ if and only if $\hat{ϕ} ({a}) = {d}$ , so that $\hat{ϕ} ({[a]}_{n + 1}) = {[ϕ (a)]}_{n + 1}$ . Since ${[a]}_{n}$ is the predecessor of ${[a]}_{n + 1}$ , it follows that $\hat{ϕ} ({[a]}_{n})$ is the predecessor of $\hat{ϕ} ({[a]}_{n + 1}) = {[ϕ (a)]}_{n + 1}$ , which is ${[ϕ (a)]}_{n}$ . Proceeding by induction, we see that $\hat{ϕ} ({[a]}_{i}) = {[ϕ (a)]}_{i}$ for all i. Then for each $a, a^{'} \in A$ and all $i ⩽ n + 1$ , we have $\begin{matrix} a E_{i} a^{'} ⟺ {[a]}_{i} = {[a^{'}]}_{i} ⟺ \hat{ϕ} ({[a]}_{i}) = \hat{ϕ} ({[a^{'}]}_{i}) ⟺ {[ϕ (a)]}_{i} = {[ϕ (a^{'})]}_{i} ⟺ ϕ (a) E_{i} ϕ (a^{'}) \end{matrix}$ which shows that ϕ is an automorphism of $A$ . □
Corollary 8.5.
If $A = (A, E_{1}, \dots, E_{n})$ is a nested ultrahomogeneous equivalence structure such that all equivalence classes are finite, then $A$ is ultrahomogeneous if and only if each $(A, E_{i})$ is ultrahomogeneous.
Proof.
Suppose that each $(A, E_{i})$ is ultrahomogeneous, so that all $E_{i}$ classes have the same finite size $m_{i}$ . It follows that each $E_{i}$ class is partitioned into exactly $m_{i} / m_{i + 1} = k_{i}$ many $E_{i + 1}$ classes. Conversely, if $A$ is ultrahomogenous, then by Theorem 8.4, there exist $k_{0}, \dots, k_{n}$ such that each $E_{i}$ class is partitioned into $k_{i}$ many $E_{i + 1}$ classes. For $i = n$ , it follows that each $E_{n}$ class has size $k_{n}$ . Then by induction, we see that for $i = 1, \dots, n$ , each $E_{i}$ class has size $k_{i} \cdot k_{i + 1} \dots k_{n}$ . Thus $(A, E_{i})$ is ultrahomogeneous for $i = 1, \dots, n$ . □

Here is an example which shows that the finiteness condition is necessary in Corollary 8.5
Example 8.1.
Let $E_{1}$ be congruence modulo 2 over the natural numbers, which partitions ω into two infinite classes, the odd numbers and the even numbers. Now let $E_{2}$ partition the even numbers modulo 3 and partition the odd numbers modulo 5. Then each $E_{2}$ class is also infinite, so that both $(A, E_{1})$ and $(A, E_{2})$ are ultrahomogeneous. But $A$ is not ultrahomogeneous, since ${[0]}_{1}$ is partitioned into 3 subclasses, whereas ${[1]}_{1}$ is partitioned into 5 subclasses.

Unlike in the ultrahomogeneous case, it is not the case, even for a weakly homogeneous nested equivalence structure, that each individual equivalence relation must be weakly ultrahomogeneous.
Example 8.2.
Let $A = (A, E_{1}, E_{2})$ where $E_{1}$ has two infinite classes B and C, while $E_{2}$ partitions B into two element classes and C into three element classes. So $(A, E_{2})$ is not weakly ultrahomogeneous. Now let $S = {b, c}$ be our exceptional set with $b \in B, c \in C$ and suppose $⟨ b, c, x ⟩ ≅ ⟨ b, c, y ⟩$ . Since the isomorphism respects the partition ${B, C}$ and both of $(B, E_{2}), (C, E_{2})$ are ultrahomogeneous, the isomorphism extends on B and C separately, hence it extends to an automorphism of $A$ .

The above example indicates a property of 2-equivalence structures ensuring they are weakly ultrahomogeneous. This property leads to the following characterization, again using the connection with trees.
Theorem 8.6.
Let $A = (A, E_{1}, \dots, E_{n})$ be a nested n-equivalence structure and let $E_{0} = A \times A$ and $E_{n + 1}$ be equality. Then $T_{A}$ is weakly ultrahomogeneous in the predecessor representation if and only if $A$ is weakly ultrahomogeneous.
Proof.
Suppose that $T_{A}$ is weakly ultrahomogeneous with exceptional subtree S and let $C \subset A$ contain a representative c for each leaf x of S. Now let θ be an isomorphism mapping a finite subset B of A to a finite subset D with $θ (c) = c$ for each $c \in C$ . This induces an isomorphism $\hat{θ}$ mapping the finite subtree ${{[b]}_{i} : b \in B, i ⩽ n + 1}$ of $T_{A}$ to ${{[d]}_{i} : d \in D, i ⩽ n +_{1}}$ such that $\hat{θ} (x) = x$ for all $x \in S$ and such that $\hat{θ} ({[b]}_{i}) = {[θ (b)]}_{i}$ . $\hat{θ}$ preserves predecessors as seen in the proof of Theorem 8.4 above. Since $T_{A}$ is weakly ultrahomogeneous in the predecessor framework, with exceptional set S, it follows that $\hat{θ}$ may be extended to an automorphism $\hat{ϕ}$ of $T_{A}$ . Then as in the proof of Theorem 8.4, we may extend θ to an automorphism ϕ on $A$ so that, for each a, $ϕ (a) = b$ if and only if $\hat{ϕ} ({a}) = {b}$ , so that $\hat{ϕ} ({[a]}_{n + 1}) = {[ϕ (a)]}_{n + 1}$ .

Suppose next that $A$ is weakly homogeneous with exceptional set C and let $S = {{[c]}_{i} : c \in S, i ⩽ n}$ . Let $x = {[c]}_{i} \in S$ . By Theorem 7.11, it suffices to show that $T_{S} [x]$ is ultrahomogeneous. Suppose by way of contradiction that $T_{S} [x]$ is not ultrahomogeneous. Then there are extensions ${[a]}_{j}$ and ${[b]}_{j}$ of x with $i < j$ and $h < k$ such that ${[a]}_{j}$ is partitioned into h many $E_{j + 1}$ classes and ${[b]}_{j}$ is partitioned into k many classes. We claim that $S \cup {a} ≅ S \cup {b}$ . That is, by the definition of $T_{S} [x]$ , we have for any $d \in S$ , $a E_{i} d ⟺ c E_{i} d ⟺ b E_{i} d$ and we have $\neg a E_{i + 1} d$ and $\neg b E_{i + 1} d$ . But this partial isomorphism cannot be extended to an automorphism since $h \neq k$ . □

For nested 2-equivalence structures, Theorem 8.6 and Proposition 7.13 lead to the following characterization.
Corollary 8.7.
Let $A = (A, E_{1}, E_{2})$ be a nested 2-equivalence structure. Then $A$ is weakly ultrahomogeneous if and only if $A$ satisfies the following conditions: $E_{1}$ is weakly ultrahomogeneous, $E_{2}$ restricted to each $E_{1}$ -class is weakly ultrahomogeneous, and there are $h, k ⩽ ω$ such that all but finitely many of the restrictions are ultrahomogeneous with h many 2-classes of size k.

Since n-equivalence structures are relational, every weakly ultrahomogeneous n-equivalence structure is computably categorical. But unlike for equivalence structures and linear orders, this containment is strict even for nested 2-equivalence structures. Example 8.3.
Let $A = (A, E_{1}, E_{2})$ be a computable nested 2-equivalence structure where $E_{2}$ has infinitely many classes of size 2 and $E_{1}$ is such that infinitely many $E_{2}$ -classes are split into $E_{1}$ -classes of size 1 and infinitely many $E_{2}$ -classes contain a single $E_{1}$ -class of size 2. Given $x \in A$ , find $y E_{2} x$ . Asking if $y E_{1} x$ will then let us computably determine which type of $E_{2}$ -class x belongs to. Then via a back and forth construction we see that $A$ is computably categorical. But $A$ is not weakly ultrahomogeneous since two types of restrictions appear infinitely often.

9. Conclusion

In this paper, we have introduced the notion of a weakly ultrahomogeneous structure and examined several types of countable ultrahomogeneous and weakly ultrahomogeneous structures. We observed that countable ultrahomogeneous linear orderings and also countable ultrahomogeneous equivalence structures all have computable models. We showed that for computable linear orders and computable equivalence structures, the weakly homogeneous structures are exactly the computably categorical structures. For computable injection structures, we observed that there are continuum many ultrahomogeneous structures with no computable copy, and there are ultrahomogeneous structures which are not computably categorical, although every computably categorical structure is weakly ultrahomogeneous. We proved that any computable weakly ultrahomogeneous structure is $Δ_{2}^{0}$ categorical .We also showed that there are continuum many ultrahomogeneous trees $(T, f)$ under predecessor and that all are relatively computably categorical. We made a connection between trees under predecessor and nested equivalence structures.

For these structures, we used index sets to determine the complexity of the property of being ultrahomogeneous, and the complexity of the property of being weakly ultrahomogeneous.

We introduced the notion of a minimal exceptional set for weakly ultrahomogeneous structures. We gave characterizations of these sets for linear orders, equivalence structures, and injection structures. We also looked at the set of elements definable from the minimal exceptional set.

Future research topics include the study of other structures such as vector spaces, Boolean algebras, Abelian p-groups, and partial orderings. One goal is to classify the weakly ultrahomogeneous structures. A second goal is to determine the effective categoricity of computable weakly ultrahomogeneous structures.

Footnotes

Acknowledgement

This research was partially supported by NSF DMS-1362273.

References

Adams and

Cenzer, Computability and categoricity of ultrahomogeneous structures, in: Language, Life, Limits: Proc. CiE 2014 (Computability in Europe),

Beckmann,

Csuhaj-Varju and

Meer, eds, Springer Lecture Notes in Computer Science, Vol. 8493, 2014, pp. 1–10.

Calvert,

Cenzer,

Harizanov and

Morozov, Effective categoricity of equivalence structures, Annals of Pure and Applied Logic 14(1) (2006), 61–78. doi:10.1016/j.apal.2005.10.002.

Calvert,

J.F.

Knight and

Millar, Computable trees of Scott rank

ω_{1}^{CK}

and computable approximation, J. Symbolic Logic 76 (2006), 283–298. doi:10.2178/jsl/1140641175.

Cenzer,

Harizanov and

J.B.

Remmel, Computability theoretic properties of injection structures, Algebra and Logic 53 (2014), 39–69. doi:10.1007/s10469-014-9270-0.

Csima,

Harizanov,

Miller and

Montalban, Computability of Fraisse limits, J. Symbolic Logic 76 (2011), 66–93. doi:10.2178/jsl/1294170990.

Fokina,

J.F.

Knight,

Melnikov,

S.M.

Quinn and

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

Fraisse, Theory of Relations, North-Holland, Amsterdam, 1986.

A.H.

Lachlan, Homogeneous structures, in: Proceedings of the International Congress of Mathematicians, Berkeley, CA, 1986, Vol. 1, Amer. Math. Soc., Providence, RI, 1987, pp. 314–321.

A.H.

Lachlan and

R.E.

Woodrow, Countable ultrahomogeneous undirected graphs, Trans. Amer. Math. Soc. 262 (1980), 51–94. doi:10.1090/S0002-9947-1980-0583847-2.

10.

Lempp,

McCoy,

Miller and

Solomon, Computable categoricity of trees of finite heights, J. Symbolic Logic 70 (2005), 151–215. doi:10.2178/jsl/1107298515.

11.

Marker, Model Theory: An Introduction, Springer, New York, 2002.

12.

Marshall, Computability-Theoretic Properties of Partial Injections, Trees, and Nested Equivalences, Ph.D. dissertation, George Washington University, 2015.

13.

Miller, The computable dimensions of trees of infinite height, J. Symbolic Logic 70 (2005), 111–141. doi:10.2178/jsl/1107298513.

14.

J.B.

Remmel, Recursively categorical linear orders, Proceedings of the AMS 83 (1981), 387–391. doi:10.1090/S0002-9939-1981-0624937-1.

15.

Soare, Recursive Enumerable Sets and Degrees, Springer-Verlag, 1987.