Zhaohua Luo Clones and Genoids (Basic Concepts) 12/1/2007 Genoids A genoid theory  is a category of two objects (A, G) such that G is the product of A and G, and G is dense.  A left algebra of (A, G)  is a functor from (A, G)  to the category Set of sets preserving the given product. A linear algebra of a monoid  (G, e) is a triple (A, x, +) where A is a  right act of G, x is an element of A and + is an element of G such that  for any a in A and u in G there is a unique element [a, u] in G with x[a, u] = a and +[a, u] = u.
 A genoid A = (A, G) consists of a monoid G and a linear algebra A of G.  The notions of genoid theory and genoid are equivalent. Let S be a nonempty set. An S-genoid is a pair (A, G) consisting of a  monoid G and an S-indexed set of linear algebras A =  {(As, xs, +s) | s in S} of G such that xs+t = xs  and +s+t = +t+s for any two distinct elements s, t of S. Let A = (A, G)  be an S-genoid. A left A-algebra D = (D, T, μ) consists of a left G-act T, an S-sorted set D = {Ds} and an S-indexed set of maps μ ={ μs:  As X T -> Ds} such that for any a in As, u in G, w  in T (i) (au)w = a(uw). (ii) For any (d, w) in Ds X T there is a unique element [d, w] in T such that xs[d, w] = d and +s[d, w] = w. A genoid A = (A, G) is called complete if for any infinite sequence a1, a2, ...of elements of A there is a unique element [a1, a2, ...] of G such that xn[a1, a2,  ...] = an for any n > 0,  where x1 = x,  xn+1 = xn+ inductively.  A genoid A = (A, G) is called standard  if it is generated by A as a 2-sorted algebra with universes A and G.  Similarly one defines a complete S-genoid for any set S. Let A = (A, G) be a genoid.  A left A-algebra D = (D, T, μ) is complete if for any infinite sequence d1, d2, ...of elements of D  there is a unique element [d1, d2, ...] of T such that xn[d1, d2,  ...] = dn  for any n > 0.  Similarly one defines a complete  left algebra for an S-genoid. An  algebraic genoid   (G, x, +) consists of a monoid (G, e),  two elements x, + in G such that xx = +x = x,  and (xG, x, +) is a linear algebra of G. Any algebraic  genoid determines a genoid  (xG, G). Let (G, x, +)  be an algebraic genoid. A left A-algebra is a left G-act T such that for any (w, z) in T X T there is a unique element [w, z] in T such that x[w, z] = xw and +[w, z] = z  (thus (xT, T) is a left algebra of genoid  (xG, G)).
Clones
 A clone  (in algebraic form) is a set A such that the set AN of maps from the set N of positive integers to A is a monoid and (ru)v = r(uv) for any maps r: N -> N and u, v: N -> A. Let A be a clone. A left A-algebra is a set D such that DN is a left act of AN and (ru)m = r(um) for any maps r: N -> N, u: N -> A and m: N -> D. A clone (in extension form) is a set A such that the set AN of infinite sequences of elements of A is a monoid with a unit [x1, x2, ...], A is a right act of AN and xi[a1, a2, ...]  = ai for any [a1, a2, ...]  in AN. A left A-algebra is a set D together wit a map A X DN -> D such that the induced map  AN X DN -> DN turns DN  into a left AN act. Any clone (in both forms) A determines a complete genoid (A, AN) with + = [x2, x3, ...],.  Any left A-algebra D determines a complete left algebra (D, DN) of the genoid (A, AN). A clone theory is a category of two objects (A, G) such that G is a countable power of A. A left algebra of (A, G) is a functor from (A, G) to Set preserving the countable power. The notions of clone theory, clone (in algebraic or extension form) and complete genoid are equivalent. Let S be a nonempty set. An S-clone is a category (A, G) consists of an object G and an S-indexed set A = {As} of objects such that G is the product of countable powers of all As.  A left algebra of (A, G)  is a functor from (A, G)  to Set preserving the product Let N be a full subcategory of a category X. A clone over N (in algebraic form) (resp. in extension form) is a pair (K, T) where K is a category and T is a function T: Ob K -> Ob X (resp. a functor T: K -> X) such that for any A, B, C, D in N (i). Ob N = Ob K. (ii). K(A, B) = X(A, TB).(iii). r(fg) = (rf)g (resp. f(Tg) = fg) for r in X(D, A), f in K(A, B) and g in K(B, C).If N is dense then these two forms of clones are equivalent. In particular, a clone over  N = X in both forms corresponds to a monad on X. Examples: Let X = Set be the category of sets.  1. A clone over a singleton is equivalent to a monoid. 2. A clone over a finite set is equivalent to a unitary Menger algebra. 3. A clone over a countable set is  equivalent to a clone in both forms defined above. 4. A clone over the subcategory {0, 1, 2, ...} of finite sets  is equivalent to a clone in the classical sense (or a Lawvere theory). 5. A clone over a one-object category is equivalent to a Kleisli algebra.
Genoids and Kleisli Algebras
 Suppose A = (A, G)  is a genoid. Let  δ: G -> G be the map sending u to [x, u+]. Then δ is an endomorphism of monoid G. Let - = [x, e], where e is the unit of G. Then (δ, +, -) is a monad on G (viewed as a one-object category). Thus G is a Kleisli algebra. If P is any right act of G denote by PA  the new right act  (P, *) of G defined by p*u = p(δu) = p[x, u+]. Let ev: PA X A-> P be the map defined by ev(p, a) = p[a, e].  Define  Λ: hom(T X A, P) -> hom(T, PA) given by (Λf)t = f(t+, x) and  Λ*: hom(T, PA) ->  hom(T X A, P)  given by (Λ*g)(t, a) = ev(g(t), a). It is easy to see that  Λ  is the inverse of Λ*. hence Λ is bijective. Thus (PA, ev) is the exponent in the the cartesian closed category ActG of right acts of G. Letting T = P = A  we obtain a bijection Λ: hom(A X A, A) -> hom(A, AA).  This is the starting point of lambda calculus. The endomorphism δ induces a functor  Δ : ActG  ->  ActG  sending each act P to PA, and each morphism f: P ->  Q  to f: PA ->  QA.  The actions of + and -  induces two natural transformations + : Id ->  Δ  and -: Δ2 ->  Δ. It is easy to see that  (Δ, +, -)is a monad on ActG .
Universal Algebra
 Let P be a right act of a genoid A. We say an element p of P has a rank 0 (or p is closed) if pu = p for any u in G.  We say p has a finite rank n > 0 if pu = pv for any u, v in G with xiu = xiv  for each 0 < i < n + 1. We say P is locally finitary if for any p in P has a finte rank. We say a genoid is locally finitary if it is so as a right act of itself. Theorem. The category of locally finitary clones is equivalent to the category of finitary varieties. The category of algebras in a finitary variety is equivalent to the category of left algebras of the corresponding clone (which is determined by the free algebra of countable rank of the variety). The class of genoids forms a variety of 2-sorted heterogeneous (finitary) algebras with universes A and G.  The class of algebraic (resp. standard) genoids forms a variety of (finitary) algebras with universe A. The class of clones forms a variety of (infinitary) algebras with universe A.
Lambda Calculus
 We say a genoid (A, G)  is reflexive if AA is a retract of A (as right acts of G).  We say (A , G) is extensive if AA is isomorphic to A. A lambda calculus is a genoid A together with two homomorphisms λ : AA -> A and AXA -> A of right acts of G. If (λ a)+x = a  we say A is a reflexive lambda calculus (or a λβ calculus). If furthermore  λ(a+x) = a  then we say A is an extensive lambda calculus (or a λβη calculus). Thus a genoid is reflexive (resp. extensive)  iff it is the underlying genoid of a reflexive (resp. extensive) lambda calculus. Let S be a nonempty set carrying a binary operation -> . An S-simply typed lambda calculus  is an S-genoid (A, G)   together with homomorphisms {λs: AtAs ->  As->t} and {As->t X As ->  At} such that for any a in At  and c  in As->t we have  (λsa)+sxs = a and  λs(c+sxs) = c.
First Order Logic
 A predicate algebra with terms in a genoid (A, G)  is a right act P of G with homomorphisms ∃: PA -> P, F: P0 -> P, and =>: P X P -> P.  We define derived operations on P: ~ p = p => F, T = ~F, p ∨ q = (~ p) => q, p Λ q = ~ (p => ~ q). A predicate algebra P is a quantifier algebra if(i)  A is a Boolean algebra with respect to (V, Λ, ~, F, T). (ii) ∃ (p ∨ q) = (∃ p) ∨ (∃ q) for any p,q, in P. (iii)  p < (∃p)+ for any p in P. Theorem. Suppose A is a locally finitary clone. Any left algebra D of A determines a locally finitary quantifier algebra P(DN), where P(DN) is the power set of DN. A locally finitary predicate algebra with terms in A  is a quantifier algebra iff it belongs to the variety generated by predicate algebras P(DN) for all left algebras D of A. It is straight forward to extend these results to an S-genoid (A, G) for any set S.
Binding Operations
 Suppose (A, G) is a genoid and P is a right act of G.  Let  [a1, a2, ..., an,, u] = [a1, [a2, ..., [an,, u]]] for any n > 0. Let - = [x, e]. Then +- = e. Any homomorphism ∃: PA -> P is called an abstract binding operation on P. (if P = A we usually write λ for ∃). We assume y, z, w, ...in {x1, x2 , x3 ...}, which are called syntactical variables. Suppose ∃: PA -> P  is an abstract binding operation. For any variable y = xi we introduce a new map ∃y: P -> P ∃y.p = ∃xi.p = ∃(p[x2, x3, ..., xi, x1, +i+1]) which is called a classical binding operation. Write  ∃y1 ... yn.p  for ∃y1 (∃y2(.... (∃yn.p)...)). For any p in P we have∃x1.p = ∃(p[x1, ++]) = (∃p)+ .∃p = (∃x1.p)-. Suppose λ: A ->  A is an abstract binding operation on a genoid A. If an element a of A has a finite rank n > 0, then  λa has a finite rank n-1. Since each xi  has a finite rank i, It follows that for any variable y, z, and w the following elements are closed:I = λy,y =  λx1.K = λyz.y = λλ x2. S = λyzw.yw(zw) = λλλ x3 x1 (x2 x1).
Mathematics Books | Universal Algebra | Lambda Calculus | Logic | Category Theory