nLab clone

Clones

Clones

Idea

An abstract clone is a structure that describes a single-sorted algebraic theory in a presentation-invariant way.

An abstract clone is equivalent to a cartesian operad, that is, a cartesian multicategory with one object. However, clones are presented differently, and quite economically, with projections rather than with symmetries, contraction and weakening.

Abstract clones are equivalent to Lawvere theories, and also to finitary monads. These are all different ways of giving presentation-invariant descriptions of single-sorted algebraic theories.

Definition

A set of algebraic operations on a fixed set SS is a concrete clone on SS if it contains all (component) projections S nSS^{n}\to S and is closed under composition (“superposition”).

An abstract clone consists of an abstract set of “nn-ary operations” for every nn together with projection and composition operations. This is the notion that’s equivalent to a cartesian operad or a Lawvere theory.

More precisely, the usual presentation of abstract clone comprises

  • a set T(n)T(n) for each natural number nn;

  • functions η n:nT(n)\eta_n : n \to T(n);

  • functions c m,n:T(m)×T(n) mT(n)c_{m,n} : T(m) \times T(n)^m\to T(n)

such that

  • η(i)j.t=t\eta(i) \rhd j. t=t;

  • ti.η(i)=tt \rhd i.\eta(i) =t;

  • ti.(u(i)j.v(j))=(ti.u(i))j.v(j)t \rhd i.(u(i) \rhd j.v(j)) = (t \rhd i.u(i)) \rhd j. v(j)

where we omit subscripts and write (ti.u(i))(t \rhd i.u(i)) for c(t,(u i) i)c(t,(u_i)_i).

This resembles the Kleisli triple presentation of a monad, except that nn is a natural number rather than an arbitrary set; in this sense it is the Kleisli triple form of a relative monad for the embedding FinSetSet\mathbf{FinSet}\to\mathbf{Set}.

Examples

Concrete clones as abstract clones

Suppose a concrete clone is given on a set SS, i.e. a set of operations S nSS^n\to S of different arities, closed under composition and containing all the projections. We regard this as an abstract clone by putting T(n)T(n) as the set of admitted operations S nSS^n\to S. The functions η n\eta_n pick out the projections, and c m,nc_{m,n} is multi-ary function composition.

Abstract clones from algebraic signatures

An algebraic signature comprises, for each number nn, a set Σ n\Sigma_n of formal nn-ary operations. For example, the theory of groups has Σ 0={1}\Sigma_0=\{1\}; Σ 1={() 1}\Sigma_1=\{(-)^{-1}\}; Σ 2={}\Sigma_2=\{\cdot\}.

We then build for all nn the terms in nn variables, written x 1x nx ix_1\dots x_n\vdash x_i, by the following inductive definition:

  • x 1x nx ix_1\dots x_n\vdash x_i is a term if 1in1\leq i\leq n;

  • if nt 1nt mn\vdash t_1\ \ \dots\ \ n\vdash t_m are terms and σΣ m\sigma\in \Sigma_m then nσ(t 1,,t m)n\vdash \sigma(t_1,\dots, t_m) is a term. Here we write n=(x 1x n)n =(x_1\dots x_n).

Now we form an abstract clone by putting T Σ(n)={t|(nt is a term)}T_\Sigma(n)=\{t\ \ |\ \ (n\vdash t\ \ \text{ is a term})\}. The functions η n\eta_n picks out the variables, and the function c m,nc_{m,n} amount to substitutions of terms for variables, which produces well-formed terms.

The inhabitants of T ΣT_\Sigma are sometimes called “derived operations”, since although they are not in the signature they have an interpretation in any model.

Abstract clones from presentations of algebraic theories

An algebraic theory over a signature is given by a collection of axioms of the form Γt=u\Gamma\vdash t=u, where Γt\Gamma \vdash t and Γu\Gamma \vdash u. We then form equivalence relations n\sim_n of terms by closing under substitution instances, congruence, and reflexivity, symmetry and transitivity. These are the equations that are true in all models of the theory.

We can now form an abstract clone for the theory, derived from the abstract clone for the signature. Put T(n)=T Σ(n)/ nT(n)=T_\Sigma(n)/_{\sim_n}. The η\eta and cc respect equivalence relations because we closed under substitution instances and congruence.

For example, starting from the theory of groups, T(n)T(n) will be the free group on nn generators.

Algebraic theories from abstract clones

Conversely, any abstract clone can be regarded as a presentation of an algebraic theory. The signature has Σ n=T(n)\Sigma_n=T(n), and we include the axioms

  • η n(i)=x i\eta_n(i) = x_i

  • s(t 1t n)=(si.t(i))s(t_1\dots t_n) = (s \rhd i. t(i)).

An abstract clone is a presentation of a “saturated” algebraic theory: all derived operations are equivalent to basic operations that are already in the signature.

Lawvere theories and abstract clones

If TT is an abstract clone, we can form a category whose objects are natural numbers and where a morphism mnm\to n is a tuple T(m) nT(m)^n. The identity morphisms are η n\eta_n. Composition is (gf)(i)=(g(i)j.f(j))(g\circ f)(i)=(g(i)\rhd j.f(j)). This category is a Lawvere theory.

(This is the opposite category of the Kleisli category of TT regarded as a relative monad.)

Conversely, if LL is a Lawvere theory then we can build a clone T(n)=L(n,1)T(n)=L(n,1). This gives an equivalence between abstract clones and Lawvere theories.

Algebras of abstract clones and connection with finitary monads

We can define an algebra of an abstract clone TT to be a set XX together with nn-ary function t:X nXt \rhd : X^n\to X for each tT(n)t\in T(n), such that

  • η ii.x(i)=x(i)\eta_i \rhd i.x(i)= x(i);

  • (ti.u(i))j.x(j)=ti.(u(i)j.x(j))(t\rhd i.u(i))\rhd j.x(j)= t\rhd i.(u(i)\rhd j.x(j)).

Here we are writing \rhd for both the clone composition and the algebra structure, and again writing ti.x(i)t \rhd i.x(i) for t(x i) it\rhd(x_i)_i.

For example, an algebra for the abstract clone of groups is a group.

Now the category of TT-algebras has a forgetful functor

TAlgSet T\mathbf{-Alg} \to \mathbf{Set}

One can show that this functor is monadic by showing it preserves limits, satisfies the solution set condition, reflects isomorphisms, and has reflexive coequalizers. Thus every abstract clone gives rise to a monad.

Another way to define this monad is to note that TT can be regarded as a functor FinSetSet\mathbf{FinSet}\to \mathbf{Set}, with T(f):T(m)T(n)T(f):T(m)\to T(n) given by T(f)(t)=(ti.η(f(i)))T(f)(t)=(t\rhd i.\eta(f(i))). Then we extend this to a functor M:SetSetM:\mathbf{Set}\to\mathbf{Set} by a coend or by Kan extension:

M(X)= nT(n)×X n=(LanT)(X) M(X) = \int^n T(n)\times X^n = (\mathrm{Lan}\,T)(X)

In other words, an inhabitant of M(X)M(X) is a derived operation tT(n)t\in T(n) formally applied to an nn-tuple in X nX^n, modulo change of variables. This functor MM can be given the structure of a monad on Set\mathbf{Set}, and its Eilenberg-Moore algebras are the TT-algebras.

Conversely, suppose that MM is a monad on the category of sets. We can define an abstract clone by regarding a natural number nn as a finite set and putting T(n)=M(n)T(n)=M(n). Then η\eta is the unit of the monad and cc is the Kleisli composition (called “monadic bind”).

This gives an equivalence between finitary monads and abstract clones. They are also the monads with arities in FinSet\mathbf{FinSet}.

Monadicity of the category of abstract clones

The definition of abstract clones given here is itself a presentation of algebraic structure. Indeed we can consider an obvious notion of homomorphism of clones, and then the forgetful functor

AbstractClones[FinSet,Set] \mathbf{AbstractClones} \to [\mathbf{FinSet},\mathbf{Set}]

is monadic.

In fact this adjunction is enriched in [FinSet,Set][\mathbf{FinSet},\mathbf{Set}]. Moreover, we can consider a more general notion of abstract clone enriched in a locally presentable category, where the arities nn are replaced by finitely presentable objects. Then the plain abstract clones themselves are algebras for an abstract clone enriched in [FinSet,Set][\mathbf{FinSet},\mathbf{Set}]. One way to present this formally is in terms of the substitution algebras of Fiore, Plotkin and Turi.

Another view of this adjunction starts from viewing [FinSet,Set][\mathbf{FinSet},\mathbf{Set}] as a monoidal category. To get this, we can understand functors FinSetSet\mathbf{FinSet}\to \mathbf{Set} as filtered colimit preserving endofunctors SetSet\mathbf{Set}\to\mathbf{Set}, and then composition forms a monoidal structure on a category of endofunctors. In detail, the unit is FinSet(1,)\mathbf{FinSet}(1,-) and tensor product is

(FG)(n)= mF(m)×G(n) m=((LanF)G)(n)(F \otimes G) (n) = \int^m F(m) \times G(n)^m = ((\mathrm{Lan}\,F)\circ G)(n)

Then the category of abstract clones is (equivalent to) the category of monoids for this monoidal structure. Since a finitary monad is a filtered-colimit-preserving “monoid in the category of endofunctors”, this also gives an abstract view of the connection between abstract clones and finitary monads on Set\mathbf{Set}.

References

  • Ágnes Szendrei, Clones in universal algebra, Séminaire de mathématiques supérieures 99, Les presses de l’université de Montreal, 1986. — 166 p.

A rather general framework is discussed in

  • Zhaohua Luo, Clone theory, its syntax and semantics, applications to universal algebra, lambda calculus and algebraic logic, arxiv/0810.3162
  • Dietlinde Lau, Function algebras on finite sets: Basic course on many-valued logic and clone theory, Springer Monographs in Mathematics

A common generalization of a clone and of an operad is proposed, using a new notion of a verbal category, in

  • S. Tronin, Abstract clones and operads, Siberian Mathematical Journal 43, No.4, 746–755, 2002 link

Another unification of clones and operads is via the formalism in

  • Pierre-Louis Curien, Operads, clones, and distributive laws, arxiv/1205.3050

See also the thesis

  • Miles Gould, Coherence for operadic theories, Glasgow 2009 pdf

Algebraic theories are treated as abstract clones in the enriched setting (but abstractly), and monadicity is dealt with, in

Substitution algebras as a theory over [FinSet,Set][\mathbf{FinSet},\mathbf{Set}] are presented in:

One description of enriched abstract clones is in Section 5 of

Last revised on July 29, 2022 at 19:33:45. See the history of this page for a list of all contributions to it.