Containers for number-classes

June 9th, 2005 by Hank

The following is an example of an operation on (non-dependent) containers that may be of interest to those (me and Dr Altenkirch) of us with an interest in constructive versions of the higher `number classes’.

What’s a number class? Well, the notion and terminology comes from Cantor. Traditionally, the natural numbers $Nat = (\mu X)X + 1$ form the first number class, the countable Brouwer-ordinals
$BO = (\mu X)X + 1 + X^{Nat}$ form the second, and you can push on further into the so-called `finite’ number classes in the obvious way, by chucking in a $+ X^{NC_n}$ to the functor whose $\mu$ gave you the previous number class NC_n. (You can think of these sets as `aleph numbers’ \aleph_0, \aleph_1, \ldots
.)

Computable versions of these blighters were defined by Church and Kleene in 1937-1938, and by Markwald and Spector in 1954-1955. In fact they extended the series into the transfinite: at `\omega‘ one takes the union of the finite number classes, and then presses on as in the step from $\aleph_n$ to $\aleph_{n+1}$. In type theory, the theory of the finite number classes is quite interesting (there are some well-cool `collapsing functions’ $\aleph_{n+1} \to \aleph_n$)), but somewhat hindered by being full of `dot dot dots’. Moreover, as far as I know, there is no decent development of transfinite number-classes in type-theory. (One wants in the first place to get up to the first inaccessible ordinal, this being, for those of you who know what `regular’ means, a regular
ordinal closed under the step to the next regular. )

Anyway. The best way to approach the finite number classes is via the endofunctors of which they are the initial algebras. And the most natural way to do it is as follows.
\begin{displaymath}      \begin{array}[t]{l}      F_0(X)  =  X \\      F_{n+1}(X) = F_n(X) + X^{\mu(F_{n})}  \end{array} \end{displaymath}
The initial algebras of these chaps are, successively,

\[ \begin{array}[t]{lclclcl}  0 &=& (\mu F_0) &=& (\mu X)X \\ Nat &=& (\mu F_1) &=& (\mu X)X + X^0 &=& (\mu X) X + 1\\ BO &=& (\mu F_2) &=& (\mu X)X + 1 + X^{Nat}\\ \ldots& & \end{array}\]
(Now you can maybe see why I wrote $X + 1$ rather than $1 + X$.)
Funnily enough, the empty set comes out as the first `number-class’, the naturals as the second, etc., so we’re off-by-one from the conventional terminology, but who cares. The point is by working with the endo-functors rather than their initial algebras, we get a nice closed-form description of the step to the next number-class, without any `dot dot dots’ as in $\aleph_{n+1} = (\mu X)1 + X + X^{\aleph_0} + \ldots + X^{\aleph_n} $.

And of course, these functors are given by containers: $S_0 = 1, P_0(0) = 1$,
$S_{n+1} = S_{n} + 1, P_{n+1}(inL(s)) = P_{n}(s), P_{n+1}(inR(0)) = \mu(S_n \rhd P_n)$.
Moreover, it is obvious that there are natural transformations from $F_n$ to $F_{n+1}$ all the way up. Taking the colimit of this series (the formalisation requires a universe to `recurse into’), we get a functor $F_\omega$ whose $\mu$ is $\aleph_{\omega + 1}$, and whose value at 0 is \aleph_{\omega}.

In other words, the theory of (non-dependent) containers seems to provide quite a bit of the apparatus one needs to make a type-theoretic development of number-classes beyond the finite ones, whose absence (till now) constitutes a minor scandal in type-theory.

Some further thoughts along/beyond these lines can be found here, and here.

What are dependent containers (for)?

June 8th, 2005 by Hank