COMPLEXITY OF EQUATIONS VALID IN ALGEBRAS OF RELATIONS

Part II: Finite axiomatizations.

Hajnal Andréka^{1}

Abstract. We study algebras whose elements are relations, and the operations are natural “manipulations” of relations. This area goes back to 140 years ago to works of De Morgan, Peirce, Schröder (who expanded the Boolean tradition with extra operators to handle algebras of binary relations). Well known examples of algebras of relations are the varieties RCA_{n} of cylindric algebras of n-ary relations, RP EA_{n} of polyadic equality algebras of n-ary relations, and RRA of binary relations with composition. We prove that any axiomatization, say E, of RCA_{n} has to be very complex in the following sense: for every natural number k there is an equation in E containing more than k distinct variables and all the operation symbols, if 2 < n < ω. Completely analogous statement holds for the case n ≥ ω. This improves Monk’s famous non-finitizability theorem for which we give here a simple proof. We prove analogous nonfinitizability properties of the larger varieties SNr_{n}CA_{n+k}. We prove that the complementation-free (i.e. positive) subreducts of RCA_{n} do not form a variety. We also investigate the reason for the above “non-finite axiomatizability” behaviour of RCA_{n}. We look at all the possible reducts of RCA_{n} and investigate which are finitely axiomatizable. We obtain several positive results in this direction. Finally, we summarize the results and remaining questions in a figure. We carry through the same programme for RP EA_{n} and for RRA. By looking into the reducts we also investigate what other kinds of natural algebras of relations are possible with more positive behaviour than that of the well known ones. Our investigations have direct consequences for the logical properties of the n-variable fragment L_{n} of first order logic. The reason for this is that RCA_{n} and RP EA_{n} are the natural algebraic counterparts of L_{n} while the varieties SNr_{n}CA_{n+k} are in connection with the proof theory of L_{n}.

This paper appears in two parts. The first part contains the non-finite axiomatizability results. The present second part contains finite axiomatizations of some fragments (reducts) together with a figure summarizing the finite and non-finite axiomatizability results in this area and the problems left open.

1This work contains the material in the author’s Doctoral Dissertation with Hungar. Acad. Sci., Budapest 1991. Research supported by Hungarian National Foundation for Scientific Research OTKA grants No T16448, T7255.

CONTENTS

Part I. Nonfinite axiomatizability of algebras of relations of higher rank (Simple proof for nonfinitizability in algebraic logic.) Introduction

Theorem 1 (simple proof) Theorem 2 (neat reducts) Theorem 3 (diagonals in case n ≥ ω) Theorem 4 (diagonals in case n < ω) Theorem 5 (unary, additive, permutation invariant functions don’t help) Theorem 6 (diagonals in the polyadic case) Theorem 7 (complementation) Theorem 8 (complementation in RRA)

References

Part II. Complementary finite axiomatizability results Proposition 1 (axiomatization of permutations) Proposition 2 (axiomatization of diagonals) Proposition 3 (axiomatization of diagonals and permutations) Figure 1 (summary of results) Figure 2 (interconnections of operations of RRA)

References

This is second part of the paper Complexity of equations valid in algebras of relations. This part is self-contained. We use the notation of the first part, but we introduce less usual notation.

In this part we prove some “positive” axiomatizability theorems. These theorems are complementing the results in Part I. We prove that the Boolean operations together with the permutations p_{ij}, or together with the diagonals d_{ij}, or together with both, are finitely axiomatizable. So in a sense, yet the cylindrifications cause the complexity of the equations valid in algebras of relations. At the end of the paper we summerize both the positive and the negative axiomatizability theorems on two figures, where we also indicate the questions that remained open.

Let U be a set. Then P(U) denotes the powerset of U and 𝔓(U) denotes the Boolean algebra of all subsets of U. Let n be an ordinal. Then ^{n}U is the set of all U–termed sequences of length n, and thus P(^{n}U) is the set of all n–ary relations on U. We consider n as the set of all smaller ordinals, and a sequence s ∈ ^{n}U to be a map from n to U. Thus, if σ : n → n, then s ∘ σ : n → U is another sequence, the sequence s “rearranged” according to σ. Let s ∈ ^{n}U, i < n and u ∈ U. Then s(i/u) denotes the sequence we obtain from s by replacing its i–th value with u. Let i, j < n and σ : n → n. The unary operations p_{ij}^{U}, p_{σ}^{U}, s_{ij}^{U}, c_{i}^{U} on n–ary relations over U and the constant d_{ij}^{U} ∈ P(^{n}U) are defined as

p_{ij}^{U}(X) = {s(i/s_{j})(j/s_{i}) : s ∈ X}
p_{σ}^{U}(X) = {s ∘ σ : s ∈ X}
s_{ij}^{U}(X) = {s(i/s_{j}) : s ∈ X}
c_{i}^{U}(X) = {s ∈ ^{n}U : s(i/u) ∈ X for some u ∈ U},
d_{ij}^{U} = {s ∈ ^{n}U : s_{i} = s_{j}}.

We often omit the upper indices U. We will need c_{i} and s_{ij} only at the end of the paper, in Figure 1.

If K is any class of algebras, then SK, IK, PK, HK, UpK denote the classes of all subalgebras, isomorphic copies, direct products, homomorphic imeges, and ultraproducts of elements of K, respectively. In this paper we shall characterize the (equations valid in the) classes

RA_{n}^{d} = SI{⟨𝔓(^{n}U), d_{ij}^{U}⟩_{i,j<n} : U is a set},
RA_{n}^{p} = SI{⟨𝔓(^{n}U), p_{ij}^{U}⟩_{i,j<n} : U is a set}, and
RA_{n}^{dp} = SI{⟨𝔓(^{n}U), d_{ij}^{U}, p_{ij}^{U}⟩_{i,j<n} : U is a set}.

We note that these classes are all axiomatizable by sets of quantifier–free formulas, because it is quite easy to show that they are closed under ultraproducts, and by definition, they are closed under subalgebras. (For the techniques of these proofs see Németi[90].)

Throughout this paper we assume that n is finite. If i, j < n then [i, j] denotes the permutation of n which interchanges i and j and leaves all other elements of n fixed. S(n) denotes the set of all permutations of n. The permutations [i, j] are usually called transpositions, and it is known that each permutation σ ∈ S(n) is a product of transpositions. For any σ ∈ S(n) let us fix a sequence i_{0}, j_{0}, i_{1}, j_{1}, ..., i_{k}, j_{k} < n such that

σ = [i_{0}, j_{0}] ∘ [i_{1}, j_{1}] ∘ ... ∘ [i_{k}, j_{k}].

(Such a sequence exists for all σ ∈ S(n).) We then define the term

p_{σ}(x) = p_{i_{k}j_{k}}...p_{i_{1}j_{1}}p_{i_{0}j_{0}}(x).

We will need the terms p_{σ} in writing up the axioms in (BP2) below.

We begin with characterizing p_{ij} together with the Boolean operations. Consider the following formulas. Let i, j, k < n.

(B) a finite equational axiom system for Boolean algebras. (P) p_{ij}x = p_{ji}x, p_{ij}p_{ij}x = x, p_{ij}p_{ik}x = p_{jk}p_{ij}x, p_{ii}x = x for k ∉ {i, j}. (BP1) p_{ij}(x + y) = p_{ij}x + p_{ij}y, p_{ij} − x = −p_{ij}x. (BP2) ∑{p_{σ}x : σ ∈ S(n)} = 1 ∧ ∏{p_{σ}x : σ ∈ S(n)} = 0 → 1 = 0.

In the following, we will consider (B),(P) etc. to be sets of formulas, e.g.

(P) = ⋃{{p_{ij}x = p_{ji}x, p_{ij}p_{ij}x = x, p_{ij}p_{ik}x = p_{jk}p_{ij}x, p_{ii}x = x} :
i, j, k < n, k ∉ {i, j}}.

It follows from the results in Jónsson[62] that the equations in (P) axiomatize the operations p_{ij} (see also [HMT85]3.2.17). Thus (P) implies (P’) below.

(P’) p_{δ}p_{σ}x = p_{σ∘δ}x for all δ, σ ∈ S(n).

We shall make use of this fact several times. We also note that (BP1) just states that the p_{ij}’s are Boolean homomorphisms, and thus (BP1) is equivalent to (BP1’) below:

(BP1’) p_{ij}(x + y) = p_{ij}x + p_{ij}y, p_{ij}(x · y) = p_{ij}x · p_{ij}y, p_{ij}1 = 1, p_{ij}0 = 0.

We will also use this fact several times.

Let Ax_{1} = (B) ∪ (P) ∪ (BP 1) , and Ax_{2} = Ax_{1} ∪ (BP 2).

PROPOSITION 1.

(i) RA_{n}^{p} = Mod(Ax_{2}).

(ii) Ax_{2} is an axiomatization of both the quantifier–free theory and of the quasi– equational theory of RA_{n}^{p}, while Ax_{1} is an axiomatization of the equational theory of RA_{n}^{p}. In Ax_{2}, (BP2) cannot be replaced with any set of equations if n ≥ 2, i.e. Ax_{1} |̸= Ax_{2}. Hence RA_{n}^{p} = SPUpRA_{n}^{p} ≠ HRA_{n}^{p}, i.e. RA_{n}^{p} is closed under subalgebras, products and ultraproducts but RA_{n}^{p} is not closed under taking homomorphic images, if n ≥ 2.

Proof: \underline{(i):} RA_{n}^{p} ⊧ Ax_{1} is easy to check, therefore we leave it to the reader. To check RA_{n}^{p} ⊧ (BP 2), let 𝔄 ⊆ ⟨𝔓(^{n}U), p_{ij}^{U}⟩_{i,j<n}, a ∈ A and assume that ∑{p_{σ}a : σ ∈ S(n)} = 1 ≠ 0 holds in 𝔄. Then U ≠ ∅. Let u ∈ U be arbitrary and let s = ⟨u, ..., u⟩ = n × {u} be the constant sequence of length n and with values u. Then σ ∘ s = s for all σ ∈ S(n). Thus s ∈ ^{n}U = ⋃{p_{σ}a : σ ∈ S(n)} implies s ∈ ⋂{p_{σ}a : σ ∈ S(n)}, i.e. ∏{p_{σ}a : σ ∈ S(n)} ≠ 0 in 𝔄.

To prove Mod(Ax_{2}) ⊆ RA_{n}^{p}, let 𝔄 = ⟨𝔅, p_{ij}⟩_{i,j<n} be any algebra satisfying (B),(P),(BP1),(BP2). Then 𝔅 is a Boolean algebra by 𝔄 ⊧ (B). We may assume that 𝔅 is countable because RA_{n}^{p} is an axiomatizable class. We may also assume |B| > 1. Let Uf denote the set of all ultrafilters of 𝔅. First we prove that 𝔅 has an ultrafilter which is closed under all the p_{ij}’s, i.e. we will prove

(*)  (∃F ∈ Uf)(∀i, j < n)p_{ij}^{∗}F ⊆ F.

To prove (*), let x ∈ B. We say that x is a \underline{fixpoint} if p_{ij}x = x for all i, j < n. We say that x is \underline{decomposable} if there exists a y ∈ B for which x = ∑\{p_{σ}y : σ ∈ S(n)\} and ∏\{p_{σ}y : σ ∈ S(n)\} = 0. We say that x is indecomposable (\underline{indec} for short) if x is not decomposable. Thus x is indecomposable if x = ∑{p_{σ}y : σ ∈ S(n)} implies ∏{p_{σ}y : σ ∈ S(n)} ≠ 0. If x, x_{0}, …, x_{k} are elements of a Boolean algebra, then we say that x_{0}, …, x_{k} is a \underline{partition} of x provided that x = ∑\{x_{i} : i ≤ k\} and x_{i} ∩ x_{j} = 0 ≠ x_{i} for all distinct i, j ≤ k. The following is an easy observation, as we shall see:

(1) Assume that x is an indec fixpoint and the fixpoints x_{0}, ..., x_{k} constitute a partition of x. Then one of x_{0}, ..., x_{k} is indecomposable.

Indeed, assume that no one of x_{i}, i ≤ k is indecomposable, i.e. that all of them are decomposable. For all i ≤ k let y_{i} be such that x_{i} = ∑{p_{σ}y_{i} : σ ∈ S(n)} and ∏{p_{σ}y_{i} : σ ∈ S(n)} = 0. Let y = ∑{y_{i} : i ≤ k}. Then p_{σ}y = ∑{p_{σ}y_{i} : i ≤ k} by (BP1), hence x = ∑{x_{i} : i ≤ k} = ∑{p_{σ}y : σ ∈ S(n)}. But ∏{p_{σ}y : σ ∈ S(n)} = 0 because p_{σ}y_{i} · p_{δ}y_{j} = 0 if σ, δ ∈ S(n) and i ≠ j, since x_{i}, x_{j} are disjoint fixpoints and y_{i} ≤ x_{i} (by p_{Id}y_{i} = y_{i} ≤ x_{i}). This contradicts the fact that x is indecomposable. (1) has been proved.

We will construct a descending chain x_{0} ≥ x_{1} ≥ ... of indec fixpoints such that

(2)  for all y ∈ B there is k < ω such that x_{k} ≤ y or x_{k} ≤ −y

will hold. Let B = {b_{k} : k ∈ ω}. We let

x_{0} = 1.

Then x_{0} is an indec fixpoint by 𝔄 ⊧ (BP 1), (BP 2) and by |B| > 1. Assume that x = x_{k} has already been constructed such that x_{k} is an indec fixpoint. Let y = x_{k} · b_{k}, \overline{y} = x_{k} − b_{k}. Let I = P(S(n)). For every i ∈ I define

a_{i} = ∏\{p_{σ}y : σ ∈ i\} · ∏\{p_{σ}\overline{y} : σ ∈ S(n) ∖ i\}.

Let A = {a_{i} : i ∈ I}. We will prove

(3) A ∖ {0} is a partition of x and A is closed under p_{σ}, i.e. p_{σ}^{∗}A ⊆ A for all σ ∈ S(n).

Indeed, if i ≠ j then a_{i} ·a_{j} = 0 (by p_{σ}y·p_{σ}\overline{y} = p_{σ}(y·\overline{y}) = p_{σ}0 = 0). By x = y+\overline{y} = p_{σ}x we have x = p_{σ}y + p_{σ}\overline{y} for all σ ∈ S(n). Thus x = ∏\{p_{σ}y + p_{σ}\overline{y} : σ ∈ S(n)\}. The latter equals ∑ A by the distributivity law, and the definitions of a_{i}, A. Thus x = ∑ A. Therefore A ∖ {0} is a partition of x. Let δ ∈ S(n) and i ∈ I. Then p_{δ}a_{i} = ∏\{p_{δ}p_{σ}y : σ ∈ i\} · ∏\{p_{δ}p_{σ}\overline{y} : σ ∉ i\} = a_{j} where j = \{σ ∘ δ : σ ∈ i\} (by p_{δ}p_{σ}y = p_{σ∘δ}y). We have proved (3).

Let e_{i} = ∑{p_{σ}a_{i} : σ ∈ S(n)}, for all i ∈ I.

(4) e_{i} is a fixpoint and e_{i} · e_{j} ≠ 0 ⟹ e_{i} = e_{j} for all i, j ∈ I.

Indeed, let δ ∈ S(n), i ∈ I. Then p_{δ}e_{i} = ∑{p_{δ}p_{σ}a_{i} : σ ∈ S(n)} = ∑{p_{σ}a_{i} : σ ∈ S(n)} = e_{i} because {σ ∘ δ : σ ∈ S(n)} = S(n). Therefore e_{i} is a fixpoint. Assume that e_{i} · e_{j} ≠ 0 for i, j ∈ I. Then p_{ε}a_{i} · p_{δ}a_{j} ≠ 0 for some ε, δ ∈ S(n), therefore p_{ε}a_{i} = p_{δ}a_{j} by (3). Now e_{i} = ∑{p_{δ}a_{i} : σ ∈ S(n)} = ∑{p_{σ}p_{ε}a_{i} : σ ∈ S(n)} = ∑{p_{σ}p_{δ}a_{j} : σ ∈ S(n)} = ∑{p_{σ}a_{j} : σ ∈ S(n)} = e_{j}. (4) has been proved.

(5) If e_{i} is indec then e_{i} = a_{i}, for all i ∈ I.

Indeed, assume a_{i} ≠ e_{i} = ∑{p_{σ}a_{i} : σ ∈ S(n)}. Then a_{i} ≠ p_{σ}a_{i} for some σ ∈ S(n), but then a_{i} · p_{σ}a_{i} = 0, therefore e_{i} is decomposable by ∏{p_{σ}a_{i} : σ ∈ S(n)} = 0.

(5) has been proved.

By (3),(4), {e_{i} : i ∈ I} ∖ {0} is a partition of x consisting of fixpoints. By (1) then e_{i} is indec for some i ∈ I. Let e_{i} be indec. Then e_{i} = a_{i} by (5). We now define

x_{k+1} = a_{i}, for this i.

Then x_{k+1} is an indec fixpoint (by a_{i} = e_{i}), x_{k+1} ≤ x_{k} and x_{k+1} ≤ b_{k} or x_{k+1} ≤ −b_{k} (by the definition of a_{i}).

By induction we have constructed the descending chain x_{0} ≥ x_{1} ≥ ... of fixpoints with property (2). Let F = {b ∈ B : (∃k ∈ ω)x_{k} ≤ b}. Then F ∈ Uf by (2) and p_{σ}^{∗}F ⊆ F because x_{k} is a fixpoint for all k ∈ ω. (*) has been proved.

Let ℭ be the complete atomic extension of 𝔄 constructed from ultrafilters, i.e. let

ℭ = ⟨𝔓(Uf), p_{ij}⟩_{i,j<n}

where p_{ij}X = {p_{ij}^{∗}F : F ∈ X} for any X ⊆ Uf. (It is easy to check that p_{ij}^{∗}F ∈ Ff for any F ∈ Uf.) Then 𝔄 is embeddable into ℭ, because the usual embedding em(b) = {F ∈ Uf : b ∈ F } works (to see this, one has to check p_{ij}em(b) = em(p_{ij}b) for all i, j < n and b ∈ B). Therefore it is enough to represent ℭ (i.e. to show ℭ ∈ RA_{n}^{p}). ℭ is atomic and, by (*), ℭ has an atom, say c, which is a fixpoint. Also, ℭ ⊧ (P), (BP 1) is easy to check by using the definition of ℭ.^{2} Let At denote the set of atoms of ℭ. Then p_{σ} : At ↣ → At is a bijection for all σ ∈ S(n). Let us define

a ≡ b iff (∃σ ∈ S(n))b = p_{σ}a.

Then ≡ is an equivalence relation on At. Let At′ ⊆ At be a set of representatives for ≡ (i.e. At′ contains exactly one element from each block of ≡). Let ⟨U_{a} : a ∈ At′⟩ be a system of disjoint sets such that |U_{a}| ≥ n for all a ∈ At′. Let U = ⋃{U_{a} : a ∈ At′} and for all a ∈ At′ let s_{a} ∈ ^{n}(U_{a}) be an arbitrary but fixed repetition–free sequence. We define rep : C ⟶ P(^{n}U) as follows:

2This follows also from Jónsson–Tarski[51] Thm.2.18, which says that any equation not containing Boolean complementation is preserved from 𝔄 to ℭ; and in any Boolean algebra (BP1) is easily seen to be equivalent to (BP1’) which contains no complementation.

rep(a) = {s_{a′} ∘ σ : a = p_{σ}a′, σ ∈ S(n), a′ ∈ At′} if a ∈ At, a ≠ c,
rep(c) = ^{n}U ∖ ⋃{rep(a) : a ∈ At, a ≠ c},
rep(x) = ⋃{rep(a) : a ∈ At, a ≤ x} for x ∈ C.

We will show the following for all a, b ∈ At:

(I) rep(a) ≠ 0.

(II) rep(a) ∩ rep(b) = 0 if a ≠ b. (III) p_{σ}^{U}rep(a) = rep(p_{σ}a) for all σ ∈ S(n).

(I) is clear. Assume rep(a) ∩ rep(b) ≠ 0, a ≠ c. Then b ≠ c by the definition of rep(c). Thus s_{a′} ∘ σ = s_{b′} ∘ δ, a = p_{σ}a′, b = p_{δ}b′ hold for some σ, δ ∈ S(n), a′, b′ ∈ At′. Then Rng(s_{a′}) ∩ Rng(s_{b′}) ≠ 0, therefore a′ = b′. Since s_{a′} is repetition–free, then also σ = δ by s_{a′} ∘ σ = s_{a′} ∘ δ. Thus a = p_{σ}a′ = p_{δ}a′ = p_{δ}b′ = b. Therefore (II) holds. To show (III), let σ ∈ S(n), a ∈ At, a ≠ c, a′ ∈ At′ be such that a ≡ a′. Then p_{σ}a ≠ c, p_{σ}a ≡ a′. Now p_{σ}rep(a) = p_{σ}{s_{a′} ∘ δ : a = p_{δ}a′, δ ∈ S(n)} = {s_{a′} ∘ δ ∘ σ : a = p_{δ}a′, δ ∈ S(n)} = {s_{a′} ∘ ε : p_{σ}a = p_{ε}a′, ε ∈ S(n)} = rep(p_{σ}a). To show p_{σ}rep(c) = rep(p_{σ}c) = rep(c), it is enough to notice that rep(c) = {s ∘ σ : s ∈ rep(c)} for all σ ∈ S(n). Therefore (III) holds, too. By (I)–(III) then rep is a representation for ℭ, i.e. rep : ℭ ↣ ⟨𝔓(^{n}U), p_{ij}^{U}⟩_{i,j<n} is a homomorphic embedding. Mod(Ax_{2}) ⊆ RA_{n}^{p} has been proved.

\underline{(ii):} Since Ax_{2} consists of quasi–equations, by (i) we only have to show that Ax_{1} is an axiomatization of the equational theory of RA_{n}^{p} and that RA_{n}^{p} ≠ HRA_{n}^{p}.

First we show that RA_{n}^{p} is not closed under taking homomorphic images. Let n ≥ 2 and let 𝔄 = ⟨𝔓(^{n}U), p_{ij}^{U}⟩_{i,j<n} ∈ RA_{n}^{p} with |U| = n. We will show that a homomorphic image of 𝔄 is not in RA_{n}^{p}. Let V = {s ∈ ^{n}U : s is repetition–free} and let rl(V) : P(^{n}U) ⟶ P(V) be defined by

rl(V)(x) = V ∩ x for all x ⊆ ^{n}U.

Clearly, rl(V) is a Boolean homomorphism. Let σ ∈ S(n) and x ∈ A. Then rl(V)(p_{σ}x) = V ∩ p_{σ}x = p_{σ}V ∩ p_{σ}x = p_{σ}(V ∩ x) = p_{σ}rl(V)(x), because V = p_{σ}V. Thus rl(V) is indeed a homomorphism on 𝔄. Let 𝔅 be the image of 𝔄 under this homomorphism rl(V). We will show 𝔅 ∉ RA_{n}^{p} by showing 𝔅 |̸= (BP 2). By |U| ≥ n ≥ 2 we have V ≠ ∅. Let s ∈ V be arbitrary and let x = {s} ∈ B. Then ∑{p_{σ}x : σ ∈ S(n)} = V = 1^{𝔅}, but ∏{p_{σ}x : σ ∈ S(n)} = 0 ≠ 1^{𝔅} in 𝔅, showing 𝔅 |̸= (BP 2).

Next we show that Ax_{1} is an axiomatization of the equational theory of RA_{n}^{p}. To this end, it is enough to show that the finitely generated free Ax_{1}–algebras are in RA_{n}^{p}. Let k < ω and let 𝔄 be an Ax_{1}–free algebra freely generated by g_{0}, ..., g_{k}. We will show that 𝔄 ⊧ (BP 2). By (i), this will imply 𝔄 ∈ RA_{n}^{p}. Let x ∈ A. We will show that either ∏{p_{σ}x : σ ∈ S(n)} ≠ 0 or ∑{p_{σ}x : σ ∈ S(n)} ≠ 1. Let U be any set with |U| ≥ 2, and let D = {s ∈ ^{n}U : s_{i} = s_{j} for all i, j < n}. Then 0 ≠ D ≠ ^{n}U and p_{σ}D = D for all σ ∈ S(n). Let ℭ = ⟨𝔓(^{n}U), p_{ij}^{U}⟩_{i,j<n}. Then ℭ ⊧ Ax_{1} by ℭ ∈ RA_{n}^{p}. Since 𝔄 is an Ax_{1}–free algebra, there is a homomorphism h : 𝔄 ⟶ ℭ such that h(g_{j}) = D for all j ≤ k. By 𝔄 ⊧ Ax_{1} we have that every element of A is a Boolean combination of elements from {p_{σ}g_{i} : σ ∈ S(n), i ≤ k}. By h(p_{σ}g_{j}) = p_{σ}D = D for all σ ∈ S(n), j ≤ k then h(x) is a Boolean combination of D, −D, i.e. h(x) ∈ {0, D, −D,^{n}U}. Then h(x) = p_{σ}h(x) for all σ ∈ S(n), therefore h(x) = ∏{p_{σ}h(x) : σ ∈ S(n)} = ∑{p_{σ}h(x) : σ ∈ S(n)}. This shows that either ∏{p_{σ}x : σ ∈ S(n)} ≠ 0 or ∑{p_{σ}x : σ ∈ S(n)} ≠ 1 in 𝔄. QED(Proposition 1)

REMARK 1. Proposition 1 can be generalized as follows. Let G ⊆ S(n) be the universe of any finitely presentable subgroup of ⟨S(n), ∘⟩. Let

RA_{n}^{G} = SI{⟨𝔓(^{n}U), p_{σ}^{U}⟩_{σ∈G} : U is a set}.

Then Proposition 1 remains true if we replace RA_{n}^{p} with RA_{n}^{G} and (P),(BP1) with the similar equations obtained from a finite presentation of G. ■

Next we characterize the diagonal constants d_{ij} together with the Boolean operations.

Let Ekv(n) denote the set of all equivalence relations on n = {0, ..., n − 1}. If e ∈ Ekv(n), and R ⊆ n × n then

∥e∥ denotes the number of blocks of e,

and

d(R) denotes the term ∏{d_{ij} : i, j < n, i R j} · ∏{−d_{ij} : i, j < n, i R̸ j}.

Consider the following formulas. Let i, j, k < n, e, e′ ∈ Ekv(n).

(BD1) d_{ii} = 1, d_{ij} = d_{ji}, d_{ij} · d_{jk} ≤ d_{ik}. (BD2) d(e) = 0 → d(e′) = 0 if ∥e∥ ≤ ∥e′∥. (BD3) d(e) = 0 ∧ x_{0} + ... + x_{l} ≤ d(e′) → ⋁{x_{i} = x_{j} : i < j ≤ l}, where l =

2^{m}, m = (∥e∥ − 1) · ... · (∥e∥ − ∥e′∥), whenever ∥e∥ ≥ ∥e′∥.

As before, we will consider (BD1),...,(BD3) to be sets of formulas. Let Ax_{1} = (B) ∪ (BD1), Ax_{2} = Ax_{1} ∪ (BD2), Ax_{3} = Ax_{2} ∪ (BD3).

PROPOSITION 2.

(i) RA_{n}^{d} = Mod(Ax_{3}).

(ii) Ax_{1}, Ax_{2}, Ax_{3} are axiomatizations of the equational theory, of the quasi– equational theory and of the quantifier–free theory of RA_{n}^{d}, respectively. If n > 2 then these theories are strictly stronger in this order, i.e. Ax_{1} |̸= Ax_{2} and Ax_{2} |̸= Ax_{3}, or equivalently,

RA_{n}^{d} ⫋ SPRA_{n}^{d} ⫋ HSPRA_{n}^{d}. Further, HSPRA_{n}^{d} = HRA_{n}^{d}.

Proof: RA_{n}^{d} ⊧ Ax_{2} is easy to check. To check RA_{n}^{d} ⊧ (BD3), let 𝔄 ⊆ ⟨𝔓(^{n}U), d_{ij}^{U}⟩_{i,j<n}. We note that in 𝔄, d(e) = {s ∈ ^{n}U : ker(s) = e} for all e ∈ Ekv(n) where ker(s) = {(i, j) : s_{i} = s_{j}, i, j ∈ n}. Assume that d(e) = 0 holds in 𝔄 and let e′ ∈ Ekv(n), ∥e′∥ ≤ ∥e∥. Then |U| ≤ ∥e∥ − 1 by d(e) = 0 and hence |d(e′)| ≤ (∥e∥ − 1) · ... · (∥e∥ − ∥e′∥) = m. Then d(e′) has at most l = 2^{m} subsets, and x_{0} + ... + x_{l} ≤ d(e′) → ⋁{x_{i} = x_{j} : i < j ≤ l} expresses exactly this.

To prove Mod(Ax_{2}) ⊆ SPRA_{n}^{d}, let 𝔄 = ⟨𝔅, d_{ij}⟩_{i,j<n} and assume 𝔄 ⊧ Ax_{2}. We may assume |B| > 1. By 𝔄 ⊧ (B) we have that 𝔅 is a Boolean algebra, hence 1 = ∑{d(R) : R ⊆ n × n}. By 𝔄 ⊧ (BD1) we have that d(R) = 0 if R ∉ Ekv(n), thus 1 = ∑{d(e) : e ∈ Ekv(n)}. Then d(e) ≠ 0 for some e ∈ Ekv(n), by |B| > 2. Let

κ = max{∥e∥ : d(e) ≠ 0}.

Then by 𝔄 ⊧ (BD2) we have

d(e) ≠ 0 iff ∥e∥ ≤ κ.

Let ⟨U_{a} : a ∈ B⟩ be a system of disjoint sets each of cardinality κ. Let V = ⋃{^{n}(U_{a}) : a ∈ B}. For any e ∈ Ekv(n) let

D(e) = {s ∈ V : ker(s) = e}

and let 𝔅(e) be the Boolean algebra 𝔅 relativized to d(e), i.e. 𝔅(e) is the homomorphic image of 𝔅 along the homomorphism h defined by

h(x) = x · d(e) for all x ∈ B.

Then either 1 < |𝔅(e)| ≤ |A| ≤ |D(e)| or (1 = |𝔅(e)| and 0 = D(e)). For each e ∈ Ekv(n) let h_{e} : 𝔅(e) ↣ 𝔓(D(e)) be any representation of the Boolean algebra 𝔅(e). Such representations exist by the above facts. Keeping in mind that D(e) ⊆ V for all e ∈ Ekv(n), we may define h : B → P(V) by defining for all x ∈ B

h(x) = ⋃{h_{e}(x · d(e)) : e ∈ Ekv(n)}.

By 1 = ∑{d(e) : e ∈ Ekv(n)} we have that {d(e) : e ∈ Ekv(n), ∥e∥ ≤ κ} is a partition of 1. By V = ⋃{D(e) : e ∈ Ekv(n), ∥e∥ ≤ κ} then it is not difficult to check that h : 𝔅 ↣ 𝔓(V) is a one–one homomorphism and h(d(e)) = D(e) for all e ∈ Ekv(n). For any i, j < n let

D_{ij}^{V} = {s ∈ V : s_{i} = s_{j}}.

It is not difficult to check that d_{ij} = ∏{d(e) : e ∈ Ekv(n), (i, j) ∈ e} and D_{ij}^{V} = ⋂{D(e) : e ∈ Ekv(n), (i, j) ∈ e}. Thus h(d_{ij}) = D_{ij}^{V}. Finally, it is easy to check that

⟨𝔓(V), D_{ij}^{V}⟩_{i,j<n} ≅ ×_{a∈A}⟨𝔓(^{n}U_{a}), d_{ij}⟩_{i,j<n}.

Thus h : 𝔄 ↣ ⟨𝔓(V), D_{ij}^{V}⟩_{i,j<n} ∈ PRA_{n}^{d}, showing that 𝔄 ∈ SPRA_{n}^{d}.

To show Mod(Ax_{3}) ⊆ RA_{n}^{d}, let 𝔄 ⊧ (BD3). First suppose that κ < n. Then there is e ∈ Ekv(n) with d(e) = 0 and ∥e∥ = κ + 1. For any λ ≤ κ let

m(λ) = κ · (κ − 1) · ... · (κ − λ + 1).

Then 𝔄 ⊧ (BD3) implies that |𝔅(e′)| ≤ 2^{m(∥e′∥)}, for all e′ ∈ Ekv(n). Let U be any set with cardinality κ, V = ^{n}U and define D(e) as before. Then for any e ∈ Ekv(n), ∥e∥ ≤ κ

|D(e)| = m(∥e∥).

Then |𝔅(e)| ≤ 2^{|D(e)|}, thus there is a representation h_{e} : 𝔅(e) ↣ 𝔓(D(e)) of the Boolean algebra 𝔅(e). Then we can construct, as in the previous case, a homomorphism h : 𝔄 ↣ ⟨𝔓(^{n}U), d_{ij}^{U}⟩_{i,j<n}, showing that 𝔄 ∈ RA_{n}^{d}.

Assume now κ = n. Then d(e) ≠ 0 for all e ∈ Ekv(n). Let U be any set with cardinality ≥ |A|. Let V = ^{n}U, and 𝔅(e), D(e) as before. Then 1 < |𝔅(e)| ≤ |D(e)| for all e ∈ Ekv(n), and then as in the previous cases we can construct a one–one homomorphism h : 𝔄 ↣ ⟨𝔓(^{n}U), d_{ij}^{U}⟩_{i,j<n} showing 𝔄 ∈ RA_{n}^{d}.

We proved Mod(Ax_{3}) ⊆ RA_{n}^{d} and Mod(Ax_{2}) ⊆ SPRA_{n}^{d}.

To show Mod(Ax_{1}) ⊆ HRA_{n}^{d}, let 𝔄 be any Ax_{1}–free algebra. We will show 𝔄 ∈ RA_{n}^{d} by showing 𝔄 ⊧ (BD2), (BD3). We will show that d(e) ≠ 0 in 𝔄, for all e ∈ Ekv(n). Let U be any set with |U| ≥ n and let ℭ = ⟨𝔓(^{n}U), d_{ij}^{U}⟩_{i,j<n}. Then ℭ ⊧ Ax_{1} by 𝔄 ∈ RA_{n}^{d}, therefore there is a homomorphism h : 𝔄 ⟶ ℭ since 𝔄 is free. Then h(d(e)^{𝔄}) = d(e)^{ℭ} ≠ 0 shows that d(e) ≠ 0 in 𝔄. We have proved Mod(Ax_{1}) ⊆ HRA_{n}^{d}.

Finally we show Ax_{1} |̸= Ax_{2} and Ax_{2} |̸= Ax_{3}, if n > 2. Let ℭ = ⟨𝔓(^{n}U), d_{ij}^{U}⟩_{i,j<n} ∈ RA_{n}^{d} with |U| ≥ n. Let e, e′ ∈ Ekv(n), ∥e∥ < ∥e′∥. Let V = ^{n}U ∖ D(e) and define

rl(V)x = V ∩ x for all x ∈ C.

Then rl(V) is a homomorphism of ℭ. Let 𝔅 be the homomorphic image of ℭ along rl(V). Then 𝔅 ⊧ Ax_{1} by ℭ ⊧ Ax_{1}. But by h(d(e)) = 0 ≠ h(d(e′)) we have 𝔅 |̸= (BD2), showing that Ax_{1} |̸= Ax_{2}. Let u, v be different, V = ^{n}{u} ∪^{n}{v}, and ℭ = ⟨𝔓(V), D_{ij}^{V}⟩_{i,j<n}. Then ℭ ⊧ Ax_{2} and d(e) ≠ 0 in ℭ iff ∥e∥ = 1. Let e ∈ Ekv(n) be such that ∥e∥ = 2, and let e′ = n × n. Then |d(e′)| = 2 and |{x : x ≤ d(e′)}| = 4 in ℭ. Then 1 = (∥e∥ − 1) · ... · (∥e∥ − ∥e′∥) but there are more than 2^{1} elements below d(e′) in ℭ, showing that ℭ |̸= (BD3). Thus Ax_{2} |̸= Ax_{3}. QED(Proposition 2)

Finally we characterize the operations p_{ij}, d_{ij} together with the Boolean operations. Consider the following formulas. Let i, j, k, l < n.

(BDP) p_{ij}(x · d_{ij}) = x · d_{ij}, p_{ik}d_{ij} = d_{kj}, p_{lk}d_{ij} = d_{ij} for {l, k} ∩ {i, j} = ∅, i ≠ j.

We will need also a more complex form of (BD3). To formulate this, we need some preparation. Let k, κ < ω. Then η(k) denotes the formula

∑_{i<k} x_{i} = 1∧ ⋀_{i<j<k}x_{i}·x_{j} = 0∧ ⋀_{\begin{matrix}i<k \\ σ∈S(n) \end{matrix}} (x_{i} ≠ 0 ∧ ⋁_{e∈Ekv(n)}x_{i} ≤ d(e) ∧ ⋁_{j<k}p_{σ}x_{i} = x_{j}) .

K(k, κ) denotes the set of all bijections f : X ↣ → At𝔄 where X = {x_{i} : i < k} and 𝔄 ⊆ ⟨𝔓(^{n}U), d_{ij}^{U}, p_{ij}^{U}⟩_{i,j<n} for some U with U ⊆ κ. Note that K(k, κ) is finite. For f ∈ K(k, κ) define the formula δ(f) as

⋀_{\begin{matrix}i,j<k \\ e∈Ekv(n) \\ σ∈S(n) \end{matrix}} ( ⋀_{f(x_{i})≤d(e)}x_{i} ≤ d(e) ∧ ⋀_{p_{σ}f(x_{i})=f(x_{j})}p_{σ}x_{i} = x_{j}) .

Let now (BDP3) denote the following formulas. Let e ∈ Ekv(n), κ = ∥e∥ − 1 and k ≤ 2^{(κ^{n})}. Then

(BDP3)  d(e) = 0 ∧ η(k) → ⋁{δ(f) : f ∈ K(k, κ)}.

Let Ax_{1} = (B)∪(P)∪(BD1)∪(BP 1)∪(BDP), Ax_{2} = Ax_{1}∪(BD2), Ax_{3} = Ax_{2} ∪ (BD3) ∪ (BDP 3).

PROPOSITION 3.

(i) RA_{n}^{dp} = Mod(Ax_{3}).

(ii) Ax_{1}, Ax_{2}, Ax_{3} are axiomatizations of the equational theory, of the quasi– equational theory and of the quantifier–free theory of RA_{n}^{dp}, respectively. If n > 2 then these theories are strictly stronger in this order, i.e. Ax_{1} |̸= Ax_{2} and Ax_{2} |̸= Ax_{3}, or equivalently,

RA_{n}^{dp} ⫋ SPRA_{n}^{dp} ⫋ HSPRA_{n}^{dp}. Further, HSPRA_{n}^{dp} = HRA_{n}^{dp}.

Proof: RA_{n}^{dp} ⊧ (BDP) is easy to check. To check RA_{n}^{dp} ⊧ (BDP 3), let 𝔄 ⊆ ⟨𝔓(^{n}U), d_{ij}^{U}, p_{ij}^{U}⟩_{i,j<n} ∈ RA_{n}^{dp} and let e ∈ Ekv(n), κ = ∥e∥ − 1, k ≤ 2^{(κ^{n})}. Let a_{0}, ..., a_{k−1} ∈ A, a⃗ = ⟨a_{0}, ..., a_{k−1}⟩ and assume 𝔄 ⊧ d(e) = 0 ∧ η(k)[a⃗]. By 𝔄 ⊧ d(e) = 0 then |U| ≤ κ. We may assume U ⊆ κ. Let 𝔅 be the subalgebra of 𝔄 generated by {a_{0}, ..., a_{k−1}}. By 𝔄 ⊧ η(k)[a⃗] we have that {a_{0}, ..., a_{k−1}} = At𝔅. Let f : {x_{i} : i < k} ⟶ 𝔅 be such that f(x_{i}) = a_{i} for all i < k. Then f ∈ K(k, κ), and 𝔄 ⊧ δ(f)[a⃗]. Thus 𝔄 ⊧ (BDP 3). We have seen that RA_{n}^{dp} ⊧ Ax_{3}.

To prove Mod(Ax_{2}) ⊆ SPRA_{n}^{dp} and Mod(Ax_{3}) ⊆ RA_{n}^{dp}, let 𝔄 = ⟨𝔅, d_{ij}, p_{ij}⟩_{i,j<n}, and assume 𝔄 ⊧ Ax_{2}. Let κ = max{∥e∥ : d(e) ≠ 0, e ∈ Ekv(n)}. Then by 𝔄 ⊧ (B), (BD1), (BD2),

d(e) ≠ 0 iff ∥e∥ ≤ κ

for all e ∈ Ekv(n).

Assume κ < n, and 𝔄 ⊧ Ax_{3}. Then |A| < ω by 𝔄 ⊧ (BD3), thus 𝔄 is atomic. Let k = |At𝔄|. Let X = {x_{i} : i < k} and let h : X ↣ → At𝔄 be any bijection. Let e ∈ Ekv(n) be such that d(e) = 0 and ∥e∥ = κ + 1. Such e exists by the definition of κ, and by κ < n. Then 𝔄 ⊧ d(e) = 0 ∧ η(k) under the evaluation h of variables, therefore by 𝔄 ⊧ (BDP 3) we have that 𝔄 ⊧ δ(f) under the evaluation h, for some f : X ↣ → Atℭ and ℭ ⊆ ⟨𝔓(^{n}U), d_{ij}, p_{ij}⟩_{i,j<n}. Define

rep(a) = f(h^{−1}(a))  if a ∈ At𝔄,  and
rep(b) = ⋃{rep(a) : a ≤ b, a ∈ At𝔄}.

We will show that rep : 𝔄 ↣ → ℭ is an isomorphism. Clearly,

rep : At𝔄 ↣ → Atℭ

by the conditions on f and h. Let a, b ∈ At𝔄, a = h(x_{i}), b = h(x_{j}). Then rep(a) = f(x_{i}), rep(b) = f(x_{j}). Thus by 𝔄 ⊧ δ(f)[h] we have that for all e ∈ Ekv(n) and σ ∈ S(n)

rep(a) ≤ d(e) implies a ≤ d(e), and
p_{σ}rep(a) = rep(b) implies p_{σ}a = b.

Since for every atom there is a unique e ∈ Ekv(n) such that the atom is below d(e), both in 𝔄 and in ℭ, then

rep(a) ≤ d(e) iff a ≤ d(e), and
p_{σ}rep(a) = rep(p_{σ}a).

The above imply that rep is an isomorphism. Then 𝔄 ∈ RA_{n}^{dp} by ℭ ∈ RA_{n}^{dp}.

Assume now only 𝔄 ⊧ Ax_{2}. We show that 𝔄 can be embedded into an atomic ℭ such that ℭ ⊧ Ax_{2}. As in the proof of Proposition 1, let Uf denote the set of all ultrafilters of 𝔅 and let

ℭ = ⟨𝔓(Uf), d_{ij}, p_{ij}⟩_{i,j<n}

where d_{ij} = {F ∈ Uf : d_{ij} ∈ F } and p_{ij}(X) = {p_{ij}^{∗}F : F ∈ X} for all X ⊆ Uf. In Proposition 1 we showed ℭ ⊧ (B), (P), (BP 1). By the same argument, ℭ ⊧ (BD1), (BDP) since these are equations not containing Boolean complementation. Finally, we have to show ℭ ⊧ (BD2). By em : 𝔅 ↣ ℭ we have d(e)^{𝔅} = 0 iff em(d(e)) = d(e)^{ℭ} = 0 for all e ∈ Ekv(n). This immediately implies ℭ ⊧ (BD2). Also, by d(e)^{ℭ} = d(e)^{𝔅} we have that max{∥e∥ : d(e)^{ℭ} ≠ 0} = κ. Therefore, from now on we assume that 𝔄 is atomic.

Assume 𝔄 ⊧ Ax_{2} and 𝔄 is atomic. We will show 𝔄 ∈ SPRA_{n}^{dp}. Let At denote the set of all atoms of 𝔄. Define ≡ on At as follows. For any a, b ∈ At

a ≡ b  iff  (a = p_{σ}b for some σ ∈ S(n)).

Then ≡ is an equivalence relation on At. Let At′ ⊆ At be a set of representatives for ≡ (i.e. At′ contains exactly one element from each block of ≡). Let ⟨U_{a} : a ∈ At′⟩ be a system of disjoint sets each having cardinality κ. Let V = ⋃{^{n}(U_{a}) : a ∈ At′}. For any a ∈ At define

ker(a) = {(i, j) : a ≤ d_{ij}}.

Then ker(a) ∈ Ekv(n) by 𝔄 ⊧ (BD1), and in fact, ker(a) is the unique e ∈ Ekv(n) for which a ≤ d(e). For any a ∈ At′ let s_{a} ∈ ^{n}(U_{a}) be such that ker(s_{a}) = ker(a). Let rep_{0} : At → P(V) be defined by defining for all a ∈ At

rep_{0}(b) = {s_{a} ∘ σ : b = p_{σ}a, σ ∈ S(n), a ∈ At′}.

Then rep_{0}(b) ≠ 0 for all b ∈ At since At′ contains an atom from each block of ≡.

Having achieved rep(b) ≠ 0 for all b ∈ At, we now distribute the remaining sequences among the atoms. Let Z = ⋃{rep_{0}(b) : b ∈ At} and W = V ∖ Z. Then Z = {s_{a} ∘σ : a ∈ At′, σ ∈ S(n)}, hence p_{σ}Z = Z for all σ ∈ S(n). Then p_{σ}W = W for all σ ∈ S(n), since p_{σ}V = V. We define an equivalence relation on W. For all s, z ∈ W

s ≈ z iff z = s ∘ σ for some σ ∈ S(n).

Then ≈ is an equivalence relation on W. Let W′ ⊆ W be a set of representatives for ≈, i.e. W′ contains exactly one sequence from each block of ≈. For any s ∈ W′ let at(s) ∈ At be such that ker(at(s)) = ker(s). (Such an atom exists, because ∥ker(s)∥ ≤ κ and d(e) ≠ 0 for all e ∈ Ekv(n) with ∥e∥ ≤ κ.) We now define rep_{1} : At ⟶ P(W) and rep : At ⟶ P(V) as follows. For all b ∈ At

rep_{1}(b) = {s ∘ σ : b = p_{σ}(at(s)), σ ∈ S(n), s ∈ W′}.
rep(b) = rep_{0}(b) ∪ rep_{1}(b).

For all a ∈ A define

rep(a) = ⋃{rep(b) : b ≤ a, b ∈ At}.

We want to show that rep : 𝔄 ↣ ⟨𝔓(V), D_{ij}^{V}, p_{ij}⟩ ≅ ×_{a∈At′}⟨𝔓(^{n}U_{a}), d_{ij}, p_{ij}⟩_{i,j<n}.

This will imply 𝔄 ∈ SPRA_{n}^{dp}.

To show that rep is a homomorphism, we will prove the following for all a, b ∈ At, s ∈ V and σ ∈ S(n).

(I) rep(a) ≠ 0.

(II) rep(a) ∩ rep(b) ≠ 0 implies a = b. (III) ⋃{rep(a) : a ∈ At} = V. (IV) s ∈ rep(a) implies ker(s) = ker(a). (V) s ∈ rep(a) implies s ∘ σ ∈ rep(p_{σ}a).

First we show that (I)–(V) imply that rep is a one–one homomorphism. Now (I)–(III) mean that ⟨rep(a) : a ∈ At⟩ is a partition of V, hence rep is a one–one Boolean homomorphism. Let s ∈ V. Then there is a unique a ∈ At for which s ∈ rep(a), and by (IV) we have s_{i} = s_{j} iff a ≤ d_{ij}. Hence rep(d_{ij}) = ⋃{rep(a) : a ≤ d_{ij}, a ∈ At} = D_{ij}^{V}. Let σ ∈ S(n). To show that rep is a homomorphism w.r.t. p_{σ}, it is enough to show p_{σ}rep(a) = rep(p_{σ}a) for a ∈ At because both p_{σ} and rep are additive. By (V), p_{σ}rep(a) = {s ∘ σ : s ∈ rep(a)} ⊆ rep(p_{σ}a). Let δ = σ^{−1}. Then p_{δ}rep(p_{σ}a) ⊆ rep(p_{δ}p_{σ}a) = rep(a) by the above, hence rep(p_{σ}a) = p_{σ}p_{δ}rep(p_{σ}a) ⊆ p_{σ}rep(a). Thus p_{σ}rep(a) = rep(p_{σ}a).

We start checking (I)–(V). (I) holds because rep_{0}(a) ≠ 0 for all a ∈ At. Next we check (III). Let s ∈ W. Then there is z ∈ W′ with s = z ∘ σ. Let a = at(z). Then s ∈ rep_{1}(p_{σ}a) ⊆ rep(p_{σ}a). Thus (III) holds. It is easy to check that (V) holds, by inspecting the definitions of rep_{0} and rep_{1}.: Assume s ∈ rep(a). If s ∈ Z then s ∈ rep_{0}(a), i.e. s = s_{a′} ∘ δ, a = p_{δ}a′ and a′ ∈ At′ for some δ. Then s ∘ σ = s_{a′} ∘ (δ ∘ σ), p_{σ}a = p_{σ}p_{δ}a′ = p_{(δ∘σ)}a′, a′ ∈ At′, hence s ∘ σ ∈ rep_{0}(p_{σ}a) by the definition or rep_{0}. The case s ∈ W is completely analogous and we omit it. To check (IV), let σ ∈ S(n) and for any e ∈ Ekv(n) let σe = {(σ^{−1}i, σ^{−1}j) : (i, j) ∈ e}. Then ker(s ∘ σ) = σker(s), and by 𝔄 ⊧ (BDP) and by the definition of p_{σ}, we have ker(p_{σ}a) = σker(a). By the definition of rep, this implies (IV).

To check (II), we will need to prove the following statement. Let a ∈ At, s ∈ V and σ ∈ S(n). Then

(*)  s ∘ σ = s ∘ δ and ker(s) = ker(a)  imply  p_{σ}a = p_{δ}a.

Indeed, assume s ∘ σ = s ∘ δ, ker(s) = ker(a). Then s = s ∘ π for π = δ ∘ σ^{−1}. By s = s ∘ π we have that π acts inside the blocks of ker(s) only, thus there are i_{0}, j_{0}, ..., i_{k}, j_{k} such that

π = [i_{0}, j_{0}] ∘ ... ∘ [i_{k}, j_{k}] and (i_{l}, j_{l}) ∈ ker(s) for all l ≤ k.

Then p_{π}a = p_{i_{k}j_{k}}...p_{i_{0}j_{0}}a by 𝔄 ⊧ (P). By ker(a) = ker(s) and 𝔄 ⊧ (BDP) then p_{π}a = a. Then p_{σ}a = p_{δ}a by π = δ ∘ σ^{−1}, as desired.

We are ready for checking (II). Assume s ∈ rep(a) ∩ rep(b). We have to show a = b. Assume first s ∈ W. Then s ∈ rep_{1}(a) ∩ rep_{1}(b). Then s = z ∘ σ, a = p_{σ}at(z), z ∈ W′, and s = z′ ∘ δ, b = p_{δ}at(z′), z′ ∈ W′, for some z, z′ ∈ W′, σ, δ ∈ S(n). By z∘σ = z′∘δ and z, z′ ∈ W′ we have z = z′. Then by z∘σ = z∘δ, ker(z) = ker(at(z)), (*) implies a = p_{σ}at(z) = p_{δ}at(z) = p_{δ}at(z′) = b. Assume next s ∉ W. Then s ∈ rep_{0}(a) ∩ rep_{0}(b). Then s = s_{a′} ∘ σ, a = p_{σ}a′ and s = s_{b′} ∘ δ, b = p_{δ}b′ for some σ, δ and a′, b′ ∈ At′. By Rng(s_{a′}) = Rng(s_{b′}) then a′ = b′. Let z = s_{a′} = s_{b′}. Then z ∘σ = z ∘δ, ker(z) = ker(a′) imply, by (*), that a = p_{σ}a′ = p_{δ}a′ = p_{δ}b′ = b. We have checked (II). Thus rep is a one–one homomorphism and 𝔄 ∈ SPRA_{n}^{dp}.

Assume finally 𝔄 ⊧ Ax_{2} and κ = n. We will show that 𝔄 ∈ RA_{n}^{dp}. Let U be a set with |U| ≥ n · |A|. Let V = ^{n}U. Let At′ be as in the previous case. For any a ∈ At′ let s_{a} ∈ ^{n}U be such that Rng(s_{a}) ∩ Rng(s_{b}) = ∅ if a ≠ b. We define rep exactly as in the previous case: For any a ∈ At let

rep_{0}(a) = {s_{a′} ∘ σ : a = p_{σ}a′, σ ∈ S(n), a′ ∈ At′}.

Let W, W′ be as in the previous case and define for a ∈ At

rep_{1}(a) = {s ∘ σ : a = p_{σ}at(s), σ ∈ S(n), s ∈ W′},

and define

rep(a) = rep_{0}(a) ∪ rep_{1}(a) if a ∈ At,
rep(b) = ⋃{rep(a) : a ≤ b, a ∈ At} if b ∈ A.

Then one can see, exactly as in the previous case, that rep : 𝔄 ↣ ⟨𝔓(^{n}U), d_{ij}, p_{ij}⟩_{i,j<n} ∈ RA_{n}^{dp}.

So far we have proved Mod(Ax_{2}) ⊆ SPRA_{n}^{dp} and Mod(Ax_{3}) ⊆ RA_{n}^{dp}. Now we prove Mod(Ax_{1}) ⊆ HRA_{n}^{dp}. The proof of this is very simple: Let 𝔄 be any Ax_{1}–free algebra. Then d(e) ≠ 0 in 𝔄 for any e ∈ Ekv(n), hence 𝔄 ⊧ (BD2), (BD3), (BDP 3). Thus 𝔄 ⊧ Ax_{3}, hence 𝔄 ∈ RA_{n}^{dp}. Since any Ax_{1}– algebra is a homomorphic image of a free one, this implies Mod(Ax_{1}) ⊆ HRA_{n}^{dp}.

To finish the proof, we show Ax_{1} |̸= Ax_{2} and Ax_{2} |̸= Ax_{3} if n > 2. Let n ≥ 2 and let U be a set with |U| ≥ 2 and let V = {s ∈ ^{n}U : s_{i} = s_{j} for all i, j < n}, W = ^{n}U ∖ V. Let 𝔄 = ⟨𝔓(^{n}U), d_{ij}, p_{ij}⟩_{i,j<n} and rl(W)(a) = W ∩ a for all a ∈ A. Then rl(W) is a homomorphism on 𝔄 by p_{σ}W = W for all σ ∈ S(n). Let 𝔅 be the homomorphic image of 𝔄 taken along rl(W). Then 𝔅 ⊧ Ax_{1} but 𝔅 |̸= (BD2) showing Ax_{1} |̸= Ax_{2}. Let n ≥ 3 and let 𝔄 be as above with |U| = 2 and let 𝔅 = 𝔄 × 𝔄. Then 𝔅 ⊧ Ax_{2} but 𝔅 |̸= (BD3) showing Ax_{2} |̸= Ax_{3}. QED(Proposition 3)

We note that the above proof of Proposition 3 is somewhat similar to the proof in Andréka–Thompson[88].

We conclude with summarizing the known facts on a figure.

On the figure there is a tree. The nodes represent classes of algebras of n–ary relations (on some set U) and the operations are those indicated along the path leading to the node. In other words, a node represents the class of all algebras of n–ary relations, up to isomorphisms, where the greatest relation is of form ^{n}U for some U, and the operations are those indicated along the unique path leading to the node. So the classes on different nodes have different similarity types. On the figure we concentrate only on the equational theories of the classes involved.

Let K, L be classes of algebras such that the similarity type of K is contained in that of L. Let Eq(K), Eq(L) denote the sets of all equations valid in K and L respectively. We say that L is finitely axiomatizable over K if Eq(K) ∪ Σ is an (equational) axiomatization of Eq(L) for some finite Σ. If K consists of all appropriate subreducts of elements of L, as in our cases, then this means that Eq(L) has an axiomatization in which the operation symbols not present in K occur only finitely many times.

On the figure, a broken edge like - - - - between two nodes means that the bigger one of the corresponding classes is finitely axiomatizable over the other one. A bold edge like ====== between two nodes means that the bigger one of the corresponding classes is not finitely axiomatizable over the other one. Normal line ——– means that we (the author) do not know the answer.

The most interesting open case presently seems to be whether the operations s_{ij} are finitely axiomatizable over ∪, ∖, c_{i} or not.

There are labels on some of the edges. These indicate where the proof (of the represented statement) can be found. Propositions 1–3 refer to statements in the present paper, while Theorems 1–6 refer to theorems of Part I of the present work.

Now we list the results not in this work that we will use on the figure.

Nonfinite axiomatizability of the operations p_{ij} over ∪, −, c_{i}, d_{ij} (i, j < n) was proved by Andréka and Tuza, see Andréka–Tuza[88]. This is a solution of Problem 2.b in Johnson[69] and of Problems 5.7,5.8 in Henkin–Monk–Tarski[HMT85].

Finite axiomatization of substitutions s_{ij}, and of the substitutions together with the diagonals over the Boolean operations are given in Sági–Németi[96].

It is not difficult to see that the proof in Monk[69] also proves that the Boolean operations together with cylindrifications and substitutions are not finitely axiomatizable. This together with the results in Sági–Németi[96] proves e.g. nonfinite axiomatizability of cylindrifications over the Booleans and the substitutions.

Monk[89] proved that the Boolean operations together with substitutions, permutations, and the same together with diagonals are finitely axiomatizable.

On the figure, the root of the tree contains the Boolean operations ∪, ∖. This means that the Boolean operations are present in every class considered on the figure. There are known axiomatizations of the other operations when considered without or with only some of the Boolean operations. We now list some results of this kind.

Jónsson[62] gives a finite set of equations characterizing the operations p_{ij}, s_{ij} and Thompson[87,93] give a finite axiom system for the operations s_{ij} in themselves. The equations for s_{ij} are much more involved when we cannot use the p_{ij}’s. For a simple proof of Thompson’s theorem see Sági[96].

An axiomatization for the operations c_{i} in themselves is due to Hansen[92,95] and is the following. For all i, j < n

c_{i}c_{i}x = c_{i}x, c_{i}c_{j}x = c_{j}c_{i}x,

c_{0}...c_{n−1}x = x ∧ c_{0}...c_{n−1}y = y ∧ c_{0}...c_{n−1}z = z → (x = y ∨ x = z ∨ y = z),

c_{0}...c_{n−1}x′ = x ∧ c_{0}...c_{n−1}y′ = y → (x′ = x ∨ y′ = y ∨ x = y),

and an axiomatization of the operations d_{ij} in themselves is the following. For all i, j < n

d_{ii} = d_{jj}, d_{ij} = d_{ji}, d_{ij} = d_{pq} → d_{kl} = d_{pq} for p ≠ q.

Interesting are the results when we keep only part of the Boolean operations or weaker structures such as Stone algebras. More such results can be found in Hansen[92,95]. Or, as another example, Comer[89] proved that the positive reducts of cylindric algebras (i.e. the equational theory of the class {⟨𝔓(^{n}U), ∪, ∩, ∅,^{n}U, c_{i}^{U}, d_{ij}^{U}⟩_{i,j<n} : U is a set}) is not finitely axiomatizable. These and similar reducts (also for binary relations) are widely investigated recently, e.g. in connection with modal logic (“arrow logic”), and in connection with computer science (theory of relational databases, theory of incomplete information, rough sets). For a sample we list Düntsch[90,93,94], Cirulis [88], Comer[90,93], Cosmadakis[87], Marx[95], Mikulás[95,96], Andréka–Mikulás[94], Andréka–Ryan– Schobbens[95], Karger[94]^{3}, Karger–Hoare[95], Andréka–Bredikhin[95], Jónsson[90], Jipsen–Jónsson–Rafter [95]. Open problems concerning these reducts can be found in the Problems part of Andréka–Monk–Németi[88].

In the following figure, in a node all indices range over n, e.g. d_{ij} means {d_{ij} : i, j < n}.

3We note that sequential algebras are RRA’s relativized to reflexive and transitive relations and endowed with the two residuals of relation composition.

FIGURE 1 20

The corresponding picture for relation algebras (algebras of binary relations with composition) is radically different. While the “strength of RCA_{n}” is distributed among the operations of RCA_{n} quite evenly, all the strength of RRA is concentrated in relation composition: this operation is so strong that relative to it all the other non–Boolean operations are finitely axiomatizable.

Figure 2 below summarizes the interconnection between the RRA–operations ∪, −, |,^{−1}, Id. If we take the Boolean operations ∪, − for granted, then the only cause of nonfinite axiomatizability of RRA is |, namely ^{−1} and Id are finitely axiomatizable over any other subsets of the operations, while | is only infinitely axiomatizable over any sets of others. Of these, the finite axiomatizability results are proved in Andréka-Németi[96] (see also Jipsen–Jónsson–Rafter[95]), where the finite axiomatizations are also given. Since RRA is not finitely axiomatizable (by Monk[64], or by Theorem 8 in Part I of this work), it follows from these finite axiomatizability results that relation composition is non–finitely axiomatizable relative any other sets of the non–Boolean operations of RRA.

The “reading” of Figure 2 is exactly the same as that of Figure 1. I.e.. a node represents the class of all algebras of binary relations, up to isomorphisms, where the greatest relation is an equivalence relation and the operations are those indicated along the path leading to the node, etc. We note that all classes represented by the nodes are varieties except the ones inside a box (those are only quasi–varieties).

FIGURE 2

References

Andréka,H. and Bredikhin,D. [95], The equational theory of union-free algebras of relations,

Algebra Universalis 33,4 (1995), 516-532. Andréka,H. and Mikulás,Sz. [94], Lambek Calculus and its relational semantics: Completeness

and incompleteness, J. of Logic, Language and Information 3 (1994), 1-37. Andréka,H. Monk,J.D. and Németi,I.(ed.s) [88], Algebraic Logic. Colloq. Math. Soc. J. Bolyai

Vol. 54, North–Holland, Amsterdam, 1991. Andréka,H. and Németi,I. [96], Axiomatization of identity-free equations valid in relation

algebras, Algebra Universalis 35 (1996), 256-264. Andréka,H. Ryan,M. and Schobbens,P-Y. [95], Operators and laws for combining preferential

relations (Extended abstract). In: Information Systems: Correctness and Reusability (Selected papers), eds. R.J. Wieringa and R.B. Feenstra, World Scientific Publishing Co, 1995. pp.191-206.

Andréka,H. and Thompson,R.J. [88], A Stone–type representation theorem for algebras of

relations of higher rank, Trans. Amer. Math. Soc. 309,2 (1988), 671–682. Andréka,H. and Tuza,Zs. [88], Nonfinite axiomatizability of the polyadic operations in alge-

braic logic, Abstracts of Amer. Math. Soc. 9 (1988), 500. *88T–03–264 Cirulis,J. [88], Relational algebras in databases and generalized cylindric algebras (in Russian),

Theoretical Questions of Programming, Latvian University, Riga (1988), 100–107. Comer,S.D. [89], A remark on representable positive cylindric algebras, Algebra Universalis

28 (1991), 150–151. Comer,S.D. [90], An algebraic approach to the approximation of information, Fundamenta

Informaticae XIV (1991), 492-503. Comer,S.D. [93], On connections between information systems, rought sets, and algebraic

logic. In: Algebraic Methods in Logic and Computer Science, C. Rauszer (ed), Banach Center Publications Vol. 28, Warsaw, 1993. pp.117-124.

Cosmadakis,S.S. [87], Database theory and cylindric lattices. (Extended abstract). In: IEEE

28th Annual Symposium on Foundations of Computer Science, 1987. pp. 411-420. Düntsch,I. [90], Join dependencies and cylindric algebras. Preprint, Universiti of Brunei,

Darussalam, Negara Brunei, 1990. Düntsch,I. [93], A note on cylindric lattices. In: Algebraic Methods in Logic and Computer

Science, C. Rauszer (ed), Banach Center Publications Vol. 28, Warsaw, 1993. pp.231-238. Düntsch,I. [94], Rough relation algebras, Fundamenta Informaticae 21 (1994), 321-331. Hansen,B. [92], Representation theorems of reducts of cylindric agebras. In: Abstracts of the

1992 European Summer Meeting of the Assoc. Symb. Logic, J. Symbolic Logic 58,3 (1993), 1125.

Hansen,B. [95], Finitizability questions for some reducts of cylindric algebras. In: Logic Colloquium’92, Csirmaz,L. Gabbay,D.M. and de Rijke,M. (eds), CSLI Publications, Stanford, 1995. pp.115-134.

Henkin,L. Monk,J.D. and Tarski,A. [HMT85], Cylindric Algebras, Part II. North–Holland,

Amsterdam, 1985. Jipsen,P. Jónsson,B. and Rafter,J. [95], Adjoining units to residuated Boolean algebras, Alge-

bra Universalis 34 (1995), 118–127. Johnson,J.S. [69], Nonfinitizability of classes of representable polyadic algebras, J. Symbolic

Logic 34 (1969), 344–352.

Jónsson,B. [62], Defining relations for full semigroups of finite transformations, Michigan

Math. J. 9 (1962), 77–85. Jónsson,B. [90], Program specification as Boolean operators. Preprint, Vanderbilt University,

circulated at the Jónsson Conference, Iceland, 1990. Jónsson,B. and Tarski,A. [51], Boolean algebras with operators. Part I., Amer. J. Math. 73

(1951), 891–939. von Karger,B. [94], The class of representable sequential algebras is not finitely axiomatizable.

Manuscript, July 1994. von Karger,B. and Hoare,C.A.R. [95], Sequential calculus, Information Processing Letters 53

(1995), 123–130. Marx,M. [95], Algebraic relativization and arrow logic. PhD Dissertation, University of Ams-

terdam, Amsterdam, 1995. Marx,M. Pólos,L. and Masuch,M. (eds) [96], Arrow Logic and Multi-Modal Logic. CSLI Pub-

lications, Stanford, 1996. vi+247pp. Mikulás,Sz. [95], Taming Logic. PhD Dissertation, University of Amsterdam, Amsterdam,

1995. Mikulás,Sz. [96], Undecidable relativization of algebras of relations. Submitted. Monk,J.D. [64], On representable relation algebras, Michigan Math. J. 11 (1964), 207–210. Monk,J.D. [69], Nonfinitizability of classes of representable cylindric algebras, J. Symbolic

Logic 34 (1969), 331–343. Monk,J.D. [89], Personal communication. Budapest, 1989. Németi,I. [90], Algebraizations of quantifier logics: an introductory overview. Version 12,

Preprint No 13/1996, Mathematical Institute, Budapest. Shortened version appeared as: Studia Logica 50/3-4(1991)458-569.

Sági,G. [96], Finite schema presentation of the semigroup of non-permutational finite trans-

formations (a simple proof), Semigroup Forum. To appear. Sági,G. and Németi,I. [96], The modal logic of substitutions and its algebras. Manuscript.

Mathematical Institute Budapest, 1996. Thompson,R.J. [87], Semigroups of finite transformations and cylindric algebras. Preprint

No 45/1987, Mathematical Institute, Budapest, 1987. Thompson,R.J. [93], Complete description of substitutions in cylindric algebras and other

algebraic logic. In: Algebraic Methods in Logic and in Computer Science. Banach Center Publications Vol 28. Polish Academy of Science, Warszawa, 1993. pp.327–342.

Keywords. Algebraic logic, algebras of relations, cylindric algebras, polyadic algebras, relation algebras, representation theory, nonfinitizability, finitization problem, completeness theorems, incompleteness theorems, modal logic of quantification and substitution, logic of first–order formula schemas, logic with finitely many variables. 1980 Mathematics subject classifications: 03G15, 06, 08

H. Andréka : Mathematical Institute of Hung. Acad. Sci., Budapest, Pf.127, H–1364, Hungary. e-mail: andreka@math-inst.hu