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.

  • $\begingroup$ What do you mean by $f^{-1}$? What if $f$ is not surjective? $\endgroup$ – Yuval Filmus Dec 12 '20 at 19:27
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Dec 12 '20 at 19:28
  • $\begingroup$ 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. $\endgroup$ – cs_learner Dec 13 '20 at 12:55
  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Dec 13 '20 at 12:56
  • $\begingroup$ 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^{*}$ $\endgroup$ – cs_learner Dec 13 '20 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.