For $A,B \subseteq \mathbb{N}$, define $A\sim B$ when there exist partial computable functions $f,g\colon \mathbb{N}\rightharpoonup \mathbb{N}$ such that $f$ is defined at least on all of $A$ and $g$ at least on all of $B$ and such that they restrict to inverse bijections $f|_A\colon A\to B$ and $g|_B\colon B\to A$. (Or more concisely but also more confusingly: “there exists a bicomputable bijection $A \to B$”.)

This definition comes from an incorrect attempt of mine to remember what "computably isomorphic" meant and what the Myhill isomorphism theorem says (and then getting all confused since $A\sim B$ does not even imply that $A$ and $B$ have the same Turing degree: indeed, $\mathbb{N} \sim K$ where $K$ is the halting problem). To remove any ambiguity, $A$ and $B$ are said to be "computably isomorphic" ($A\equiv B$) when there exists a total computable $h$ that is a bijection $\mathbb{N}\to \mathbb{N}$ and such that $h(A) = B$: I'm tempted to say that "computably isomorphic" is about being isomorphic as subsets of $\mathbb{N}$ rather than as sets of integers as the relation $\sim$ above.

But now I'd like to know more about the relation $A\sim B$ that I inadvertently defined, because it seems fairly natural and I couldn't find any reference to it anywhere (of course, it's hard to find something when one does not know a name for the thing):

  • Does it have a standard name? Has it appeared in the literature previously? Or is it completely trivial for some reason that escaped me?

  • What nontrivial things can be said about it? E.g., can its equivalence classes be, if not characterized, at least related to some more classical objects?

  • Is there some reason to think that it's not an interesting or "good" notion to define?

Easy facts: It is easy to see that $\mathbb{N} \sim A$ iff $A$ is computably enumerable. Also, we can bound $\sim$ by two fairly standard equivalence relations: on the one hand, $A \equiv B$ trivially implies $A\sim B$ (where $\equiv$ is defined above; the Myhill isomorphism theorem states essentially that $\equiv$ is equality of one-one degrees); and conversely, if $A\sim B$ then $\mathbf{a} \cup 0' = \mathbf{b} \cup 0'$ where $\mathbf{a},\mathbf{b}$ are the Turing degrees of $A,B$ (because using an oracles for $A$ and for $0'$ we can decide $y\in B$ by testing whether $g(y)$ is defined and belongs to $A$ and its image by $f$ is defined); so at least $\sim$ is neither insanely fine nor insanely coarse.

Addendum: If I didn't mess up too badly, $A \sim B$ is equivalent to saying that the objects of the effective topos defined by $A$ and $B$ (the source of the subobjects $A \hookrightarrow \mathcal{N}$ and $B \hookrightarrow \mathcal{N}$ of the n.n.o. $\mathcal{N}$ classified by the maps $\mathcal{N} \to \Omega_{\neg\neg} = \nabla(2)$ defined from the characteristic functions of $A$ and $B$) are isomorphic (equivalently: internally isomorphic). (If someone can confirm this, I'd appreciate it.) This should at least give some motivation for thinking that $\sim$ might be interesting or natural.

  • $\begingroup$ I have forgotten more recursion theory than I remember (perhaps more than I learned), so take the following with some skepticism. It seems using the total functions identify all the recursive sets with 0, while your notion identifies most or all r.e. sets with 0. If you are dealing with a larger hierarchy than 0', this notion might be of interest; I don't recall enough to say if e.g. 0' and 0" are different under your relation. If not, then I'd toss the notion and move on. Gerhard "Had Trouble With Recursive Predecessor" Paseman, 2016.01.16. $\endgroup$ Jan 16, 2016 at 22:48
  • $\begingroup$ The $\sim$-class of $\mathbb{N}$ is exactly the set of infinite computably enumerable sets (given an infinite c.e. set we can find a 1-to-1 enumeration of it, proving the equivalence; conversely, the function $f$ in the condition $\mathbb{N}\sim E$ shows that $E$ is c.e.). I should probably have mentioned this. So all infinite c.e. sets are identified but not, say, with the complements of c.e. sets or anything of degree $0''$. $\endgroup$
    – Gro-Tsen
    Jan 16, 2016 at 23:01
  • $\begingroup$ @bof No - every pair of sets satisfies that property (take $\hat{A}=\hat{B}=\mathbb{N}$). You need the computable partial maps to send $A$ to $B$ and $B$ to $A$, and invert each other when restricted to those sets. $\endgroup$ Jan 17, 2016 at 3:33

1 Answer 1


The equivalence relation $\sim$ is referred to as recursive equivalence, and the equivalence classes as recursive equivalence types.

I don't know much about them, other than McCarty showed in his PhD thesis Realizability and Recursive Mathematics, that in the realizability model $V(\mathcal{Kl})$ this notion corresponds to the $\neg \neg$ stable subsets of $\mathbb{N}$ up to cardinality, which is basically the same as the topos theoretical definition you gave.

McCarty attributes the notion to Dekker and Myhill, who apparently wrote a book on the topic titled Recursive Equivalence Types. An internet search turns up several papers referring to them (eg Myhill, Recursive equivalence types and combinatorial functions and Nerode, Additive relations among recursive equivalence types).

By the way, the usual definition is that $A \sim B$ iff there is a partial computable $f$ which is injective on its domain and such that $f(A) = B$. To show this is implied by the other definition: note that given $f$ and $g$ as in the question, we define $f'$ by restricting $f$ to only those $n$ such that $g(f(n))$ is defined and equal to $n$, and then $f'$ is injective on its domain and is still defined on $A$.

  • $\begingroup$ Great! Knowing the True Name of a concept unlocks a lot of power to search about it. Thank you also for the final comment, I had wondered about that among other things. $\endgroup$
    – Gro-Tsen
    Jan 18, 2016 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.