Let $f$ be a computable and injective function. Is $f^{-1}$ computable and injective?

122 Views Asked by At

So I just started learning about computability, undecidability and Turing machines. And I wonder if:

Given a computable and injective function $f$, is $f^{-1}$ also computable and injective?

I don't really know where to start to prove this, any hint or explanation would be appreciated.

1

There are 1 best solutions below

0
On

This question seems somewhat under-specified, but I think the answer is no.

  1. Consider $λ(x : ℕ). 2\cdot x$. The pre-image of even naturals are distinct, but the pre-image of all odd naturals is empty, so $f^{-1}$ is not injective.

  2. Consider the embedding from the naturals to the reals $f : ℕ → ℝ$. The pre-image of $r$ is $f^{-1}(r) = \{ n \in ℕ\ |\ f(n) = r \}$, but equality of reals is not computable (not even for computable reals).