Zhaohua Luo


with Applications to Universal Algebra, Lambda Calculus and Mathematical Logic

Part I (5/8/2008)



A hyperalgebra is an algebra of type (0, 0, ..., 2, 3, 4, ...) satisfying three axioms. Finitary hyperalgebras form a coreflective full subcategory of the variety of hyperalgebras, which is equivalent to the opposite of the category of varieties. Thus any subvariety of the variety of hyperalgebras may be viewed as a hypervariety, i.e. a variety of varieties in the sense of W. D. Neumann.


Definition. A hyperalgebra is a nonempty set A together with a sequence X = {x1, x2, ...} of elements of A and a sequence S = {s1, s2, ...} of operations sn: An+1 -> A, which satisfies the following three axioms for M, M1,..., Mm, N1, ..., Nn in A.
Write M[M1, ..., Mn] for sn(M, M1, ..., Mn).
A1. xn[M1, ..., Mm] = Mn if n
A2. (M[M1, ..., Mm])[N1, ..., Nn] = M[M1[N1, ..., Nn], ..., Mm[N1, ..., Nn]].
A3. M[M1, ..., Mm] = M[M1, ..., Mm, Mm].

The class Hyp of hyperalgebras forms a variety. Therefore the category Hyp is complete and cocomplete, with free algebras over arbitrary set.

We say an element M of a hyperalgebra A has a finite rank n > 0 if M = M[x1, ..., xn], We say M has a rank 0 (or M is closed) if M[x1] = M[x2] = M. An element M in A is called  finitary if it has a finite rank. If n is a nonnegative integer denote by Fn(A) the set of elements of rank n  of A.   

Denote by Fin(A) the set of finitary elements of A. It is the largest finitary subalgebra of A. Since any homomorphism of hyperalgebras preserves finitary elements, the category FHyp of finitary  hyperalgebras is a coreflective subcategory of Hyp. Therefore FHyp is also complete and cocomplete. But FHyp is not algebraic over Set, because it has no free algebra over any nonempty set.

Note that a hyperalgebra A is finitary iff it is generated by a set of finitary elements.

We have the following basic facts:
1, Any subalgebra of a finitary hyperalgebra is finitary.
2. Any homomorphic image of a finitary hyperalgebra is finitary.
3. The Direct product of a collection K of finitary hyperalgebras  is finitary iff K is a finite set.
Thus if G is the direct product of finitary hyperalgebras for an infinite set K then Fin(G) is the direct product
of these finitary hyperalgebras in FHyp.

Example. Let V be a variety and let T(V) be the free algebra of V over X = {x1, x2, ...}. Then T(V) is naturally a finitary hyperalgebra such that M[M1, ..., Mm] is the image of M under the endomorphism on T(V) sending xi to Mi if i ≤ m and to Mm otherwise.

Let A be a hyperalgebra. A model of A is a set D together with a sequence U = {u1, u2,...}  of operations un: A x Dn -> D, which satisfying the following axioms for M, M1, ..., Mm in A and a1, ..., an in D:
Write M[a1, ..., an] for un(M, a1, ..., an).
B1. xn[a1, ..., am] = an if n ≤ m.
B2. (M[M1, ..., Mm])[a1, ..., an] = M[M1[a1, ..., an], ..., Mm[a1, ..., an]].
B3. M[a1, ..., an] = M[a1, ..., an, an ].

Define homomorphisms of models of A in an obvious way. Denote by Mod(A) the category of models of A.

Example. Note that A is a model of A. For any nonnegative integer n the set Fn(A)  of elements of rank n of A is also a model of A. In fact Fn(A)  is the free model of A of rank n.

Theorem. 1. If V is a variety and T(V) is the free algebra of V over X, then T(V) is naturally a finitary hyperalgebra algebra, and V is equivalent to Mod(T(V)) as concrete categories over Set .
2. If A is a hyperalgebra then the class Mod(A) forms a variety. If A is a finitary  hyperalgebra then A is isomorphic to T(Mod(A)).
3. The correspondences A -> Mod(A) and V -> T(V) establish an equivalence between the category FHyp of finitary hyperalgebras and the opposite of the category of varieties.

Example. For any nonempty set S let [S*] be the set of all infinite sequences [a1, ..., an, an, a...] (n > 0) of elements of S. Let H(S) be the set of all  functions from [S*] to S. Let xi : [S*] -> S be the i-th projection. Then H(S) is naturally a hyperalgebra with M[M1, ..., Mm] being defined by M[M1, ..., Mm][a1, a2, ...] = M[M1[a1, a2, ...], ..., Mn[a1, a2, ...], Mn[a1, a2, ...], ...].

Definition. H(S) is called a primal hyperalgebra. F(H(S))  is called a finitary primal hyperalgebra.

Any hyperalgebra A determines a homomorphism h: A -> H(A) sending each M in A to the function h(M): [A*] -> A  given by h(M)[M1, ..., Mn, Mn, Mn,  ...] = M[M1, ..., Mn]. If A is finitary then h(A) is finitary and h is injective as M[x1, ..., xn] = M for some n > 0.. Since h(A) is a subalgebra of F(H(A)),  we have the following

Theorem (Cayley's theorem for hyperalgebras) Any finitary hyperalgebra is isomorphic to a subalgebra of a finitary primal hyperalgebra.

Part I  II  III


Mathematics Books | Universal Algebra | Lambda Calculus | Logic | Category Theory

Comments to: zluo@azd.com
Copyright by Zhaohua Luo  All rights reserved