From: whopkins@alpha2.csd.uwm.edu (Mark William Hopkins)
Subject: Universal Embedding Theorem (was: single universal lambda combinator)
Date: 8 Oct 2000 01:30:08 -0500
Newsgroups: sci.math.research

In article <8rnuf1$ldg$1@nnrp1.deja.com> Urs Schreiber <Urs.Schreiber@uni-essen.de> writes:
>Sorry for the unnecessary question. The answer is (of course) found in
>Barendregt (p.162)

The obvious answer, since combinatory algebra is non-associative, is
the imposition of the axioms:

                     (XX)X = S, X(XX) = K.

or, equivalently, the axioms

		(( ((XX)X) x) y) z = (xz)(yz)
		( (X(XX)) x) y = x

So, chances are, this is also what Barendregt came up with.

This observation leads directly to the following theorem:

THEOREM: Universal Embedding Theorem
   Any finitely generated algebra, with a recursively enumerable set of
   identities, can be embedded in an algebra generated by a single element,
   and presented by a finite set of identities.

By "algebra", here, I mean a mathematical system given by a single binary
operation (denoted as a product operation) and no axioms.  As a corollary,
this applies to finitely generated (semigroups, monoids, groups) which
have r.e. sets of identities.

The algebra, in fact, given by the axioms above should be a universal
embedding algebra.

This result is similar to the Higman Embedding Theorem, which says a
similar thing for semigroups, and there should also be a similar theorem
for groups and one for monoids.