Home
Introduction
A genoid theory is a
category (A, G) of two objects such that
G together with two morphisms x:
G > A and
+: G >
G
is the product of A and G, and
G is a dense object. A left algebra of
(A, G) is a functor from
(A, G) to the category Set
of sets preserving the product.
Let A =
hom(G, A) and G =
hom(G, G). For any pair (a, u) in
A X G let [a,
u]: G > G be the
unique morphism such that x[a, u] =
a and + [a, u] = u. Then u
= [xu, +u] for any u in
G. 
A clone theory is a category
(A, G) of two objects such that
G together with an infinite sequence of morphisms
x_{1}, x_{2}, .. from G to
A is a countable power of
A. A left algebra of
(A, G) is a functor from
(A, G) to Set preserving the
power. Left algebras of clone theories are main objects of study in
universal algebra.
Let A =
hom(G, A) and G =
hom(G, G). For any infinte
sequence a_{1}, a_{2}, .... in
A let [a_{1}, a_{2}...]:
G >
G be the unique morphism
such that x_{i}[a_{1},
a_{2}...] = a_{i}. Then u =
[x_{1}u, x_{2}u,...] for any
u in G. Any clone theory determines a
genoid theory with x = x_{1}, + = [
x_{2}, x_{3} ,
...]. 
Let (A, G) be a genoid.
Let P be a right act of the monoid G =
hom(G, G). An abstract binding
(resp. cobinding) operation on P is a
map σ: P
> P such that (σp)u =
σ(p[x, u+]) (resp. σ(pu) =
(σp)[x, u+]) for any p in P and
u in G. A binding algebra of
(A, G) is a right
act P of G equipped with some binding, cobinding
operations, and other homomorphism of right acts
P^{n} >
P for various arity n
≥ 0. Here are two
important types of binding algebras:
Lambda
Calculus: A reflexive lambda calculus is
a genoid (A, G) together with a
binding operation λ: A >
A and a cobinding operation λ*: A
> A such that
λλ* = id_{A}. An extensive lambda
calculus is a genoid (A,
G) together with a bijective binding operation
λ: A > A.
First Order Logic: A quantifier
algebra with terms in a genoid
(A, G) is a right act P of
G with an abstract binding operation : P > P and two
homomorphisms F:
P^{0} >
P, and =>: P
X P
> P such that (i) P is a Boolean
algebra with respect to the derived operations (V, Λ, ~, F,
T). (ii) ∃ (p ∨ q) =
(∃ p) ∨ (∃ q) for
any p,q, in P. (iii) p <
(∃p)+ for any p in P.
 
Genoids 
A genoid (A,
G, x, +, [ ]) consisting of a
monoid (G, e), a right act A of G, an
element x of A, an element + of G, and a map
[ ]: A X
G > G such that
for any a in A and u in G we
have (i) x[a, u] =
a. (ii) +[a, u] =
u. (iii) u = [xu,
+u]. In the following we fix a
genoid, denoted simply by (A, G). We shall write
[a_{1}, a_{2}, ..a_{n}, u]
for [a_{1}, [a_{2}, [...
[a_{n}, u]...]]]. 
Let x_{1} = x, x_{i
}=_{
}x_{i}+_{ }for any i
> 0. Then (iii) extends to
u = = [x_{1}u,
x_{2}u, ... x_{n}u, +^{n}u]
for any n > 0. Let κ_{n}: G
> A^{n} be the
map sending each u to the expression [x_{1}u,
x_{2}u, ... x_{n}u]. We assume y, z, w, ...in
{x_{1},_{ }x_{2 },
x_{3} ...}, which are called syntactical
variables. 
Let P be a right act of the
monoid G. We say an element p of P has a
finite rank n > 0 if pu = pv for any u,
v in G with κ_{n}(u) = κ_{n}(v). We say
p has a finite rank 0 (or p is closed) if pu
= pv for any u, v in G. An element of P is
called finitary if it has a finite rank. We say P (or
A) is locally finitary if any of its element is
finitary. We say an element p of P is
independent of x_{n }if p
= p[x_{1}, .. x_{(n1)},
x_{(n+1)},
+^{n}]. 
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 oneobject 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+]. A map σ: P > P is an abstract
binding (resp. cobinding)
operation if it is a homomorphism from P^{A }to P (resp. from P to P^{A}). Such abstract binding operations can be applied to defined
algebraic theories for lambda calculus and first order logic. The
traditional binding operation σx_{i} : P > P (for each
variable x_{i}) is then defined as the derived
operation:
σx_{i}.p = σ(p[x_{2}, x_{3}, ...,
x_{i}, x_{1}, +^{i+1}]).
If y = x_{i}
then σy.p means
σx_{i}.p. 
The main difference between an
abstract binding σ: P > P and a derived operation
σy: P
>
P is that
σ reduces the rank n > 0
of a finitary element of P by 1 while σy
makes any element of P independent of the variable
y (i.e. binding y). Hence if p has a finite
rank n > 0 then σ^{n}p and σx_{1}. ...
σx_{n}.p are
always closed. 
If P is
a right act of G let ev: P^{A}
X
A
> P
be the map defined by ev(p, a) =
p[a, e]. For any right act T of
G define Λ: hom(T X A, P) >
hom(T, P^{A}) given by
(Λf)t = f(t+, x).
Define Λ^{1}:
hom(T, P^{A}) >
hom(T X A, P) by
(Λ^{1}g)(t, a) = g(t)[a,
e] = ev(g(t), a).
It is easy to see that
Λ is the inverse of Λ^{1}. 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. 
We say (A, G) is an extensive
genoid (or (extensive) lambda
calculs) if it has a bijective abstract binding operation λ:
A >
A. Denote by λ*
the inverse of λ. Then λ* is a cobinding operation.
Thus λ* determines a homomorphism
Λ^{1}(λ*): A X A > A defined by
ab = λ*a[b, e].
Hence a genoid is extensive iff there is a
homomorphism A X
A > A of right acts of G such that the induced
cobinding operation λ* defined by
λ*(a) = (a+)x
is bijective. Since id_{A
}= λ*λ = λλ*, we have the following
two axioms
a =
(λa)+x 
(or a = (λy.a)y for any
y) 
(βconversion) 
a =
λ(a+x) 
(or a
= λy.(ay) if a is independent of
y) 
(ηconversion) 

We list some of
the useful properties for lambda calculus: (a, b, c in
A and u in G)
(1) (λa)b
= a[b, e].
(2) ((λ
a)u)b = a[b,
u].
(3) (λa+)b = a.
(4) (λ^{n} a)+^{n}
x_{n}...x_{1} = a for any integer n
> 0.
(5) If a has a finite rank n
> 0 then (λ^{n}a)x_{n}...x_{1}
= a and λ^{n}a is closed.
Thus
(λ^{n}a)a_{n}...a_{1
}= (λ^{n}a)x_{n}...x_{1}
[a_{1}, ..., a_{n}, e] =
a[a_{1}, ..., a_{n}]
(6) An element
a has a finite rank n > 0 if and only if
there is a closed element c such that
a =
cx_{n}...x_{1}. 
The following closed terms play important
role in lambda calculus (notation:
λy_{1}...y_{n}.a =
λy_{1}.(λy_{2}.(..(λy_{n}.a)...)).)
I =
λy,y = λx_{1}. K =
λyz.y = λλ x_{2} S =
λyzw.yw(zw) =
λλλx_{3}x_{1}(x_{2}
x_{1}).
It follows from
(5) we have
Ia
= x_{1} [a, e] = a.
Kab =
x_{2}[b, a, e] =
a.
Sabc =
(x_{3}x_{1}(x_{2}x_{1}))[c,
b, a, e] = ac(bc). 

Clones 
A clone is a set
A such that (i) The set A* of
all the infinite sequences [a_{1}, a_{2},
...] of elements of A is a monoid with a unit
[x_{1}, x_{2}, ...]. (ii) A is a right act of A*. (iii) x_{i}[a_{1},
a_{2}, ...] = a_{i }for any
[a_{1}, a_{2}, ...] and i >
0. 
Any clone A determines a
genoid (A, A*, x_{1}, +, [ ])
with + = [x_{2}, x_{3}, ...] and
[a_{1}, [b_{1}, b_{2} ,..]] =
[a_{1}, b_{1}, b_{2} ,..].
Conversely, assume (A, G) is a any genoid. Denote by
F(A) the set of finitary elements of A. For any
a in F(A) with a finite rank n >
0 and [a_{1}, a_{2}, ...] in
F(A)* define a[a_{1}, a_{2},
...] = a[a_{1}, a_{2}, ...,
a_{n} , e], which is independent of the choice
of n. Let
[a_{1}, a_{2},
...][b_{1}, b_{2}, ...] =
[a_{1}[b_{1}, b_{2}, ...],
a_{2}[b_{1}, b_{2}, ...],
...]
Then F(A)* is a monoid with
the unit [x_{1}, x_{2}, ...],
F(A) is a right act of A*, and
x_{i}[a_{1}, a_{2}, ...] =
a_{i}._{ }Thus (F(A),
F(A)*) is a locally finitary genoid. If A =
F(A) is locally finitary then we have a canonical
homomorphism of genoids (A, G) > (A, A*) sending each
u in G to [x_{1}u, x_{2}u, ...
x_{n}u, ...]. Since any abstract binding operation
preserving finitary elements, if (A, G) is a lambda
calculus, then so is (F(A),
F(A)*). 
The class of
genoids forms a variety of 2sorted heterogeneous finitary algebras
with universes A and G. The class of clones
forms a variety of infinitary algebras with universe
A. 
Let N be a full
subcategory of a category X. A Kleisli
triple over N is a system T =
(T, η, *) consisting
of functions (a) T: Ob N > Ob X, (b) η assigns to each object A in
N a morphism η_{A}: A
> TA, (c) *
maps each morphism f: B > TC with B, C in
N to a morphism *f: TB > TC, such that for
any g: C > TD with D
in N (i) *f*g = *(f*g
). (ii) η_{B}*f =
f. (iii) *η_{C} =
id_{TC}. 
If N = X
we obtain the original definition for a Kleisli triple over a
category, which is an alternative description of a
monad. 
Let N be a
full subcategory of a category X. A
clone over N is a pair (K,
T) where K is a category and T is a functor
T: K > X such that
for any A, B, C in N (i). Ob N =
Ob K. (ii). K(A, B) =
X(A, TB). (iii). f(Tg) = fg for
any f in K(A, B) and g in K(B,
C). 
The notions of a clone over N
is equivalent to a Kleisli triple over N
defined above.. 
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 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 oneobject category is equivalent to a Kleisli
algebra. 
1. Clone Theory, its
Syntax and Semantics, and Applications to Lambda Calculus and
Algebraic Logic 

pdf 
2. Clones and Genoids
(Basic Concepts) 
html 
pdf 
3. Clones and Genoids in
Lambda Calculus and First Order Logic 

pdf 


 