Recursive Bijections Between Countably Infinite Sets

Question

The textbook I am currently studying (Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi) uses the term 'recursive bijection'. In this context I believe that recursive refers to a total recursive function (i.e. a computable function which is defined for all arguments).

Consider two countably infinite sets $\mathcal{S}, \mathcal{T}$ and a bijection $F: \mathcal{S} \to \mathcal{T}.$

Question 1: Since $F$ must be defined for all arguments, does this mean that any computable bijection must be total recursive and not partial recursive?

Question 2: Are there bijections between two countably infinite sets that are not recursive?

The answer to the first question seems to me to be yes. However I am much more unsure about the second. However, the use of the term 'recursive bijection' seems to imply to me that there must be bijections that are not recursive.

Answer 1

A) This depends on how you've set things up. If, eg, you have $\mathcal{S}$, $\mathcal{T}$ as subsets of $\mathbb{N}$, then a computable (recursive) bijection $F : \mathcal{S} \to \mathcal{T}$ needs to be only defined on $\mathcal{S}$, not on all of $\mathbb{N}$.

B) A straight-forward example would be $G : \mathbb{N} \to \mathbb{N}$ where $G(2n) = 2n$ if $n \in H$, $G(2n+1) = 2n+1$ if $n \in H$, $G(2n) = 2n+1$ if $n \notin H$ and $G(2n+1) = 2n$ if $n \notin H$. Here $H$ denotes the Halting problem.

If you want an example where there is no computable bijection at all, consider $\mathbb{N}$ and $\mathbb{N} \setminus H$. It is a standard exercise to show that there cannot be any computable surjection $s : \mathbb{N} \to (\mathbb{N} \setminus H)$.