A combinatory algebra consists of
for all .
The first two requirements - a set with a binary operation - require that forms an applicative structure. In fact, a combinatory algebra is an applicative structure with two distinguished constants which satisfy certain equations.
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 and ).
Considered as algebraic structures, combinatory algebras are an algebraist's nightmare.
In particular, Barendregt proves that
Theorem. A combinatory algebra is
For a proof, see §5.1 of [Barendregt 1984].
Barendregt, Henk. 1984. Lambda Calculus: Its Syntax and Semantics. Amsterdam: North-Holland. [link]
@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?