"Partial-computably isomorphic" sets 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.
 A: 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$.
