# nLab Kleene's second algebra

Kleene’s second algebra is a partial combinatory algebra based on Baire space.

Let $ℕ$ be the set of natural numbers equipped with the discrete topology, so that the function space ${ℕ}^{ℕ}$ is a countable product of copies of $ℕ$. By means of continued fractions?, this space is homeomorphic to the Baire space $B$ of irrational numbers between $0$ and $1$.

To define Kleene’s second algebra, we need several ingredients:

1. There is a function $p:B\to 1+ℕ$ which takes the constant function at $0$ to $*\in 1$, and any other function $\alpha :ℕ\to ℕ$ to the predecessor of the first non-zero $\alpha \left(k\right)$.

2. Each irrational number $\beta \in B$ releases a stream of rational approximants ${q}_{1}\left(\beta \right),{q}_{2}\left(\beta \right),\dots$ by successive truncations of the continued fraction of $\beta$. By coding rational numbers by natural numbers, we get a corresponding stream of natural numbers $\left({\beta }_{1},{\beta }_{2},\dots \right)\in {ℕ}^{ℕ}$. The map

$\varphi :B\to B$\phi \colon B \to B

that sends $\beta$ to $\left({\beta }_{1},{\beta }_{2},\dots \right)$ is continuous.

3. $B$ is the terminal coalgebra of the endofunctor $-×ℕ$ on $\mathrm{Top}$, so there is an isomorphism $\xi :B\to B×ℕ$ whose inverse is denoted $\mathrm{prefix}$.

4. Composition of functions $ℕ\to ℕ$ defines a map $\mathrm{comp}:B×B\to B$.

Now consider the composite

$B×B×ℕ\stackrel{{1}_{B}×\mathrm{prefix}}{\to }B×B\stackrel{{1}_{B}×\varphi }{\to }B×B\stackrel{\mathrm{comp}}{\to }B\stackrel{p}{\to }1+ℕ$B \times B \times \mathbb{N} \stackrel{1_B \times prefix}{\to} B \times B \stackrel{1_B \times \phi}{\to} B \times B \stackrel{comp}{\to} B \stackrel{p}{\to} 1 + \mathbb{N}

and curry this to a map $\psi :B×B\to \left(1+ℕ{\right)}^{ℕ}$. Let $i:ℕ\to 1+ℕ$ be the inclusion map.

Kleene’s second algebra is the applicative structure or partial binary operation on $B$ defined by the pullback

$\begin{array}{ccc}D& \to & {ℕ}^{ℕ}\\ ↓& & {↓}^{{i}^{ℕ}}\\ B×B& \underset{\psi }{\to }& \left(1+ℕ{\right)}^{ℕ}\end{array}$\array{ D & \to & \mathbb{N}^\mathbb{N} \\ \downarrow & & \downarrow^\mathrlap{i^\mathbb{N}} \\ B \times B & \underset{\psi}{\to} & (1 + \mathbb{N})^\mathbb{N} }
Created on September 8, 2012 02:16:18 by Todd Trimble (67.81.93.25)