Given a recursive function, show there is a n such that Wn is recursive

51 Views Asked by At

Let $f$ be a recursive function. Show that there is an $n$ such that: $W_{n}$ is recursive; and $(\mu y)[ W_{y} = \overline{W_{n}} ] > f(n)$. Hint: Enumerate a finite set $W_{n}$ by first computing $f(n)$ and then defining $W_{n} = K \upharpoonright (f(n) + 1)$, where $A \upharpoonright x$ denotes the restriction of $A$ to elements $y<x$.

For the first one, I have an intuition that there are also infinitely many ones, because if there is one, by the padding lemma we can obtain the rest. The problem is that I can not find a formal argument for the existence. For the second one, I do not understand why do we need such enumeration.