Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 37 (1996), No. 2, 259-287.

Varieties of Partial Algebras

Ferdinand Börner

Universität Potsdam, WIP “Algebra & Logik” Am Neuen Palais 10, PF 601553, D–14415 Potsdam e–mail: FBOERNER@RZ.UNI-POTSDAM.DE

Abstract. Starting with a notion of an abstract partial clone, we introduce a concept for varieties of partial algebras.

1. Introduction

The investigation of partial algebras has provided several different concepts of partial varieties, equational theories and termfunctions for partial algebras ([1],[2],[5],[7],[13],[21]). Usually these concepts are, more or less, natural generalizations of the corresponding notions in the case of total functions. These approaches are not only of theoretical interest. Of practical interest is the desire, in computer science, to find convenient tools to handle partial functions. (See e.g. [18].)

In the total case, there is a well known connection between varieties and clones (see [16]). Our aim is to generalize this connection to the partial case. Therefore, our starting point is a notion of an “abstract partial clone”. We want to define “partial varieties” to establish the same connection as in the total case. Our approach is influenced by H.-J. Hoehnke’s description of categories of partial functions ([8], [9], [10]) and by the investigations of B.M. Schein and V.S. Trochimenko on Menger algebras and Menger systems ([20]).

With this point of view, our developements seem quite natural. We define our notion of a variety of partial algebras using partial clones and then try to find the “correct” definitions for terms and equations to characterize these classes. It turns out that we must use the equational language Eq(e) described by W. Craig ([7]). In this paper, he already mentioned the relationship between clones and this language.

Using these notions, we introduce some special partial term algebras. We can use such to prove, that partial varieties are exactly those classes of partial algebras which are closed under

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1996 Heldermann Verlag, Berlin

forming filtered products, subalgebras, and images of closed homomorphisms. An (almost) equivalent notion of a partial variety was introduced by P. Burmeister in [5] under the name “ECE-varieties”. The “ECE” stands for “existentially conditioned existence equations”, a special semantical concept for equations of terms and the connected term operations. In our paper, we use only the so called “Kleene-equality” for our (extended) concept of terms.

In section 2, we begin with the notion of a partial clone and the corresponding characterization theorem. We introduce partial algebras, homomorphisms, subalgebras, products and define our main notion in section 3. In section 4, we turn to terms and equations. Finally, we introduce our term algebras and prove a Birkhoff-type theorem for our variety concept.

The author is grateful to P. Burmeister for lots of useful suggestions and interesting discussions.

2. Partial Functions and Partial Clones

To define a partial function f, we need four things. First a set A (the source object of f), a set B (the target object of f), a subset dom f ⊆ A (the domain of f) and an assignment, mapping each a ∈ dom f to a value f(a) ∈ B. We write this in the following form:

f : A ∘→ B
dom f := …
a ↦ f(a)

The range of f is the set range f := {f(a) | a ∈ dom f}. If dom f = A, then f is called total, and we write f : A → B instead of f : A ∘→ B.

If f : A ∘→ B and g : B ∘→ C, then the composition g ∘ f of f and g is the partial function:

g ∘ f : A ∘→ C
dom g ∘ f := {a ∈ A | a ∈ dom f and f(a) ∈ dom g}
a ↦ g(f(a))

If f_{i} : A ∘→ B_{i} for i = 1 … n, then the tupelfunction of f_{1}, …, f_{n} is the partial function:

[f_{1}, …, f_{n}] : A ∘→ ∏_{i=1...n} B_{i}
dom [f_{1}, …, f_{n}] := ⋂_{i=1...n} domf_{i}
a ↦ (f_{1}(a), …, f_{n}(a))

Now let n ∈ Np := N \ {0} and let A be a set. The set of all n-ary partial functions on A is Par^{(n)}(A) := {f | f : A^{n} ∘→ A}, and the set of all finitary partial functions on A is Par(A) := ⋃_{n∈Np} Par^{(n)}(A). If C ⊆ Par(A), then we put C^{(n)} := C ∩ Par^{(n)}(A).

A subset B ⊆ A is said to be closed under the function f ∈ Par^{(n)}(A), if f(\underline{b}) ∈ B for all \underline{b} ∈ B^{n} ∩ dom f. In this case we can define the restriction of f to B:

f|_{B} : B^{n} ∘→ B
dom f|_{B} := B^{n} ∩ dom f
\underline{b} ↦ f(\underline{b})

Special n-ary (total) functions are the projections to the i-th argument, where 1 ≤ i ≤ n:

e_{i,A}^{n} : A^{n} → A
(a_{1}, …, a_{n}) ↦ a_{i}

For n, m ∈ Np we define the (n, m) - superposition.

sup_{m,A}^{n} : Par^{(n)}(A) × (Par^{(m)}(A))^{n} → Par^{(m)}(A)
f, g_{1}, …, g_{n} ↦ f ∘ [g_{1}, …, g_{n}]

Remark. The superposition sup_{m,A}^{n} is a total many sorted operation, mapping partial functions on A to a new partial function on A. More exactly we have:

f ∘ [g_{1}, …, g_{n}] : A^{m} ∘→ A
dom (f ∘ [g_{1}, …, g_{n}]) = \{\underline{a} ∈ A^{m} | \underline{a} ∈ ⋂_{i=1...n} dom g_{i}
and (g_{1}(\underline{a}), …, g_{n}(\underline{a})) ∈ dom f\}
\underline{a} ↦ f(g_{1}(\underline{a}), …, g_{n}(\underline{a}))

There are also other possibilities to define superpositions of partial functions (see e.g. [11]). Our notion is known as Malcev superposition. It is described in [15], and it seems to be the most natural generalization of the superposition of total functions.

Now we can consider a many-sorted (total) algebra with carrier family (Par^{(n)}(A))_{n∈Np}, with the superpositions as operations and the projections as constants.

Definition 2.1

\underline{Par}(A) := ⟨ (Par^{(n)}(A))_{n∈Np} ; (sup_{m,A}^{n})_{n,m∈Np} , (e_{i,A}^{n})_{1≤i≤n∈Np} ⟩

The many sorted algebra \underline{Par}(A) is called the full partial clone on the set A. A concrete partial clone on the set A is a subalgebra of \underline{Par}(A).

Remark. Please observe that partial clones are total algebras on an Np-sorted carrier family. We assume that the reader is familiar with the notions of homomorphisms, subalgebras and congruences for many sorted algebras; we refer e.g. to [12] .

The partial clones, defined in 2.1, are concrete structures, i.e. they are defined by concrete operations on concrete sets. Now we turn to the question, how to give an abstract description for partial clones. More exactly, we want to find a description for the variety, generated by all concrete partial clones.

Definition 2.2 Let \underline{C} be a Np-sorted algebra of the form

\underline{C} := ⟨ (C_{n})_{n∈Np} ; (s_{m}^{n})_{n,m∈Np} , (e_{i}^{n})_{1≤i≤n∈Np} ⟩ ,

where e_{i}^{n} ∈ C_{n} and s_{m}^{n} : C_{n} × (C_{m})^{n} → C_{m} for all n, m ∈ Np and 1 ≤ i ≤ n. \underline{C} is called an abstract partial clone, if the following equations hold for all n, m, l ∈ Np, 1 ≤ i ≤ n and all f, g, h ∈ C_{n}, g_{1}, …, g_{n} ∈ C_{m}, h_{1}, …, h_{m} ∈ C_{l}:

s_{l}^{m}(s_{m}^{n}(f , g_{1} …, g_{n}) , h_{1}, …, h_{m}) = s_{l}^{n}(f , s_{l}^{m}(g_{1}, h_{1}, …, h_{m}), …, s_{l}^{m}(g_{n}, h_{1}, …, h_{m}))
s_{n}^{2}(e_{1}^{2} , f, g) = s_{n}^{n}(f , s_{n}^{2}(e_{1}^{2}, e_{1}^{n}, g), …, s_{n}^{2}(e_{1}^{2}, e_{n}^{n}, g))
s_{n}^{1}(e_{1}^{1} , f) = f
s_{n}^{2}(e_{1}^{2} , f, e_{i}^{n}) = f
s_{n}^{2}(e_{1}^{2} , s_{n}^{2}(e_{1}^{2} , f, g), h) = s_{n}^{2}(e_{1}^{2} , f, s_{n}^{2}(e_{1}^{2} , g, h))
s_{m}^{n+1}(e_{1}^{n+1} , g_{1}, …, g_{n+1}) = s_{m}^{2}(e_{1}^{2} , g_{1}, s_{m}^{n}(e_{1}^{n} , g_{2}, …, g_{n+1})
s_{m}^{n+1}(e_{i+1}^{n+1} , g_{n+1}, g_{1}, …, g_{n}) = s_{m}^{n+1}(e_{i}^{n+1} , g_{1}, …, g_{n+1})

Obviously the class of all abstract partial clones forms a variety of many sorted algebras. But before we show that this is exactly the variety, generated by the concrete partial clones, we want to introduce an abbreviation. We will abbreviate:

f[g_{1}, …, g_{n}] := s_{m}^{n}(f , g_{1}, …, g_{n})

Then the equations in 2.2 look as follows:

(f[g_{1}, …, g_{n}])[h_{1}, …, h_{m}] = f[g_{1}[h_{1}, …, h_{m}], …, g_{n}[h_{1}, …, h_{m}]]  (1)
e_{1}^{2}[f, g] = f[e_{1}^{2}[e_{1}^{n}, g], …, e_{1}^{2}[e_{n}^{n}, g]]  (2)
e_{1}^{1}[f] = f  (3)
e_{1}^{2}[f, e_{i}^{n}] = f  (4)
e_{1}^{2}[e_{1}^{2}[f, g], h] = e_{1}^{2}[f, e_{1}^{2}[g, h]]  (5)
e_{1}^{n+1}[g_{1}, …, g_{n+1}] = e_{1}^{2}[g_{1}, e_{1}^{n}[g_{2}, …, g_{n+1}]]  (6)
e_{i+1}^{n+1}[g_{n+1}, g_{1}, …, g_{n}] = e_{i}^{n+1}[g_{1}, …, g_{n+1}]  (7)

The equation (1) is known as the law of superassociativity.

The following theorem was proved in the dissertation [3, Satz 4.2.3] (unpublished) and can also be found in the preprint [4, Theorem 1.5]. It is an answer to a problem, posed 1987 by H.-J. Hoehnke. He asked for an abstract description of concrete partial clones with a superposition operation in the sense of Malcev [15]. In [9], Hoehnke gave an abstract characterization with the help of dht-symmetric theories. A category theoretical interpretation of our theorem can be found in [10, Part IV, Theorem 27.3]. In a more general context, one can consider categories of partial functions between arbitrary sets instead of concrete partial clones. For an abstract characterization of such categories see [22]. Another way to describe clone-like structures uses Menger algebras and Menger systems, we refer to [20].

Theorem 2.3 Every concrete partial clone is an abstract partial clone. Every abstract partial clone is isomorphic to a subdirect product of concrete partial clones.

Proof. To show the first part of 2.3 it is only necessary to check the equations (1)-(7) for all concrete partial clones. This can be done easily by using Definition 2.1 and the definitions of sup_{m,A}^{n} and e_{i,A}^{n}. We leave this part of the proof to the interested reader and turn to the second part.

Let \underline{C} be an abstract partial clone as in 2.2. We will construct a family (γ_{A})_{A∈M} of homomorphisms γ_{A} : \underline{C} → \underline{Par}(A) in such a way, that for all n ∈ Np and all f, g ∈ C_{n} with f ≠ g there is an A ∈ M such that γ_{A}(f) ≠ γ_{A}(g). Then \underline{C} is isomorphic to a subdirect product of the images γ_{A}(\underline{C}) with A ∈ M, which are concrete partial clones.

We fix an l ∈ Np and define a relation ⪯ on C_{l}:

f ⪯ g :⇔ e_{1}^{2}[f, g] = f

First we show that ⪯ is a reflexive and transitive relation on C_{l}, i.e. it is a quasiorder. Reflexivity:

e_{1}^{2}[f, f] =^{(3)} e_{1}^{2}[e_{1}^{1}[f], e_{1}^{1}[f]] =^{(1)} (e_{1}^{2}[e_{1}^{1}, e_{1}^{1}])[f] =^{(4)} e_{1}^{1}[f] =^{(3)} f  (8)

Transitivity: Let f ⪯ g (+) and g ⪯ h (++). Then we have:

e_{1}^{2}[f, h] =^{(+)} e_{1}^{2}[e_{1}^{2}[f, g], h] =^{(5)} e_{1}^{2}[f, e_{1}^{2}[g, h]] =^{(++)} e_{1}^{2}[f, g] =^{(+)} f

We define another relation on C_{l}:

f ∼ g :⇔ f ⪯ g and g ⪯ f

The relation ⪯ is a quasiorder and consequently ∼ is an equivalence relation. Therefore C_{l} is partitioned into the equivalence classes with respect to ∼. Now fix such an equivalence class and call it A. Let n ∈ Np and let f ∈ C_{n}. We define a partial function f^{A} ∈ Par^{(n)}(A):

f^{A} : A^{n} ∘→ A
dom f^{A} := {(h_{1}, …, h_{n}) ∈ A^{n} | f[h_{1}, …, h_{n}] ∈ A}
(h_{1}, …, h_{n}) ↦ f[h_{1}, …, h_{n}]

We prove that the map γ_{A} : \underline{C} → \underline{Par}(A), f ↦ f^{A} is a clone-homomorphism. First we consider the constants e_{i}^{n}.

By (3) it is immediately clear that (e_{1}^{1})^{A} = e_{1,A}^{1}. Now consider e_{1}^{2}. Let h_{1}, h_{2} ∈ A. Then h_{1} ∼ h_{2} and therefore h_{1} ⪯ h_{2}. Consequently e_{1}^{2}[h_{1}, h_{2}] = h_{1} ∈ A, i.e. (e_{1}^{2})^{A} is total and (e_{1}^{2})^{A} = e_{1,A}^{2}. Now, using (6) and (7), it is easy to prove by induction on i and n that

e_{i}^{n}[h_{1}, …, h_{n}] = h_{i} for all h_{1}, …, h_{n} ∈ A .  (9)

But this means that (e_{i}^{n})^{A} = e_{i,A}^{n} and therefore γ_{A}(e_{i}^{n}) = e_{i,A}^{n} for all 1 ≤ i ≤ n ∈ Np.

Now we turn to the superposition operations of our partial clones. Let f ∈ C_{n} and g_{1}, …, g_{n} ∈ C_{m}. We want to prove that γ_{A} has the homomorphism property, and therefore we have to compare the partial functions (s_{m}^{n}(f , g_{1}, …, g_{n}))^{A} and sup_{m,A}^{n}(f^{A} , g_{1}^{A}, …, g_{n}^{A}), or in the abbreviated form, (f[g_{1}, …, g_{n}])^{A} and f^{A} ∘ [g_{1}^{A}, …, g_{n}^{A}]. So let

(h_{1}, …, h_{m}) ∈ dom (f^{A} ∘ [g_{1}^{A}, …, g_{n}^{A}]) ⊆ A^{m} .

264 F. Börner: Varieties of Partial Algebras

By our definitions we have:

(f^{A} ∘ [g_{1}^{A}, …, g_{n}^{A}])(h_{1}, …, h_{m}) =^{(def)} f^{A}(g_{1}^{A}(h_{1}, …, h_{m}), …, g_{n}^{A}(h_{1}, …, h_{m}))
=^{(def)} f[g_{1}[h_{1}, …, h_{m}], …, g_{n}[h_{1}, …, h_{m}]]
=^{(1)} (f[g_{1}, …, g_{n}])[h_{1}, …, h_{m}] ∈ A
=^{(def)} (f[g_{1}, …, g_{n}])^{A}(h_{1}, …, h_{m})

This shows (h_{1}, …, h_{m}) ∈ dom (f[g_{1}, …, g_{n}])^{A}, therefore

dom (f^{A} ∘ [g_{1}^{A}, …, g_{n}^{A}]) ⊆ dom (f[g_{1}, …, g_{n}])^{A} and

(f^{A} ∘ [g_{1}^{A}, …, g_{n}^{A}])(h_{1}, …, h_{m}) = (f[g_{1}, …, g_{n}])^{A}(h_{1}, …, h_{m})

for all (h_{1}, …, h_{m}) ∈ dom (f^{A} ∘ [g_{1}^{A}, …, g_{n}^{A}]). Now we only have to prove that:

dom (f[g_{1}, …, g_{n}])^{A} ⊆ dom (f^{A} ∘ [g_{1}^{A}, …, g_{n}^{A}])

For this step we need some preparations.

e_{1}^{2}[e_{1}^{2}[f, g], f] =^{(5)} e_{1}^{2}[f, e_{1}^{2}[g, f]] =^{(8)} e_{1}^{2}[f, e_{1}^{2}[e_{1}^{2}[g, g], f]] =^{(5)} e_{1}^{2}[f, e_{1}^{2}[g, e_{1}^{2}[g, f]]] =^{(5)}

= e_{1}^{2}[e_{1}^{2}[f, g], e_{1}^{2}[g, f]] =^{(7)} e_{1}^{2}[e_{1}^{2}[f, g], e_{2}^{2}[f, g]] =^{(1)} (e_{1}^{2}[e_{1}^{2}, e_{2}^{2}])[f, g] =^{(4)} e_{1}^{2}[f, g]

Consequently e_{1}^{2}[f, g] ⪯ f. By (3) we have e_{1}^{1}[k_{1}] = k_{1} ⪯ k_{1}. If n > 1, then because of (6)

e_{1}^{n}[k_{1}, …, k_{n}] =^{(6)} e_{1}^{2}[k_{1}, e_{1}^{n−1}[k_{2}, …, k_{n}]] ⪯ k_{1} ,

and for i > 1

e_{i}^{n}[k_{1}, …, k_{n}] =^{(7)} e_{1}^{n}[k_{i}, …, k_{n}, k_{1}, …, k_{i−1}] ⪯ k_{i} .

Therefore we obtain for all 1 ≤ i ≤ n ∈ Np and all k_{1}, …, k_{n} ∈ C_{m}:

e_{i}^{n}[k_{1}, …, k_{n}] ⪯ k_{i}  (10)

Furthermore we obtain:

e_{1}^{2}[f[k_{1}, …, k_{n}], e_{i}^{n}[k_{1}, …, k_{n}]] =^{(1)} (e_{1}^{2}[f, e_{i}^{n}])[k_{1}, …, k_{n}] =^{(4)} f[k_{1}, …, k_{n}]

f[k_{1}, …, k_{n}] ⪯ e_{i}^{n}[k_{1}, …, k_{n}] ⪯^{(10)} k_{i}  (11)

Now let (h_{1}, …, h_{m}) ∈ dom (f[g_{1}, …, g_{n}])^{A}. Then (f[g_{1}, …, g_{n}])[h_{1}, …, h_{m}] ∈ A and therefore in particular h_{1} ∼ (f[g_{1}, …, g_{n}])[h_{1}, …, h_{m}].

(f[g_{1}, …, g_{n}])[h_{1}, …, h_{m}] =^{(1)} f[g_{1}[h_{1}, …, h_{m}], …, g_{n}[h_{1}, …, h_{m}]]
⪯^{(11)} g_{i}[h_{1}, …, h_{m}]
⪯^{(11)} h_{1} ∼ (f[g_{1}, …, g_{n}])[h_{1}, …, h_{m}]

Now we have h_{1} ∼ g_{i}[h_{1}, …, h_{m}] ∼ (f[g_{1}, …, g_{n}])[h_{1}, …, h_{m}], i.e. g_{i}[h_{1}, …, h_{m}] ∈ A and therefore [h_{1}, …, h_{m}] ∈ dom g_{i}^{A} and furthermore (g_{1}[h_{1}, …, h_{m}], …, g_{n}[h_{1}, …, h_{m}]) ∈ dom f^{A}. This proves dom (f[g_{1}, …, g_{n}])^{A} ⊆ dom (f^{A} ∘ [g_{1}^{A}, …, g_{n}^{A}]) and yields:

(s_{m}^{n}(f , g_{1}, …, g_{n}))^{A} = sup_{m,A}^{n}(f^{A} , g_{1}^{A}, …, g_{n}^{A})

Therefore γ_{A} is a homomorphism between partial clones.

We can now choose M to be the set of all possible equivalence classes of ∼ on the sets C_{l} with l ∈ Np. To finish our proof we have to show that for every pair f, g ∈ C_{n} with f ≠ g there is an A ∈ M such that γ_{A}(f) ≠ γ_{A}(g). Let us assume that g^{A} = f^{A} for all A ∈ M. Because of

e_{1}^{2}[g, e_{1}^{2}[e_{i}^{n}, g]] =^{(5)} e_{1}^{2}[e_{1}^{2}[g, e_{i}^{n}], g] =^{(4)} e_{1}^{2}[g, g] =^{(8)} g ,

(i.e. g ⪯ e_{1}^{2}[e_{i}^{n}, g]), and because of (11) we obtain g ∼ e_{1}^{2}[e_{i}^{n}, g] for all i = 1, …, n. If we choose l = n and A to be the equivalence class containing g, then we have:

g =^{(8)} e_{1}^{2}[g, g] =^{(2)} g[e_{1}^{2}[e_{1}^{n}, g], …, e_{1}^{2}[e_{n}^{n}, g]] =^{(def)} g^{A}(e_{1}^{2}[e_{1}^{n}, g], …, e_{1}^{2}[e_{n}^{n}, g])

= f^{A}(e_{1}^{2}[e_{1}^{n}, g], …, e_{1}^{2}[e_{n}^{n}, g]) =^{(def)} f[e_{1}^{2}[e_{1}^{n}, g], …, e_{1}^{2}[e_{n}^{n}, g]] =^{(2)} e_{1}^{2}[f, g] ⪯^{(10)} f

If we interchange f and g, then we obtain f = e_{1}^{2}[g, f]. Now g ⪯ f gives us f = g. This finishes our proof.

Remark. If f and g are n-ary partial functions on a set A, then f ⪯ g simply means dom f ⊆ dom g, and f ∼ g means dom f = dom g.

In the case of total clones, every abstract clone is isomorphic to some concrete clone. This is no longer true in the partial case. According to 2.3 we can describe every abstract partial clone as a subdirect product of concrete clones. But we can give an example of a partial clone which is not isomorphic to any concrete clone.

Example. Let |A| = 1. Consider the full partial clone \underline{Par}(A) on A. For every arity n ∈ Np, this clone contains exactly two functions — the empty function (with empty domain) and the (unique) total n-ary function. Therefore |Par^{(n)}(A)| = 2 for all n ∈ Np. Now let \underline{C} := \underline{Par}(A) × \underline{Par}(A). Then \underline{C} is again an abstract partial clone. (Abstract partial clones are defined by identities, therefore they form a variety of many sorted algebras.) We have |C_{n}| = |Par^{(n)}(A) × Par^{(n)}(A)| = 4 for all n ∈ Np. \underline{C} cannot be isomorphic to a concrete partial clone. If |B| = 1, then |C_{n}| = 4 > |Par^{(n)}(B)|, hence \underline{C} is not isomorphic to a subclone of \underline{Par}(B). But if |B| > 1, then Par^{(n)}(B) contains at least n different elements, namely the projections e_{i,B}^{n} for i = 1 … n. (The projections belong to every subclone of \underline{Par}(B).) Consequently every concrete clone on B contains at least n elements of arity n. Therefore \underline{C} is not isomorphic to a concrete partial clone.

If C = (C_{n})_{n∈Np} and D = (D_{n})_{n∈Np} are Np-sorted families of sets, and if D_{n} ⊆ C_{n} for all n ∈ Np, then we write D ⊆ C , and f ∈ D means f ∈ D_{n} for some n ∈ Np. To denote, that \underline{D} is a subclone of \underline{C} , we write \underline{D} ≤ \underline{C}. If the sets C_{n} are pairwise disjoint and F ⊆ ⋃{C_{n} | n ∈ Np}, then we also write F ⊆ C instead of (F_{n})_{n∈Np} ⊆ C, where F_{n} := F ∩ C_{n}. Please note that Par^{(n)}(A) ∩ Par^{(m)}(A) = ∅ if n ≠ m. (Even the n-ary and m-ary functions with empty domain are distinct, because they have different source objects). Therefore in the case of concrete partial clones we sometimes identify a subset F of Par(A) with the subfamily (F ∩ Par^{(n)}(A))_{n∈Np} of Par(A).

Definition 2.4 Let \underline{C} be a partial clone with carrier family C and let F be a subfamily of C. The clone, generated by F is the smallest subclone of \underline{C} containing F. It will be denoted with:

\underline{clone}\underline{C} (F) := ⋂\{\underline{D} | F ⊆ \underline{D} ≤ \underline{C}\}

The family F is called a generating system for \underline{clone}\underline{C} (F). If \underline{C} is a concrete clone with \underline{C} ≤ \underline{Par}(A), then we write \underline{clone}_{A} (F) instead of \underline{clone}\underline{C} (F). The carrier family of \underline{clone}\underline{C} (F) (of

\underline{clone}_{A} (F) resp.) will be denoted with clone\underline{C} (F) = (clone\underline{C}^{(n)}(F))_{n∈Np} (with clone_{A} (F) =

(clone_{A} ^{(n)}(F))_{n∈Np} resp.).

Lemma 2.5 Let \underline{C} be a partial clone, and let F = (F_{n})_{n∈Np} be a subfamily of its carrier C. For all n ∈ Np we define by induction on k ∈ N:

D_{0}^{(n)} := F_{n} ∪ {e_{i}^{n} | 1 ≤ i ≤ n}
D_{k+1}^{(n)} := {f[f_{1}, …, f_{m}] | m ∈ Np and f ∈ D_{0}^{(m)} and f_{1}, …, f_{m} ∈ D_{k}^{(n)}}
D^{(n)} := ⋃_{k∈N} D_{k}^{(n)}
D := (D^{(n)})_{n∈Np}

Then D = clone\underline{C} (F).

Proof. Obviously F ⊆ D, and it is also clear that every subclone of \underline{C} which contains F also has to contain D. To prove our Lemma, we have to show that D is a subclone by itself.

But D contains all projections. Therefore we only have to show that D is closed under superposition. To show this, it suffices to show that for all k ∈ N, n, m ∈ Np, g ∈ D_{k}^{(n)} and all g_{1}, …, g_{n} ∈ D^{(m)} also g[g_{1}, …, g_{n}] ∈ D^{(m)}. We prove this by induction on k.

First we mention that f ∈ D_{k}^{(n)} implies f =^{(3)} e_{1}^{1}[f] ∈ D_{k+1}^{(n)}, therefore D_{k}^{(n)} ⊆ D_{k+1}^{(n)}. If now g_{1}, …, g_{n} ∈ D^{(m)}, then there has to exist an l ∈ N such that g_{1}, …, g_{n} ∈ D_{l}^{(m)}. Now let us start our induction with k = 0. Let g ∈ D_{0}^{(n)} and let g_{1}, …, g_{n} ∈ D_{l}^{(m)}. Then by the definition of D_{l+1}^{(m)} we have g[g_{1}, …, g_{n}] ∈ D_{l+1}^{(m)} ⊆ D^{(m)}.

Now let us assume that our induction hypothesis is true for k and consider g ∈ D_{k+1}^{(n)}. By definition g = g_{0}[f_{1}, …, f_{j}] with g_{0} ∈ D_{0}^{(j)} for some j ∈ Np and f_{1}, ...f_{j} ∈ D_{k}^{(n)}. For g_{1}, …, g_{n} ∈ D_{l}^{(m)} we have:

g[g_{1}, …, g_{n}] = (g_{0}[f_{1}, …, f_{j}])[g_{1}, …, g_{n}]
=^{(1)} g_{0}[f_{1}[g_{1}, …, g_{n}], …, f_{j}[g_{1}, …, g_{n}]]

But f_{1}, …, f_{j} ∈ D_{k}^{(n)}, and therefore by our induction hypothesis we have:

f_{1}[g_{1}, …, g_{n}], …, f_{j}[g_{1}, …, g_{n}] ∈ D^{(m)}

And now g_{0} ∈ D_{0}^{(j)} implies as in the start of the induction, that g[g_{1}, …, g_{n}] ∈ D^{(m)}. This finishes our induction. Consequently D is the smallest subclone containing F.

We can use this Lemma to give inductive proofs for properties of functions in a partial clone. But sometimes it is better to use the following corollary.

Corollary 2.6 Let \underline{C} be a partial clone and let F = (F_{n})_{n∈Np}, M = (M_{n})_{n∈Np} and let F, M ⊆ C such that for all n, m ∈ Np:

(i) F ⊆ M and {e_{i}^{n} | 1 ≤ i ≤ n} ⊆ M_{n}. (ii) For all i = 1, …, n and all g_{1}, …, g_{n} ∈ M_{m} one has e_{i}^{n}[g_{1}, …, g_{n}] ∈ M_{m}. (iii) For all f ∈ F_{n} and all g_{1}, …, g_{n} ∈ M_{m} one has f[g_{1}, …, g_{n}] ∈ M_{m}. Then we have: clone\underline{C} (F) ⊆ M

Proof. We use Lemma 2.5 and prove by induction that the sets D_{k}^{(n)} (notation of 2.5) are in M_{n}. For D_{0}^{(n)} this is clear because of (i). But if D_{k}^{(n)} ⊆ M_{n}, then by (ii) and (iii) also D_{k+1}^{(n)} ⊆ M_{n}. Now by Lemma 2.5 we have clone\underline{C} (F) ⊆ M.

3. Partial Algebras

In this section we introduce our main notations. If we talk about partial algebras, then we have many possibilities to define homomorphisms, subalgebras and different kinds of products. An extended overview on such notions can be found in Burmeister [5]. We also want to refer to [21] for a general treatment of partial algebras. For other features, like the one-point extension or strong regular varieties of partial algebras, we refer to [19], [13], [14].

In the present paper we introduce only the notions necessary for our aim — the definition of a “variety of partial algebras”. As mentioned in the introduction, we want to define this notion in strong connection with the notion of a partial clone. To avoid some technical difficulties, we consider only partial functions with positive arities. Nullary constants can be replaced by constant unary (total or empty) functions. Furthermore we restrict ourselves to algebras with nonempty carrier sets.

A type τ is a pair τ := (Ψ, α), where Ψ is a set of symbols and α is a (total) map α : Ψ → Np, assigning to each ψ ∈ Ψ an arity α(ψ) ∈ Np.

Definition 3.1 (i) A partial algebra A of type τ and with carrier-set A ≠ ∅ is a pair

A := ⟨A ; (f_{ψ}^{A})_{ψ∈Ψ} ⟩ ,

where f_{ψ}^{A} ∈ Par^{(α(ψ))}(A) for all ψ ∈ Ψ. (ii) A τ-clone is a pair

\underline{C}^{τ} := (\underline{C} ; (g_{ψ})_{ψ∈Ψ}) ,

where 1. \underline{C} is an abstract partial clone (with carrier-family (C_{n})_{n∈Np}),

2. g_{ψ} ∈ C_{α(ψ)} for all ψ ∈ Ψ and

3. the family G = (G_{n})_{n∈Np} with G_{n} := {g_{ψ} | ψ ∈ Ψ and α(ψ) = n} is a generating system for \underline{C}.

(iii) If A = ⟨A ; (f_{ψ}^{A})_{ψ∈Ψ} ⟩ is a partial algebra, then we define:

\underline{clone} A := \underline{clone}_{A} (\{f_{ψ}^{A} | ψ ∈ Ψ and α(ψ) = n\})_{n∈Np}
\underline{clone}^{τ} A := (\underline{clone} A ; (f_{ψ}^{A})_{ψ∈Ψ})

The carrier family of \underline{clone} A is denoted with clone A. (iv) The trivial algebra of type τ is the following one-element algebra:

S(τ) := ⟨{∅}; (f_{ψ}^{S(τ)})_{ψ∈Ψ}⟩  with
f_{ψ}^{S(τ)} : {∅}^{α(ψ)} → {∅}
(∅, …, ∅) ↦ ∅

In the following we will assume, that τ is an arbitrary but fixed type. All our algebras and varieties are assumed to be of this type. Now we are able to define our main notion.

Definition 3.2 Let \underline{C}^{τ} = (\underline{C} ; (g_{ψ})_{ψ∈Ψ}) be a τ-clone. The partial variety, belonging to \underline{C}^{τ} is the following class of partial algebras of type τ:

pVar(\underline{C}^{τ}) := \{ ⟨A ; ( γ(g_{ψ}) )_{ψ∈Ψ} ⟩ | A is a nonempty set
and γ : \underline{C} → \underline{Par}(A) is a clone homomorphism \}

A class K of partial algebras of type τ is called a variety of partial algebras — or shorter a partial variety — if K = pVar(\underline{C}^{τ}) for some τ-clone \underline{C}.

The usual notion of a homomorphism between partial algebras ([5], [21]) is too weak for our purposes. What we need is called in [5] a closed homomorphism.

Definition 3.3 ([5, Definition 2.4.2.(ii)]) Let A = ⟨A ; (f_{ψ}^{A})_{ψ∈Ψ} ⟩ and B = ⟨B ; (f_{ψ}^{B})_{ψ∈Ψ} ⟩ be partial algebras. A total (!) map h : A → B is called a closed homomorphism from A into B, denoted with h : A → B, if for all ψ ∈ Ψ

(a_{1}, …, a_{α(ψ)}) ∈ dom f_{ψ}^{A} ⇔ (h(a_{1}), …, h(a_{α(ψ)})) ∈ dom f_{ψ}^{B} ,

and if for all (a_{1}, …, a_{α(ψ)}) ∈ dom f_{ψ}^{A}:

h(f_{ψ}^{A}(a_{1}, …, a_{α(ψ)})) = f_{ψ}^{B}(h(a_{1}), …, h(a_{α(ψ)}))

If the closed homomorphism h : A → B is bijective, then h^{−1} : B → A is also a closed homomorphism and we call h an isomorphism between A and B. If such an isomorphism exists, then we say that A and B are isomorphic, and we write A ≅ B.

Definition 3.4 Let A = ⟨A ; (f_{ψ}^{A})_{ψ∈Ψ} ⟩ and B = ⟨B ; (f_{ψ}^{B})_{ψ∈Ψ} ⟩ be partial algebras and let B ⊆ A. If B is closed under f_{ψ}^{A} and f_{ψ}^{B} = f_{ψ}^{A}|_{B} for all ψ ∈ Ψ, then B is called a subalgebra of A, and we write B ≤ A. If K is a class of partial algebras (of the same type τ), then we put:

S K := {B | B ≤ A for some A ∈ K}

If K = S K, then we call K closed under S .

Remark. If B ⊆ A, then B ≤ A iff the natural embedding h : B ↪ A is a closed homomorphism.

Lemma 3.5 Let A = ⟨A ; (f_{ψ}^{A})_{ψ∈Ψ} ⟩ and B = ⟨B ; (f_{ψ}^{B})_{ψ∈Ψ} ⟩ be partial algebras and let h : A → B be a closed homomorphism. Then the set h(A) := range h is a closed subset for the functions f_{ψ}^{B} with ψ ∈ Ψ. The algebra

h(A) := ⟨h(A) ; (f_{ψ}^{B}|_{h(A)})_{ψ∈Ψ} ⟩

is a subalgebra of B. If h is an injective map, then A ≅ h(A).

Proof. If α(ψ) = n and (b_{1}, …, b_{n}) ∈ h(A)^{n} ∩ dom f_{ψ}^{B} then there are a_{1}, …, a_{n} ∈ A with b_{i} = h(a_{i}), and by the properties of a closed homomorphism we have (a_{1}, …, a_{n}) ∈ dom f_{ψ}^{A}. Therefore f_{ψ}^{B}(b_{1}, …, b_{n}) = h(f_{ψ}^{A}(a_{1}, …, a_{n})) ∈ h(A). So h(A) is a closed subset of B, and consequently h(A) is a subalgebra of B. If h is injective, then the function h′ : A → h(A), a ↦ h(a) is a bijective closed homomorphism, i.e. an isomorphism between A and h(A).

Definition 3.6 The algebra h(A) in Lemma 3.5 is called the image of the closed homomorphism h. If K is a class of partial algebras (of the same type τ), then we put:

H_{c} K := {h(A) | A ∈ K and h : A → B is a closed

homomorphism into some partial algebra B}

If K = H_{c} K, then we call K closed under H_{c}.

Lemma 3.7 Every partial variety is closed under H_{c}.

Proof. Let A = ⟨A ; (f_{ψ}^{A})_{ψ∈Ψ} ⟩ ∈ pVar(\underline{C}^{τ}) , \underline{C}^{τ} = (\underline{C} ; (g_{ψ})_{ψ∈Ψ} ) and let h : A → B = ⟨B ; (f_{ψ}^{B})_{ψ∈Ψ} ⟩ be a surjective closed homomorphism, i.e. h(A) = B. Then there exists a clone-homomorphism γ : \underline{C} → \underline{clone} A such that f_{ψ}^{A} = γ(g_{ψ}) for all ψ ∈ Ψ. If we find a clone homomorphism δ : \underline{clone} A → \underline{Par}(B) with f_{ψ}^{B} = δ(f_{ψ}^{A}), then the composition δ ∘ γ : \underline{C} → \underline{Par}(B) is a clone homomorphism with f_{ψ}^{B} = δ(γ(g_{ψ})), and this will show B ∈ pVar(\underline{C}^{τ}).

So let f ∈ clone A be an n-ary partial function, and let (a_{1}, …, a_{n}), (a′_{1}, …, a′_{n}) ∈ A^{n}. First we want to show:

if (a_{1}, …, a_{n}) ∈ dom f and h(a_{i}) = h(a′_{i}) for all i = 1, …, n , then
(a′_{1}, …, a′_{n}) ∈ dom f and h(f(a_{1}, …, a_{n})) = h(f(a′_{1}, …, a′_{n}))  (12)

This can be easily checked for the projections, and by the Definition 3.3 of a closed homomorphism it is also true for the functions f_{ψ}^{A}. Now we can use Corollary 2.6 to assure that (12) is true for all f ∈ clone A: The set {f_{ψ} | ψ ∈ Ψ} is a generating system for clone A. We choose M (notation of 2.6) to be the family of all f ∈ clone A with (12). Then the projections and the functions f_{ψ}^{A} are in M. If (12) is true for g_{1}, …, g_{n} ∈ M_{m}, and if α(ψ) = n and (a_{1}, …, a_{m}) ∈ dom (f_{ψ}^{A} ∘ [g_{1}, …, g_{n}]) with h(a_{i}) = h(a′_{i}) for all i = 1, …, m, then:

(a_{1}, …, a_{m}) ∈ dom g_{i} ⇒ (a′_{1}, …, a′_{m}) ∈ dom g_{i} and
h(g_{i}(a_{1}, …, a_{m})) = h(g_{i}(a′_{1}, …, a′_{m}))
h((f_{ψ}^{A} ∘ [g_{1}, …, g_{n}])(a_{1}, …, a_{m})) = h(f_{ψ}^{A}(g_{1}(a_{1}, …, a_{m}), …, g_{n}(a_{1}, …, a_{m})))
=^{(hom)} f_{ψ}^{B}(h(g_{1}(a_{1}, …, a_{m})), …, h(g_{n}(a_{1}, …, a_{m})))
= f_{ψ}^{B}(h(g_{1}(a′_{1}, …, a′_{m})), …, h(g_{n}(a′_{1}, …, a′_{m})))
=^{(hom)} h(f_{ψ}^{A}(g_{1}(a′_{1}, …, a′_{m}), …, g_{n}(a′_{1}, …, a′_{m})))

Consequently (a′_{1}, …, a′_{m}) ∈ dom (f_{ψ}^{A} ∘ [g_{1}, …, g_{n}]) and

h((f_{ψ}^{A} ∘ [g_{1}, …, g_{n}])(a_{1}, …, a_{m})) = h((f_{ψ}^{A} ∘ [g_{1}, …, g_{n}])(a′_{1}, …, a′_{m})) .

Therefore by Lemma 2.6 we have (12) for all f ∈ clone A.

The property (12) implies for all f_{1}, …, f_{n} ∈ clone^{(m)}A:

{(h(a_{1}), …, h(a_{m})) | (a_{1}, …, a_{m}) ∈ ⋂_{i=1,...,n} dom f_{i}}

= ⋂_{i=1,...,n}{(h(a_{1}), …, h(a_{m})) | (a_{1}, …, a_{m}) ∈ dom f_{i}}  (13)

Furthermore (12) assures, that for f ∈ clone^{(n)}A the following definition of a partial function δ(f) ∈ Par^{(n)}(B) is correct:

δ(f) : B^{n} ∘→ B
dom δ(f) := {(h(a_{1}), …, h(a_{n})) | (a_{1}, …, a_{n}) ∈ dom f}
(h(a_{1}), …, h(a_{n})) ↦ h(f(a_{1}, …, a_{n}))

It is easy to check that δ(e_{i,A}^{n}) = e_{i,B}^{n} ∈ clone B. (Here we need the surjectivity of h ). Furthermore the properties of a closed homomorphism imply δ(f_{ψ}^{A}) = f_{ψ}^{B} ∈ clone B for all ψ ∈ Ψ.

We have to compare δ(f ∘ [f_{1}, …, f_{n}]) and δ(f) ∘ [δ(f_{1}), …, δ(f_{n})]. Again we use Corollary 2.6. Let M be the family of all functions f ∈ clone A such that

δ(f ∘ [f_{1}, …, f_{n}]) = δ(f) ∘ [δ(f_{1}), …, δ(f_{n})]  (14)

for all m ∈ Np and all f_{1}, …, f_{n} ∈ clone^{(m)}A. First let f = e_{i,A}^{n}. Then

dom δ(e_{i,A}^{n} ∘ [f_{1}, …, f_{n}]) =^{(13)} dom δ(e_{i,A}^{n}) ∘ [δ(f_{1}), …, δ(f_{n})] ,

and it is easy to check, that e_{i,A}^{n} ∈ M_{n}.

Now let us consider the case f = f_{ψ}^{A} with α(ψ) = n. We have to compare the two functions δ(f_{ψ}^{A} ∘ [f_{1}, …, f_{n}]) and δ(f_{ψ}^{A}) ∘ [δ(f_{1}), …, δ(f_{n})] for f_{1}, …, f_{n} ∈ clone^{(m)}A. The homomorphism h is surjective and therefore every \underline{b} ∈ B^{m} has the form \underline{b} = h(\underline{a}) = (h(a_{1}), …, h(a_{m})) for some \underline{a} = (a_{1}, …, a_{m}) ∈ A^{m}. Now we have:

h(\underline{a}) ∈ dom δ(f_{ψ}^{A}) ∘ [δ(f_{1}), …, δ(f_{n})]
⇔ h(\underline{a}) ∈ ⋂_{i=1...n} dom δ(f_{i}) and (δ(f_{1})(h(\underline{a})), …, δ(f_{n})(h(\underline{a}))) ∈ dom δ(f_{ψ}^{A})
⇔ h(\underline{a}) ∈ ⋂_{i=1...n}\{h(\underline{a′}) | \underline{a′} ∈ dom f_{i}\} and (h(f_{1}(\underline{a})), …, h(f_{n}(\underline{a}))) ∈ dom f_{ψ}^{B}
⇔^{(13)} \underline{a} ∈ ⋂_{i=1...n} dom f_{i} and (h(f_{1}(\underline{a})), …, h(f_{n}(\underline{a}))) ∈ dom f_{ψ}^{B}
⇔ \underline{a} ∈ ⋂_{i=1...n} dom f_{i} and (f_{1}(\underline{a}), …, f_{n}(\underline{a})) ∈ dom f_{ψ}^{A}
⇔ \underline{a} ∈ dom f_{ψ}^{A}[f_{1}, …, f_{n}]
⇔ h(\underline{a}) ∈ dom δ(f_{ψ}^{A}[f_{1}, …, f_{n}])

Consequently our functions have the same domain. Using the definition of δ, it is easy to check that they are equal. Therefore the projections and the functions f_{ψ}^{A} belong to M. To do the induction step, let f = e_{i,A}^{k} or f = f_{ψ}^{A} with α(ψ) = k and let g_{1}, …, g_{k} ∈ M_{n}. We have to show, that f[g_{1}, …, g_{k}] ∈ M_{n}. So let f_{1}, …, f_{n} ∈ clone^{(m)}A, and take into account that f itself is in M.

δ((f[g_{1}, …, g_{k}])[f_{1}, …, f_{n}]) =^{(1)} δ(f[g_{1}[f_{1}, …, f_{n}], …, g_{k}[f_{1}, …, f_{n}]])
= δ(f) [δ(g_{1}[f_{1}, …, f_{n}]), …, δ(g_{k}[f_{1}, …, f_{n}])]
= δ(f) [δ(g_{1})[δ(f_{1}), …, δ(f_{n})], …, δ(g_{k})[δ(f_{1}), …, δ(f_{n})]]
=^{(1)} (δ(f)[δ(g_{1}), …, δ(g_{k})])[δ(f_{1}), …, δ(f_{n})]
= δ(f[g_{1}, …, g_{k}])[δ(f_{1}), …, δ(f_{n})]

But then f[g_{1}, …, g_{k}] also has the M-property, and by 2.6 we have clone A ⊆ M. This implies that δ is a clone homomorphism and finishes the proof.

Lemma 3.8 Every partial variety is closed under S .

Proof. Let A ∈ pVar(\underline{C}^{τ}) and let B be a subalgebra of A. Similar to the proof of Lemma 3.7 it is enough to find a clone homomorphism δ : \underline{clone} A → \underline{Par}(B) with f_{ψ}^{B} = δ(f_{ψ}^{A}) for all ψ ∈ Ψ. First we show that B is closed for all functions f ∈ clone A. So let M be the family of all partial functions on A for which B is a closed set. Obviously M contains the projections, and — because B is a subalgebra of A — the functions f_{ψ}^{A} are also in M. If f_{1}, …, f_{n} ∈ M and α(ψ) = n, then B is also closed under f_{ψ}^{A} ∘ [f_{1}, …, f_{n}]. Therefore by 2.6 we have clone A ⊆ M.

Now we can define:

δ : \underline{clone} A → \underline{Par}(B)
δ(f) := f|_{B}

It follows immediately that δ(e_{i,A}^{n}) = e_{i,B}^{n} and that δ(f_{ψ}^{A}) = f_{ψ}^{B}. To show that δ is a clone homomorphism we still have to compare (f ∘ [f_{1}, …, f_{n}])|_{B} and f|_{B} ∘ [f_{1}|_{B}, …, f_{n}|_{B}]. The equality follows in a straightforward way from the definitions of restriction and superposition. Therefore δ is a clone homomorphism. This proves the Lemma.

Another construction element are products of partial algebras. First we introduce the basic notion.

Definition 3.9 Let I be an index set and let A_{i} = ⟨A_{i} ; (f_{ψ}^{A_{i}})_{ψ∈Ψ}⟩ be partial algebras of the same type τ. The direct product of the algebras A_{i} is the algebra

∏_{ı∈I} A_{i} := B = ⟨B ; (f_{ψ}^{B})_{ψ∈Ψ}⟩ ,

where B := ∏_{i∈I} A_{i} is the direct product of the sets A_{i} and f_{ψ}^{B} is the following function:

f_{ψ}^{B} := ∏_{i∈I} f_{ψ}^{A_{i}} : B^{n} ∘→ B  (n := α(ψ))
dom f_{ψ}^{B} := {((a_{1,i})_{i∈I}, …, (a_{n,i})_{i∈I}) ∈ B^{n} |
(a_{1,i}, …, a_{n,i}) ∈ dom f_{ψ}^{A_{i}} for all i ∈ I}
((a_{1,i})_{i∈I}, …, (a_{n,i})_{i∈I}) ↦ (f_{ψ}^{A_{i}}(a_{1,i}, …, a_{n,i}))_{i∈I}

(If I = {1, 2}, then we write A_{1} × A_{2} instead of ∏_{i∈{1,2}} A_{i}.)

If A = ⟨A ; (f_{ψ}^{A})_{ψ∈Ψ}⟩ is a partial algebra and M is a set, then (in accordance with the former definition) we let A^{M} be the algebra:

A^{M} := ⟨A^{M} ; (f_{ψ}^{A^{M}})_{ψ∈Ψ}⟩

Here A^{M} is the set of all total functions d : M → A, and the functions f_{ψ}^{A^{M}} are defined as follows:

f_{ψ}^{A^{M}} : (A^{M})^{n} ∘→ A^{M}  (n = α(ψ))
dom f_{ψ}^{A^{M}} := {(d_{1}, …, d_{n}) ∈ (A^{M})^{n} |
(d_{1}(m), …, d_{n}(m)) ∈ domf_{ψ}^{A} for all m ∈ M}
(d_{1}, …, d_{n}) ↦ f_{ψ}^{A} ∘ [d_{1}, …, d_{n}]

If M = ∅, then A^{∅} is an algebra with a one-element carrier set (containing only the empty function). The f_{ψ}^{A^{∅}} are total α(ψ)-ary functions. Therefore this algebra is isomorphic to the trivial algebra S(τ) (3.1(iv)).

Remark. As in the case of total algebras, we can consider partial varieties as categories: Objects are the partial algebras, and the morphisms are the closed (!) homomorphisms. But in this category we miss the nice properties of varieties of total algebras. The direct product of partial algebras is not a product in the category theoretical sense. The natural projection from A × B to A or B is in general not a closed homomorphism.

We still need another notion of a product for partial algebras — the filtered (or reduced) product — see [5, 4.5.3]. Consider nonempty sets A_{i} with i ∈ I and let F be a filter on the index set I. (See e.g. [5, 4.5.2.].) As in the case of total algebras, we can define an equivalence relation θ_{F} on ∏_{i∈I} A_{i}, namely:

(a_{i})_{i∈I} θ_{F} (b_{i})_{i∈I} :⇔ {i ∈ I | a_{i} = b_{i}} ∈ F

If we consider a fixed filter F, then for \underline{a} = (a_{i})_{i∈I} we denote with ˆ \underline{a} := \underline{a}/θ_{F} the equivalence class of θ_{F} which contains \underline{a}. We write

∏_{i∈I} |F A_{i} := \{ˆ\underline{a} | \underline{a} ∈ ∏_{i∈I} A_{i}\}

for the filtered (or reduced) product of the sets A_{i}.

If f_{i} : A_{i}^{n} ∘→ A_{i} are n-ary functions on the sets A_{i}, then we can define a partial function f on the filtered product. First, using the axiom of choice, we can choose a fixed element \underline{c} = (c_{i})_{i∈I} ∈ ∏_{i∈I} A_{i}.

f : ( ∏_{i∈I} |F A_{i})^{n} ∘→ ∏_{i∈I} |F A_{i}
dom f := \{(ˆ\underline{a}_{1}, …, ˆ \underline{a}_{n}) | \{i ∈ I | (a_{i,1}, …, a_{i,n}) ∈ dom f_{i}\} ∈ F\}
(ˆ\underline{a}_{1}, …, ˆ \underline{a}_{n}) ↦ ˆ \underline{b} = ˆ (b_{i})_{i∈I}, with b_{i} = \{ \begin{matrix}f_{i}(a_{i,1}, …, a_{i,n}) & if (a_{i,1}, …, a_{i,n}) ∈ dom f_{i} \\ c_{i} & else \end{matrix}

The filter properties of F assure, that this definition is correct and independent from the choice of \underline{c}. We denote this function by ∏_{i∈I} |F f_{i} and call it the filtered product of the functions f_{i}.

Definition 3.10 Let I be a nonempty index set and let

A_{i} = ⟨A_{i} ; (f_{ψ}^{A_{i}})_{ψ∈Ψ}⟩

be partial algebras of the same type τ. Furthermore let F be a filter on I. The filtered product (or reduced product) of the algebras A_{i} is the algebra:

∏_{i∈I} |F A_{i} := ⟨∏_{i∈I} |F A_{i} ; ( ∏_{i∈I} |F f_{ψ}^{A_{i}})_{ψ∈Ψ}⟩

If K is a class of partial algebras (of the same type τ), then we put:

Pfilt K := { ∏_{i∈I} |F A_{i} | I ≠ ∅ is a set, F is a filter on I and A_{i} ∈ K for all i ∈ I}

If K = Pfilt K, then we call K closed under Pfilt .

Remark. If we choose the improper filter F = P(I), then ∏_{i∈I} |F A_{i} is isomorphic to the trivial algebra S(τ).

Remark. The direct product in Definition 3.9 can be considered as a special case of the filtered product. (We have to choose the filter F = {I}.)

Lemma 3.11 Every partial variety is closed under Pfilt .

Proof. Let \underline{C}^{τ} be a τ-clone. We have to prove, that pVar(\underline{C}^{τ}) is closed under filtered products. So let I ≠ ∅, and let F be a filter on I.

For i ∈ I let A_{i} ∈ K = pVar(\underline{C}^{τ}), where \underline{C}^{τ} = (\underline{C} ; (g_{ψ})_{ψ∈Ψ}), and let

A = ⟨A ; (f_{ψ}^{A})_{ψ∈Ψ}⟩ := ∏_{i∈I} |F A_{i} .

Then there are clone homomorphisms γ_{i} : \underline{C} → \underline{clone} A_{i} with γ_{i}(g_{ψ}) = f_{ψ}^{A_{i}} for all ψ ∈ Ψ. We define a function γ : \underline{C} → \underline{Par}(A), g ↦ ∏_{i∈I} |F γ_{i}(g). By Definition 3.10 we have γ(g_{ψ}) = f_{ψ}^{A}

for all ψ ∈ Ψ and it is easy to check that γ(e_{k}^{n}) = ∏_{i∈I} |F e_{k,A_{i}}^{n} = e_{k,A}^{n} for 1 ≤ k ≤ n ∈ Np. So we

only have to show that γ(g_{0}[g_{1}, …, g_{n}]) = γ(g_{0})[γ(g_{1}), …, γ(g_{n})] for all g_{0} ∈ C_{n}, g_{1}, … g_{n} ∈ C_{m}. Then γ : \underline{C} → \underline{clone} A is a clone homomorphism.

So let (ˆ\underline{a}_{1}, …, ˆ \underline{a}_{m}) ∈ dom γ(g_{0}[g_{1}, …, g_{n}]) (with \underline{a}_{j} = (a_{i,j})_{i∈I}). This means, that

{i | (a_{i,1}, …, a_{i,m}) ∈ dom γ_{i}(g_{0}[g_{1}, …, g_{n}])} ∈ F.

The functions γ_{i} are clone homomorphisms, therefore this is the same set as

{i | (a_{i,1}, …, a_{i,m}) ∈ dom γ_{i}(g_{0})[γ_{i}(g_{1}), …, γ_{i}(g_{n})]} .

So this set is in F, and this in turn is equivalent with

(ˆ\underline{a}_{1}, …, ˆ \underline{a}_{m}) ∈ dom γ(g_{0})[γ(g_{1}), …, γ(g_{n})] .

It is an easy exercise to show that also the values are the same. Consequently γ is a clone homomorphism, and this shows A ∈ pVar(\underline{C}^{τ}).

4. Terms and Equations

In this section we want to introduce the notions of terms and equations. There are many ways to extend the equational logic for total functions to the partial case. We mention the papers [1], [2] and [5]. Here we need a concept which allows to find for every function in clone A a corresponding term. Therefore we are forced to introduce new symbols ε_{i}^{n} to describe the effect of the projections e_{i,A}^{n}. The resulting language was introduced and investigated under the name Eq(e) by W. Craig in [7]. (He used only a single new symbol e, which corresponds to our ε_{1}^{2}.) In this paper he also gives a sound and complete system of rules of derivation for Eq(e), based on five rules ([7, part II, section 7]). Here, in our article, we will derive all necessary rules and equations from corresponding clone-equations.

As before we assume that τ = (Ψ, α) is a fixed type and that all our partial algebras are of type τ. We start with the notion of a term.

Definition 4.1 Let X be a set of symbols such that X ∩ Ψ = ∅ and ε_{i}^{n} ∉ X ∪ Ψ for all 1 ≤ i ≤ n ∈ Np. We give an inductive definition for the notion of a term over X. At the same time we define occ (t), the set of variables, occuring in the term t.

1. If x ∈ X, then x is a term and occ (x) := {x}.

2. If 1 ≤ i ≤ n ∈ Np and t_{1}, … t_{n} are terms, then ε_{i}^{n}(t_{1}, …, t_{n}) is a term and we define occ (ε_{i}^{n}(t_{1}, …, t_{n})) := ⋃_{j=1...n} occ (t_{j}).

3. If ψ ∈ Ψ with α(ψ) = n ∈ Np and t_{1}, … t_{n} are terms, then ψ(t_{1}, …, t_{n}) is a term and

occ (ψ(t_{1}, …, t_{n})) := ⋃_{j=1...n} occ (t_{j}). A sequence of symbols is a term if and only if it is a term as a consequence of a finite number of applications of 1.–3. The set of all terms over X is denoted with pTerm(X).

This definition has to be understood in a purely syntactical sense - terms are only sequences of some symbols. To give a semantical interpretation, we have to define the validity of equations in partial algebras.

Definition 4.2 Let A = ⟨A ; (f_{ψ}^{A})_{ψ∈Ψ}⟩ be a partial algebra and let ϱ : X → A be a total function. Furthermore we assume that ∞ ∉ A. We follow the steps in Definition 4.1 and define a total function ϱ^{⋆} : pTerm(X) → A ∪ {∞}:

1. If t = x ∈ X then ϱ^{⋆}(t) := ϱ(x).

2. If t = ε_{i}^{n}(t_{1}, …, t_{n}), then:

ϱ^{⋆}(t) := \{ \begin{matrix}ϱ^{⋆}(t_{i}) & if ϱ^{⋆}(t_{1}), …, ϱ^{⋆}(t_{n}) ∈ A \\ ∞ & else \end{matrix}

3. If t = ψ(t_{1}, …, t_{n}), then:

ϱ^{⋆}(t) := \{ \begin{matrix}f_{ψ}^{A}(ϱ^{⋆}(t_{1}), …, ϱ^{⋆}(t_{n})) & if (ϱ^{⋆}(t_{1}), …, ϱ^{⋆}(t_{n})) ∈ dom f_{ψ}^{A} \\ ∞ & else \end{matrix}

An equation (over X) is a pair (s, t) ∈ pTerm(X) × pTerm(X). We say that the equation (s, t) holds in A or is valid in A — denoted with A ⊧ s ≈ t — if ϱ^{⋆}(s) = ϱ^{⋆}(t) for all ϱ : X → A. We say that the equation (s, t) holds in a class K of partial algebras (of the same type) — denoted with K ⊧ s ≈ t — if A ⊧ s ≈ t for all A ∈ K.

The set of all equations which hold in a class K is denoted with

pEq_{X}(K) := {(s, t) ∈ pTerm(X) × pTerm(X) | K ⊧ s ≈ t} .

If Γ ⊆ pTerm(X) × pTerm(X), then

pMod_{X}(Γ) := {A | A is a partial algebra and
A ⊧ s ≈ t for all (s, t) ∈ Γ}

is the class of all models of Γ.

Remark. This definition of the validity of an equation is known under the name “Kleene equality”.

We still have another important notion of validity for an equation.

Definition 4.3 Let \underline{C}^{τ} = (\underline{C} ; (g_{ψ})_{ψ∈Ψ}) be a τ-clone with carrier family (C_{n})_{n∈Np}. Furthermore let m ∈ Np and let μ : X → {1, …, m}. We define a function μ^{⋆} : pTerm(X) → C_{m}:

1. If t = x ∈ X, then μ^{⋆}(t) := e_{μ(x)}^{m} ∈ C_{m}.

2. If t = ε_{i}^{n}(t_{1}, …, t_{n}), then μ^{⋆}(t) := e_{i}^{n}[μ^{⋆}(t_{1}), …, μ^{⋆}(t_{n})] ∈ C_{m}.

3. If t = ψ(t_{1}, …, t_{n}), then μ^{⋆}(t) := g_{ψ}[μ^{⋆}(t_{1}), …, μ^{⋆}(t_{n})] ∈ C_{m}. An equation (s, t) is valid in \underline{C}^{τ} — denoted with \underline{C}^{τ} ⊧ s ≈ t — if μ^{⋆}(s) = μ^{⋆}(t) for all m ∈ Np and all μ : X → {1, …, m}.

The next Lemma connects the notions in 4.2 and 4.3.

Lemma 4.4 Let A be a partial algebra. For μ : X → {1, …, m} we can define a function μ^{⋆} : pTerm(X) → clone^{(m)} A as in Definition 4.3, and for ϱ : X → A we can define a function ϱ^{⋆} : pTerm(X) → A ∪ {∞} as in Definition 4.2.

(i) Let t ∈ pTerm(X) with occ (t) ⊆ {x_{1}, …, x_{m}} and let ϱ : X → A. Furthermore let μ : X → {1, …, m} be the function with μ(x_{j}) := j for j ∈ {1, …, m} and μ(x) := 1 for x ∉ {x_{1}, …, x_{m}}. Then ϱ^{⋆}(t) ∈ A iff (ϱ(x_{1}), …, ϱ(x_{m})) ∈ dom μ^{⋆}(t). If ϱ^{⋆}(t) ∈ A, then ϱ^{⋆}(t) = μ^{⋆}(t)(ϱ(x_{1}), …, ϱ(x_{m})).

(ii) Let t ∈ pTerm(X), and let μ : X → {1, …, m} be a total function. Furthermore, let (a_{1}, …, a_{m}) ∈ A^{m}. Define ϱ : X → A by ϱ(x) := a_{μ(x)}. Then (a_{1}, … a_{m}) ∈ dom μ^{⋆}(t) iff ϱ^{⋆}(t) ∈ A, and in this case we have μ^{⋆}(t)(a_{1}, …, a_{m}) = ϱ^{⋆}(t).

Proof. We prove (i) and (ii) by induction on the structure of t.

(i) If t = x_{j} (j ∈ {1, …, m}), then we have:

ϱ^{⋆}(t) = ϱ(x_{j}) = e_{j,A}^{m}(ϱ(x_{1}), …, ϱ(x_{m})) = μ^{⋆}(x_{j})(ϱ(x_{1}), …, ϱ(x_{m})) ∈ A

If t has the form t = ε_{i}^{n}(t_{1}, …, t_{n}), and (i) is true for t_{1} … t_{n}, then

ϱ^{⋆}(t) ∈ A iff ϱ^{⋆}(t_{1}), …, ϱ^{⋆}(t_{n}) ∈ A,

and this is the case if and only if (ϱ(x_{1}), …, ϱ(x_{m})) ∈ ⋂_{k=1...n} dom μ^{⋆}(t_{k}) = dom μ^{⋆}(t). Then we have ϱ^{⋆}(t) = ϱ^{⋆}(t_{i}) = μ^{⋆}(t)(ϱ(x_{1}), …, ϱ(x_{m})). If t = ψ(t_{1}, …, t_{n}), and (i) is true for t_{1} … t_{n}, then ϱ^{⋆}(t) ∈ A iff (ϱ^{⋆}(t_{1}), …, ϱ^{⋆}(t_{n})) ∈ dom f_{ψ}^{A}, and this is equivalent to (ϱ(x_{1}), …, ϱ(x_{m})) ∈ dom (f^{A} ∘ [μ^{⋆}(t_{1}), …, μ^{⋆}(t_{n})]) = dom μ^{⋆}(t). It is obvious that then also ϱ^{⋆}(t) = μ^{⋆}(t)(ϱ(x_{1}), …, ϱ(x_{m})). This finishes the proof of (i).

(ii) If t = x ∈ X, then μ^{⋆}(t) = e_{μ(x),A}^{m}, a total function, and e_{μ(x),A}^{m}(a_{1}, …, a_{m}) = a_{μ(x)} = ϱ^{⋆}(x). If t has the form t = ε_{i}^{n}(t_{1}, …, t_{n}), and (ii) is true for all t_{1} … t_{n}, then (a_{1}, …, a_{m}) ∈ dom μ^{⋆}(t) iff (a_{1}, …, a_{m}) ∈ dom μ^{⋆}(t_{j}) for all j = 1, …, m. But this is equivalent with ϱ^{⋆}(t_{j}) ∈ A for all j = 1, … m, and this means ϱ^{⋆}(t) ∈ A. In this case we have ϱ^{⋆}(t) = ϱ^{⋆}(t_{i}) = μ^{⋆}(t_{i})(a_{1}, …, a_{m}) = μ^{⋆}(t)(a_{1}, …, a_{m}). If t = ψ(t_{1}, …, t_{n}), then (a_{1}, …, a_{m}) ∈ dom μ^{⋆}(t) iff (a_{1}, …, a_{m}) ∈ ⋂_{j=1...n} dom μ^{⋆}(t_{j}) and (μ^{⋆}(t_{1})(a_{1}, …, a_{m}), …, μ^{⋆}(t_{n})(a_{1}, …, a_{m})) ∈ dom f_{ψ}^{A}. But if our induction hypothesis holds for all t_{1} … t_{n}, then this is equivalent with ϱ^{⋆}(t_{j}) ∈ A for all j ∈ {1, …, n} and (ϱ^{⋆}(t_{1}), …, ϱ^{⋆}(t_{n})) ∈ dom f_{ψ}^{A}. This is equivalent with ϱ^{⋆}(t) ∈ A, and in this case we have ϱ^{⋆}(t) = μ^{⋆}(t)(a_{1}, …, a_{m}). This finishes the proof of (ii).

Lemma 4.5 An equation holds in a partial algebra A iff it holds in \underline{clone}^{τ} A.

Proof. This is a corollary of Lemma 4.4. Let us assume that A |̸= s ≈ t. Then there is a ϱ : X → A such that ϱ^{⋆}(s) ≠ ϱ^{⋆}(t). We can choose x_{1}, …, x_{m} such that occ (t) ∪ occ (s) ⊆ {x_{1}, …, x_{m}}. Then by 4.4 (i) there is a μ : X → {1, …, m} such that μ^{⋆}(s) ≠ μ^{⋆}(t). Consequently \underline{clone}^{τ} A |̸= s ≈ t.

Vice versa, if \underline{clone}^{τ} A |̸= s ≈ t, then there has to exist an m ∈ Np and a μ : X → {1, …, m} such that μ^{⋆}(s) ≠ μ^{⋆}(t). By 4.4 there exists an ϱ : X → A such that ϱ^{⋆}(s) ≠ ϱ^{⋆}(t), consequently also A |̸= s ≈ t.

Two more notions are very important for our developements. We use for them the usual definitions, which we do not repeat here. So we assume that the reader knows what it means

1. that a term t′ is a subterm of a term t, and

2. that a term s arises from a term t by replacing the subterm t′ of t by the term s′ (at

one or more places of its occurence in t). We make extensive use of these notions. In particular we will use the following lemma, which is given without a proof. (If we had defined “subterm” and “replacement” and “place of occurence”, then this would be an easy proof by induction on the structure of t.)

Lemma 4.6 Let A be a partial algebra and t, t′, s, s′ ∈ pTerm(X). Assume that t′ is a subterm of t and that s arises from t by replacing t′ at one or more places of its occurence by s′. Furthermore let A ⊧ s′ ≈ t′. Then A ⊧ s ≈ t.

In our article we have two kinds of terms and equations. The first kind is connected with partial clones, e.g. equations (1) - (7) in section 2, while the second kind is connected with partial algebras. It is important to distinguish between them sharply, they talk about different things and we should not mix them up. But nevertheless there are connections between them. If the terms in a clone equation have a special form, then we can derive some equations for partial algebras. The following Lemma will illustrate this connection.

Lemma 4.7 Let 1 ≤ i ≤ n ∈ Np, ψ ∈ Ψ with α(ψ) = n and let x ∈ X, s, t, u, t_{1}, …, t_{n} ∈ pTerm(X). The following equations hold in every τ-clone, in every partial algebra and in every class of partial algebras.

ε_{1}^{2}(s, s) ≈ s  (15)
ε_{1}^{2}(ε_{1}^{2}(s, t), u) ≈ ε_{1}^{2}(s, ε_{1}^{2}(t, u))  (16)
ε_{1}^{2}(ψ(t_{1}, …, t_{n}), t_{i}) ≈ ψ(t_{1}, …, t_{n}) for all i ∈ {1, …, n}  (17)
ε_{1}^{2}(ε_{1}^{2}(s, t), s) ≈ ε_{1}^{2}(s, t)  (18)
ψ(ε_{1}^{2}(t_{1}, s), …, ε_{1}^{2}(t_{n}, s)) ≈ ε_{1}^{2}(ψ(t_{1}, …, t_{n}), s)  (19)

Proof. Let m ∈ Np and μ : X → {1, …, m}. Then by Definition 4.3 we have μ^{⋆}(ε_{1}^{2}(s, s)) = e_{1}^{2}[μ^{⋆}(s), μ^{⋆}(s)] =^{(8)} μ^{⋆}(s). Therefore ε_{1}^{2}(s, s) ≈ s holds in every τ-clone and therefore (by Lemma 4.5) it also holds in every partial algebra and in every class of partial algebras.

Here we have used equation (8). Also the other equations can be proved in this manner, using some clone equations and Lemma 4.6. We give the corresponding clone-equations. For (16) use (5). For (17) we can use (11) in the form:

e_{1}^{2}[f[k_{1}, …, k_{n}], k_{i}] = f[k_{1}, …, k_{n}]

For (18) we can use (10). For the last equation we need a little bit more.

μ^{⋆}(ψ(ε_{1}^{2}(t_{1}, s) …, ε_{1}^{2}(t_{n}, s)))

≈^{(def)} f_{ψ}[e_{1}^{2}[μ^{⋆}(t_{1}), μ^{⋆}(s)], …, e_{1}^{2}[μ^{⋆}(t_{n}), μ^{⋆}(s)]]
≈^{(2)} f_{ψ}[μ^{⋆}(t_{1})[e_{1}^{2}[e_{1}^{m}, μ^{⋆}(s)], …, e_{1}^{2}[e_{m}^{m}, μ^{⋆}(s)]], …, μ^{⋆}(t_{n})[e_{1}^{2}[e_{1}^{m}, μ^{⋆}(s)], …, e_{1}^{2}[e_{m}^{m}, μ^{⋆}(s)]]]
≈^{(1)} (f_{ψ}[μ^{⋆}(t_{1}), …, μ^{⋆}(t_{n})])[e_{1}^{2}[e_{1}^{m}, μ^{⋆}(s)], …, e_{1}^{2}[e_{m}^{m}, μ^{⋆}(s)]]
≈^{(def)} μ^{⋆}(ψ(t_{1}, …, t_{n}))[e_{1}^{2}[e_{1}^{m}, μ^{⋆}(s)], …, e_{1}^{2}[e_{m}^{m}, μ^{⋆}(s)]]
≈^{(2)} e_{1}^{2}[μ^{⋆}(ψ(t_{1}, …, t_{n})), μ^{⋆}(s)]
≈^{(def)} μ^{⋆}(ε_{1}^{2}(ψ(t_{1}, …, t_{n}), s)

Lemma 4.8 Let X be a set and let Γ ⊆ pTerm(X)×pTerm(X). Then there exists a τ-clone \underline{C}^{τ} such that pVar(\underline{C}^{τ}) = pMod_{X}(Γ).

Proof. By Definition 2.2 the partial clones form a variety of total and heterogeneous algebras. Therefore there exists a free abstract clone \underline{D(Ψ)} with the free generating system (Ψ_{n})_{n∈Np},

where Ψ_{n} := \{ψ ∈ Ψ | α(ψ) = n\}. Then (\underline{D(Ψ)} ; (ψ)_{ψ∈Ψ}) is a τ-clone. Let D = (D_{n})_{n∈Np} be the carrier family of \underline{D(Ψ)}. Every μ : X → \{1, …, m\} generates as in Definition 4.3 a function μ^{⋆} : pTerm(X) → D_{m}. We define a binary relation ϕ_{m} ⊆ D_{m} × D_{m} by:

ϕ_{m} := {(μ^{⋆}(s), μ^{⋆}(t)) | (s, t) ∈ Γ and μ : X → {1, …, m} }

The family ϕ = (ϕ_{n})_{n∈Np} generates a congruence relation θ = (θ_{n})_{n∈Np} on \underline{D(Ψ)}. We put

\underline{C} := \underline{D(Ψ)}/θ, g_{ψ} := ψ/θ ∈ C_{α(ψ)} and \underline{C}^{τ} := (\underline{C} ; (g_{ψ})_{ψ∈Ψ}). All equations in Γ are valid in \underline{C}. If γ : \underline{C} → \underline{clone} A is a clone homomorphism with γ(g_{ψ}) = f_{ψ}^{A} for all ψ ∈ Ψ, then γ is surjective, and all equations which are valid in \underline{C}^{τ} also hold in \underline{clone}^{τ} A. By Lemma 4.5 they hold also in A and consequently A ∈ pMod_{X}(Γ). This implies:

pVar(\underline{C}^{τ}) ⊆ pMod_{X}(Γ)

Now let A ∈ pMod_{X}(Γ). The mapping ψ ↦ f_{ψ}^{A} can be extended to a clone homomorphism γ : \underline{D(Ψ)} → \underline{clone} A which is surjective because the f_{ψ}^{A} form a generating system for \underline{clone} A. The kernel ker (γ) of γ is a congruence on \underline{D(Ψ)} which has to contain the relation ϕ and therefore θ ⊆ ker (γ). But then there is a clone homomorphism

δ′ : \underline{D(Ψ)}/θ → \underline{D(Ψ)}/ker (γ)

and because of \underline{C} ≅ \underline{D(Ψ)}/θ and \underline{clone} A ≅ \underline{D(Ψ)}/ker (γ), there exists a surjective clone homomorphism

δ : \underline{C} → \underline{clone} A

with δ(g_{ψ}) = f_{ψ}^{A} for all ψ ∈ Ψ. But then A ∈ pVar(\underline{C}^{τ}) and this implies:

pMod_{X}(Γ) ⊆ pVar(\underline{C}^{τ})

This finishes our proof.

5. K-term algebras

If K is a class of partial algebras and X is a countable set, then K ⊆ pMod_{X}(pEq_{X}(K)). In this section we want to prove that equality holds, if K is closed under H_{c} , S and Pfilt . This will be done in three steps. First we construct some termalgebras, then we prove that they belong to K, and finally we will use these term algebras to construct the algebras in pMod_{X}(pEq_{X}(K)) as homomorphic images of algebras in K.

In the following let K be a fixed class of partial algebras of the same type τ, and let Y be an arbitrary nonempty set. With s ≈ t we abbreviate K ⊧ s ≈ t (for s, t ∈ pTerm(Y)) - consequently the relation ≈ is just pEq_{Y} (K).

Definition 5.1 We define two binary relations on pTerm(Y). For s, t ∈ pTerm(Y) we put:

s ⪯ t :⇔ ε_{1}^{2}(s, t) ≈ s
s ∼ t :⇔ s ⪯ t and t ⪯ s

For s ∈ pTerm(Y) we put:

˜s̃ := {t ∈ pTerm(Y) | s ≈ t}
s̃ := {t ∈ pTerm(Y) | s ∼ t}

Remark. Please note, that the definitions of ≈ and ∼ depend on the class K. Furthermore, we want to mention the analogy between these relations and corresponding notions in the proof of Theorem 2.3.

Lemma 5.2 (i) The relation ⪯ is a quasiorder (i.e. it is reflexive and transitive). (ii) The relations ∼ and ≈ are equivalence relations on the set pTerm(Y), and s̃ and ˜ s̃ are

the equivalence classes of ∼ and ≈, containing s. (iii) If s ≈ t, then s ∼ t.

Proof. The equations of Lemma 4.7 hold in every class of partial algebras, therefore we can use them together with the replacement property of Lemma 4.6. We refer to this property by writing (rep).

(i) ε_{1}^{2}(s, s) ≈^{(15)} s, i.e. s ⪯ s, consequently ⪯ is reflexive. If s ⪯ t and t ⪯ u, then

ε_{1}^{2}(s, u) ≈^{(rep)} ε_{1}^{2}(ε_{1}^{2}(s, t), u) ≈^{(16)} ε_{1}^{2}(s, ε_{1}^{2}(t, u)) ≈^{(rep)} ε_{1}^{2}(s, t) ≈ s, therefore s ⪯ u, i.e. it is

transitive. (ii) Obvious by (i) and by the definitions of ∼ and ≈.

(iii) If s ≈ t, then ε_{1}^{2}(s, t) ≈^{(rep)} ε_{1}^{2}(s, s) ≈^{(15)} s, i.e. s ⪯ t and similarly t ⪯ s, consequently s ∼ t.

Lemma 5.3 Let A ∈ pMod_{Y} (pEq_{Y} (K)), m ∈ Np and μ : Y → {1, …, m}. Then μ generates as in Definition 4.3 a function μ^{⋆} : pTerm(Y) → clone^{(m)}A. Now let s, t ∈ pTerm(Y). If s ⪯ t, then dom μ^{⋆}(s) ⊆ dom μ^{⋆}(t). If s ∼ t, then dom μ^{⋆}(s) = dom μ^{⋆}(t).

If ϱ : Y → A, then ϱ extends as in Definition 4.2 to a function ϱ^{⋆} : pTerm(Y) → A∪{∞}. Now let s, t ∈ pTerm(Y). If s ⪯ t, then ϱ^{⋆}(s) ∈ A ⇒ ϱ^{⋆}(t) ∈ A. If s ∼ t, then ϱ^{⋆}(s) ∈ A ⇔ ϱ^{⋆}(t) ∈ A.

Proof. If s ⪯ t, then by the definition of μ^{⋆} and because of ε_{1}^{2}(s, t) ≈ s we have μ^{⋆}(s) = μ^{⋆}(ε_{1}^{2}(s, t)) = e_{1,A}^{2}[μ^{⋆}(s), μ^{⋆}(t)]. So the domains of μ^{⋆}(s) and e_{1,A}^{2}[μ^{⋆}(s), μ^{⋆}(t)] have to be equal. This implies dom μ^{⋆}(s) ⊆ dom μ^{⋆}(t). The remaining part is obvious.

Definition 5.4 Let Y ≠ ∅ and let s ∈ pTerm(Y). Then T_{K}(Y, s) is the following set:

T_{K}(Y, s) := {˜t̃ | t ∈ s̃}

For ψ ∈ Ψ with α(ψ) = n we define an n-ary partial function f_{ψ}^{s} on T_{K}(Y, s):

f_{ψ}^{s} : T_{K}(Y, s)^{n} → T_{K}(Y, s)
dom f_{ψ}^{s} := {( ˜t̃_{1}, …, ˜ t̃_{n}) ∈ T_{K}(Y, s)^{n} | ψ(t_{1}, …, t_{n}) ∼ s}
( ˜t̃_{1}, …, ˜ t̃_{n}) ↦ ˜ ψ̃(t_{1}, …, t_{n})

The algebra

T_{K}(Y, s) := ⟨T_{K}(Y, s) ; (f_{ψ}^{s})_{ψ∈Ψ}⟩

is called the K-term algebra over Y, belonging to the term s.

Lemma 5.5 If K is closed under H_{c} , S and Pfilt , then T_{K}(Y, s) ∈ K for all sets Y ≠ ∅ and all terms s ∈ pTerm(Y).

Proof. Let I be an index set, and for i ∈ I let

m_{i} ∈ Np, μ_{i} : Y → {1, …, m_{i}}, A_{i} = ⟨A_{i} ; (f_{ψ}^{A_{i}})_{ψ∈Ψ}⟩ ∈ K.

As in Definition 4.3 the function μ_{i} generates a function μ_{i}^{⋆} : pTerm(Y) → clone^{(m_{i})}A_{i}. Then μ_{i}^{⋆}(s) is an m_{i}-ary partial function on A_{i}. By Lemma 5.3 we have dom μ_{i}^{⋆}(t) = dom μ_{i}^{⋆}(s) for

all ˜ t̃ ∈ T_{K}(Y, s). Now we can consider the algebra B_{i} := A_{i}^{dom μ_{i}^{⋆}(s)} (see Definition 3.9). The class K is closed under direct products, therefore B_{i} ∈ K. The carrier of this algebra is the set B_{i} := A_{i}^{dom μ_{i}^{⋆}(s)} of all total functions dom μ_{i}^{⋆}(s) → A_{i}. We define a (total ) function h_{i}.

h_{i} : T_{K}(Y, s) → B_{i}
˜t̃ ↦ h_{i}(˜t̃) : dom μ_{i}^{⋆}(s) → A_{i}, (a_{1}, …, a_{m_{i}}) ↦ μ_{i}^{⋆}(t)(a_{1}, …, a_{m_{i}})

The algebra A_{i} is in K, and therefore (Lemma 4.5) μ_{i}^{⋆}(t′) = μ_{i}^{⋆}(t) if t′ ≈ t — this assures that our definition of h_{i}(˜t̃) is correct. The function h_{i}(˜t̃) is the function μ_{i}^{⋆}(t), considered as a total function from its domain to A_{i}.

Now let B = ⟨B ; (f_{ψ}^{B})_{ψ∈Ψ}⟩ := ∏_{i∈I} B_{i}. The algebras B_{i} are in K and K is closed under direct products. Therefore B ∈ K. We define a (total) function h : T_{K}(Y, s) → B by

˜t̃ ↦ (h_{i}(˜t̃))_{i∈I}.

Let us assume that ( ˜t̃_{1}, …, ˜ t̃_{n}) ∈ dom f_{ψ}^{s}. This is equivalent with ψ(t_{1}, …, t_{n}) ∼ s. But then by Lemma 5.3 we have dom μ_{i}^{⋆}(s) = dom μ_{i}^{⋆}(ψ(t_{1}, …, t_{n})) = dom f_{ψ}^{A_{i}}[μ_{i}^{⋆}(t_{1}), …, μ_{i}^{⋆}(t_{n})]. But this implies that f_{ψ}^{A_{i}}[μ_{i}^{⋆}(t_{1}), …, μ_{i}^{⋆}(t_{n})] can be considered as a total function dom μ_{i}^{⋆}(s) → A_{i}, and this leads to (h_{i}( ˜t̃_{1}), …, h_{i}( ˜t̃_{n})) ∈ dom f_{ψ}^{B_{i}} for all i ∈ I. So ( ˜t̃_{1}, …, ˜ t̃_{n}) ∈ dom f_{ψ}^{s} implies (h_{i}( ˜t̃_{1}), …, h_{i}( ˜t̃_{n})) ∈ dom f_{ψ}^{B_{i}}, and therefore also (h( ˜t̃_{1}), …, h( ˜t̃_{n})) ∈ dom f_{ψ}^{B}. Moreover, in this case we have

h_{i}(f_{ψ}^{s}( ˜t̃_{1}, …, ˜ t̃_{n})) = h_{i}( ˜ψ̃(t_{1}, …, t_{n})) = f_{ψ}^{B_{i}}(h_{i}( ˜t̃_{1}), …, h_{i}( ˜t̃_{n})).

Therefore also h(f_{ψ}^{s}( ˜t̃_{1}, …, ˜ t̃_{n})) = f_{ψ}^{B}(h( ˜t̃_{1}), …, h( ˜t̃_{n})). This is true for every index set I and arbitrary choices of A_{i} ∈ K, m_{i} and μ_{i}.

Now we are going to specify the set I, the partial algebras A_{i} and to choose m_{i} and μ_{i} for i ∈ I. We put I := (pTerm(Y) × pTerm(Y)) \ pEq_{Y} (K). Therefore I is the set (!) of all equations over Y which do not hold in K. Let M_{(s,t)} := {A ∈ K | A |̸= s ≈ t}. If (s, t) ∈ I, then M_{(s,t)} ≠ ∅. Using the axiom of choice, we can find a function I → K, assigning to each i = (s, t) ∈ I a partial algebra A_{i} ∈ M_{(s,t)}. But if i = (s, t) and A_{i} |̸= s ≈ t, then by Lemma 4.5 also \underline{clone}^{τ} A_{i} |̸= s ≈ t. Consequently there is an m_{i} ∈ Np and a μ_{i} : Y → \{1, …, m_{i}\} such that μ_{i}^{⋆}(s) ≠ μ_{i}^{⋆}(t). We want to prove that for this choice of I, A_{i}, m_{i}, μ_{i} our function h is an injective closed homomorphism.

We have already seen, that ( ˜t̃_{1}, …, ˜ t̃_{n}) ∈ dom f_{ψ}^{s} implies (h( ˜t̃_{1}), …, h( ˜t̃_{n})) ∈ dom f_{ψ}^{B}. Furthermore, in this case we have h(f_{ψ}^{s}( ˜t̃_{1}, …, ˜ t̃_{n})) = f_{ψ}^{B}(h( ˜t̃_{1}), …, h( ˜t̃_{n})). So we only have to prove, that h is injective and closed.

1. injective: Let ˜ t̃, ˜ t̃′ ∈ T_{K}(Y, s) with ˜ t̃ ≠ ˜ t̃′, i.e. K |̸= t ≈ t′. But then (t, t′) ∈ I and we obtain that there is an i ∈ I with μ_{i}^{⋆}(t) ≠ μ_{i}^{⋆}(t′), consequently h_{i}(˜t̃) ≠ h_{i}(˜t̃′) and therefore h(˜t̃) ≠ h(˜t̃′).

2. closed homomorphism: We must show that (h( ˜t̃_{1}), …, h( ˜t̃_{n})) ∈ dom f_{ψ}^{B} implies

( ˜t̃_{1}, … ˜ t̃_{n}) ∈ dom f_{ψ}^{s},

i.e. ψ(t_{1}, … t_{n}) ∼ s. So let us assume that ψ(t_{1}, …, t_{n}) ≁ s. Equation (17) in Lemma 4.7 shows that ψ(t_{1}, …, t_{n}) ⪯ t_{i}. We have t_{i} ⪯ s and by Lemma 5.2(i) we have also ψ(t_{1}, …, t_{n}) ⪯ s. If ψ(t_{1}, …, t_{n}) ≁ s, then s ⪯̸ ψ(t_{1}, …, t_{n}), i.e. the equation ε_{1}^{2}(s, ψ(t_{1}, …, t_{n})) ≈ s cannot hold in K. Therefore i = (ε_{1}^{2}(s, ψ(t_{1}, …, t_{n})) , s) ∈ I, and for this i we have

μ_{i}^{⋆}(ε_{1}^{2}(s, ψ(t_{1}, …, t_{n}))) ≠ μ_{i}^{⋆}(s)

This yields:

e_{1,A_{i}}^{2}[μ^{⋆}(s), f_{ψ}^{A_{i}}[μ^{⋆}(t_{1}), …, μ^{⋆}(t_{n})] ] ≠ μ^{⋆}(s)

But then there exists an \underline{a} ∈ A_{i}^{m_{i}} such that:

\underline{a} ∈ dom μ^{⋆}(s) and \underline{a} ∉ dom f_{ψ}^{A_{i}}[μ^{⋆}(t_{1}), …, μ^{⋆}(t_{n})] .

If we take into account that dom μ^{⋆}(s) = dom μ^{⋆}(t_{1}) = … = dom μ^{⋆}(t_{n}), then we find that

(μ^{⋆}(t_{1})(\underline{a}), …, μ^{⋆}(t_{n})(\underline{a})) ∉ dom f_{ψ}^{A_{i}}.

But then also (h_{i}( ˜t̃_{1}), …, h_{i}( ˜t̃_{n})) ∉ dom f_{ψ}^{B_{i}}, therefore (h( ˜t̃_{1}), …, h( ˜t̃_{n})) ∉ dom f_{ψ}^{B}. This proves that h is a closed homomorphism between partial algebras.

The algebra B is in K. We found an injective closed homomorphism h : T_{K}(Y, s) → B. Now by Lemma 3.5 we have T_{K}(Y, s) ≅ h(T_{K}(Y, s)) ≤ B. The class K is closed under taking subalgebras and homomorphic (and therefore isomorphic) images, consequently T_{K}(Y, s) ∈ K.

Remark. In this proof we used only that K is closed under taking subalgebras, direct products and isomorphic images.

All functions in our partial algebras have finite arities. Therefore every equation contains only finitely many variables. For the formulation of our equations it is enough to have a countable infinite set X of variables. This is the content of the following Lemma.

Lemma 5.6 Let X be a countably infinite set and let Y ≠ ∅ be an arbitrary set. If K is a class of partial algebras (of type τ), then we have:

pMod_{X}(pEq_{X}(K)) ⊆ pMod_{Y} (pEq_{Y} (K))

Proof. Let A ∈ pMod_{X}(pEq_{X}(K)). Then every equation over X, valid in K, is also valid in A. Now let s, t ∈ pTerm(Y) with K ⊧ s ≈ t. We have to show that also A ⊧ s ≈ t.

Let us assume that A |̸= s ≈ t. Then there is a ϱ : Y → A with ϱ^{⋆}(s) ≠ ϱ^{⋆}(t). The values ϱ^{⋆}(s), ϱ^{⋆}(t) ∈ A depend only on the values ϱ(y) for y ∈ occ (s) ∪ occ (t). This set is finite. Therefore we can find X_{0} ⊂ X with |X_{0}| = |occ (s) ∪ occ (t)|, w.l.o.g. put X_{0} = {x_{y} | y ∈ occ (s) ∪ occ (t)}. (Here y ≠ y′ implies x_{y} ≠ x_{y′}). We can define terms s′, t′ ∈ pTerm(X) by replacing every y in s and t by x_{y}. If we choose a function ϱ′ : X → A with ϱ′(x_{y}) := ϱ(y), then ϱ^{′⋆}(s′) = ϱ^{⋆}(s) ≠ ϱ^{⋆}(t) = ϱ^{′⋆}(t′). Consequently A |̸= s′ ≈ t′ and therefore also K |̸= s′ ≈ t′. But then there exists a B ∈ K and a ρ′ : X → A such that ρ^{′⋆}(s′) ≠ ρ^{′⋆}(t′). If we now define ρ : Y → A with ρ(y) := ρ′(x_{y}) for all y ∈ occ (s) ∪ occ (t) (and arbitrarily on the rest of Y), then we have ρ^{⋆}(s) = ρ^{′⋆}(s′) ≠ ρ^{′⋆}(t′) = ρ^{⋆}(t), i.e. K |̸= s ≈ t — a contradiction.

Now we are able to start with our main construction. Let K be a class of partial algebras, closed under H_{c} , S and Pfilt . Furthermore let X be a countably infinite set. Our aim is to prove that

pMod_{X}(pEq_{X}(K)) ⊆ K .

Therefore let A = ⟨A ; (f_{ψ}^{A})_{ψ∈Ψ}⟩ ∈ pMod_{X}(pEq_{X}(K)). First we will construct a filtered product of some K-term algebras T_{K}(Y, s) (which are in K because of Lemma 5.5). Then we will figure out a special subalgebra of this filtered product. Finally we will prove that A is a closed homomorphic image of this subalgebra.

We choose a set Y with |Y | = |A|, namely let Y := {y_{a} | a ∈ A} (where a ≠ b implies y_{a} ≠ y_{b}). Furthermore we fix a special function ϱ, namely let ϱ : Y → A, y_{a} ↦ a. We define an index set I and a filter F on I.

I := {s ∈ pTerm(Y) | ϱ^{⋆}(s) ∈ A}
F := {F ⊆ I | there exists s_{0} ∈ I
such that for all s ∈ I, s ⪯ s_{0} ⇒ s ∈ F }

By the definition of F it is obvious that F ≠ ∅ for all F ∈ F and that F ∈ F, F ⊆ F′ implies F′ ∈ F. Furthermore I ∈ F, therefore F ≠ ∅. We have to check the intersection property. Therefore let F, F′ ∈ F and choose s_{0} ∈ F, s′_{0} ∈ F′ such that for all s ∈ I the conditions s ⪯ s_{0} ⇒ s ∈ F and s ⪯ s′_{0} ⇒ s ∈ F′ are fulfilled. Consider the term ε_{1}^{2}(s_{0}, s′_{0}). We have ϱ^{⋆}(s_{0}), ϱ^{⋆}(s′_{0}) ∈ A, therefore also ϱ^{⋆}(ε_{1}^{2}(s_{0}, s′_{0})) = e_{1,A}^{2}(ϱ^{⋆}(s_{0}), ϱ^{⋆}(s′_{0})) ∈ A, i.e. ε_{1}^{2}(s_{0}, s′_{0}) ∈ I. Furthermore Lemma 4.7 and Lemma 4.6 (we refer to this Lemma with (rep)) imply:

ε_{1}^{2}(ε_{1}^{2}(s_{0}, s′_{0}), s′_{0}) ≈^{(16)} ε_{1}^{2}(s_{0}, ε_{1}^{2}(s′_{0}, s′_{0})) ≈^{(15,rep)} ε_{1}^{2}(s_{0}, s′_{0})

This means ε_{1}^{2}(s_{0}, s′_{0}) ⪯ s′_{0}.

ε_{1}^{2}(ε_{1}^{2}(s_{0}, s′_{0}), s_{0}) ≈^{(18)} ε_{1}^{2}(s_{0}, s′_{0})

This means ε_{1}^{2}(s_{0}, s′_{0}) ⪯ s_{0}. Consequently ε_{1}^{2}(s_{0}, s′_{0}) ∈ F ∩ F′. By Lemma 5.2(i), the relation ⪯ is transitive, i.e. s ∈ I, s ⪯ ε_{1}^{2}(s_{0}, s′_{0}) ⇒ s ∈ F ∩ F′. Therefore F ∩ F′ ∈ F, i.e. F is a proper filter on I.

Now let B = ⟨B ; (f_{ψ}^{B})_{ψ∈Ψ}⟩ be the filtered product of the algebras T_{K}(Y, s).

B := ∏_{s∈I} |F T_{K}(Y, s)

The algebras T_{K}(Y, s) are in K (Lemma 5.5), and K is assumed to be closed under filtered products. Therefore B ∈ K.

The elements of B have the form \binom{}{ ˆt̃_{s}}_{s∈I}. Here t_{s} ∈ T_{K}(Y, s), the ˜ denotes the equiva-

lence class w.r. to ≈ and the denotes the equivalence class w.r. to the filter equivalence θ_{F}. But this element is uniquely determined by the I-tuple (t_{s})_{s∈I}, therefore we can omit the ˜ in our notation and we will write ˆ (t_{s})_{s∈I} for this element of B. The filter equivalence θ_{F} can be described using only I-tuples of terms:

ˆ (t_{s})_{s∈I} = ˆ (t′_{s})_{s∈I} ⇔ {s ∈ I | t_{s} ≈ t′_{s}} ∈ F

We want to introduce another abbreviation. Let s, t ∈ pTerm(Y). Then we put:

t^{⟨s⟩} := \{ \begin{matrix}t & if t ∈ T_{K}(Y, s) \\ s & else \end{matrix}

If (t_{s})_{s∈I} is an arbitrary family of terms t_{s} ∈ pTerm(Y), then ˆ (t_{s}^{⟨s⟩})_{s∈I} is in B. Moreover, we always have t^{⟨s⟩} = t iff t ∼ s.

The algebra A is in pMod_{X}(pEq_{X}(K)), X is countable and by Lemma 5.6 we also know that A ∈ pMod_{Y} (pEq_{Y} (K)). This means that every equation over Y, which holds in K, is also true in A. Therefore, if t ≈ t′, then ϱ^{⋆}(t) = ϱ^{⋆}(t′). And by Lemma 5.3, if t ∼ t′, then ϱ^{⋆}(t) ∈ A ⇔ ϱ^{⋆}(t′) ∈ A.

Let u ∈ pTerm(Y). Then we have:

u ∈ I ⇔ {s ∈ I | ε_{1}^{2}(u, s) ∼ s} ∈ F  (20)

Namely if u ∉ I and s ∈ I, then ϱ^{⋆}(u) = ∞ and therefore ϱ^{⋆}(ε_{1}^{2}(u, s)) = ∞, while ϱ^{⋆}(s) ∈ A. Then Lemma 5.3 shows that ε_{1}^{2}(u, s) ≁ s. Consequently {s ∈ I | ε_{1}^{2}(u, s) ∼ s} = ∅ ∉ F. Vice versa, let u ∈ I. We must show {s ∈ I | ε_{1}^{2}(u, s) ∼ s} ∈ F. Therefore we have to find an element s_{0} ∈ I such that s ∈ I, s ⪯ s_{0} implies ε_{1}^{2}(u, s) ∼ s. We choose s_{0} := u ∈ I.

If s ∈ I, s ⪯ u, then ε_{1}^{2}(ε_{1}^{2}(u, s), s) ≈^{(16)} ε_{1}^{2}(u, ε_{1}^{2}(s, s)) ≈^{(15)} ε_{1}^{2}(u, s) and ε_{1}^{2}(s, ε_{1}^{2}(u, s)) ≈^{(16)}

ε_{1}^{2}(ε_{1}^{2}(s, u), s) ≈^{(s⪯u)} ε_{1}^{2}(s, s) ≈^{(15)} s. But this means ε_{1}^{2}(u, s) ∼ s. Consequently (20) is true.

If we observe that ε_{1}^{2}(u, s) ∼ s iff ε_{1}^{2}(u, s)^{⟨s⟩} = ε_{1}^{2}(u, s), then we can formulate (20) as follows:

u ∈ I ⇔ {s ∈ I | ε_{1}^{2}(u, s)^{⟨s⟩} = ε_{1}^{2}(u, s)} ∈ F  (21)

Now for u ∈ pTerm(Y) we define an element ζ(u) ∈ B:

ζ(u) := ˆ (ε_{1}^{2}(u, s)^{⟨s⟩})_{s∈I}

Furthermore let M be the following set:

M := {ζ(u) | u ∈ I} ⊆ B

Let us assume that t_{1}, …, t_{n} ∈ I and (ζ(t_{1}), …, ζ(t_{n})) ∈ dom f_{ψ}^{B} (α(ψ) = n). Then we have:

f_{ψ}^{B}(ζ(t_{1}), …, ζ(t_{n})) = ˆ (ψ(ε_{1}^{2}(t_{1}, s)^{⟨s⟩}, …, ε_{1}^{2}(t_{n}, s)^{⟨s⟩})^{⟨s⟩})_{s∈I}

Equation (21) and the intersection property for the filter F show:

{s ∈ I | ε_{1}^{2}(t_{j}, s)^{⟨s⟩} = ε_{1}^{2}(t_{j}, s) for all j = 1 … n} ∈ F

Consequently also

{s ∈ I | (ψ(ε_{1}^{2}(t_{1}, s)^{⟨s⟩}, …, ε_{1}^{2}(t_{n}, s)^{⟨s⟩})^{⟨s⟩})_{s∈I} = (ψ(ε_{1}^{2}(t_{1}, s), …, ε_{1}^{2}(t_{n}, s))^{⟨s⟩})_{s∈I}} ∈ F ,

therefore

f_{ψ}^{B}(ζ(t_{1}), …, ζ(t_{n})) = ˆ (ψ(ε_{1}^{2}(t_{1}, s), …, ε_{1}^{2}(t_{n}, s))^{⟨s⟩})_{s∈I}

But now equation (19) in Lemma 4.7 shows:

f_{ψ}^{B}(ζ(t_{1}), …, ζ(t_{n})) = ˆ (ε_{1}^{2}(ψ(t_{1}, …, t_{n}), s)^{⟨s⟩})_{s∈I} = ζ(ψ(t_{1}, …, t_{n})) ∈ M

Consequently M is a closed subset for the functions f_{ψ}^{B} with ψ ∈ Ψ. The following algebra is a subalgebra of B:

M := ⟨M ; (f_{ψ}^{B}|_{M})_{ψ∈Ψ}⟩

The class K is assumed to be closed under S , B ∈ K, consequently also M ∈ K.

Now we define a (total) function h : M → A by ζ(t) ↦ ϱ^{⋆}(t). (It is easy to check that this is a correct definition). This function is surjective, namely for a ∈ A we have y_{a} ∈ I and therefore h(ζ(y_{a})) = ϱ^{⋆}(y_{a}) = a. We want to show, that h is a closed homomorphism h : M → A.

Consider the domains of f^{M}ψ and f^{A}ψ. We have:

(ζ(t_{1}), …, ζ(t_{n})) ∈ dom f_{ψ}^{M}
⇔ {s ∈ I | ε_{1}^{2}(ψ(t_{1}, …, t_{n}), s) ∼ s} ∈ F
⇔ ψ(t_{1}, …, t_{n}) ∈ I
⇔ ϱ^{⋆}(ψ(t_{1}, …, t_{n})) ∈ A
⇔ (ϱ^{⋆}(t_{1}), …, ϱ^{⋆}(t_{n})) ∈ dom f_{ψ}^{A}
⇔ (h(ζ(t_{1})), …, h(ζ(t_{n}))) ∈ dom f_{ψ}^{A}

We have already seen that for all (ζ(t_{1}), …, ζ(t_{n})) ∈ dom f_{ψ}^{M} there holds:

f_{ψ}^{M}(ζ(t_{1}), …, ζ(t_{n})) = ζ(ψ(t_{1}, …, t_{n}))

Consequently for all (ζ(t_{1}), …, ζ(t_{n})) ∈ dom f_{ψ}^{M} we have:

h(f_{ψ}^{M}(ζ(t_{1}), …, ζ(t_{n}))) = ϱ^{⋆}(ψ(t_{1}, ….t_{n})) = f_{ψ}^{A}(h(ζ(t_{1})), …, h(ζ(t_{n})))

This proves that h is indeed a closed homomorphism. But then A is a closed homomorphic image of M ∈ K, therefore (K is closed under H_{c}) also A ∈ K. This proves the following Lemma.

Lemma 5.7 Let X be a countably infinite set and let K be a class of partial algebras. If K is closed under H_{c} , S and Pfilt , then

K = pMod_{X}(pEq_{X}(K)) .

We can summarize our results in the following Theorem.

Theorem 5.8 Let τ be a type and let K be a class of partial algebras of type τ. Then the following statements are equivalent:

(i) K is a variety of partial algebras, i.e. there exists a τ-clone \underline{C}^{τ} with K = pVar(\underline{C}^{τ}). (ii) K is closed under H_{c} , S and Pfilt . (iii) There exists a set X and a set of equations Γ ⊆ pTerm(X) × pTerm(X) such that

K = pMod_{X}(Γ).

Proof. (i)⇒(ii) is the content of the Lemmas 3.7, 3.8 and 3.11. (ii)⇒(iii) by Lemma 5.7 and (iii)⇒(i) because of Lemma 4.8.

This theorem shows that our notion of a partial variety is a natural generalization of the notion of a variety in the total case.

If we compare our notions with other concepts, then we see ([5, Theorem 8.3.5.(iii)]), that our “partial varieties” are almost the same like the “ECE-varieties” in the sense of P. Burmeister. ECE-varieties are defined on the model theoretical basis of so called “existentially conditioned equations”. So we note, that our model theoretical concept — generalized terms with Kleene-equality — has nearly the same power like the ECE-equations. For a comparison of ECE- and generalized Kleene-equations we refer to [6].

References

[1] Andréka, H.; Németi, I.: Generalization of the concept of variety and quasivariety to partial algebras through category theory. Dissertationes Mathematicae, vol. 204, Polska Akademia Nauk, Warsaw, 1983.

[2] Andréka, H.; Craig, W.; Németi, I.: A system of logic for partial functions under existence-dependent Kleene equality. Journal of Symbolic Logic, vol. 53/3(1988), 834– 839.

[3] Börner, F.: Operationen auf Relationen. Dissertation A. Karl-Marx-Universität Leipzig 1988.

[4] Börner, F.; Pöschel, R.: Partial clones. Beiträge der Jahrestagung “Algebra und Grenzgebiete”. PREPRINT-Reihe der PH Güstrow 1990.

[5] Burmeister, P.: A Model Theoretic Oriented Approach to Partial Algebras. Akademie Verlag Berlin 1986.

[6] Burmeister, P.: On the equivalence of ECE- and generalized Kleene-equations. Preliminary Report. Manuscript 1994.

[7] Craig, W.: Near-equational and equational systems of logic for partial functions. Part I in: Journal of Symbolic Logic, vol. 54/3(1989), 795–827. Part II in: Journal of Symbolic Logic, vol. 54/4(1989), 1167–1182.

[8] Hoehnke, H.-J.: On partial algebras. Colloquia Mathematica Societatis János Bolyai. 29. Universal Algebra, Esztergom (Hungary), 1977.

[9] Hoehnke, H.-J.: Monoidal Structure of Mal’cev clones, their theories and completions. Preprint 34/87 Karl-Weierstraß-Institut für Mathematik, Berlin 1987.

[10] Hoehnke, H.-J.: On certain classes of categories and monoids constructed from abstract Mal’cev clones. Part I-IV. Preprints P-MATH 48/88, 30/89, 08/90, Karl-Weierstraß-Institut für Mathematik, Berlin 1988–1990.

[11] Lau, D.: Über partielle Funktionenalgebren. Rostock. Math. Kolloq. 33 (1988), 23–48.

[12] Lugowski, H.: Grundzüge der Universellen Algebra. Teubner Verlag Leipzig 1976.

[13] Lau, D.; Denecke, K.: Congruences on maximal partial clones and strong regular varieties generated by preprimal partial algebras I. Wissenschaftliche Zeitung der PH “Karl Liebknecht” Potsdam 34 (1990), Heft 1, 117–122.

[14] Lau, D.; Denecke, K.: Congruences on maximal partial clones and strong regular varieties generated by preprimal partial algebras II. Demonstratio Mathematika, Vol. XXIV, No 1–2 (1991), 105–119.

[15] Malcev, A. I.: Algorithmen und rekursive Funktionen. Akademie-Verlag Berlin 1974.

[16] McKenzie, R.; McNulty, G.; Taylor, W.: Algebras, Lattices, Varieties. Volume I. Monterey 1987.

[17] Pöschel, R.; Kalužnin, L. A.: Funktionen- und Relationenalgebren. Deutscher Verlag der Wissenschaften, Berlin 1979.

[18] Reichel, H.: Structural Induction on Partial Algebras. Akademie-Verlag Berlin 1984.

[19] Rosenberg, I. G.: Partial algebras and clones via one-point extension. Preprint D.M.S. No 88-16, Université de Montréal, Sept. 1988.

[20] Schein, B.; Trochimenko, V. S.: Algebras of multiplace functions. Semigroup Forum 17 (1979), 1–64.

[21] Schmidt, J.: Allgemeine Algebra. Vorlesungsmanuskript. Preprint Universität Bonn 1966.

[22] Schreckenberger, J.: Über die Einbettung von dht-symmetrischen Kategorien in die Kategorie der partiellen Abbildungen zwischen Mengen. Preprint P-12/80, AdW, Zentralinstitut für Mathematik, Berlin 1980.

[23] Whitlock, H. I.: A Composition Algebra for Multiplace Functions. Math. Annalen 157 (1964), 167–178.

Received February 7, 1994; revised version February 1, 1996