# Possible typos in the proof of Recursion Theorem

Below is the proof I took from textbook A Course in Mathematical Analysis by Proof D. J. H. Garling.

I think there are some typos, which I highlighted in the attached picture.

1. $g(s(n))= f(n)$

Since the theorem states $a_{s(n)}=f(a_{n})$, I think the right version should be: $g(s(n))=f(g(n))$, not $g(s(n))= f(n)$.

2.$(n,a)\in P$ and $(n,a')\in P$

I think the right version should be: $(n,a)\in g$ and $(n,a')\in g$

3.$(s(m),f(b))\in g$

Since the author is trying to prove $g'\in S$, I think the right version should be: $(s(m),f(b))\in g'$, not $(s(m),f(b))\in g$.

4.$(s(m),f(b))\notin g$

As in 3., I think the right version should be: $(s(m),f(b))\notin g'$, not $(s(m),f(b))\notin g$.

• For (1) don't you want $g(s(n))=f(g(n))$? Jan 20, 2018 at 10:28
• Yes, we use mapping $g$, not $a$. I agree with you, it should be: $g(s(n))=f(g(n))$ ^^ Jan 20, 2018 at 10:44

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$.

• I think the author is to prove $g'\in S$. As a result, he assumes $(m,b)\in g'$, then he proves $(s(m),f(b))\in g'$ too. This is why i think it should be "Then $(s(m),f(b))\in g'$". And to prove $(s(m),f(b))\in g'$, he assumes the contrary, i.e $(s(m),f(b))\notin g'$. If "Then $(s(m),f(b))∈g$" is not a typo, I don't know what is the role of "Then $(s(m),f(b))∈g$"? Jan 20, 2018 at 11:03
• Hi @AsafKaragila, can you have a check on my above reasoning? Jan 21, 2018 at 1:53

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'$).

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$.]

• I'm now clear, many thanks @drhab! Jan 21, 2018 at 14:47
• You are welcome. Jan 21, 2018 at 14:47