Combinatory algebras

A combinatory algebra consists of

1. a set D
2. an binary operation, \cdot : D \times D \to D
3. distinguished elements \mathbf{k}, \mathbf{s} \in D satisfying

\mathbf{k} \cdot x \cdot y = x

\mathbf{s} \cdot f \cdot g \cdot x = (f \cdot x) \cdot (g \cdot x)

for all x, f, g \in D.

The first two requirements - a set with a binary operation - require that (D, \cdot) forms an applicative structure. In fact, a combinatory algebra is an applicative structure with two distinguished constants which satisfy certain equations.

As models of combinatory logic

Combinatory algebras are the simplest notion of model of combinatory logic, aka the SK calculus.

As combinatory logic does not contain any form of binding, it can be seen as a first-order algebraic theory (much like the theory of groups). Hence, a combinatory algebra is the simplest structure that contains algebraic operations that model its primitives (in particular, a binary operation that interprets application) and its constants (in particular, two constants that interpret the combinators \textbf{S} and \textbf{K}).

As algebras

Considered as algebraic structures, combinatory algebras are an algebraist's nightmare.

In particular, Barendregt proves that

Theorem. A combinatory algebra is

• never associative
• never commutative
• never finite (unless trivial)
• never recursive

For a proof, see §5.1 of Barendregt 1984.

See also

• Combinatory Logic

References

• Applicative structures and combinatory algebras are defined in §5.1 of

@book{barendregt_1984,
	address = {Amsterdam},
	title = {Lambda {Calculus}: {Its} {Syntax} and {Semantics}},
	isbn = {978-0-444-87508-2},
	publisher = {North-Holland},
	author = {Barendregt, Henk},
	year = {1984}
}

Is it known if they predate Barendregt?