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.



"Partial-computably isomorphic" sets
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*](https://projecteuclid.org/euclid.bams/1183522848) and Nerode, [*Additive relations among recursive equivalence types*](http://link.springer.com/article/10.1007%2FBF01362769)).


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$.


