Freyd's hierarchy of combinator monoids
Rick Statman · 2002
The Freyd hierarchy of monoids is introduced. The Freyd hierarchy is a fragment of type-free combinatory algebra lambda -calculus that has some remarkable properties, some of which are presented. One result characterizes the combinators in the hierarchy in terms of some simple ideas from the theory of rewrite rules. The computational/expressive power of the fragment is studied. This includes not only the functions computable by the combinators but also the varieties definable by combinator equations. Certain extraordinary connections between the lowest level of the hierarchy, combinatorics, and topology are also included.>