|
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)). |
| 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. |
| 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 . |
| 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. |
| 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. |
| 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. |
|
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 |
|
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). |
Comments to:
zluo@azd.com
Copyright by Zhaohua Luo All
rights reserved