_{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 = {(A^{s}, x^{s}, +^{s}) | s in S} of G such that x^{s}+^{t}^{ }= x^{s} 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 = {D^{s}} and an S-indexed set
of
maps μ ={ μ^{s}: A^{s} X
T ->
D^{s}} such that for any a in A^{s},
u in G, w in T (i) (au)w = a(uw). (ii) For any (d, w) in D^{s} X T there is a unique element [d, w] in T such that x^{s}[d, w] = d and +^{s}[d, w] = w. |
A genoid A = (A, G) is called complete if for any infinite sequence a_{1}, a_{2}, ...of elements of A there is a unique element [a_{1}, a_{2}, ...] of G such that x_{n}[a_{1}, a_{2}, ...] = a_{n} for any n > 0, where x_{1} = x,_{ } x_{n+1} = x_{n}+ 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 d_{1}, d_{2}, ...of elements of D there is a unique element [d_{1}, d_{2}, ...] of T such that x_{n}[d_{1}, d_{2}, ...] = d_{n} 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 A^{N} 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 D^{N} is a left act of A^{N} 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 A^{N} of infinite sequences of elements of A is a monoid with a unit [x_{1}, x_{2}, ...], A is a right act of A^{N} and x_{i}[a_{1}, a_{2}, ...] = a_{i} for any [a_{1}, a_{2}, ...] in A^{N}. A left A-algebra is a set D together wit a map A X D^{N} -> D such that the induced map A^{N} X D^{N} -> D^{N} turns D^{N } into a left A^{N} act. |
Any clone (in both forms) A determines a complete genoid (A, A^{N}) with + = [x_{2}, x_{3}, ...],. Any left A-algebra D determines a complete left algebra (D, D^{N}) of the genoid (A, A^{N}). |
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 = {A^{s}} of objects such that G is the product of countable powers of all A^{s}. 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 P^{A} the new right act (P, _{*}) of G defined by p_{*}u = p(δu) = p[x, u+]. Let ev: P^{A} X A-> P be the map defined by ev(p, a) = p[a, e]. Define Λ: hom(T X A, P) -> hom(T, P^{A}) given by (Λf)t = f(t+, x) and Λ*: hom(T, P^{A}) -> 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 (P^{A}, ev) is the exponent in the the cartesian closed category Act_{G }of right acts of G. |
Letting T = P = A we obtain a bijection Λ: hom(A X A, A) -> hom(A, A^{A}). This is the starting point of lambda calculus. |
The endomorphism δ induces a functor Δ : Act_{G } -> Act_{G} sending each act P to P^{A}, and each morphism f: P -> Q to f: P^{A} -> Q^{A}. The actions of + and - induces two natural transformations + : Id -> Δ and -: Δ^{2} -> Δ. It is easy to see that (Δ, +, -)is a monad on Act_{G } . |
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 x_{i}u = x_{i}v 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 A^{A }is a retract of A (as right acts of G). We say (A , G) is extensive if A^{A }is isomorphic to A. |
A lambda calculus is a genoid A together with two homomorphisms λ : A^{A} -> 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:} A^{tAs} -> A^{s->t}} and {A^{s->t }X A^{s} -> A^{t}} such that for any a in A^{t } and c in A^{s->t} we have (λ^{s}a)+^{s}x^{s} = a and λ^{s}(c+^{s}x^{s}) = c. |
A predicate algebra with terms in a genoid (A, G) is a right act P of G with homomorphisms ∃: P^{A} -> P, F: P^{0} -> 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(D^{N}), where P(D^{N}) is the power set of D^{N}. A locally finitary predicate algebra with terms in A is a quantifier algebra iff it belongs to the variety generated by predicate algebras P(D^{N}) 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 [a_{1}, a_{2}, ..., a_{n},, u] = [a_{1}, [a_{2}, ..., [a_{n},, u]]] for any n > 0. Let - = [x, e]. Then +- = e. |
Any homomorphism ∃: P^{A} -> P is called an abstract binding operation on P. (if P = A we usually write λ for ∃). |
We assume y, z, w, ...in {x_{1},_{ }x_{2 } , x_{3} ...}, which are called syntactical variables. |
Suppose ∃: P^{A} -> P is an abstract binding operation. For any variable y = x_{i} we introduce a new map ∃y: P -> P |
For any p in P we have ∃x_{1}.p = ∃(p[x_{1}, ++]) = (∃p)+ . ∃p = (∃x_{1}.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 x_{i } has
a finite rank i, It follows that for any variable y, z,
and w the following elements are closed: I = λy,y = λx_{1}. K = λyz.y = λλ x_{2}. S = λyzw.yw(zw) = λλλ x_{3} x_{1} (x_{2} x_{1}). |
Comments to:
zluo@azd.com
Copyright by Zhaohua Luo All
rights reserved