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)[M_{1}, ..., M_{n}] = (M[M_{1}, ..., M_{n}])
(N[M_{1}, ..., M_{n}]).
L2. (λM)[M_{1}, ..., M_{n}][x_{1},
..., x_{n}] = λ (M[x_{1}, M_{1}[x_{2},
..., x_{n+1}], ..., M_{n}[x_{2}, ..., x_{n+1}]]).
If furthermore we have
L3. ((λM)[x_{2}, ..., x_{n+1}]) x_{1}
= M[x_{1}, ..., x_{n+1}] (β
conversion).
then we say that A is a λ_{β}-hyperalgebra.
A λ_{η}-hyperalgebra is a
λ_{β}-hyperalgebra.such that
L4. λ(M[x_{2}, ..., x_{n+1}]x_{1})
= M[x_{1}, ..., x_{n}] (η
conversion).
**Remark. ** In L2 if we let M_{1} = x_{1}, ...,
M_{n} = x_{n} then we obtain
L2'. (λ M)[x_{1}, ..., x_{n}] =
λ (M[x_{1}, ..., 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 λ^{n}M =
λ ... λ M is closed.
**Theorem.** Suppose A is a λ_{β}-hyperalgebra.
1. If M has a rank n > 0 then M = (λ^{n}M)
x_{n}...x_{1}.
2. ((λM)[N_{1}, ..., N_{n}]) N
= M[N, N_{1 }..., N_{n}].
**Lemma.** Suppose A is a λ_{β}-hyperalgebra.
Let** K** = λλx_{2} and **S** = λλλx_{3}x_{1}(x_{2}x_{1}).
Then **K**MN = M and **S**MNL = 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_{1},
x_{2}, ...} such that if M, N are in Λ
then MN and λM are in Λ.
First we define M[M_{1}, M_{2}, ....] inductively on M
as follows:
1. x_{i}[M_{1}, M_{2}, ...] = M_{i}.
2. (MN)[M_{1}, M_{2}, ...] = (M[M_{1}, M_{2},
...]) (N[M_{1}, M_{2}, ...]).
3. (λ M)][M_{1}, M_{2}, ...] =
λ (M[x_{1}, M_{1}[x_{2},
x_{3}, ...], M_{2}[x_{2}, x_{3}, ...],
... ]).
Let M[M_{1}, ..., M_{m}] = M[M_{1}, ..., 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_{2},
..., x_{n+1}]) x_{1} = M[x_{1}, ..., x_{n+1}]
} and **η** = { λ(M[x_{2},
..., x_{n+1}]x_{1}) = M[x_{1}, ..., 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_{0}(A). One can show that Г induces an
equivalent functor from the category of finitary λ_{β}-hyperalgebras
to the category of syntactical λ_{β}-algebras.
Also each F_{0}(A) is naturally a λ-algebra (cf. Barendregt's book:)
with **K** = λλx_{2} and **S** = λλλx_{3}x_{1}(x_{2}x_{1}).
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 |