  Working with the simple types over a base type of natural numbers (including
product types), we consider the question of when a type $\sigma$ is encodable
as a definable retract of $\tau$: that is, when there are $\lambda$-terms
$e:\sigma\rightarrow\tau$ and $d:\tau\rightarrow\sigma$ with $d \circ e = id$.
In general, the answer to this question may vary according to both the choice
of $\lambda$-calculus and the notion of equality considered; however, we shall
show that the encodability relation $\preceq$ between types actually remains
stable across a large class of languages and equality relations, ranging from a
very basic language with infinitely many distinguishable constants $0,1,\ldots$
(but no arithmetic) considered modulo computational equality, up to the whole
of Plotkin's PCF considered modulo observational equivalence. We show that
$\sigma \preceq \tau \preceq \sigma$ iff $\sigma \cong \tau$ via trivial
isomorphisms, and that for any $\sigma,\tau$ we have either $\sigma \preceq
\tau$ or $\tau \preceq \sigma$. Furthermore, we show that the induced linear
order on isomorphism classes of types is actually a well-ordering of type
$\epsilon_0$, and indeed that there is a close syntactic correspondence between
simple types and Cantor normal forms for ordinals below $\epsilon_0$. This
means that the relation $\preceq$ is readily decidable, and that terms
witnessing a retraction $\sigma \lhd \tau$ are readily constructible when
$\sigma \preceq \tau$ holds.
