Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 41 (2000), No. 2, 537-555.

Pairwise Intersections of Słupecki Type Maximal Partial Clones

Lucien Haddad^{1} Dietlinde Lau

Département de Mathématiques et d’Informatique, Collège militaire royal du Canada boite postale 17000, STN Forces, Kingston ON K7K 7B4 Canada

Fachbereich Mathematik, Universität Rostock Universitätsplatz 1, 18055 Rostock, Germany e-mail: dietlinde.lau@mathematik.uni-rostock.de

Abstract. Let k ≥ 2 and k be a k-element set. We study the pairwise intersections of all maximal partial clones of Słupecki type on k. More precisely, we show that with one exception, if M and M′ are two strong maximal partial clones of Słupecki type on k, then M ∩ M′ is covered by both M and M′. We also show that the situation is quite different if the non-strong maximal partial clone on k is involved in the intersection.

1. Introduction

Let k ≥ 2 and k := {0, …, k−1}. Denote by Par(k) the set of all partial functions and Op(k) the set of all (total) functions on k, that is Op(k) consists of all everywhere defined functions on k. A partial clone on k is a subset of Par(k) closed under composition and containing all the projections on k. If a partial clone is contained in Op(k), then it is called a clone on k. For example if ρ is any relation on k, then the set pPol ρ (Pol ρ) of all partial functions (of all functions) that preserve ρ is a partial clone (a clone) on k (this and other concepts will be precisely defined in Section 2). The partial clones on k (the clones on k), ordered by inclusion, form a dually atomic lattice, that is a bounded lattice where every proper partial clone (proper clone) can be extended to a maximal one and contains a minimal one (see e.g., [2], [7] and [15]). The foundation of a partial clone is the set of its unary functions. A famous result on clones whose foundation is Op^{(1)}(k), the set of all unary functions on k, was established by Słupecki in 1939 ([20]). This result is known as the Słupecki criterion and may be formulated as follows. For 3 ≤ h ≤ k, let

1Financially supported by NSERC Canada and ARP grants.

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

τ_{h} := {(x_{1}, …, x_{h}) ∈ k^{h} | x_{i} = x_{j} for some 1 ≤ i < j ≤ h}.

Then Pol τ_{k} is the unique maximal clone that contains the set Op^{(1)}(k) of all unary functions on k. Motivated by the remarkable Słupecki criterion, we call a partial clone on k of Słupecki type if it contains the set Op^{(1)}(k) of all unary functions on k.

In [14], A.I. Mal’tsev gives an excellent proof of the Słupecki criterion and moreover improves it by showing that

Pol τ_{3} ⊂ … ⊂ Pol τ_{k} ⊂ Op(k)

is the unique unrefinable finite chain of clones containing Pol τ_{3}. Later on Burle in [4] uses Mal’tsev results to show that the interval of all clones of Słupecki type on k is simply the chain

⟨Op^{(1)}(k)⟩ ⊂ Pol R_{1} ⊂ Pol τ_{3} ⊂ … ⊂ Pol τ_{k} ⊂ Op(k),

where ⟨Op^{(1)}(k)⟩ is the clone generated by the set Op^{(1)}(k) and

R_{1} = {(x, y, z, t) ∈ k^{4} | [x = y and z = t] or [x = z and y = t] or [x = t and y = z]}. As Op^{(1)}(k) is a finite set, one can easily obtain (e.g., see [3]) that every clone of Słupecki type on k is finitely generated.

The situation is quite different for the partial case. Denote by M_{k} the set of all partial functions that are either everywhere or nowhere defined on k. It is shown in [7] that this is the unique non-strong maximal partial clone on k and it is clearly of Słupecki type. A partial clone is strong if it is closed under formation of suboperations. Now from the description of all maximal partial clones on k given in [6] and [8], one can easily see that there are k strong maximal partial clones of Słupecki type on k, they consist of pPol R_{1}, pPol R_{2}, pPol τ_{3}, …, pPol τ_{k}, where

R_{2} = {(x, y, z, t) ∈ k^{4} | [x = y and z = t] or [x = t and y = z]}.

We point out here that these results were found independently by Romov in [17] and [19]. Moreover it is shown in citeinfinite that M_{k} is the only finitely generated maximal partial clone of Słupecki type on k. Finally, it is shown in [10] that for k ≥ 2, the interval of all partial clones of Słupecki type on k has the cardinality of the continuum.

In this paper, we focus our attention on maximal partial clones of Słupecki type over k. We study the pairwise intersection of such clones and show that with one exception, the intersection of any two strong maximal partial clones of Słupecki type on k is covered by both these two maximal partial clones. The exception is the case of the two maximal partial clones pPol R_{1} and pPol R_{2} since pPol R_{1} ∩ pPol R_{2} is not covered by pPol R_{2}. Furthermore, we show that such results do not hold if the non-strong maximal partial clone M_{k} on k is considered. Here we show that if M is a strong maximal partial clone of Słupecki type, then the interval of partial clones [M_{k} ∩ M, M] is of continuum cardinality on k. A part of the proof here is based on results established in [1] and [10].

2. Preliminaries

Let k ≥ 2 be an integer and k := {0, 1, …, k − 1}. For a positive integer n, an n-ary partial function on k is a map f : dom (f) → k where dom (f) ⊆ k^{n} is called the domain of f. Let Par^{(n)}(k) denote the set of all n-ary partial operations on k and let Par(k) := ⋃_{n≥1} Par^{(n)}(k).

Moreover set Op^{(n)}(k) := {f ∈ Par^{(n)}(k) | dom (f) = k^{n}} and let Op(k) := ⋃_{n≥1} Op^{(n)}(k), i.e.,

Op(k) is the set of all total functions on k. In the sequel we will say “function” for “total function”.

For every positive integer n, and every 1 ≤ i ≤ n, we denote by e_{i}^{n} the n-ary function i-th projection defined by e_{i}^{n}(x_{1}, …, x_{n}) := x_{i} for all (x_{1}, …, x_{n}) ∈ k^{n}. Furthermore let

J_{k} := {e_{i}^{n} | 1 ≤ i ≤ n < ∞}

be the set of all projections on k. Definitions. 1. A partial clone on k is a composition closed subset of Par(k) containing the set of all projections J_{k}. For a formal definition, we refer the reader to one of the papers [2], [6] or [8].

2. A partial function g ∈ Par^{(n)}(k) is a subfunction of f ∈ Par^{(n)}(k) (in symbols g ≤ f or g = f|_{dom (g)}) if dom (g) ⊆ dom (f) and g(a⃗) = f(a⃗) for all a⃗ ∈ dom (g). A partial clone C is strong if it contains all subfunctions of its partial functions, i.e., if for every f ∈ C and g ∈ Par(k), g ≤ f ⟹ g ∈ C. It is well known (e.g., see [3]) that a partial clone C is a strong partial clone if and only if it contains the set of all partial projections on k.

3. Let h ≥ 1 and ρ be an h-ary relation on k, (i.e., ρ ⊆ k^{h}), and let f be an n-ary partial function on k. Denote by M(ρ, dom(f)) (ρ ≠ ∅) the set of all h×n matrices M whose columns M_{∗j} ∈ ρ, for j = 1, …, n and whose rows M_{i∗} ∈ dom (f) for i = 1, …, h. We say that f preserves ρ if for every M ∈ M(ρ, dom(f)), the h-tuple f(M) := (f(M_{1∗}), …, f(M_{h∗})) ∈ ρ. Set pPol ρ := {f ∈ Par(k) | f preserves ρ} and Pol ρ = pPol ρ ∩ Op(k) (i.e., Pol ρ is the set of all (total) functions that preserve the relation ρ). It is well known that for every relation ρ, pPol ρ (Pol ρ) is a strong partial clone (a clone) on k. Now an h-ary relation ρ is said to be repetition-free if for all 0 ≤ i < j ≤ h − 1, there exists (a_{0}, …, a_{h−1}) ∈ ρ with a_{i} ≠ a_{j}. Moreover ρ is said to be irredundant if it is repetition-free and has no fictitious components, i.e., there is no i ∈ {0, …, h − 1} such that (a_{0}, …, a_{h−1}) ∈ ρ ⟹ (a_{0}, …, a_{i−1}, x, a_{i+1}, …, a_{h−1}) ∈ ρ for all x ∈ k. It is easy to see that if μ is any relation, then one can find an irredundant relation ρ such that pPol μ = pPol ρ (see [8] for details).

4. The partial clones on k, ordered by inclusion, form an algebraic lattice ([17]) in which every meet is the set-theoretical intersection. A partial clone C covers a partial clone D if D ⊂ C and the strict inclusions D ⊂ C′ ⊂ C hold for no partial clone C′ on k. Furthermore a partial clone M is a maximal partial clone if M is covered by Par(k). For F ⊆ Par(k), the partial clone ⟨F ⟩ generated by F, is the intersection of all partial clones containing the set F.

5. Let h ≥ 2 and let E_{h} denote the set of all equivalence relations on the set {1, …, h}. For ε ∈ E_{h}, put

Δ_{ε} = {(x_{1}, …, x_{h}) ∈ k^{h} | (i, j) ∈ ε ⇒ x_{i} = x_{j}},

thus Δ_{ε} consists of all h-vectors over k constant on every equivalence class of ε. An h-ary relation ρ is diagonal if there exists ε ∈ E_{h} such that ρ = Δ_{ε}. It is well known (see e.g. [8]) that a non-empty relation λ on k is a diagonal if and only if pPol (λ) = Par(k).

6. A partial clone is called of Słupecki type if it contains all unary (total) functions on k (see [3], [10] and [18]). It is shown in [10], that if λ is an irredundant relation on k, then pPol λ is a Słupecki type partial clone if and only if λ is a union of diagonal relations. Such relations are called primitive relations in [8] and [10].

For k ≥ 2, let M_{k} := Op(k) ∪ {p_{n} | n ≥ 1}, where p_{n} is the n-ary partial function on k with empty domain. Notice that M_{k} is a partial clone of Słupecki type of k, however it is not a strong partial clone and cannot be written as pPol ρ, where ρ is some relation over k (see [7]). We need the following relations. For 3 ≤ h ≤ k, let

τ_{h} := {(x_{1}, …, x_{h}) ∈ k^{h} | |{x_{1}, …, x_{h}}| ≤ h − 1},

R_{1} = {(x, y, z, t) ∈ k^{4} | [x = y and z = t] or [x = z and y = t] or [x = t and y = z]},

and

R_{2} = {(x, y, z, t) ∈ k^{4} | [x = y and z = t] or [x = t and y = z]}.

Recall that an h-ary relation ρ on k is totally symmetric if for every (x_{1}, …, x_{h}) ∈ k^{h} and every permutation π on the set {1, …, h}, we have

(x_{1}, …, x_{h}) ∈ ρ ⟺ (x_{π(1)}, …, x_{π(h)}) ∈ ρ.

Notice that R_{1}, τ_{3}, …, τ_{k} are totally symmetric relations on k. This fact will be used later on in this paper.

The following result comes from [8] (see also [17]). It gives a description of all maximal partial clones of Słupecki type on k.

Theorem 1. Let k ≥ 3. Then there are exactly k + 1 maximal partial clones of Słupecki type on k, namely M_{k}, pPol R_{1}, pPol R_{2}, pPol τ_{3}, …, pPol τ_{k}.

We want to study the pairwise intersections of maximal partial clones of Słupecki type over k. We will employ the Definability Lemma shown in [17] (see Lemma 1.7 in [8] for a weak version of it). We need the following terminology to state it: Let h_{1}, …, h_{n} ≥ 1 be integers and ϱ_{1}, …, ϱ_{n} be n relations on a set B, each of arity h_{i}, i = 1, …, n. We say that the family F := {ϱ_{1}, …, ϱ_{n}} covers the set B if for every x ∈ B, there is an i ∈ {1, …, n} such that x appears in at least one h_{i}-tuple of the relation ϱ_{i}. We have

Lemma 2. [17] (Definability Lemma) Let h_{1}, …, h_{n} ≥ 1, t ≥ 1 be integers, ρ_{i} be an h_{i}-ary

relation on k, i = 1, …, n and λ be a t-ary irredundant relation on k. Then ⋂_{i=1}^{n} pPol ρ_{i} ⊆

pPol λ if and only if there are n auxiliary relations ϱ_{1}, …, ϱ_{n} on the set {1, …, t}, each of arity h_{i}, such that the family F := {ϱ_{1}, …, ϱ_{n}} covers the set {1, …, t} and

λ = {(x_{1}, …, x_{t}) ∈ k^{t} | (x_{i_{1}^{j}}, …, x_{i_{h_{j}}^{j}}) ∈ ρ_{j} for all (i_{1}^{j}, …, i_{h_{j}}^{j}) ∈ ϱ_{j}, j = 1, …, n}. □

Example. Let ρ_{1} be a binary and ρ_{2} be a ternary relation on k. Suppose that the 5-ary irredundant relation λ is defined by

λ := {(x_{1}, …, x_{5}) ∈ k^{5} | (x_{1}, x_{2}) ∈ ρ_{1}, (x_{3}, x_{3}) ∈ ρ_{1}, (x_{2}, x_{5}, x_{4}) ∈ ρ_{2}},

then pPol ρ_{1} ∩ pPol ρ_{2} ⊆ pPol λ. Here n = 2, j_{1} = 2, j_{2} = 3, ϱ_{1} = {(1, 2), (3, 3)} and ϱ_{2} = {(2, 5, 4)}.

We will also employ the following result established by Romov.

Lemma 3. [17]. Let C be a strong partial clone on k. There exists a non-empty family of irredundant relations {ρ_{i} | i ∈ I} such that C = ⋂_{i∈I} pPol ρ_{i}.

Our study is divided into two main parts. In the first part we consider only strong maximal partial clones of Słupecki type, while in the second part the intersection of these partial clones with M_{k} is considered.

3. Intersections of strong partial clones

Consider two (distinct) maximal partial clones pPol ρ and pPol θ and suppose that

[pPol ρ ∩ pPol θ ⊆ pPol λ] ⟹ [pPol λ ⊆ pPol ρ or pPol λ = pPol θ]

holds for every irredundant relation λ. Then the partial clone pPol ρ ∩ pPol θ is covered by the maximal partial clone pPol θ. Indeed let C be a partial clone on k such that pPol ρ ∩ pPol θ ⊆ C ⊆ pPol θ. As both pPol ρ and pPol θ contain all partial projections, the same holds for C and so C is a strong partial clone. By Lemma 3, there exists a family of irredundant relations {ρ_{i} | i ∈ I} such that C = ⋂_{i∈I} pPol ρ_{i}. Then

pPol ρ ∩ pPol θ ⊆ pPol ρ_{i} and by the above property we have pPol ρ_{i} ⊆ pPol ρ or pPol ρ_{i} = pPol θ for each i ∈ I. If pPol ρ_{i} = pPol θ holds for all i ∈ I, then C = pPol θ. On the other hand, if pPol ρ_{i} ⊆ pPol ρ for some i ∈ I, then as C ⊆ pPol θ we get C = ⋂_{i∈I} pPol ρ_{i} ⊆

pPol ρ ∩ pPol θ and consequently C = pPol ρ ∩ pPol θ. This shows that

[pPol ρ ∩ pPol θ ⊆ C ⊆ pPol θ] ⟹ [C = pPol ρ ∩ pPol θ or C = pPol θ]

holds for every partial clone C on k, i.e., the partial clone pPol ρ ∩ pPol θ is covered by the maximal partial clone pPol θ. This fact will be used later on in this paper.

In the sequel we will assume k ≥ 3. We start with the following

Theorem 4. Let ϱ ∈ {R_{1}, R_{2}}, θ ∈ {R_{1}, τ_{3}, …, τ_{k}} with ρ ≠ θ. Then the partial clone pPol ρ ∩ pPol θ is covered by the maximal partial clone pPol θ.

Proof. Let t ≥ 1 and λ be a t-ary irredundant relation such that

pPol ρ ∩ pPol θ ⊆ pPol λ.

By Lemma 2, there is a 4-ary relation ϱ and an ℓ-ary relation ϑ, (where ℓ = 4 if θ = R_{1} and ℓ = h if θ = τ_{h} for some h = 3, …, k), with {ϱ, ϑ} covering the set {1, …, t} and such that

λ = {(x_{1}, …, x_{t}) ∈ k^{t} | (x_{i_{1}}, …, x_{i_{4}}) ∈ ρ for all (i_{1}, …, i_{4}) ∈ ϱ

and (x_{j_{1}}, …, x_{j_{ℓ}}) ∈ θ for all (j_{1}, …, j_{ℓ}) ∈ ϑ}.

Note that if ϱ = ∅, then λ can be defined from θ and by Lemma 2, pPol θ ⊆ pPol λ, thus pPol θ = pPol λ by the maximality of pPol θ. So assume ϱ ≠ ∅. We have Claim 1. If |{i_{1}, …, i_{4}}| ≤ 3 for all (i_{1}, …, i_{4}) ∈ ϱ, then pPol λ = pPol θ.

Proof (of the claim). Let (i_{1}, …, i_{4}) ∈ ϱ be such that |{i_{1}, …, i_{4}}| ≤ 3. Since λ is repetitionfree, the inequality |{i_{1}, …, i_{4}}| ≤ 3 implies that the condition (x_{i_{1}}, x_{i_{2}}, x_{i_{3}}, x_{i_{4}}) ∈ ρ is superfluous. This fact is shown in detail in [8]: Proposition 3.8 for the case ρ = R_{2} and Proposition 3.10 for ρ = R_{1}. We give a sketch of the proof for the case ρ = R_{1}. Suppose |{i_{1}, …, i_{4}}| ≤ 3. Since R_{1} is totally symmetric, we may assume i_{1} = i_{2}. If i_{3} ≠ i_{4}, then the condition (x_{i_{1}}, x_{i_{1}}, x_{i_{3}}, x_{i_{4}}) ∈ R_{1} gives x_{i_{3}} = x_{i_{4}} for all (x_{1}, …, x_{t}) ∈ λ, contradicting the fact that λ is an irredundant relation. On the other hand if i_{3} = i_{4}, then (x_{i_{1}}, x_{i_{2}}, x_{i_{3}}, x_{i_{4}}) ∈ R_{1} reduces to (x_{i_{1}}, x_{i_{1}}, x_{i_{3}}, x_{i_{3}}) ∈ R_{1}, which holds for every x_{i_{1}}, x_{i_{3}} ∈ k, i.e., the condition (x_{i_{1}}, x_{i_{2}}, x_{i_{3}}, x_{i_{4}}) ∈ ρ is superfluous. Now if |{i_{1}, …, i_{4}}| ≤ 3 holds for all (i_{1}, …, i_{4}) ∈ ϱ, then λ may be defined from θ and so pPol θ ⊆ pPol λ. Again as pPol θ is a maximal partial clone, we deduce that pPol θ = pPol λ. □

We now suppose that the t-ary relation λ satisfies pPol ρ ∩ pPol θ ⊆ pPol λ and pPol λ ≠ pPol θ. According to Claim 1, the 4-ary relation ϱ contains at least one 4-tuple (i_{1}, …, i_{4}) with |{i_{1}, …, i_{4}}| = 4. Thus t ≥ 4. For notational ease we assume that (1, 2, 3, 4) ∈ ϱ. We have

Claim 2. Let ρ = R_{1}. Then there are two 0-1 t-vectors a_{∼} = (a_{1}, …, a_{t}) and b_{∼} = (b_{1}, …, b_{t}) ∈ λ such that (a_{1}, …, a_{4}) ≠ (b_{1}, …, b_{4}) and (a_{1}, …, a_{4}), (b_{1}, …, b_{4}) ∈ {(0, 0, 1, 1), (0, 1, 1, 0), (0, 1, 0, 1)}.

Proof (of the claim). Since λ is repetition-free, there is a u_{∼} = (u_{1}, …, u_{t}) ∈ λ with u_{1} ≠ u_{2}. As (u_{1}, …, u_{4}) ∈ R_{1}, we have either [u_{1} = u_{3} and u_{2} = u_{4}] or [u_{1} = u_{4} and u_{2} = u_{3}]. Define the unary partial function φ by setting dom (φ) = {u_{1}, …, u_{t}}, φ(u) = 0 if u ≠ u_{2} and φ(u_{2}) = 1. As λ is a primitive relation, φ ∈ pPol λ and so (φ(u_{1}), …, φ(u_{t})) ∈ λ and satisfies (φ(u_{1}), …, φ(u_{4})) ∈ {(0, 1, 0, 1), (0, 1, 1, 0)}. In a similar fashion, one can use the fact that λ admits two t-vectors v_{∼} = (v_{1}, …, v_{t}), w_{∼} = (w_{1}, …, w_{t}) with v_{1} ≠ v_{3} and w_{1} ≠ w_{4}, to show that there are two 0-1 t-vectors (x_{1}, …, x_{t}), (y_{1}, …, y_{t}) ∈ λ such that (x_{1}, …, x_{4}) ∈ {(0, 1, 1, 0), (0, 0, 1, 1)} and (y_{1}, …, y_{4}) ∈ {(0, 1, 0, 1), (0, 1, 0, 1)}. As the three sets {(0, 1, 0, 1), (0, 1, 1, 0)},{(0, 1, 1, 0), (0, 0, 1, 1)} and {(0, 0, 1, 1), (0, 1, 0, 1)} have no common element, the result follows. □

Using the definition of R_{2}, we can show in a similar fashion the following

Claim 2’. Let ρ = R_{2}. Then there are two 0-1 t-tuples a_{∼} = (a_{1}, …, a_{t}) and b_{∼} = (b_{1}, …, b_{t}) ∈ λ such that a_{1} = a_{2} = 0; a_{3} = a_{4} = 1 and b_{1} = b_{4} = 0; b_{2} = b_{3} = 1. □

We turn to the proof of our theorem. We have

Claim 3. pPol λ ⊆ pPol ρ.

Proof (of the claim). We argue the contrapositive. Suppose pPol λ ⊈ pPol ρ and let φ ∈ pPol λ \ pPol ρ be n-ary. Then there is a 4 × n matrix M = [M_{ij}] ∈ M(ρ, dom (φ)) such that (φ(M_{1∗}), φ(M_{2∗}), φ(M_{3∗}), φ(M_{4∗})) ∉ ρ. Put D := {M_{1∗}, M_{2∗}, M_{3∗}, M_{4∗}} and let φ′ := φ|_{D}. As pPol λ is a strong partial clone, φ′ ∈ pPol λ. Define n binary partial functions g_{1}, …, g_{n} by

dom (g_{1}) = … = dom (g_{n}) = {(0, 0), (0, 1), (1, 1), (1, 0)},

and

( \begin{matrix}g_{i}(0, 0) \\ g_{i}(0, 1) \\ g_{i}(1, 1) \\ g_{i}(1, 0) \end{matrix} ) = ( \begin{matrix}M_{1i} \\ M_{2i} \\ M_{3i} \\ M_{4i} \end{matrix} ) for all i = 1, …, n.

As (M_{1i}, M_{2i}, M_{3i}, M_{4i}) ∈ ρ, we have that |{M_{1i}, M_{2i}, M_{3i}, M_{4i})}| ≤ 2 (recall that ρ is either the relation R_{1} or R_{2}). Consequently |Im (g_{i})| ≤ 2 and so g_{i} ∈ pPol τ_{h} for all i = 1, …, n, and all h = 3, …, k. We treat the cases ρ = R_{1} and ρ = R_{2} separately.

Case 1. ρ = R_{1}. In this case θ ∈ {τ_{3}, …, τ_{k}}. First note that R_{1} is a totally symmetric relation, that is

(x_{1}, …, x_{4}) ∈ R_{1} ⟺ (x_{π(1)}, …, x_{π(4)}) ∈ R_{1},

for every permutation π on the set {1, …, 4}. Since (M_{1i}, M_{2i}, M_{3i}, M_{4i}) ∈ R_{1} and R_{1} is totally symmetric, we see that g_{i} ∈ pPol R_{1} for all i = 1, …, n. Consequently g_{i} ∈ pPol ρ ∩ pPol θ, and thus g_{i} ∈ pPol λ, for all i = 1, …, n. It follows that the binary partial function \overline{φ} := φ′[g_{1}, …, g_{n}] satisfies \overline{φ} ∈ pPol λ. Note that dom (\overline{φ}) = \{(0, 0), (0, 1), (1, 1), (1, 0)\} and \overline{φ}(0, 0) = φ(M_{1∗}), \overline{φ}(0, 1) = φ(M_{2∗}), \overline{φ}(1, 1) = φ(M_{3∗}) and \overline{φ}(1, 0) = φ(M_{4∗}). Denote by N := [a_{∼} | b_{∼}] the 0-1 matrix of size t×2 with first column N_{∗1} = a_{∼} and second column N_{∗2} = b_{∼}, where a_{∼} and b_{∼} are constructed in Claim 2. Since dom (\overline{φ}) = \{(0, 0), (0, 1), (1, 1), (1, 0)\}, all rows of the matrix N belong to the domain of \overline{φ}. Moreover as a_{∼}, b_{∼} ∈ λ, we have N ∈ M(λ, dom (\overline{φ})). Now (\overline{φ}(N_{1∗}), …, \overline{φ}(N_{4∗})) = (φ(M_{π(1)∗}), φ(M_{π(2)∗}), φ(M_{π(3)∗}), φ(M_{π(4)∗})) for some permutation π on the set {1, …, 4}. Since R_{1} is a totally symmetric relation and since (φ(M_{1∗}), φ(M_{2∗}), φ(M_{3∗}), φ(M_{4∗})) ∉ R_{1}, we get (\overline{φ}(N_{1∗}), …, \overline{φ}(N_{4∗})) ∉ R_{1}. It follows that (\overline{φ}(N_{1∗}), …, \overline{φ}(N_{t∗}) ∉ λ contradicting \overline{φ} ∈ pPol λ.

Case 2. ρ = R_{2}. In this case θ ∈ {R_{1}, τ_{3}, …, τ_{k}}. As in Case 1, one may use the symmetries of R_{2} and the fact that (M_{1i}, M_{2i}, M_{3i}, M_{4i}) ∈ R_{2} to show that g_{i} ∈ pPol R_{1} ∩ pPol R_{2}, for all i = 1, …, n. Consequently, for ρ = R_{2} and θ ∈ {R_{1}, τ_{3}, …, τ_{k}}, we have g_{i} ∈ pPol λ for all i = 1, …, n. The rest of the proof is similar to the one given for the Case 1, with the difference that (\overline{φ}(N_{1∗}), …, \overline{φ}(N_{4∗})) = (φ(M_{1∗}), φ(M_{2∗}), φ(M_{3∗}), φ(M_{4∗})) in this case. □

From Claim 3 we deduce that for every ρ ∈ {R_{1}, R_{2}}, θ ∈ {R_{1}, τ_{3}, …, τ_{k}} with ρ ≠ θ, the inclusions pPol ρ ∩ pPol θ ⊂ C ⊂ pPol θ hold for no partial clone C. This concludes the proof of our theorem. □

Remark. From Theorem 4, we have that the partial clone pPol R_{1} ∩ pPol R_{2} is covered by the maximal partial clone pPol R_{1}. One can easily verify that this results holds for k = {0, 1}. The proof given above fails for the case ρ = R_{1} and θ = R_{2}. Indeed there is no guarantee that the partial functions g_{i} defined in Claim 3 above preserve the relation R_{2}. In fact the dual result for R_{2} does not hold, indeed there is at least one partial clone that strictly lies between pPol R_{1} ∩ pPol R_{2} and pPol R_{2}. To show this, we define the 7-ary relation λ := {(x_{1}, …, x_{7}) ∈ k^{7} | (x_{1}, x_{2}, x_{3}, x_{4}) ∈ R_{1}, (x_{1}, x_{2}, x_{5}, x_{6}) ∈ R_{2} and (x_{2}, x_{4}, x_{6}, x_{7}) ∈ R_{2}}. Then from Lemma 2 we have pPol R_{1}∩pPol R_{2} ⊆ pPol λ. Define the ternary partial function φ by setting

dom (φ) := {(1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 1)},

and

( \begin{matrix}φ(1, 0, 0) \\ φ(0, 1, 0) \\ φ(0, 0, 1) \\ φ(1, 1, 1) \end{matrix} ) = ( \begin{matrix}0 \\ 0 \\ 0 \\ 1 \end{matrix} ) .

Then clearly φ ∉ pPol R_{1}. The mathematical software Maple V was used to check that there is no 7 × 4 matrix A with rows from the set {(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (1, 1, 1, 1)} and such that the first three columns of A are in λ while the fourth is not, thus φ ∈ pPol λ. Consequently pPol λ ≠ pPol R_{1} and in view of the Theorem 4 we have pPol λ ⊆ pPol R_{2}. Define now the 4-ary partial function ψ by

dom (ψ) := {(0, 0, 0, 0), (1, 0, 1, 0), (0, 0, 1, 1), (0, 1, 1, 0), (1, 0, 0, 1), (1, 1, 1, 1), (1, 1, 0, 0)} and

( \begin{matrix}ψ(1, 0, 0, 1) \\ ψ(0, 0, 0, 0) \\ ψ(1, 0, 1, 0) \\ ψ(0, 0, 1, 1) \\ ψ(0, 1, 1, 0) \\ ψ(1, 1, 1, 1) \\ ψ(1, 1, 0, 0) \end{matrix} ) = ( \begin{matrix}1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \end{matrix} ) .

From the above matrix we see that ψ ∉ pPol λ (notice that (1, 0, 0, 0, 0, 1, 1) ∉ λ since (1, 0, 0, 0) ∉ R_{1}). We used Maple V to check that there is no 4 × 5 matrix with all rows from the set

{(0, 0, 0, 0, 0), (1, 0, 1, 0, 0), (0, 0, 1, 1, 0), (0, 1, 1, 0, 0), (1, 0, 0, 1, 1), (1, 1, 1, 1, 1), (1, 1, 0, 0, 1)}

and such that its first 4 columns belong to R_{2} while the fifth row does not, thus ψ ∈ pPol R_{2}. This shows that pPol R_{1} ∩ pPol R_{2} ⊂ pPol λ ⊂ pPol R_{2}.

We now focus our attention on the family of maximal partial clones {pPol τ_{h} | 3 ≤ h ≤ k}. We have

Theorem 5. Let h ∈ {4, …, k}, θ ∈ {R_{1}, R_{2}, τ_{3}, …, τ_{h−1}}. Then the partial clone pPol τ_{h} ∩ pPol θ is covered by the maximal partial clone pPol θ. Moreover for i = 1, 2, the partial clone pPol τ_{3} ∩ pPol R_{i} is covered by the maximal partial clone pPol R_{i}.

Proof. Let 3 ≤ h ≤ k, θ ∈ {R_{1}, R_{2}, τ_{3}, …, τ_{h−1}} if h ≥ 4 and θ ∈ {R_{1}, R_{2}} if h = 3. Let φ ∈ pPol θ \(pPol τ_{h} ∩pPol θ) be n-ary. As τ_{h} and θ are primitive relations, n ≥ 2. Moreover since φ ∉ pPol τ_{h}, there is an h × n matrix M = M_{ij} ∈ M(τ_{h}, dom(φ)) such that the hvector (φ(M_{1∗}), …, φ(M_{h∗})) ∉ τ_{h}. Thus |{φ(M_{1∗}), …, φ(M_{h∗})}| = h and so the φ(M_{i∗}) are pairwise distinct. We show that ⟨(pPol τ_{h} ∩ pPol θ) ∪ {φ}⟩ = pPol θ. Let φ_{1} be the n-ary partial function defined by dom (φ_{1}) = {M_{1∗}, …, M_{h∗}} and φ_{1}(M_{j∗}) = j −1, for j = 1, …, h. We have

Claim 1. φ_{1} ∈ ⟨(pPol τ_{h} ∩ pPol θ) ∪ {φ}⟩.

Proof (of the claim). Since ⟨(pPol τ_{h} ∩ pPol θ) ∪ {φ}⟩ is a strong partial clone, it contains the partial function φ′ := φ|_{D} where D := {M_{1∗}, …, M_{h∗}}. Let α be the unary partial function defined by dom (α) = {φ(M_{1∗}), …, φ(M_{h∗})} and α(φ(M_{j∗})) := j − 1 for all j = 1, …, h. As pPol τ_{h} ∩ pPol θ contains all unary partial functions, we have α ∈ ⟨(pPol τ_{h} ∩ pPol θ) ∪ {φ}⟩ and so φ_{1} := α[φ′] ∈ ⟨(pPol τ_{h} ∩ pPol θ) ∪ {φ}⟩. □

Claim 2. The partial clone ⟨(pPol τ_{h} ∩ pPol θ) ∪ \{φ\}⟩ contains an n-ary partial function \overline{φ} that satisfies dom (\overline{φ}) ⊆ \{0, …, h − 2\}^{n}, |dom (\overline{φ})| = h and Im (\overline{φ}) = \{0, …, h − 1\}. Proof (of the claim). Let j ∈ {1, …, h} and M_{∗j} = {M_{1j}, …, M_{hj}} be the j-th column of the matrix M. Since M_{∗j} ∈ τ_{h} we have |{M_{1j}, …, M_{hj}}| ≤ h − 1, and so one can define a surjective unary function α_{j} : {0, …, h − 2} → {M_{1j}, …, M_{hj}}. As pPol τ_{h} and pPol θ are Słupecki type partial clones, we have α_{j} ∈ pPol τ_{h} ∩ pPol θ. Let B_{ij} ∈ {0, …, h − 2} be such that α_{j}(B_{ij}) = M_{ij} for i = 1, …, n and j = 1, …, h. Consider now the n-ary partial function \overline{φ} := φ_{1}[a_{1}, …, α_{n}]. Then \overline{φ} ∈ ⟨(pPol τ_{h} ∩ pPol θ) ∪ \{φ\}⟩, dom (\overline{φ}) = \{(B_{11}, …, B_{1n}), …, (B_{h1}, …, B_{hn})\} and Im(\overline{φ}) =Im(φ_{1}) = \{0, 1, …, h − 1\}. □

We turn to the proof of the theorem. For 4 ≤ ℓ < k, denote by γ_{ℓ} the ℓ-ary partial function whose domain consists of the cyclic permutations of the ℓ-vector (0, 0, 1, …, ℓ − 2), (thus |dom (γ_{ℓ})| = ℓ), and defined by

γ_{ℓ}(x_{1}, …, x_{ℓ}) = \{ \begin{matrix}ℓ − 1, if (x_{1}, …, x_{ℓ}) = (0, 0, 1, …, ℓ − 2). \\ x_{1}, otherwise \end{matrix}

Note that Im (γ_{ℓ}) = {0, …, ℓ − 2, ℓ − 1}. We have

Claim 3. γ_{ℓ} ∈ pPol τ_{h} ∩ pPol R_{1} ∩ pPol R_{2} for all 3 ≤ h < ℓ ≤ k. Proof (of the claim). First notice that if (x_{1}, …, x_{ℓ}), (y_{1}, …, y_{ℓ}) ∈ dom (γ_{ℓ}) are such that x_{i} = y_{i} ≠ 0 for some i = 1, …, ℓ, then (x_{1}, …, x_{ℓ}) = (y_{1}, …, y_{ℓ}). Moreover as ℓ ≥ 4, any matrix with all rows in dom (γ_{ℓ}) contains at least two non-zero entries in each of its rows. Using these facts, one can easily show that if M ∈ M(R_{i}, dom(γ_{ℓ})) is 4 × ℓ matrix, then (γ_{ℓ}(M_{1∗}), γ_{ℓ}(M_{2∗})γ_{ℓ}(M_{3∗})γ_{ℓ}(M_{4∗})) ∈ R_{i}, for i = 1, 2. Consequently γ_{ℓ} ∈ pPol R_{i} for i = 1, 2. We now show that γ_{ℓ} ∈ pPol τ_{h} for all 3 ≤ h < ℓ < k. Let B ∈ M(τ_{h}, dom(γ_{ℓ})) be an h × ℓ matrix. Then every column of B has at least two equal entries. If a column contains two equal entries that are not zeros, then by the observation above the two rows containing these entries are equal, and consequently (γ_{ℓ}(B_{1∗}), …, γ_{ℓ}(B_{h∗})) ∈ τ_{h}. So suppose that every column of B contains at least two zeros. It follows that at least 2ℓ entries of B are zeros. On the other hand, as every ℓ-vector in dom (γ_{ℓ}) contains exactly 2 zeros, we have that B contains exactly 2h zeros with h < ℓ, a contradiction. Therefore γ_{ℓ} ∈ pPol τ_{h} for every 3 ≤ h < ℓ ≤ k. □

Set m := \frac{k! n}{h!} . We have

Claim 4. The partial clone ⟨(pPol τ_{h} ∩ pPol θ) ∪ {φ}⟩ contains an m-ary partial function ψ that satisfies dom (ψ) ⊆ {0, …, h − 2}^{m}, |dom (ψ)| = k and (Im ψ) = k.

Proof (of the claim). For i ≥ 0 let m_{i} := \frac{(h + i)!}{h!}n, thus m_{i} = (h + i)m_{i−1} for every i ≥ 1. We construct recursively, for every 0 ≤ i ≤ k − h, an m_{i}-ary partial function ψ_{i} as follows.

Let \overline{φ} be the n-ary partial function constructed in Claim 2 and set ψ_{0} := \overline{φ}. Consider now 1 ≤ i ≤ k − h. Define the m_{i}-ary partial function ψ_{i} from the (m_{i−1})-ary partial function ψ_{i−1} and the (h + i)-ary partial function γ_{h+i} by setting

(x_{1}, …, x_{m_{i}}) ∈ dom (ψ_{i}) ⟺

1) (x_{1}, …, x_{m_{i−1}}) ∈ dom (ψ_{i−1}), …, (x_{(h+i−1)m_{i−1}+1}, …, x_{m_{i}}) ∈ dom (ψ_{i−1}) and
2) (ψ_{i−1}(x_{1}, …, x_{m_{i−1}}), …, ψ_{i−1}(x_{(h+i−1)m_{i−1}+1}, …, x_{m_{i}})) ∈ dom (γ_{h+i}) and
ψ_{i}(x_{1}, …, x_{m_{i}}) := γ_{h+i}[ψ_{i−1}(x_{1}, …, x_{m_{i−1}}), …, ψ_{i−1}(x_{(h+i−1)m_{i−1}+1}, …, x_{m_{i}})].

It is easy to verify that |dom (ψ_{i})| = |dom (ψ_{i−1})| + 1 holds for every 1 ≤ i ≤ k − h. As |dom (ψ_{0})| = h (recall that ψ_{0} = \overline{φ} constructed in Claim 2), we have |dom (ψ_{i})| = h + i for all 0 ≤ i ≤ k − h.

Now from Claim 3 we have γ_{ℓ} ∈ pPol τ_{h} ∩ pPol R_{1} ∩ pPol R_{2} whenever ℓ > h, and so γ_{h+i} ∈ pPol τ_{h} ∩ pPol R_{1} ∩ pPol R_{2} for every i ≥ 1. Consequently

[ψ_{i} ∈ ⟨(pPol τ_{h} ∩ pPol θ) ∪ {φ}⟩ ⟹ ψ_{i+1} ∈ ⟨(pPol τ_{h} ∩ pPol θ) ∪ {φ}⟩], for all i ≥ 0. As ψ_{0} = \overline{φ} ∈ ⟨(pPol τ_{h} ∩ pPol θ) ∪ \{φ\}⟩, we have ψ_{i+1} ∈ ⟨(pPol τ_{h} ∩ pPol θ) ∪ \{φ\}⟩ for all 0 ≤ i < k − h.

Furthermore, one can check that for every 0 ≤ i < k−h, the equality Im (ψ_{i}) = Im (γ_{h+i}) implies Im (ψ_{i+1}) = Im (γ_{h+i+1}). This together with Im (ψ_{0}) = Im (γ_{h}) = {0, …, h − 1} gives Im (ψ_{k−h}) = Im (γ_{k}) = {0, …, k − 1} = k. Moreover it is straightforward to verify that dom (ψ_{k−h}) ⊆ {0, …, h − 2}^{m_{k−h}} and |dom (ψ_{k−h})| = k. Put ψ := ψ_{k−h} and note that

m_{k−h} = \frac{(h + (k − h))! n}{h!} = m. This completes the proof of Claim 4. □

We now can complete the proof of our theorem. Denote by Ψ the (k × m) matrix whose rows consist of dom (ψ) and such that ψ(Ψ_{1∗}) = 0, …, ψ(Ψ_{k∗}) = k − 1. Note that by construction of the partial function ψ, we have that every entry of the matrix Ψ belongs to the set {0, …, h−2}. Let t ≥ 2 and g ∈ pPol θ be t-ary. We show that g ∈ ⟨(pPol τ_{h}∩pPol θ)∪{φ}⟩. First define m unary total functions α_{1}, …, α_{m} by a_{j}(r) := Ψ_{(r+1)j}, for all r ∈ k and all j = 1, …, m. Notice that Im (α_{j}) = Ψ_{∗j}, the j-th column of the matrix Ψ. As pPol θ is Słupecki type partial clone, we have α_{j} ∈ pPol θ for every j = 1, …, m. Next define m t-ary partial functions g_{1}, …, g_{m} by setting g_{j}(x_{1}, …, x_{t}) := α_{j}[g(x_{1}, …, x_{t})], for all j = 1, …, m and all (x_{1}, …, x_{t}) ∈ dom (g). Since α_{1}, …, α_{m} are total functions we have

dom (g_{1}) = …, dom (g_{m}) = dom (g).

Moreover as g ∈ pPol θ, we have g_{j} = α_{j}[g] ∈ pPol θ for all j = 1, …, m.

As Im (g_{j}) ⊆ Im (α_{j}), the partial function g_{j} takes on values from Ψ_{∗j}, the j-th column of the matrix Ψ. Thus |Im (g_{j})| ≤ h − 1 and so g_{j} ∈ pPol τ_{h} for all j = 1, …, m. It follows that g_{j} ∈ pPol τ_{h} ∩pPol θ for all j = 1, …, m, and thus ψ[g_{1}, …, g_{m}] ∈ ⟨(pPol τ_{h} ∩pPol θ)∪{φ}⟩.

We show that g = ψ[g_{1}, …, g_{m}]. Clearly dom (ψ[g_{1}, …, g_{m}]) ⊆ dom (g_{1}) = dom (g). Let

x_{∼} ∈ dom (g), then x_{∼} ∈ ⋂_{j=1}^{n} dom (g_{j}) and (g_{1}(x_{∼}), …, g_{m}(x_{∼}) = (α_{1}[g(x_{∼})], …, α_{m}[g(x_{∼})]) which

is a row of the matrix Ψ, i.e., (g_{1}(x_{∼}), …, g_{m}(x_{∼}) ∈ dom (ψ). Now let x_{∼} ∈ dom (g) and let

g(x_{∼}) = r ∈ k. Then

ψ[g_{1}, …, g_{m}](x_{∼}) = ψ[α_{1}(r)), …, α_{m}(r)]
= ψ[Ψ_{(r+1)1}, …, Ψ_{(r+1)m}] (by definition of the functions α_{1}, …, α_{m})
= r = g(x_{∼}) (by definition of the matrix Ψ).

This shows that g ∈ ⟨(pPol τ_{h} ∩ pPol θ) ∪ {φ}⟩ and concludes the proof of our theorem. □

Remark. The proof above cannot be used to show that pPol τ_{h} ∩ pPol τ_{h′} is covered by pPol τ′_{h} if h < h′. Indeed take θ = τ_{h′} and let i in Claim 4 take the value h′ − h. But then γ_{h+(h′−h)} ∉ pPol τ_{h′} and so ψ_{h′−h} will not necessarily belong to the partial clone ⟨(pPol τ_{h} ∩ pPol θ) ∪ {φ}⟩. However the result holds, we use Romov’s definability Lemma to prove it. We have

Theorem 6. Let 3 ≤ h < h′ ≤ k. Then the partial clone pPol τ_{h} ∩ pPol τ_{h′} is covered by the maximal partial clone pPol τ_{h′}.

Proof. The proof here is similar to that of Theorem 4. Let λ be a t-ary irredundant relation such that

pPol τ_{h} ∩ pPol τ_{h′} ⊆ pPol λ.

We show that [pPol λ ≠ pPol τ_{h′} ⟹ pPol λ ⊆ pPol τ_{h}]. By Lemma 2, there is an h-ary relation ϱ and an h′-ary relation ϱ′ with {ϱ, ϱ′} covering the set {1, …, t} and such that

λ = {(x_{1}, …, x_{t}) ∈ k^{t} | (x_{i_{1}}, …, x_{i_{h}}) ∈ τ_{h} for all (i_{1}, …, i_{h}) ∈ ϱ and

(x_{j_{1}}, …, x_{j_{h′}}) ∈ τ_{h′} for all (j_{1}, …, j_{h′}) ∈ ϱ′}.

As in Theorem 4, we may assume that ϱ ≠ ∅ ≠ ϱ′ (otherwise pPol λ = pPol τ_{h} or pPol λ = pPol τ_{h′}). Moreover we may assume that no condition (x_{i_{1}}, …, x_{i_{h}}) ∈ τ_{h} or (x_{j_{1}}, …, x_{j_{h′}}) ∈ τ_{h′} is superfluous. Thus |{i_{1}, …, i_{h}}| = h for all (i_{1}, …, i_{h}) ∈ ϱ and |{j_{1}, …, j_{h′}}| = h′ for all (j_{1}, …, j_{h′}) ∈ ϱ′. Consequently t ≥ h′ > h. For notational ease let (1, …, h) ∈ ϱ. We have

Claim. (a_{1}, …, a_{h}, a_{1}, …, a_{1}) ∈ λ for all (a_{1}, …, a_{h}) ∈ τ_{h}. Proof (of the claim). Let (a_{1}, …, a_{h}) ∈ τ_{h}. Then (a_{1}, …, a_{h}, a_{1}, …, a_{1}) ∈ λ if and only if for every (i_{1}, …, i_{h}) ∈ ϱ and every (j_{1}, …, j_{h′}) ∈ ϱ′, we have (b_{i_{1}}, …, b_{i_{h}}) ∈ τ_{h} and (b_{j_{1}}, …, b_{j_{h′}}) ∈ τ_{h′}, where b_{s} = a_{s} for s ∈ {1, …, h} and b_{s} = a_{1} for s ∈ ({i_{1}, …, i_{h}} ∪ {j_{1}, …, j_{h′}}) \ {1, …, h}.

First we show that (b_{i_{1}}, …, b_{i_{h}}) ∈ τ_{h} for all (i_{1}, …, i_{h}) ∈ ϱ. If {i_{1}, …, i_{h}} = {1, …, h} then (b_{i_{1}}, …, b_{i_{h}}) ∈ τ_{h} holds trivially. Suppose therefore that {i_{1}, …, i_{h}} ≠ {1, …, h}. If |{i_{1}, …, i_{h}} ∩ {1, …, h}| ≤ h − 2, then a_{1} appears at least twice in the sequence b_{i_{1}}, …, b_{i_{h}} and consequently (b_{i_{1}}, …, b_{i_{h}}) ∈ τ_{h}. Suppose now that |{i_{1}, …, i_{h}} ∩ {1, …, h}| = h − 1. If 1 ∈ {i_{1}, …, i_{h}}, then again a_{1} appears at least twice in the sequence b_{i_{1}}, …, b_{i_{h}} and we are done. So let 1 ∉ {i_{1}, …, i_{h}}. As |{i_{1}, …, i_{h}} ∩ {1, …, h}| = h − 1, we may assume {i_{1}, …, i_{h}} = {i_{1}, 2, …, h} with i_{1} ∉ {1, …, h}. Then b_{i_{1}} = a_{1} and thus (b_{i_{1}}, …, b_{i_{h}}) = (a_{1}, …, a_{h}) ∈ τ_{h}.

We now show that (b_{j_{1}}, …, b_{j_{h′}}) ∈ τ_{h′} for all (j_{1}, …, j_{h′}) ∈ ϱ′. If {1, …, h} ⊆ {j_{1}, …, j_{h′}}, then |{b_{j_{1}}, …, b_{j_{h′}}}| ≤ h′−1, proving (b_{j_{1}}, …, b_{j_{h′}}) ∈ τ_{h′}. Otherwise |{1, …, h}∩{j_{1}, …, j_{h′}}| ≤ h − 1, and so a_{1} appears at least h′ − (h + 1) times (thus at least twice as h′ ≥ h + 1) in the sequence b_{j_{1}}, …, b_{j_{h′}}. Again this shows that (b_{j_{1}}, …, b_{j_{h′}}) ∈ τ_{h′} and completes the proof of our claim. □

We return to the proof of our theorem. Set

μ := {(x_{1}, …, x_{h}) ∈ k^{h} | (x_{1}, …, x_{h}, x_{1}, …, x_{1}) ∈ λ},

then in view of Lemma 2 we have pPol λ ⊆ pPol μ. We show that μ = τ_{h}. Let (x_{1}, …, x_{h}) ∈ τ_{h}. Then from the claim above (x_{1}, …, x_{h}, x_{1}, …, x_{1}) ∈ λ and so (x_{1}, …, x_{h}) ∈ μ. Conversely if (x_{1}, …, x_{h}) ∈ μ, then (x_{1}, …, x_{h}, x_{1}, …, x_{1}) ∈ λ and in view of (1, …, h) ∈ ϱ we have (x_{1}, …, x_{h}) ∈ τ_{h}, proving μ = τ_{h}.

We have shown that if λ is an irredundant relation such that pPol τ_{h} ∩ pPol τ_{h′} ⊆ pPol λ, then [pPol λ ≠ pPol τ_{h′} ⟹ pPol λ ⊆ pPol τ_{h}]. Consequently

pPol τ_{h} ∩ pPol τ_{h′} ⊂ C ⊂ pPol τ_{h′}

for no partial clone C, hence the partial clone pPol τ_{h} ∩ pPol τ_{h′} is covered by the maximal partial clone pPol τ_{h′}. □

Combining Theorems 4, 5 and 6 we get

Corollary 7. Let k ≥ 2 and M ≠ M′ be two strong maximal partial clones of Słupecki type on k. If (M, M′) ≠ (pPol R_{1}, pPol R_{2}), then the partial clone M ∩ M′ is covered by the maximal partial clone M′. □

It is shown in [3] that no strong maximal partial clone of Słupecki type on k is finitely generated (this result was shown earlier in [12] for k = 2). As the intersection of two strong maximal partial clones of Słupecki type is covered by (at least) one of them, we get

Corollary 8. Let k ≥ 2 and M ≠ M′ be two strong maximal partial clones of Słupecki type on k. Then the partial clone M ∩ M′ is not finitely generated. □

4. Intersections of Słupecki type partial clones with M_{k}

In this section, we consider the intervals of partial clones [M_{k} ∩ pPol θ, pPol θ] and [M_{k} ∩ pPol θ, M_{k}] on k, where θ ∈ {R_{1}, R_{2}, τ_{3}, …, τ_{k}}. First notice that intervals of the type [M_{k} ∩ pPol θ, M_{k}] are quite easy to describe. Indeed the equality Pol R_{2} = ⟨Op^{(1)}(k)⟩ follows from Burle’s Theorem ([4]) and is shown in [10]. Again from Burle’s Theorem we have that the unrefinable chain

Pol R_{2} ∪ {p_{n} | n ≥ 1} ⊂ Pol R_{1} ∪ {p_{n} | n ≥ 1} ⊂ Pol τ_{3} ∪ {p_{n} | n ≥ 1} ⊂ …

⊂ Pol τ_{k} ∪ {p_{n} | n ≥ 1} ⊂ Op(k) ∪ {p_{n} | n ≥ 1},

is the interval of partial clones [Pol R_{2} ∪ {p_{n} | n ≥ 1}, Op(k) ∪ {p_{n} | n ≥ 1}]. Thus for θ ∈ {R_{1}, R_{2}, τ_{3}, …, τ_{k}}, the interval [pPol θ ∩ M_{k}, M_{k}] is simply a subchain of the unrefinable chain

pPol R_{2} ∩ M_{k} ⊂ pPol R_{1} ∩ M_{k} ⊂ pPol τ_{3} ∩ M_{k} ⊂ … ⊂ pPol τ_{k} ∩ M_{k} ⊂ M_{k}.

We now focus on intervals of the type [M_{k} ∩ pPol θ, pPol θ]. We first need to recall the descriptions of the clones Pol θ for θ ∈ {R_{1}, τ_{3}, …, τ_{k}}.

Recall that an n-ary function f is said to be essentially unary if there are 1 ≤ i ≤ n and g ∈ Op^{(1)}(k) such that f(x_{1}, …, x_{n}) = g(x_{i}) holds for all (x_{1}, …, x_{n}) ∈ k^{n}. Moreover f is quasilinear if there are ϕ_{0} : {0, 1} → k and ϕ_{i} : k → {0, 1} (i = 1, …, n) such that

f(x_{1}, …, x_{n}) = ϕ_{0}(ϕ_{1}(x_{1}) + … + ϕ_{n}(x_{n}))

for all (x_{1}, …, x_{n}) ∈ k^{n}, where the sum is mod 2 on {0, 1}.

It is well known that ⟨Op^{(1)}(k)⟩ is the set of all essentially unary functions on k and Pol R_{1} is the set of all functions that are essentially unary or quasilinear. Furthermore for 3 ≤ h ≤ k, Pol τ_{h} is the set of all functions f that are essentially unary or satisfy |Im f| ≤ h−1 (see e.g., [16] and [21] for details).

We start with the maximal partial clone pPol R_{1}. We will need the following notation here. If C is a total clone on k, then we denote the strong closure of C by Str (C), that is Str (C) := {g ∈ Par(k) | g ≤ f for some f ∈ C}. Notice that for every clone C, Str (C) is a strong partial clone on k. Moreover, if ρ is an irredundant relation on k, then Str (Pol ρ) ⊆ pPol ρ, with the equality holding if and only if every partial function that preserve ρ can be extended to a total function that preserve ρ (see [3] for details). We have

Theorem 9. Let k ≥ 2. Then the interval of partial clones [Str (Pol R_{1}), pPol R_{1}] is of continuum cardinality on k.

Proof. This theorem is shown in [1] for k = 2. We use the proof given in [1] to establish the result for k ≥ 3. In the proof below, we will use the definition of a partial clone involving the three Mal’tsev operations ζ, τ, Δ as well as the composition ⋆ of partial functions (see [8],[9] for partial clones and [15] for the general theory). Moreover, we will denote by Op(2) (Par(2)) the set of all functions (partial functions) on {0, 1}. Furthermore let Pol_{2} R_{1} ⊂ Op(2) (pPol_{2} R_{1} ⊂ Par(2)) be the clone (the partial clone) of all functions (partial functions) that preserve the relation R_{1} on {0, 1}. Let

Q := {C ⊆ Par(2) | C is a partial clone and Str (Pol_{2} R_{1}) ⊆ C ⊆ pPol_{2} R_{1}}.

The equality |Q| = 2^{ℵ_{0}} is shown in [1]. Our main idea is to construct a one-to-one map from the subset Q of Par(2) to the interval of partial clones [Str (Pol R_{1}), pPol R_{1}] on k. For every C ∈ Q we define a set Ĉ ⊆ Par(k) as follows:

Ĉ := ⟨Par^{(1)}(k)⟩ ⋃

⋃_{n≥1}{f ∈ Par^{(n)}(k) | for some t ≥ 1, ∃ F ∈ C ∩ Par ^{(t)}(2), ∃φ_{0}, φ_{1}, …, φ_{t} ∈ Op^{(1)}(k) ,

∃{i_{1}, i_{2}, …, i_{t}} ⊆ {1, 2, …, n} such that the following hold :

|Im (φ_{0})| ≤ 2, and

Im (φ_{i}) ⊆ {0, 1} ∀i ∈ {1, …, t} and,

f(x_{1}, …, x_{n}) = φ_{0}(F (φ_{1}(x_{i_{1}}), φ_{2}(x_{i_{2}}), …, φ_{n}(x_{i_{t}}))) for all (x_{1}, …, x_{n}) ∈ dom (f)}.

Recall that ⟨Par^{(1)}(k)⟩ is the partial clone generated by all partial unary functions on k. We show that Ĉ is a partial clone on k.

First {ζ(f), τ(f), Δ(f)} ⊂ Ĉ for every f ∈ Ĉ follows from {ζ(F), τ(F), Δ(F)} ⊂ C for every F ∈ C. Now let f ∈ Ĉ, g ∈ Ĉ ∩ Par^{(1)}(k). Then g ⋆ f ∈ Ĉ is immediate and f ⋆ g ∈ Ĉ follows from Im (φ_{1}) ⊆ {0, 1} ⟹ Im (φ_{1}⋆g) ⊆ {0, 1}. Let now f, g ∈ Ĉ\⟨Par^{(1)}(k)⟩, where f is n-ary and g is m-ary. Then (w.l.o.g.) there are F, G ∈ C, f_{0}, …, f_{n}, g_{0}, …, g_{m} ∈ Op^{(1)}(k) with |Im (f_{0})| ≤ 2, |Im (g_{0})| ≤ 2, Im (h) ⊆ {0, 1} for all h ∈ {f_{1}, …, f_{n}, g_{1}, …, g_{m}} and

f(x_{1}, …, x_{n}) = f_{0}(F (f_{1}(x_{1}), f_{2}(x_{2}), …, f_{n}(x_{n})))

and

g(x_{1}, …, x_{m}) = g_{0}(G(g_{1}(x_{1}), g_{2}(x_{2}), …, g_{m}(x_{m}))).

hold for every (x_{1}, …, x_{n}) ∈ dom (f) and every (x_{1}, …, x_{m}) ∈ dom (g). Thus

\begin{matrix}(f ⋆ g)(x_{1}, …, x_{m+n−1}) = f(g(x_{1}, …, x_{m}), x_{m+1}, …, x_{m+n−1}) = \\ f_{0}(F (f_{1}(g_{0}(G(g_{1}(x_{1}), g_{2}(x_{2}), …, g_{m}(x_{m})))), f_{2}(x_{m+1}), …, f_{n}(x_{m+n−1}))). \end{matrix}

Since Par^{(1)}(2) ⊂ C and G ∈ C, there is a function H ∈ C with

H(g_{1}(x_{1}), …, g_{m}(x_{m})) = f_{1}(g_{0}(G(g_{1}(x_{1}), g_{2}(x_{2}), …, g_{m}(x_{m})))).

Put T := F ⋆ H. Then T ∈ C and from

(f ⋆ g)(x_{1}, …, x_{m+n−1}) =
f_{0}(F (H(g_{1}(x_{1}), …, g_{m}(x_{m})), f_{2}(x_{m+1}), …, f_{n}(x_{m+n−1}))) =
f_{0}(T (g_{1}(x_{1}), g_{2}(x_{2}), …, g_{m}(x_{m}), f_{2}(x_{m+1}), …, f_{n}(x_{m+n−1}))),

we get f ⋆ g ∈ Ĉ. Hence Ĉ is a partial clone on k.

Furthermore, from the characterization of Pol R_{1} given above, we see that Ĉ ∩ Op(k) = Pol R_{1}. Now from

⋃_{n≥1}{f ∈ Par(2) | ∃f_{1} ∈ Ĉ ∩ Par^{(n)}(k) such that ∀a⃗ ∈ {0, 1}^{n}, f_{1}(a⃗) = f(a⃗)} = C,

for all C ∈ Q, we deduce

∀C, C′ ∈ Q; C ≠ C′ ⟹ Ĉ ≠ Ĉ′.

This concludes the proof of our theorem. □

Now as pPol R_{1} ∩ Op(k) = Pol R_{1} ⊂ Str (Pol R_{1}) and {p_{n} | n ≥ 1} ⊂ Str (Pol R_{1}), we have pPol R_{1} ∩ M_{k} ⊂ Str (Pol R_{1}) , and so from Theorem 9 we deduce

Corollary 10. Let k ≥ 2. The interval of partial clones [pPol R_{1} ∩ M_{k}, pPol R_{1}] has the cardinality of continuum on k. □

We now prove a result similar to Theorem 10 for the each member of the family {pPol τ_{3}, …, pPol τ_{k}}. We have

Theorem 11. Let 3 ≤ h ≤ k. Then the interval of partial clones [Str (Pol τ_{h}), pPol τ_{h}] is of continuum cardinality on k.

Proof. For n ≥ 2, denote by F_{2n+h} the family of all (binary) equivalence relations ε on the set {1, …, 2n + h} such that either 1) ε has at most h − 1 equivalence classes or 2) ε has exactly h equivalence classes and these h classes satisfy the following: h − 2 of them are singleton (thus consist of one element each), one has size 2 and finally one has size 2n. For example, if h = 5 and n = 3, then the equivalence ε on the set {1, …, 11} with classes {1}; {2}; {3}; {4, 5}; and {6, 7, 8, 9, 10, 11} belongs to F_{11}.

Furthermore, for every n ≥ 2, let σ_{2n+h} be the relation of arity (2n + h) on the set {1, …, 2n+ h} defined by

σ_{2n+h} := ⋃_{ε∈F_{2n+h}} Δ_{ε} .

Thus for every (x_{1}, …, x_{2n+h}) ∈ k^{2n+h}, (x_{1}, …, x_{2n+h}) ∈ σ_{2n+h} ⟺ |{x_{1}, …, x_{2n+h}}| ≤ h−1 or |{x_{1}, …, x_{2n+h}}| = h with 1) h−2 symbols occuring each once and 2) one symbol occuring exactly twice and 3) one symbol occuring 2n times in x_{1}, …, x_{2n+h} .

Notice that σ_{2n+h} is a totally symmetric relation. Moreover since σ_{2n+h} is a primitive relation, pPol σ_{2n+h} contains all partial unary functions on k, and consequently it contains the set ⟨Par^{(1)}(k)⟩ of all essentially unary functions on k. Moreover since any at most (h−1)- valued (2n + h)-vector of k belongs to σ_{2n+h}, pPol σ_{2n+h} contains all at most (h − 1)-valued functions on k, thus Pol τ_{h} ⊆ pPol σ_{2n+h}. As pPol τ_{h} is a strong partial clone, we have Str (Pol τ_{h}) ⊆ pPol σ_{2n+h}. On the other hand

τ_{h} = {(x_{1}, …, x_{h}) ∈ k^{h}|(x_{1}, …, x_{1}, x_{2}, …, x_{h}) ∈ σ_{2n+h}} .

Indeed, if (x_{1}, …, x_{h}) ∉ τ_{h}, then the x_{i}’s are all pairwise distinct, and so the vector v⃗ := (x_{1}, …, x_{1}, x_{2}, …, x_{h}) is h-valued. As the equivalence relation ker(v⃗) := {(i, j) ∈ {1, …, h}^{2}| x_{i} = x_{j}} has h − 1 equivalence classes of size 1, we have v⃗ ∉ σ_{2n+h}. On the other hand, if (x_{1}, …, x_{h}) ∈ τ_{h}, then |{x_{1}, …, x_{h}}| ≤ h − 1 and so v⃗ := (x_{1}, …, x_{1}, x_{2}, …, x_{h}) ∈ σ_{2n+h} by definition of σ_{2n+h}. This shows that pPol σ_{2n+h} ⊆ pPol τ_{h}, and consequently, Str (Pol τ_{h}) ⊆ pPol σ_{2n+h} ⊆ pPol τ_{h} for all n ≥ 1.

Our goal is to show that the partial clones pPol σ_{2n+h} give a family of partial clones of continuum cardinality in the interval [Str (Pol τ_{h}), pPol τ_{h}].

We define a family of partial functions for this task. For every m ≥ 1, denote by v⃗_{0} the (2m + h)-vector over k

v⃗_{0} := (0, 1, …, h − 3, h − 2, h − 2, h − 1, …, h − 1).

Notice that the (2m+h)-vector v⃗_{0} contains one symbol from each of 0, 1, …, h−3, two symbols h−2 and 2m symbols h−1. Furthermore, let α be the cyclic permutation (0 1 … 2m+h−1) and for j = 0, …, 2m + h − 1, let

v⃗_{j} := (x_{α^{j}(0)}, x_{α^{j}(1)}, …, x_{α^{j}(2m+h−1)}),

where

(x_{0}, …, x_{2m+h−1}) := v⃗_{0}.

Thus

v⃗_{1} = (1, …, h − 3, h − 2, h − 2, h − 1, …, h − 1, 0), …
v⃗_{h−2} = (h − 2, h − 2, h − 1, …, h − 1, 0, …, h − 3),
v⃗_{h−1} = (h − 2, h − 1, …, h − 1, 0, …, h − 3, h − 2),

while

v⃗_{h} = (h − 1, …, h − 1, 0, …, h − 3, h − 2, h − 2), …

and

v⃗_{2m+h−1} = (h − 1, 0, …, h − 3, h − 2, h − 2, h − 1, …, h − 1).

We now define the (2m + h)-ary partial function φ_{2m+h} by

dom (φ_{2m+h}) := {v⃗_{0}, v⃗_{1}, …, v⃗_{2m+h−1}},

and

φ_{2m+h}(x_{1}, …, x_{2m+h}) = \{ \begin{matrix}h − 1 if (x_{1}, …, x_{2m+h}) = v⃗_{h−1} \\ x_{1} otherwise \end{matrix}

Notice that φ_{2m+h}(v⃗_{j}) = j for j = 0, …, h − 1. Also φ_{2m+h}(v⃗_{ℓ}) = e_{1}^{2m+h}(v⃗_{ℓ}) for all ℓ = 0, …, 2m + h − 1, ℓ ≠ h − 1.

We have Claim Let n, m ≥ 1. Then φ_{2m+h} ∈ pPol σ_{2n+h} ⟺ n ≠ m. Proof. (⟹) Let n = m and consider the square matrix A of size 2n + h whose 2n + h rows are the vectors of the domain of φ_{2n+h}. Then in every column of A, the symbols 0, 1, …, h−3 appear exactly once, the symbol h − 2 appears exactly twice while the symbol h − 1 appears 2n times. Thus every column of A belongs to σ_{2n+h}. Applying φ_{2n+h} on the rows of A we get a (2n + h)-vector where each of 0, 1, …, h − 3, h − 2 appears exactly once while the symbol h − 1 appears 2n + 1 times. So if A_{[i∗]} denotes the i-th row of A, we have

(φ_{2n+h}(A_{[1∗]}), …, φ_{2n+h}(A_{[2n+h∗]})) ∉ σ_{2n+h},

proving φ_{2n+h} ∉ pPol σ_{2n+h}.

(⟸) Let A be a matrix of size (2n + h) × (2m + h) with all rows A_{[1∗]}, …, A_{[2n+h∗]} ∈ dom (φ_{2m+h}), all columns A_{[∗1]}, …, A_{[∗2m+h]} ∈ σ_{2n+h} and such that

(φ_{2m+h}(A_{[1∗]}), …, φ_{2m+h}(A_{[2n+h∗]})) ∉ σ_{2n+h}.

We show that m = n. For 1 ≤ j ≤ 2m + h, denote the (2m + h)-ary operation j-th projection by e_{j}. Since σ_{2n+h} is a totally symmetric relation, the rows of the matrix A may be listed in any convenient order. As

(φ_{2m+h}(A_{[1∗]}), …, φ_{2m+h}(A_{[2n+h∗]})) ∉ σ_{2n+h},

we have that (φ_{2n+h}(A_{[1∗]}), …, φ_{2m+h}(A_{[2n+h∗]})) is an h-valued vector over k. Thus each of v⃗_{0}, v⃗_{1}, …, v⃗_{h−2} is a row of the matrix A. We will assume that the first h − 1 rows of A are v⃗_{0}, v⃗_{1}, …, v⃗_{h−2} respectively. Now if v⃗_{h−1} is not a row of A, then φ_{2m+h}(v⃗) = e_{1}(v⃗) for every row v⃗ of the matrix A, which is a contradiction with the choice of A. So let v⃗_{h−1} be the h-th row of A. It follows that the last column A_{[∗ 2m+h]} of A is an h-valued vector.

On the other hand, as φ_{2m+h}(v⃗_{i}) = e_{2m+h}(v⃗_{i}) + 1 (mod h), for all i = 0, …, h, at least one row of A is different from v⃗_{0}, v⃗_{1}, …, v⃗_{h}. Now as every v⃗ ∈ dom (φ_{2m+h}) different from v⃗_{0}, v⃗_{1}, …, v⃗_{h} has both its first and last entries equal to h − 1, we deduce on one hand that the first column A_{[∗1]} of A is an h-valued vector and, on the other hand, that the last column A_{[∗ 2m+h]} of A contains at least two entries equal to h − 1. Moreover as v⃗_{h−2} and v⃗_{h−1} are two rows of A, we deduce that at least two entries of A_{[∗1]} are h − 2. We have three cases: Case 1. There is a j ∈ {0, 1, …, h − 3} such that j is repeated 2n times in A_{[∗1]}. Since σ_{2n+h} is a totally symmetric relation, we may assume that

A_{[∗1]} = (0, 1, …, h − 3, h − 2, h − 2, h − 1, j …, j),

and so

(φ_{2m+h}(A_{[1∗]}), …, φ_{2m+h}(A_{[2n+h∗]})) =

(0, 1, …, h − 3, h − 2, h − 1, h − 1, j …, j) ∈ σ_{2n+h},

a contradiction with the choice of A. Case 2. h − 2 is repeated 2n times in A_{[∗1]}. Thus 2n rows of A belong to the set {v⃗_{h−2}, v⃗_{h−1}} and so 2n entries of the last column A_{[∗ 2m+h]} belong to {h − 3, h − 2}. However since each of h − 3 and h − 2 appears at least once and h − 1 appears twice in A_{[∗ 2m+h]}, we obtain the contradiction A_{[∗ 2m+h]} ∉ σ_{2n+h}. Case 3. h − 1 appears 2n times in A_{[∗1]}. Notice that in this case each of v⃗_{0}, v⃗_{1}, …, v⃗_{h−1} is a row exactly once in A. Now since every element of dom (φ_{2m+h}) whose first entry is h−1 has its last entry from the set {h − 2, h − 1}, and since h − 1 appears at least once in A_{[∗ 2m+h]} (as v⃗_{0} is a row of A), we deduce that at least one row of A has the form (h − 1, …, h − 1).

Suppose that h − 2 appears 2n times in the last column A_{[∗ 2m+h]}. Then as v⃗_{h−1} = (h − 2, h − 1, …, h − 1, 0, 1, …, h − 2) is a row of A, we have that 2n − 1 rows of A are equal to v⃗_{h}. Now as v⃗_{0}, v⃗_{1} are rows of A, the symbol h − 1 appears twice in the next to last column A_{[∗ 2m+h−1]}. If v⃗_{h+1} = (h − 1, …, h − 1, 0, …, h − 2, h − 2, h − 1) is not a row of A, then the symbol h−2 will occur an odd number of times ( ≥ 3) in the next to last column A_{[∗ 2m+h−1]}, a contradiction. It follows that v⃗_{h+1} is a row of A and consequently the 2m + h−2-th column A_{[∗ 2m+h−2]} is an h-valued vector and contains exactly three symbols h − 1, a contradiction.

It follows that the symbol h − 2 appears exactly twice in the last column A_{[∗ 2m+h]} and so h − 1 appears 2n times in that last column A_{[∗ 2m+h]}. Moreover this shows that exactly one row of A is equal to v⃗_{h}.

Suppose now that m = 1 and n ≠ m, thus n ≥ 2. As each of v⃗_{0}, v⃗_{1}, …, v⃗_{h−1} and v⃗_{h} is a row exactly once of A, we have that v⃗_{h+1} (in this case equal to (h−1, 0, 1, …, h−2, h−2, h−1) ) is a row 2n − 1 times of A. Then the symbol 0 appears 2n − 1 times in the second column A_{[∗2]}, a contradiction.

We assume now that m ≥ 2. So far we have shown each of the vectors v⃗_{0}, …, v⃗_{h} is a row exactly once in A. Now the symbol h − 1 appears at least twice in the next to last column A_{[∗ 2m+h−1]}, and by a similar argument as above we can show that the vector v⃗_{h+1} is a row exactly once of A. Now let 1 ≤ i ≤ 2n − 1 and suppose that v⃗_{0}, …, v⃗_{h}, …, v⃗_{h+i} are the first h + i + 1 rows of A and that each of these vectors is a row exactly once of A.

Then A_{[∗2n+h−(i)]} (i.e., the (2n+h−(i))-th column of A) is an h-valued vector and contains two symbols h − 2 and at least 3 symbols h − 1. Thus all other entries of that column must be h − 1. On the other hand, A_{[∗2n+h−(i+1)]} is an h-valued vector and contains symbol h − 2 and at least 4 symbols h − 1. Thus this column must contain one more symbol h − 2. As every row of A different from v⃗_{0}, …, v⃗_{h−1}, v⃗_{h} has its first entry as well as its last entry equal to h − 1, we see that one row of A must be (h − 1, …, h − 2, h − 2, h − 1, …, h − 1) where the number of the consecutive h − 1 on the right is i + 1, i.e., v⃗_{h+i+1} is also a row of A. If v⃗_{h+i+1} appears more than once as a row of A, then each of the symbols h − 2 and h − 1 would be at least 3 times in the column A_{[∗2n+h−(i+1)]}, a contradiction.

We have shown that each of the vectors in dom (φ_{2m+h}) is a row exactly once of A. Thus each row and each column of A contains exactly 2 symbols h − 2. Counting in two different ways the number of symbols h − 2 in A leads to n = m. □

We turn to the proof of our theorem. Let P (N) be the power set of N = {1, 2, …}. From the above claim, the correspondence χ : P (N) → [Str (Pol τ_{h}), pPol τ_{h}] defined by χ(X) := ⋂_{n∉X} pPol σ_{2n+h} is a one-to-one mapping, which completes the proof of our Theorem. □

As for the case of the relation R_{1}, we deduce

Corollary 12. Let 3 ≤ h ≤ k. Then the interval of partial clones [pPol τ_{h} ∩ M_{k}, pPol τ_{h}] has the cardinality of continuum on k. □

On the other hand, a result similar to Corollary 10 is established for the relation R_{2}. The relations used for the proof can be found in [9], Theorem 11. We have Corollary 13. ([10], Corollary 7) Let k ≥ 2. The interval of partial clones [pPol R_{2} ∩ M_{k}, pPol R_{2}] has cardinality of the continuum on k. □

Combining Corollaries 10, 12 and 13, we get

Corollary 14. Let k ≥ 2, pPol θ be any maximal partial clone of Słupecki type on k. Then the interval of partial clones [pPol θ ∩ M_{k}, pPol θ] has cardinality of the continuum on k. □

Remark. This study yields several open problems, we mention some of them here.

1. Theorem 4 states that the interval of partial clones [pPol R_{1} ∩ pPol R_{2}, pPol R_{1}] consists of the two bounds only. As shown after Theorem 4, this does not hold for the interval [pPol R_{1} ∩ pPol R_{2}, pPol R_{2}]. So one may ask for a description of this interval. In particular, is this interval finite?

2. The results established in Section 3 give families of partial clones covered by the maximal partial clones pPol R_{1}, pPol R_{2}, pPol τ_{3}, …, pPol τ_{h}. So one may ask here for a description of all partial clones covered by pPol R_{1}, pPol R_{2}, pPol τ_{3}, …, pPol τ_{h}.

3. Given a maximal partial clone of the form pPol ρ, describe the interval of partial clones [Pol ρ, pPol ρ]. Notice that this problem was addressed in Section 4 for Słupecki type maximal partial clones. The description of all maximal partial clones on k is given in [6], [8] and [19].

References

[1] Alekseev. V. B.; Voronenko, L. L.: Some closed classes in the partial two-valued logic. (Russian). Diskretn. Mat. 6 (4) (1994), 58–79.

[2] Börner, F.; Haddad, L.; Pöschel, R.: Minimal partial clones. Bull. Austral. Math. Soc. 44 (1991), 405–415.

[3] Börner, F.; Haddad, L.: Maximal Partial Clones with no finite basis. Preprint 1997, to appear in: Algebra Universalis.

[4] Burle, G. A.: Classes of k-valued logic which contain all functions of a single variable. (Russian). Diskret. Analiz (Novosibirsk) 10 (1967), 3–7.

[5] Freivald, T. V.: Completeness criterion for partial functions of logic and many-valued logic algebras (Russian). Dokl. Akad. Nauk SSSR 167 (1966), 1249–1250, translated as Soviet Physics Dokl. 11 (1966), 288–289.

[6] Haddad, L.; Rosenberg, I. G.: Crière général de complètude pour les algèbres partielles finies. C. R. Acad. Sci. Paris, Sér. I, 304 (1987), 507–507.

[7] Haddad, L.; Rosenberg, I. G.; Schweigert, D.: A maximal partial clone and a Słupeckitype criterion. Acta Sci. Math. 54 (1990), 89–98.

[8] Haddad, L.; Rosenberg, I. G.: Completeness theory for finite partial algebras. Algebra Universalis 29 (1992), 378–401.

[9] Haddad, L.; Rosenberg, I. G.: Partial clones containing all permutations. Bull. Austral. Math. Soc. 52 (1995), 263–278.

[10] Haddad, L.: On the depth of the intersection of two maximal partial clones. Multiple-Valued Logic, an International Journal, to appear.

[11] Lau, D.: Bestimmung der Ordnung maximaler Klassen von Funktionen der k-wertigen Logik. Z. Math. Logik u. Grundl. Math. 24 (1978), 79–96.

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

[13] Mal’tsev, A. I.: Iterative algebras and Post’s varieties. (Russian). Algebra i Logika 5 No. 2 (1966), 5–24. English translation in: The metamathematics of algebraic systems, Collected papers 1936-67. Studies in Logics and Foundations of Mathematics, vol. 66, North-Holland 1971.

[14] Mal’tsev, A. I.: A strengthening of the theorems of Słupecki and Iablonskii. (Russian). Algebra i Logika 6 No. 2 (1967), 61–75.

[15] Pöschel, R.; Kaluz̆nin, L. A. Funktionen- und Relationenalgebren. VEB Deutscher Verlag der Wissenschaften, Berlin 1979.

[16] Rosenberg, I. G.: Composition of functions on finite sets, completeness and relations, a short survey. In D. Rine (ed.), Multiple-valued Logic and Computer Science, 2nd edition, North-Holland, Amsterdam (1984), 150–192.

[17] Romov, B. A.: Maximal subalgebras of algebras of partial multivalued logic functions. Kibernetika; English translation in: Cybernetics 1 (1980), 31–41.

[18] Romov, B. A.: The algebras of partial functions and their invariants. Kibernetika; English translation in: Cybernetics 17 (1981), 157–167.

[19] Romov, B. A.: The completeness problem in the algebra of partial functions of finitevalued logic. Kibernetika; English translation in: Cybernetics 26 (1990), 133–138.

[20] Słupecki. J.: Completeness criterion for systems of many-valued propositional calculus. (Polish). Comptes Rendus des Séances de la Société des Sciences et Lettres de Varsovie Cl. II,32 (1939), 102–109. English Translation: Studia Logica 30 (1972), 153–157.

[21] Szendrei, A.: Clones in Universal Algebra. Séminaires de Mathématiques Supérieures 99, Université de Montréal, Canada 1986.

Received November 17, 1998; revised version February 25, 2000