Generically and coarsely computable isomorphisms

Abstract

Inspired by the study of generic and coarse computability in computability theory, we extend such investigation to the context of computable model theory. In this paper, we continue our study initiated in the previous paper (Journal of Logic and Computation32 (2022) 581–607) , where we introduced and studied the notions of generically and coarsely computable structures and their generalizations. In this paper, we introduce the notions of generically and coarsely computable isomorphisms, and their weaker variants. We sometimes also require that the isomorphisms preserve the density structure. For example, for any coarsely computable structure $A$ , there is a density preserving coarsely computable isomorphism from $A$ to a computable structure. We demonstrate that each notion of generically and coarsely computable isomorphisms, density preserving or not, gives interesting insights into the structures we consider, focusing on various equivalence structures and injection structures.

Keywords

Generically computable coarsely computable isomorphism equivalence structure injection structure

1. Introduction and previous work on densely computable structures

In computable structure theory, we typically take the approach of “worst case” complexity – a problem is hard if it has a hard instance. We may ask whether hardness results in computable structure theory depend on a rare worst case instance, or whether the hardness is somehow typical of instances of the problem. Toward this difficult long-term problem, the authors began in [1] the study of densely computable structures.

To analyze the sensitivity (as described above) of the word problem on groups, Kapovich, Myasnikov, Schupp, and Shpilrain [10] used asymptotic density to investigate whether a partial computable function could solve “almost all” instances of a problem. Jockusch and Schupp [8] carried this approach into the context of computability theory. They introduced and studied generically computable and coarsely computable sets, which are defined using dense sets (also, see [9] and [6,7]). Recently, in [1], we extended these notions of approximate computability from sets to structures. The present paper continues this program by addressing isomorphisms which are computable in this asymptotic sense.

The asymptotic density of a set $A \subseteq ω$ , if it exists, is $\begin{matrix} lim_{n \to \infty} \frac{| A \cap {0, \dots, n} |}{n + 1} . \end{matrix}$ We say that a set A is dense if its asymptotic density is 1.

We showed that a set $A \subseteq ω$ has asymptotic density δ if and only if the set $A \times A$ has density $δ^{2}$ in $ω \times ω$ . We also showed that there is a computable dense set $C \subseteq ω \times ω$ such that for any infinite c.e. set A, the product $A \times A$ is not a subset of C. These results led us to the notion of a generically computable structure below [1]. We further defined a $Σ_{n}$ -generically c.e. structure using the following definition of a $Σ_{n}$ elementary substructure. We say that a substructure $B$ of $A$ is $Σ_{n}$ elementary substructure if for every infinitary $Σ_{n}$ formula $θ (x_{1}, \dots, x_{n})$ and any $b_{1}, \dots, b_{n}$ from $B$ , we have: $\begin{matrix} A ⊧ θ (b_{1}, \dots, b_{n}) iff B ⊧ θ (b_{1}, \dots, b_{n}) . \end{matrix}$

In the present paper we consider only countable structures in finite languages, and, in keeping with convention, treat effectiveness of structures by identifying a structure with its atomic diagram. A structure $D$ for a finite language and with domain D is a c.e. structure if D is c.e., each relation is c.e., and each function is the restriction of a partial computable function to D (hence the partial computable function is total on D). By $c_{R}$ we denote the characteristic function of R. Throughout the paper, every structure will have for its domain some subset of ω. Frequently the domain will be ω itself, and we will specify the domain in any case where confusion is likely to arise.

Definition 1.1.

A structure $A$ is generically computable if $A$ has a substructure $D$ with a c.e. domain D of asymptotic density 1 such that for every k-ary function f and every k-ary relation R of $A$ , both $f ↾ D^{k}$ and $c_{R} ↾ D^{k}$ are restrictions to $D^{k}$ of some partial computable functions.

A structure $A$ is $Σ_{n}$ -generically c.e. if there is a c.e. dense set D such that the substructure $D$ with domain D is a c.e. substructure and also a $Σ_{n}$ elementary substructure of $A$ .

Next, we introduced the notions of coarsely computable and $Σ_{n}$ -coarsely c.e. structures [1].
Definition 1.2.

A structure $A$ is coarsely computable if there are a computable structure $E$ and a dense set D such that the structure $D$ with domain D is a substructure of both $A$ and $E$ and all relations and functions agree on D.

A structure $A$ is $Σ_{n}$ -coarsely c.e. if there are a c.e. structure $E$ and a dense set D such that the substructure $D$ with domain D is a $Σ_{n}$ elementary substructure of both $A$ and $E$ and all relations and functions agree on D.

At least two ways are possible to define a generic or coarse notion of isomorphism. We might ask that there be a total isomorphism that is computable on a set of density one, or we might ask that there be a partial computable isomorphism defined on a set of density one. We instantiate these two approaches as either generically (coarsely, respectively) computable or weakly generically (coarsely, respectively) computable isomorphisms (Definitions 1.3, 1.5, 2.2 and 3.2). We state here the “strong” definitions, and delay the “weak” definitions to later parts of the paper.
Definition 1.3.

We say that an isomorphism $F : A \to B$ from a structure $A$ to a structure $B$ is a generically computable isomorphism if there are a c.e. set C of asymptotic density one and a partial computable function θ with $C = Dom (θ)$ , which satisfy the following:

C is the domain of a substructure $C$ of $A$ ;

$F (x) = θ (x)$ for all $x \in C$ ;

The image $F [C]$ has asymptotic density one.

A structure $A$ is generically computably isomorphic to a structure $B$ if there is a generically computable isomorphism F mapping $A$ to $B$ .

The isomorphism F occurring in this definition is, in general, non-effective, but the restriction of F to the dense set C is effective. This feature will be common to most of the similar definitions throughout the paper. We could modify the definition above so that we require only that $C \subseteq Dom (θ)$ , but since both the domain of θ and C are computably enumerable, this would be equivalent. It was shown in [1] that a structure $A$ of the form $(ω, A)$ is generically computable if and only if the set A is generically computable.
Example 1.4.
Let A and B be two dense co-infinite c.e. sets. Let $A = (ω, A)$ and $B = (ω, B)$ . There is a generically computable isomorphism from $A$ to $B$ . To see this, let A have computable one-to-one enumeration ${a_{0}, a_{1}, \dots}$ and similarly $B = {b_{0}, b_{1}, \dots}$ and define $θ : A \to B$ with domain A and range B, by $θ (a_{i}) = b_{i}$ , leaving $θ (x)$ undefined if $x \neq a_{i}$ for any i. Define $F : A \to B$ in two cases. For $x \in A$ , let $F (x) = θ (x)$ . Then let $F : (ω - A) \to (ω - B)$ be an arbitrary bijection.
Definition 1.5.
We say that an isomorphism $F : A \to B$ from a structure $A$ to a structure $B$ is a coarsely computable isomorphism if there are a set C of asymptotic density one and a (total) computable bijection θ such that:
C is the domain of a substructure $C$ of $A$ ;

$F (x) = θ (x)$ for all $x \in C$ ;

The image $F [C]$ has asymptotic density one.

Note that in Definition 1.5, the function θ must be an isomorphism between $C$ and its image, because F is an isomorphism. Moreover, $F [C]$ is, as a consequence of the definition, the domain of a substructure of $B$ . Again, we have the expected result on structures with a single dense unary relation.

We might also require, in either case, that the isomorphism preserve the density structure. To this end, we will also introduce a notion of density preserving and examine its consequences.
Definition 1.6.
A function ψ mapping a set C to a set D is density preserving if for any subset A of C with asymptotic density p, the image $ψ (A)$ also has asymptotic density p.

We demonstrate in the present paper that each notion – density preserving or not – gives interesting insights into the structures under consideration. It is likely that under further investigation one notion or the other will become dominant, but we present both here. We would like to say that a structure is generically (coarsely, resp.) computable if and only if it is generically (coarsely, resp.) computably isomorphic to a computable structure. The closest result we have of this kind is the following result, which appears later as Proposition 3.4.
Proposition 1.7.
If the structure $A$ is coarsely computable, then there is a density preserving weakly coarsely computable isomorphism from $A$ to a computable structure. Conversely, if there is a weakly coarsely computable isomorphism (density preserving or not) from $A$ to a computable structure, then $A$ is coarsely computable.

We have a weaker result for a generically computable isomorphism, which will be presented in Proposition 2.8.

In both [1] and the present work, we focus on examples arising among injection structures (see also [4]) and equivalence structures (see also [2,3,5]).

An injection structure $A$ is a set A together with a one-to-one function $f : A \to A$ . It is not hard to see that every c.e. injection structure is isomorphic to a computable injection structure. The orbit of an element a under f is $\begin{matrix} O_{f} (a) = {x : (\exists n \in ω) [x = f^{(n)} (a) \lor a = f^{(n)} (x)]} . \end{matrix}$ Infinite orbits may be of type $Z$ or of type ω. The character of $A$ is $\begin{matrix} χ (A) = {(k, n) \in (ω - {0}) \times (ω - {0}) : A has at least n orbits of size k} . \end{matrix}$ Further, let $Fin (A)$ denote the elements that belong to a finite orbit.

In [1], we showed that an injection structure has a generically computable copy if and only if it has an infinite substructure isomorphic to a computable structure, or, equivalently, it has either an infinite orbit or a character with an infinite c.e. subset. For injection structures, having an isomorphic $Σ_{1}$ -generically c.e. copy has a simple characterization: it is equivalent to having a computable copy, to having a $Σ_{2}$ -generically c.e. copy, and to the character being c.e.

In the present paper, we will establish the following result on generically computable isomorphisms of injection structures.
Theorem 1.8 (Proved as Theorem 2.9).

Let $A = (ω, f)$ and $B = (ω, g)$ be isomorphic computable injection structures with a specified finite number of elements $a_{1}, \dots, a_{k} \in A$ and $b_{1}, \dots, b_{k} \in B$ where, for each i, $a_{i}$ and $b_{i}$ have infinite orbits of the same type. Suppose that $Fin (A) \cup ⋃_{1 ⩽ i ⩽ k} O_{f} (a_{i})$ and $Fin (B) \cup ⋃_{1 ⩽ i ⩽ k} O_{g} (b_{i})$ are asymptotically dense. Then $A$ and $B$ are generically computably isomorphic.

Any computable injection structure $A$ , with a finite number of infinite orbits ${O_{f} (a_{i}) : i = 1, \dots, k}$ such that $Fin (A) \cup ⋃_{1 ⩽ i ⩽ k} O_{f} (a_{i})$ is asymptotically dense, is generically computably isomorphic to a computable structure $C$ such that $Fin (C)$ is computable.

An equivalence structure $A = (A, E)$ is a set A with an equivalence relation E on A. For $a \in A$ by ${[a]}_{E}$ , we denote the equivalence class of a under E. The character of $A$ is $\begin{matrix} χ (A) = {(k, n) \in (ω - {0}) \times (ω - {0}) : A has at least n classes of size k} . \end{matrix}$ We say that $χ (A)$ is bounded if and only if there is some finite k such that all finite equivalence classes of $A$ have size at most k.

In [1], we obtained a surprising result that every equivalence structure $(ω, E)$ has a generically computable copy. We showed in [1] that if an equivalence structure $(ω, E)$ is generically computable, then there is an infinite computable $C \subseteq ω$ such that the restriction of E to $C \times C$ is computable. In that paper, also, we reviewed the definition of $s_{1}$ -functions, which play a role in the following result. We do not repeat the definition here because it will play no significant role in the new results of the present paper.

Definition 1.9.
For an equivalence structure $A = (A, E)$ and $n ⩽ ω$ , let $A (n) = {a : | {[a]}_{E} | = n}$ . For brevity, we sometimes refer to elements of $A (n)$ as being of type n. Theorem 1.10 ([1]).

An equivalence structure $A = (ω, E)$ has a $Σ_{1}$ -generically c.e. copy if and only if at least one of the following conditions holds:

$χ (A)$ is bounded;

$χ (A)$ has a $Σ_{2}^{0}$ subset K which is a character with a computable Khisamiev $s_{1}$ -function;

$A$ has an infinite class and $χ (A)$ has a $Σ_{2}^{0}$ subset K;

$A$ has infinitely many infinite classes.

On the other hand, an equivalence structure has a $Σ_{2}$ -generically c.e. copy if and only if it has a c.e. copy, or, equivalently, it has a $Σ_{3}$ -generically c.e. copy.

A standard example of an equivalence structure which is not computably categorical is the so-called $(1, 2)$ -equivalence structure, which consists exactly of infinitely many equivalence classes in each of sizes one and two.

Theorem 1.11 (Proved as Theorem 2.13).

If $A$ and $B$ are $Σ_{1}$ -generically c.e. $(1, 2)$ -equivalence structures such that in each structure the set of elements in equivalence classes of size 2 is dense, then $A$ and $B$ are generically computably isomorphic.

Moreover, we have examples of equivalence structures with elements of only two finite sizes which are not weakly generically computably isomorphic.

With respect to coarsely computable isomorphism, we show the following.

Theorem 1.12 (Proved as Theorem 3.6).

Let $A = (A, R)$ and $B = (B, S)$ be isomorphic equivalence structures, and suppose that in each structure there is a dense set of elements in equivalence classes of size one. Then there is a density preserving coarsely computable isomorphism between $A$ and $B$ .

Theorem 1.13 (Proved as Theorem 3.12).

Suppose that $A$ and $B$ are computable $(1, 2)$ -equivalence structures with universe ω such that the asymptotic density of $A (1)$ and $B (1)$ both equal the same computable real number q. Then $A$ and $B$ are weakly coarsely computably isomorphic.

In the present paper, we consider the following notions of isomorphism:

Generically computable isomorphism

Weakly generically computable isomorphism

Density preserving generically computable isomorphism

Coarsely computable isomorphism

Weakly coarsely computable isomorphism

Density preserving coarsely computable isomorphism

For each of these notions, we give partial characterizations in the context of injection structures or equivalence structures, and, in some cases, both. The major goal of these partial characterizations is to elucidate the structural meaning of each notion of isomorphism, demonstrating their differences from one another and from (classically) computable isomorphism. Of course, conditions weaker than isomorphism (e.g., monomorphism or epimorphism) would also be interesting, but we do not take up those notions separately in the present paper. In Section 2, we investigate generically computable isomorphisms and their weaker variants. In Section 3, we investigate coarsely computable isomorphisms and their weaker variants. In both sections our main examples on which we demonstrate various phenomena are equivalence structures and injection structures.

2. Generically computable isomorphisms

In this section, we consider isomorphisms that are densely computable. Thus, we first need to extend these notions from sets and relations to functions.

Definition 2.1.
Let $F : ω \to ω$ be a total function.
We say that F is generically computable if there is a partial computable function θ such that $θ = F$ on the domain of θ, and such that the domain of θ has asymptotic density 1.

We say that F is coarsely computable if there is a total computable function θ such that ${n : F (n) = θ (n)}$ has asymptotic density 1.

It is easy to see that a set S is generically computable if and only if $c_{S}$ is generically computable and likewise for coarsely computable sets.

We have already stated the Definition 1.3 of a generically computable isomorphism. We also want to consider the following weaker notion.
Definition 2.2.
We say that structures $A$ and $B$ are weakly generically computably isomorphic if there are a c.e. set C of asymptotic density one, a bijection $F : A \to B$ , and a partial computable function θ with $C = Dom (θ)$ , which satisfy the following:
C is the domain of a substructure $C$ of $A$ ;

$F (x) = θ (x)$ for all $x \in C$ ;

$F [C]$ has asymptotic density one and is the domain of a substructure $C_{1}$ of $B$ .

θ is an isomorphism from $C$ to $C_{1}$ .

It is important here that the function F is only a bijection, whereas θ is an isomorphism. Of course, a generically computable isomorphism is also a weakly generically computable isomorphism. As for generically computable isomorphisms, the bijection F need not be effective, but its restriction to the dense set C is effective. In fact, for the most part, the results below on this definition (and also on the corresponding notion of weakly coarsely computably isomorphic) regard structures that are actually isomorphic (although not effectively), although the definition does not require that.
Proposition 2.3.

Any generically computable isomorphism F is a generically computable function.

If F is a generically computable (weakly generically computable, resp.) isomorphism mapping structure $A$ to structure $B$ , then $F^{- 1}$ is a generically computable (weakly generically computable, resp.) isomorphism from $B$ to $A$ .

Proof.
(1) This is immediate from the definitions.

(2) Let $F : A \to B$ be a generically computable isomorphism and let C and θ be given as in the definition. The image $F [C] = θ [C]$ is a c.e. set. Define the partial computable function ψ to be $θ^{- 1}$ , that is, $ψ (b) = a$ if and only if $θ (a) = b$ . Then if $ψ (b) = a$ , it follows that $F (a) = b$ and, therefore, $F^{- 1} (b) = a$ . The domain of ψ equals the range of θ and is, therefore, asymptotically dense since $θ [C] = F [C]$ . □

It follows that if $A$ is (weakly) generically computably isomorphic to $B$ , then $B$ is (weakly) generically computably isomorphic to $A$ . Thus, the relation of being (weakly) generically computably isomorphic is symmetric. To obtain a transitive relation, we need the notion of density preserving, defined in Section 1.
Example 2.4.
For any two dense c.e. sets A and B, and structures $A = (ω, A)$ and $B = (ω, B)$ , there is a weakly generically computably density preserving isomorphism from $A$ to $B$ . Here, we let $D = A \cap B$ be the needed c.e. set of density one, so that the substructure of $(ω, A)$ with universe D is simply $(D, D)$ , and likewise for $(ω, B)$ . Then the desired bijection from $A$ to $B$ is just the identity map, which is an isomorphism from $(D, D)$ to itself.
Proposition 2.5.
Suppose that $F_{1} : A_{1} \to A_{2}$ and $F_{2} : A_{2} \to A_{3}$ are generically computable (weakly generically computable, resp.) density preserving isomorphisms. Then the composition $F_{2} \circ F_{1} : A_{1} \to A_{3}$ is a generically computable (weakly generically computable, resp.) density preserving isomorphism.
Proof.
The proof is essentially the same for generically computable isomorphisms and for weakly generically computable isomorphisms. For a structure $A$ we will use A to denote its domain, and will adopt similar notation for other structures. Given $F_{1}$ and $F_{2}$ as above, certainly $F_{2} \circ F_{1}$ is a bijection from the structure $A_{1}$ to the structure $A_{3}$ . For any $E \subseteq A_{1}$ and any δ, E has density δ if and only if $F_{1} [E]$ has density δ, and $(F_{2} \circ F_{1}) [E]$ has density δ if and only if $F_{1} [E]$ has density δ. Thus, $F_{2} \circ F_{1}$ is density preserving.

Let $C_{1} \subseteq A_{1}$ and $C_{2} \subseteq A_{2}$ be dense c.e. sets such that each $C_{i}$ is the domain of a substructure of $A_{i}$ . Let $θ_{1}$ and $θ_{2}$ be partial computable functions such that $F_{1} = θ_{1}$ on $C_{1}$ , and $F_{2} = θ_{2}$ on $C_{2}$ . Then $F_{1} [C_{1}] \cap C_{2}$ is the domain of a substructure of $A_{2}$ since both $F_{1} [C_{1}]$ and $C_{2}$ are the domains of substructures. The set $F_{1} [C_{1}] \cap C_{2}$ has asymptotic density 1 since both $F_{1} [C_{1}]$ and $C_{2}$ have density 1. The set $D = F_{2} [F_{1} [C_{1}] \cap C_{2}]$ has asymptotic density 1 since $F_{2}$ is density preserving. Now, let $C = C_{1} \cap F_{1}^{- 1} [C_{2}]$ . Then C has asymptotic density 1 since $F_{1}$ is density preserving and $F_{1} [C] = F_{1} [C_{1}] \cap C_{2}$ . Finally, let $D = (F_{2} \circ F_{1}) [C]$ . Then D has asymptotic density 1. The set D also equals $θ_{2} [C_{2} \cap θ_{1} [C_{1}]]$ and hence is a c.e. set. The composition $θ_{2} \circ θ_{1}$ is partial computable, agrees with $F_{2} \circ F_{1}$ on C, and is a isomorphism from the structure $C$ with the domain C to the structure $D$ with the domain D. □

We have shown that the relation of generically computable density preserving isomorphism is transitive, by showing that if we have generically computable density preserving isomorphisms $F_{1} : A_{1} \to A_{2}$ and $F_{2} : A_{2} \to A_{3}$ , their composite is a generically computable density preserving isomorphism. The following example shows that this compositional strategy does not work without the hypothesis that the functions are density preserving.
Example 2.6.
Recall that a weakly generically computable isomorphism from $A$ to $B$ is a multifaceted object including a function F, dense subsets $A_{0} \subseteq A$ and $B_{0} \subseteq B$ and a computable function θ.

Now let $A = B = C$ all be the plain structure ω with no relations or functions. Let $E_{0} = {2^{n} : n > 0}$ and $E_{1} = {3^{n} : n > 0}$ .

We now construct weakly generically computable isomorphisms whose composition is not a weakly generically computable isomorphism. Let $F : A \to B$ be the identity function mapping dense subset $A_{0} = ω - E_{0}$ to dense set $B_{0} = ω - E_{0}$ . Let $G : B \to C$ be a computable bijection mapping dense subset $B_{1} = ω - E_{1}$ to dense set $C_{1} = ω - E_{1}$ , such that G maps $E_{1}$ to $E_{1}$ , maps $E_{0}$ to $ω - (E_{0} \cup E_{1})$ and thus maps $ω - (E_{0} \cup E_{1})$ to $E_{0}$ . Consequently, the composition $G \circ F$ maps the dense set $A_{0}$ to the non-dense set $E_{0} \cup E_{1}$ .

Curiously, the following question remains open.
Question 2.7.
Let $F_{1} : A_{1} \to A_{2}$ and $F_{2} : A_{2} \to A_{3}$ be (weakly) generically computable isomorphisms. Must there be a (weakly) generically computable isomorphism from $A_{1}$ to $A_{3}$ ?

A slight modification of the definition of a computably generic structure leads to the following connection with a generically computable isomorphism.
Proposition 2.8.
Suppose that a structure $A$ has a c.e. substructure $D$ on a dense computable set, the domain of $D$ . Then there are a c.e. structure $B$ and a weakly generically computable density preserving isomorphism from $A$ to $B$ . Moreover, if there is a weakly generically computable density preserving isomorphism from $A$ to a c.e. structure, then $A$ is generically computable.
Proof.
Let D be a computable set of density one such that $D$ is a c.e. substructure of $A$ , that is, each relation on D is c.e. and each function on D is the restriction of a partial computable function. Extend $D$ to a c.e. structure on ω by making the relations and functions trivial on $A - D$ . That is, all relations are uniformly true, and all functions are just a projection to the first input. Then the identity is a bijection and the restriction to $D$ is an isomorphism. The second statement is immediate from the definitions. □

It was shown in [4] that a computable injection structure is computably categorical if and only if it has finitely many infinite orbits. Thus we are led to the following natural result.
Theorem 2.9.

Let $A = (ω, f)$ and $B = (ω, g)$ be isomorphic computable injection structures with a specified finite number of elements $a_{1}, \dots, a_{k} \in A$ and $b_{1}, \dots, b_{k} \in B$ where, for each i, $a_{i}$ and $b_{i}$ have infinite orbits of the same type. Suppose that $Fin (A) \cup ⋃_{1 ⩽ i ⩽ k} O_{f} (a_{i})$ and $Fin (B) \cup ⋃_{1 ⩽ i ⩽ k} O_{g} (b_{i})$ are asymptotically dense. Then $A$ and $B$ are generically computably isomorphic.

Any computable injection structure $A$ , with a specified finite number of infinite orbits ${O_{f} (a_{i}) : i = 1, \dots, k}$ such that $Fin (A) \cup ⋃_{1 ⩽ i ⩽ k} O_{f} (a_{i})$ is asymptotically dense (of course, it may not be the whole domain of the structure, if there are other orbits not included among the $O_{f} (a_{i})$ ), is generically computably isomorphic to a computable structure $C$ such that $Fin (C)$ is computable.

Proof.
For part (1), we note that $Fin (A)$ is a c.e. set and that each orbit $O_{f} (a_{i})$ is also a c.e. set. Hence the structure $A_{1}$ , where $A_{1} = Fin (A) \cup ⋃_{1 ⩽ i ⩽ k} O_{f} (a_{i})$ , is a c.e. injection structure. A structure $B_{1}$ can be similarly defined. It follows from Theorem 7.4 of [4] that there is a partial computable function ψ that defines an isomorphism from $A_{1}$ to $B_{1}$ .

This function may be extended to an isomorphism F from $A$ to $B$ as follows. Since $A$ and $B$ are isomorphic, there is an isomorphism $G : A \to B$ . Define F so that $F (a) = G (a)$ for $a \in ω - A_{1}$ and $F (a) = ψ (a)$ for $a \in A_{1}$ . Note that, since $A_{1}$ consists of complete orbits, $a \in ω - A_{1}$ implies that $F (a) \in ω - A_{1}$ . It follows that F is indeed an isomorphism.

Toward part (2), let B be the dense set $Fin (A) \cup ⋃_{1 ⩽ i ⩽ k} O_{f} (a_{i})$ and let $B$ be the substructure of $A$ with domain B. Since $A$ is computable, $χ (A)$ is a c.e. set, and therefore, by 3.4 of [1] there is a computable structure $B_{1}$ isomorphic to $B$ such that $Fin (B_{1})$ is computable. Let $E$ be the substructure of $A$ with universe $ω - B$ . This consists of some countable number of infinite orbits, so there is a computable structure $B_{2}$ isomorphic to $E$ . The desired structure $C$ consists of a copy of $B_{1}$ with domain a dense co-infinite computable set $C_{1}$ and a copy of $B_{2}$ with universe $ω - C_{1}$ . Let ${b_{1}, \dots, b_{k}}$ be elements of the copies in $C$ of the k specified infinite orbits of $C$ such that each $b_{i}$ has the same orbit type as $a_{i}$ . Then $A$ is generically computably isomorphic to $C$ by part (1). □

It should be noted that there need not be any computable, or even $Δ_{2}^{0}$ , isomorphism between the structures described in Theorem 2.9

Theorem 2.9 applies, in particular, when $Fin (A)$ and $Fin (B)$ are both dense and when $A$ and $B$ each have a single infinite orbit, of the same type, which is dense. In the latter case, there is a stronger result.
Theorem 2.10.
Suppose that $A$ and $B$ are isomorphic $Σ_{1}$ -generically c.e. injection structures such that each has a single infinite orbit (of the same type) which constitutes an asymptotically dense set. Then $A$ and $B$ are generically computably isomorphic.
Proof.
Let $O_{f} (a)$ be dense in $A = (A, f)$ and let $O_{g} (b)$ be dense in $B$ , where the two orbits are infinite and of the same type. Since each structure is generically c.e., there exist dense c.e. sets $C \subseteq A$ and $D \subseteq B$ such that the corresponding structures $C$ and $D$ are $Σ_{1}$ elementary substructures of $A$ and $B$ (resp.). Then $C \cap O_{f} (a)$ is dense and therefore nonempty. Since $C$ is a $Σ_{1}$ elementary substructure of $A$ , this means that $O_{f} (a) \subseteq C$ . Similarly, we show that $O_{g} (b) \subseteq D$ . Furthermore, there are partial computable functions ϕ and ψ such that $ϕ = f$ on C and $ψ = g$ on D. Thus, the structures $O_{f} (a)$ and $O_{g} (b)$ are c.e. structures, and the argument from Part 2 of Theorem 2.9 again provides a partial computable isomorphism from $O_{f} (a)$ to $O_{g} (b)$ which may be extended arbitrarily from $A$ to $B$ . □

We observe that this result does not necessarily hold even when there are two infinite orbits with a dense union. This is because one orbit may be dense in the first structure whereas each infinite orbit may have density less than one in the second. Similarly, the argument can fail for injection structures with only finite orbits. Now we turn to equivalence structures.
Definition 2.11.
We say that the equivalence structure $A = (ω, E)$ has generic character K for a finite subset K of $ω - {0}$ if, for each $k \in K$ , the set $A (k)$ has positive asymptotic density and the union $⋃_{k \in K} A (k)$ has asymptotic density one.

Thus, if the generic character of $A$ is ${k}$ for some $k < ω$ , then the set of all elements of $A$ with equivalence classes of size k has asymptotic density one.

The classic example of a computable equivalence structure that is not computably categorical is one which consists of infinitely many classes of size 1 and infinitely many classes of size 2. Indeed, there are computable structures of this kind which are not computably isomorphic. We will call such an equivalence structure $A$ a $(1, 2)$ -equivalence structure. The next result shows that under certain density conditions two computable $(1, 2)$ -equivalence structures will be generically computably isomorphic.
Theorem 2.12.

If $A$ and $B$ are computable $(1, 2)$ -equivalence structures, each having generic character ${2}$ , then $A$ and $B$ are generically computably isomorphic.

Any computable $(1, 2)$ -equivalence structure $A$ with generic character ${2}$ is generically computably isomorphic to a computable structure $C$ in which the set of elements of size 2 is computable.

Proof.
(1) The elements in $A$ of type 2 form a c.e. set, so the classes of size 2 may be computably enumerated as ${a_{0}, a_{1}}$ , ${a_{2}, a_{3}}$ , …. That is, there is a computable enumeration of the set of pairs ${(x, y) : x \neq y \land E (x, y)}$ . Similarly, $B (2)$ has a computable enumeration ${b_{0}, b_{1}}$ , ${b_{2}, b_{3}}$ , …. Then a partial computable function may be defined so that $ϕ (a_{n}) = b_{n}$ for all n; the inverse of ϕ is also partial computable. This partial isomorphism can be extended as before on the elements of type one to produce a generically computable isomorphism $F : A \to B$ .

(2) The statement follows from (1). □

This result also holds for $Σ_{1}$ -generically c.e. equivalence structures.
Theorem 2.13.
If $A$ and $B$ are $Σ_{1}$ -generically c.e. $(1, 2)$ -equivalence structures, each having generic character ${2}$ , then $A$ and $B$ are generically computably isomorphic.
Proof.
The following lemma is needed. Lemma 2.14.
A dense c.e. set C has a co-infinite dense c.e. subset D. Furthermore, if C is a c.e. set of distinct k-tuples, for a fixed k, then C has a co-infinite dense c.e. subset of k-tuples.
Proof.
Let C be a dense c.e. set with one-to-one computable enumeration $c_{0}, c_{1}, \dots$ and let $C_{n} = {c_{0}, \dots, c_{n - 1}}$ . The construction of the set D will delete, for each $n > 0$ , an element of the interval $[2^{n}, 2^{n + 1})$ from C whenever $C \cap [2^{n}, 2^{n + 1})$ is nonempty.

Stage 0: $D_{0} = \emptyset$ .

Stage $s + 1$ : Given $D_{s} \subseteq C_{s}$ , find n such that $2^{n} ⩽ c_{s + 1} < 2^{n + 1}$ and check to see whether there is $t < s$ such that $2^{n} ⩽ c_{t} < 2^{n}$ . If not, then $D_{s + 1} = D_{s}$ . If so, then $D_{s + 1} = D_{s} \cup {c_{s + 1}}$ .

It follows from the construction that D is a c.e. subset of C. Since C is dense and therefore infinite, there must be infinitely many n such that $C \cap [2^{n}, 2^{n + 1}) \neq \emptyset$ . Thus $C - D$ is infinite.

For each n, $C - D$ has at most one element in $[2^{n}, 2^{n + 1})$ (and none less than 2) and therefore at most n elements less than $2^{n + 1}$ . This implies as follows that $C - D$ has asymptotic density 0.

Given any m, let n be such that $2^{n} ⩽ m < 2^{n + 1}$ . Then $\begin{matrix} \frac{| m \cap (C - D) |}{m} ⩽ \frac{n}{m} ⩽ \frac{log m}{m} . \end{matrix}$

It follows that ${lim}_{m \to \infty} \frac{| m \cap (C - D) |}{m} = 0$ , and therefore $C - D$ has asymptotic density zero. This implies that D has asymptotic density 1.

For the second part, the above argument is modified so that at most k elements are deleted from an interval $[2^{n}, 2^{n + 1})$ . Suppose that C is partitioned into distinct (un-ordered) tuples $\vec{a_{0}}, \vec{a_{1}}, \dots$ . Then, at stage $s + 1$ , we put ${\vec{a}}_{s + 1}$ into $D_{s + 1}$ unless every element of ${\vec{a}}_{s + 1}$ belongs to an interval from which no elements have previously been deleted. When $D_{s + 1} = D_{s}$ , it may be that two or more elements fall into the same interval, but at most k. □

We now proceed with the proof of the theorem. Let $C \subseteq A$ and $D \subseteq B$ be dense c.e. sets such that the corresponding structures $C$ and $D$ are $Σ_{1}$ elementary c.e. substructures. Then $C (2)$ and $D (2)$ are dense c.e. sets with $C (2) = C \cap A (2)$ and $D (2) = D \cap B (2)$ (this is possible because of $Σ_{1}$ elementarity). If necessary, use Lemma 2.14 to obtain dense c.e. subsets $C_{2} \subseteq C (2)$ and $D_{2} \subseteq D (2)$ so that $A (2) - C_{2}$ and $B (2) - D_{2}$ are both infinite. The argument from Theorem 2.12 provides a partial computable isomorphism from the dense c.e. substructure $C (2)$ to the dense c.e. substructure $D (2)$ , which may be extended to an isomorphism from $A$ to $B$ , since $A - D (2)$ and $B - D (2)$ will be isomorphic, both consisting of infinitely many classes of size one and infinitely many classes of size 2. □

This result can be generalized to structures having generic character ${k}$ and only finitely many classes of size $> k$ . For infinite classes, we have the following.
Theorem 2.15.
If $A$ and $B$ are isomorphic computable equivalence structures with finitely many infinite classes such that the infinite classes constitute a set of asymptotic density 1 in each structure, then $A$ and $B$ are generically computably isomorphic. It follows that any such structure $A$ is generically computably isomorphic to a computable structure $C$ in which the set of elements that belong to infinite classes is computable.
Proof.
Suppose that $A$ has m infinite classes and let $a_{i}$ be the least element of its class for $i = 1, \dots, m$ . Similarly, define $b_{1}, \dots, b_{m}$ from $B$ . Then each class $[a_{i}]$ is computable and we may define a computable partial function mapping each class $[a_{i}]$ to the class $[b_{i}]$ . This partial isomorphism can be extended as before on the finite classes to produce a generically computable isomorphism $F : A \to B$ . □

There is also a result for $Σ_{1}$ -generically c.e. equivalence structures.
Theorem 2.16.
Let $A$ and $B$ be isomorphic $Σ_{1}$ -generically c.e. equivalence structures, each with a single infinite class of asymptotic density 1. Then $A$ and $B$ are generically computably isomorphic.
Proof.
Let the infinite equivalence class $C_{1}$ be dense in $A$ , and let the infinite class $D_{1}$ be dense in $B$ . Since each structure is $Σ_{1}$ -generically c.e., there exist dense c.e. sets $C \subseteq A$ and $D \subseteq B$ such that the corresponding structures $C$ and $D$ are $Σ_{1}$ elementary substructures of $A$ and $B$ (resp.). Then $C \cap C_{1}$ is dense and, therefore, nonempty, so we can choose some $a \in C \cap C_{1}$ . Since $C$ is a $Σ_{1}$ elementary substructure of $A$ , this means that $[a] \cap C$ is infinite. Using Lemma 2.14, we may assume that $[a] - C$ is also infinite. Similarly, we can find $b \in B$ so that $[b] \cap D$ is dense and $[b] - D$ is infinite. Furthermore, the equivalence relations on C and D are both c.e. and we may define a partial computable isomorphism ψ from $[a] \cap C$ to $[b] \cap D$ . This partial isomorphism can be extended to produce a generically computable isomorphism $F : A \to B$ , although the extension is not so arbitrary as in earlier results because it is necessary to distinguish equivalent and inequivalent elements not in the dense parts. □

On the other hand, if $A$ and $B$ have generic character ${k}$ but have infinitely many classes of sizes larger than k, we will show that no similar result holds. Jockusch and Schupp [8] constructed a simple (hence c.e.) set with density 0. In that case, the complement is an immune co-c.e. set of density 1. (For immune and simple sets see [11].) We extend that result as follows. Lemma 2.17.
For any rational number p with $0 < p ⩽ 1$ , there is an immune co-c.e. set P of asymptotic density p.
Proof.
It is shown in Proposition 2.15 in [8] that there is a simple set B of asymptotic density zero. Thus, the complement $D = ω - B$ has density one. Given $p = \frac{m}{n}$ , let $P = {k n + i : i < m and k \in D}$ . Then P has asymptotic density p, and if K were an infinite c.e. subset of P, then J would be an infinite subset of K, where $k \in J \Leftrightarrow (\exists i < n) (k n + i \in K)$ . □
Theorem 2.18.
For any $k > 1$ and any rational number p with $0 < p ⩽ 1$ , there exist computable $(1, k)$ -equivalence structures $A$ and $B$ such that $A (1)$ and $B (1)$ each have asymptotic density p, which are not weakly generically computably isomorphic.
Proof.
Let P be an immune co-c.e. set of asymptotic density p as in Lemma 2.17. Then, by Theorem 4.1 of [3], there is a computable $(1, k)$ -equivalence structure $A$ with $A (1) = P$ . We compare this with some standard computable structure $B$ isomorphic to $A$ such that $B (1)$ is a computable set of density p.

Now suppose, by way of contradiction, that $A$ and $B$ were weakly generically isomorphic. Let C be an asymptotically dense c.e. set which is the domain of a substructure $C$ of $A$ . Let $F : A \to B$ be a bijection, such that the set $F [C] = D$ is asymptotically dense and is the domain of a substructure $D$ of $B$ , and such that F restricted to $C$ is an isomorphism. Finally, let θ be a partial computable function which agrees with F on the set C. Then the set $B (1) \cap D$ will have asymptotic density p as the intersection of a set of density 1 with a set of density p, so $D (1) \cap D$ is infinite. The set $B (1) \cap D$ is c.e. since D is c.e. and $B (1)$ is computable. Since θ is a isomorphism from $C$ to $D$ , the inverse image $θ^{- 1} [B (1) \cap D]$ is a c.e. subset of $A (1)$ . Then we will obtain an infinite c.e. subset of $A (1)$ , contrary to the assumption that $A (1)$ is immune. □

3. Coarsely computable isomorphisms

In this section, we explore the notions of coarsely computable and weakly coarsely computable isomorphisms.

Recall the definition of a coarsely computable isomorphism.

Definition 3.1.
We say that an isomorphism $F : A \to B$ from a structure $A$ to a structure $B$ is a coarsely computable isomorphism if there are a set C of asymptotic density one and a (total) computable bijection θ such that:
C is the domain of a substructure $C$ of $A$ ;

$F (x) = θ (x)$ for all $x \in C$ ;

The image $F [C]$ has asymptotic density one.

It is easy to see that if $A$ is coarsely computably isomorphic to a computable structure, then $A$ is a coarsely computable structure.
Definition 3.2.
We say that structures $A$ and $B$ are weakly coarsely computably isomorphic if there is a set C of asymptotic density one, a bijection $F : A \to B$ and a total computable bijection θ, which satisfy the following:
C is the domain of a substructure $C$ of $A$ ;

$F (x) = θ (x)$ for all $x \in C$ ;

The image $F [C]$ also has asymptotic density one and is the universe of a substructure of $B$ ;

θ is an isomorphism from $C$ to its image.

As for the previous definition of weakly generically isomorphic, it is important to note that F is only a bijection, whereas θ is a structural isomorphism. Moreover, if F is a weakly coarsely computable isomorphism, then $F^{- 1}$ is, as well. We know even less about the transitivity of isomorphism here than we do in the generic case.
Question 3.3.
Is the composition of (weakly) coarsely computable isomorphisms a (weakly) coarsely computable isomorphism?
Proposition 3.4.
If a structure $A$ is coarsely computable, then there is a density preserving weakly coarsely computable isomorphism from $A$ to a computable structure. Conversely, if there is a weakly coarsely computable isomorphism from $A$ to a computable structure, then $A$ is coarsely computable.
Proof.
Suppose $A$ is coarsely computable. Then there is a computable structure $E$ , and a dense set D such that the structure $D$ with domain D is a substructure of both $A$ and $E$ , and all relations and functions agree on D. Then the identity function serves as the desired isomorphism.

For the other direction, suppose there is a weakly coarsely computable isomorphism F from $A$ to a computable structure $B$ with dense set C and computable bijection θ as in Definition 3.2. Let $E$ be the computable structure $θ^{- 1} (B)$ . Then the structure $C$ is also a substructure of $E$ , so that $A$ is coarsely computable, as desired. □
Example 3.5.
Let A and B be dense sets, and $A = (ω, A)$ and $B = (ω, B)$ the corresponding structures with unary relations. Now, there is a weakly coarsely computable isomorphism from $A$ to $B$ because $A \cap B$ is a dense set, and we argue as in Example 2.4.

In contrast to Theorem 2.18, we have the following result, which distinguishes the notion of a coarsely computable isomorphism from the notion of a weakly generically computable isomorphism.
Theorem 3.6.
Let $A = (A, R)$ and $B = (B, S)$ be isomorphic equivalence structures with generic character ${1}$ (that is, both $A (1)$ and $B (1)$ have asymptotic density one). Then there is a density preserving coarsely computable isomorphism between $A$ and $B$ .
Proof.
Define the set U to be $A (1) \cap B (1)$ . By assumption, U has asymptotic density one. Now, the identity function $ϕ (x) = x$ is a total computable function and acts as an isomorphism of $(U, R)$ to $(U, S)$ . We want to arbitrarily extend ϕ to an isomorphism $F : A \to B$ . The only difficulty might be that $A (1) - U$ and $B (1) - U$ have different cardinalities, say, without loss of generality, that $B (1) - U$ is smaller. We can then remove from U a subset of $B (1)$ of density zero to produce a set $V \subseteq U$ of density one such that $A (1) - V$ and $B (1) - V$ have the same cardinality. This will make $A - V$ isomorphic to $B - V$ , so that we may extend ϕ from V to an isomorphism F from $A$ to $B$ , which agrees with ϕ on the set V of density one. □

This result has a converse, as follows. Suppose that there is a density preserving coarsely computable isomorphism F from a structure $A$ with generic character ${1}$ to an arbitrary structure $B$ . Let C be a dense set given by the definition. Then $C (1) = C \cap A (1)$ is dense and $F [C (1)] = F [C] \cap B (1)$ is also dense, so $B (1)$ has asymptotic density 1.

It is not clear whether Theorem 3.6 can be extended, even to structures with generic character ${k}$ for $k ⩾ 2$ .

Recall from [2] that a computable equivalence structure $A$ is computably categorical if and only if one of the following holds:

$A$ has only finitely many finite equivalence classes, or

$A$ has finitely many infinite classes, there is a bound on the size of the finite equivalence classes, and there is at most one k such that $A$ has infinitely many classes of size k.

We have seen by now a number of examples of structures which are not computably categorical but which satisfy a version of generically or coarsely computable categoricity.

Next, we look at structures where the densities are positive but not 1. We will again focus here on $(1, 2)$ -equivalence structures. From the examples seen so far we might suspect that different densities pose a barrier to asymptotically computable isomorphism in such structures. We will see that, at least for weakly coarsely computable isomorphism, they do not.

The following proposition is of interest, and clarifies the impact of the theorems that follow.
Proposition 3.7.

Let $A$ be a computable $(1, 2)$ -equivalence structure.

The asymptotic density of $A (1)$ is a $Δ_{3}^{0}$ real;

If $A (1)$ is computable, then its asymptotic density is $Δ_{2}^{0}$ .

For any $Δ_{2}^{0}$ real $q \in [0, 1]$ , there is a computable $(1, 2)$ -equivalence structure $A$ such that $A (1)$ is computable and has asymptotic density q.

Proof.
(1a) Given an oracle for $0^{'}$ , we can compute whether $n \in A (1)$ uniformly in n, so we can compute the sequence $\frac{| A (1) \cap n |}{n}$ uniformly in n. Since the asymptotic density of $A (1)$ is given by ${lim}_{n \to \infty} \frac{| A (1) \cap n |}{n}$ , this means the density is $Δ_{2}^{0}$ relative to $0^{'}$ , and therefore $Δ_{3}^{0}$ .

For part (1b), $A (1)$ is computable so the sequence $\frac{| A (1) \cap n |}{n}$ is computable uniformly in n, and thus the density, as a limit of a computable sequence, is $Δ_{2}^{0}$ computable.

(2) Let q be a computable real. There are two cases.

First suppose that $q = \frac{k}{m}$ is rational. Then $A$ will be defined in blocks of $2 m$ elements, of the form $α_{i} = {2 i m + ℓ : ℓ ⩽ 2 m - 1}$ , including in each $α_{i}$ a collection of $2 k$ classes of size 1 given by ${2 i m + ℓ : ℓ ⩽ 2 k - 1}$ , and a collection of $m - k$ classes of size 2 (the rest of $α_{i}$ ). Thus the density $\frac{| A (1) \cap 2 m n |}{2 m n}$ will be q for all n.

For arbitrary $j = 2 m n + i$ , with $i < 2 m$ , we have $2 k n ⩽ | A (1) \cap j | ⩽ 2 k (n + 1)$ , so that $\begin{matrix} q \cdot \frac{n}{n + 1} = \frac{2 k n}{2 m (n + 1)} ⩽ \frac{2 k n}{2 m n + i} ⩽ \frac{| A (1) \cap j |}{j} ⩽ \frac{2 k (n + 1)}{2 m n + i} ⩽ \frac{2 k (n + 1)}{2 m n} = q \cdot \frac{n + 1}{n} \end{matrix}$ Since $\frac{n}{n + 1}$ converges to 1 from below and $\frac{n + 1}{n}$ converges to 1 from above, it follows that the density of $A (1)$ is exactly q.

Next suppose that q is irrational. Then we can uniformly compute, for each n, the unique $i = i_{n} ⩽ n$ such that $| q - \frac{i}{n} | < \frac{1}{2 n}$ . We will build a structure $A$ with $A (1)$ computable and of asymptotic density q in stages, $A_{n}$ on the elements ${0, 1, \dots, 2 n - 1}$ , so that for $q_{n} = \frac{| A (1) \cap n |}{n}$ , we have $q_{n} = \frac{i_{n}}{n}$ , and thus $| q - q_{n} | ⩽ \frac{1}{2 n}$ . It will follow as in the rational case above that $A (1)$ has the desired asymptotic density q.

At stage 1, either $i_{1} = 0$ or $i_{1} = 1$ . If $i_{1} = 0$ , then we construct $A_{1}$ to have one equivalence class ${0, 1}$ , so that $q_{1} = 0$ . If $i_{1} = 1$ , then we construct $A_{1}$ to have two classes ${0}$ and ${1}$ , so that $q_{1} = 1$ . In either case, $| q - q_{1} | ⩽ \frac{1}{2}$ , by the choice of $i_{1}$ .

At stage $n + 1$ , we are given $A_{n}$ with universe $2 n$ and $\frac{i_{n}}{n} = q_{n} = \frac{| A_{n} (1) |}{2 n}$ , where $| q - q_{n} | ⩽ \frac{1}{2 n}$ , that is, $\frac{i_{n} - 1}{2 n} ⩽ q ⩽ \frac{i_{n} + 1}{2 n}$ . It follows that $\frac{i_{n} - 1}{2 n + 2} < q < \frac{i_{n} + 3}{2 n + 2}$ so that either
$\frac{i_{n} - 1}{2 n + 2} < q < \frac{i_{n} + 1}{2 n + 2}$ , or

$\frac{i_{n} + 1}{2 n + 2} < q < \frac{i_{n} + 3}{2 n + 2}$ .
In case (i), we have $i_{n + 1} = i_{n}$ and we extend $A_{n}$ to $A_{n + 1}$ by adding the class ${2 n, 2 n + 1}$ , so that $q_{n + 1} = \frac{i_{n}}{2 n + 2}$ . In case (ii), we have $i_{n + 1} = i_{n} + 2$ and we add the classes ${2 n}$ and ${2 n + 1}$ , so that $q_{n + 1} = \frac{i_{n} + 2}{2 n + 2}$ .

This completes the construction. The set $A (1)$ is computable since we decide the classes of all $j < 2 n$ by stage n. □
Lemma 3.8.
If two isomorphic computable equivalence structures $A$ and $B$ have bounded character, and for each $n ⩽ ω$ , $A (n)$ and $B (n)$ are computable, then $A$ and $B$ are computably isomorphic.
Proof.
Since each $A (n)$ is computably categorical, it is computably isomorphic to $B (n)$ . For any $x \in A$ , we can effectively determine the unique n such that $x \in A (n)$ , since the character is bounded. We then choose the appropriate isomorphism to apply for x. □
Theorem 3.9.
Suppose that $A = (ω, R)$ is a computable $(1, 2)$ -equivalence structure such that $A (1)$ has computable asymptotic density q, where $0 < q < 1$ . Then there are a computable structure $B$ , such that $B (1)$ is a computable set with asymptotic density q, and a density preserving weakly coarsely computable isomorphism from $A$ to $B$ .
Proof.
We build the structure $B$ as follows. Let $\begin{matrix} A^{s} (2) = {x ⩽ s : \exists y ⩽ s [(y \neq x) \land (x R y)]}, \end{matrix}$ and let $A^{s} (1) = s - A^{s} (2)$ . Then for each s, $A^{s} (2) ⊊ A (2)$ whereas $A (1) \cap s \subseteq A^{s} (1)$ . The idea of the proof is that classes of size two are observable and that the sets $A^{s} (1)$ approximate $A (1)$ . Thus, we will define $B = (ω, R_{B})$ so that $R_{B}$ is a subset of R and differs from R on a set of asymptotic density zero, so that we can use the identity as our bijection.

We define computable increasing sequences ${(n_{i})}_{i < ω}$ and ${(s_{i})}_{i < ω}$ with $2^{i} ⩽ n_{i} ⩽ s_{i}$ and define the relation $R_{B}$ for all pairs $(x, y)$ for all $x, y < n_{i}$ at stage $s_{i}$ , so that $R_{B}$ is computable. We will let $q_{i} = \frac{| A (1) \cap n_{i} |}{n_{i}}$ , so that ${lim}_{i \to \infty} q_{i} = q$ . Let $n_{0} = 1 = s_{0}$ . Given $n_{i}$ and $s_{i}$ , and having defined $R_{B}$ on all elements less than $n_{i}$ as well as some other elements less than $s_{i}$ , and having defined $B (1)$ up to $n_{i}$ , let $(n_{i + 1}, s_{i + 1})$ be the least pair $(n, s)$ such that $| A^{s} (1) \cap n | / n < q + 2^{- i}$ . Now extend the definition of $R_{B}$ and of $B (1)$ as follows. For any x, y with $n_{i} < x < y < s$ , let $x R_{B} y$ if and only if $x R y$ . For x such that $n_{i} ⩽ x < n_{i + 1}$ , put $x \in B (1)$ if there is no y with $x < y < s_{i + 1}$ such that $x R y$ . For y with $s_{i} ⩽ y < s_{i + 1}$ , put $y \in B (1)$ if there is $x \in B (1)$ such that $x R y$ . This is necessary to ensure that $B (1)$ is computable, so that we cannot change our mind about ${[x]}_{B}$ being a singleton once we have decided that it is. This also means that $B (1)$ will contain pairs x, y of elements where $x R y$ but y is much larger than x.

It is clear that $A (1) \subseteq B (1)$ and it remains to calculate the density of $B (1) - A (1)$ . Let $\begin{matrix} e_{i} = \frac{| (A^{s_{i}} (1) \cap n_{i}) - A (1) |}{n_{i}}; \end{matrix}$ these elements of $(A^{s_{i}} (1) \cap n_{i}) - A (1)$ are the only elements which may be put into $B (1)$ since they will have a partner larger than $n_{i}$ . Since $| A^{s_{i}} (1) \cap n_{i} | / n_{i} < q + 2^{- i}$ , it follows that $e_{i} < q - q_{i} + 2^{- i}$ . Since $A (1)$ has asymptotic density q and $n_{i} ⩾ 2^{i}$ , it follows that ${lim}_{i} q_{i} = q$ , and hence the set of elements where $R_{B}$ differs from R has asymptotic density zero. We observe that the desired set D of density one, $A (1) \cup B (2)$ , makes up a substructure, closed under equivalence classes, in both $A$ and $B$ .

Thus, the identity is a bijection which is an isomorphism between $A$ and $B$ on the set D of asymptotic density one, as desired. Note that, since $0 < q < 1$ , and $B (1) - A (1)$ has density zero, the set $B (1)$ will still have asymptotic density q. □

We observe that this result will also hold for $(1, k)$ -equivalence structures, that is, equivalence structures consisting of infinitely many classes of size 1 and infinitely many classes of size k for some finite $k > 1$ .
Lemma 3.10.
Suppose that $A = {a_{0} < a_{1} < \dots}$ has positive asymptotic density α and that ${lim}_{n \to \infty} \frac{| C \cap a_{n} |}{n} = 0$ . Then C has asymptotic density zero.
Proof.
Since A has positive density α and $A \cap a_{n} = {a_{0}, \dots, a_{n - 1}}$ , it follows that $\frac{| A \cap a_{n} |}{a_{n}} = \frac{n}{a_{n}}$ and thus ${lim}_{n \to \infty} \frac{n}{a_{n}} = α$ . Then $\begin{matrix} lim_{n \to \infty} \frac{a_{n}}{a_{n + 1}} = \frac{{lim}_{n \to \infty} \frac{n + 1}{a_{n + 1}}}{{lim}_{n \to \infty} \frac{n}{a_{n}}} = \frac{α}{α} = 1 . \end{matrix}$

For any $i > a_{0}$ , we have $a_{n} < i ⩽ a_{n + 1}$ for some n. Then $| C \cap a_{n} | ⩽ | C \cap i | ⩽ | C \cap a_{n + 1} |$ , so $\begin{matrix} \frac{| C \cap i |}{i} ⩽ \frac{| C \cap a_{n + 1} |}{a_{n}} = \frac{| C \cap a_{n + 1} |}{a_{n + 1}} \cdot \frac{a_{n + 1}}{a_{n}}, \end{matrix}$ so that ${lim}_{i \to \infty} \frac{| C \cap i |}{i} = 0$ , as desired. □
Lemma 3.11.
Let A and B be computable subsets of ω having positive asymptotic densities α and β, respectively. Suppose that $C \subseteq A$ and $D \subseteq B$ are c.e. sets, both of asymptotic density zero. Then there is a computable bijection $F : A \to B$ such that $F [C]$ and $F^{- 1} [D]$ each have asymptotic density zero.
Proof.
Let $A = {a_{0} < a_{1} < \dots}$ and $B = {b_{0} < b_{1} < \dots}$ . Let ${c_{0}, c_{1}, \dots}$ be a computable enumeration of C, and let ${d_{0}, d_{1}, \dots}$ be a computable enumeration of D, both without repetition. The goal is to define a map F so that it maps C to D modulo asymptotic density zero. The function F is defined in alternating stages as follows. Map $c_{0}$ to $d_{0}$ . If $a_{0} = c_{0}$ , then, of course, $F (a_{0}) = d_{0}$ . So suppose $a_{0} \neq c_{0}$ . If $b_{0} \neq d_{0}$ , then let $F (a_{0}) = b_{0}$ and otherwise, let $F (a_{0}) = b_{1}$ .

Then at stage $s + 1$ , we define $F (a_{s + 1})$ and $F (c_{s + 1})$ as follows. If $F (c_{s + 1})$ is not already defined, let $F (c_{s + 1}) = d_{j}$ for the least j such that $d_{j}$ is still available, that is, we have not already defined $F (a) = d_{j}$ for some a. Since we have only defined $s + 1$ values of F, it follows that $j ⩽ s + 1$ . If $F (a_{s + 1})$ is not already defined, let $F (a_{s + 1}) = b_{i}$ for the least i such that $b_{i}$ is still available and note here that $i ⩽ s + 1$ .

Since D has asymptotic density zero, it suffices to show that $F [C] - D$ has asymptotic density zero. By Lemma 3.10, it is enough to show that $\begin{matrix} lim_{n \to \infty} \frac{| (F [C] - D) \cap b_{n} |}{b_{n}} = 0 . \end{matrix}$

It follows from the construction that $\begin{matrix} (F [C] - D) \cap b_{n} \subseteq {F (a_{i}) : i < n and a_{i} \in C} . \end{matrix}$ It now follows that $\begin{matrix} | (F [C] - D) \cap b_{n} | ⩽ | C \cap a_{n} |, \end{matrix}$ and, therefore, $\begin{matrix} \frac{| (F [C] - D) \cap b_{n} |}{b_{n}} ⩽ \frac{| C \cap a_{n} |}{a_{n}} \cdot \frac{a_{n}}{b_{n}} . \end{matrix}$ Now we saw in the proof of Lemma 3.10 that ${lim}_{n \to \infty} n / a_{n} = α$ if ${a_{0} < a_{1} < \dots}$ has asymptotic density α, and similarly ${lim}_{n \to \infty} \frac{n}{b_{n}} = β$ , so that ${lim}_{n \to \infty} \frac{a_{n}}{b_{n}} = \frac{β}{α}$ . Since ${lim}_{n \to \infty} \frac{| C \cap a_{n} |}{a_{n}} = 0$ and ${lim}_{n \to \infty} \frac{a_{n}}{b_{n}} = \frac{β}{α}$ exists, it follows that ${lim}_{n \to \infty} \frac{| (F [C] - D) \cap b_{n} |}{b_{n}} = 0$ , as desired.

For the other part, we have $(F^{- 1} [D] - C) \cap a_{n} \subseteq {a_{i} : i < n and F (a_{i}) \in D}$ .

It now follows that $\begin{matrix} | (F^{- 1} [D] - C) \cap a_{n} | ⩽ | D \cap b_{n} |, \end{matrix}$ and, therefore, $\begin{matrix} \frac{| (F^{- 1} [D] - C) \cap a_{n} |}{a_{n}} ⩽ \frac{| D \cap b_{n} |}{b_{n}} \cdot \frac{b_{n}}{a_{n}} . \end{matrix}$

Since ${lim}_{n \to \infty} \frac{| D \cap b_{n} |}{b_{n}} = 0$ and ${lim}_{n \to \infty} \frac{b_{n}}{a_{n}} = α / β$ exists, it follows that $\begin{matrix} lim_{n \to \infty} \frac{| (F^{- 1} [D] - C) \cap a_{n} |}{a_{n}} = 0 \end{matrix}$ as desired. □
Theorem 3.12.
Suppose that $A$ and $B$ are computable $(1, 2)$ -equivalence structures with domain ω such that the asymptotic density of $A (1)$ and $B (1)$ both equal the same computable real q. Then $A$ and $B$ are weakly coarsely computably isomorphic.
Proof.
Let $A$ , $B$ and q be given as above. Let $C$ be the computable structure obtained from $A$ as a consequence of Theorem 3.9, and $D$ that obtained from $B$ in the same way. Note that $C (1)$ , $C (2)$ , $D (1)$ , and $D (2)$ are all computable sets, by the construction in the proof of Theorem 3.9. Moreover, the identity map is a weakly coarsely computable isomorphism from $A$ to $C$ , and from $B$ to $D$ . Additionally, $A (1) \subseteq C (1)$ , $B (1) \subseteq D (1)$ , $C (2) \subseteq A (2)$ , and $D (2) \subseteq B (2)$ . We also know from Theorem 3.9 that $C (1) - A (1)$ has density zero, as does $D (1) - B (1)$ .

Certainly there is a computable isomorphism $G_{2} : C (2) \to D (2)$ . Moreover, by Lemma 3.11, there is a computable isomorphism $G_{1}$ from $C (1)$ to $D (1)$ such that $G_{1} [C (1) - A (1)]$ and $G_{1}^{- 1} [D (1) - B (1)]$ each have asymptotic density zero.

Then the desired bijection $G : A \to B$ is defined as follows. Given $x \in A$ , there are two cases. If $x \in C (1)$ , then $F (x) = G_{1} (x)$ , and if $x \in C (2)$ , then $F (x) = G_{2} (x)$ . Let $E = C (2) \cup (A (1) \cap G_{1}^{- 1} [B (1)])$ . Then $ω - E = (C (1) - A (1)) \cup (G_{1}^{- 1} [D (1) - B (1)])$ , and therefore has asymptotic density zero, so that E has density one. At the same time, $ω - F [E] = (D (1) - B (1)) \cup G_{1} [C (1) - A (1)])$ has asymptotic density zero, so that $F [E]$ has asymptotic density one and thus E has density one. Let $x, y \in E$ . It follows from the construction of Theorem 3.9 that for any $x, y \in E$ , we have both $\begin{matrix} x R_{A} y \Leftrightarrow x R_{C} y, \end{matrix}$ and $\begin{matrix} x R_{B} y \Leftrightarrow x R_{D} y . \end{matrix}$

It remains to check that F is an isomorphism on the set E. Let $x, y \in E$ . There are three cases, without loss of generality. First note that if $x \in (A (1) \cap G_{1}^{- 1} [B (1)]$ , then $x \in C (1)$ , since $A (1) \subseteq C (1)$ , so that $F (x) = G_{1} (x)$ and $G_{1} (x) \in B (1)$ , and therefore $F (x) \in B (1)$ .

Case 1: $x, y \in C (2)$ . Then $F (x) = G_{2} (x)$ and $F (y) = G_{2} (y)$ and we have $\begin{matrix} x R_{A} y \Leftrightarrow x R_{C} y \Leftrightarrow G_{2} (x) R_{D} G_{2} (y) \Leftrightarrow G_{2} (x) R_{B} G_{2} (y), \end{matrix}$ so that $x R_{A} y \Leftrightarrow F (x) R_{B} F (y)$ .

Case 2: $x \in A (1) \cap G_{1}^{- 1} [B (1)]$ and $y \in C (2)$ . Then $y \in A (2)$ , and therefore $\neg R_{A} (x, y)$ . Now, by the remark above, $F (x) \in B (1)$ , whereas $F (y) = G_{2} (y) \in D (2) \subseteq B (2)$ and therefore $F (y) \in B (2)$ . Hence we have $\neg F (x) R_{B} F (y)$ .

Case 3: $x \neq y$ and both are in $A (1) \cap G_{1}^{- 1} [B (1)]$ . Then, since both are in $A (1)$ , we have $\neg x R_{A} y$ . By the remark above, $F (x), F (y) \in B (1)$ as well and therefore $\neg F (x) R_{B} F (y)$ .

Thus F acts as an isomorphism on the set E of asymptotic density one. This completes the proof that $A$ and $B$ are weakly coarsely computably isomorphic. □

It is interesting to note in the previous proof that the role of θ is played exactly by F. The only thing preventing this from being a computable isomorphism is that F sometimes fails to respect the structure.

The previous result also extends to computable $(1, k)$ -equivalence structures – that is, to structures with infinitely many classes of size one and infinitely many of size k, for any single finite $k > 2$ , but no classes of any other size. This suggests the following conjecture. Conjecture 3.13.
Let ${k_{1}, \dots, k_{n}}$ be distinct positive integers and let $q_{1}, \dots, q_{n}$ be positive reals such that $q_{1} + \dots + q_{n} = 1$ . Let $A$ and $B$ be computable equivalence structures such that $A (k_{i})$ and $B (k_{i})$ have asymptotic density $q_{i}$ for each i. Then $A$ and $B$ are weakly coarsely computably isomorphic.

4. Conclusion

Having laid out in [1] and the present paper the fundamental definitions for densely computable structure theory, we believe the time is now ripe for investigation of these concepts in a broader context. There are, of course, several remaining open questions on even these basic notions, some of which we have explicitly identified in this paper. We might even hope that, in the long run, it will be clear which of the various notions we have defined (e.g., generically computably isomorphic, weakly generically computably isomorphic, or either of those in a density preserving variant) will be most productive.

However, it seems to the present authors at this time that the greatest gains moving forward from this point will be in two directions. First, the approach of dense computable structure theory should be applied to structures of greater independent interest. This will be the real testing ground for which notions are most useful. Second, general semantic conditions should be found that predict the behavior of examples, rather than simply catalog it.

Footnotes

Acknowledgements

This research was partially supported by the National Science Foundation SEALS grant DMS-1362273. The work was done partially while the latter two authors were visiting the Institute for Mathematical Sciences, National University of Singapore, in 2017. The visits were supported by the Institute. This material is partially based upon work supported by the National Science Foundation under grant DMS-1928930 while all three authors participated in a program hosted by the Mathematical Sciences Research Institute in Berkeley, California during the Fall 2020 semester and again in Summer 2022. The third author was partially supported by the Simons Foundation grant 853762 and Focused Research Group grant from the National Science Foundation DMS-2152095. The authors are also grateful to the anonymous referee for a careful reading which greatly improved the paper.

References

Calvert,

Cenzer and

Harizanov, Densely computable structures, Journal of Logic and Computation 32 (2022), 581–607. doi:10.1093/logcom/exab057.

Calvert,

Cenzer,

Harizanov and

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

Cenzer,

Harizanov and

J.B.

Remmel,

Σ_{1}^{0}

and

Π_{1}^{0}

structures, Annals of Pure and Applied Logic 162 (2011), 490–503. doi:10.1016/j.apal.2011.01.002.

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.

Cenzer,

LaForte and

Remmel, Equivalence structures and isomorphisms in the difference hierarchy, Journal of Symbolic Logic 74 (2009), 535–556. doi:10.2178/jsl/1243948326.

Downey,

Jockusch,

T.H.

McNicholl and

Schupp, Asymptotic density and the Ershov hierarchy, Mathematical Logic Quarterly 61 (2015), 189–195. doi:10.1002/malq.201300081.

R.G.

Downey,

C.G.

Jockusch and

P.E.

Schupp, Asymptotic density and computably enumerable sets, Journal of Mathematical Logic 14 (2013), 1350005, 43 pp.

C.G.

Jockusch and

P.E.

Schupp, Generic computability, Turing degrees and asymptotic density, Journal of the London Mathematical Society 85 (2012), 472–490. doi:10.1112/jlms/jdr051.

C.G.

Jockusch and

P.E.

Schupp, Asymptotic density and the theory of computability: A partial survey, in: Computability and Complexity , Lecture Notes in Computer Science, Vol. 10010, Springer, 2017, pp. 501–520. doi:10.1007/978-3-319-50062-1_30.

10.

Kapovich,

Myasnikov,

Schupp and

Shpilrain, Generic-case complexity, decision problems in group theory, and random walks, Journal of Algebra 264 (2003), 665–694. doi:10.1016/S0021-8693(03)00167-4.

11.

R.I.

Soare, Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets , Springer-Verlag, Berlin, 1987.

Generically and coarsely computable isomorphisms

Abstract

Keywords

1. Introduction and previous work on densely computable structures

Definition 1.9. For an equivalence structure A = ( A , E ) and n ⩽ ω , let A ( n ) = { a : | [ a ] E | = n } . For brevity, we sometimes refer to elements of A ( n ) as being of type n. Theorem 1.10 ([1]).

Theorem 1.11 (Proved as Theorem 2.13).

Theorem 1.12 (Proved as Theorem 3.6).

Theorem 1.13 (Proved as Theorem 3.12).

2. Generically computable isomorphisms

Footnotes

Acknowledgements

References

Definition 1.9.
For an equivalence structure $A = (A, E)$ and $n ⩽ ω$ , let $A (n) = {a : | {[a]}_{E} | = n}$ . For brevity, we sometimes refer to elements of $A (n)$ as being of type n. Theorem 1.10 ([1]).