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

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.

• What do you mean by $f^{-1}$? What if $f$ is not surjective? Dec 12, 2020 at 19:27
• If $f$ is surjective, then $f^{-1}$ is automatically a bijection, and it is computable: given $y$, just try all $x$ until you find one such that $f(x) = y$. Dec 12, 2020 at 19:28
• Sorry for the confusion. By $f^{-1}$ I mean the inverse function of $f$. I have a question on this: if a function $f$ is not surjective implies not having an inverse? Thanks for the surjective case. Dec 13, 2020 at 12:55
• That's really a question to you. What do you mean by $f^{-1}$ in this context? How is $f^{-1}$ defined? Can you explain what $f^{-1}$ is without using the word inverse? Dec 13, 2020 at 12:56
• Oh my bad. Let $A, B$ be languages over an alphabet $\Sigma$, then $f: A \subseteq \Sigma^{*} \mapsto B \subseteq \Sigma^{*}$ then, I guess, the inverse function would be defined as: $f^{-1}: B \subseteq \Sigma^{*} \mapsto A \subseteq \Sigma^{*}$ Dec 13, 2020 at 13:07