A singleton generator

THEOREM: Let X be any infinite set, and let g₁, g₂, ... countably many operations on X (i.e., functions from some finite power of X into X). Then there is a single binary operation "+" on X such that the clone generated by "+" contains each g_i; that is, every g_i can be obtained by nesting sufficiently many instances of +, e.g., g₁(x,y,z) could be z+((y+x)+x).

A pdf version is available.

The proof is easy, and perhaps quite old and well-known. (Does anybody know a reference? Please write me.)

The same theorem is true for finite sets, with a different proof. (Donald Webb, 1935)

Back to Martin Goldstern's Home page