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.