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.


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

  • $\begingroup$ Would the integers in your construction represent indices in an enumeration of all partial recursive functions? $\endgroup$
    – Taolonia23
    Sep 10, 2021 at 13:48
  • $\begingroup$ @Taolonia23 No, they are just integers. $\endgroup$
    – Arno
    Sep 10, 2021 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.