0

Suppose $f(x)$ is a total computable function. Use minimalization to show that there is a computable function $g(y)$ with $dom$ $g = im$ $f$ and $f(g(y))=y$ for all $y \in dom$ $g$

I know this then means that $f(g(y))=y$ for all $y \in im$ $f$ but I don't know where to go from here.

Jim
  • 1
  • @BrianM.Scott Haha it autocorrected me :P I meant minimalization but i've also heard it called minimisation – Jim Nov 07 '13 at 13:49
  • Minimization (US) or minimisation (UK) is the usual term. (But I really liked mineralization: autocorrection sometimes produces really funny results.) – Brian M. Scott Nov 07 '13 at 13:52

1 Answers1

1

$g(y)=\min\{x:f(x)=y\}$ (plus a few more characters because the site doesn't like minimalization of answers)

Andreas Blass
  • 71,833
  • I have no idea how you got to this answer, can you explain? – Jim Nov 07 '13 at 14:18
  • I'm assuming $g(y)$ is the minimum $x$ such that $f(x)=y$ but I don't get how – Jim Nov 07 '13 at 14:20
  • The question was not to prove something about some already given $g$, which might very well not have chosen the minimum $x$ for each $y$, but to show that there exists a computable $g$ satisfying the requirements in the question. So, of the (possibly many) $g$'s that satisfy $f(g(y))=y$ for all $y\in\text{Im}(f)$, I chose the simplest one. It has the advantage that minimization immediately proves that this $g$ is computable. – Andreas Blass Nov 07 '13 at 15:48