Relation algebras from Cylindric and Polyadic algebras

István Németi^{∗} András Simon^{†}

November 9, 1996

Abstract

This paper is a survey of recent results concerning connections between relation algebras (RA), cylindric algebras (CA) and polyadic equality algebras (PEA). We describe exactly which subsets of the standard axioms for RA are needed for axiomatizing RA over the RA-reducts of CA_{3}’s, and we do the same for the class SA of semi-associative relation algebras. We also characterize the class of RA-reducts of PEA_{3}’s. We investigate the interconnections between the RA-axioms within CA_{3} in more detail, and show that only four implications hold between them (one of which was proved earlier by Monk). In the other direction, we introduce a natural CA-theoretic equation MGR^{+}, a generalization of the well-known Merry-Go-Round equation MGR of CA-theory. We show that MGR^{+} is equivalent to the RA-reduct being an SA, and that MGR^{+} implies that the RA-reduct determines the algebra itself, while MGR is not sufficient for either of these to hold. Then we investigate how different CA’s a single RRA can “generate” in the general case. We solve the first part of Problem 11 from the “Problem Session Paper” of [AMN90].

While proving some of the statements, for others we give only outline of proof. The paper contains several open problems. A full version of this paper is under preparation.

1 Introduction

Relation algebras (RA), cylindric algebras (CA) and polyadic equality algebras (PEA) are abstract versions of natural algebras of relations. In this paper we investigate the connection between them. The connections between these three classes of algebras are analogous with the kind of connection which exists between the class of Boolean groups (BG) and Boolean algebras (BA). Namely, Boolean groups are exactly the subreducts of BA’s, formally BG = S ℜ𝔡 BA. The operator ℜ𝔡 involves taking a term-definitionally equivalent version BA′ of BA and then throwing away some of the operations of BA′.

Here we will work on a similarly close connection between RA’s, CA’s and PEA’s. First let us look at the representable versions RRA, RCA and RPEA of these algebras. For the purposes of this introduction, all CA’s and PEA’s are assumed to be 3-dimensional.

RCA’s are exactly the subreducts of RPEA’s (where, of course, the reduct is taken to the language of CA’s), i.e., RCA = S ℜ𝔡 RPEA. The RA-operations are term-definable in CA’s, hence it is meaningful to talk about the RA-reducts ℜa^{∗} CA of CA’s. In forming ℜa^{∗} CA, we throw away not only operations, but also elements of the CA’s. (In the CA ↦ RA direction we use the notation ℜa^{∗} instead of ℜ𝔡, for historical reasons, c.f. Henkin–Monk– Tarski [HMT85b, §5.2].) Now RRA = S ℜa^{∗} RCA(= S ℜa^{∗} RPEA). So, all the connections match up perfectly, just as in the above recalled BG—BA example.

∗Supported by Hungarian National Foundation for Scientific Research grants T16448 and T7255.

†Supported by Hungarian National Foundation for Scientific Research grant F17452.

Let us see what happens if we try to generalize these connections to the larger, axiomatic classes RA, CA and PEA. We will find that that the connections become more interesting (and less smooth). E.g., we have

CA ⊋ S ℜ𝔡 PEA = Var(S ℜ𝔡 PEA) ⊋ RCA,

which motivates the problem of finding finitely many natural CA-theoretic equations which describe the subvariety S ℜ𝔡 PEA of CA. We will look into this, among others. We will also look into the kind of question when one asks whether “S ℜ𝔡”=“ℜ𝔡” in the given context. Further,

S ℜa^{∗} CA ⊋ RA ⊊ S ℜa^{∗} PEA.  (1)

Here one looks again for natural CA-theoretic equations defining a subvariety CA^{+} ⊂ CA such that S ℜa^{∗} CA^{+} = RA (and similarly with PEA in place of CA). In connection with the equations axiomatizing CA^{+} we will answer a problem raised in Monk [Mon61] (see Theorem 2.2 in section 2). A further question in connection with (1) is the following. It is known that the well-investigated variety SA ⊃ RA of semi-associative relation algebras is contained in S ℜa^{∗} PEA. We will show that they are actually equal, i.e., that SA = S ℜa^{∗} PEA. This is one motivation to investigate the connections between CA and SA. E.g. we will write up equations defining CA^{0} ⊂ CA with S ℜa^{∗} CA^{0} = SA. Also, we will investigate the varities between SA and S ℜa^{∗} CA.

Outline of the paper. In section 2 we describe exactly which subsets of the standard axioms for RA are needed for axiomatizing RA over the RA-reducts of CA_{3}’s, and we do the same for the class SA of semi-associative relation algebras. Theorem 2.2 in section 2 solves Problem 4 in Monk [Mon61]. We also characterize the class of RA-reducts of PEA_{3}’s. In section 5 we investigate the interconnections between the RA-axioms within CA_{3} in more detail, and show that only four implications hold between them (one of which was proved earlier by Monk). In section 3 we introduce a natural CA-theoretic equation MGR^{+}, a generalization of the well-known Merry-Go-Round equation MGR of CA-theory. We show that MGR^{+} is equivalent to the RA-reduct being an SA, and that MGR^{+} implies that the RA-reduct determines the algebra itself, while MGR is not sufficient for either of these to hold. In section 4 we investigate how different CA’s a single RRA can “generate” in the general case and solve the first part of Problem 11 from the “Problem Session Paper” of [AMN90] (c.f. Corollary 4.5). Some non-finitizability results appear at the end of section 4 as by-products of the investigations there. In section 6 we recall an axiom system, due to H. Andréka, which defines CA^{+} such that S ℜa^{∗} CA^{+} = RA. We raise some problems in connection with this.

2 Relation Algebras from Cylindric and Polyadic Algebras

We use the notation and terminology of the fundamental textbook [HMT85a], [HMT85b]. In particular, RA, CA_{n} and PEA_{n} stand for “relation algebras”, “cylindric algebras of dimension n” and “polyadic equality algebras of dimension n”, respectively. Throughout, 2 < n < ω. BAO (nBAO) denotes the class of (normal) Boolean Algebras with Operators.

First we recall from [HMT85b] §5.3 the standard axiomatization of Relation Algebras (RA’s).

Definition 2.1 ([HMT85b] §5.3) i. RA is the variety axiomatized by the equations (R0)–(R7) below.

(R0) The Boolean axioms

(R1) (x; y) ; z = x; (y ; z) (associativity)

(R2) (x + y) ; z = (x; z) + (y ; z)

(R3) x; 1′ = x

(R4) x^{⌣}^{⌣} = x

(R5) (x + y)^{⌣} = x^{⌣} + y^{⌣}

(R6) (x; y)^{⌣} = y^{⌣} ; x^{⌣}

(R7) x^{⌣} ; [−(x; y)] ≤ −y.

ii. The semiassociative law is

(R1_{0}) (x; 1) ; 1 = x; 1.

iii. The cycle law is the formula (∀xyz)[(x;y)·z = 0 ↔ (x^{⌣};z)·y = 0 ↔ (z;y^{⌣})·x = 0].

The cycle law is due to De Morgan and the semiassociative law was introduced in Maddux [Mad78].

Next we recall some definitions from [HMT85b]. The natural relation algebra type reduct ℜa ℭ of an algebra ℭ ∈ CA_{n} or PEA_{n} is defined the following way. Its universe is Ra ℭ = {x ∈ C : (∀i ≥ 2) c_{i} x = x}. The Boolean operations of ℜa ℭ are the same as those of ℭ, 1′ = d_{01}, x^{⌣} = s_{0}^{2} s_{1}^{0} s_{2}^{1} x, and x; y = c_{2}(s_{2}^{1}(x) · s_{2}^{0}(y)) are the rest of the relation algebraic operations.

For a class K of CA_{n}’s or PEA_{n}’s we define

ℜa^{∗}(K) = ℜa^{∗} K =^{def} {ℜa ℭ : ℭ ∈ K}

cf. [HMT85b] p. 218. If n ≥ 4, then ℜa^{∗} CA_{n} ⊆ RA, but for n = 3, RA ⊊ ℜa^{∗} CA_{3}. By Monk [Mon61] and Maddux [Mad78] we have

ℜa^{∗} CA_{3} ⊧ (R1_{0}), (R2), (R3), (R5).  (2)

It is known that each of the remaining axioms ((R1), (R4), (R6) and (R7)) can fail in ℜa^{∗} CA_{3}.

Monk [Mon61] proves the following result (and credits the ⊇ part to G. Fuhrken)

RA = ℜa^{∗} CA_{3} ∩ Mod{(R1), (R4), (R6)}.  (3)

Problem 4 in [Mon61] asks whether both (R4) and (R6) are needed in the above theorem. Our next theorem says (among others) that (R6) is, but (R4) is not, see Corollary 2.4. We note that ℜa^{∗} CA_{3} can be replaced with S ℜa^{∗} CA_{3} (where, for a class K of algebras, S K denotes the class of subalgebras of members of K) in (3); one can check this by inspecting the proof in [Mon61].

Theorem 2.2 i. S ℜa^{∗} CA_{3} ∩ Mod{(R7)} ⊧ (R4)

ii. S ℜa^{∗} CA_{3} ∩ Mod{(R6)} ⊧ (R4)

iii. S ℜa^{∗} CA_{3} ∩ Mod{(R1),(R7)} ⊧ (R6)

iv. ℜa^{∗} CA_{3} ∩ Mod{(R1),(R4)} |̸= (R6)

v. ℜa^{∗} CA_{3} ∩ Mod{(R7)} |̸= (R6)

vi. ℜa^{∗} CA_{3} ∩ Mod{(R1)} |̸= (R4)

Outline of proof. We only give detailed proof for i. But first we note that in the proof of iv. and v. we use dilation and in the proof of vi. we use both dilation and twisting; these are methods (described in [HMT85b] 3.2.69, 3.2.71) for obtaining non-representable cylindric algebras from representable ones. We have to apply twisting in the proof of vi. because dilation does not change “converse”.

i. is a consequence of the following, stronger proposition: Let (R2’) stand for the “mirror image” of the axiom (R2) for RAs, that is,

(R2’) x; (y + z) = (x; y) + (x; z).

Proposition 2.3 (R0, R2’, R3, R7) ⊧ x^{⌣}^{⌣} ≤ x.

Proof. Assume (R0, R2’, R3, R7). By (R7) we have

(∗)  x^{⌣}^{⌣} ; −(x^{⌣} ; −x) ≤ x.

Also by (R7) x^{⌣};−(x;1′) ≤ −1′ which by (R3) yields x^{⌣};−x ≤ −1′, hence −(x^{⌣};−x) ≥ 1′. Putting these together:

x^{⌣}^{⌣} = x^{⌣}^{⌣} ; 1′ ≤ ; ↑ ; (R2’)x^{⌣}^{⌣} ; −(x^{⌣} ; −x) ≤ ; ↑ ; (∗)x.

□

Now i. follows by Proposition 5.3 in §5 below, and Proposition 2.3, since ℜa^{∗} CA_{3} ⊧ (R2’).

□

In passing we note that using Proposition 2.3, it can be shown that in axiomatizing RA, axiom (R4) can be replaced by the weaker postulate x ≤ x^{⌣⌣} (if we use (R2’) in place of (R2)).

Corollary 2.4 A subset E of the RA-axioms defines RA within ℜa^{∗} CA_{3} (or within S ℜa^{∗} CA_{3}) iff E ⊇ {(R1), (R6)} or E ⊇ {(R1), (R7)}. That is, for all E ⊆ {(R0), …, (R7)},

RA = ℜa^{∗} CA_{3} ∩ Mod E ⟺ RA = S ℜa^{∗} CA_{3} ∩ Mod E
⟺ E ⊇ {(R1) (R6)} or E ⊇ {(R1), (R7)}.

Proof. By Theorem 2.2 ii and (3), {(R1), (R6)}, and hence by Theorem 2.2 iii {(R1), (R7)} define RA in ℜa^{∗} CA_{3}. If E defines RA in ℜa^{∗} CA_{3} then (R1) ∈ E because RA ⊊ SA (see below for the definition of SA; this result is due to Maddux [Mad78], [Mad82]). Finally, either (R6) ∈ E or (R7) ∈ E because of Theorem 2.2 iv. □

Let us turn to polyadic equality algebras (PEA’s) in place of cylindric algebras. We need the equality part because in polyadic algebras we cannot define the relation algebraic identity 1′.

The following theorem is implicit in Monk [Mon61].

ℜa^{∗} PEA_{3} ⊧ (R1_{0}, R2–R7),  (4)

i.e., with the exception of the associativity axiom (R1) for “;”, all the axioms of RA are valid in ℜa^{∗} PEA_{3}.

Motivated by the failure of associativity in ℜa^{∗} CA_{3}, Maddux [Mad78], [Mad82] introduced the weaker axiom (R1_{0}), called the semiassociativity law, see Definition 2.1 herein. He proved that

(ℜa^{∗} CA_{3}) ∩ Mod (cycle law) ⊧ (R1_{0}), (R2—R7).  (5)

He defined the variety SA of semi-associative relation algebras as follows:

SA =^{def} Mod{(R0), (R1_{0}), (R2–R7)}.

Maddux also proved that

SA = ℜa^{∗} CA_{3} ∩ Mod(cycle law).  (6)

By now the theory of SA has been developed to quite an extent. SA turned out to be a useful class.

Rd PEA_{3} denotes the class of all cylindric-type reducts of PEA_{3}’s.

Theorem 2.5 i. ℜa^{∗} PEA_{3} = SA.

ii. If 𝔄 ∈ CA_{3} is generated by Ra 𝔄, then

ℜa 𝔄 ∈ SA ⟺ 𝔄 ∈ Rd PEA_{3} ⟺ 𝔄 ∈ S Rd PEA_{3}.

Our next theorem characterizes the subsets of the SA-axioms which define SA in ℜa^{∗} CA_{3}. We note that in the theorem below, ℜa^{∗} CA_{3} can be replaced by S ℜa^{∗} CA_{3}.

Theorem 2.6 A subset of the SA-axioms characterizes SA in ℜa^{∗} CA_{3} (or in S ℜa^{∗} CA_{3} iff it contains both (R6) and (R7). I.e., for all E ⊆ {(R0), (R1_{0}), (R2),…,(R7)},

SA = ℜa^{∗} CA_{3} ∩ Mod E ⟺ SA = S ℜa^{∗} CA_{3} ∩ Mod E ⟺ {(R6), (R7)} ⊆ E.

Proof. By (2) and Theorem 2.2 i. we have that {(R6), (R7)} defines SA in ℜa^{∗} CA_{3}. By Theorem 2.2 i., v. {(R4), (R7)} does not define SA in ℜa^{∗} CA_{3} and by Theorem 4.1 in §4 in this paper we have that {(R4), (R6)} does not define SA in ℜa^{∗} CA_{3}. Hence neither does any subset of them. □

Theorem 2.6 shows an interesting property of the axiom sets {(R1), (R6)} and {(R1), (R7)}. Almost all definitions of RA are such that replacing (R1) by (R1_{0}) in them yields a set defining SA. But by Corollary 2.4 and Theorem 2.6 we have RA = ℜa^{∗} CA_{3}∩Mod{(R1), (R6)} and SA ≠ ℜa^{∗} CA_{3} ∩ Mod{(R6)}(= ℜa^{∗} CA_{3} ∩ Mod{(R1_{0}),(R6)}), so the above mentioned common phenomenon is by no means necessary.

We will investigate the interconnections of the RA-axioms within ℜa^{∗} CA_{3} in more detail in §5. In particular, we will see that, in a sense, the only implications between the RA-axioms that hold in ℜa^{∗} CA_{3} are (3) and Theorem 2.2 i–iii.

3 Looking at the connections backwards

It is natural to ask ourselves the following question: Are there sets of natural CA-theoretic equations E and E′ such that

SA = ℜa^{∗}(CA_{3} ∩ Mod E)  (7)
RA = ℜa^{∗}(CA_{3} ∩ Mod E′).  (8)

In connection with the second question we note the following: Maddux [Mad78] proved that RA = ℜa^{∗}(S Nr_{3} CA_{4}), and Andréka [And] gave a finite set of equations axiomatizing S Nr_{3} CA_{4} (see section 6 below for details). So there is a set E′ such that (8) holds. For this reason, in this section we will concentrate on the first question. It is important in this question that E be simple and natural in the language of CA’s, for otherwise a mechanical translation of the SA axioms would do the job. Such a translation might not be illuminating, it might look like a “Gödel number” from the CA-theoretic point of view.

Below we will give a natural set MGR^{+} of equations such that (i) MGR^{+} is a good choice for E in (7) above, and (ii) MGR^{+} can be used to generalize some results in [HMT85b] §5.3.

MGR^{+} will be a stronger version of the well-known Merry Go Round equation schema MGR.

Definition 3.1 Let us recall from [HMT85a] that _{k} s(i, j)x = s_{i}^{k} s_{j}^{i} s_{k}^{j} x. The axiom schema MGR^{+} is defined as follows:

(MGR^{+}) _{k} s(i, j)c_{k}(c_{i}x · c_{j}y) = c_{k}(s_{i}^{j} c_{i}x · s_{j}^{i} c_{j}y) for k ∉ {i, j}.

For completeness, we recall that MGR is _{k} s(i, j)_{k} s(i, j) c_{k} x = c_{k} x in CA_{3}.

Theorem 3.2 Let 𝔄 ∈ CA_{3}. Then

i. ℜa 𝔄 ∈ SA ⟺ 𝔄 ⊧ MGR^{+}, i.e., SA = ℜa^{∗}(CA_{3} ∩ Mod(MGR^{+}))

ii. 𝔄 ∈ Rd PEA_{3} ⟺ 𝔄 ⊧ MGR^{+}, provided 𝔄 is generated by Ra 𝔄.

Open problem 3.3 i. Is the condition that 𝔄 is generated by Ra 𝔄 needed in Theorem 3.2 ii?

ii. If the answer to the previous question is affirmative, then: For 𝔄 ∈ CA_{α}, let ℜ𝔡_{s} 𝔄 be the reduct of 𝔄 in which the substitutions s_{j}^{i} are basic operations and the d_{ij}’s are forgotten. Is then

ℜ𝔡_{s} 𝔄 ∈ S Rd PA_{3} ⟺ 𝔄 ∈ S Rd PEA_{3}

true for every 𝔄 ∈ CA_{3}?

We turn to investigating another type of connection between RAs and CAs. For an algebra 𝔄 and a subset X of A, Sg^{(𝔄)}X denotes the subalgebra of 𝔄 gnerated by X.

Consider the following statements about K ⊆ CA_{3}:

(⋆) In members of K, the cylindric operations do not generate more c_{2}-closed elements from c_{2}-closed elements than the relation algebraic operations do. In symbols:

Sg^{(ℜa ℭ)}X = ℜa Sg^{(ℭ)}X

for any ℭ ∈ K and X ⊆ Ra ℭ.

(⋆⋆) For any algebra 𝔄 there is at most one ℭ ∈ K (up to isomorphism) such that 𝔄 = ℜa ℭ and A generates ℭ.

We note that (⋆) and (⋆⋆) imply (⋆ ⋆ ⋆) below:

(⋆ ⋆ ⋆) For any algebra 𝔄 there is at most one ℭ ∈ K (up to isomorphism) such that 𝔄 ⊆ ℜa ℭ and A generates ℭ.

Theorems 5.3.12, 5.3.15 in [HMT85b] state that (⋆) and (⋆⋆) are true for K = S Nr_{3} CA_{4}, and Theorems 7,8 in Maddux [Mad78] state that (⋆) and (⋆⋆) are true for K = CA′_{3}, where

CA′_{3} = {𝔄 ∈ CA_{3} : ℜa 𝔄 ∈ SA}.

Notice that Theorem 3.2 i. says that CA′_{3} = CA_{3} ∩ Mod MGR^{+}. Therefore (⋆) and (⋆⋆) hold for CA_{3} ∩ Mod MGR^{+}, but we will see later that neither of (⋆), (⋆⋆) and (⋆ ⋆ ⋆) holds for CA_{3} ∩ Mod MGR.

Corollary 3.4 Let ℭ ∈ CA_{3} ∩ Mod MGR^{+} and X ⊆ Ra ℭ. Then

Sg^{(ℜa ℭ)}X = ℜa Sg^{(ℭ)}X.

Corollary 3.5 (Uniqueness of generated CA’s) For i = 1, 2, let ℭ_{i} ∈ CA_{3}∩Mod MGR^{+}, 𝔄_{i} = ℜa ℭ_{i} and assume that A_{i} generates ℭ_{i}. Then

𝔄_{1} ≅ 𝔄_{2} ⇒ ℭ_{1} ≅ ℭ_{2},

moreover, the second isomorphism is an extension of the first one.

Theorem 3.6 Corollaries 3.4 and 3.5 become false if we replace MGR^{+} with MGR in them.

Theorem 3.6 implies that [HMT85b] 5.3.12, 5.3.15 cannot be generalized from S Nr_{3} CA_{4} to CA_{3} ∩ Mod MGR. Similarly, Theorems 7,8 of Maddux [Mad78] do not generalize from CA′_{3} to CA_{3} ∩ Mod MGR.

By Theorem 3.2 i. and Theorem 2.5 i., ℜa^{∗}(CA_{3} ∩ Mod MGR^{+}) and ℜa^{∗} PEA_{3} are closed under taking subalgebras. In contrast with this, we have the following:

Theorem 3.7 ℜa^{∗} CA_{3} is not closed under taking subalgebras.

Outline of proof. By the method described in Remark 5.5 one can construct a ℭ ∈ CA_{3} and a subalgebra 𝔄 ⊆ ℜa ℭ such that ^{⌣} is not surjective in 𝔄. Hence 𝔄 ∉ ℜa^{∗} CA_{3} by Proposition 5.2 i.

Open problem 3.8 Is ℜa^{∗}(CA_{3} ∩ Mod MGR) closed under taking subalgebras?

4 RA’s from RRA’s via CA’s

In this section we will show that all of (⋆), (⋆⋆) and (⋆ ⋆ ⋆) (in §3) fail for K = CA_{3} and for K = CA_{3} ∩ Mod MGR. We will be able to use this fact for constructing nonrepresentable RA-like algebras from representable ones. We will do the following. We take a representable RA 𝔄, generate a CA_{3} ℭ with 𝔄 and then we take the RA-reduct of ℭ. Of course, we get a bigger, RA-like algebra. The question is how different this bigger algebra can be from the original 𝔄. In §3 we saw that if MGR^{+} is valid in ℭ, then we cannot get a proper superalgebra of 𝔄, we get back our original 𝔄. In this section we will see that there are situations when we really get a different algebra, even if MGR is valid in ℭ.

Let (R7^{⌣}) be

(R7^{⌣}) x = x^{⌣} → x; −(x; y) ≤ −y.

Though (R7^{⌣}) does not look like an equation, it is equivalent with the equation x;−(x;y) ≤ −y ∪ ([1 ; (x ⊕ x^{⌣})] ; 1) in every algebra of the discriminator variety S ℜa^{∗} CA_{3}. Clearly, (R7^{⌣}) is a special case of the axiom (R7) of RA (see §2 above).

RRA is the class of representable RA’s. Recall that x ∈ 𝔄 ∈ RA is called an equivalence element if x^{⌣} = x = x ; x. Jónsson [Jón88] proved that RAs generated by a single equivalence element are always representable and very small.

Theorem 4.1 There are an 𝔄 ∈ RRA and a ℭ ∈ CA_{3} such that

i. 𝔄 ⊆ ℜa ℭ, A generates ℭ (where A is the universe of 𝔄) and 𝔄 is generated by a single equivalence element.

ii. MGR holds in ℭ

iii. (R7^{⌣}) fails in ℜa ℭ and (R4), (R6) hold in ℜa ℭ.

The proof of Theorem 4.1 is based on^{1} the method of dilation.

Conjecture 4.2 There are 𝔄, ℭ as in Theorem 4.1 satisfying i. of Theorem 4.1 such that both (R4) and (R7^{⌣}) fail in ℜa ℭ.

Conjecture 4.3 There are 𝔄, ℭ as in Theorem 4.1 satisfying i. of Theorem 4.1 such that (R7^{⌣}) holds in ℜa ℭ and (R4) fails in ℜa ℭ.

By contrast, if (R7) holds in ℜa ℭ, then (R4) holds in ℜa ℭ, too, see Theorem 2.2 i.

Theorem 4.1 implies that all of (⋆), (⋆⋆) and (⋆⋆⋆) (in §3) fail for K = CA_{3}∩Mod MGR. Of course, Theorem 4.1 (and Conjectures 4.2, 4.3, if true) do not generalize to PEA’s (in place of CA’s), because of (4) in §2.

The following proposition says that

CA_{3} |̸= “RA-equivalence elements are also CA-equivalence elements”.

That is, ℜa ℭ may “think” that x is an equivalence element despite of ℭ’s thinking that it is not. We will not recall the definition of a CA-equivalence element, but we note that if x is such then x · s_{2}^{0}x ≤ s_{2}^{1}x.

1The method in these proofs dealing with equivalence elements evolved from ideas developed by H.

Andréka, S. Givant and I. Németi to obtain non-representable cylindric algebras and semiassociative relation algebras generated by a single equivalence element, cf. e.g. Andréka-Givant-Németi [AGN95], Givant [Giv94].

Proposition 4.4 CA_{3} |̸= d_{01} ≤ x = x^{⌣} = x; x → x · s_{2}^{0}x ≤ s_{2}^{1}x.

The following theorem solves the first part of Problem 11 from the “Problem Session Paper” of [AMN90].

Theorem 4.5 Let α > 2. Then there is a ℭ ∈ CA_{α} generated by a set G of elements satisfying MGR , such that ℭ |̸= MGR. (I.e. MGR has one free variable x, so we could write MGR(x). Now, (∀a ∈ G)ℭ ⊧ MGR[a] but for some b ∈ C, ℭ ⊧ ¬MGR[b].)

In the rest of this section some non-finite axiomatizability results will show up. They are included here because the methods and issues studied so far lead to them naturally.

So far, we have generated a bigger RA, ℜa ℭ from a smaller RA, 𝔄 via a CA_{3}. Let us see what happens if we use a CA_{n} for some big n < ω. If n > 3, then the RA-axioms (R1—R7) cannot be “destroyed”. But we conjecture that even then infinitely many equations valid in RRAs can be destroyed. The following theorem improves Monk’s result saying that RRA is not finitely axiomatizable (Monk [Mon64], cf. also Andréka-Németi [AN94]).

For 2 < n < ω, let

K_{n} = S{ℜa ℭ : ℭ ∈ CA_{n} and (∃𝔄 ∈ RRA)(𝔄 ⊆ ℜa ℭ and A generates ℭ)}.

We note that RRA ⊆ K_{3} and if n > 3 then RRA ⊆ K_{n} ⊆ RA.

Theorem 4.6 RRA is not axiomatizable finitely over K_{3}. That is, for no finite set E_{0} of formulas does E_{0} ∪ Th(K_{3}) axiomatize RRA, where Th(K_{3}) is the first order theory of K_{3}.

The proof goes by relation algebraic splitting [AMN91], [AN90], dilation and by the methods in [And96].

Conjecture 4.7 RRA is not axiomatizable finitely over K_{n}, for any 3 < n < ω.

We conjecture that the proof of 4.6 will go through with some modifications.

Theorem 4.8 Assume 𝔄 ⊆ ℜa ℭ, ℭ ∈ CA_{3} is simple, and 𝔄 is finitely generated. Then the subalgebra Sg^{(ℭ)}A is generated by a single element.

The above result can be generalized from the RA–CA relationship to the CA_{n}–CA_{n+1} relationship, as follows.

Theorem 4.9 Let ℭ ∈ CA_{n+1} be simple. Then for any finite X ⊆ Nr_{n} ℭ = {x ∈ C : c_{n} x = x} there is an a ∈ C which generates X, i.e., X ⊆ Sg^{(ℭ)}{a}.

RCA_{n} denotes the class of representable CA_{n}’s.

During the 1987 Asilomar Algebraic Logic conference, R. Maddux brought up the question whether Jónsson’s theorem saying that RRA is not axiomatizable by any set Σ of equations if Σ involves only finitely many variables could perhaps be used to prove Andréka’s analogous result for RCA_{n} and RCA_{ω}. Theorems 4.8 and 4.9 point in the direction that the answer will be probably in the negative. The reason for this is that the key step in proving the Jónsson–Andréka type results is to construct non-representable algebras 𝔄_{k} for each k < ω such that every k-generated subalgebra of 𝔄_{k} is representable. Suppose we constructed such an RA 𝔄_{k}. If we build a CA ℭ_{k} from 𝔄_{k} by the usual methods, then 𝔄_{k} ⊆ ℜa^{∗} ℭ_{k}, and A_{k} will generate ℭ_{k}. But then by Theorems 4.8 and 4.9, ℭ_{k} is 1-generated, hence cannot be used in the described style.

At the same time, Theorems 4.8 and 4.9 can be used to prove a new non-finitazibility result (analogous to Maddux’s one cited in [TG87, p. 62, footnote 6]).

For 2 < n < ω, let

Eq_{1}(RCA_{n}) = {e : RCA_{n} ⊧ e, e is an equation involving at most one variable},

and let T h(RCA_{n}) stand for the first-order theory of RCA_{n}.

Corollary 4.10 For any finite set Σ ⊆ T h(RCA_{3}) we have

Σ |̸= Eq_{1}(RCA_{3}).

The proof uses Andréka’s proof of non-finitizability of S Nr_{n} CA_{n+2} in [And96] (see also [And]), in conjunction with Theorem 4.8.

Conjecture 4.11 Let 3 < n < ω. Then for any finite set Σ ⊆ T h(RCA_{n}) we have

Σ |̸= Eq_{1}(RCA_{n}).

5 Subvarieties of S ℜa^{∗} CA_{3}

Fact 5.1 S ℜa^{∗} CA_{3} is a discriminator variety.

Proof. This is proved exactly the same way as S Nr_{α} CA_{α+β} is proved to be an equational class in [HMT85a]. □

We conjecture that S ℜa^{∗} CA_{3} is a finitely axiomatizable variety.

Proposition 5.2 i. ^{⌣} is a Boolean automorphism in every member of ℜa^{∗} CA_{3}.

ii. Let x^{∘} = s_{1}^{2}s_{0}^{1}s_{2}^{0}x. Then ^{∘} is the inverse of ^{⌣}, that is, ℜa^{∗} CA_{3} ⊧ x^{⌣∘} = x = x^{∘⌣}, by a slight abuse of notation (i.e. pretending that ^{∘} is an operation of ℜa^{∗} CA_{3}).

Proposition 5.3 The following statements are equivalent in S ℜa^{∗} CA_{3}.

i. ∀x(x ≤ x^{⌣⌣})

ii. ∀x(x ≥ x^{⌣⌣})

iii. ∀x(x = x^{⌣⌣})

The proof is based on the observation that in every BAO where ^{⌣} is a BA-homomorphism, we have ∀xx ≤ x^{⌣⌣} ↔ ∀xx ≥ x^{⌣⌣}.

By contrast, we have the following.

Theorem 5.4 The quasi-equations (x^{⌣}^{⌣} ≤ x → x^{⌣}^{⌣} = x) and (x ≤ x^{⌣}^{⌣} → x^{⌣}^{⌣} = x) can fail in ℜa^{∗} CA_{3}. (We note that both are valid in RA-reducts of finite CA_{3}’s, and neither of them follows in nBAO from (R0—R3, R5—R7).)

Remark 5.5 In connection with Theorem 5.4, we note that for α > 2, CA_{α} ⊧ x^{⌣⌣} ≤ c_{0}x · c_{1}x. Further, we claim that the method of twisting, as described in [HMT85b] is not suitable for obtaining, from RCA’s, a CA_{3} ℭ, and an x ∈ ℜa ℭ for which x^{⌣⌣} < x or x < x^{⌣⌣} (at least not in finitely many applications of twisting). However, it is possible to generalize the definition of twisting the following way. We will use the notation of [HMT85b] 3.2.71. We choose κ = 2. In [HMT85b], two 2-closed elements X, Y are chosen denoted as X = x/T_{κ}, Y = y/T_{κ}. Instead of choosing only two elements X, Y, we could choose a family {X_{i} : i ∈ I} of 2-closed elements. As X was decomposed to two parts X_{0}, X_{1} in [HMT85b], now we could decompose each X_{i} to be a disjoint union of (X_{i})_{0}, (X_{i})_{1}. Further, all the natural translations of conditions (1)—(3) in [HMT85b] should be postulated for (X_{i})_{0}, (X_{i})_{1} (i ∈ I). E.g., for each distinct i, j ∈ I we could postulate (1) of [HMT85b] for (X_{i})_{0}, (X_{i})_{1}, (X_{j})_{0}, (X_{j})_{1} in place of X_{0}, X_{1}, Y_{0}, Y_{1}. Next, let p be an arbitrary permutation of I. Now, the new T′_{2} (determining the new c′_{2}) is defined to be an equivalence relation with equivalence classes (X_{i})_{0} ∪ (X_{p(i)})_{1}, for i ∈ I and the rest of T′_{2} is defined exactly as in [HMT85b]. This generalized form of twisting (i) always yields a CA when applied to a CA, and (ii) is suitable for obtaining an instance of x^{⌣⌣} < x in some “twisted” RCA.

Next we look at subclasses of S ℜa^{∗} CA_{3} defined by one or more of the (quasi)- equational axioms (R1—R7), (cycle law). Though the cycle law consists of four quasiequations, each of these is equivalent (in ℜa^{∗} CA_{3}) to an equation. The reason for this is the following. Let V be a discriminator variety of normal BAO’s. Then there is a term function c(x) such that in every subdirectly irreducible member of V, c(0) = 0 and c(x) = 1 if x > 0. Let q abbreviate the quasiequation τ_{0} = τ_{1} → σ_{0} = σ_{1}. Assume q is strongly positive in the sense that no constant symbol other than 0 and no complementation “−” occurs in q. Then q is equivalent (in V) with the equation e(q) defined as σ_{0}−c(τ_{0}⊕τ_{1}) = σ_{1}−c(τ_{0}⊕τ_{1}); i.e.,

V ∩ Mod(q) = V ∩ Mod(e(q)).  (9)

To see this, it is enough to substitute x_{i} − c(τ_{0} ⊕ τ_{1}) for each variable x_{i} of q, and to observe that relativization with −c(y) is an endomorphism of the strongly positive reduct of members of V.

It seems that (9) remains true if in q we require only τ_{0}, τ_{1} to be strictly positive and we leave σ_{0}, σ_{1} to be arbitrary (we did not check this). Also, the translation function e can be extended to quasiequations of the form τ_{0} = τ′_{0} ∧… ∧ τ_{n} = τ′_{n} → σ = σ′ in such a way that (9) remains true. Here again it seems to be enough to restrict the form of τ_{i}, τ′_{i} for i ≤ n.

Because of (9), all of the quasiequations occurring in (cycle law) are equivalent (in S ℜa^{∗} CA_{3}) with certain equations. Therefore the sub-quasivarieties they determine are actually subvarieties of S ℜa^{∗} CA_{3}.

Theorem 5.6 below summarizes the connection between the subvarieties of S ℜa^{∗} CA_{3} defined by a subset of the RA-axioms. It says that the only implications that hold in S ℜa^{∗} CA_{3} between the RA-axioms are (3) and Theorem 2.2 i–iii. in §2.

Theorem 5.6 Let E ∪ {φ} ⊆ {(R1), (R4), (R6), (R7)}, φ ∉ E. Then ℜa^{∗} CA_{3} ∩ Mod E ⊧ φ iff S ℜa^{∗} CA_{3} ∩ Mod E ⊧ φ iff one of the following conditions hold:

1. {((R6), (R7)} ∩ E ≠ ∅ and φ = (R4)

2. {((R1), (R7)} ⊆ E and φ = (R6)

3. {((R1), (R6)} ⊆ E and φ = (R7)

Proof. That the three conditions are sufficient (i.e. both (R6) and (R7) imply (R4) in S ℜa^{∗} CA_{3} etc.) follows from Theorem 2.2 i, ii (for condition 1.), Theorem 2.2 iii (for condition 2.) and Theorem 2.2 ii together with (3) in §2 (for condition 3.).

Now suppose that ℜa^{∗} CA_{3} ∩ Mod E ⊧ φ, φ ∉ E. Then φ cannot be (R1), since (R1) is not implied by {(R4), (R6), (R7)} in S ℜa^{∗} CA_{3} (this is because SA ≠ RA, proved in Maddux [Mad78], [Mad82]). If φ is (R4), then E must contain either (R6) or (R7) by Theorem 2.2 vi. If φ is (R6), then E must contain (R7) by Theorem 2.2 iv. and (R1) by Theorem 2.2 i, v. Finally, if φ is (R7), then E must contain (R6) by Theorem 2.2 iii, iv., and E must contain (R1) by Theorem 4.1. □

Notation. In the rest of this section, (R7) ⇒ (R4) means that V ∩ Mod (R7) ⊧ (R4), and similarly, (R4) ⇏ (R7) denotes that V ∩ Mod (R4) |̸= (R7) where V = S ℜa^{∗} CA_{3}. The notation is the same for the other members of (R1)—(cycle law).

In the next theorem we investigate the interconnections of the cycle law and the RA-axioms.

Theorem 5.7 In S ℜa^{∗} CA_{3} we have the following (using the notation introduced above).

i. (R6, R7) ⇔ (cycle law)

ii. (R7) ⇔ ((x; y) · z = 0 → (x^{⌣} ; z) · y = 0) ⇔ ((x; y) · z = 0 ↔ (x^{⌣} ; z) · y = 0)

iii. (R6) ⇔ (z ≤ y^{⌣} ; x^{⌣} ↔ z^{⌣} ≤ x; y)

iv. ((x^{⌣} ; z) · y = 0 ↔ (z ; y^{⌣}) · x = 0) + (R4) ⇏ (R6)

v. ((x; y) · z = 0 ↔ (z ; y^{⌣}) · x = 0) + (R4) ⇏ (R6)

Outline of proof. i. This is true because of (6) in §2 and Theorem 2.6.

ii. The first equivalence is true already in nBAO’s, the second holds because of Theorem 2.2 i.

iii. One proves this using Theorem 2.2 ii.

Let (R6)^{↔} denote the formula z ≤ y^{⌣} ; x^{⌣} ↔ z^{⌣} ≤ x; y. The interest in (R6)^{↔} stems from (I) the fact that in BAO ∩ Mod((R4)), (R6)^{↔} is equivalent to (R6), and from (II) the similarity between (R6)^{↔} and the cycle law. Then in nBAO we have

(R1_{0}, R3) + (R6)^{↔} ⇏ (R4) and (R1_{0}, R3) + (R6)^{↔} ⇏ (R6).

To prove this, we construct a normal BAO 𝔅 such that 𝔅 ⊧ (R1_{0}, R3) + (R6)^{↔} but both (R4) and (R6) fail in 𝔅. Let ω = {0, 1,…, n,…} be the set of atoms of 𝔅. For each x ∈ ω we let x^{⌣} = x. We let 1′ = 0. The least element of 𝔅 will be denoted by 0^{𝔅} to avoid confusion with 0 ∈ ω. Define ; : ω × ω ⟶ ω ∪ {0^{𝔅}} as follows: 0 ; n = n = n ; 0 for all n ∈ ω; and if 0 ∉ {n, m} ⊆ ω, then n; m is m − 2n if m ≥ 2n, n − 2m if n ≥ 2m and 0^{𝔅} otherwise. 𝔅 is defined as the complex algebra ℭ𝔪⟨ω,^{⌣},;⟩ of the atom structure ⟨ω,^{⌣},;⟩ defined above.

The proofs of iv—v go by dilation. □

Remarks. BAO + (R3) + ((x; y) · z = 0 ↔ (x^{⌣} ; z) · y = 0) ⇒ (R4) but nBAO + (R3) + ((x; y) · z = 0 → (x^{⌣} ; z) · y = 0) ⇏ (R4).

The key to the power of the cycle law seems to be (R3) in the following sense. In BAO ∩ Mod(R3) we have (cycle law) ⇔ R2—R7 e.g. by modifying the proofs of Theorems 8–10 in [Mad78], pp. 16–20 as follows. One checks that the proof of Theorem 8 uses only our axioms. One modifies the proof of Theorem 9 deriving it directly from BAO and Theorem 8. Then, by Theorems 8, 10, we get BAO∩Mod(R3) ⊧ (cycle law) ⇒ (R4, R6). Then by R4 and R6 we derive 1′ ; x = x as in [CT51]. The rest goes through by e.g. [Mad78]. This yields ⇒. The other direction follows from Lemma 1.2 in [Giv94]. By contrast, we have

nBAO ∩ Mod(R0—R2, R5—R7, cycle law) ⇏ (R4)

nBAO ∩ Mod(R0—R2, R4, R5, R7, cycle law) ⇏ (R6),

and nBAO ∩ Mod(R0—R3, R5—R7) ⇏ (R4).

The last statement is shown by the following simple example: take the two-element RA and change ^{⌣} such that 1^{⌣} = 0 = 0^{⌣}.

6 Axiomatization of neat reducts and related results

For completeness we include here the equational characterization of S Nr_{n} CA_{n+1} for the case n = 3 given in Andréka [And]. Let Ax consist of the standard CA-axioms (C0—C7) together with (C8—C12) below.

(C8) MGR

(C9) c_{i}x = s_{j}^{i}c_{j}y → c_{j}c_{k}x ≤ c_{j}c_{k}(c_{j}x · c_{i}y · c_{k}(s_{k}^{j}c_{k}x · s_{k}^{i}c_{k}y))

(C10) c_{i}x = s_{j}^{i}c_{j}y ∧ c_{j}x · c_{i}y · c_{k}(s_{k}^{j}c_{k}x · s_{k}^{i}c_{k}y) ≤ d_{ij} → x = y

(C11) c_{i}x = c_{i}y → c_{j}c_{k}x ≤ c_{j}c_{k}(s_{k}^{j}c_{k}x · s_{k}^{j}s_{j}^{i}c_{k}y · c_{k}(c_{j}x · s_{j}^{i}c_{j}y))

(C12) c_{i}x = c_{i}y ∧ s_{k}^{j}(c_{k}x · s_{j}^{i}c_{k}y) · c_{k}(c_{j}x · s_{j}^{i}c_{j}y) ≤ d_{ij} → x = y

Let 𝔄 ∈ CA_{n+1}. Recall that Nr_{n} 𝔄 = {x ∈ A : c_{n} x = x} and 𝔑r_{n} 𝔄 is the subalgebra of the CA_{n}-reduct of 𝔄 with universe Nr_{n} 𝔄. S Nr_{n} CA_{n+1} = S{𝔑r_{n} 𝔄 : 𝔄 ∈ CA_{n+1}}.

Theorem 6.1 (Andréka [And]) S Nr_{3} CA_{4} = Mod (C0—C12).

Now [HMT85b]§5.3 Theorem 5.3.17 implies RA = ℜa^{∗} Mod (C0—C12). In view of this, it would be nice to see a set of natural (like MGR or MGR^{+}) CA-theoretic equations E such that

ℜa ℭ ⊧ (R1) ⟺ ℭ ⊧ E  (10)

holds for every ℭ ∈ CA_{3}.

The mechanical translation of (c_{2}x;c_{2}y);c_{2}z = c_{2}x;(c_{2}y;c_{2}z) where x;y = c_{2}(s_{2}^{1}x·s_{2}^{0}y), though satisfies (10), is NOT natural enough from the CA-theoretic point of view.

Open problem 6.2 i. Simplify axioms C8—C12. ii. Assume (C0—C7)+MGR^{+}. In view of this simplify the remaining (C9—C12). I.e.,

obtain a simple set E of equations such that (C0—C7) + MGR^{+} + E ⊧ (C9—C12) and vice versa, i.e. Nr_{3} CA_{4} ⊧ E.

Open problem 6.3 Let Dil(RCA_{α}) denote the class of algebras obtainable from RCA_{α}’s by (possibly repeated or simultaneous) application of dilation as described in [HMT85b]. It would be nice to have an axiomatic (or any) description of S Dil(RCA_{α}). Actually, the work Andréka–Givant–Németi [AGN95] seems to point in the direction that such a description is possible.

For related work see Monk [Mon61], Maddux [Mad78], [Mad90], Sain–Thompson [ST90], Andréka–Németi [AN88], Andréka–Givant–Németi [AGN95], Givant [Giv94].

A paper which is a direct continuation of the present one is in preparation [NS95]. In that paper, among others, we will give an answer to the following problem raised by Leon Henkin in the 70’s. “Can all CA’s be obtained from RCA’s by the construction methods described in [HMT85b] when performed in some finite, fixed order?”

Acknowledgement: István Németi would like to express his thanks to Hajnal Andréka and Steven Givant, because working with them on cylindric algebras gave the stimulation to his mind which eventually led to his contribution to these constructions.

References

[AGN95] H. Andréka, R. Givant, and I. Németi. The structure of cylindric algebras generated by relativizations. Manuscript, 1992–1995.

[AMN90] H. Andréka, J.D. Monk, and I. Németi, editors. Algebraic Logic, volume 54 of Colloq. Math. Soc. J. Bolyai, Amsterdam, 1990. North-Holland.

[AMN91] H. Andréka, R. D. Maddux, and I. Németi. Splitting in relation algebras. Proceedings of the Amer. Math. Soc., 111(4):1085–1093, April 1991.

[AN88] H. Andréka and I. Németi. Relation algebraic conditions for representability of cylindric and polyadic algebras. Preprint, Math. Inst. of the Hung. Acad. of Sci., 1988.

[AN90] H. Andréka and I. Németi. Constructing unusual relation algebras. Manuscript, 1990.

[AN94] H. Andréka and I. Németi. On the finitization problem for expanded RRA’s and RCA’s. Manuscript, 1994.

[And] H. Andréka. Finite axiomatizability of S Nr_{n} CA_{n+1} and non-finite axiomatizability of S Nr_{n} CA_{n+2}. Lecture notes for a series of lectures given at the Algebraic Logic Meeting, Oakland, CA, June 1990.

[And96] H. Andréka. Complexity of equations valid in algebras of relations. Annals of Pure and Applied Logic, 1996. To appear.

[CT51] L.H. Chin and A. Tarski. Distributive and modular laws in the arithmetic of relation algebras. University of California Publications in Mathematics, New Series, 1:341–384, 1951.

[Giv94] S.R. Givant. The structure of relation algebras generated by relativizations, volume 156 of Contemporary Mathematics. American Mathematical Society, Providence, R.I., 1994.

[HMT85a] L. Henkin, J. D. Monk, and A. Tarski. Cylindric Algebras, Part I. North-Holland, Amsterdam, 1971, 1985.

[HMT85b] L. Henkin, J. D. Monk, and A. Tarski. Cylindric Algebras, Part II. North-Holland, Amsterdam, 1985.

[Jón88] B. Jónsson. Relation algebras and Schröder categories. Discrete Mathematics, 70:27–45, 1988.

[Mad78] R.D. Maddux. Topics in relation algebras. PhD thesis, University of California, Berkeley, 1978.

[Mad82] R.D. Maddux. Some varieties containing relation algebras. Trans. Amer. Math. Soc., 272:501–526, 1982.

[Mad90] R.D. Maddux. Introductory course on relation algebras, finite-dimensional cylindric algebras, and their interconnections. In Andréka et al. [AMN90], pages 361–392.

[Mon61] J.D. Monk. Studies in cylindric algebra. PhD thesis, University of California, Berkeley, 1961.

[Mon64] J. D. Monk. On representable relation algebras. Michigan Math. J., 11:207– 210, 1964.

[NS95] I. Németi and A. Simon. Relation algebras from cylindric and polyadic algebras II. In preparation, 1995.

[ST90] I. Sain and R. Thompson. Strictly finite schema axiomatization of quasipolyadic algebras. In Andréka et al. [AMN90], pages 539–571.

[TG87] A. Tarski and S. Givant. A formalization of set theory without variables. American Mathematical Society, Providence, R.I., 1987.

Mathematical Institute Hungarian Academy of Sciences Budapest Pf. 127 H-1364 Hungary