Possible typos in the proof of Recursion Theorem

Solution 1:

Ad 1. Indeed, $n\in P$, not $n\in A$, hence $f(n)$ would not even make sense. But the correct formula should be $$ g(s(n))=f(g(n)).$$It is only after finding this nice $g$ that we can set $a_n=g(n)$ an have our recursively defined sequence.

Ad 2. Yes. Again, $\in P$ would not even make sense. If you follow the argument, you will notice that $\in g$ is used and shown, so at least the typo is no show-stopper for the proof.

Ad 3 and 4. No and then Yes. That step of the argument should read

Then $(s(m),f(b))\in g$. Thus if $(s(m),f(b))\notin g'$ then $(s(m),f(b))=(s(n),a')$.

There seem to be more typos, e.g., there is a superfluous $S$ in what should read

Since $(0,\bar a)\in R$ for all $R\in S$, $(0,\bar a)\in g$.

Solution 2:

3 is no type and 4 should read: "Thus if $(s(m),b)\notin g'$.."

The author is indeed proving that $g'\in S$. This by induction.

From $g'=g-\left\{ \left(s\left(n\right),a'\right)\right\} $ and $\left(0,\overline{a}\right)\in g$ it follows that $\left(0,\overline{a}\right)\in g'$.

Then it remains to prove that $\left(m,b\right)\in g'\implies\left(s\left(m\right),f\left(b\right)\right)\in g'$.

Suppose that this is not true for some $m\in P$ so that $\left(m,b\right)\in g'\wedge\left(s\left(m\right),f\left(b\right)\right)\notin g'$.

This route is taken by the author but unfortunately a typo was made ($g$ instead of $g'$).

It will be shown now that this assumption leads to contradiction.

From $\left(m,b\right)\in g'$ it follows that $\left(m,b\right)\in g$ so that $\left(s\left(m\right),f\left(b\right)\right)\in g$.

Then from $\left(s\left(m\right),f\left(b\right)\right)\notin g'$ it follows that $\left(s\left(m\right),f\left(b\right)\right)=\left(s\left(n\right),a'\right)$ and consequently $m=n$ and $f\left(b\right)=a'$.

However it was assumed that $n\in U$ and that for a unique $a\in A$ we had $\left(n,a\right)\in g$.

So $\left(n,b\right)=\left(m,b\right)\in g$ tells us that $b=a$.

Then $a'=f\left(b\right)=f\left(a\right)$ and a contradiction is found.

Proved is now that $g'\in S$.

[This leads to a contradiction again, which allows the conclusion that $n\in U\implies s(n)\in U$.]