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.
For a formalization of Turing machines you could look at
The book
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 smn and utm 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 smn and utm 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 smn 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 smn 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 utm 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 utm 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 smn theorem twice. By the smn 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 smn theorem is total. By the smn 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. 


You may be interested in the following demonstration how natural numbers can be implemented within pca's: (see pages 1920) http://www.mathematik.tudarmstadt.de/~streicher/REAL/REAL.pdf 

