with Applications to Universal Algebra, Lambda Calculus and Mathematical Logic

Part III

A λ-hyperalgebra is a hyperalgebra A together with a binary operation A X A -> A and a unary operation λ: A -> A satisfying the following axioms:

L1 (MN)[M1, ..., Mn] = (M[M1, ..., Mn]) (N[M1, ..., Mn]).

L2. M)[M1, ..., Mn][x1, ..., xn] = λ (M[x1, M1[x2, ..., xn+1], ..., Mn[x2, ..., xn+1]]).

If furthermore we have

L3. ((λM)[x2, ..., xn+1]) x1 = M[x1, ..., xn+1] (β conversion).

then we say that A is a λβ-hyperalgebra.

A λη-hyperalgebra is a λβ-hyperalgebra.such that

L4. λ(M[x2, ..., xn+1]x1) = M[x1, ..., xn] (η conversion).

Remark.  In L2 if we let M1 = x1, ..., Mn = xn then we obtain

L2'. M)[x1, ..., xn] = λ (M[x1, ..., xn+1]).

From L2' we have

Lemma. Suppose A  is a λβ-hyperalgebra.

1. If M has a rank n + 1 then  λM  has a rank n.

2. If M is closed then  λM  is closed.

3. If M has a rank n > 0 then λnM = λ ... λ M is closed.

Theorem. Suppose A is a λβ-hyperalgebra.

1. If M has a rank n > 0 then M = (λnM) xn...x1.

2. ((λM)[N1, ..., Nn]) N = M[N, N1 ..., Nn].

Lemma. Suppose A is a λβ-hyperalgebra. Let K =  λλx2 and S = λλλx3x1(x2x1). Then KMN = M and SMNL = ML(NL). Thus A and  Fn(A) are combinartory algebras.

λ-hyperalgebras form a variety of algebras of type (0, 0, ..., 2, 3,  4, ..., 1, 2) therefore free λ-hyperalgebra exist over any set F.  In particular, the initial λ-hyperalgebra exists, which is the free λ-hyperalgebra over the empty set.  Similarly, initial λβ-hyperalgebra and λη-hyperalgebra exist.

Let Λ be the smallest set containing X = {x1, x2, ...} such that if M, N are  in Λ then  MN and λM are in Λ.   First we define M[M1, M2, ....]  inductively on M as follows:

1. xi[M1, M2, ...] = Mi.
2. (MN)[M1, M2, ...] = (M[M1, M2, ...]) (N[M1, M2, ...]).
3. M)][M1, M2, ...] = λ (M[x1, M1[x2,  x3, ...], M2[x2,  x3, ...], ... ]).

Let M[M1, ..., Mm] = M[M1, ..., Mm, Mm, Mm ...]. Define the operation Λ  X Λ  -> Λ and λ: Λ  -> Λ  on Λ in an obvious way. Then it is easy to see that Λ is  the initial λ-hyperalgebra.

Let  λ = { ((λM)[x2, ..., xn+1]) x1 = M[x1, ..., xn+1] } and η = { λ(M[x2, ..., xn+1]x1) = M[x1, ..., xn] } be the sets of identities in Λ.  Let (λ) be the congruence relation in  Λ generated by λ, and let  (λ + η) be the congruence relation in Λ  generated by λ and η. Then the quotient algebra Λβ =  Λ/(λ) is the initial λβ-hyperalgebra, and the quotient algebra Λη =  Λ/(λ + η)  is the initial λη-hyperalgebra.

Theorem.  Λβ  and Λη are nontrivial hyperalgebras (i.e. they have more than one element).

Definition. A congruence relation in Λ containing λ  is called a lambda theory.

Definition. A model of the hyperalgebra Λβ  is called a syntactical λβ-algebra.

If A is a λβ-hyperalgebra then the set  Fn(A) of elements of rank n of A  is also a model of Λβ   via the unique homomorphism from the initial λβ-hyperalgebra  Λβ  to A. Thus each  Fn(A)  is a syntactical λβ-algebra. Any homomorphism A -> B of λβ-hyperalgebras induces a homomorphism Fn(A)  -> Fn(A)  of syntactical λβ-algebras. In particular for n = 0 we obtain a functor Г  from the category of λβ-hyperalgebras to the category of syntactical λβ-algebras sending each A to F0(A). One can show that Г induces an equivalent functor from the category of finitary λβ-hyperalgebras to the category of syntactical λβ-algebras. Also each F0(A) is naturally a λ-algebra (cf. Barendregt's book:) with K =  λλx2 and S = λλλx3x1(x2x1).  Our main theorem is the following

Theorem. The following categories are naturally equivalent:

1. The category of finitary λβ-hyperalgebras.

2. The category of syntactical λβ-algebras.

3. The category of λ-algebras

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