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.

everypair 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$ – Noah Schweber Jan 17 '16 at 3:33