My question is from Hartley Rogers' textbook (1967).
Here's how I'm thinking about this so far. I know given infinite recursive sets A, B with infinite complements by theorem II of the current chapter (5) that both A & ~A (complement of A) and B & ~B are recursively enumerable. By theorem III(b), we have that A and B can be enumerated in increasing order, where each enumeration is surjective and recursive. Not sure where to go from here . . .
So I describe informally a bijection $h:\mathbb{N} \mapsto \mathbb{N}$ so that $h(A)=B$. It is probably a good exercise to then write it formally:
You assigm $b_0$ to be the first element of $B$ and $c_0$ to be the first element of $B^c$, the complement of $B$.
$h(0)$ is equal to $b_0$ if $0 \in A$ and is equal to $c_0$ if $0 \in A^c$. Also in the first case you set $b_{1}$ to be the next element of $B$ (the first element of $B$ bigger than $b_0$) and $c_1=c_0$. In the second case you set $c_1$ to be the next element of $B^c$ (the first element of $B^c$ bigger than $c_0$) and $b_1=b_0$.
Then $h(n+1)$ is equal to $b_{n+1}$ if $n+1 \in A$ and is equal to $c_{n+1}$ if $n+1 \in A^c$. Also in the first case you set $b_{n+2}$ to be the next element of $B$ and $c_{n+2}=c_{n+1}$. In the second case you set $c_{n+2}$ to be the next element of $B^c$ and $b_{n+2}=b_{n+1}$.
This is a variation of the answer by Archimondain in which we fix the enumerations up front. Let $a_1, a_2, \ldots$ enumerate $A$, let $a'_1, a'_2,\ldots$ enumerate $A^c$, let $b_1, b_2, \ldots $ enumerate $B$, and let $b'_1, b'_2, \ldots$ enumerate $B^c$. Let $f(a_i) = b_i$ and $f(a'_i) = b'_i$. Then $f$ is computable (assuming we chose computable enumerations), total, a bijection, and $f(A) = B$.
To see $f$ is total computable, note that given $n$ we can enumerate $A$ and $A^c$ until we find an $i$ such that $n = a_i$ or $n =a'_i$. Then we enumerate $B$ and $B^c$ until we find $b_i$ and $b'_i$, and we know which one to return.
