# Recursive Bijections Between Countably Infinite Sets

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.

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