It is known that the set of natural numbers with the operation ab = {a}b, where {a} represents the index of a recursive function, forms a partial combinatory algebra (pca). All the references I have so far consulted mention the set of natural numbers as an example of a pca with no proof. If possible, I would appreciate if someone could refer me to such proof.



A Proof that the Natural Numbers Form a pca?
For a formalization of Turing machines you could look at



> 
> Andrea Asperti and Wilmer Ricciotti: [*Formalizing Turing Machines*](http://www.cs.unibo.it/~asperti/PAPERS/turing.pdf). Lecture Notes in Computer Science Volume 7456, 2012, pp 1-25.
> 
> 
> 


The book



> 
> Martin Davis. *Computability and Unsolvability.* Courier Dover Publications, 1982 (3rd reprint).
> 
> 
> 


contains an amazing amount of detail about Turing machines.


Given these references, let us take as granted the details of the numbering $\varphi$ of partial computable maps, the [s-m-n](http://en.wikipedia.org/wiki/Smn_theorem) and [u-t-m](http://en.wikipedia.org/wiki/Utm_theorem) theorems from computability theory, and one bit of knowledge: if we fix one argument of a partial computable map of two arguments we obtain a partial computable map again.


With s-m-n and u-t-m theorems in hand, it is not hard to show that Kleene's first algebra is a partial combinatory algebra. We just need to construct the $\mathsf{K}$ and $\mathsf{S}$ combinators.


To get the $\mathsf{K}$ combinator, consider the partial computable map
$$f(x, y) = x.$$
By the s-m-n theorem there exists $p$ such that $\varphi\_{s(p, x)}(y) \simeq f(x,y)$ for all $x, y \in \mathbb{N}$. Here $s$ is the total computable map appearing in the s-m-n theorem and $\simeq$ is Kleene equality "if one side is defined then so it the other and they are equal". Now the map $x \mapsto s(p, x)$ is total and computable, hence there is $\mathsf{K}$ such that $\varphi\_{\mathsf{K}}(x) = s(p, x)$ for all $x$. We now have (I write $a \cdot b$ for Kleene application, i.e., $a \cdot b = \lbrace a \rbrace b = \varphi\_a(b)$):
$$(\mathsf{K} \cdot x) \cdot y = \varphi\_{\mathsf{K}}(x) \cdot y = s(p,x) \cdot y = \varphi\_{s(p,x)}(y) = f(x,y) = x.$$


For the $\mathsf{S}$ combinator, let $u$ be the universal computable map from the u-t-m theorem. It has the property that, for all $t$ and $m$,
$$u(t, m) \simeq \varphi\_t(m).$$
In other words, $u(t,m) \simeq t \cdot m$ so the u-t-m theorem is just saying that Kleene application is computable.
Consider the map
$$g(x,y,z) = u(u(x, z), u(y,z)).$$
We have
$$g(x,y,z) \simeq u(x,z) \cdot u(y,z) \simeq (x \cdot z) \cdot (y \cdot z).$$
We just need a code for $g$, which we get by appying the s-m-n theorem twice.


By the s-m-n theorem there is $p$ such that $\varphi\_{s^{(2)}(p, x, y)}(z) \simeq g(x,y,z)$ for all $x,y,z$. Let $r$ be such that $\varphi\_r(x,y) = s^{(2)}(p, x, y)$ for all $x, y$. Note that $\varphi\_r$ is total because the map $s^{(2)}$ from the s-m-n theorem is total. By the s-m-n theorem there is $q$ such that $\varphi\_{s(q,x)}(y) = \varphi\_r(x,y)$ for all $x,y$. Let $\mathsf{S}$ be such that $\varphi\_\mathsf{S}(x) = s(q,x)$ for all $x$. Now finally compute
$$((\mathsf{S} \cdot x) \cdot y) \cdot z \simeq
(s(q,x) \cdot y) \cdot z \simeq
\varphi\_{s(q,x)}(y) \cdot z \simeq
\varphi\_r(x,y) \cdot z \simeq$$


$$
s^{(2)}(p,x,y) \cdot z \simeq
\varphi\_{s^{(2)}(p,x,y)}(z) \simeq
g(x,y,z) = (x \cdot z) \cdot (y \cdot z).$$
Also, since $\mathsf{S} \cdot x \cdot y = s^{(2)}(p,x,y)$ we see that $\mathsf{S} \cdot x \cdot y$ is defined for all $x, y$, as required.


