_{Hyperalgebras}

_{with Applications to Universal Algebra, Lambda Calculus and Mathematical Logic}

Part III

If furthermore we have

L3. ((λM)[x₂, ..., x_n+1]) x₁ = M[x₁, ..., x_n+1] (β conversion).

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

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

L4. λ(M[x₂, ..., x_n+1]x₁) = M[x₁, ..., x_n] (η conversion).

Remark.  In L2 if we let M₁ = x₁, ..., M_n = x_n then we obtain

L2'. (λ M)[x₁, ..., x_n] = λ (M[x₁, ..., x_n+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 λⁿM = λ ... λ M is closed.

Theorem. Suppose A is a λ_β-hyperalgebra.

1. If M has a rank n > 0 then M = (λⁿM) x_n...x₁.

2. ((λM)[N₁, ..., N_n]) N = M[N, N₁ ..., N_n].

Lemma. Suppose A is a λ_β-hyperalgebra. Let K =  λλx₂ and S = λλλx₃x₁(x₂x₁). Then KMN = M and SMNL = ML(NL). Thus A and  F_n(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 = {x₁, x₂, ...} such that if M, N are  in Λ then  MN and λM are in Λ.   First we define M[M₁, M₂, ....]  inductively on M as follows:

1. x_i[M₁, M₂, ...] = M_i.
2. (MN)[M₁, M₂, ...] = (M[M₁, M₂, ...]) (N[M₁, M₂, ...]).
3. (λ M)][M₁, M₂, ...] = λ (M[x₁, M₁[x₂,  x₃, ...], M₂[x₂,  x₃, ...], ... ]).

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

Let  λ = { ((λM)[x₂, ..., x_n+1]) x₁ = M[x₁, ..., x_n+1] } and η = { λ(M[x₂, ..., x_n+1]x₁) = M[x₁, ..., x_n] } 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  F_n(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  F_n(A)  is a syntactical λ_β-algebra. Any homomorphism A -> B of λ_β-hyperalgebras induces a homomorphism F_n(A)  -> F_n(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 F₀(A). One can show that Г induces an equivalent functor from the category of finitary λ_β-hyperalgebras to the category of syntactical λ_β-algebras. Also each F₀(A) is naturally a λ-algebra (cf. Barendregt's book:) with K =  λλx₂ and S = λλλx₃x₁(x₂x₁).  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