# computability – 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.