NOTIONS OF DENSITY THAT IMPLY REPRESENTABILITY IN ALGEBRAIC LOGIC

HAJNAL ANDRÉKA, STEVEN GIVANT, SZABOLCS MIKULÁS, ISTVÁN NÉMETI, AND ANDRÁS SIMON

Abstract. Henkin and Tarski proved that an atomic cylindric algebra in which every atom is a rectangle must be representable (as a cylindric set algebra). This theorem and its analogues for quasi-polyadic algebras with and without equality are formulated in Henkin-Monk-Tarski [1985].

We introduce a natural and more general notion of rectangular density that can be applied to arbitrary cylindric and quasi-polyadic algebras, not just atomic ones. We then show that every rectangularly dense cylindric algebra is representable, and we extend this result to other classes of algebras of logic, for example quasi-polyadic algebras and substitution-cylindrification algebras with and without equality, relation algebras, and special Boolean monoids. The results of op. cit. mentioned above are special cases of our general theorems.

We point out an error in the proof of the Henkin-Monk-Tarski representation theorem for atomic equality-free quasi-polyadic algebras with rectangular atoms. The error consists in the implicit assumption of a property that does not, in general, hold. We then give a correct proof of their theorem.

Henkin and Tarski also introduced the notion of a rich cylindric algebra and proved in op. cit. that every rich cylindric algebra of finite dimension (or, more generally, of locally finite dimension) satisfying certain special identities is representable.

We introduce a modification of the notion of a rich algebra that, in our opinion, renders it more natural. In particular, under this modification richness becomes a density notion. Moreover, our notion of richness applies not only to algebras with equality, such as cylindric algebras, but also to algebras without equality. We show that a finite dimensional algebra is rich iff it is rectangularly dense and quasi-atomic; moreover, each of these conditions is also equivalent to a very natural condition of point density. As a consequence, every finite dimensional (or locally finite dimensional) rich algebra of logic is representable. We do not have to assume the validity of any special identities to establish this representability. Not only does this give an improvement of the Henkin-Tarski representation theorem for rich cylindric algebras, it solves positively an open problem in op. cit. concerning the representability of finite dimensional rich quasi-polyadic algebras without equality.

Boolean algebra is an abstract algebraic theory that allows us to study the laws and theorems of propositional logic using modern algebraic methods. There

The research of Andréka, Mikulás, Németi, and Simon was supported by the Hungarian National Foundation for Scientific Research, grant numbers T16448, T7255, and F17452. Givant’s research was supported by the Soros Foundation and by Mills College.

are concrete set-theoretical Boolean algebras that consist of collections of sets and set-theoretical operations (say, union and complementation). There are also abstract Boolean algebras that are the models of a certain finite collection of axioms. Stone’s representation theorem states that every abstract Boolean algebra can be represented as (i.e., is isomorphic to) a concrete Boolean algebra of sets. Thus, the axioms for Boolean algebra adequately capture the intuition of the concrete, set-theoretical models.

There are also abstract algebraic theories associated with more expressive parts of logic, for instance first-order logic. Examples include the relation algebras that date back to Peirce and Schröder, the cylindric algebras of Tarski and his collaborators, the polyadic and quasi-polyadic algebras of Halmos, and many others. In each of these domains, a situation analogous to that in Boolean algebra exists: there is a class of concrete, set-theoretical algebras and a more comprehensive class of abstract algebras that model a certain finite set (or, in infinite dimensions, a finite scheme) of equations. In each case the problem arises whether every abstract algebra can be represented as a concrete set-theoretical one. In contrast to the situation in Boolean algebra, the answer for algebras connected with first-order logic is in general negative. Not every abstract relation algebra is isomorphic to a set algebra of binary relations, not every cylindric algebra of dimension α ≥ 2 is isomorphic to a set algebra of α-ary relations, and so on.

These negative results lead to the important problem of finding various interesting criteria that do imply the representability of algebras of logic. For example, Jónsson-Tarski [1952] showed that an atomic relation algebra in which each atom is “functional” is representable. Using this result, Tarski [1955] was then able to prove the fundamental theorem that the class of all representable relation algebras can be axiomatized by an infinite set of equations.

In the domain of cylindric algebras, one of the main representation theorems involves the notion of a rectangle. In set-theoretical cylindric algebras of finite dimension α, a rectangle is the intersection of α many pairwise orthogonal cylinders. In dimension α = 2 this corresponds to the usual notion of a rectangle. Henkin and Tarski gave an abstract definition of the notion of a rectangle and proved that every atomic cylindric algebra (of dimension at least 2) in which all atoms are rectangles is representable (see Henkin-Monk-Tarski [1985], Theorem 3.2.14).

In this paper we introduce a new notion: an algebra of logic is rectangularly dense if every non-zero element is above a non-zero rectangle. A particular example of such an algebra is an atomic cylindric algebra in which all atoms are rectangles. We show that many classes of rectangularly dense algebras of logic — in particular, rectangularly dense cylindric algebras — are representable. The proof for cylindric algebras breaks into three main steps. We show (in Lemma 3.10) that a simple, rectangularly dense cylindric algebra of finite dimension is in fact atomic, and hence representable by the Henkin-Tarski Theorem. We also show (in Corollary 2.10 and Theorem 2.11) that a rectangularly dense cylindric algebra of finite dimension is the directed union of subdirect products of countable, simple, rectangularly dense cylindric algebras, and hence representable. In this theorem we actually establish a much more general result, applying to arbitrary Boolean algebras with operators in a discriminator variety; one consequence of this theorem is that, e.g., the representability of the class of simple φ-dense algebras (for some notion φ of objects, such as rectangles) implies the representabilty of all φ-dense algebras. Finally, we show (in Theorem 3.11) how to make the passage from finite to infinite dimensions. We then use our representation theorems to prove that for many other classes of algebras of logic, rectangular density implies representability. In Section 4 we treat the case of quasi-polyadic algebras and substitution-cylindrification algebras with and without equality, and in Section 6 the case of relation algebras and special Boolean monoids.

In Section 5 we investigate two other notions of density: richness and point density. Both are related to notions that have already been studied in the literature and that are known to imply representability in certain special cases. The notion of richness that we shall introduce is a variant of a notion with the same name that was studied by Henkin and Tarski (see op. cit., Section 3.2, or Henkin-Tarski [1961], Theorem 2.11). They proved that every rich algebra of finite dimension α ≥ 2 in which a certain collection of equations ε_{ij} (i, j < α and i ≠ j) is valid must be representable. Jónsson-Tarski [1952] essentially proved in Theorem 4.30 that every atomic relation algebra in which each atom is a “point” is representable. (However, they do not introduce the term “point”.)

Our particular variant of the notion of richness, and our definition of point density, are formulated without any reference to diagonal (or identity) elements. Thus, in our formulation these notions can be applied not only to cylindric algebras and relation algebras, but also to other algebras of logic in which diagonal elements are not present, for example quasi-polyadic algebras and substitution cylindrification algebras without equality. We prove in Theorems 5.18 and 6.6 that in each of the finite dimensional algebras of logic 𝔄 under discussion, the three density notions essentially coincide. Specifically, 𝔄 is rich iff it is point dense iff it is rectangularly dense and quasi-atomic; moreover, in the presence of diagonal elements (e.g., in the case of cylindric algebras and relation algebras) we may drop “quasi-atomic”: 𝔄 is rich iff it is point dense iff it is rectangularly dense.

This equivalence theorem helps to clarify the relationship between the two representation theorems of Henkin-Monk-Tarski [1985] and the representation theorem of Jónsson-Tarski [1952] mentioned above. It also shows that by modifying somewhat the definition of richness, one can obtain (from Theorem 3.11) a representation theorem for rich cylindric algebras without assuming the validity of the equations ε_{ij} . Finally, it shows that finite dimensional quasi-polyadic algebras (without equality) that are rich are representable. This solves positively Problem 5.6 in Henkin-Monk-Tarski [1985].

The original motivation behind the theorems in Sections 3, 4, and 6 lies not in algebraic logic, but in logic. Some of the authors were interested in the question of the completeness of several versions of first-order logic (corresponding to cylindric, quasi-polyadic, and substitution-cylindrification algebras) and of arrow logic (corresponding to relativized relation algebras and Boolean monoids). The analogue in algebraic logic of a completeness theorem is a representation theorem. To establish the completeness theorems, representation theorems for rectangularly dense algebras were needed. The known theorems were inadequate for the task because they required the additional hypothesis of atomicity. The interested reader is referred to Andréka-Németi-Sain [1994] and Mikulás [1995], [1996] for further details.

1. Preliminaries

We suppose the ordinal numbers to be defined so that each ordinal is equal to the set of its predecessors. The smallest infinite ordinal is denoted by “ω”. The symbols “0” and “1” will be used in two different senses: as the names of the first two ordinals, and as the names of the least and greatest elements in a Boolean algebra. No confusion should arise from this dual use of notation. We shall sometimes use lower case Greek letters to denote ordinals, but usually we shall use i, j, k, ℓ, m, n, especially as subscripts of ordinally indexed operations.

The collection of all subsets of a set A will be denoted by Sb(A). If f is a mapping from A to some set, and a ∈ A, then we shall sometimes write fa, instead of f(a), to denote the value of f at a. The set of all mappings from A into a set B is denoted by ^{A}B and is called the A^{th} power of B.

Upper case German script letters 𝔄, 𝔅, ℭ, … denote algebras, and the corresponding upper case Roman letters A, B, C, … denote the corresponding universes. If 𝔄 = ⟨A , O_{i}⟩_{i∈I}, then the operations O_{i} are called the fundamental operations of 𝔄. Two algebras 𝔄 = ⟨A , O_{i}⟩_{i∈I} and 𝔅 = ⟨B , Q_{j}⟩_{j∈J} are of the same similarity type provided that I = J and that O_{i} and Q_{i} have the same rank (i.e., take the same number of arguments) for each i ∈ I. 𝔅 is a reduct of 𝔄 (to a subset J of I) if Q_{i} = O_{i} for each i ∈ J. If 𝔅 is a reduct of 𝔄, then 𝔄 is called an expansion of 𝔅. A subalgebra of a reduct is called a subreduct. An algebra 𝔄 is simple provided that it has at least two elements and every homomorphism from 𝔄 into another algebra is either constant or one-one. 𝔄 is a subdirect product of a family of algebras ⟨𝔅_{i} : i ∈ I⟩ if it is a subalgebra of the direct product and if, for each i ∈ I, the i^{th} projection function maps 𝔄 onto the factor algebra 𝔅_{i}. 𝔄 is subdirectly irreducible if it has at least two elements and if, for any isomorphism f between 𝔄 and a subdirect product of algebras, the composition of f with at least one of the projection functions is an isomorphism. By a well-known theorem of Birkhoff, every algebra is a subdirect product of subdirectly irreducible algebras.

A class of algebras is called a variety if it is axiomatizable by a set of equations. By another famous theorem of Birkhoff, a class of algebras is a variety iff it is closed under the formation of homomorphic images, subalgebras, and direct products.

We shall conceive of Boolean algebras as algebras of the form

𝔄 = ⟨A , +^{𝔄} , −^{𝔄}⟩ .

When no confusion can arise, we shall drop the superscript references to 𝔄 on the operations. A similar remark applies in other, analogous situations. The binary operations · and ⊕ of Boolean multiplication and symmetric difference, the constants 0 and 1, and the partial ordering ≤ are defined in 𝔄 in the usual way. For example, we define a ≤ b iff a + b = b. This definition makes clear that, in Boolean algebra, every inequality can be expressed as an equation. The class of all Boolean algebras is denoted by BA. We shall also use this notation as an abbreviation for the phrase “Boolean algebra”. If X ⊆ A, then ∑^{𝔄}X and ∏^{𝔄}X, or simply ∑X and ∏X, denote the supremum and infimum of X in 𝔄, whenever they exist. In particular, ∑∅ = 0 and ∏∅ = 1. A Boolean algebra is complete if the supremum and infimum of every set of elements exist, and atomic if every non-zero element is above an atom, i.e., a minimal non-zero element. A homomorphism f from a Boolean algebra 𝔄 into a Boolean algebra 𝔅 is said to be complete provided that, for every X ⊆ A, if ∑X exists (in 𝔄), then ∑{f(x) : x ∈ X} exists (in 𝔅) and f(∑X) = ∑{f(x) : x ∈ X}.

In writing algebraic expressions we follow the usual conventions concerning the omission of parentheses: unary operations have the highest priority, then operations of multiplication, and then operations of addition. Thus, for example, the expression a · −b + c is to be read as [a · (−b)] + c.

We assume that a first-order language (sometimes referred to as an elementary language) is correlated with each class of algebras of a given similarity type. The basic sentential connectives of the language are conjunction, disjunction, and negation, and there is a universal and an existential quantifier. A formula is open if it contains no quantifiers. An open formula that is the disjunction of one equation with a (possibly empty) finite collection of negations of equations is called a conditional equation. An open formula preceded by universal quantifiers is called a universal formula. A formula is positive if it contains no occurrences of the negation symbol.

Suppose that τ(x_{0}, …, x_{n−1}) is a term in the language of an algebra 𝔄 with variables among x_{0}, …, x_{n−1}. Then τ^{𝔄} denotes the n-ary operation defined by τ in 𝔄. Similarly, if φ(x_{0}, …, x_{n−1}) is a formula in the language of 𝔄 with variables among x_{0}, …, x_{n−1}, then φ^{𝔄} denotes the n-ary relation defined by φ in 𝔄. Of course this notation should also contain some reference to the rank n of the operation or relation being defined. However, it will always be clear from our discussion which n we have in mind. An operation f on A, say of rank n, is term-definable in 𝔄 if there is a term τ(x_{0}, …, x_{n−1}) such that f coincides with τ^{𝔄}. An algebra 𝔅 is a term definitional extension of 𝔄 if 𝔅 is an expansion of 𝔄 and if every fundamental operation of 𝔅 that does not occur among the fundamental operations of 𝔄 is term definable in 𝔄. An algebra 𝔅 is an elementary subalgebra (or an elementary submodel) of 𝔄 provided that 𝔅 is a subalgebra of 𝔄, and that, for each elementary formula φ(x_{0}, …, x_{n−1}) in the language of 𝔄 and each sequence y of n elements from B, y is in φ^{𝔄} iff it is in φ^{𝔅}.

A formula φ with one free variable is preserved (respectively, strictly preserved) under homomorphisms on 𝔄 if, for every homomorphism f from 𝔄 to an algebra 𝔅 and every element y of 𝔅 we have y in φ^{𝔅} if (respectively, if and only if) there is an element x in φ^{𝔄} such that f(x) = y.

2. Dense Boolean algebras with operators

We recall from Jónsson-Tarski [1951] the notion of a Boolean algebra with operators. A Boolean algebra with operators, or a BAO for short, is an algebra

𝔄 = ⟨A , + , − , f_{i}⟩_{i∈I}

such that ⟨A , + , −⟩ is a Boolean algebra and, for each i ∈ I, the extra-Boolean operation f_{i} is additive in every coordinate, i.e., if f_{i} has rank n > 0, then

f_{i}(x_{0}, …, x_{j} + y_{j}, …, x_{n−1}) = f_{i}(x_{0}, …, x_{j}, …, x_{n−1}) + f_{i}(x_{0}, …, y_{j}, …, x_{n−1})

for each j < n and each sequence x_{0}, …, x_{n−1}, y_{j} of elements from 𝔄. The algebra 𝔄 is normal if every extra-Boolean operation f_{i} is normal in each argument, i.e., if f_{i} has rank n > 0, then

f_{i}(x_{0}, …, x_{j}, …, x_{n−1}) = 0

whenever x_{j} = 0 for some j < n. 𝔄 is completely additive if each of its extra-Boolean operations f_{i} (of positive rank n) is completely additive in every coordinate, i.e., for each j < n, each sequence of elements x_{0}, …, x_{j−1}, x_{j+1}, …, x_{n−1} in A, and each set X ⊆ A such that ∑X exists, the sum

∑{f_{i}(x_{0}, …, x_{j−1}, y, x_{j+1}, …, x_{n−1}) : y ∈ X}

exists and

f_{i}(x_{0}, …, x_{j−1}, ∑X, x_{j+1}, …, x_{n−1}) = ∑{f_{i}(x_{0}, …, x_{j−1}, y, x_{j+1}, …, x_{n−1}) : y ∈ X} .

𝔄 is atomic if its Boolean reduct is atomic, and complete if it is completely additive and its Boolean reduct is complete. Because they are additive, the operators f_{i} of a BAO are always monotone in the sense that

f_{i}(x_{0}, …, x_{n−1}) ≤ f_{i}(y_{0}, …, y_{n−1})

whenever x_{j} ≤ y_{j} for all j < n.

A term in the language of a BAO is said to be positive if the complementation symbol does not occur in it; however, we do allow the defined symbols ·, 0, and 1 to occur. An equation in this language is positive if the right-hand and left-hand terms are both positive.

Boolean algebras with operators play a fundamental role in algebraic logic. Indeed, most of the algebraic structures encountered in algebraic versions of logics are BAOs. Another fundamental notion in algebraic logic is that of a discriminator operation.

A ternary operation t on a set A is a ternary discriminator if, for all x, y, z in A,

t(x, y, z) = \begin{cases}z & if x = y, \\ x & if x ≠ y. \end{cases}

A unary operation c on A is a unary discriminator (with respect to elements 0 and 1 of A) if, for all x in A,

c(x) = \begin{cases}0 & if x = 0, \\ 1 & if x ≠ 0. \end{cases}

It is known that an algebra 𝔄 with a Boolean reduct ⟨A , + , − ⟩ has a termdefinable ternary discriminator iff it has a term-definable unary discriminator. Indeed, if t is a ternary discriminator, then

c(x) = −t(0, x, 1) for all x ∈ A (1)

defines a unary discriminator (here, 0 and 1 are the Boolean zero and unit), and we have

t(x, y, z) = x · c(x ⊕ y) + z · −c(x ⊕ y) for all x, y, z ∈ A (2)

(where · and ⊕ are the Boolean multiplication and symmetric difference operations). Conversely, if c is a unary discriminator, then (2) defines a ternary discriminator and (1) holds. (See Jipsen [1993], pp. 240–241.)

A variety V is a discriminator variety if there is a term that defines a ternary discriminator on the universe of each subdirectly irreducible algebra in V. It follows from the remarks of the previous paragraph that if V is, e.g., a variety of BAOs, then we can equivalently replace the word “ternary” by “unary” in the preceding definition.

It is a property of discriminator varieties that every subdirectly irreducible algebra is simple, and hence every algebra is a subdirect product of simple algebras. One consequence of this is that an equation or conditional equation holds in the variety iff it holds in all simple algebras of the variety.

We shall refer to a term that defines a ternary or unary discriminator in all subdirectly irreducible algebras of V as a ternary or unary discriminator term for V. McKenzie [1975] showed that the property of being a ternary discriminator term for V is expressible by a set of equations. Recently, Jipsen [1993], Theorem 3, showed that the property of being a unary discriminator term for a variety of normal Boolean algebras with operators is expressible by a simple set of equations. Corollary 2.2 below presents a variant of Jipsen’s theorem.

Lemma 2.1. Suppose that 𝔄 is a subdirectly irreducible, normal BAO and c a unary operation on A. Then the following conditions are equivalent.

(i) c defines a unary discriminator in 𝔄.

(ii) The following equations are identically satisfied in ⟨𝔄 , c ⟩: (α) x ≤ c(x) , (β) c(c(x)) ≤ c(x) , (γ) c(−c(x)) ≤ −c(x) , (δ) f(x_{0}, …, x_{n−1}) ≤ c(x_{i}) for every extra-Boolean operation f of

rank n > 0 and every i < n.

Proof: Let 𝔄 be a subdirectly irreducible, normal BAO. Suppose, first, that condition (i) holds. Because c(x) = 1 for every non-zero x in 𝔄, we readily check that equations (α)–(δ) all hold in 𝔄. (The assumption of normality is needed to verify equation (δ) in the case when x_{i} = 0.)

Now suppose that condition (ii) holds. For a given extra-Boolean operation f of 𝔄 of rank n > 0 and a given i < n, define a unary operation g_{i} on A by stipulating that

g_{i}(x) = f(1, …, 1, x, 1, …, 1) for all x ∈ A,

where x occurs as the i^{th} argument of f. Then

g_{i}(c(x)) ≤ c(x) for all x ∈ A, (1)

since

g_{i}(c(x)) ≤ c(c(x)) ≤ c(x)

by (β) and (δ). Also,

g_{i}(−c(x)) ≤ −c(x) for all x ∈ A. (2)

Indeed,

g_{i}(−c(x)) ≤ c(−c(x)) ≤ −c(x)

by (δ) (with “−c(x)” in place of “x_{i}”), the definition of g_{i}, and (γ).

c(0) = 0 . (3)

To prove (3) notice, first of all, that c(1) = 1 by condition (α); using this and (γ), we get

c(0) = c(−1) = c(−c(1)) ≤ −c(1) = −1 = 0 .

Jipsen, ibid., shows that for a subdirectly irreducible algebra 𝔄, condition (i) is equivalent to the validity of equations (3), (ii)(α), and each instance of (1) and (2) (i.e., each instance arising from an extra Boolean operation f and an i < n). Since (α)–(δ) imply the validity of each instance of (1) and (2), this shows that (ii) implies (i).

Using the fact that an equation holds in a variety iff it holds in all subdirectly irreducible algebras in the variety, we immediately draw the following conclusion from the preceding lemma.

Corollary 2.2. Let V be a variety of normal BAOs and c a term with one free variable (in the language of V). Then c is a unary discriminator term for V iff equations (α)–(δ) of 2.1 hold in V.

When a BAO has a unary discriminator, it is obviously unique, by the very form of its definition. Therefore, any term c such that equations (α)–(δ) hold in V must be unique up to term equivalence. Indeed, let c′ be any other term for which these equations hold in V. Since both c and c′ define unary discriminators in the subdirectly irreducibles, the equation c(x) = c′(x) is identically satisfied in all subdirectly irreducibles of V, and hence in V itself. We may therefore refer to c as the unary discriminator term for V. In what follows we shall always denote this term (or the corresponding operation in an algebra of V) by c.

Corollary 2.3. Let V be a variety of normal BAOs and c a term such that equations (α)–(δ) of Lemma 2.1 are valid in V. Then the following equations and conditional equations are also valid in V.

(i) c(x) = 0 iff x = 0.

(ii) If x ≤ y, then c(x) ≤ c(y).

(iii) c(c(x)) = c(x).

(iv) c(−c(x)) = −c(x).

(v) c(x · c(y)) = c(x) · c(y).

(vi) c(x + y) = c(x) + c(y).

(vii) x · c(y) = 0 iff y · c(x) = 0.

Proof: The implication from right to left in (i) is demonstrated in (3) of the proof of Lemma 2.1, and the reverse implication follows from equation (α). For (ii)–(vi), it suffices to check that they hold in all subdirectly irreducible algebras in V. As an example, we verify (v). Let 𝔄 be a subdirectly irreducible algebra in V and suppose that x, y ∈ A. If y = 0, then by (i) we have

(1)  c(x · c(y)) = c(x · 0) = 0

and

(2)  c(x) · c(y) = c(x) · 0 = 0 .

If y ≠ 0, then using the fact that c must be a unary discriminator, we get

(3)  c(x · c(y)) = c(x · 1) = c(x)

and

(4)  c(x) · c(y) = c(x) · 1 = c(x) .

We leave the verification of (ii)–(iv) and (vi) to the reader. Part (vii) follows from (i) and (v):

x · c(y) = 0 iff c(x · c(y)) = 0  by (i),
iff c(x) · c(y) = 0  by (v),
iff c(c(x) · y) = 0  by (v),
iff c(x) · y = 0  by (i).

An operation c on a set A satisfying conditions 2.1(ii)(α) and 2.3(ii),(iii) is called a closure operation. If, in addition, 2.3(iv) holds, then c is said to be complemented. Thus, we can reformulate Corollary 2.2 as follows:

A variety V of normal BAOs is a discriminator variety iff there is a term-definable complemented closure operation c satisfying 2.1(ii)(δ).

Just as in the case of rings and of Boolean algebras, there is the notion of an ideal of a Boolean algebra with operators 𝔄. A subset I of the universe of 𝔄 is an ideal if there is a congruence relation Θ on 𝔄 such that I is the kernel of Θ, i.e., I is the equivalence class of 0 under Θ. Ideals in the theory of BAOs function just as they do in the theory of rings. For example, we can form the quotient structure 𝔄/I of 𝔄 modulo the ideal I and there is a canonical homomorphism of 𝔄 onto 𝔄/I given by the mapping x ⟼ x/I. If g is a homomorphism of 𝔄 onto 𝔅, then the kernel of g (i.e., the set of elements mapped to 0) forms an ideal I, and the corresponding quotient algebra 𝔄/I is canonically isomorphic to 𝔅 via the mapping x/I ⟼ g(x).

Notice that an ideal must be closed under every term-definable operation (of non-zero rank) that is normal. In fact, suppose that I is an ideal of 𝔄, say it is the kernel of the congruence Θ. Let f be any term-definable normal operation of 𝔄, say of rank n > 0, and let x_{0}, …, x_{n−1} be any elements of A. If, for some fixed i < n, the element x_{i} is in I, then ⟨0, x_{i}⟩ and ⟨x_{j}, x_{j}⟩ for j < n with j ≠ i are all in Θ. Therefore,

⟨f(x_{0}, …, x_{i−1}, 0, x_{i+1}, …, x_{n−1}), f(x_{0}, …, x_{i−1}, x_{i}, x_{i+1}, …, x_{n−1})⟩

is in Θ, since f is term-definable. Because f is normal,

f(x_{0}, …, x_{i−1}, 0, x_{i+1}, …, x_{n−1}) = 0 .

Therefore, ⟨0, f(x_{0}, …, x_{n−1})⟩ is in Θ, so f(x_{0}, …, x_{n−1}) is in I.

The following intrinsic characterization of ideals of Boolean algebras with normal operators is a special case of a result due to Ildikó Sain. (See Sain [1982], Proposition 7.4, for a formulation and proof of the key case when all the extra-Boolean operators are unary.)

Lemma 2.4. A subset I of the universe of a Boolean algebra with normal operators 𝔄 is an ideal iff the following conditions are satisfied :

(i) 0 ∈ I;

(ii) If x, y ∈ I, then x + y ∈ I;

(iii) If x ∈ I and y ≤ x, then y ∈ I; (iv) For each extra-Boolean operation f of rank n > 0 and each sequence

x_{0}, …, x_{n−1} of elements from A, if x_{i} ∈ I for some i, then f(x_{0}, …, x_{n−1}) is in I.

To prove the principal lemma of the present section we shall need to derive a few easy facts about ideals of algebras in a discriminator variety of normal BAOs. These facts are well known for finite-dimensional cylindric algebras (see Henkin-Monk-Tarski [1971], Theorems 2.3.8–2.3.10 and 2.3.18), and the cylindric algebraic proofs essentially carry over to the present case.

Given a subset X of the universe of 𝔄, the ideal generated by X is defined to be the intersection of all the ideals that include X.

Lemma 2.5. Let V be a discriminator variety of normal BAOs and 𝔄 ∈ V. (i) For any X ⊆ A, the ideal generated by X is the set

{x ∈ A : x ≤ ∑{c(y) : y ∈ Y } for some finite Y ⊆ X} .

(ii) For any ideal J and any z ∈ A, the ideal generated by J ∪ {z} is the set

{x ∈ A : x ≤ y + c(z) for some y ∈ J} .

Proof: We begin with the following observation:

(1) If J is an ideal and Y a finite subset of J, then ∑{c(w) : w ∈ Y } is in J.

Indeed, since the operation c is term-definable, and normal by 2.3(i), J is closed under it (see the remarks preceding 2.4). Because J is also closed under finite sums, by 2.4(ii), we get (1).

Let I be the set displayed in (i).

(2) I is an ideal.

To prove (2) we use Sain’s characterization. Since

0 = ∑{c(x) : x ∈ ∅} ,

the element 0 is in I. It is equally easy to verify conditions 2.4(ii),(iii). Therefore, we turn our attention to verifying 2.4(iv). Let f be an extra-Boolean operation of 𝔄, say of rank n > 0, and let x_{0}, …, x_{n−1} be elements of A. Suppose, for a fixed i < n, that x_{i} ∈ I. By definition of I there is a finite set Y ⊆ X such that

x_{i} ≤ ∑{c(y) : y ∈ Y }.

Then

f(x_{0}, …, x_{n−1}) ≤ c(x_{i})  by 2.2,
≤ c(∑{c(y) : y ∈ Y })  by 2.3(ii),
≤ ∑{cc(y) : y ∈ Y }  by 2.3(vi),
≤ ∑{c(y) : y ∈ Y }  by 2.3(iii).

Thus, f(x_{0}, …, x_{n−1}) is in I by definition of I, which proves (2).

To prove (i), let J be any ideal including X. Then I ⊆ J by (1) and 2.4(iii), so I is the smallest ideal including X.

Part (ii) follows from (i) (with J ∪ {z} in place of X), since by (1) each sum of the form ∑{c(w) : w ∈ Y }, with Y ⊆ J, may be replaced by a single element of J.

An ideal of 𝔄 is said to be trivial if 0 is its only element, proper if it is different from A, and maximal if it is proper and there are no other proper ideals that include it. As in the case of rings, the quotient algebra 𝔄/I of a BAO 𝔄 is simple iff I is maximal.

Lemma 2.6. Let V be a discriminator variety of normal BAOs and 𝔄 ∈ V. Then an ideal I of 𝔄 is :

(i) improper iff, for some (or every) z, both z and −c(z) are in I; (ii) maximal iff, for every z, exactly one of z and −c(z) is in I; (iii) maximal or improper iff, for every z, at least one of z and −c(z) is in I.

Proof: We begin the implication from left to right in (i). If I is improper, then certainly z and −c(z) are in I for some (and in fact every) z. For the reverse implication, suppose that z and −c(z) are in I. Then c(z) is in I (since c is normal and I is closed under term-definable, normal, unary operations). Therefore, the element c(z) + −c(z), i.e., 1, is in I, so I = A.

To establish the implication from left to right in (ii), assume that I is maximal and that z ∉ I. Set

J = {x ∈ A : x ≤ y + −c(z) for some y ∈ I} .

Then J is an ideal by Lemma 2.5(ii) and Corollary 2.3(iv), and it certainly includes I and contains −c(z). To see that J is proper, observe that z ∉ J. Indeed, z · −c(z) = 0 since z ≤ c(z). Hence, if we had z ∈ J, the inequality z ≤ y + −c(z) would force z ≤ y for some y ∈ I. But then we would have z ∈ I, a contradiction. Because J is a proper ideal including I, and I is maximal, we conclude that J = I and therefore that −c(z) ∈ I, as desired. We cannot have both z and −c(z) in I by part (i).

To prove the reverse implication, let I be an ideal that contains exactly one of z, −c(z) for every z ∈ A. Suppose that J is an ideal that properly includes I, say z is in J but not in I. Then −c(z) is in I—and hence also in J—by assumption. Therefore, J = A by (i).

Part (iii) is an immediate consequence of (i) and (ii).

We remark in passing that the preceding lemma remains true if we replace “z and −c(z)” by “c(z) and −c(z)” in the statement.

Recall from Sikorski [1964], p. 37, that a subset X of a Boolean algebra 𝔅 is dense in 𝔅 if for every non-zero y in B there is a non-zero x in X such that x ≤ y. This definition can be carried over without change to an arbitrary BAO 𝔄. It is well-known and easy to check that if X is dense in 𝔅, then every element of 𝔅 is the sum of the elements of X that are below it.

We shall be concerned with the special case of the notion of density when X is a definable subset of 𝔄. In what follows φ will be a formula in some language (not necessarily first-order) appropriate for the algebra 𝔄. It is assumed to have a single free variable that ranges over individuals. Therefore, φ defines a subset φ^{𝔄} of the universe of 𝔄.

Definition 2.7. (Density) A BAO 𝔄 is said to be φ-dense if, for every non-zero y in A, there is a non-zero x in φ^{𝔄} that is below y.

For a classic example, suppose that φ defines the notion of an atom. Then to say that an algebra is φ-dense just means that the algebra is atomic.

The reader may notice that the notion of φ-density actually makes sense for any algebraic structure with a partial ordering defined on its universe. Also, observe that if 𝔄 is φ-dense, then each element is the sum of the elements in φ^{𝔄} that are below it.

A problem with notions of density is that they are not necessarily preserved under homomorphisms. (See, for instance, Example 5.23.) Therefore, we cannot automatically conclude that every φ-dense algebra is a subdirect product of simple φ-dense algebras. The next lemma and its consequences, Corollary 2.10 and Theorem 2.11, are the principal tools that we shall use to overcome this difficulty (thereby avoiding the hypothesis of simplicity in some of our representation theorems). For example, in 2.11 we prove that, under suitable conditions on φ, if all the simple φ-dense algebras of a variety L are in a subvariety K, then all the φ-dense algebras of L are in K.

Lemma 2.8. Let V be a discriminator variety of normal BAOs and 𝔄 a countable algebra in V. Suppose φ is a formula that is preserved under homomorphisms on 𝔄. If 𝔄 is φ-dense, then for each non-zero x in A there is a maximal ideal I excluding x such that 𝔄/I is φ-dense.

Proof: Fix a non-zero x in A, and let ⟨y_{n} : n ∈ ω⟩ be an enumeration of the elements of A such that x = y_{0} (here we use the assumption of countability). We easily construct by induction on n a sequence ⟨z_{n} : n ∈ ω⟩ of non-zero elements below x that are in φ^{𝔄} and have the following properties:

z_{0} ≤ y_{0} (1)

and either

y_{n} · c(z_{n}) = 0 and z_{n+1} = z_{n} (2)

or else

y_{n} · c(z_{n}) ≠ 0 and z_{n+1} ≤ y_{n} · c(z_{n}) . (3)

Indeed, since x ≠ 0, we can apply the assumption of φ-density to obtain a nonzero z_{0} in φ^{𝔄} that is below x = y_{0}. This verifies (1). Now suppose that z_{n} has been defined. If y_{n} · c(z_{n}) = 0, we set z_{n+1} = z_{n} as desired in (2). Suppose that y_{n} · c(z_{n}) ≠ 0. Then by φ-density there is a non-zero z_{n+1} in φ^{𝔄} that is below y_{n} · c(z_{n}), as called for in (3).

An easy argument by induction on integers, using the properties of a closure operation, shows that

(4) 0 < c(z_{m}) ≤ c(z_{n}) whenever n ≤ m .

Also,

(5) y_{0} · c(z_{n}) ≠ 0 for every n ∈ ω.

To prove (5) observe that

0 < c(z_{n}) ≤ c(z_{0}) ≤ c(y_{0}) . (6)

by (4) and (1). Therefore

c(y_{0} · c(z_{n})) = c(y_{0}) · c(z_{n}) by 2.3(v),
= c(z_{n})  by (6),
≠ 0  by (6).

Applying Corollary 2.3(i), we conclude that y_{0} · c(z_{n}) ≠ 0.

Let I be the ideal generated by the set {−c(z_{n}) : n ∈ ω}. By Lemma 2.5(i) and Corollary 2.3(iv)

(7) I = {u ∈ A : u ≤ ∑{−c(z_{n}) : n ∈ Y } for some finite Y ⊆ ω} .

It is easy to check that, in fact,

I = {u ∈ A : u ≤ −c(z_{n}) for some n ∈ ω} . (8)

Indeed, the inclusion from right to left follows trivially from (7). For the reverse inclusion, suppose that Y is a finite subset of ω and that u ≤ ∑{−c(z_{n}) : n ∈ Y }. Set m = max(Y). Then c(z_{m}) ≤ c(z_{n}) for each n ∈ Y, by (4), so

u ≤ ∑{−c(z_{n}) : n ∈ Y } = −∏{c(z_{n}) : n ∈ Y } = −c(z_{m}) .

This proves (8).

From (5), (8), and x = y_{0} we immediately see that

x ∉ I . (9)

Before proceeding to the next step, we make some simple observations. Let v be an element of A that is not in I. By (8) we have

(10) v · c(z_{n}) ≠ 0 for every n ∈ ω .

Now ⟨y_{n} : n ∈ ω⟩ is an enumeration of A, so for some k ∈ ω we have v = y_{k}. Thus, y_{k} · c(z_{k}) ≠ 0, by (10). We conclude from (3) that

0 < z_{k+1} ≤ y_{k} · c(z_{k}) . (11)

We now show that

(12) I is maximal.

I is proper, by (9). Therefore, by Lemma 2.6(iii) it suffices to fix an arbitrary element v of A that is not in I and to show that −c(v) must be in I. Let k be as above, i.e., v = y_{k}. Using (11) and Corollary 2.3(ii) we have

c(z_{k+1}) ≤ c(y_{k} · c(z_{k})) ≤ c(y_{k}) = c(v) .

It follows that −c(v) ≤ −c(z_{k+1}), so −c(v) is in I by (8). This completes the proof of (12).

It remains to show that the quotient algebra 𝔄/I is φ-dense. We fix an arbitrary element v of A that is not in I (thus, v/I is an arbitrary non-zero element of 𝔄/I). Again, let k be such that v = y_{k}. Then (11) holds, and z_{k+1} is in φ^{𝔄} by choice of z_{k+1}. It follows from (11) that z_{k+1}/I is below v/I (= y_{k}/I), and it is in φ^{𝔄/I} because φ is preserved under homomorphisms. (This is the unique place where we use the assumption that φ is preserved under homomorphisms.) Clearly, −c(z_{k+1}) is in I by (8), and I is proper by (9). Therefore, z_{k+1} is not in I, by Lemma 2.6(i). Thus, z_{k+1}/I is a non-zero element of 𝔄/I. The proof of the lemma is completed.

Remark 2.9. The idea behind the proof of the preceding lemma is the following. We wish to construct a maximal ideal I so that 𝔄/I is φ-dense. To achieve this we deal with the elements of 𝔄 one at a time. At stage n, if y_{n} has already been forced into the ideal (the condition y_{n} · c(z_{n}) = 0 just means that y_{n} ≤ −c(z_{n}), so that y_{n} must be put into I), then we do not have to do anything: y_{n}/I will be zero in the quotient algebra. If y_{n} has not yet been forced into the ideal, then we force it to be non-zero, and at the same time maintain φ-density, in the quotient algebra by choosing a non-zero witness z_{n+1} in φ^{𝔄} below y_{n} and putting −c(z_{n+1}) into I to ensure that z_{n+1}/I is non-zero. The condition z_{n+1} ≤ c(z_{n}) ensures the consistency of I, so that it does not become improper.

Corollary 2.10. Let V be a discriminator variety of normal BAOs and 𝔄 a countable algebra in V. Suppose φ is a formula that is preserved under homomorphisms on 𝔄. If 𝔄 is φ-dense, then it is isomorphic to a subdirect product of simple φ-dense algebras.

Proof: For each non-zero element x in A, let I_{x} be a maximal ideal of 𝔄 that excludes x and such that 𝔄/I_{x} is φ-dense; such an ideal exists by the previous lemma. Since I_{x} is maximal, the quotient 𝔄/I_{x} is simple. Let g be the canonical homomorphism of 𝔄 into the product 𝔅 of the algebras 𝔄/I_{x} with 0 < x ∈ A. Thus, g is defined by the stipulation

g(y) = ⟨y/I_{x} : 0 < x ∈ A⟩

for each y in A. For each non-zero y in A, the composition of the y^{th} projection function (from the product 𝔅 to the factor 𝔄/I_{y}) with g maps 𝔄 onto 𝔄/I_{y}. It remains to check that g is one-one, and for this it suffices to check that the kernel of g is {0}. Suppose y ≠ 0. Then y ∉ I_{y} by Lemma 2.8, and therefore y/I_{y} is non-zero. Since this is one of the coordinates of g(y), we conclude that the latter is non-zero.

Theorem 2.11. Let L be a discriminator variety of normal Boolean algebras with operators, K a subvariety of L, and φ an elementary, positive formula. If every simple φ-dense algebra of L is in K, then every φ-dense algebra of L is in K.

Proof: Let 𝔄 be any φ-dense algebra of L. We first treat the case when 𝔄 is countable. In this case, since φ is positive and hence preserved under homomorphisms, we can apply the previous corollary to represent 𝔄 as a subdirect product of simple φ-dense algebras. Each of the latter is in L—since L is a variety—and therefore in K, by assumption. Since K is a variety, we conclude that 𝔄 is also in K.

Now suppose that 𝔄 is uncountable. Since φ is an elementary formula, we see that φ-density is an elementary property and hence is preserved under formation of elementary subalgebras. In particular, every countable elementary subalgebra of 𝔄 is φ-dense. We can now apply the first case to conclude that every countable elementary subalgebra of 𝔄 is in K. But it is a well-known, easy consequence of the Downward Löwenheim-Skolem-Tarski Theorem (see, e.g., Chang-Keisler [1973], Theorem 3.1.6) that every algebra is the directed union of its countable, elementary subalgebras. Thus, 𝔄 is the directed union of algebras in K. It follows that 𝔄 is in K, since K is a variety.

We discuss briefly some extensions of Theorem 2.11. First of all, we do not fully use the hypotheses that L and K are varieties. Our proof still goes through if we assume only that L is closed under homomorphic images and elementary substructures (and generates a discriminator variety), and that K is closed under subalgebras, direct products, and directed unions.

The second extension concerns the assumption that the formula φ is elementary. We only use this assumption in applying the Downward Löwenheim-Skolem-Tarski Theorem. Now the latter theorem is known to hold in more general settings. For example, it holds in countable fragments of the infinitary language ℒ_{ω_{1}ω} (in which countably infinite conjunctions and disjunctions are allowed). Thus, Theorem 2.11 actually holds when φ is, e.g., a positive formula of ℒ_{ω_{1}ω}.

We can also replace the single formula φ by a countable collection Φ of, e.g., firstorder formulas. However, this extension is essentially included in the case when φ is a formula of ℒ_{ω_{1}ω}.

Another extension concerns a weakening of the notion of φ-density. Let φ and ψ be formulas in some language (not necessarily first-order) appropriate for a BAO 𝔄. As before, φ and ψ are assumed to have a single free variable ranging over individuals.

Definition 2.12. 𝔄 is φ-dense in ψ if, for every non-zero y in ψ^{𝔄}, there is a nonzero x in φ^{𝔄} that is below y.

We get the notion of φ-density by taking ψ to be the formula x = x. However, we shall encounter other interesting examples where ψ does not define the entire universe. Clearly, φ-density implies φ-density in ψ for any formula ψ. The converse fails in general, even when ψ satisfies conditions (i)–(iii) of the next lemma.^{1} Lemma 2.13. Let V be a discriminator variety of normal BAOs and 𝔄 a countable algebra in V. Suppose φ is a formula that is preserved under homomorphisms on 𝔄 and suppose ψ is a formula with the following properties :

1For example, in the language of relation algebras (see Section 6), let ψ be the formula x ≤ 1’ expressing the property of being below the identity element 1’, and let φ be the formula x;1;x ≤ 1’ expressing the property of being either 0 or a singleton below the identity. It is easy to check that ψ satisfies conditons (i)–(iii) of Theorem 2.15. Full set relation algebras over sets of cardinality at least 2 are φ-dense in ψ. However, they are certainly not φ-dense, since not every non-zero

(i) ψ is strictly preserved under homomorphisms on 𝔄; (ii) If y is in ψ^{𝔄}, then for each non-zero x in A the element y · c(x) is in ψ^{𝔄}; (iii) For each non-zero x in A there is a y in ψ^{𝔄} such that c(x) = c(y).

If 𝔄 is φ-dense in ψ, then for each non-zero x in A there is a maximal ideal I excluding x such that 𝔄/I is φ-dense in ψ.

Proof: We proceed as in the proof of Lemma 2.8, and we continue its numeration scheme. Fix a non-zero x in A, and let ⟨y_{n} : n ∈ ω⟩ be an enumeration of the elements of ψ^{𝔄} such that c(x) = c(y_{0}). Such an enumeration is possible because 𝔄 is countable and because ψ satisfies condition (iii). We construct a sequence ⟨z_{n} : n ∈ ω⟩ of non-zero elements in φ^{𝔄} that are below x and that satisfy properties (1)–(3). Indeed, since x ≠ 0 and c(x) = c(y_{0}), we have c(y_{0}) ≠ 0 and hence y_{0} ≠ 0. Using the assumption of φ-density in ψ we obtain a non-zero z_{0} in φ^{𝔄} that is below y_{0} . Now suppose that z_{n} has been defined. If y_{n} · c(z_{n}) = 0, we set z_{n+1} = z_{n}. If y_{n} · c(z_{n}) ≠ 0, then y_{n} · c(z_{n}) is a non-zero element of ψ^{𝔄} by condition (ii). Hence, by φ-density in ψ there is a non-zero z_{n+1} in φ^{𝔄} that is below y_{n} · c(z_{n}).

The proofs of (4)–(8) are exactly as before. To proceed, suppose that v is a non-zero element of A. By condition (iii) there is a k ∈ ω such that c(v) = c(y_{k}) . Using 2.3(vii) we see that

v · c(z_{n}) ≠ 0 iff z_{n} · c(v) ≠ 0 iff z_{n} · c(y_{k}) ≠ 0 iff y_{k} · c(z_{n}) ≠ 0 .

Thus,

v · c(z_{n}) ≠ 0 iff y_{k} · c(z_{n}) ≠ 0 . (13)

Taking v = x and k = 0 in (13) we obtain (9) from (5) and (8). The proofs of (11) and (12) are as before except that we choose k so that c(v) = c(y_{k}) and we use (13) and (10) to obtain y_{k} · c(z_{k}) ≠ 0 .

It remains to show that 𝔄/I is φ-dense in ψ. Let w/I be a non-zero element of ψ^{𝔄/I}. Since ψ satisfies condition (i) (see the last paragraph of the preliminaries for the relevant definition), there is a v in ψ^{𝔄} such that v/I = w/I. In particular, v/I ≠ 0 and therefore v ∉ I. Choose a k such that v = y_{k}; this is possible because ⟨y_{n} : n ∈ ω⟩ enumerates ψ^{𝔄}. The remainder of the proof is as in 2.8.

Corollary 2.14. Under the hypotheses of 2.13, if 𝔄 is φ-dense in ψ, then 𝔄 is isomorphic to a subdirect product of simple algebras that are φ-dense in ψ.

The proof is identical to the proof of Corollary 2.10.

Theorem 2.15. Let L be a discriminator variety of normal Boolean algebras with operators, K a subvariety of L, φ an elementary, positive formula , ψ an elementary formula , and L_{φψ} the class of algebras of L that are φ-dense in ψ. Suppose that ψ satisfies the following conditions :

(i) ψ is strictly preserved under homomorphisms, (ii) ∀x∀y[ ψ(y) → ψ(y · c(x)) ] holds in all algebras of L_{φψ}, (iii) ∀x∃y[ ψ(y) ∧ (c(x) = c(y)) ] holds in all algebras of L_{φψ}.

element is above a non-zero element below the identity.

If every simple algebra of L_{φψ} is in K, then every algebra of L_{φψ} is in K.

The proof is nearly identical to the proof of Theorem 2.11. We leave the details to the reader.

In general, in a product of Boolean algebras with operators, a sequence of atoms and zeros is no longer an atom. Still, such a sequence possesses many of the important properties of an atom. The definition of a quasi-atom is intended to capture these properties.

Definition 2.16. Suppose that 𝔄 is in a discriminator variety of normal BAOs.

(i) An element x is a quasi-atom if for every y ≤ x we have y = x · c(y). (ii) 𝔄 is quasi-atomic if every non-zero element is above a non-zero quasi-atom.

Notice that quasi-atomicity is a notion of density. The following lemma is an easy consequence of the definition, so we leave the proof to the reader.

Lemma 2.17. Suppose that 𝔄 is in a discriminator variety of normal BAOs.

(i) An element x is a quasi-atom iff x · y = x · c(x · y) for all y.

(ii) If 𝔄 is simple , then x is a quasi-atom iff x = 0 or x is an atom. Therefore simple, quasi-atomic algebras are atomic.

The next corollary shows that, in the case of countable algebras, the intuition behind the definition of a quasi-atom corresponds to the actual situation.

Corollary 2.18. Let V be a discriminator variety of normal BAOs and 𝔄 a countable quasi-atomic algebra in V. Then 𝔄 is isomorphic to a subdirect product of simple, atomic algebras. Moreover, the isomorphism takes each quasi-atom of 𝔄 to a sequence in the product consisting of zeros and atoms.

Proof: Let φ be the formula

∀y[x · y = x · c(x · y)] .

By part (i) of the preceding lemma, quasi-atomicity is the same thing as φ-density. Therefore, the first assertion of the corollary follows at once from Corollary 2.10 and part (ii) of the preceding lemma. Let f be an embedding of 𝔄 into a direct product 𝔅 = ∏_{ξ<Ξ}𝔅_{ξ} of simple, atomic algebras 𝔅_{ξ} such that p_{ξ} ^{∘}f maps 𝔄 onto 𝔅_{ξ} (where p_{ξ} is the projection function from 𝔅 to 𝔅_{ξ}). Suppose that x is a quasiatom in 𝔄. Since φ is preserved under “onto” homomorphisms, the coordinate p_{ξ} ^{∘}f(x) of the sequence f(x) must be a quasi-atom and therefore either 0 or an atom by 2.17(ii).

Problem 2.19. Can the hypothesis of countability be removed from Lemma 2.8 or at least from Corollaries 2.10 and 2.18?

Just as with φ-density, one can specialize the notion of a quasi-atom. Let ψ be a formula with one free variable. An element x of 𝔄 is a quasi-atom in ψ^{𝔄} provided that x ∈ ψ^{𝔄} and for every y ∈ ψ^{𝔄}, if y ≤ x, then y = x · c(y). We shall sometimes use this notion to simplify the statement of certain lemmas.

The next two examples are intended to illustrate the notion of quasi-atomicity. They show, in particular, that a quasi-atomic algebra need not have any atoms.

Example 2.20. Consider a variety V of normal BAOs in which each extra-Boolean operation f is (uniformly) definable by a term τ_{f} that involves only the Boolean operations; in other words, V is a term definitional extension of BA. The two element Boolean algebra 𝔄, expanded by the extra-Boolean operations τ_{f}^{𝔄}, is the unique subdirectly irreducible algebra in V. Since the extra Boolean operations are assumed to be normal, it is easy to check that the identity function is a unary discriminator in 𝔄. Thus, the term c(x) given by c(x) = x is a unary discriminator for V.

Let 𝔅 be any algebra of V. From the definition of c we see that an element x in 𝔅 is a quasi-atom iff

x · y = x · (x · y)

for all y ∈ B. But every element x satisfies this formula. Thus, every element of 𝔅 is a quasi-atom. It follows that all algebras in V, including atomless algebras, are quasi-atomic.

Examples of such varieties include the variety of discrete cylindric algebras of a specified dimension and the variety of Boolean relation algebras.

Example 2.21. For each n, k ∈ ω with k < 2^{n} let N_{n,k} be the set of natural numbers that are congruent to k modulo 2^{n}. For example,

N_{1,0} = {2m : m ∈ ω}  ,  N_{1,1} = {2m + 1 : m ∈ ω} ,

and

N_{2,0} = {4m : m ∈ ω}  ,  N_{2,1} = {4m + 1 : m ∈ ω} ,
N_{2,2} = {4m + 2 : m ∈ ω}  ,  N_{2,3} = {4m + 3 : m ∈ ω} .

For each n the sets N_{n,k} with k < 2^{n} form a partition of ω into 2^{n} many infinite sets. Moreover, N_{n+1,k} and N_{n+1,2^{n}+k} partition N_{n,k} into two infinite sets.

Fix a normal BAO ℭ with a unary discriminator. Notice that the quasi-atoms of ^{ω}ℭ (the ω^{th} direct power of ℭ) are just the functions f from ω to C such that each value of f is either an atom of ℭ or 0. We construct a subalgebra 𝔄 of ^{ω}ℭ as follows. For each n ∈ ω, define B_{n} to be the set of functions f in ^{ω}ℭ such that f is constant on N_{n,k} for each k < 2^{n}. For example, B_{0} consists of the functions from ω to C that are constant, i.e., that assume just one value, and B_{1} consists of the functions from ω to C that assume at most two values, one on the even numbers and one on the odd numbers. It is easy to check that B_{n} is a subuniverse of ^{ω}ℭ and that the mapping f ⟼ f ↾ 2^{n} (the restriction of f to 2^{n}) is an isomorphism from the corresponding subalgebra 𝔅_{n} to ^{2^{n}}ℭ. Thus, the atoms of 𝔅_{n} are the functions f such that, for some k < 2^{n}, the value of f on N_{n,k} is an atom and its value off of N_{n,k} is 0. In particular, each such atom is a non-zero quasi-atom of ^{ω}ℭ. Also, 𝔅_{n} is a subalgebra of 𝔅_{n+1} , and each non-zero element of 𝔅_{n} gets split into non-zero pieces in 𝔅_{n+1} . In fact, for each non-zero f in 𝔅_{n} define f_{0} and f_{1} in 𝔅_{n+1} by specifying their values on each set N_{n,k} as follows:

f_{0}(m) = \begin{cases}f(m) & for m ∈ N_{n+1,k}, \\ 0 & for m ∈ N_{n+1,2^{n}+k}, \end{cases}

and

f_{1}(m) = \begin{cases}0 & for m ∈ N_{n+1,k}, \\ f(m) & for m ∈ N_{n+1,2^{n}+k}. \end{cases}

Then f_{0} and f_{1} are non-zero, pairwise disjoint, and sum to f. Moreover, if f is a quasi-atom of ^{ω}ℭ, then the same is true of f_{0} and f_{1} .

Let 𝔄 be the union of the chain {𝔅_{n} : n ∈ ω}. Then 𝔄 is a subalgebra of ^{ω}ℭ that is atomless. In fact, as we have just seen, every non-zero element of 𝔄 gets split into two disjoint, non-zero elements.

Suppose that ℭ is atomic. Then each 𝔅_{n} is certainly atomic (because it is isomorphic to ^{2^{n}}ℭ). If g is any non-zero element of 𝔄, then g is in B_{n} for some n. Therefore, there is an atom of 𝔅_{n} that is below g. We have seen that such an atom is a non-zero quasi-atom of ^{ω}ℭ and hence also of 𝔄. Thus, in addition to being atomless, 𝔄 is a quasi-atomic algebra. (See Givant [1994], Example 7.11, for a related construction. Notice that if ℭ is a finite Boolean algebra, then 𝔄 is just a countable, atomless Boolean algebra.)

3. Rectangularly dense cylindric algebras

We now turn our attention to the representation theorem for rectangularly dense cylindric algebras. Throughout this and the following section we fix an ordinal α. We begin by recalling from Henkin-Monk-Tarski [1971] the definition of a cylindric algebra of dimension α.

Definition 3.1. A cylindric algebra of dimension α is an algebra

𝔄 = ⟨A , + , − , c_{i} , d_{ij}⟩_{i,j∈α}

such that ⟨A , + , −⟩ is a Boolean algebra, d_{ij} is a constant and c_{i} is a unary operation for each i, j ∈ α, and the following postulates are satisfied for all x, y ∈ A and all i, j, k ∈ α:

(C1) c_{i}(0) = 0 ,

(C2) x ≤ c_{i}(x) ,

(C3) c_{i}(x · c_{i}(y)) = c_{i}(x) · c_{i}(y) ,

(C4) c_{i}c_{j}(x) = c_{j}c_{i}(x) ,

(C5) d_{ii} = 1 ,

(C6) d_{jk} = c_{i}(d_{ji} · d_{ik}) whenever i ≠ j, k, (C7) c_{i}(d_{ij} · x) · c_{i}(d_{ij} · −x) = 0 whenever i ≠ j.

The class of all cylindric algebras of dimension α is denoted by CA_{α}. We also use the notation “CA_{α}” as an abbreviation for the phrase “cylindric algebra of dimension α”. The element d_{ij} is called the ij^{th} diagonal element, and the operation c_{i} is called the i^{th} cylindrification.

To give an example of a CA_{α}, let U be any set and define ℭ_{α}(U) to be the algebra

⟨Sb(^{α}U) , ∪ , ∼ , C_{i} , D_{ij}⟩_{i,j<α} ,

where Sb(^{α}U) is the collection of all subsets of ^{α}U, ∪ and ∼ are the set-theoretic operations of union and complementation with respect to ^{α}U, and for each X ⊆ ^{α}U and each i, j ∈ α we have

C_{i}(X) = {u ∈ ^{α}U : there is an x ∈ X with u_{k} = x_{k} for all k ∈ α ∼ {i}},
D_{ij} = {u ∈ ^{α}U : u_{i} = u_{j}} .

It is easy to check that ℭ_{α}(U) is a cylindric algebra. It is called the full cylindric set algebra over U of dimension α.

A CA_{α} is said to be representable if it can be embedded into a direct product of full cylindric set algebras of dimension α. The class of all such representable algebras is denoted by RCA_{α}. It is well known that RCA_{α} is a subvariety of CA_{α} (see Henkin-Monk-Tarski [1971], p. 171, and [1985], Corollary 3.1.108). For α = 0, 1 the two varieties coincide, i.e., every cylindric algebra of dimension 0 or 1 is representable (see Henkin-Monk-Tarski [1971], p. 171). However, for α ≥ 2 the two varieties are distinct, i.e., there are cylindric algebras in every dimension ≥ 2 that are not representable. In fact, for α > 2, RCA_{α} is not even finitely axiomatizable (and not even finitely schematizable when α ≥ ω) over CA_{α} (see Henkin-Monk-Tarski [1985], Theorems 4.1.3 and 4.1.7).^{2} Thus, the problem of finding simple criteria that imply the representability of a cylindric algebra becomes interesting and important.

Suppose that 𝔄 is a CA_{α} and that β < α. By the β-reduct of 𝔄 we mean the algebra

⟨A , + , − , c_{i} , d_{ij}⟩_{i,j∈β} .

It is easily seen to be a CA_{β} .

Let N_{β}(U) be the set of elements X in ℭ_{α}(U) such that for all x ∈ X and all y ∈ ^{α}U, if y agrees with x on β, then y ∈ X. Thus, X is in N_{β}(U) iff there is a set Z ⊆ ^{β}U such that X has the form

X = Z × \underbrace{U × U × U × …}_{α−β times} .

The set N_{β}(U) is easily seen to be a subuniverse of the β-reduct of ℭ_{α}(U). Let 𝔑_{β}(U) be the corresponding subalgebra. It is not difficult to verify the well-known fact that ℭ_{β}(U) is canonically isomorphic to 𝔑_{β}(U). From this it is a simple matter to check that every equation in the language of CA_{β} that holds in RCA_{α} must also hold in RCA_{β} . Indeed if ε is such an equation holding in RCA_{α}, then ε must hold in ℭ_{α}(U) for every set U. Since ℭ_{β}(U) is isomorphic to a subalgebra of the β-reduct of ℭ_{α}(U), we see that ε must hold in ℭ_{β}(U) for every set U. But every algebra in RCA_{β} is isomorphic to a subalgebra of a direct product of such full cylindric set algebras. Therefore ε must hold RCA_{β} . The converse is also true, but its proof is more involved; see Henkin-Monk-Tarski [1985], Theorem 3.1.126 or 3.1.127.

2These negative results were considerably strengthened in Andréka [a]. For example, no set of equations, whether finite or infinite, that involves only a finite number of variables can axiomatize RCA_{α}. For α < ω this remains true even if we add an arbitrary number of unary operators or generalized quantifiers of arbitrary rank.

In the sequel, we will use the following abbreviations. For a finite subset

Γ = {i_{0}, …, i_{n−1}}

of α with i_{0} < ⋯ < i_{n−1}, we write c_{(Γ)}(x) for c_{i_{0}} … c_{i_{n−1}}(x). We make the convention that c_{(∅)}(x) = x. For a finite dimension α we set

d = ∏{d_{ij} : i < j < α} .

The element d is called the main diagonal and an element below d is called a subdiagonal element. An element x is said to be closed under c_{(Γ)} , or c_{(Γ)}-closed, if c_{(Γ)}(x) = x.

In the next lemma we list some simple, easy, and well-known laws regarding cylindric algebras that we shall need. The derivations of these laws can be found in Henkin-Monk-Tarski [1971], Chapter 1, Sections 2–3.

Lemma 3.2. Let 𝔄 be a CA_{α} and x, y elements of 𝔄.

(i) c_{i}c_{i}(x) = c_{i}(x).

(ii) If x ≤ y, then c_{i}(x) ≤ c_{i}(y).

(iii) c_{i}(x + y) = c_{i}(x) + c_{i}(y).

(iv) c_{i}(−c_{i}(x)) = −c_{i}(x).

(v) c_{i}(x · y) = x · y whenever c_{i}(x) = x and c_{i}(y) = y.

(vi) c_{i}(d_{ij}) = 1.

(vii) c_{i}(d_{jk}) = d_{jk} when i ≠ j, k.

(viii) d_{ij} · d_{jk} = d_{ij} · d_{ik}.

(ix) d_{ij} · c_{i}(x) = 0 iff x = 0.

(x) d_{ij} · c_{i}(d_{ij} · x) = d_{ij} · x when i ≠ j.

(xi) x · c_{i}(y) = 0 iff y · c_{i}(x) = 0.

From postulates (C1), (C2), (C4), Lemma 3.2(iii),(iv), and Corollary 2.2 it is seen that CA_{α} is a variety of normal Boolean algebras with complemented closure operations c_{i}, and for finite α, the term c_{(α)} is a unary discriminator for CA_{α}. Thus, for finite α, CA_{α} is a discriminator variety of normal BAOs, the subdirectly irreducible algebras of CA_{α} are simple, and a conditional equation holds in CA_{α} iff it holds in all simple algebras of CA_{α}.

Certain generalizations of the postulates and of the laws in Lemma 3.2 are completely obvious. For example, for any finite Δ ⊆ α and any finite set J we have the following generalizations of (C3) and Lemma 3.2(v):

c_{(Δ)}(x · y) = c_{(Δ)}(x) · y whenever c_{i}(y) = y for each i ∈ Δ,
c_{(Δ)}(∏_{j∈J}y_{j}) = ∏_{i∈J}y_{j}  whenever c_{i}(y_{j}) = y_{j} for each i ∈ Δ and j ∈ J.

We shall use such generalizations without further explanation, referring only to the corresponding postulate or law. The three generalizations that we formulate in Lemma 3.3 below concern products of diagonal elements and are slightly more involved. The first generalizes 3.2(viii) and the second 3.2(x). The third combines and generalizes (C6) and 3.2(vi),(vii). The three generalizations are stated and proved in Henkin-Monk-Tarski [1971], Theorems 1.8.5, 1.8.12(iv), and 1.8.6 respectively.

Lemma 3.3. Let 𝔄 be a CA_{α} and Δ, Γ finite subsets of α.

(i) ∏_{i∈Γ}d_{ik} = ∏_{i,j∈Γ∪{k}}d_{ij} .

(ii) c_{(Δ)}(x) · ∏_{i∈Δ}d_{ik} = x whenever k ∈ α ∼ Δ and x ≤ ∏_{i∈Δ}d_{ik}.

(iii) c_{(Δ)}(∏_{i,j∈Γ}d_{ij}) = ∏_{i,j∈Γ∼Δ}d_{ij} .

Recall that d denotes the main diagonal of a finite-dimensional CA_{α}.

Lemma 3.4. Let α be finite and suppose that x is a non-zero element of a CA_{α}. Then d · c_{(α∼{i})}(x) ≠ 0.

Proof: By Lemma 3.3(iii) (with Γ = α and Δ = α ∼ {i}) and (C5) we have

c_{(α∼{i})}(d) = d_{ii} = 1 .

Therefore, x · c_{(α∼{i})}(d) ≠ 0. The desired conclusion follows from Lemma 3.2(xi).

Lemma 3.5. Suppose α is finite and 𝔄 a CA_{α}. Then for each sequence ⟨x_{i} : i ∈ α⟩ of elements of 𝔄 and each Δ ⊆ α we have

(i) c_{(Δ)}( ∏_{i∈α}c_{(α∼{i})}(x_{i})) = ∏_{i∈α∼Δ}c_{(α∼{i})}(x_{i}) · ∏_{i∈Δ}c_{(α)}(x_{i}) . If 𝔄 is simple and the elements x_{i} non-zero, then

(ii) c_{(Δ)}( ∏_{i∈α}c_{(α∼{i})}(x_{i})) = ∏_{i∈α∼Δ}c_{(α∼{i})}(x_{i}) .

Proof: The proof is by induction on the size of Δ. When Δ is empty, the equation holds trivially. Suppose now that the equation holds whenever the set has size n, and assume that Δ has n + 1 elements, say j is the smallest of these. For each i in α set

y_{i} = c_{(α∼{i})}(x_{i}) . (1)

Observe that

c_{j}(y_{i}) = y_{i} for j ≠ i (2)

by (1), (C4), and Lemma 3.2(i), and

c_{i}(y_{i}) = c_{(α)}(x_{i}) (3)

by (1). Therefore

c_{(Δ)}( ∏_{i∈α}y_{i}) = c_{j}c_{(Δ∼{j})}(∏_{i∈α}y_{i})  by convention,

= c_{j}[(∏_{i∈α∼(Δ∼{j})}y_{i}) · (∏_{i∈Δ∼{j}}c_{i}(y_{i}))] by the induction

hypothesis,

= c_{j}(y_{j}) · ∏_{i∈α∼Δ}y_{i} · ∏_{i∈Δ∼{j}}c_{i}(y_{i})  by (2) and (C3),
= ∏_{i∈α∼Δ}y_{i} · ∏_{i∈Δ}c_{i}(y_{i})  by BA.

In view of (1) and (3), this completes the proof of (i). Part (ii) follows at once from (i).

Notice, in the statement of the previous lemma, that when Δ = α, the right-hand side of the displayed equation in (ii) is just 1.

Definition 3.6. Let 𝔄 be a CA_{α}.

(i) An element a of 𝔄 is said to be rectangular or a rectangle if

c_{(Γ)}(a) · c_{(Δ)}(a) = c_{(Γ∩Δ)}(a)

for all finite subsets Γ and Δ of α. (ii) 𝔄 is rectangularly dense if below every non-zero element there is a non-zero

rectangle.

The notion of a rectangular element is from Henkin-Monk-Tarski [1971], Definition 1.10.6. In two-dimensional cylindric set algebras over a set U, rectangles are elements that have the form X ×Y for some subsets X, Y of U (see the next lemma and Figure 1). In the Cartesian plane U × U such elements have the appearance of rectangles in the ordinary sense of the word (provided that the elements of U are geometrically represented in a suitable way). More generally, for finite α, rectangles in an α-dimensional cylindric set algebra are elements of the form X_{0} × ⋯ × X_{α−1} for some subsets X_{0}, …, X_{α−1} of U. If X_{i} is a singleton for each i < α, say X_{i} = {x_{i}}, then the rectangle X_{0} × ⋯ × X_{α−1} is the singleton {(x_{0}, …, x_{α−1})}. Thus, every singleton is a rectangle. In particular, ℭ_{α}(U) is rectangularly dense, since every non-zero set is above a singleton. When α = 0, 1 each element in a CA_{α} is trivially a rectangle; therefore, all cylindric algebras of dimension 0 or 1 are rectangularly dense.

Figure 1. A rectangle X × Y.

Observe that, for finite α, the notion of rectangularity is definable by a finite conjunction of equations. Therefore, it is an elementary notion that is preserved under homomorphisms. Notice also that in a rectangularly dense algebra, every element is the sum of the rectangles below it.

Lemma 3.7. Let α be finite and 𝔄 a CA_{α}. An element z is a rectangle iff there are x_{0}, …, x_{α−1} such that z = ∏_{i∈α}c_{(α∼{i})}(x_{i}) .

Proof: For the implication from left to right, just set x_{i} = z for each i ∈ α and use the definition of a rectangle:

∏_{i∈α}c_{(α∼{i})}(z) = c_{(∅)}(z) = z .

For the reverse implication, observe that it can be expressed as a series of conditional equations. Since a conditional equation holds in all CA_{α} iff it holds in all simple CA_{α}, it suffices to verify the implication under the additional hypothesis that 𝔄 is simple. Set

y_{i} = c_{(α∼{i})}(x_{i}) , (1)

and suppose that

z = ∏_{i∈α}y_{i} . (2)

Let Γ and Δ be arbitrary subsets of α. Then

c_{(Γ)}(z) · c_{(Δ)}(z) = c_{(Γ)}(∏_{i∈α}y_{i}) · c_{(Δ)}(∏_{i∈α}y_{i}) by (2),
= ∏_{i∈α∼Γ}y_{i} · ∏_{i∈α∼Δ}y_{i}  by (1), 3.5(ii),
= ∏_{i∈α∼(Γ∩Δ)}y_{i}  by BA,
= c_{(Γ∩Δ)}(∏_{i∈α}y_{i})  by (1), 3.5(ii),
= c_{(Γ∩Δ)}(z)  by (2).

Thus, z is a rectangle by Definition 3.6(i).

The preceding lemma is closely related to Theorem 1.10.11 in Henkin-Monk-Tarski [1971]. Indeed, the equivalence of (i) and (iv) in that theorem is just the special case of our lemma when

x_{0} = x_{1} = ⋯ = x_{n−1} = z .

On the other hand, let y_{i} be as defined in (1) of the preceding proof, and suppose that (2) holds. Then by (1) and Lemma 3.5(ii), using also the simplicity of 𝔄, we have

c_{(α∼{i})}(z) = c_{(α∼{i})}(∏_{j∈α}y_{j}) = c_{(α∼{i})}(∏_{j∈α}c_{(α∼{j})}(x_{j})) = c_{(α∼{i})}(x_{i}) = y_{i} .

Therefore, our lemma also follows immediately from the theorem in Henkin-Monk-Tarski [1971].

Part (ii) of the next lemma occurs as Lemma 1.10.13(ii) in Henkin-Monk-Tarski [1971].

Lemma 3.8. Suppose that 2 ≤ α < ω.

(i) In a CA_{α} every rectangle below the main diagonal is a quasi-atom.

(ii) In a simple CA_{α} every non-zero rectangle below the main diagonal is an atom.

Proof: To prove (i) suppose that x is a non-zero rectangle below d, and let y be below x. Since x · −y is below x, it must be below d. Therefore,

d · c_{(α∼{0})}(x · −y) = x · −y and d · c_{(α∼{i})}(y) = y for 0 < i < α, (1)

by Lemma 3.2(i),(ii). Set

a = c_{(α∼{0})}(x · −y) · ∏_{0<i<α}c_{(α∼{i})}(y) . (2)

Then

a ≤ c_{(α∼{0})}(x) · ∏_{0<i<α}c_{(α∼{i})}(x)  by (2) and monotony,
= x  since x is a rectangle,
≤ d  by assumption.

Therefore,

a = d · a
= d · c_{(α∼{0})}(x · −y) · ∏_{0<i<α}c_{(α∼{i})}(y)  by (2),
= (x · −y) · y  by (1),
= 0  by BA.

We have shown that

c_{(α∼{0})}(x · −y) · ∏_{0<i<α}c_{(α∼{i})}(y) = 0 .

Consequently,

0 = c_{0} … c_{α−1}[c_{(α∼{0})}(x · −y) · ∏_{0<i<α}c_{(α∼{i})}(y)] by (C1),
= c_{0}c_{(α∼{0})}(x · −y) · ∏_{0<i<α}c_{i}c_{(α∼{i})}(y)  by (C3), 3.2(i),(v),
= c_{(α)}(x · −y) · ∏_{0<i<α}c_{(α)}(y)  by definition of c_{(α)},
= c_{(α)}(x · −y) · c_{(α)}(y)  by Boolean algebra.

Applying 3.2(xi),(i) α times we conclude that

x · −y · c_{(α)}(y) = 0 .

Thus, x · c_{(α)}(y) ≤ y. The reverse inclusion follows from the assumption that y ≤ x and from postulate (C2). This proves part (i).

Part (ii) follows from part (i) and Lemma 2.17(ii).

Remark 3.9. The converse to 3.8 is false: there can be quasi-atoms (and even atoms) below the main diagonal that are not rectangles. In fact, let U be a set of cardinality at least 2 and let 𝔄 be the subalgebra of ℭ_{α}(U) consisting of constants. Then d is itself an atom of 𝔄, but it is not a rectangle.

Lemma 3.10. Suppose that 2 ≤ α < ω. Then every rectangularly dense, simple CA_{α} is atomic.

Proof: Suppose that 𝔄 is a rectangularly dense, simple CA_{α}. Let x be a nonzero element of 𝔄. We shall construct an atom below x. Since 𝔄 is rectangularly dense, there is a non-zero rectangle y below x. Then for each i ∈ α we have d · c_{(α∼{i})}(y) ≠ 0, by Lemma 3.4. Thus, we can choose a non-zero rectangle z_{i} below d · c_{(α∼{i})}(y). By the previous lemma and the simplicity of 𝔄 we have

(1) z_{i} is an atom.

Set

w = ∏_{i∈α}c_{(α∼{i})}(z_{i}) . (2)

(See Figure 2.) Because z_{i} ≤ c_{(α∼{i})}(y), we have

c_{(α∼{i})}(z_{i}) ≤ c_{(α∼{i})}c_{(α∼{i})}(y) = c_{(α∼{i})}(y)

by Lemma 3.2(i),(ii). Hence,

w ≤ ∏_{i∈α}c_{(α∼{i})}(y) by (2),
= y  since y is a rectangle,
≤ x  by assumption.

Further, c_{(α)}(w) = 1, by (2), Lemma 3.5(ii) (with Δ = α), and the simplicity of 𝔄. Consequently, w ≠ 0 by (C1). Finally, w is a rectangle by Lemma 3.7. We have shown that

(3) w is a non-zero rectangle below x.

Figure 2. The construction of the atom w below x.

Our goal is to prove that

(4) w is an atom.

We first show:

(5) If u is a non-zero rectangle below w, then w = u.

Let u be a non-zero rectangle below w. Then

0 < d · c_{(α∼{i})}(u)  by 3.4,
≤ d · c_{(α∼{i})}(w)  by 3.2(ii) and u ≤ w,
≤ d · c_{(α∼{i})}(c_{(α∼{i})}(z_{i})) by 3.2(ii) and (2),
= d · c_{(α∼{i})}(z_{i})  by 3.2(i),
= z_{i}  by 3.3(i),(ii) and z_{i} ≤ d.

But z_{i} is an atom, by (1). Therefore, z_{i} = d · c_{(α∼{i})}(u). It follows that

c_{(α∼{i})}(z_{i}) = c_{(α∼{i})}(d · c_{(α∼{i})}(u))
= c_{(α∼{i})}(d) · c_{(α∼{i})}(u) by (C3),
= 1 · c_{(α∼{i})}(u)  by (C5), 3.3(iii),
= c_{(α∼{i})}(u)  by BA,

(In the above application of Lemma 3.3(iii) we take Δ = α ∼ {i} and Γ = α.) Using the above equality together with (2) and the assumption that u is a rectangle, we see that

w = ∏_{i∈α}c_{(α∼{i})}(z_{i}) = ∏_{i∈α}c_{(α∼{i})}(u) = u ,

which proves (5).

Now assume that v is any non-zero element below w. Then there is a non-zero rectangle u below v, by rectangular density. By (5) we see that w = u. This forces w = v. We have proven (4). Together, (3) and (4) show that every non-zero element in 𝔄 is above an atom. The proof of the lemma is complete.

We shall see in Theorem 5.18 below that the hypothesis of simplicity in the previous lemma can be dropped provided we replace “atomic” with “quasi-atomic”, i.e., a rectangularly dense CA_{α} is always quasi-atomic. Moreover, we shall see there that the above proof really has two main parts: the proof that below every non-zero element x there is a non-zero “point” w, and the proof that every non-zero point w is an atom (or a quasi-atom in a non-simple algebra).

As mentioned in the introduction, Henkin and Tarski proved that an atomic CA_{α}with rectangular atoms is representable. The next theorem is a generalization of their result.

Theorem 3.11. For α ≥ 2, every rectangularly dense CA_{α} is representable.

Proof: First, assume that α is finite. Each simple, rectangularly dense CA_{α} is atomic, by the previous lemma. Therefore it is in RCA_{α} by the Henkin-Tarski representation theorem for atomic cylindric algebras with rectangular atoms (see Henkin-Monk-Tarski [1985], Theorem 3.2.14). It now follows from Theorem 2.11 (with L = CA_{α} and K = RCA_{α}) that every rectangularly dense CA_{α} is in RCA_{α}.

Suppose that α is infinite, and let 𝔄 be a rectangularly dense CA_{α}. RCA_{α} is a variety. Therefore, to show that 𝔄 is in RCA_{α} it suffices to show that every equation true of RCA_{α} is true of 𝔄. Let ε be any such equation. Then ε contains only finitely many of the symbols that denote cylindrifications and diagonal elements in the language of CA_{α}. By reindexing these symbols, we may assume without loss of generality that ε is an equation in the language of CA_{β} for some finite β ≥ 2. Let 𝔅 be the β-reduct of 𝔄, i.e., the reduct of 𝔅 to the language of CA_{β}. Then 𝔅 is also rectangularly dense, since the property of being a rectangle is preserved under formation of reducts. Therefore 𝔅 is in RCA_{β} by the finite dimensional case of the present theorem. Now every equation true of RCA_{α} is true of RCA_{β} (see the remarks concerning β-reducts that follow the definition of RCA_{α}). It follows that ε holds in 𝔅 and therefore also in its expansion 𝔄. This completes the proof of the theorem.

Strictly speaking, the restriction α ≥ 2 in the statement of Theorem 3.11 is not necessary. In the case when α = 0, 1 the theorem would assert that every CA_{0} and CA_{1} is representable (see the remark following Definition 3.6). As was pointed out after Definition 3.1, this assertion is known to be true. However, our proof does not cover these cases: it is based on Lemma 3.8, which requires the assumption α ≥ 2. A similar remark also applies to some of our later results, for example Theorems 4.6, 4.7, and 4.18. To emphasize that when α = 0, 1 our theorems assert nothing new and our proofs do not apply, we shall always add the restriction α ≥ 2.

The reader will have noticed that the proof of our representation theorem uses the special case of the Henkin-Tarski representation theorem when the dimension is finite and the algebra is simple. As is pointed out in Discussion 3.2.15 of Henkin-Monk-Tarski [1985], this special case of their theorem has a substantially simpler and more intuitive proof than the general case. It will be helpful to present a brief sketch of this proof.

We assume that α is finite and 𝔄 is simple. Let U be the set of subdiagonal atoms of 𝔄. For each atom x of 𝔄 and each i < α, the meet of the hyperplane c_{(α−{i})}(x) with the main diagonal, i.e., the element d·c_{(α−{i})}(x), is a subdiagonal atom. Let’s call it the i^{th} coordinate atom of x. We define a mapping h of the atoms of 𝔄 to elements of ^{α}U by sending each atom x to the sequence of its coordinate atoms, i.e.,

h(x) = (x_{0}, …, x_{α−1}) .

Then h is one-one and onto, because any α-tuple (y_{0}, …, y_{α−1}) in ^{α}U is the sequence of coordinate atoms of a unique atom of 𝔄, namely the element

x = ∏_{i<α}c_{(α−{i})}(y_{i}) .

We extend h in the obvious way to an additive mapping of the elements of 𝔄 to elements of ℭ_{α}(U). Certainly, h is a Boolean embedding, and it is not difficult to check that it preserves cylindrifications and diagonal elements as well. This completes our sketch.

Corollary 3.12. For α ≥ 2, a CA_{α} is representable iff it is embeddable into a rectangularly dense CA_{α}.

Proof: The difficult direction of the corollary, from right to left, follows from the previous theorem. For the converse direction, suppose that 𝔄 is a representable CA_{α}. Then 𝔄 is embeddable into the direct product 𝔅 of a family of full cylindric set algebras of dimension α. Now each such set algebra is rectangularly dense, since the singletons are always rectangles (see the remark after Definition 3.6). Moreover, the direct product of a family of rectangularly dense cylindric algebras is again rectangularly dense. This follows from two simple observations: (1) 0 is a rectangle in every cylindric algebra; (2) the property of being a rectangle is defined by a collection of equations, and hence an element of a direct product is a rectangle iff each coordinate element is a rectangle (in the coordinate algebra). Therefore, 𝔅 is rectangularly dense.

Each of the representation theorems for rectangularly dense algebras that we shall formulate in the subsequent sections (Theorems 4.6, 4.7, 4.18, 6.7, and 6.13) has an “if and only if” corollary that is analogous in statement and proof to the preceding one. With few exceptions, we shall not bother to formulate them.

4. Rectangularly dense quasi-polyadic and substitution-cylindrification algebras

Polyadic and quasi-polyadic algebras (with and without equality) of dimension α were defined by Halmos in a series of papers in the 1950s (see Halmos [1962]). For finite dimensions the two notions coincide. An elegant definition of the notion of a quasi-polyadic algebra (with or without equality) that is equivalent to Halmos’ original definition was given by Sain-Thompson [1991], Definition 1 and the remark on p. 548, and it is this latter definition that we shall use. Substitution-cylindrification algebras were introduced by Pinter [1973] under the name of quantifier algebras.

We shall extend Theorem 3.11 to quasi-polyadic and substitution-cylindrific-ation algebras with and without equality. In each case the extension to algebras with equality is relatively routine. From this extension we are then able to derive the result for algebras without equality under the proviso that the substitution operations are completely additive. We shall show that this condition is met if the algebra is quasi-atomic. The representation theorems for algebras without equality should be viewed as the principal results of this section.

Representation theorems for atomic quasi-polyadic algebras of finite dimension with rectangular atoms are formulated in Henkin-Monk-Tarski [1985], Theorems 5.4.36 and 5.4.38. However, the proof of 5.4.38 is defective. It depends on Theorem 5.4.37, which asserts the existence of the completion of an arbitrary equality-free quasi-polyadic algebra 𝔄 of finite dimension. Unfortunately, such completions have only been shown to exist under the proviso that the substitution operations of the original algebra 𝔄 are completely additive. We correct this error by showing that in an atomic, rectangularly dense quasi-polyadic algebra the substitution operations are always completely additive.

Definition 4.1. A quasi-polyadic algebra of dimension α is an algebra

𝔄 = ⟨A , + , − , c_{i} , s_{ij} , p_{ij} ⟩_{i,j∈α}

such that ⟨A , + , −⟩ is a Boolean algebra , the operations c_{i}, s_{ij} , and p_{ij} are all unary , and the following postulates are satisfied for all x, y ∈ A and all i, j, k ∈ α:

(Q1) s_{ii}(x) = x,

(Q2) p_{ii}(x) = x,

(Q3) p_{ij}(x) = p_{ji}(x) ,

(Q4) x ≤ c_{i}(x) ,

(Q5) c_{i}(x + y) = c_{i}(x) + c_{i}(y) ,

(Q6) s_{ij}c_{i}(x) = c_{i}(x) ,

(Q7) c_{i}s_{ij}(x) = s_{ij}(x) whenever i ≠ j, (Q8) s_{ij}c_{k}(x) = c_{k}s_{ij}(x) whenever k ≠ i, j, (Q9) s_{ij}(x + y) = s_{ij}(x) + s_{ij}(y) , (Q10) s_{ij}(−x) = −s_{ij}(x) , (Q11) p_{ij}(x + y) = p_{ij}(x) + p_{ij}(y) , (Q12) p_{ij}(−x) = −p_{ij}(x) , (Q13) p_{ij}p_{ij}(x) = x, (Q14) p_{ij}p_{ik}(x) = p_{jk}p_{ij}(x) whenever i, j, k are distinct , (Q15) p_{ij}s_{ji}(x) = s_{ij}(x), when α ≥ 3, and (Q1)–(Q15) and the following two additional postulates (Q16) c_{i}(x · c_{i}(y)) = c_{i}(x) · c_{i}(y) , (Q17) c_{i}c_{j}(x) = c_{j}c_{i}(x) , when α ≤ 2. A quasi-polyadic equality algebra of dimension α is an algebra

𝔄 = ⟨A , + , − , c_{i} , s_{ij} , p_{ij} , d_{ij} ⟩_{i,j∈α}

such that the reduct

𝔄 = ⟨A , + , − , c_{i} , s_{ij} , p_{ij} ⟩_{i,j∈α}

is a quasi-polyadic algebra and the d_{ij} are constants satisfying the additional postulates (Q18) s_{ij}(d_{ij}) = 1 , (Q19) x · d_{ij} ≤ s_{ij}(x) . The classes of all quasi-polyadic algebras and all quasi-polyadic equality algebras

of dimension α are denoted by QPA_{α} and QPEA_{α} respectively . We also use the notations “QPA_{α}” and “QPEA_{α}” as abbreviations for the phrases “quasi-polyadic algebra of dimension α” and “quasi-polyadic equality algebra of dimension α” respectively. The element d_{ij} is called the ij^{th} diagonal element, and the operations c_{i}, s_{ij} , and p_{ij} are called the i^{th} cylindrification , the ij^{th} substitution , and the ij^{th} permutation or transposition.

From postulates (Q9) and (Q11) we easily see that whenever x ≤ y we have s_{ij}(x) ≤ s_{ij}(y) and p_{ij}(x) ≤ p_{ij}(y). We shall refer to these as monotony laws for quasi-polyadic algebras.

To give an example of a quasi-polyadic algebra and of a quasi-polyadic equality algebra, let U be any set and define 𝔔_{α}(U) and 𝔓_{α}(U) to be the algebras

⟨Sb(^{α}U) , ∪ , ∼ , C_{i} , S_{ij} , P_{ij} ⟩_{i,j<α}

and

⟨Sb(^{α}U) , ∪ , ∼ , C_{i} , S_{ij} , P_{ij} , D_{ij} ⟩_{i,j<α}

respectively, where

⟨Sb(^{α}U) , ∪ , ∼ , C_{i} , D_{ij}⟩_{i,j<α}

is the full cylindric set algebra over U of dimension α, and the operations S_{ij} and P_{ij} are defined by

S_{ij}(X) = X if i = j ,
S_{ij}(X) = {u ∈ ^{α}U : for some x ∈ X with x_{i} = x_{j} , u_{k} = x_{k} for k ≠ i} if i ≠ j ,
P_{ij}(X) = {u ∈ ^{α}U : for some x ∈ X, u_{k} = x_{k} for k ≠ i, j and u_{i} = x_{j} , u_{j} = x_{i}}

for each X ⊆ ^{α}U and each i, j in α. It is easy to check that 𝔔_{α}(U) (respectively 𝔓_{α}(U)) is a quasi-polyadic algebra (respectively, a quasi-polyadic equality algebra) for every set U. It is called the full quasi-polyadic (respectively, the full quasipolyadic equality) set algebra over U of dimension α. A quasi-polyadic algebra (respectively, a quasi-polyadic equality algebra) is said to be representable if it can be embedded into a direct product of full quasi-polyadic (respectively, quasipolyadic equality) set algebras of dimension α.

The class RQPA_{α} (respectively, RQPEA_{α}) of all representable quasi-polyadic algebras (respectively, all representable quasi-polyadic equality algebras) of dimension α is a subvariety of QPA_{α} (respectively, of QPEA_{α}) for each α ≥ 2.^{3} However, as in the cylindric algebraic case, the two varieties are distinct, and in fact, for α > 2, RQPA_{α} (respectively, RQPEA_{α}) is not finitely axiomatizable and not even axiomatizable by a finite set of equational schemata (see Johnson [1969], Theorem 3.5, and Sain-Thompson [1991], Theorem 2).

Suppose that β < α. Just as for cylindric algebras, every equation in the language of QPA_{β} (or QPEA_{β}) that holds in RQPA_{α} (or RQPEA_{α}) must hold in RQPA_{β} (or RQPEA_{β}). (See the remarks concerning β-reducts following the definition of RCA_{α}.)

It is well known and easy to check that both QPA_{α} and QPEA_{α} are varieties of normal Boolean algebras with operators. For finite α they are also discriminator varieties with the same discriminator term as CA_{α}.

We gather together some consequences of the axioms for quasi-polyadic algebras.

Lemma 4.2. Let α ≥ 2 and 𝔄 a QPA_{α} or a QPEA_{α}. Then the following are true for all x, y ∈ A and all i, j < α.

(i) The mapping x ⟼ s_{ij}(x) is an endomorphism, and x ⟼ p_{ij}(x) an automorphism, of the Boolean reduct ⟨A , + , −⟩ of 𝔄.

(ii) If x ≤ y, then c_{i}(x) ≤ c_{i}(y) .

(iii) c_{i}c_{i}(x) = c_{i}(x) .

(iv) c_{i}(−c_{i}(x)) = −c_{i}(x) .

(v) c_{i}(x · c_{i}(y)) = c_{i}(x) · c_{i}(y) .

(vi) x · c_{i}(y) = 0 iff y · c_{i}(x) = 0 .

(vii) c_{i}c_{j}(x) = c_{j}c_{i}(x) .

(viii) s_{ij}s_{ij}(x) = s_{ij}(x) .

(ix) s_{ij}s_{ji}(x) = s_{ij}(x) .

(x) If y ≤ s_{ij}(x), then c_{i}(y) ≤ s_{ij}(x) when i ≠ j.

(xi) c_{j}s_{ij}(x) = c_{i}s_{ji}(x) .

(xii) c_{j}p_{ij}(x) = p_{ij}c_{i}(x) .

(xiii) p_{ij}c_{i}c_{j}(x) = c_{i}c_{j}(x) .

(xiv) s_{ij}c_{j}(x) = p_{ij}c_{j}(x) .

(xv) s_{ij}p_{ij}c_{i}(x) = c_{i}(x) .

(xvi) p_{ij}s_{ki}(x) = s_{kj}p_{ij}(x) when i, j, k are distinct .

3It seems that an explicit statement and proof of these facts have not appeared in the literature.

However, the proof given in Henkin-Monk-Tarski [1985] that RCA_{α} is a variety goes through with minor modifications to show that RQPA_{α} and RQPEA_{α}, as well as the classes RSCA_{α} and RSCEA_{α} defined below, are varieties. See, in particular, Lemmas 3.1.92, 3.1.93, and Theorems 3.1.103, 3.1.108 in op. cit. A simpler proof, in the context of discriminator varieties, is given Németi

(xvii) s_{0i}(x) = p_{1i}s_{01}p_{1i}(x) when i ≠ 0 . (xviii) s_{i0}(x) = p_{i0}p_{1i}s_{01}p_{1i}(x) when i ≠ 0 . (xix) s_{ij}(x) = p_{0j}p_{i0}p_{1i}s_{01}p_{1i}p_{0j}(x) for distinct i, j ≠ 0 . (xx) If c_{i}(x) = x, then s_{ij}(x) = x.

Proof: Part (i) follows at once from Axioms (Q9)–(Q13) (see Sain-Thompson [1991], p. 546). In particular, s_{ij}(0) = 0. From this and Axiom (Q7) we see that

c_{i}(0) = 0 (1)

(see equation (5) in op. cit., p. 546). The equivalence in (vi) is an immediate consequence of (v), Axiom (Q4), and (1). (For a proof see Henkin-Monk-Tarski [1971], Theorem 1.2.5.)

The validity of the remaining laws is a consequence of Theorem 1 in Sain-Thompson [1991], according to which two different formulations of the notion of a quasi-polyadic algebra are equivalent. It is possible to cite explicit passages in op. cit. where (ii)–(iv), (vii)–(ix), (xii) and (xvi) are established: laws (ii)–(iv) are established on pp. 545–546, equation (vii) in Claim 1.1, p. 548^{4}, equation (viii) in the proof of (J7) on p. 550, equations (ix) and (xvi) in Lemma 1.5(i),(v)^{5} and equation (xii) in Lemma 1.6(i).^{6}

Since (v), (x), (xi), (xiii)–(xv), and (xvii)–(xx) are not explicitly proved in op. cit., we provide simple demonstrations. From (ii) and (iii) we easily get

c_{i}(x · c_{i}(y)) ≤ c_{i}c_{i}(y) = c_{i}(y) . (2)

Similarly, from (ii) and (iv) we get

c_{i}(x · −c_{i}(y)) ≤ c_{i}(−c_{i}(y)) = −c_{i}(y) . (3)

By BA and (Q5) we see that

c_{i}(x) = c_{i}(x · c_{i}(y) + x · −c_{i}(y)) = c_{i}(x · c_{i}(y)) + c_{i}(x · −c_{i}(y)) .

Multiplying both sides by c_{i}(y) and using Boolean distributivity gives us

c_{i}(x) · c_{i}(y) = c_{i}(x · c_{i}(y)) · c_{i}(y) + c_{i}(x · −c_{i}(y)) · c_{i}(y) .

Now the second summand is 0 by (3) and BA. The first summand is c_{i}(x · c_{i}(y)) by (2) and BA. Thus, we arrive at (v).

Part (x) follows from (ii) and (Q7), and (xx) is a simple consequence of (Q6). For (xiii) we have

p_{ij}c_{i}c_{j}(x) = p_{ij}s_{ij}c_{i}c_{j}(x)  by (Q6),

4The proof of this claim makes essential use of the hypothesis that α > 2. However, in case α = 2, (vii) is actually one of our axioms (see Definition 4.1). The first term in the penultimate line of p. 548 should read “c_{i}c_{j}” instead of “c_{i}c_{i}”.

5Although Lemma 1.5 has the hypothesis that α > 2, the hypothesis is not needed for the proof of part (i). In particular, the proof is valid when α = 2.

6Again, the given hypothesis α > 2 may be relaxed to α ≥ 2 and the proof remains valid. The formulation of Lemma 1.6(i) and its proof contain several typographic errors: the first term in the formulation should read “c_{j}p_{ij}”, not “c_{i}p_{ij}”; the seventh and eighth terms in (25) should read “p_{ji}s_{j}^{i}c_{i}” and “p_{ij}s_{j}^{i}c_{i}” instead of “p_{ij}s_{i}^{j}c_{i}” and “p_{ij}s_{i}^{j}c_{i}”.

= s_{ji}c_{i}c_{j}(x)  by (Q15),
= s_{ji}c_{j}c_{i}(x)  by (vii),
= c_{j}c_{i}(x)  by (Q6),
= c_{i}c_{j}(x)  by (vii).

For (xi) we have

c_{j}s_{ij}(x) = c_{j}p_{ij}s_{ji}(x)  by (Q15),
= p_{ij}c_{i}s_{ji}(x)  by (xii),
= p_{ij}c_{i}c_{j}s_{ji}(x)  by (Q7),
= c_{i}c_{j}s_{ji}(x)  by (xiii),
= c_{i}s_{ji}(x)  by (Q7).

For (xiv) we have

s_{ij}c_{j}(x) = p_{ij}s_{ji}c_{j}(x)  by (Q15),
= p_{ij}c_{j}(x)  by (Q6).

For (xv) we have

s_{ij}p_{ij}c_{i}(x) = s_{ij}c_{j}p_{ij}(x)  by (xii),
= p_{ij}c_{j}p_{ij}(x)  by (xiv),
= p_{ij}p_{ij}c_{i}(x)  by (xii),
= c_{i}(x)  by (Q13).

We now take up the proof of (xvii). The case i = 1 follows from (Q2). Suppose that i ≠ 0, 1. Then by (xvi) (with i, j, k replaced by 1, i, 0 respectively) we get

p_{1i}s_{01}(x) = s_{0i}p_{1i}(x)

for all x. Replacing x by p_{1i}x in this equation and using (Q13) we see that

p_{1i}s_{01}p_{1i}(x) = s_{0i}p_{1i}p_{1i}(x) = s_{0i}(x) .

For (xviii) we use (Q15) and (xvii):

s_{i0}(x) = p_{i0}s_{0i}(x) = p_{i0}p_{1i}s_{01}p_{1i}(x) .

To prove (xix) we again use (xvi) (with i, j, k replaced by 0, j, i respectively):

p_{0j}s_{i0}(x) = s_{ij}p_{0j}(x) . (4)

Hence,

s_{ij}(x) = s_{ij}p_{0j}p_{0j}(x)  by (Q13),
= p_{0j}s_{i0}p_{0j}(x)  by (4),
= p_{0j}p_{i0}p_{1i}s_{01}p_{1i}p_{0j}(x)  by (xviii).

Corollary 4.3. Let α ≥ 2 and 𝔄 a QPA_{α} or a QPEA_{α}. Then each permutation p_{ij} of 𝔄 is completely additive. If s_{01} is completely additive, then every other substitution s_{ij} of 𝔄 is completely additive.

Proof: Since the permutation p_{ij} is a Boolean automorphism, it is easily seen to be self-conjugate in the sense that

y · p_{ij}(x) = 0 iff x · p_{ij}(y) = 0 . (1)

Indeed, for any x, y, z we have p_{ij}(z) = 0 iff z = 0, and

p_{ij}(y · p_{ij}(x)) = p_{ij}(y) · p_{ij}p_{ij}(x) = p_{ij}(y) · x ,

by Lemma 4.2(i) and (Q13). Together, these two observations yield (1).

Since a self-conjugate operation is known to be completely additive, by Jónsson-Tarski [1951], Theorem 1.14, this proves the first assertion of the corollary. For the second, suppose that s_{01} is completely additive. In view of the first part of the corollary, it follows from Lemma 4.2(xvii)–(xix) and (Q1) that every substitution can be written as a composition of unary, completely additive operations, namely the permutations and s_{01} . By Theorem 1.9 of op. cit., the composition of two (unary) completely additive functions is again completely additive. Hence, every substitution is completely additive.

The reduct of a QPEA_{a} 𝔄 to the cylindric algebraic operations is a cylindric algebra (see Henkin-Monk-Tarski [1985], Theorem 5.4.3) and is called the cylindric reduct of 𝔄. Similiarly, the reduct of 𝔄 to the quasi-polyadic operations is called the quasi-polyadic reduct of 𝔄.

Lemma 4.4. Let α be finite and 𝔄 a QPEA_{α}. A subset of A is an ideal of 𝔄 iff it is an ideal of the cylindric reduct of 𝔄. Hence, 𝔄 is simple iff its cylindric reduct is simple.

Proof: Let 𝔄 be a QPEA_{α} and 𝔅 its cylindric reduct. A subset I of A that is an ideal of 𝔄 is obviously an ideal of 𝔅. Suppose now that I is an ideal of 𝔅.

(1) s_{ij}(x) and p_{ij}(x) are in I whenever x ∈ I.

Indeed, let x ∈ I. Then

s_{ij}(x) ≤ s_{ij}c_{i}c_{(α∼{i})}(x)  by (Q4) and monotony,
= c_{(α)}(x)  by (Q6) and 4.2(vii).

Therefore, s_{ij}(x) is in I by Lemma 2.4(iii),(iv) applied to 𝔅. Also,

p_{ij}(x) ≤ p_{ij}c_{j}c_{(α∼{j})}(x)  by (Q4) and monotony,
= s_{ij}c_{j}c_{(α∼{j})}(x)  by 4.2(xiv),
= s_{ij}c_{i}c_{(α∼{i})}(x)  by 4.2(vii),
= c_{(α)}(x)  by (Q6).

Hence, p_{ij}(x) is in I by Lemma 2.4(iii),(iv) applied to 𝔅. This proves (1). Using (1), we see that I satisfies Sain’s conditions for being an ideal of 𝔄 (see Lemma 2.4).

The notions of a rectangle and of a rectangularly dense algebra (see Definition 3.6) carry over without change from CA_{α} to QPA_{α} and QPEA_{α}.

Recall that for finite α a polyadic algebra (respectively, a polyadic equality algebra) is the same thing as a quasi-polyadic algebra (respectively, a quasi-polyadic equality algebra). Thus, any result concerning finite dimensional polyadic algebras and polyadic equality algebras applies automatically to quasi-polyadic algebras and quasi-polyadic equality algebras. We shall use this observation several times below without further mention.

Corollary 4.5. Let 2 ≤ α < ω. Then every rectangularly dense, simple QPEA_{α} is atomic.

Proof: Let 𝔄 be a simple, rectangularly dense QPEA_{α} and 𝔅 its cylindric reduct. Then 𝔅 is a simple cylindric algebra, by the preceding lemma. Furthermore, 𝔅 is rectangularly dense, since the definition of this notion involves only the operations of the cylindric reduct. Therefore 𝔅 is atomic, by Lemma 3.10. Because the definition of the notion of being atomic involves only the Boolean operations, 𝔄 must also be atomic.

Theorem 4.6. For α ≥ 2, every rectangularly dense QPEA_{α} is representable.

The proof of the theorem is nearly identical to the proof of the cylindric algebraic version, Theorem 3.11. Instead of Lemma 3.10 and Theorem 3.2.14 in Henkin-Monk-Tarski [1985], we use Corollary 4.5 and Theorem 5.4.36 in op. cit.The latter states that, for finite α ≥ 3, every atomic QPEA_{α} with rectangular atoms is representable. One can check that the theorem and its proof are valid also in the case when α = 2. We leave the details of the proof to the reader.

We now turn to the task of extending Theorem 4.6 to quasi-polyadic algebras. First, recall the notion of a completion of a BAO. Let 𝔄 and 𝔅 be Boolean algebras with operators of the same similarity type. Then 𝔅 is a completion^{7} of 𝔄 provided that: (i) the Boolean reduct of 𝔅 (but not necessarily 𝔅 itself) is complete and 𝔄 is a subalgebra of 𝔅; (ii) for every y in B, we have (in 𝔅)

y = ∑{x ∈ A : x ≤ y};

(iii) for every extra-Boolean operator f of 𝔅, say of rank n, and for all y_{0}, …, y_{n−1} in B we have (in 𝔅)

f(y_{0}, …, y_{n−1}) = ∑{f(x_{0}, …, x_{n−1}) : x_{i} ∈ A and x_{i} ≤ y_{i} for all i < n} .

(The point of the caution in (i) is that the extra-Boolean operations of 𝔅 are not required to be completely additive.) A general study of completions of Boolean algebras with operators can be found in Monk [1970]. He shows that every completely additive BAO 𝔄 has a completion 𝔅, and this completion is unique up to isomorphisms over 𝔄. Moreover, any positive equation holding in 𝔄 holds in 𝔅.

7An equivalent formulation of condition (ii) is that A is dense in 𝔅. Condition (iii) actually follows from conditions (i) and (ii) (and is therefore superfluous) when the extra-Boolean operators of 𝔅 are completely additive. This is the case for cylindric algebras, quasi-polyadic algebras with equality, and relation algebras. In Henkin-Monk-Tarski [1971], Remark 2.7.22, another condition is added to the definition of a completion, namely it is required that ∑^{𝔅}X = ∑^{𝔄}X for every X ⊆ A such that ∑^{𝔄}X exists. However, the proof of 23.1 in Sikorski [1964], p. 93, shows that this condition is implied by conditions (i) and (ii).

Suppose that 𝔄 is a QPA_{α} in which s_{01} is completely additive. Then by Corollary 4.3, 𝔄 is completely additive, so it has a completion 𝔅. Now 𝔅 must be a QPA_{α} as well. Indeed, all the equations defining quasi-polyadic algebras, with the exception of (Q10) and (Q12), are positive and hence hold in 𝔅. The fact that substitutions and permutations preserve + , · , 0 , and 1 is expressible by positive equations, so this is true in 𝔅 as well. To verify that (Q10) holds in 𝔅, suppose that y = −x. Then x + y = 1 and x · y = 0. Therefore,

s_{ij}(x) + s_{ij}(y) = s_{ij}(x + y) = s_{ij}(1) = 1 ,

and similarly

s_{ij}(x) · s_{ij}(y) = 0 ,

i.e., s_{ij}(y) = −s_{ij}(x). An analogous argument applies in the case of (Q12). (A similar argument is used by Sain-Thompson [1991], Proposition 9, to show that the perfect extension of a quasi-polyadic algebra is again a quasi-polyadic algebra. Halmos [1962], pp. 230–232, shows directly that the perfect extension of a polyadic algebra is itself a polyadic algebra.)

Sain-Thompson [1991], pp. 561–562, shows that the perfect extension of a QPA_{α} has a first-order definitional extension that is a QPEA_{α}. (Hence, every QPA_{α} is a subreduct of a QPEA_{α}.) The same argument shows that the completion 𝔅 has a first-order definitional extension that is a QPEA_{α}. We give the argument here for the sake of completeness.

(1) s_{ij}(∏X) = ∏{s_{ij}(x) : x ∈ X} for every X ⊆ B .

Indeed,

s_{ij}(∏X) = s_{ij}(−∑{−x : x ∈ X})  by Boolean algebra,
= −s_{ij}(∑{−x : x ∈ X})  by 4.2(i),
= −∑{s_{ij}(−x) : x ∈ X}  by complete additivity,
= −∑{−s_{ij}(x) : x ∈ X}  by 4.2(i),
= ∏{s_{ij}(x) : x ∈ X}  by Boolean algebra.

Now define elements d_{ij} in 𝔅 by stipulating

d_{ij} = ∏{y : s_{ij}(y) = 1} , (2)

and notice that this definition (due to Halmos [1962], p. 228) is first-order: it is the conjunction of the two conditions

∀y(s_{ij}(y) = 1 → x ≤ y)  ,  ∀z[∀y(s_{ij}(y) = 1 → z ≤ y) → z ≤ x] .

Then

s_{ij}(d_{ij}) = s_{ij}(∏{y : s_{ij}(y) = 1})  by (2),
= ∏{s_{ij}(y) : s_{ij}(y) = 1}  by (1),
= 1  by BA.

Thus (Q18) holds. Also, for any x we have

s_{ij}(−x · d_{ij} + s_{ij}(x)) = −s_{ij}(x) · s_{ij}(d_{ij}) + s_{ij}(s_{ij}(x))  by 4.2(i),
= −s_{ij}(x) + s_{ij}(x)  by (Q18) and 4.2(viii),
= 1  by BA.

Thus, −x · d_{ij} + s_{ij}(x) is one of the factors y in the definition (2) of d_{ij} . It follows that

d_{ij} ≤ −x · d_{ij} + s_{ij}(x) ,

and therefore

x · d_{ij} ≤ −x · d_{ij} + s_{ij}(x) .

But x · d_{ij} and −x · d_{ij} are disjoint, so x · d_{ij} ≤ s_{ij}(x) . This shows that (Q19) holds. It follows that the expansion ℭ of 𝔅 obtained by adding the constants d_{ij} is a QPEA_{α}.

Now assume that 𝔄 is also rectangularly dense. By the remarks of the previous paragraphs, its completion 𝔅 is the reduct of a QPEA_{α} ℭ. Using condition (ii) in the definition of a completion, we easily check that 𝔅, and hence also ℭ, inherit the rectangular density of 𝔄. Therefore ℭ is representable, by Theorem 4.6. This gives us a representation of 𝔅 and hence also of 𝔄. We have shown that

Theorem 4.7. For α ≥ 2, every rectangularly dense QPA_{α} in which s_{01} is completely additive is representable.

It is worth emphasizing why we have used completions instead of perfect extensions in the previous argument. In general, the completion of a rectangularly dense algebra is rectangularly dense. However, the perfect extension of a rectangularly dense algebra may not be rectangularly dense.

In the case of a quasi-atomic QPA_{α} the substitutions are always completely additive, as the next lemma shows.

Lemma 4.8. Let 𝔄 be a quasi-atomic, rectangularly dense QPA_{α}. Then each substitution is completely additive.

Proof: Let 𝔄 be a quasi-atomic, rectangularly dense QPA_{α}, and suppose X is a subset of A such that the sum w = ∑X exists. We must show that s_{ij}(w) is the least upper bound of {s_{ij}(x) : x ∈ X}. When i = j this is trivial by (Q1). Thus, we may assume that i ≠ j. Since s_{ij} is a Boolean endomorphism, s_{ij}(w) is certainly an upper bound for {s_{ij}(x) : x ∈ X}. Suppose that z is any other upper bound, with the goal of showing that s_{ij}(w) ≤ z. Since 𝔄 is quasi-atomic, it suffices to show that every quasi-atom below s_{ij}(w) is below z.

Assume that

38 ANDRÉKA, GIVANT, MIKULÁS, NÉMETI, AND SIMON

(1) y is a non-zero quasi-atom and

(2) y ≤ s_{ij}(w) , with the goal of proving

(3) y · z ≠ 0 . We begin by showing that

(4) c_{i}(y) is a quasi-atom in the set {x : c_{i}(x) = x}. Indeed, suppose that

x = c_{i}(x) ≤ c_{i}(y) .

Then

x · y

= y · c_{(α)}(x · y)

by 2.17(i), since y is a quasi-atom,

= y · c_{(α∼{i})}c_{i}(x · y) by 4.2(vii),
= y · c_{(α∼\{i\})}(x · c_{i}(y)) {by 4.2(v) and \atop c_{i}(x) = x,}
= y · c_{(α∼{i})}(x)  since x ≤ c_{i}(y),
= y · c_{(α∼{i})}c_{i}(x)  since c_{i}(x) = x,
= y · c_{(α)}(x)  by 4.2(vii).

Applying c_{i} to both sides, and using c_{i}(x) = x and 4.2(v), we get

x · c_{i}(y) = c_{i}(y) · c_{(α)}(x) .

But x ≤ c_{i}(y). Thus we arrive at (4).

Next, we establish that

(5) s_{ji}c_{i}(y) is a quasi-atom in the set {x : c_{j}(x) = x}. To prove (5), set v = c_{i}(y). Certainly s_{ji}(v) is c_{j}-closed, by (Q7). To show that it is a quasi-atom in the set of c_{j}-closed elements, let x be such that c_{j}(x) = x and x ≤ s_{ji}(v). Applying s_{ij} to both sides, we get

s_{ij}(x) ≤ s_{ij}s_{ji}(v)  by 4.2(i),
= s_{ij}(v)  by 4.2(ix),
= v  by 4.2(xx).

Because s_{ij}(x) is a c_{i}-closed element, by (Q7), and v is a quasi-atom in the set of c_{i}-closed elements, by (4), we obtain

s_{ij}(x) = v · c_{(α)}s_{ij}(x) .

NOTIONS OF DENSITY THAT IMPLY REPRESENTABILITY 39

Applying s_{ji} to both sides and proceeding stepwise, we get

s_{ji}s_{ij}(x) = s_{ji}(v) · s_{ji}c_{(α)}s_{ij}(x)  by 4.2(i),
s_{ji}(x) = s_{ji}(v) · c_{(α)}s_{ij}(x)  by 4.2(ix),(xx),
s_{ji}(x) = s_{ji}(v) · c_{(α)}c_{j}s_{ij}(x)  by 4.2(vii),(iii),
s_{ji}(x) = s_{ji}(v) · c_{(α)}c_{i}s_{ji}(x)  by 4.2(xi),
s_{ji}(x) = s_{ji}(v) · c_{(α)}s_{ji}(x)  by 4.2(vii),(iii),
x = s_{ji}(v) · c_{(α)}(x)  by 4.2(xx).

This proves (5).

Set u = c_{i}(y) · s_{ji}c_{i}(y) . (6)

(7) v = u · c_{(α)}(v) for every rectangle v ≤ u. To establish (7), suppose that v is a rectangle below u. Then

c_{i}(v) ≤ c_{i}(u) ≤ c_{i}(y)

by (6) and 4.2(ii). Therefore c_{i}(v) = c_{i}(y) · c_{(α)}(v) (8) by (4). Similarly,

c_{j}(v) ≤ c_{j}(u) ≤ s_{ji}c_{i}(y)

by 4.2(ii) and (Q7), so c_{j}(v) = s_{ji}c_{i}(y) · c_{(α)}(v) (9) by (5). Hence,

v

= c_{i}(v) · c_{j}(v)

since v is a rectangle and i ≠ j,

= c_{i}(y) · c_{(α)}(v) · s_{ji}c_{i}(y) · c_{(α)}(v)  by (8), (9),
= u · c_{(α)}(v)  by (6).

This proves (7).

With the help of (7) we establish

(10) u is a quasi-atom as follows. Let x ≤ u and take V to be the set of rectangles below x. Since 𝔄 is rectangularly dense we have x = ∑V . (11) Because c_{(α)} is completely additive (since it is self-conjugate — see 2.3(vii) and the proof of 4.3), (11) gives c_{(α)}(x) = ∑{c_{(α)}(v) : v ∈ V } . (12)

Therefore

u · c_{(α)}(x) = u · ∑{c_{(α)}(v) : v ∈ V }  by (12),
= ∑{u · c_{(α)}(v) : v ∈ V }  by BA,
= ∑{v : v ∈ V }  by (7),
= x  by (11).

This proves (10).

Next, we show that

s_{ij}(u) = c_{i}(y) . (13)

Indeed,

s_{ij}(u) = s_{ij}(c_{i}(y) · s_{ji}c_{i}(y))  by (6),
= s_{ij}c_{i}(y) · s_{ij}s_{ji}c_{i}(y)  by 4.2(i),
= s_{ij}c_{i}(y)  by 4.2(ix) and BA,
= c_{i}(y)  by (Q6).

From (13) we conclude

s_{ij}(u · w) = c_{i}(y) (14)

as follows:

s_{ij}(u · w) = s_{ij}(u) · s_{ij}(w)  by 4.2(i),
= c_{i}(y) · s_{ij}(w)  by (13),
= c_{i}(y)  by (2) and 4.2(x).

Finally, from (6) and 4.2(ii) we see that c_{i}(u · x) ≤ c_{i}(y) for any x. Therefore, by (4) we have

(15) c_{i}(u · x) = c_{i}(y) · c_{(α)}(u · x) for every x .

We are ready to prove (3). Since c_{i}(y) ≠ 0 by (1) and (Q4), we have s_{ij}(u·w) ≠ 0 by (14). It follows that u · w ≠ 0. Because w is the supremum of X, there must be an x ∈ X such that u · x ≠ 0. Now u is a quasi-atom by (10), so

u · x = u · c_{(α)}(u · x)

by 2.17(i). Applying s_{ij} to both sides we get

s_{ij}(u) · s_{ij}(x) = s_{ij}(u) · c_{(α)}(u · x)  by 4.2(i), (Q6),
c_{i}(y) · s_{ij}(x) = c_{i}(y) · c_{(α)}(u · x)  by (13),
c_{i}(y) · s_{ij}(x) = c_{i}(u · x)  by (15),
c_{i}(y) · s_{ij}(x) ≠ 0  since u · x ≠ 0,
y · c_{i}s_{ij}(x) ≠ 0  by 4.2(vi),
y · s_{ij}(x) ≠ 0  by (Q7),
y · z ≠ 0  since s_{ij}(x) ≤ z.

This proves (3).

It follows from (3) that s_{ij}(w) ≤ z, i.e., s_{ij}(w) · −z = 0. Otherwise there would be a non-zero quasi-atom y below s_{ij}(w) · −z, and this would contradict (3).

Remark 4.9. We shall see below that the assumptions of quasi-atomicity (atomicity in the simple case) and of rectangular density are both necessary in the preceding lemma. However, it is possible to give the lemma a somewhat stronger formulation. By Corollary 4.3, it suffices to prove that s_{01} is completely additive. Therefore, everywhere in the proof we may replace “i” with “0” and “j” with “1”. Doing this, we notice that only one instance of rectangularity is needed, namely v = c_{0}(v) · c_{1}(v), just after (9). Let us say that an element v is a 01-rectangle if it satisfies this condition, and let us say that 𝔄 is 01-rectangularly dense if every non-zero element is above a non-zero 01-rectangle. Then the modified proof of Lemma 4.8 shows the following: If 𝔄 is quasi-atomic and 01-rectangularly dense, then s_{01} — and hence every substitution of 𝔄 — is completely additive.

Corollary 4.10. Let 𝔄 be a QPA_{α}, where α ≥ 2. Then the following are equivalent :

(i) 𝔄 is representable ; (ii) 𝔄 is embeddable in an atomic, rectangularly dense QPA_{α}; (iii) 𝔄 is embeddable in a quasi-atomic, rectangularly dense QPA_{α}; (iv) 𝔄 is embeddable in a rectangularly dense QPA_{α} in which s_{01} is completely

additive ;

(v) 𝔄 is embeddable in a rectangularly dense, completely additive QPA_{α}.

Proof: Every representable QPA_{α} is embeddable into the direct product of full quasi-polyadic set algebras of dimension α. Each of these full set algebras is atomic and rectangularly dense. Hence, as is easy to check, the product is atomic and rectangularly dense. This establishes the implication from (i) to (ii). The implication from (ii) to (iii) is trivial and the implication from (iii) to (v) is just Lemma 4.8 (see also Corollary 4.3). The implication from (v) to (iv) is obvious and the implication from (iv) to (i) is proved in Theorem 4.7.

Remark 4.11. Theorem 5.4.38 in Henkin-Monk-Tarski [1985] asserts that for finite α ≥ 3 a QPA_{α} is representable iff it is embeddable into an atomic QPA_{α} with rectangular atoms. It follows from the definition of rectangular density that an algebra is atomic and rectangularly dense iff it is atomic and has rectangular atoms. Thus, the equivalence of (i) and (ii) in Corollary 4.10 is essentially an extension of 5.4.38 to the infinite dimensional case. However, the proof of 5.4.38 is based on Theorem 5.4.37 in op. cit., which asserts that every finite dimensional quasi-polyadic algebra has a completion. The proof of the latter theorem is defective since it assumes implicitly that the substitution operations are completely additive. (Thus, it is still unknown whether every QPA_{α} has a completion, even in case when α is finite.) However, it is a consequence of Lemma 4.8 above that

(1) An atomic, rectangularly dense QPA_{α} has a completion.

In the proof of Theorem 5.4.38, instead of referring to 5.4.37, it suffices to refer to (1). The rest of the proof remains unchanged and is very similiar to our proof (except that it refers to Halmos [1962] instead of to Sain-Thompson [1991]).

A stronger theorem than Corollary 4.10 is known in the case α = 2. Theorem 5.4.33 in Henkin-Monk-Tarski [1985] says that every QPA_{2} is representable.

We now give two examples which show that in a quasi-polyadic algebra that is rectangularly dense but not atomic, or that is atomic but not rectangularly dense, the substitutions need not be completely additive.

Example 4.12. To show that the assumption of atomicity in necessary in Lemma 4.8 we construct an example of an (incomplete) atomless, rectangularly dense quasipolyadic set algebra of dimension 2 in which substitutions are not completely additive.

Let 𝔅 be an atomless Boolean set algebra, say with unit U, that has the following separation property:

(1) For any distinct u, v ∈ U there is an X ∈ B such that u ∈ X and v ∈ ∼ X.

(For instance, 𝔅 can be taken to be the Stone representation of some atomless Boolean algebra.) Put

R = {X × Y : X, Y ∈ B}  and  A = { ⋃S : S ⊆ R and |S| < ω} .

Thus, R is a set of rectangles whose sides are subsets of U (and elements of B), and A is the collection of finite unions of these rectangles.

(2)  A is a subuniverse of 𝔔_{2}(U), the full 2-dimensional quasi-polyadic set alge- bra on U.

Obviously A is closed under finite unions. It is also closed under finite intersections. Indeed, R is closed under finite intersections since

(X_{1} × Y_{1}) ∩ (X_{2} × Y_{2}) = (X_{1} ∩ X_{2}) × (Y_{1} ∩ Y_{2}) .

Hence, if S_{1} and S_{2} are finite subsets of R, then

S_{3} = {W ∩ Z : W ∈ S_{1} and Z ∈ S_{2}}

is also a finite subset of R, and we have

(⋃S_{1}) ∩ (⋃S_{2}) = ⋃S_{3}

by the distributive law. To check that A is closed under complementation, observe first of all that the complement of each rectangle from R is in A:

∼ (X × Y) = [∼ X × U] ∪ [U ×∼ Y] .

If S ⊆ R is finite, then

∼ ⋃S = ⋂{∼ Z : Z ∈ S}

by De Morgan’s laws. Since each ∼ Z is in A, by the previous remark, and since A is closed under intersections, we conclude that ∼ ⋃S is in A. Thus, A is closed under the Boolean operations.

To show that A is closed under cylindrifications, substitutions, and permutations, consider first the case of a rectangle X × Y from R. Then, e.g.,

C_{0}(X × Y) = U × Y  ,  C_{1}(X × Y) = X × U ,
S_{01}(X × Y) = U × (X ∩ Y)  ,  S_{10}(X × Y) = (X ∩ Y) × U ,

P_{01}(X × Y) = P_{10}(X × Y) = Y × X ,

i.e., R is closed under cylindrifications, substitutions, and permutations. Since these operations are additive, it follows from the definition of A that A is closed under them as well. This completes the proof of (2).

In view of (2) we can form the subalgebra 𝔄 of 𝔔_{2}(U) with universe A. It is obviously rectangularly dense since its universe consists of unions of rectangles. It remains to show that, e.g., S_{01} is not completely additive.

(3) The only subset of D_{01} in 𝔄 is ∅.

To prove (3) it suffices, by rectangular density, to show that no non-zero rectangle in R is included in D_{01} . Indeed, suppose that X ×Y is a non-empty subset of D_{01} . Then for any u ∈ X and v ∈ Y we have u = v. Thus, X = Y = {u} for some u ∈ U. But then X and Y cannot be in 𝔅 since the latter is atomless and X and Y are atoms.

Set

S = {X×∼ X : X ∈ B} . (4)

Observe that

⋃S = ∼ D_{01} . (5)

Indeed, if (u, v) is in ⋃S, say (u, v) is in X× ∼ X, then u ≠ v. Therefore, ⋃S is a subset of ∼ D_{01} . For the reverse inclusion, suppose that u, v ∈ U are distinct. By the separation property (1) there is an X ∈ B such that (u, v) is in X× ∼ X. Hence, (u, v) is in ⋃S, by (4).

∑^{𝔄}S = U × U . (6)

Certainly U × U is an upper bound for S in 𝔄. Suppose that Z is any other upper bound for S in 𝔄. Then ⋃S ⊆ Z. By (5) this means that ∼ D_{01} ⊆ Z, i.e., ∼ Z ⊆ D_{01} . In view of (3) we see that ∼ Z = ∅, i.e., Z = U × U.

Now using the definition of S_{01} we see that

S_{01}(U × U) = U × (U ∩ U) = U × U .

On the other hand,

S_{01}(X×∼ X) = U × (X∩ ∼ X) = ∅

for each X ∈ B. Thus,

S_{01}(∑^{𝔄}S) = U × U  and  ∑^{𝔄}{S_{01}(Z) : Z ∈ S} = ∅ .

This competes the proof that S_{01} is not completely additive in 𝔄.

It is not difficult to extend the above example to arbitrary dimensions α ≥ 2. We define R to be the set of α-dimensional rectangles

X_{0} × X_{1} × ⋯ × X_{ξ} × …, ξ < α ,

such that X_{ξ} ∈ B for every ξ < α and X_{ξ} = U for all but finitely many ξ. The definition of A remains unchanged. Take the set S in (4) to be the collection of rectangles

X×∼ X × U × U × …

such that X ∈ B.

Example 4.13. To show that the assumption of rectangular density is necessary in Lemma 4.8 we construct an example of a complete, atomic quasi-polyadic set algebra of dimension 2 in which substitutions are not completely additive. A fortiori, the algebra is not rectangularly dense, by Lemma 4.8.

Let U be an infinite set and ⟨Q_{n} : n ∈ ω⟩ a sequence of binary relations on U with the following properties:

(1) ⟨Q_{n} : n ∈ ω⟩ is a partition of U × U,

i.e., the relations are non-empty, pairwise disjoint, and have U × U as their union;

(2) Q_{0} is the identity relation on U,

i.e., Q_{0} = {(x, x) : x ∈ U};

(3) Each Q_{n} has U as its domain and range,

i.e., for every x ∈ U there are y, z ∈ U such that (x, y) and (z, x) are in Q_{n};

(4) Each Q_{n} is symmetric,

i.e., if (x, y) is in Q_{n}, then so is (y, x). (At the end of the example we define a specific sequence of relations with the above properties.)

Fix a non-principal ultrafilter F on the set ω^{+} of positive integers. For each subset X of ω^{+} we define a binary relation R_{X} on U as follows:

R_{X} = \begin{cases}⋃\{Q_{n} : n ∈ X\} & if X ∉ F , \\ ⋃\{Q_{n} : n ∈ X ∪ \{0\}\} & if X ∈ F . \end{cases} (5)

Set

A = {R_{X} : X ⊆ ω^{+}} . (6)

We begin by showing that

(7) A is a subuniverse of 𝔔_{2}(U).

To prove (7), let X, Y be subsets of ω^{+}. If either X or Y is in F, then so is X ∪ Y (since F is a filter). Hence,

R_{X} ∪ R_{Y} = ⋃{Q_{n} : n ∈ X} ∪ ⋃{Q_{n} : n ∈ Y } ∪ Q_{0} = R_{X∪Y} .

If neither X nor Y is in F, then X ∪ Y is also not in F (since F is an ultrafilter). Hence,

R_{X} ∪ R_{Y} = ⋃{Q_{n} : n ∈ X} ∪ ⋃{Q_{n} : n ∈ Y } = R_{X∪Y} .

Thus, A is closed under finite unions.

Now suppose that X is the complement of Y in ω^{+}. Since F is an ultrafilter, exactly one of them, say X, is in F. In view of (5) and (1) we have

∼ R_{X} = ∼ ⋃{Q_{n} : n ∈ X ∪ {0}} = ⋃{Q_{n} : n ∈ Y } = R_{Y} ,

and hence also ∼ R_{Y} = R_{X} . Therefore, A is closed under complementation.

To show closure under cylindrifications and permutations, notice first of all that for i, j < 2 we have C_{i}(Q_{n}) = U × U by (3), and P_{ij}(Q_{n}) = Q_{n} by (4). Because cylindrifications and permutations in 𝔔_{2}(U) are completely additive, it follows that

C_{i}(R_{X}) = \begin{cases}U × U & if X ≠ ∅ , \\ ∅ & if X = ∅ , \end{cases}

and that each permutation is the identity operation on A.

Turning to the non-trivial substitutions, we have

S_{01}(R_{X}) = C_{0}(Q_{0} ∩ ⋃{Q_{n} : n ∈ X}) = C_{0}(∅) = ∅ if X ∉ F (8)

and

S_{01}(R_{X}) = C_{0}(Q_{0} ∩ ⋃{Q_{n} : n ∈ X ∪ {0}}) = C_{0}(Q_{0}) = U × U if X ∈ F ,

by definition of S_{01} , (1), and (2). Similarly,

S_{10}(R_{X}) = \begin{cases}∅ & if X ∉ F , \\ U × U & if X ∈ F . \end{cases}

This completes the proof of (7).

Let 𝔄 be the subalgebra of 𝔔_{2}(U) with universe A. Then 𝔄 is a quasi-polyadic set algebra of dimension 2. Moreover, it is atomic and its atoms are just the elements

R_{{n}} = Q_{n} for n ∈ ω^{+} ;

to show this, one makes use of the assumption that F is non-principal, i.e.,

{n} ∉ F for n ∈ ω^{+} . (9)

Finally, 𝔄 is complete . To prove this, notice that by (6) and (7) an arbitrary sum in 𝔄 is the supremum of a set

{R_{X_{ξ}} : ξ ∈ Ξ} , (10)

where ⟨X_{ξ} : ξ ∈ Ξ ⟩ is a sequence of subsets of ω^{+}. Put X = ⋃{X_{ξ} : ξ ∈ Ξ}. It suffices to show that

R_{X} = ∑{R_{X_{ξ}} : ξ ∈ Ξ} . (11)

It is clear from (5) that R_{X} is an upper bound for the set (10). From (5)–(7) we see that any upper bound for (10) must have the form R_{Y}, where R_{X_{ξ}} ⊆ R_{Y} and hence X_{ξ} ⊆ Y for each ξ ∈ Ξ . It follows that X ⊆ Y by definition of X. In particular, if X ∈ F, then Y ∈ F (since F is a filter). Therefore we have R_{X} ⊆ R_{Y} , by (5). This proves (11).

Applying the preceding reasoning to the sequence ⟨R_{{n}} : n ∈ ω^{+} ⟩, we see that

∑{R_{{n}} : n ∈ ω^{+}} = R_{ω^{+}} = ⋃{Q_{n} : n ∈ ω} = U × U .

Now

∑{S_{01}(R_{{n}}) : n ∈ ω^{+}} = ∑{∅ : n ∈ ω^{+}} = ∅ ,

by (8) and (9). On the other hand,

S_{01}(U × U) = U × U .

Therefore

S_{01}(∑{R_{{n}} : n ∈ ω^{+}}) ≠ ∑{S_{01}(R_{{n}}) : n ∈ ω^{+}} .

This shows that S_{01} is not completely additive.

To complete the example, we must define a set U and a sequence ⟨Q_{n} : n ∈ ω⟩ of binary relations on U with properties (1)–(4). For simplicity take U to be the set of integers and let P be the predecessor function. For n ∈ ω^{+} take Q_{n} to be the union of P^{n}—the composition of P with itself n times—and the inverse of P^{n}, and take Q_{0} to be the identity function on U.

With the help of the methods used to prove Theorem 4.7 it is possible to establish other, related representation theorems. We give an example using the substitutioncylindrification algebras that were first introduced in Pinter [1973] under the name of quantifier algebras.

Definition 4.14. A substitution-cylindrification algebra of dimension α is an algebra

𝔄 = ⟨A , + , − , c_{i} , s_{ij} ⟩_{i,j∈α}

such that ⟨A , + , −⟩ is a Boolean algebra , the operations c_{i} and s_{ij} are unary, and postulates (Q1), (Q4)–(Q10), and

s_{ij}s_{ki}(x) = s_{ij}s_{kj}(x) for all i, j, k < α

are valid in 𝔄 when α ≥ 3; when α ≤ 2 we require in addition that (Q16) and (Q17) are valid in 𝔄. A substitution-cylindrification equality algebra of dimension α is an algebra

𝔄 = ⟨A , + , − , c_{i} , s_{ij} , d_{ij} ⟩_{i,j∈α}

such that the reduct

𝔄 = ⟨A , + , − , c_{i} , s_{ij} ⟩_{i,j∈α}

is a substitution-cylindrification algebra and the d_{ij} are constants satisfying the additional postulates (Q18) and (Q19). The classes of all substitution-cylindrification algebras and all substitution-cylindrification equality algebras of dimension α are denoted by SCA_{α} and SCEA_{α} respectively. We also use these notations as abbreviations for the phrases “substitution-cylindrification algebra of dimension α” and “substitution-cylindrification equality algebra of dimension α” respectively.

The notions of a full substitution cylindrification set algebra (with or without equality), a representable substitution cylindrification algebra, a rectangularly dense substitution cylindrification algebra, and the cylindric reduct of a substitution cylindrification algebra are the obvious analogues of the quasi-polyadic notions. The classes RSCA_{α} and RSCEA_{α} of all representable SCA_{α} and SCEA_{α} are varieties. Also, for β < α, every equation in the language of SCA_{β} (or SCEA_{β}) that holds in RSCA_{α} (or RSCEA_{α}) must hold in RSCA_{β} (or RSCEA_{β}). (See the analogous remarks concerning QPA_{α} and QPEA_{α}.) The next two lemmas are intended to clarify the relationship between cylindric algebras and substitution cylindrification algebras. The first of them is due to Pinter [1973], p. 366.

Lemma 4.15. The class SCEA_{α} is a term definitional extension of CA_{α}.

Proof: Let 𝔄 be in SCEA_{α} and 𝔅 its cylindric reduct. Then 𝔅 is in CA_{α} and each substitution s_{ij} of 𝔄 can be defined by the formula

s_{ij}(x) = \begin{cases}x & if i = j, \\ c_{i}(d_{ij} · x) & if i ≠ j. \end{cases}

Conversely, if 𝔄 is in CA_{α} and we define s_{ij} as above, then ⟨𝔄 , s_{ij}⟩_{i,j<α} is in SCEA_{α}. Indeed, the postulates for SCEA_{α} are all valid in CA_{α} under the given definition of substitution, by Henkin-Monk-Tarski [1971], Section 1.5.

Lemma 4.16. Every SCA_{α} is a subreduct of a CA_{α} (more precisely, a subreduct of the definitional extension of a CA_{α} to a SCEA_{α}).

Proof: The proof is very similar to the proof of Theorem 4.7. Let 𝔄 be a SCA_{α} and 𝔅 its perfect extension in the sense of Jónsson-Tarski [1951]. From the definition of a perfect extension we know, in particular, that 𝔅 is a complete, atomic BAO and that 𝔄 is a subalgebra of 𝔅. The proof we gave to show that the completion of a QPA_{α} is again a QPA_{α} carries over to the case of the perfect extension of a SCA_{α} and shows that

(1) 𝔅 is a SCA_{α}.

Also, the proof that the completion of a QPA_{α} has a definitional extension which is a QPEA_{α} carries over to show that

(2) 𝔅 has a definitional extension which is a SCEA_{α}.

The key point to observe in carrying over this proof to (2) is that substitutions are completely additive in a perfect extension (as opposed to the situation in a completion, where they need not be completely additive). This is a consequence of the additivity of substitutions (see (Q9)) and the fact that the canonical extension of an additive operation (in a perfect extension) is completely additive (see Jónsson-Tarski [1951], Theorem 2.4). To carry over the proof to (2) one must also check that (viii) and the first part of (i) in 4.2 hold in SCA_{α}, and this is easy.

Let ℭ be the definitional extension of 𝔅 to a SCEA_{α} that is guaranteed by (2). By the previous lemma, ℭ is a term definitional extension of a CA_{α} 𝔇. Thus, 𝔄 is a subalgebra of 𝔅, which is a reduct of ℭ, which is a definitional extension of 𝔇. This proves the assertion of the lemma.

Corollary 4.17. An equation in the language of SCA_{α} is true of SCA_{α} iff it is true of CA_{α} (with substitutions defined as usual ).

Proof: Suppose that ε is an equation in the language of SCA_{α}. Assume first that ε is valid in SCA_{α}. Let 𝔄 be any CA_{α}, 𝔅 the definitional extension of 𝔄 to a SCEA_{α} guaranteed by Lemma 4.15, and ℭ the reduct of 𝔅 to a SCA_{α}. Then ε holds in ℭ by assumption and therefore also in 𝔄 (more precisely, in 𝔅).

Now assume that ε is valid in CA_{α}. Let ℭ be an arbitrary SCA_{α}, 𝔅 the definitional extension to a SCEA_{α} of the perfect extension of ℭ, and 𝔄 the reduct of 𝔅 to CA_{α}. Then ε holds in 𝔄 (more precisely, in 𝔅) by assumption. Therefore it must hold in the subreduct ℭ.

Thus, when we wish to use a law that is valid in SCA_{α} we may refer to the corresponding law for CA_{α}.

Theorem 4.18. Let α ≥ 2.

(i) Every α-dimensional rectangularly dense substitution cylindrification algebra with equality is representable.

(ii) Every α-dimensional rectangularly dense substitution cylindrification algebra without equality that has completely additive substitutions is representable.

Proof: We sketch the proof. First, suppose that 𝔄 is a SCEA_{α}, and let 𝔅 be its cylindric reduct. Then 𝔅 is a cylindric algebra and 𝔄 is a term definitional extension of 𝔅, by Lemma 4.15. Assume that 𝔄 is rectangularly dense. Then certainly 𝔅 is rectangularly dense and hence representable by Theorem 3.11. The representation must preserve term-definable operations, so we also have a representation of 𝔄.

Now suppose that 𝔄 is a SCA_{α} in which the substitutions are completely additive. Then by the results of Monk [1970] 𝔄 has a completion 𝔅. One readily checks that 𝔅 is also a SCA_{α}. Also, just as in the case of quasi-polyadic algebras (see the proof of Theorem 4.7), one can show that 𝔅 is the reduct of a SCEA_{α}, ℭ. Assuming the rectangular density of 𝔄, we easily check that 𝔅 and ℭ inherit this rectangular density. By the results of the preceding paragraph, ℭ is representable. This gives us a representation of 𝔅 and hence also of 𝔄.

The laws in Lemma 4.2(i)–(xi),(xx) are valid in CA_{α}, by the results of Sections 1.2 and 1.5 in Henkin-Monk-Tarski [1971] (see, in particular, Theorems 1.5.8 and 1.5.9). Hence, they are valid in SCA_{α}, by Corollary 4.17. Therefore, the proof that substitutions are completely additive in a quasi-atomic, rectangularly dense QPA_{α} carries over without change to the case of SCA_{α}.

Lemma 4.19. Let 𝔄 be a quasi-atomic, rectangularly dense SCA_{α}. Then each substitution is completely additive.

Consequently, we arrive at the following characterization of representability in SCA_{α}.

Corollary 4.20. Let 𝔄 be a SCA_{α}, where α ≥ 2. Then the following are equivalent :

(i) 𝔄 is representable ;

(ii) 𝔄 is embeddable in an atomic, rectangularly dense SCA_{α};

(iii) 𝔄 is embeddable in a quasi-atomic, rectangularly dense SCA_{α}; (iv) 𝔄 is embeddable in a rectangularly dense, completely additive SCA_{α}.

Problem 4.21. Can the hypothesis of the complete additivity of s_{01} in Theorem 4.7 and of the complete additivity of all the (non-trivial) substitutions in Theorem 4.18 be dropped? That is to say, is every rectangularly dense QPA_{α} or SCA_{α} representable?^{8}

Problem 4.22. Does every QPA_{α} and every SCA_{α} have a completion?

Notice that a positive solution to the second problem would give a positive solution to the first problem as well.

5. Rich cylindric and quasi-polyadic algebras

In Henkin-Monk-Tarski [1985] the concept of an i-thin element is introduced, and with its help the notions of a rich cylindric algebra and a rich quasi-polyadic equality algebra are defined (see pp. 60, 242, and in particular, Definition 3.2.1). It is shown in Theorems 3.2.13 and 5.4.34 that a cylindric algebra or a quasi-polyadic equality algebra of finite dimension α ≥ 2 is representable iff it is embeddable into a rich cylindric algebra or quasi-polyadic equality algebra (of the same dimension) in which the so-called Henkin equations are universally valid. (For quasi-polyadic equality algebras the theorem is only formulated for α ≥ 3, but the proof goes through for the case α = 2 as well.) The proof is an algebraic version of the proof of the Completeness Theorem for first-order logic (see op. cit., pp. 59–64). The authors then ask in Problem 5.6 whether this result can be extended to quasipolyadic algebras (without equality). (Actually, they refer to polyadic algebras instead of quasi-polyadic algebras, but recall that for finite dimensions the two notions coincide.) Since the concept of an i-thin element is defined with the help of diagonal elements, part of the problem consists in finding an appropriate definition of i-thinness when diagonal elements are not available.

We shall introduce a form of the definition of an i-thin element and of a rich algebra that does not depend on the presence of diagonal elements, but only on cylindrifications. Therefore, it can be applied to any of the classes of algebras studied in Sections 3 and 4. From this definition it will be seen that richness can be viewed as a density notion, similar in spirit to rectangular density. We shall then give two distinct characterizations of richness, one in terms of rectangular density and the other in terms of point density. As a consequence of these characterizations, we shall show that (for the classes studied in Sections 3 and 4) a rich algebra of finite (or locally finite) dimension is representable. Thus, we will obtain a form of the Henkin-Tarski representation theorem that does not require the presence of the Henkin equations. We will also obtain a positive solution to Problem 5.6. Finally, we shall discuss the relationship of our notions of thinness and richness to those in op. cit., and we shall give some historic remarks.

Recall that the dimension set of an element x is the set

Δx = {i < α : c_{i}(x) ≠ x} .

8Quite recently, Andréka, Givant, and Németi have obtained a positive solution to this problem.

The case α < ω requires a new argument; the case α ≥ ω follows from the case α < ω by the argument in the second paragraph of the proof of Theorem 3.11.

Recall also that an algebra is said to be locally finite dimensional if Δx is finite for each element x of the algebra. Observe that a finite dimensional algebra is always locally finite dimensional.

In what follows, assume that 𝔄 is a CA_{α}, a QPEA_{α}, a QPA_{α}, or an SCA_{α}. (We ignore SCEA_{α} because this is just a definitional extension of CA_{α}.) When establishing abstract properties of 𝔄 we shall need to refer to various laws concerning cylindrifications and substitutions that are valid not only in CA_{α}, but also in QPA_{α}, QPEA_{α}, and SCA_{α}. Among these laws are postulates (Q1) and (Q4)–(Q10), and Lemma 4.2(ii)–(xi) and the first part of (i).

Definition 5.1. Let x be an element of 𝔄 and suppose that i < α. Then x is i-thin if

(i) c_{j}(x) = x for all j < α with j ≠ i, i.e., Δx ⊆ {i}, (ii) x · c_{i}(x · y) ≤ y for every y in 𝔄.

Thin elements play the role in algebraic logic that individual constants play in model theory and, in particular, in Henkin’s proof of the Completeness Theorem for first-order logic; see op. cit., pp. 59–63. If we think of x as representing a formula, then condition (i) asserts that x has at most one free variable and condition (ii) says that for every formula y, if there is an element satisfying both x and y (with a given set of parameters for the other variables of y), then every element satisfying x must satisfy y (with the given parameters). In other words, no formula can distinguish the elements that satisfy x from one another. The Leibniz law asserts that two things are equal iff they are indistinguishable from one another. From this point of view a thin element corresponds to a formula that is satisfied by at most one element.

The next lemma sheds some light on the set-theoretic intuition behind the definition of thin elements.

Lemma 5.2. Let i < α < ω and suppose that 𝔄 is the full set algebra on a nonempty set U. Then an element X of 𝔄 is i-thin iff X = ∅ or there is a u ∈ U such that

X = {x ∈ ^{α}U : x_{i} = u} . (i)

Proof: The empty set obviously satisfies the conditions of Definition 5.1. Suppose, now, that for a fixed u ∈ U the set X has the form (i). It is easy to verify condition 5.1(i), so we concentrate on (ii). First some notation: for a sequence x ∈ ^{α}U and an element u ∈ U, let x[i\u] denote the sequence obtained from x by replacing the i^{th} coordinate x_{i} with u. Now let Y be an arbitrary subset of ^{α}U. Using the definitions of X and of set-theoretic cylindrification, we have

X ∩ Y = {x ∈ Y : x_{i} = u} and C_{i}(X ∩ Y) = {x ∈ ^{α}U : x[i\u] ∈ Y } ,

so

X ∩ C_{i}(X ∩ Y) = {x ∈ C_{i}(X ∩ Y) : x_{i} = u}
= {x ∈ ^{α}U : x_{i} = u and x ∈ Y }
= X ∩ Y .

Thus, condition 5.1(ii) is satisfied.

Now suppose that X is an i-thin element in 𝔄. From condition 5.1(i) we see that X must have the form

X = {x ∈ ^{α}U : x_{i} ∈ Z}

for some set Z ⊆ U. (Here we are using the assumption that α is finite.) If Z is empty, then clearly so is X. Suppose that Z is not empty. Fix an element u ∈ Z and put

Y = {x ∈ ^{α}U : x_{i} = u} .

Then

C_{i}(Y) = ^{α}U and X ∩ Y = Y . (1)

Using (1) and the assumption that X satisfies condition (ii), we obtain X ⊆ Y. The reverse inclusion follows from the second equation in (1). Thus, X has the form (i).

From the preceding lemma we see that in an α-dimensional space (with α finite), i-thin elements are either empty or have dimension α − 1. Thus, from the point of view of dimension they are thin (or flat) in comparison with elements of dimension α, much as lines are thin in a two dimensional world and planes are thin in a three dimensional world. It is from this geometric perspective that the name “i-thin” derives. (See Figures 3 and 4.)

Figure 3. 0-thin and 1-thin elements in two dimensions.

Thin elements are not quite quasi-atoms, but in the set of elements with dimension set included in {i} they are quasi-atoms. The next lemma expresses this fact.

Figure 4. A 2-thin element in three dimensions.

Lemma 5.3. Suppose that 𝔄 has finite dimension α ≥ 1 and that x is an i-thin element. If w ≤ x and Δw ⊆ {i}, then w is i-thin and in fact w = x · c_{(α)}(w). Thus, x is a quasi-atom in the set {y : Δy ⊆ {i}}.

Proof: Suppose that w and x satisfy the hypotheses of the lemma. Then

x · c_{(α)}(w) = x · c_{i}(w)  since Δw ⊆ {i},
= x · c_{i}(x · w)  since w ≤ x,
≤ w  since x is i-thin,
≤ x · c_{(α)}(w)  by (Q4) and w ≤ x.

This shows that w = x · c_{(α)}(w). To check condition 5.1(ii), suppose that y is an arbitrary element. Then

w · c_{i}(w · y) ≤ x · c_{i}(x · y) ≤ y

by monotony and the i-thinness of x.

We remark in passing that not all quasi-atoms in the set {y : Δ ⊆ {i}} need be i-thin. For example, in the algebra 𝔅 from Example 5.23 below, the element ^{α}U is a quasi-atom in the set

{y : Δy ⊆ {i}} = {∅,^{α}U} ,

but it is not i-thin.

The following definition is a modification of Definition 3.2.1(ii) in Henkin-Monk-Tarski [1985], and is based on our notion (as opposed to their notion) of 0-thinness.

Definition 5.4. Suppose that 𝔄 has dimension α ≥ 1. Then 𝔄 is rich if, for every non-zero y with Δy ⊆ {0}, there is a non-zero 0-thin x below y.

Full set algebras are natural examples of rich algebras.

Lemma 5.5. If 𝔄 is a full set algebra of finite dimension α ≥ 1, then 𝔄 is rich.

Proof: Let Y be a non-zero element of 𝔄 such that C_{j}(Y) = Y for every non-zero j < α. Then there is a non-empty set Z ⊆ U such that Y has the form

Y = {x ∈ ^{α}U : x_{0} ∈ Z} . (1)

Choose any u ∈ Z and set

X = {x ∈ ^{α}U : x_{0} = u} .

Then X is a 0-thin element of 𝔄 by Lemma 5.2, and X ⊆ Y by (1). Thus, 𝔄 is rich.

Remark 5.6. Let ψ(x) be the conjunction of the equations that together express the assertion Δx ⊆ {0}, let ϑ(x) be the formula

∀y[x · c_{0}(x · y) ≤ y] ,

and let φ be the conjunction of ψ and ϑ. Thus, φ is a positive formula expressing the notion of 0-thinness. It is clear that richness coincides with the notion of φ-density in ψ. Let’s verify that ψ satisfies the three conditions of Theorem 2.15. Since ψ is positive, it is preserved under homomorphisms. To check strict preservation, let f map 𝔄 homomorphically onto 𝔅 and suppose that y is in ψ^{𝔅}, i.e., Δy ⊆ {0}. Let z be an element in 𝔄 such that f(z) = y, and set x = c_{(α∼{0})}(z). Then x is obviously in ψ^{𝔄}. Further,

f(x) = f(c_{(α∼{0})}(z)) = c_{(α∼{0})}(f(z)) = c_{(α∼{0})}(y) = y ,

since Δy ⊆ {0}. This verifies condition (i) in 2.15. To verify (ii) suppose that y ∈ ψ^{𝔄} and x ∈ A. For each i with 0 < i < α we have

c_{i}(y · c_{(α)}(x)) = c_{i}(y) · c_{(α)}(x) = y · c_{(α)}(x)

by 4.2(v) and the assumpution Δy ⊆ {0}. This shows that the element y · c_{(α)}(x) is in ψ^{𝔄}. To verify condition (iii) let x ∈ A and set y = c_{(α∼{0})}(x). Then y is in ψ^{𝔄} and

c_{(α)}(y) = c_{(α)}c_{(α∼{0})}(x) = c_{(α)}(x) .

The term “rich” was probably employed by Henkin and Tarski to express that an algebra possesses a sufficient number of elements acting like constants (much as a first-order theory is sometimes called “rich” if it possesses a sufficient number of constants acting as witnesses to existential assertions).^{9} But from our perspective a better terminology might be 0-thin density (in the set of elements with dimension set included in {0}). It is natural to ask whether 0-thin density implies i-thin density for each i < α. Our first task (which is accomplished in Corollary 5.9) is to prove that this is indeed the case.

Lemma 5.7. Suppose that 𝔄 is rich and has finite dimension α ≥ 1 . Then every element whose dimension set is included in {0} is the sum of the 0-thin elements below it.

Proof: Let y be any element such that Δy ⊆ {0}, and set

X = {x : x is 0-thin and x ≤ y} .

Clearly y is an upper bound for X.

Suppose that z is an element such that y · −z ≠ 0. Then

0 ≠ c_{(α∼{0})}(y · −z) = y · c_{(α∼{0})}(−z) ,

by 4.2(v) and Δy ⊆ {0}. Because 𝔄 is rich there is a non-zero 0-thin element w ≤ y · c_{(α∼{0})}(−z). Since w ≤ y, we have w ∈ X. Since 0 < w ≤ c_{(α∼{0})}(−z), we have

0 ≠ w · c_{(α∼{0})}(−z)  by BA,
0 ≠ −z · c_{(α∼{0})}(w)  by 4.2(vi),
0 ≠ −z · w  since Δw ⊆ {0}.

Because w ∈ X and w ≰ z, the element z cannot be an upper bound for X. Thus, if z is any upper bound for X, then y · −z = 0 and therefore y ≤ z.

Lemma 5.8. Suppose that 𝔄 is rich and of finite dimension α ≥ 1. If x is a 0-thin element in 𝔄, then s_{0i}(x) is i-thin.

Proof: When i = 0 we have s_{0i}(x) = x, so the lemma is trivial. Suppose that 0 ≠ i. We verify the two conditions of i-thinness. For k ∈ α − {0, i} we have

c_{k}s_{0i}(x) = s_{0i}c_{k}(x) = s_{0i}(x)

by (Q8) and Δx ⊆ {0}. Also,

c_{0}s_{0i}(x) = s_{0i}(x)

by (Q7). This verifies condition 5.1(i).

Before verifying condition 5.1(ii) we make some preliminary observations.

(1) If y ≤ s_{0i}(x) , then s_{i0}c_{0}(y) ≤ x.

9The approach of Halmos [1962], p. 143, to constants is not via elements of the algebra — in our case, thin elements — but via systems of Boolean endomorphisms. His definition of a “rich”

(polyadic) algebra is based on his notion of a constant (see op. cit., p. 157).

NOTIONS OF DENSITY THAT IMPLY REPRESENTABILITY 55

Indeed, suppose that y ≤ s_{0i}(x) . Then c_{0}(y) ≤ c_{0}s_{0i}(x) = s_{0i}(x) (2) by 4.2(ii) and (Q7). Hence,

s_{i0}c_{0}(y) ≤ s_{i0}s_{0i}(x) by 4.2(i),
= s_{i0}(x)  by 4.2(ix),
= x

by 4.2(xx), since Δx ⊆ {0}.

This proves (1).

(3) If y ≤ s_{0i}(x) , then s_{0i}(x) · c_{0}c_{i}(y) = c_{0}(y) . For the proof, suppose that y ≤ s_{0i}(x). Then

c_{0}(y) ≤ s_{0i}(x) · c_{0}c_{i}(y)

by (2), (Q4), and 4.2(ii). For the reverse inequality we have

x · c_{0}c_{i}(y) = x · c_{i}c_{0}(y)  by 4.2(vii),
= x · c_{i}s_{0i}c_{0}(y)  by (Q6),
= x · c_{0}s_{i0}c_{0}(y)  by 4.2(xi),
= x · c_{0}(x · s_{i0}c_{0}(y))  by (1),
≤ s_{i0}c_{0}(y)  since x is 0-thin.

Applying s_{0i} to both sides yields

s_{0i}(x · c_{0}c_{i}(y)) ≤ s_{0i}s_{i0}c_{0}(y)  by 4.2(i),
s_{0i}(x) · s_{0i}c_{0}c_{i}(y) ≤ s_{0i}c_{0}(y)  by 4.2(i),(ix),
s_{0i}(x) · c_{0}c_{i}(y) ≤ c_{0}(y)  by (Q6).

This proves (3).

To verify condition 5.1(ii) let y be an arbitrary element of 𝔄 and set z = s_{0i}(x) · c_{i}(s_{0i}(x) · y) . (4) We must show that z ≤ y.

(5) If w is 0-thin, then w · z ≤ y. Indeed,

w · z = w · s_{0i}(x) · w · c_{i}(s_{0i}(x) · y)  by (4) and BA,
= w · s_{0i}(x) · c_{i}(w · s_{0i}(x) · y)  since Δw ⊆ {0} and i ≠ 0,
≤ w · s_{0i}(x) · c_{0}c_{i}(w · s_{0i}(x) · y)  by (Q4),
= w · c_{0}(w · s_{0i}(x) · y)  by (3) with “w · s_{0i}(x) · y” for “y”,
≤ s_{0i}(x) · y  since w is 0-thin,
≤ y  by BA.

Figure 5. A 0-thin element x and its s_{01} substitution.

Now let X be the set of 0-thin elements below c_{(α∼{0})}(z). Then c_{(α∼{0})}(z) = ∑X (6) by the richness of 𝔄 and the preceding lemma. Hence,

z = z · c_{(α∼{0})}(z)  by (Q4),
= z · ∑X  by (6),
= ∑{z · w : w ∈ X}  by BA,
≤ y  by (5).

Corollary 5.9. Suppose that 𝔄 is rich and has finite dimension α ≥ 1. Then for every non-zero y with Δy ⊆ {i} there is a non-zero i-thin x below y. Proof: If i = 0, then this follows at once from the definition of richness. Suppose that i ≠ 0. Then s_{0i}(y) = y (1) by 4.2(xx) and the assumptions Δy ⊆ {i} and i ≠ 0. Now

c_{k}s_{i0}(y) = s_{i0}c_{k}(y) = s_{i0}(y) for k ≠ 0, i ,

by (Q8) and Δy ⊆ {i}, and

c_{i}s_{i0}(y) = s_{i0}(y)

by (Q7). In other words, Δs_{i0}(y) ⊆ {0}. Hence, using the assumption that 𝔄 is rich, we can find a non-zero 0-thin element x ≤ s_{i0}(y). Applying s_{0i} to both sides, we obtain

s_{0i}(x) ≤ s_{0i}s_{i0}(y) 4.2(i),
s_{0i}(x) ≤ s_{0i}(y)  by 4.2(ix),
s_{0i}(x) ≤ y  by (1).

The element s_{0i}(x) is i-thin by Lemma 5.8. Further, s_{0i}(x) ≠ 0 since

0 ≠ x = s_{i0}(x) = s_{i0}s_{0i}(x)

by Δx ⊆ {0} and 4.2(ix),(xx). Therefore, the conclusion of the lemma is satisfied by s_{0i}(x) (in place of x).

The notion of a point in relation algebras occurs implicitly in Theorem 4.30 of Jónsson-Tarski [1952] and was studied by several subsequent researchers (see, for example, Maddux [1991]^{10}). We now introduce a notion of a point that is appropriate for finite dimensional algebras with cylindrification operations.

Definition 5.10. Suppose that 𝔄 is of finite dimension α ≥ 1. An element x is a point if c_{(α∼{i})}(x) is i-thin for each i < α.

Lemma 5.11. Suppose 𝔄 has finite dimension α ≥ 1. Then every point is a rectangle.

Proof: Assume that x is a point. Then

(1) c_{(α∼{i})}(x) is i-thin for each i < α,

by definition. From (Q4) we see that

(2) c_{(Δ)}(x) ≤ c_{(α∼{i})}(x) for Δ ⊆ α − {i}.

Using 4.2(vii), (2), and (1), we obtain

(3) c_{(α∼{i})}(x) · c_{(Δ∪{i})}(x) ≤ c_{(Δ)}(x) for Δ ⊆ α − {i}

as follows:

c_{(α∼{i})}(x) · c_{(Δ∪{i})}(x) = c_{(α∼{i})}(x) · c_{i}c_{(Δ)}(x)
= c_{(α∼{i})}(x) · c_{i}[c_{(α∼{i})}(x) · c_{(Δ)}(x)]
≤ c_{(Δ)}(x) .

10In Maddux’s work a narrower notion of a point is adopted, one that corresponds to points lying below the main diagonal, i.e., below the identity element. (One might call these diagonal points or subidentity points.) However, the more general notion of a point is implicit in his Theorems 40 and 41.

We now apply (3) α times, starting with Δ = α ∼ {0, 1} and i = 1, then taking Δ = α ∼ {0, 1, 2} and i = 2, and so on, to get

∏_{i<α}c_{(α∼{i})}(x) ≤ ∏_{1≤i<α}c_{(α∼{i})}(x) · c_{(α∼{0,1})}(x)
≤ ∏_{2≤i<α}c_{(α∼{i})}(x) · c_{(α∼{0,1,2})}(x)
≤ …
≤ c_{(α∼α)}(x)
= x .

Thus,

∏_{i<α}c_{(α∼{i})}(x) ≤ x .

The reverse inclusion follows from (Q4). Hence, x is a rectangle by Lemma 3.7. (See Figure 6.)

Figure 6. A point x is a rectangle: it is the intersection of the 0-thin element c_{12}(x), the 1-thin element c_{02}(x), and the 2-thin element c_{01}(x).

The terminology “point” derives from the fact that in a full set algebra an element is a point iff it is empty or a singleton:

Lemma 5.12. Suppose 𝔄 is the full set algebra of finite dimension α ≥ 1 on a set U. Then an element X in 𝔄 is a point iff X = ∅ or there are u_{0}, …, u_{α−1} in U such that X = {(u_{0}, …, u_{α−1})}.

Proof: Suppose X is a non-empty point in 𝔄. Then C_{(α∼{i})}(X) is non-empty and i-thin by definition. By Lemma 5.2 there is an element u_{i} in U such that

C_{(α∼{i})}(X) = {w ∈ ^{α}U : w_{i} = u_{i}} . (1)

Therefore,

X = ⋂_{i<α}C_{(α∼{i})}(X)  by 5.11,
= ⋂_{i<α}{w ∈ ^{α}U : w_{i} = u_{i}}  by (1),
= {(u_{0}, …, u_{α−1})} .

For the converse, it is easy to check that the empty set is a point. Suppose that X = {(u_{0}, …, u_{α−1})}. Then

C_{(α∼{i})}(X) = {w ∈ ^{α}U : w_{i} = u_{i}}

by definition of set cylindrification, and this element is i-thin by Lemma 5.2. Therefore X is a point.

In analogy with Lemma 3.7 we have the following characterization of points.

Lemma 5.13. An element x is a point iff there exist elements y_{0}, …, y_{α−1} such that y_{i} is i-thin for each i < α and x = ∏_{i<α}y_{i}.

Proof: If x is a point, then set y_{i} = c_{(α∼{i})}(x). By Definition 5.10 the element y_{i} is i-thin and by Lemma 5.11 we have x = ∏_{i<α}y_{i}.

For the reverse implication, suppose that y_{i} is i-thin and that x = ∏_{i<α}y_{i}. Then

c_{(α∼{i})}(x) ≤ c_{(α∼{i})}(y_{i}) = y_{i} ,

since Δy_{i} ⊆ {i}. Hence, c_{(α∼{i})}(x) is i-thin for each i, by Lemma 5.3. By Definition 5.10, x is a point.

The next two lemmas elucidate the relationship between points and quasi-atoms.

Lemma 5.14. Suppose that 𝔄 has finite dimension α ≥ 1. Then every point is a quasi-atom and every element below a point is again a point. In particular, if 𝔄 is simple, then every non-zero point is an atom.

Proof: Suppose

(1) x is a point.

Let y ≤ x. Then c_{(α∼{i})}(y) ≤ c_{(α∼{i})}(x) for each i < α. Therefore, by Lemma 5.3 c_{(α∼{i})}(y) is i-thin for each i < α. Hence,

(2) y is a point.

By the same lemma, c_{(α∼{i})}(x) is a quasi-atom in the set of elements with dimension set included in {i}. Therefore

c_{(α∼{i})}(y) = c_{(α∼{i})}(x) · c_{(α)}(y) . (3)

Hence,

y = ∏_{i<α}c_{(α∼{i})}(y)  by (2) and 5.11,
= ∏_{i<α}c_{(α∼{i})}(x) · c_{(α)}(y)  by (3),
= x · c_{(α)}(y)  by (1) and 5.11.

It follows that x is a quasi-atom. The final assertion of the lemma follows from Lemma 2.17(ii).

A kind of converse to the preceding lemma is also true.

Lemma 5.15. Suppose 𝔄 has finite dimension α ≥ 1. If 𝔄 is rectangularly dense, then every quasi-atom x is a point.

Proof: Assume that 𝔄 is rectangularly dense. Let x be a quasi-atom and fix an i < α. We must show that c_{(α∼{i})}(x) is i-thin. It clearly suffices to show that for any given y we have

c_{(α∼{i})}(x) · c_{i}(c_{(α∼{i})}(x) · y) ≤ y . (1)

Suppose that z is a non-zero rectangle below c_{(α∼{i})}(x) · c_{i}(c_{(α∼{i})}(x) · y).

c_{(α∼{i})}(z) = c_{(α∼{i})}(x) · c_{(α)}(z) . (2)

To see this, notice that

c_{(α∼{i})}(z) ≤ c_{(α∼{i})}(x) (3)

by 4.2(ii),(iii),(vii), and the assumption that z ≤ c_{(α∼{i})}(x) . Because x is a quasiatom, we get

x · c_{(α∼{i})}(z) = x · c_{(α)}(x · c_{(α∼{i})}(z))  by 2.17(i),
= x · c_{i}c_{(α∼{i})}(x · c_{(α∼{i})}(z))  by 4.2(vii),
= x · c_{i}(c_{(α∼{i})}(x) · c_{(α∼{i})}(z))  by 4.2(v),
= x · c_{i}(c_{(α∼{i})}(z))  by (3),
= x · c_{(α)}(z)  by 4.2(vii).

Applying c_{(α∼{i})} to both sides, we see from 4.2(v) that

c_{(α∼{i})}(x) · c_{(α∼{i})}(z) = c_{(α∼{i})}(x) · c_{(α)}(z) .

In view of (3), this gives us (2).

z · y ≠ 0 . (4)

Indeed,

0 < z ≤ c_{i}(c_{(α∼{i})}(x) · y) and z ≤ c_{(α)}(z)

by assumption and (Q4), so

0 < z
≤ c_{i}(c_{(α∼{i})}(x) · y) · c_{(α)}(z)  by BA,
= c_{i}(c_{(α∼{i})}(x) · c_{(α)}(z) · y)  by 4.2(v),
= c_{i}(c_{(α∼{i})}(z) · y)  by (2).

Therefore,

z · c_{i}(c_{(α∼{i})}(z) · y) ≠ 0  by BA,
c_{i}(z) · c_{(α∼{i})}(z) · y ≠ 0  by 4.2(vi),
z · y ≠ 0  since z is a rectangle.

This proves (4).

We have shown that for any non-zero rectangle z below

c_{(α∼{i})}(x) · c_{i}(c_{(α∼{i})}(x) · y)

we have z · y ≠ 0. Hence, for such a z we cannot have z ≤ −y. In other words there can be no non-zero rectangles below

c_{(α∼{i})}(x) · c_{i}(c_{(α∼{i})}(x) · y) · −y . (5)

Since 𝔄 is assumed to be rectangularly dense, that means that (5) is 0. Assertion (1) is proved.

Definition 5.16. Suppose 𝔄 has finite dimension α ≥ 1.

(i) 𝔄 is point dense iff every non-zero element is above a non-zero point. (ii) 𝔄 is diagonally point dense if every non-zero subdiagonal element is above

a non-zero point.

Remark 5.17. If we take φ to be the (positive) formula that defines a point, then it becomes clear that point density is just φ-density.

Diagonal point density is another example of the notion of φ-density in ψ. Here ψ is the formula x ≤ d defining the subdiagonal elements and φ is the conjunction of ψ and the formula defining points. Notice that ψ satisfies conditions (i)–(iii) of Theorem 2.15. Indeed, since ψ is positive, it is preserved under homomorphisms. Now let f map 𝔄 homomorphically onto 𝔅 and suppose that y ∈ ψ^{𝔅}. Choose z ∈ A so that f(z) = y. Set x = d · z. Then x ∈ ψ^{𝔄} and

f(x) = f(d · z) = f(d) · f(z) = d · y = y .

This verifies condition (i). Condition (ii) is trivially satisfied. For condition (iii) let x ∈ A and set y = d · c_{(α)}(x). Then

c_{(α)}(y) = c_{(α)}(d · c_{(α)}(x)) = c_{(α)}(d) · c_{(α)}(x) = 1 · c_{(α)}(x) = c_{(α)}(x) ,

by 4.2(v) and 3.3(iii).

Theorem 5.18. Suppose that 𝔄 is a CA_{α}, QPEA_{α}, QPA_{α}, or SCA_{α} with finite dimension α ≥ 1. Then the following conditions are equivalent :

(i) 𝔄 is rich ;

(ii) 𝔄 is point dense ;

(iii) 𝔄 is rectangularly dense and quasi-atomic. If 𝔄 is a CA_{α} or a QPEA_{α}, then each of the above conditions is equivalent to each of the following conditions :

(iv) 𝔄 is rectangularly dense ;

(v) 𝔄 is diagonally point dense.

In case 𝔄 is simple we may replace “quasi-atomic ”by “atomic ”in (iii).

Proof: For the implication from (i) to (ii) suppose that 𝔄 is rich. To show that 𝔄 is point dense, fix a non-zero y. We define by induction on k ≤ α a sequence x_{0}, …, x_{k−1} of elements such that

(1) x_{i} is i-thin

for each i < k and

y · ∏_{i<k}x_{i} ≠ 0 . (2)

When k = 0 both (1) and (2) hold vacuously because y ≠ 0. Suppose now that 0 ≤ k < α and that for i < k the elements x_{i} have been defined so that (1) and (2) hold. From (Q4) and (2) we see that

c_{(α∼{k})}(y · ∏_{j<k}x_{j}) ≠ 0 . (3)

Because 𝔄 is rich, we can use Corollary 5.9 to find a non-zero k-thin element x_{k} below the left-hand side of (3). Hence, (1) holds for i = k and

x_{k} · c_{(α∼{k})}(y · ∏_{j<k}x_{j}) ≠ 0 .

Applying 4.2(vi) repeatedly we get

y · ∏_{j<k}x_{j} · c_{(α∼{k})}(x_{k}) ≠ 0 .

But c_{(α∼{k})}(x_{k}) = x_{k} since Δx_{k} ⊆ {k}. Thus, we arrive at (2), with “k + 1” in place of “k”.

Set

w = ∏_{i<α}x_{i} .

Then w is a point by (1) and Lemma 5.13, so w · y is a point by Lemma 5.14. Since w · y ≠ 0, by (2) with k = α, we see that w · y is a non-zero point beneath y. (See Figure 7.)

To establish the implication from (ii) to (iii), suppose that 𝔄 is point dense. Every point is a rectangle by Lemma 5.11. Moreover, every point is a quasi-atom by Lemma 5.14. Therefore, 𝔄 is rectangularly dense and quasi-atomic. If 𝔄 is simple, then every non-zero point is an atom by the same lemma, so 𝔄 is atomic.

To establish the implication from (iii) to (i), suppose that 𝔄 is rectangularly dense and quasi-atomic. To show that 𝔄 is rich, let y be any non–zero element with Δy ⊆ {0}. Because 𝔄 is quasi-atomic, there is a non-zero quasi-atom x below y. Then c_{(α∼{0})}(x) is below y by 4.2(ii) and the assumption that Δy ⊆ {0}. Moreover, c_{(α∼{0})}(x) is non-zero by (Q4) and 0-thin by Lemma 5.15 and the definition of a point. Thus, every non-zero element with dimension set included in {0} has a non-zero 0-thin element below it.

Assume now that 𝔄 is a CA_{α} or a QPEA_{α}. Clearly, (iii) implies (iv). To establish the implication from (iv) to (v), suppose that 𝔄 is rectangularly dense. Let y be any non-zero subdiagonal element. By rectangular density, there is a non-zero rectangle x below y. From Lemma 3.8(i) we see that x must be a quasi-atom, and therefore a point, by Lemma 5.15. Thus, 𝔄 is diagonally point dense.

Now suppose that (v) holds, with the goal of establishing (i). Let y be a nonzero element of 𝔄 whose dimension set is included in {0}. Then c_{(α∼{0})}(y) = y, Figure 7. Constructing a point w below a non-zero element y in a rich algebra.

so y · d ≠ 0 by Lemma 3.4. Invoking diagonal density, we obtain a non-zero point x below y · d. Using (Q4) and 4.2(ii), we see that

0 < c_{(α∼{0})}(x) ≤ c_{(α∼{0})}(y) = y .

Since x is a point, we conclude with the help of Definition 5.10 that c_{(α∼{0})}(x) is a non-zero 0-thin element below y. Hence, 𝔄 is rich. This completes the proof of the theorem.

Remark 5.19. From the previous theorem we see, e.g., that a simple, rich algebra is always atomic. Lemmas 5.15 and 5.14 give us a characterization of these atoms: they are precisely the non-zero points.

In contrast to the situation for CA_{α} and QPEA_{α}, in the case of QPA_{α} and SCA_{α} rectangular density does not imply quasi-atomicity. This is clear from Example 4.12, where we construct an atomless, rectangularly dense QPA_{α} 𝔄. Because 𝔄 is simple, a non-zero quasi-atom is the same thing as an atom. Hence, 𝔄 has no non-zero quasi-atoms.

Theorem 5.20. Suppose that 𝔄 is a CA_{α}, QPEA_{α}, QPA_{α}, or SCA_{α} with (possibly infinite) dimension α ≥ 2. If 𝔄 is rich, and if either α < ω or else α ≥ ω and 𝔄 is locally finite dimensional, then 𝔄 is representable.

Proof: Assume that 𝔄 is rich. If 2 ≤ α < ω, then 𝔄 is rectangularly dense and quasi-atomic by Theorem 5.18. Therefore, it is representable by Theorem 3.11 in the CA_{α} case, 4.6 in the QPEA_{α} case, 4.10 in the QPA_{α} case, and 4.20 in the SCA_{α} case.

Now suppose that α = ω and that 𝔄 is locally finite dimensional. For each n with 2 ≤ n < α let B_{n} be the set of elements whose dimension set is included in n. Then B_{n} is easily seen to be a subuniverse of the n-reduct of 𝔄, i.e., the reduct of 𝔄 to the Boolean operations and to the extra-Boolean operations and constants whose indices are included in n (see Henkin-Monk-Tarski [1971], Theorem 2.6.27.) Let 𝔅_{n} be the corresponding algebra. (This is usually called the neat n-reduct of 𝔄).

(1) Every 0-thin element of 𝔄 is in 𝔅_{n} and is 0-thin in 𝔅_{n}.

To prove (1), let x be a 0-thin element of 𝔄. Then Δx ⊆ {0} ⊆ n, so x is in 𝔅_{n}. To show that x remains 0-thin in 𝔅_{n}, let y be any element of 𝔅_{n}. Then in 𝔄 we have

x · c_{0}(x · y) ≤ y ,

and this equation must of course continue to hold in the subreduct 𝔅_{n}.

(2) 𝔅_{n} is rich.

For the proof, let y be a non-zero element of 𝔅_{n} such that Δy ⊆ {0} in 𝔅_{n}. Thus, c_{i}(y) = y for every i such that 0 < i < n. On the other hand, c_{i}(y) = y whenever n ≤ i < α, by definition of 𝔅_{n}. Therefore, Δy ⊆ {0} in 𝔄. Because 𝔄 is rich there must be a non-zero 0-thin element x below y in 𝔄. Then x is in 𝔅_{n} by (1), and in 𝔅_{n} it remains a non-zero 0-thin element below y.

From (2) and the finite dimensional case of the theorem that has already been proved, we conclude that

(3) 𝔅_{n} is representable.

Let K_{α} and K_{n} be the classes of representable algebras of dimension α and of dimension n respectively. Thus, e.g., K_{α} = RCA_{α} when 𝔄 is a CA_{α}, K_{α} = RQPA_{α} when 𝔄 is a QPA_{α}, etc. Then K_{α} is a variety. (See the remarks in Sections 3 and 4 regarding the classes of representable algebras.) To show that 𝔄 is in K_{α} it therefore suffices to show that every equation true of K_{α} is also true of 𝔄. Let ε be any such equation, say with variables among v_{0}, …, v_{k−1} . Let (y_{0}, …, y_{k−1}) be a sequence of arbitrary elements of 𝔄. Because 𝔄 is locally finite dimensional, we can find a finite n ≥ 2 such that Δy_{i} ⊆ n for each i < k and such that every extra-Boolean operation symbol of ε has its indices in n. Then y_{0}, …, y_{k−1} are in 𝔅_{n} and ε is an equation in the language of K_{n}. Because ε holds in K_{α} it must hold in K_{n}. (A proof of this in the cylindric algebraic case is given in the paragraph following the definition of RCA_{α}. As was noted in Section 4, this proof can easily be extended to cover the cases QPEA_{α}, QPA_{α}, and SCA_{α}.) Now 𝔅_{n} is in K_{n} by (3). Therefore ε holds in 𝔅_{n}. In particular, (y_{0}, …, y_{k−1}) satisfies ε in 𝔅_{n}. Since ε is an equation and 𝔅_{n} is a subreduct of 𝔄, we see that (y_{0}, …, y_{k−1}) must satisfy ε in 𝔄 as well. It follows that ε is true of 𝔄, as was to be shown.

The proof in the case when α > ω is essentially the same as in the case α = ω, but is notationally more complicated. We leave the details to the reader.

In case α ≥ ω, stronger results than the previous theorem are already known. In the remarks following Theorem 5.27 we shall explain what these results are and why we have bothered to include the case α ≥ ω in our theorem.

Corollary 5.21. Suppose that 𝔄 is a CA_{α}, QPEA_{α}, QPA_{α}, or SCA_{α} with finite dimension α ≥ 2. Then 𝔄 is representable iff it is embeddable into a rich algebra (from the same class).

Proof: Suppose that 𝔄 is embeddable into a rich algebra 𝔅. Then 𝔅 is representable by the previous theorem, so 𝔄 is representable.

Now suppose that 𝔄 is representable. Then it is embeddable into the direct product of full set algebras. Each such full set algebra is rich by Lemma 5.5, and it is not difficult to check that the product of rich algebras is again rich. (Indeed, 0-thinness is defined by a collection of equations and a single equation preceded by a universal quantifier.) Such formulas are satisfied by a sequence ⟨x_{ξ} : ξ ∈ Ξ ⟩ in a product 𝔅 = ∏_{ξ∈Ξ}𝔅_{ξ} iff each coordinate x_{ξ} satisfies them in the appropriate factor algebra 𝔅_{ξ}. Thus, a sequence is 0-thin iff each coordinate is 0-thin. Similarly, a sequence ⟨y_{ξ} : ξ ∈ Ξ ⟩ has dimension set included in {0} iff this is true of each coordinate. Suppose y = ⟨y_{ξ} : ξ ∈ Ξ ⟩ is non-zero and Δy ⊆ {0}. For each non-zero y_{ξ} (of which there must be at least one) choose a non-zero 0-thin x_{ξ} below y_{ξ} and otherwise set x_{ξ} = 0. Then x = ⟨x_{ξ} : ξ ∈ Ξ ⟩ is a non-zero 0-thin element below y in 𝔅.) Thus 𝔄 is embeddable into a rich algebra.

The remaining remarks in this section are historical, and concern principally the relationship of our notions and theorems for rich algebras to those of Henkin and Tarski. The following definition is due to Henkin and Tarski, and occurs as Definition 3.2.1 in Henkin-Monk-Tarski [1985].

Definition 5.22. Let 𝔄 be a CA_{α} with 2 ≤ α. An element x is i-thin provided that

(i) c_{j}(x) = x for j ≠ i, (ii) x · s_{ij}(x) ≤ d_{ij} for some j ≠ i, (iii) c_{i}(x) = 1 .

𝔄 is rich provided that, for every non-zero y in 𝔄 with Δy ⊆ {0}, there is a 0-thin x such that x · c_{0}(y) ≤ y.

Let us denote by ε_{ij} the equation

c_{j}[x · y · c_{i}(x · −y)] · −c_{i}[c_{j}(x) · −d_{ij}] = 0 .

Henkin and Tarski proved that for 2 ≤ α < ω every rich CA_{α} 𝔄 in which the equations ε_{ij} are valid for distinct i, j is representable (see Theorem 2.11(iii) in Henkin-Tarski [1961] for an announcement of this theorem).^{11} Condition (iii) in their definition of an i-thin element does not play a role in the proof when 𝔄 is simple. To obtain the general theorem from the simple case, one represents 𝔄 as a subdirect product of simple algebras. These simple factors are also rich and satisfy the same equations ε_{ij} . Hence, they are representable, by the simple case of the theorem. It follows that 𝔄 is representable. To prove that the simple factors

d_{ij} · c_{j}[−x · c_{i}(x)] · −c_{i}[ c_{j}(x) · −d_{ij}] = 0 .

11It is possible to replace ε_{ij} with the following equation, which has only one variable:

In fact, de Rijke-Venema [1995] have shown that for i ≠ j and 2 ≤ α < ω this equation is valid in a CA_{α} 𝔄 iff ε_{ij} is valid in 𝔄.

are rich, one must ensure that the image of a non-zero 0-thin element under a homomorphism is non-zero. This is just what condition (iii) guarantees.

In a direct proof of our version of the Henkin-Tarski theorem, condition (iii) is not needed because we do not use an arbitrary subdirect decomposition of 𝔄. Instead, we use the decomposition guaranteed by Corollary 2.10. Thus, we do not have to consider arbitrary simple homomorphic images of 𝔄, but rather only those that retain the 0-thin density character of 𝔄.

We are now in a position to understand the difference between the notions of richness defined in 5.22 and in 5.4. We believe that Henkin and Tarski would have liked to define richness (as we have) to mean that below every non-zero y with Δy ⊆ {0} there is a non-zero 0-thin x. However, the condition c_{0}(x) = 1 in their definition forces a 0-thin element in a subdirect product to have a non-zero coordinate in every factor algebra. On the other hand, such a subdirect product may have many non-zero elements y with Δy ⊆ {0} that have zero coordinates in some of the factor algebras. To get around this difficulty one must require that in each factor where the coordinate y_{ξ} of y is non-zero, the corresponding coordinate x_{ξ} of x is below y_{ξ}. This is precisely what is expressed by the condition x·c_{(α)}(y) ≤ y. (Essentially, c_{(α)}(y) is the union of the universes of all those factors where y_{ξ} is non-zero.) Since Δy ⊆ {0}, we may replace the term “c_{(α)}(y)” by “c_{0}(y)” in this condition. In this way we arrive at the Henkin-Tarski definition of a rich algebra.

Adding the condition c_{i}(x) = 1 to the definition of an i-thin element was a way for Henkin and Tarski to circumvent a difficulty that they encountered. However, it was not without its price. The next example shows that this condition restricts the number of algebras that can satisfy the definition of richness. To illustrate this quite clearly we shall construct a cylindric set algebra 𝔄 that is rich in the sense of 5.4 but does not possess a single thin element in the sense of 5.22, and hence cannot be rich in that sense. As an interesting additional property of 𝔄, we shall exhibit a homomorphic image of 𝔄 that is not rich in the sense of 5.4 (or, equivalently, that is not rectangularly dense). Thus, the notion of richness in this sense is not preserved under homomorphic images.

Example 5.23. Fix a finite α ≥ 2 and a set U of cardinality at least 2. Let 𝔅 be the minimal subalgebra of ℭ_{α}(U), i.e., the subalgebra of constants. Any subalgebra of ℭ_{2}(U), and in particular 𝔅, is simple. Therefore, by Theorem 2.1.17 in Henkin-Monk-Tarski [1971] (the cylindric algebraic analogue of quantifier elimination for the theory of equality), the elements of 𝔅 are just the Boolean combinations of diagonal elements. Using this, a rather straightforward set-theoretic argument shows:

(1) The only elements X in 𝔅 with |ΔX| ≤ 1 are ∅ and ^{α}U.

We mention in passing that ∅ is the only element of 𝔅 that is i-thin (for any i). In fact, by (1), the only possible i-thin elements of 𝔅 are ∅ and ^{α}U; it is easy to check, using Definition 5.1, that ^{α}U is not i-thin. Moreover, there is no non-zero i-thin element below ^{α}U. Thus, 𝔅 is not rich in the sense of Definition 5.4.

We single out a special subalgebra 𝔄 of the ω^{th} direct power of ℭ_{α}(U), namely the ω^{th}direct sum (also called the ω^{th}weak direct power) of ℭ_{α}(U) (see Sain [1982a] or Givant [1994]). The universe of 𝔄 consists of all those sequences that are eventually a constant. More precisely, it consists of the sequences ⟨X_{n} : n ∈ ω⟩ of subsets X_{n} of ^{α}U such that for some cofinite set Γ ⊆ ω we have

(2) X_{n} ∈ B and X_{m} = X_{n} for all m, n ∈ Γ.

(3) 𝔄 is rich in the sense of 5.4

Indeed, let Y = ⟨Y_{n} : n ∈ ω⟩ be a non-zero sequence in 𝔄 with ΔY ⊆ {0}. Then ΔY_{n} ⊆ {0} for every n ∈ ω and Y_{m} ≠ 0 for some fixed m ∈ ω. Suppose that ⟨u_{i} : i < α⟩ is an element of Y_{m}. Since ΔY_{m} ⊆ {0}, the set

Z = {x ∈ ^{α}U : x_{0} = u_{0}}

is included in Y_{m}. Define X = ⟨X_{n} : n ∈ ω⟩ by stipulating that

X_{n} = \begin{cases}Z & if n = m, \\ ∅ & if n ≠ m. \end{cases}

Then X is certainly in 𝔄 by definition of 𝔄; it is non-zero since X_{m} ≠ ∅; it is below Y since X_{n} ⊆ Y_{n} for all n ∈ ω; and it is 0-thin since each coordinate is 0-thin in ℭ_{α}(U), by 5.2. This proves (3).

(4) No element of 𝔄 is i-thin in the sense of 5.22.

To prove (4) fix i < α and suppose that X = ⟨X_{n} : n ∈ ω⟩ is an element of 𝔄 that satisfies conditions (i) and (iii) of 5.22. We shall show that it cannot satisfy condition (ii). Since X is in 𝔄, there is a cofinite subset Γ of ω such that (2) holds. Since X satisfies condition (i) we have ΔX_{n} ⊆ {i} for all n ∈ ω; therefore,

(5) For each n ∈ Γ the set X_{n} is either ∅ or ^{α}U

by (1) and (2). Since X satisfies condition (iii) we have

(6) C_{i}(X_{n}) = ^{α}U for all n ∈ ω.

Now C_{i}(∅) = ∅ ≠ ^{α}U. Therefore (5) and (6) together show us that X_{n} = ^{α}U for every n ∈ Γ. But ^{α}U does not satisfy condition (ii), since |U| ≥ 2 (see Lemma 5.2). Because of the form of condition (ii), a sequence in a direct power will satisfy it iff each coordinate satisfies it in the factor algebra. Therefore X cannot satisfy condition (ii).

From (4) we conclude that 𝔄 is not rich in the sense of 5.22.

Notice that 𝔅 is a homomorphic image of 𝔄. Indeed, the function that maps each sequence X = ⟨X_{n} : n ∈ ω⟩ in 𝔄 to the set that occurs cofinitely often in X is easily seen to be a homomorphism from 𝔄 onto 𝔅. In view of the remark after (1), this shows that 𝔄 has homomorphic images that are not rich in the sense of 5.4.

In our opinion, one of the conclusions of the above discussion is that, in view of Corollary 2.10 and Theorem 2.11, condition (iii) should be dropped from the Henkin-Tarski definition of an i-thin element and the definition of a rich algebra should be modified accordingly. Let us call an element weakly i-thin if it satisfies conditions (i) and (ii) of Definition 5.22. An algebra will be called weakly rich if below every non-zero element y with Δy ⊆ {0} there is a non-zero weakly 0-thin element. From now on, unless stated otherwise, whenever we refer to the notions of an i-thin element and a rich algebra (without the modifier “weakly”) we mean them in the sense of 5.1 and 5.4 respectively.

The definition of a weakly i-thin element differs from that of an i-thin element because the condition

x · s_{ij}(x) ≤ d_{ij} (1)

is weaker than the condition

(2) x · c_{i}(x · y) ≤ y for every y.

Indeed, suppose that (2) holds. Taking y = d_{ij} and using the definition of substitution in CA_{α}, we get (1). The reverse implication is not in general true, as we shall see in Example 5.24. However, it becomes true for fixed, distinct i, j if we assume ε_{ij} . Indeed, it is proved in Lemma 3.2.3(v) of Henkin-Monk-Tarski [1985] that if ε_{ij} is valid in a CA_{α} 𝔄, then an element of 𝔄 satisfying (1) must also satisfy (2). Thus, on the basis of the equations ε_{ij} the notions of i-thinness and weak i-thinness agree.

Whereas the notion of an i-thin element is based on a logical intuition, that of a weakly i-thin element is based on a set-theoretic intuition. In a full cylindric set algebra an element X is weakly i-thin if, for some j ≠ i, when we replace all the j^{th} coordinates of sequences in X by the elements from the i^{th} coordinates, then the i^{th} and j^{th} coordinates always agree. Under condition (i) this implies that all the sequences in X have the same i^{th} coordinate. Thus, the notion of a weakly i-thin element projects thinness back to the diagonal elements.

Example 5.24. We construct a simple CA_{2} 𝔄 which is weakly rich but not rich. In 𝔄 we will find weakly i-thin elements that are not i-thin. The universe of 𝔄 is the collection of all subsets of the set {0, 1, 2, 3, 4}. The Boolean operations are just the set-theoretic ones. The diagonal elements d_{00} and d_{11} are the unit and d_{01} = d_{10} = {0, 2}. The cylindrifications are completely determined by their action on the atoms (see Figure 8.):

c_{0}({0}) = c_{0}({3}) = c_{0}({4}) = {0, 3, 4} ,
c_{0}({1}) = c_{0}({2}) = {1, 2} ,
c_{1}({2}) = c_{1}({3}) = c_{1}({4}) = {2, 3, 4} ,
c_{1}({0}) = c_{1}({1}) = {0, 1} .

It is not difficult to check that 𝔄 is a simple CA_{2} . Its cylinders {0, 1} and {2, 3, 4} are weakly 0-thin, and {1, 2} and {0, 3, 4} are weakly 1-thin. For example, let x = {2, 3, 4} with the goal of showing that x is weakly 0-thin. Certainly c_{1}(x) = x. Also,

x · s_{01}(x) = x · c_{0}(x · d_{01}) = {2, 3, 4} ∩ c_{0}({2, 3, 4} ∩ {0, 2})
= {2, 3, 4} ∩ c_{0}({2}) = {2, 3, 4} ∩ {1, 2} = {2} ⊆ d_{01} .

Because the weakly 0-thin elements coincide with the elements different from the unit that are c_{0}-closed, we see that 𝔄 is weakly rich.

Figure 8. A weakly rich CA_{2} that is not rich.

The element x defined above is not 0-thin. To see this take y = {3}. Then

x · c_{0}(x · y) = {2, 3, 4} ∩ c_{0}({2, 3, 4} ∩ {3})
= {2, 3, 4} ∩ c_{0}({3}) = {2, 3, 4} ∩ {0, 3, 4} = {3, 4} ,

and this is not a subset of y. In a similar fashion, taking z = {0, 3, 4} and the same y, one can show that z is weakly 1-thin but not 1-thin. Thus, weak i-thinness does not imply i-thinness.

The cylinder x is not 0-thin, nor is there is a 0-thin element below it. In fact, x is an atom in the set of c_{1}-closed cylinders. Therefore, the algebra 𝔄 is not rich. Nor can it be represented. In a representable algebra the equations ε_{ij} always hold for distinct i, j and therefore the two notions of thinness coincide. However, in 𝔄 the two notions do not coincide.

The intuition behind the above example is the following. We have taken the full cylincric set algebra ℭ_{2}(2) on a base set of two elements and split one of the atoms that is off the diagonal into two (we split 3 into 3 and 4). In all other respects, 𝔄 behaves like ℭ_{2}(2). Because the definition of a weakly i-thin element projects thinness back to the diagonal (where 𝔄 is “normal”), the weakly thin elements of 𝔅 remain weakly thin in their modified form in 𝔄. However, thinness (as opposed to weak thinness) looks at the interaction of x not only with substitution instances of x, but with all elements y. Thus, it can notice that there is some abnormality “in the corner”.

It is natural to ask if one can project some notion of point back to the diagonal and in this way obtain a notion of point density that is equivalent to weak richness (without using the equations ε_{ij}). The next definition and the subsequent theorem achieve this goal.

Definition 5.25. Let α be finite and 𝔄 a CA_{α}. An element x is a weak diagonal point if it is a subdiagonal rectangle. 𝔄 is weakly diagonally point dense if every non-zero subdiagonal element is above a non-zero weak diagonal point.

Lemma 5.26. Let α ≥ 2 be finite and 𝔄 a CA_{α}.

(i) If x ≤ d_{ij} , then s_{ij}c_{(α∼{i})}(x) = c_{(α∼{j})}(x) .

(ii) If x is a non-zero weak diagonal point, then c_{(α∼{i})}(x) is a non-zero weakly

i-thin element. (iii) If x is a non-zero weakly i-thin element, then ∏_{j<α}s_{ij}(x) is a non-zero

weak diagonal point.

Proof: Since c_{(α∼{ij})}(d_{ij}) = d_{ij} , 3.2(iii) gives:

(1) If x ≤ d_{ij} , then c_{(α∼{ij})}(x) ≤ d_{ij} .

Using (1) we prove (i). When i = j the equality to be proved is a tautology. Suppose that i ≠ j.

s_{ij}c_{(α∼{i})}(x) = c_{i}(d_{ij} · c_{(α∼{i})}(x))  by definition of s_{ij} ,
= c_{i}(d_{ij} · c_{j}c_{(α∼{ij})}(x))  by (C4),
= c_{i}(c_{(α∼{ij})}(x))

by (1) and 3.3(ii) with Δ = {j}, k = i, and “c_{(α∼{ij})}(x)” for “x”,

= c_{(α∼{j})}(x)  by (C4) .

To prove (ii), suppose that x is a non-zero weak diagonal point, i.e., a non-zero subdiagonal rectangle. Then for j ≠ i we have

c_{(α∼{i})}(x) · s_{ij}c_{(α∼{i})}(x) = c_{(α∼{i})}(x) · c_{(α∼{j})}(x)  by (i),
= c_{(α∼{ij})}(x)  since x is a ; rectangle,
≤ d_{ij}  by (1).

Since Δc_{(α∼{i})}(x) ⊆ {i}, this shows that c_{(α∼{i})}(x) is weakly i-thin. If x ≠ 0, then of course c_{(α∼{i})}(x) ≠ 0 by (C2).

Taking up the proof of (iii), suppose that x is a non-zero weakly i-thin element. From Lemma 3.2.3(i) in Henkin-Monk-Tarski [1971] we obtain

x · s_{ij}(x) ≤ d_{ij} . (2)

Since s_{ii}(x) = x, we see from (2) that

∏_{j<α}s_{ij}(x) ≤ ∏_{j<α}d_{ij} = d .

Thus, ∏_{j<α}s_{ij}(x) is a subdiagonal element. Because d_{ij} · x ≤ x, we obviously have

c_{i}(d_{ij} · x) ≤ c_{i}(x) . (3)

Therefore,

s_{ij}(x)

= c_{i}(x) · c_{i}(d_{ij} · x)

by (3) and the definition of s_{ij} ,

= c_{i}(x · c_{i}(d_{ij} · x))  by (C3),
= c_{i}(x · c_{i}(d_{ij} · c_{(α∼{ij})}(x)))  since Δx ⊆ {i},

= c_{i}(x · c_{i}c_{(α∼{ij})}(d_{ij} · x)) by (C3) since

Δd_{ij} ⊆ {i, j},
= c_{i}c_{(α∼{ij})}(x · c_{i}(d_{ij} · x))  by (C4) and (C3),

= c_{(α∼{j})}(x · c_{i}(d_{ij} · x))  by (C4),
= c_{(α∼{j})}(x · s_{ij}(x))  by definition of s_{ij} .

Taking the product over all j < α we arrive at

∏_{j<α}s_{ij}(x) = ∏_{j<α}c_{(α∼{j})}(x · s_{ij}(x)) .

In view of 3.7, this shows that ∏_{j<α}s_{ij}(x) is a rectangle.

The above string of equalities also shows that

c_{(α∼{j})}s_{ij}(x) = s_{ij}(x) . (4)

In addition,

c_{j}s_{ij}(x) = c_{i}(x) . (5)

For i = j this is obvious. Suppose i ≠ j. Then

c_{j}s_{ij}(x) = c_{j}c_{i}(d_{ij} · x)  by definition of s_{ij} ,
= c_{i}c_{j}(d_{ij} · x)  by (C4) ,
= c_{i}(c_{j}(d_{ij}) · x)  {by (C3) and \atop c_{j}(x) = x,}
= c_{i}(x)  by 3.2(vi) and BA .

Therefore,

c_{(α)}(∏_{j<α}s_{ij}(x)) = c_{(α)}(∏_{j<α}c_{(α∼{j})}s_{ij}(x))  by (4),
= ∏_{j<α}c_{(α)}s_{ij}(x)  by 3.5(i) with Δ = α,
= ∏_{j<α}c_{j}c_{(α∼{j})}s_{ij}(x)  by (C4),
= ∏_{j<α}c_{j}s_{ij}(x)  by (4),
= ∏_{j<α}c_{i}(x)  by (5),
= c_{i}(x)  by BA,
≥ x  by (C2),
> 0  by assumption.

This forces ∏_{j<α}s_{ij}(x) to be non-zero.

Summarizing, we have shown that ∏_{j<α}s_{ij}(x) is a non-zero subdiagonal rectangle, which is just what was to be proved.

Theorem 5.27. Let α ≥ 2 be finite and 𝔄 a CA_{α}. Then 𝔄 is weakly rich iff it is weakly diagonally point dense.

Proof: Suppose first that 𝔄 is weakly diagonally point dense. To show that 𝔄 is weakly rich let y be a non-zero element such that Δy ⊆ {0}. We must construct a weakly 0-thin element below y. By Lemma 3.4 and y = c_{(α∼{0})}(y) we have

d · y = d · c_{(α∼{0})}(y) ≠ 0 .

Therefore, by assumption, there is a non-zero rectangle x below d · y. Then

c_{(α∼{0})}(x) ≤ c_{(α∼{0})}(y) = y .

Moreover, c_{(α∼{0})}(x) is a non-zero, weakly 0-thin element, by part (ii) of the previous lemma.

Now assume that 𝔄 is weakly rich. To show that it is weakly diagonally point dense, let y be a non-zero subdiagonal element. By our assumption, there is a non-zero, weakly 0-thin element x below c_{(α∼{0})}(y). Then

s_{0i}(x) ≤ s_{0i}c_{(α∼{0})}(y)  by 4.2(i) ,
= c_{(α∼{i})}(y)  by 5.26(i) and y ≤ d.

Therefore

∏_{i<α}s_{0i}(x) ≤ ∏_{i<α}c_{(α∼{i})}(y) .

Now

∏_{i<α}s_{0i}(x) ≤ d

by 5.26(iii). Also,

d · c_{(α∼{i})}(y) = y

by 3.3(ii) with (Δ = α ∼ {i} and k = i). Combining these three equations, we obtain

∏_{i<α}s_{0i}(x) ≤ d · ∏_{i<α}c_{(α∼{i})}(y) = y .

Since ∏_{i<α}s_{0i}(x) is a non-zero, weak diagonal point, by 5.26(iii), we are done.

In this paragraph we assume that α is infinite. Tarski proved that every locally finite dimensional CA_{α} is representable (see Henkin-Monk-Tarski [1971], Theorem 3.2.8, and see Tarski [1952] for the announcement of this result); the hypothesis of richness is not needed. Halmos proved that every locally finite dimensional polyadic algebra is representable (see, in particular, Theorems 16.9 and 17.1 in Chapter V of Halmos [1962], originally published in 1956). A consequence of this theorem is an analogous representation theorem for QPA_{α} and SCA_{α}. For the case of QPA_{α} this follows from Theorem 7.6 in Chapter 5 of op. cit. For the case of SCA_{α} we use also a theorem of Galler [1957] according to which a locally finite dimensional SCA_{α} is a reduct of a (locally finite dimensional) polyadic algebra of dimension α (see Pinter [1973], p. 365). (A direct proof that locally finite dimensional QPA_{α} and SCA_{α} are representable is given in Andréka-Gergely-Németi [1977], Theorem (A.3).) An argument similar to Galler’s shows that every locally finite dimensional QPEA_{α} is the reduct of a locally finite dimensional polyadic equality algebra of dimension α. (This also follows readily from results of Sain-Thompson [1991].) Since Halmos [1962] proved that the latter algebras are representable (see Theorem 6.9 of Chapter 7, and the remarks preceding the theorem), it follows that every locally finite dimensional QPEA_{α} is representable.

Theorem 5.20 above establishes the representability of rich algebras of finite dimension at least 2 and of rich algebras of infinite dimension that are locally finite dimensional. One may ask why we have included the latter case in our theorem when a much stronger result was established decades ago.

The proof of Tarski’s theorem in Henkin-Monk-Tarski [1985] proceeds in four main steps. Assume that α ≥ ω. The notion of richness referred to here is that of Definition 5.22.

(1)  Every simple, rich, locally finite dimensional algebra in which the equations ε_{ij} are valid for all distinct i, j < α is embeddable into a full cylindric set algebra of dimension α (see Theorem 3.2.5 in op. cit.).

(2)  A locally finite dimensional CA_{α} can be embedded into a rich, locally finite dimensional CA_{α} (see Lemma 3.2.7 in op. cit.).

(3)  Every homomorphic image of a rich, locally finite dimensional CA_{α} is rich and locally finite dimensional (see Lemma 3.2.6 in op. cit.).

(4)  The equations ε_{ij} for distinct i, j < α are valid in every locally finite di- mensional CA_{α} (see Theorem 1.11.7 in Henkin-Monk-Tarski [1971]).

Given an arbitrary locally finite dimensional CA_{α} 𝔄, one first passes to a rich, locally finite dimensional extension 𝔅 by using (2), then to a subdirect product of simple, rich, locally finite dimensional CA_{α} by using Birkhoff’s subdirect decomposition theorem and (3), and then to a representation of these simple factors by using (4) and (1).

In view of the above approach to the proof of Tarski’s theorem, and in particular in view of the important role played in the proof by (1), it seems to us of some interest to give the locally finite dimensional case (for α ≥ ω) in Theorem 5.20 as well. If one could establish the analogue of (2) for the notion of richness in 5.4 (and for each of the classes CA_{α}, QPA_{α}, QPEA_{α}, and SCA_{α}), then one would obtain as a consequence of 5.20 a general proof of the representation theorem for locally finite dimensional algebras of logic with infinite dimension.

Theorem 5.20 asserts, in particular, that every rich QPA_{α} of finite dimension α ≥ 2 is representable. This gives a positive solution to Problem 5.6 in Henkin-Monk-Tarski [1985]. Monk [1991] announced that Richard Thompson had found a solution to this problem. Unfortunately, this solution has never been published or even described in print. Thompson has communicated to us that he does not recall the details of his solution nor can he locate his notes on the subject. However, he does recollect that his solution was simple and followed closely the lines of the proof of Theorem 5.4.34 in op. cit. In attempting to reconstruct his solution on our own, we ran into the same difficulty that we encountered in Section 4: the substitution operations of a QPA_{α} need not be completely additive.

6. Rectangularly dense relation algebras and their generalizations

The first algebras of logic to be investigated after Boolean algebras were the algebras of binary relations of Peirce and Schröder. The study of an abstract version of these algebras, called relation algebras, was initiated by Tarski [1941].

Definition 6.1. A relation algebra is an algebra

𝔄 = ⟨A , + , − , ; , ^{⌣} , 1’⟩

such that ⟨A , + , −⟩ is a Boolean algebra , the operations ; and ^{⌣} of relative product (or composition) and conversion are, respectively, binary and unary, 1’ is a distinguished constant called the identity element , and the following postulates are satisfied for all x, y, z ∈ A:

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

(R2) x; (y + z) = (x; y) + (x; z) , (y + z) ; x = (y ; x) + (z ; x) , (R3) x; 1’ = x , 1’ ; x = x, (R4) x^{⌣}^{⌣} = x, (R5) (x + y)^{⌣} = x^{⌣} + y^{⌣}, (R6) (x; y)^{⌣} = y^{⌣} ; x^{⌣}, (R7) x^{⌣} ; [−(x; y)] ≤ −y. The class of all relation algebras is denoted by RA. We also use this notation as

an abbreviation for the phrase “relation algebra”.

Remark 6.2. It is well known that the second equations in (R2) and (R3) are derivable from the remaining postulate, and are therefore redundant. We have included them among the basic postulates of the theory in order to facilitate later references, in particular the definition of a Boolean monoid.

For an example of a relation algebra, let U be any set and define ℜ(U) to be the algebra

⟨Sb(U × U) , ∪ , ∼ , | , ^{−1} , Id_{U}⟩ ,

where | and ^{−1} are, respectively, the set-theoretic operations of composing two relations and taking the inverse of a relation, and Id_{U} is the identity relation on U. It is easy to check that ℜ(U) is a relation algebra; it is called the full set relation algebra over U. A relation algebra is said to be representable if it can be embedded into a direct product of full set relation algebras. The class RRA of all representable relation algebras is a subvariety of RA (see Tarski [1955]), but it is not finitely axiomatizable over the latter (see Monk [1964]). RA is a discriminator variety of BAOs with the unary discriminator term 1 ; x; 1.

We summarize some well-known laws that are valid in all relation algebras. Derivations of these laws can be found in Chin-Tarski [1951] and Givant [1994].

Lemma 6.3. Let 𝔄 be an RA and x, y, z, w elements of 𝔄.

(i) 0^{⌣} = 0 , 1^{⌣} = 1 , 1’^{⌣} = 1’ .

(ii) 1 ; 1 = 1 , 0 ; x = 0 .

(iii) (x · y)^{⌣} = x^{⌣} · y^{⌣}.

(iv) If z ≤ x and w ≤ y, then z ; w ≤ x; y.

(v) If x ≤ 1’, then x^{⌣} = x and x; x = x.

(vi) 1 ; [1’ · (1 ; x)] = 1 ; x.

(vii) (x; 1) · (1 ; y) = x; 1 ; y.

(viii) (x; y) · z ≤ x; [y · (x^{⌣} ; z)] and (x; y) · z ≤ [(z ; y^{⌣}) · x] ; y.

Laws (R1), (R2), (R3), and 6.3(iv) are respectively referred to as the associative law, the distributive laws, the identity laws, and the monotony law. In omitting parentheses, we follow the convention that ; has priority over ·.

In each RA 𝔄, we can define two unary operations c_{0} and c_{1} and constants d_{ij} for i, j ∈ {0, 1} as follows:

c_{0}(x) = 1 ; x , c_{1}(x) = x; 1 , d_{01} = d_{10} = 1’ , d_{00} = d_{11} = 1 .

It is well known that the algebra

⟨A , + , − , c_{0} , c_{1} , d_{ij}⟩_{i,j∈{0,1}}

is a CA_{2}. It is called the cylindric reduct of 𝔄. Since 𝔄 and its cylindric reduct 𝔅 have the same unary discriminator, we see that 𝔄 is simple iff 𝔅 is simple.

In view of the preceding observation, we can translate each of the notions defined in Sections 3 and 5 into the langugage of relation algebras.

Definition 6.4. Let 𝔄 be an RA and x an element of 𝔄.

(i) x is a rectangle if x = (x; 1) · (1 ; x) .

(ii) x is 0-thin if x = x; 1 and x · [1 ; (x · y)] ≤ y for all y. The definition of a

1-thin element is just the dual definition. (iii) x is weakly 0-thin if x = x; 1 and x · [1 ; (x · 1’)] ≤ 1’ . The definition of a

weakly 1-thin element is just the dual definition. (iv) x is a point if x; 1 is 0-thin and 1 ; x is 1-thin.

(v) x is a diagonal point if x is a point below 1’.

(vi) x is a weak diagonal point if x is a rectangle below 1’.

(vii) x is a quasi-atom if y ≤ x always implies y = x · (1 ; y ; 1).

Each of the above notions (i)–(vi) has equivalent forms in the theory of relation algebras that are more concise or more appealing.

Lemma 6.5. Let 𝔄 be an RA and x an element of 𝔄.

(i) The following are equivalent : (α) x is a rectangle , (β) x = x; 1 ; x, (γ) There are y, z such that x = y ; 1 ; z, (δ) There are y, z ≤ 1’ such that x = y ; 1 ; z.

(ii) The following are equivalent : (α) x is 0-thin , (β) x is weakly 0-thin , (γ) x = x; 1 and x; 1 ; x^{⌣} ≤ 1’ , (δ) x = x; 1 and x · x^{⌣} ≤ 1’ , (ϵ) x = x; 1 and x; x^{⌣} ≤ 1’ .

(iii) The following are equivalent :

(α) x is a point ,

(β) x; 1 ; x^{⌣} ≤ 1’ and x^{⌣} ; 1 ; x ≤ 1’ . (iv) The following are equivalent :

(α) x is a diagonal point , (β) x is a weak diagonal point , (γ) x; 1 ; x ≤ 1’ .

Proof: Part (i) is formulated and proved in Givant [1994], Lemma 1.12. To prove (ii), assume that

x = x; 1 . (1)

By (R6) and 6.3(i) we get

x^{⌣} = 1 ; x^{⌣} . (2)

Then

x; x^{⌣} = x; 1 ; x^{⌣}  by (1),

= (x; 1) · (1 ; x^{⌣})  by 6.3(vii),
= x · x^{⌣}  by (1), (2),
= x · (1 ; x^{⌣})  by (2),
= x · (1 ; [1’ · (1 ; x^{⌣})])  by 6.3(vi),
= x · [1 ; (1’ · x^{⌣})]  by (2),
= x · [1 ; (1’ · x)]  by 6.3(v),(iii),(i).

From this string of equalities we immediately obtain the equivalence of (β), (γ), (δ), and (ϵ). The implication from (α) to (β) follows by taking y = 1’. To show that (δ) implies (α), we use the second equation in 6.3(viii) (with “1” for “x”, “x · y” for “y”, and “x” for “z”):

x · [1 ; (x · y)] ≤ ([x; (x · y)^{⌣}] · 1); (x · y)
= x; (x^{⌣} · y^{⌣}) ; (x · y)  by BA and 6.3(iii),
= x; x^{⌣} ; y  by monotony,
≤ 1’ ; y  by (δ),
= y  by (R3).

Turning to (iii), suppose first that x is a point. By (ii)(β),

x; 1 ; x^{⌣} = (x; 1) ; 1 ; (1 ; x^{⌣})  by 6.3(ii),
= (x; 1) ; 1 ; (x; 1)^{⌣}  by (R6) and 6.3(i),
≤ 1’

by 6.4(iv) and (ii)(γ), with “x; 1” for “x”.

A similar argument using the 1-thinness of 1 ; x and the dual of (ii)(γ) for 1-thin elements shows that x^{⌣};1;x ≤ 1’. Now suppose that (iii)(β) holds, and set y = x;1. Using (iii)(β) and 6.3(i) we easily check that y ; 1 = 1 and y ; 1 ; y^{⌣} ≤ 1’. Thus, y is 0-thin. A similar argument shows that 1 ; x is 1-thin. Hence, x is a point.

Finally, we prove (iv). Under any of the three assumptions we have x ≤ 1’. Therefore

x = x^{⌣} = x; x . (1)

In particular,

x; 1 ; x = x; 1 ; x^{⌣} = x^{⌣} ; 1 ; x .

This shows that (iv)(γ) is equivalent to (iii)(β), and hence to (iv)(α). The implication from (iv)(β) to (iv)(γ) follows at once from (i)(β). To prove that (iv)(γ) implies (iv)(β) we must show that x; 1 ; x ≤ x (the reverse inclusion follows from monotony):

x; 1 ; x = (x; 1 ; x) · 1’  by (iv)(γ),
= x; [(1 ; x) · (x^{⌣} ; 1’)]

by the first equation in 6.3(viii) with “1 ; x” for “y”,

≤ x; x^{⌣}  by (R3) and monotony,
= x  by (1).

For each of the notions in Definition 6.4 we obtain a corresponding notion of density, just as in the cylindric algebraic case. We shall use the cylindric algebraic name to describe it.

Theorem 6.6. Let 𝔄 be an RA. Then the following are equivalent :

(i) 𝔄 is rectangularly dense , (ii) 𝔄 is rich , (iii) 𝔄 is weakly rich , (iv) 𝔄 is point dense ,

(v) 𝔄 is diagonally point dense , (vi) 𝔄 is weakly diagonally point dense.

If any one of these conditions holds, then 𝔄 is quasi-atomic, and atomic in case it is simple.

Proof: Let 𝔅 be the cylindric reduct of 𝔄. Then (i), (ii), (iv), and (v) are equivalent in 𝔅 by Theorem 5.18, (iii) and (vi) are equivalent by Theorem 5.27, and (ii) implies (iii) by the remarks preceding Example 5.24. Moreover, if (ii) holds in 𝔅 then it is quasi-atomic, and atomic in case it is simple, by Theorem 5.18. Because 𝔅 and 𝔄 have the same elements, and 𝔄 is simple iff 𝔅 is simple, we see that these equivalences and implications remain valid in 𝔄. Finally, since the notions of 0-thin and weakly 0-thin are equivalent by 6.5(ii), we see that (iii) implies (ii).

Maddux [1991] defines a point in a relation algebra to be a non-zero element x such that x ; 1 ; x ≤ 1’. He calls a relation algebra point-dense if every nonzero element below 1’ is above a point. In view of Lemma 6.5(iv), we see that Maddux’s notion of point density corresponds exactly to our notion of diagonal point density. Maddux proves in op. cit. (as part of a more general theorem) that a relation algebra which is (diagonally) point dense is representable. From this we immediately conclude:

Theorem 6.7. A relation algebra that satisfies one of the conditions (i)–(vi) in the preceding theorem is representable.

Lemma 6.5 sheds light on the relationship between the diagonally point dense part of Maddux’s theorem and Theorem 4.30 in Jónsson-Tarski [1952]. Jónsson and Tarski show that an atomic relation algebra in which each atom satisfies x^{⌣};1;x ≤ 1’ must be representable. Since x^{⌣} is an atom whenever x is an atom, we see that, under the hypotheses of their theorem, every atom also satisfies x; 1 ; x^{⌣} ≤ 1’. In view of 6.5(iii), we can reformulate the Jónsson-Tarski theorem as follows: every atomic relation algebra in which each atom is a point is representable. Now a special case of one of the steps in Maddux’s proof (his Theorem 48) shows that, for simple relation algebras, diagonal point density implies atomicity; the proof actually shows that each atom is a point. Thus, a simple, diagonally point dense relation algebra satisfies the hypothesis of the Jónsson-Tarski theorem; from this its representability follows at once.

We did not use Theorem 3.11 to prove the preceding theorem as we did in the case of quasi-polyadic algebras. Instead, we obtained it as an almost immediate consequence of the diagonally point dense case of Maddux’s theorem. Of course, one can also prove it quite easily using 3.11. In the process, one obtains both the Jónsson-Tarski theorem and the special case of Maddux’s theorem as immediate corollaries. In fact, using 3.11 leads to somewhat stronger results (whose proofs are correspondingly more involved). To formulate one example of such a result we introduce the following definition.

Definition 6.8. A Boolean (or Boolean-ordered) monoid is an algebra

𝔄 = ⟨A , + , − , ; , 1’⟩

(of the same type as a relation algebra without conversion) such that ⟨A , + , −⟩ is a Boolean algebra and the laws (R1)–(R3) hold. If, in addition, the laws

(R8) −(x; 1) ; 1 = −(x; 1) , 1 ; −(1 ; x) = −(1 ; x) hold, then the algebra is called special. The classes of all special Boolean monoids is denoted by BM^{∗}. We also use this notation as an abbreviation for the phrase “special Boolean monoid”.

The name “Boolean-ordered monoid” derives from the fact that ⟨A , ; , 1’ ⟩ is a monoid (i.e., a semigroup with an identity element) which is a Boolean algebra under the operations + and −, and the operation ; not only respects the Boolean order (i.e., the monotony law holds) but in fact is distributive over Boolean addition. Related structures such as lattice-ordered groups, lattice-ordered monoids, distributive lattice-ordered semigroups, etc. have been studied in the literature. See, for example, Birkhoff [1967], Chapters XIII and XIV (in particular, the remarks on pages 292 and 323) and Andréka [1991]. An apparently weaker notion of a Boolean monoid in which the monotony law replaces the distributive laws is considered in Pratt [1990]. The study of Boolean monoids has been stimulated in part by their connection with logics of the dynamic trend, for example, dynamic logic and arrow logic (see, e.g., Pratt [1990], Mikulás [1995], and Marx-Masuch-Polos [1996]).

The notions of a full set BM^{∗} (the algebra of all binary relations on some set under the obvious set-theoretic operations), a representable BM^{∗}, the cylindric reduct of a BM^{∗}, a rectangle in a BM^{∗}, and a rectangularly dense BM^{∗} are the obvious analogues of the relation algebraic notions.

All of the laws in the next lemma are very well known in the context of relation algebras. We show that they also hold in the context of special Boolean monoids. Several of the laws we shall list have a dual form. For example, the dual of (iv) is

1 ; x = 0 iff x = 0 .

The proof of the dual is just the dualized version of the proof of the given law. In what follows we shall not bother to formulate such duals. Moreover, when using these duals in other proofs, we shall simply refer to the given law in 6.9.

Lemma 6.9. The following laws are valid in all special Boolean monoids. (i) x; y ≤ u; v whenever x ≤ u and y ≤ v. (ii) x ≤ x; 1. (iii) 1 ; 1 = 1. (iv) x; 1 = 0 iff x = 0.

(v) [x · (y ; 1)] ; 1 = (x; 1) · (y ; 1).

(vi) x; 1 = [(x; 1) · 1’ ] ; 1.

(vii) If x ≤ 1’, then (x; 1) · 1’ = x.

(viii) If x ≤ 1’ and x′ = −x · 1’ , then (x; 1) · (x′ ; 1) = 0.

(ix) If x, y ≤ 1’, then x; y = x · y.

(x) x · (y ; 1) ≠ 0 iff (x; 1) · y ≠ 0.

(xi) If x, y are atoms, then x ≤ y ; 1 iff y ≤ x; 1.

(xii) If x is an atom, then so are (x; 1) · 1’ and (1 ; x) · 1’.

(xiii) x; y = 0 iff [(1 ; x) · 1’ ] · [(y ; 1) · 1’ ] = 0.

Proof: Part (i) is an almost immediate consequence of distributivity. Indeed, suppose that x ≤ u and y ≤ v. Then

u; v = u; (y + v) = u; y + u; v .

Therefore, u; y ≤ u; v. Similarly, x; y ≤ u; y. Combining these two inequalities, we get the desired result.

Part (ii) follows from the identity laws and monotony (part (i)):

x = x; 1’ ≤ x; 1 .

Part (iii) follows at once from (ii) with x = 1.

To prove (iv), assume first that x = 0. Then by (iii) and (R8) we have:

x; 1 = 0 ; 1 = [−(1 ; 1)] ; 1 = −(1 ; 1) = 0 .

Now assume that x; 1 = 0. Using the identity laws and monotony, we have

x = x; 1’ ≤ x; 1 = 0 .

The proof of part (v) is more involved. Notice that (x;1)·−(y;1) and (x;1)·(y;1) form a partition of x ; 1 in the sense that they are disjoint and sum to x ; 1. We now show that same is true of the elements [x · −(y ; 1)] ; 1 and [x · (y ; 1)] ; 1, and that these elements are below (x; 1) · −(y; 1) and (x; 1) · (y; 1) respectively. From this it follows at once that these two partitions must in fact be the same partition. In particular,

[x · (y ; 1)] ; 1 = (x; 1) · (y ; 1) .

By monotony and (R8) we have

[x · −(y ; 1)] ; 1 ≤ x; 1

and

[x · −(y ; 1)] ; 1 ≤ −(y ; 1) ; 1 = −(y ; 1) ,

so

(1)  [x · −(y ; 1)] ; 1 ≤ (x; 1) · −(y ; 1) .

Similarly,

(2)  [x · (y ; 1)] ; 1 ≤ (x; 1) · (y ; 1) .

In particular, since the elements on the right-hand sides of (1) and (2) are disjoint, so are the elements on the left. Further, using distributivity and BA we see that

[x · −(y ; 1)] ; 1 + [x · (y ; 1)] ; 1 = [x · −(y ; 1) + x · (y ; 1)] ; 1
= (x · [−(y ; 1) + (y ; 1)]) ; 1
= (x · 1) ; 1
= x; 1 .

This completes the proof of (v).

Part (vi) is an immediate consequence of (v) and the identity laws:

[(x; 1) · 1’] ; 1 = (x; 1) · (1’ ; 1) = (x; 1) · 1 = x; 1 .

For (vii)–(ix) assume that x ≤ 1’ and set x′ = −x · 1’. Then

(x; 1) · 1’ = [x; (1’ + −1’)] · 1’ by BA,
= (x; 1’ + x; −1’) · 1’ by distributivity,
= (x + x; −1’) · 1’  by the identity laws,
≤ (x + 1’ ; −1’) · 1’  by monotony and x ≤ 1’,
= (x + −1’) · 1’  by the identity law,
= x · 1’  by BA,
= x  since x ≤ 1’.

The reverse inequality follows from (ii) and the assumption that x ≤ 1’. This proves (vii).

Before proving (viii) and (ix) we establish

x · (x′ ; 1) = 0 , (3)

x; x′ = 0 . (4)

Indeed, using x, x′ ≤ 1’ and part (vii) (applied to x′) we have

x · (x′ ; 1) ≤ 1’ · (x′ ; 1) = x′ ,

and trivially

x · (x′ ; 1) ≤ x ,

so

x · (x′ ; 1) ≤ x · x′ = 0 .

Similarly, by monotony and the identity laws we have

x; x′ ≤ x; 1’ = x  and  x; x′ ≤ 1’ ; x′ = x′ ,

so

x; x′ ≤ x · x′ = 0 .

Turning to (viii), we have

(x; 1) · (x′ ; 1) = [x · (x′ ; 1)] ; 1 by (v),
= 0 ; 1  by (3),
= 0  by (iv).

For (ix) we first establish the special case when x = y, i.e.,

x; x = x . (5)

Indeed, by the identity laws, distributivity, and (4) we have

x = x; 1’ = x; (x + x′) = x; x + x; x′ = x; x .

Turning to the general case of (ix), suppose that y ≤ 1’. Then

x · y = (x · y) ; (x · y) ≤ x; y ,

by (5) and monotony. On the other hand,

x; y ≤ x; 1’ = x ,

by monotony and the identity laws. Similarly, x ; y ≤ y. Therefore, x ; y ≤ x · y. This completes the proof of (ix).

Part (x) follows from (iv) and (v):

x · (y ; 1) ≠ 0 iff [x · (y ; 1)] ; 1 ≠ 0 by (iv),
iff (x; 1) · (y ; 1) ≠ 0 by (v),
iff [(x; 1) · y] ; 1 ≠ 0 by (v),
iff (x; 1) · y ≠ 0  by (iv).

Part (xi) is an immediate consequence of (x).

To prove (xii), assume that x is an atom. Then x;1 ≠ 0 by (ii), so [(x;1)·1’];1 ≠ 0 by (vi). Hence, (x; 1) · 1’ ≠ 0 by (iv). Let y be a non-zero element below (x; 1) · 1’. Our goal is to show that (x; 1) · 1’ ≤ y. We have

y · (x; 1) = (y · 1’) · (x; 1) since y ≤ 1’,
= y  since y ≤ (x; 1) · 1’,
≠ 0  by assumption.

Therefore (y ; 1) · x ≠ 0 by (x). Hence,

x ≤ y ; 1  since x is an atom,
x; 1 ≤ y ; 1  by monotony and (iii),
(x; 1) · 1’ ≤ (y ; 1) · 1’ by BA,
(x; 1) · 1’ ≤ y  by (vii).

Finally, part (xiii) follows at once from (several applications of) (iv) and the following observation:

1 ; x; y ; 1 = 1 ; [(1 ; x) · 1’)] ; [(y ; 1) · 1’] ; 1 by (vi),
= 1 ; ([(1 ; x) · 1’)] · [(y ; 1) · 1’]); 1 by (ix).

Lemma 6.10. (i) BM^{∗} is a discriminator variety of normal Boolean algebras

with operators. In fact, the term 1 ; x; 1 is a unary discriminator for BM^{∗}. (ii) The cylindric reduct of a special Boolean monoid is a CA_{2}.

Proof: Relative product is the only extra-Boolean operation of rank > 0 in a BM^{∗}. It is additive by the distributive laws, and normal by 6.9(iv). In view of Corollary 2.2, to show that 1 ; x; 1 is a unary discriminator for BM^{∗} we must show that it satisfies the five conditions (α)–(δ) of Lemma 2.1(ii). The validity of these conditions follows from 6.9(ii),(iii), (R8), and monotony respectively. For example for (δ) we must check that, for all x, y in a special Boolean monoid we have

x; y < 1 ; x; 1  and  x; y ≤ 1 ; y ; 1 . (1)

Now x ≤ 1 ; x by 6.9(ii), and y ≤ 1, so the first inequality in (1) follows from the monotony law. The second is proved similarly. This completes our proof of (i).

To prove (ii), let 𝔄 be a BM^{∗}, and suppose that 𝔅 is its cylindric reduct. We must verify that axioms (C1)–(C7) are valid in 𝔅. This is quite easy using the postulates for special Boolean monoids and Lemma 6.9. For example, to verify the validity of (C7) in 𝔅, we first translate it into an equation in the language of special Boolean monoids and then check the validity of this equation in 𝔄. In the case when i = 1 and j = 0, (C7) translates into the equation

[(x · 1’ ) ; 1] · [(−x · 1’ ) ; 1] = 0 ,

and this is valid in 𝔄 by 6.9(viii). The validity of the translation of (C1) follows from 6.9(iv), that of (C2) from 6.9(ii), that of (C3) from 6.9(v), that of (C4) from the associative law, and that of (C5) from the definition of d_{ii}. Finally, we check the validity of (C6) in the case when i = 1. We must have j = k = 0, since i ≠ j, k. Thus, (C6) translates into the equation 1 = 1’ ; 1, and this is just a special case of the identity laws.

Lemma 6.11. Let 𝔄 be a special Boolean monoid. A set I is an ideal in 𝔄 iff it is an ideal in the cylindric reduct of 𝔄. In particular, 𝔄 is simple iff the cylindric reduct of 𝔄 is simple.

Proof: Let 𝔄 be a special Boolean monoid and 𝔅 its cylindric reduct. Suppose, first, that I is an ideal of 𝔄 and that x ∈ I. Then x; 1 and 1 ; x are in I by 2.4(iv), i.e., c_{1}(x) and c_{0}(x) are in I. Thus, I is an ideal of 𝔅 by 2.4. Now suppose that I is an ideal of 𝔅 and that x ∈ I. Then c_{1}(x) and c_{0}(x) are in I by 2.4(iv), i.e., x; 1 and 1 ; x are in I. But x; y ≤ x; 1 and y ; x ≤ 1 ; x by monotony, so x; y and y ; x are in I by 2.4(iii). Therefore I is an ideal of 𝔄 by 2.4. This proves the first assertion. The second assertion is an immediate consequence of the first.

Lemma 6.12. A simple , rectangularly dense , special Boolean monoid is representable.

Proof: Let 𝔄 be a simple, rectangularly dense BM^{∗} and 𝔅 its cylindric reduct. Then 𝔅 is a simple, rectangularly dense CA_{2} , by Lemmas 6.11 and 6.10(ii). Hence, 𝔅 is atomic and representable, by Lemma 3.10 and Theorem 3.11. In fact, taking U to be the set of atoms below 1’ = d_{01} = d, the function f mapping A into Sb(U ×U) that is determined by

f(x) = {(w; 1 · 1’ , 1 ; w · 1’) : w is an atom below x}

is an embedding of 𝔅 into ℭ_{2}(U) (see the remarks after Theorem 3.11). Notice that by its very definition, f preserves (as unions) all Boolean sums in 𝔅 that exist, i.e., it is a complete embedding.

Let 𝔇 be the full set BM^{∗} on U. Notice that 𝔇 is also simple and rectangularly dense (since its cylindric reduct, ℭ_{2}(U), is). We wish to show that f embeds 𝔄 into 𝔇. Since f preserves the cylindric algebraic operations, it preserves in particular the Boolean operations and constants, and maps the constant 1’ to Id_{U} (these are the main diagonals of 𝔅 and ℭ_{2}(U) respectively). It remains to show that f preserves relative products. In view of our previous remarks, it suffices to prove that in a simple (and hence atomic) rectangularly dense BM^{∗} the relative product operation is definable in terms of the cylindric algebraic operations.

(1) If u, v are atoms, then so is (u; 1) · (1 ; v).

To prove (1), suppose that u, v are atoms. Then

[(u; 1) · (1 ; v)] ; 1 = (u; 1) · (1 ; v ; 1) by 6.9(v),
= (u; 1) · 1  by simplicity, since v ≠ 0,
= u; 1  by BA,
≥ u  by 6.9(ii),
> 0  since u is an atom.

Thus (u ; 1) · (1 ; v) ≠ 0, by 6.9(iv). Now let w be any non-zero element below (u; 1) · (1 ; v). By rectangular density there is a non-zero rectangle e below w. In particular, e ≤ u; 1, so

e · (u; 1) ≠ 0  by BA,
(e; 1) · u ≠ 0  by 6.9(x),
u ≤ e; 1 since u is an atom,
u; 1 ≤ e; 1 by 6.9(i),(iii).

Similarly, 1 ; v ≤ 1 ; e. Therefore, using also the assumption that e is a rectangle, we get

(u; 1) · (1 ; v) ≤ (e; 1) · (1 ; e) = e .

This of course forces

e = w = (u; 1) · (1 ; v) ,

which is what we wanted to prove.

(2)  For atoms u, v we have u; v = \begin{cases}(u; 1) · (1 ; v) & if (1 ; u) · 1’ = (v ; 1) · 1’ , \\ 0 & if (1 ; u) · 1’ ≠ (v ; 1) · 1’ . \end{cases}

Indeed, suppose that u, v are atoms. If (1 ; u) · 1’ ≠ (v ; 1) · 1’, then

[(1 ; u) · 1’] · [(v ; 1) · 1’] = 0 ,

since (1 ; u) · 1’ and (v; 1) · 1’ are atoms by 6.9(xii). Therefore u; v = 0 by 6.9(xiii). If (1 ; u) · 1’ = (v; 1) · 1’, then u; v ≠ 0, by 6.9(xiii). But u; v ≤ u; 1 and u; v ≤ 1 ; v by monotony, so u; v ≤ (u; 1) · (1 ; v). Since the latter element is an atom, by (1), we conclude that equality actually holds in the previous equation.

In cylindric algebraic notation, the equation in (2) becomes:

u; v = \begin{cases}c_{1}(u) · c_{0}(v) & if c_{0}(u) · d = c_{1}(v) · d , \\ 0 & if c_{0}(u) · d ≠ c_{1}(v) · d . \end{cases}

Thus, (2) shows that, for atoms, relative product is definable in terms of the cylindric algebraic operations.

(3)  For arbitrary elements x, y we have x; y = ∑{u; v : u, v atoms and u ≤ x, v ≤ y} .

Let w be an atom below x; y. We shall construct atoms u and v below x and y respectively such that

w = u; v . (4)

Since x; y ≠ 0 (because w ≤ x; y), we see that

[(1 ; x) · 1’] · [(y ; 1) · 1’] ≠ 0

by 6.9(xiii). Because the BM^{∗} with which we are dealing is assumed to be simple, and hence atomic, there is an atom z below [(1 ; x) · 1’] · [(y; 1) · 1’]. By 6.9(vii) we have

z = (z ; 1) · 1’ = (1 ; z) · 1’ . (5)

Set

u = (w; 1) · (1 ; z)  and  v = (z ; 1) · (1 ; w) . (6)

Then

(7) u , v , (u; 1) · (1 ; v) are atoms

by (1).

Now

(1 ; u) · 1’ = (1 ; [(w; 1) · (1 ; z)]) · 1’ by (6),
= [(1 ; w; 1) · (1 ; z)] · 1’ by 6.9(v),
= (1 ; z) · 1’  by simplicity and BA.
= z  by (5).

Similarly, (v ; 1) · 1’ = z, so

(1 ; u) · 1’ = (v ; 1) · 1’ = z . (8)

Since z is non-zero, we see from (8), 6.9(xiii), and monotony that

0 < u; v ≤ (u; 1) · (1 ; v) .

But (u; 1) · (1 ; v) is an atom, by (7). Hence,

u; v = (u; 1) · (1 ; v) . (9)

Applying simplicity and 6.9(v), we get that

u; 1 = [(w; 1) · (1 ; z)] ; 1 = (w; 1) · (1 ; z ; 1) = w; 1 .

Similarly,

1 ; v = 1 ; w .

Therefore, using also (9) and monotony, we obtain

0 < w ≤ (w; 1) · (1 ; w) = (u; 1) · (1 ; v) = u; v .

But u; v is an atom, by (7) and (9). Therefore, we arrive at (4).

Since the algebra under consideration is atomic, x ; y is the sum of the atoms below it. By (4), each such atom can be written in the form u; v for some atoms u and v beneath x and y respectively. Therefore, x; y is a sum of some elements of the form u; v with u, v atoms, u ≤ x, and v ≤ y. But each such element u; v is clearly below x; y by monotony. Thus, x; y is the sum of all such elements. This completes the proof of (3).

Each of 𝔄 and 𝔇 is a simple, rectangularly dense BM^{∗}. Therefore, equations (2) and (3) apply to both algebras. In particular, in each algebra a relative product is the sum of relative products of certain atoms, and each such relative product of atoms is definable by the cylindric algebraic operations. Now f preserves arbitrary Boolean sums (by its very definition) and the cylindric algebraic operations. Hence, f must preserve relative products.

Our proof of Lemma 6.12 has relied on the proof of Henkin and Tarski that an atomic CA_{2} with rectangular atoms is representable. However, a direct proof of the lemma is easily given. In fact, all of the necessary ingredients are already present in our argument. Using (1) and some similar arguments, one first shows that

(10) f maps the set of atoms of 𝔄 one-one onto the set of atoms of 𝔇.

It follows that f preserves all of the Boolean operations. Also, f preserves 1’, since f(u) = (u, u) for every subidentity atom u. The next step is to show that

(11) f preserves the relative product of two atoms.

The proof uses (2) applied to both 𝔄 and 𝔇, (10), and the following equations:

[(U × U)|f(u)] ∩ Id_{U} = ((1 ; u) · 1’, (1 ; u) · 1’) ,
[f(u)|(U × U)] ∩ Id_{U} = ((u; 1) · 1’, (u; 1) · 1’)

for every atom u of 𝔄. From these equations it follows that

[(U × U)|f(u)] ∩ Id_{U} = [f(v)|(U × U)] ∩ Id_{U} iff (1 ; u) · 1’ = (v ; 1) · 1’

for atoms u, v of 𝔄. Finally, one uses (3) and the complete additivity of f to prove that f preserves arbitrary relative products.

Theorem 6.13. A rectangularly dense, special Boolean monoid is representable.

The proof is identical to the proof in the finite dimensional cylindric algebraic case of Theorem 3.11 except that we use the preceding lemma instead of the Henkin-Tarski representation theorem. We leave the details to the reader.

Using the previous result, one readily establishes the next theorem (see Mikulás [1995], p. 112).

Theorem 6.14. Let

𝔄 = ⟨A , + , − , ; , ^{⌣} , 1’ ⟩

be an algebra of the same similarity type as relation algebras. Suppose that ⟨A , + , −⟩ is a Boolean algebra and that laws (R1)–(R6), (R8) are valid in 𝔄. If 𝔄 is rectangularly dense, then it is isomorphic to a set relation algebra.

In particular, it follows that in the presence of (R1)–(R6), the law (R8) (which can be viewed as a very special case of (R7)) and rectangular density together imply (R7).

Example 6.15. Axiom (R8) is necessary in the proof of Theorem 6.13. To show this, let V be the ≤ relation on the integers restricted to the set U = {0, 1, 2}. Let 𝔅 be the full set BM^{∗} on U and 𝔄 the relativization of 𝔅 to V. Thus, the universe of 𝔄 consists of all subsets of V and the operations of 𝔄 are the relativizations to V of the (set-theoretic) operations of 𝔅. For example, for R, S in 𝔄 we define

R;^{𝔄} S = (R|S) ∩ V .

It is not hard to verify that (R1)–(R3) hold in 𝔄. Further, 𝔄 is rectangularly dense (in fact, it is point dense). But (R8) fails in 𝔄. For example, if R = {(0, 2)}, then

−(1 ; R) = V ∼ [(V |R) ∩ V] = V ∼ {(0, 2)}

and

1 ; [−(1 ; R)] = (V | [V ∼ {(0, 2)}]) ∩ V = V .

Since (R8) holds in all set BM^{∗}, it follows that 𝔄 is not representable.

7. Some further open problems

The representability of algebras of logic that are rectangularly dense seems to be a general phenomenon, that is, it appears to hold for many different kinds of algebras in which we can formulate a notion of rectangle. Therefore, in our opinion there should be a characteristic cause for the representability that finds its expression in the methodology of the proof: there should be a “method” for building a representation directly from a densely ordered collection of rectangles of an algebra, a method that is independent of the choice of fundamental operations of the algebra.

Unfortunately, no such method of direct representation is currently known. Each of the representation theorems for rectangularly dense algebras in this paper has been established by a reduction to the Henkin-Tarski representation theorem for atomic cylindric algebras with rectangular atoms or by using the idea of the proof of that theorem. This reduction, as well as the proof of the Henkin-Tarski Theorem itself, requires the presence of diagonal elements (perhaps in some appropriate extension). Can this reduction to the atomic case, and in particular can the dependence on diagonal elements, be avoided?

Summarizing, the problem is to (1) find a general and direct method for constructing a representation of rectangularly dense algebras from the rectangles themselves, without using diagonal elements and without reducing the construction to the atomic case, and (2) explore the areas of applicability of this method.

As a test case for such a method, we propose the (still unsolved) problem of showing that rectangularly dense diagonal-free cylindric algebras are representable. A diagonal-free cylindric algebra of dimension α is an algebra

𝔄 = ⟨A , + , − , c_{i}⟩_{i∈α}

such that ⟨A , + , −⟩ is a Boolean algebra and the c_{i} are unary operations satisfying postulates (C1)–(C4) (see Henkin-Monk-Tarski [1971], Definition 1.1.2). The definition of a rectangle and of rectangular density is the same as in the cylindric algebraic case. Since diagonal elements are not present and cannot be defined in appropriate extensions, it does not seem that the methods developed in the present paper can be used to solve the problem.^{12}

Turning to another problem, suppose that 𝔄 is, e.g., a CA_{α} or an RA (or one of the other algebras of logic considered in this paper). We shall say that a subalgebra 𝔅 of 𝔄 is dense in 𝔄 if the set B is dense in 𝔄, i.e., if every non-zero element of 𝔄 is above a non-zero element of 𝔅. As was mentioned earlier, this is equivalent to the assumption that every element of 𝔄 is the sum of the elements of 𝔅 that are below it.

Problem 7.1. If 𝔅 is dense in 𝔄 and representable, is 𝔄 necessarily representable?

12A proof that rectangularly dense, diagonal-free cylindric algebras are representable was recently obtained by Venema [1996]. A different proof was found a few months later by Andréka-Givant, who also obtained a positive solution to the general methodological problem. Venema’s approach is to build a representation using a step-by-step construction. In contrast to this, the approach of Andréka-Givant is to use the Boolean algebras of cylinders to construct directly a representation. (See Example 4.12 for another application of this idea.)

A positive solution to Problem 7.1 would provide us with a generalization of Theorem 3.11, the representation theorem for rectangularly dense CA_{α}, at least in the finite dimensional case. To see this, suppose that 𝔄 is a rectangularly dense CA_{α} with 2 ≤ α < ω. Let 𝔅 be the subalgebra of 𝔄 generated by the set of monadic elements, i.e., by the set

{x ∈ A : |Δx| ≤ 1} .

Notice that, by Lemma 3.7, every rectangle of 𝔄 is in 𝔅. Since the set of rectangles is assumed to be dense in 𝔄, the algebra 𝔅 must be dense in 𝔄. Now Monk [1964a] proved that every monadically generated CA_{α} is representable. Thus, 𝔅 is representable and dense in 𝔄. Applying the assumed positive solution to Problem 7.1, we conclude that 𝔄 is representable.

Interestingly, for classes K of algebras with completely additive extra-Boolean operations and such that K is closed under completions (i.e., the completion of each algebra in K is again in K), Problem 7.1 is equivalent to a problem formulated in Section 2 of Monk [1970]:

Problem 7.2. Is the completion of a representable algebra necessarily representable?^{13}

Indeed, suppose that Problem 7.2 has a positive solution. Let 𝔅 be a dense subalgebra of 𝔄 that is representable. Take ℭ to be the completion of 𝔄. Since 𝔅 is dense in 𝔄, it is dense in ℭ. From this it is easy to check that ℭ must be the completion of 𝔅 (use conditions (ii) and (iii) of the definition of a completion, given after Theorem 4.6, and the complete additivity of the extra-Boolean operations). Because 𝔅 is representable, we conclude from our assumption that ℭ is representable. Therefore 𝔄 is also representable.

Now suppose that Problem 7.1 has a positive solution. Let 𝔅 be a representable algebra and 𝔄 the completion of 𝔅. It is easy to check (using condition (ii) of the definition of a completion) that 𝔅 is dense in 𝔄. Hence, by our assumption, the representability of 𝔅 implies that of 𝔄.

References

[1991] Andréka, H., “Representations of distributive lattice-ordered semigroups with binary relations”, Algebra Universalis, 28 (1991), pp. 12–25.

[a] Andréka, H., “Complexity of equations valid in algebras of relations”, Annals of Pure and Applied Logic, to appear.

[1977] Andréka, H., Gergely, T., and Németi, I., “On universal algebraic constructions of logics”, Studia Logica 37,(1977), pp. 9–47.

[1994] Andréka, H., Németi, I., and Sain, I., “Applying algebraic logic to logic”, in Algebraic methodology and software technology (AMAST ’93), Proceedings Twente, The Netherlands, June 1993 (editors: Nivat, M., Rattray, C., Rus, T., and Scollo, G.), Springer-Verlag, London, 1994, pp. 7–28.

[1967] Birkhoff, G., Lattice theory, Colloquium Publications, vol. 25, American Mathematical Society, Providence, RI, 1967, vi + 418 pp.

13Quite recently, Hodkinson [1997] has given, in Corollary 8.10, an example of two relation algebras, one representable, the other not, that have the same atom structure. Using this example, it is not difficult to conclude that there must a representable relation algebra whose completion is not representable. Thus, Problems 7.1 and 7.2 both have negative solutions.

[1973] Chang, C. C. and Keisler, H. J., Model theory, Studies in Logic and the Foundations of Mathematics, vol. 73, North-Holland Publishing Company, Amsterdam, 1973, xii + 550 pp.

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

[1995] de Rijke, M. and Venema, Y., “Sahlquist’s theorem for Boolean algebras with operators with an application to cylindric algebras”, Studia Logica, 54 (1995), pp. 61–79.

[1957] Galler, B., “Cylindric and polyadic algebras”, Proceedings of the American mathematical Society, 8 (1957), pp. 176–183.

[1994] Givant, S. R., The structure of relation algebras generated by relativizations, Contemporary Mathematics, vol. 156, American Mathematical Society, Providence, R.I., 1994, xv + 134 pp.

[1962] Halmos, P. R., Algebraic logic, Chelsea Publishing Company, New York, 1962, 271 pp.

[1961] Henkin, L. and Tarski, A., “Cylindric Algebras”, in Lattice Theory (editor: R. P. Dilworth), Proceedings of Symposia in Pure Mathematics, vol. 2, American Mathematical Society, Providence, R. I., 1961, pp. 83–113.

[1971] Henkin, L., Monk, J. D., and Tarski, A., Cylindric algebras. Part I, Studies in Logic and the Foundations of Mathematics, vol. 64, North-Holland Publishing Company, Amsterdam, 1971, vi + 508 pp.

[1985] Henkin, L., Monk, J. D., and Tarski, A., Cylindric algebras. Part II, Studies in Logic and the Foundations of Mathematics, vol. 115, North-Holland Publishing Company, Amsterdam, 1985, x + 302 pp.

[1997] Hodkinson, I., “Atom structures of relation algebras”

[1993] Jipsen, P., “Discriminator varieties of Boolean algebras with residuated operators”, in Algebraic methods in logic and computer science (editor: C. Rauszer), Banach Center Publications, vol. 28, Polish Academy of Sciences, Warsaw, 1993, pp. 239–252.

[1969] Johnson, J. S., “Nonfinitizability of classes of representable polyadic algebras”, Journal of Symbolic Logic, 34 (1969), pp. 344–352.

[1951] Jónsson, B. and Tarski, A., “Boolean algebras with operators. Part I”, American Journal of Mathematics, 73 (1951), pp. 891–939.

[1952] Jónsson, B. and Tarski, A., “Boolean algebras with operators. Part II”, American Journal of Mathematics, 74 (1952), pp. 127–162.

[1975] McKenzie, R. N., “On spectra, and the negative solution of the decision problem for identities having a finite nontrivial model”, Journal of Symbolic Logic, 40 (1975), pp. 186– 196.

[1991] Maddux, R. D., “Pair-dense relation algebras”, Transactions of the American Mathematical Society, 328 (1991), pp. 83–129.

[1996] Marx, M., Masuch, M., and Polos, L., eds.,, Arrow logic and multi-modal logic, Proceedings of the conference: Logic at Work, CSLI Publications, to appear.

[1995] Mikulás, Sz., Taming logics, doctoral dissertation, Institute for Logic, Language, and Computation, University of Amsterdam, Amsterdam, 1995, viii + 121 pp.

[1996] Mikulás, Sz., “Gabbay-style calculi”, in Proof theory of modal logic (editor: H. Wansing), Kluwer Academic Publishers, Amsterdam, 1996, to appear.

[1964] Monk, J. D., “On representable relation algebras”, Michigan Mathematical Journal, 11 (1964), pp. 207–210.

[1964a] Monk, J. D., “Singulary cylindric and polyadic equality algebras”, Transactions of the American Mathematical Society, 112 (1964), pp. 185–205.

[1970] Monk, J. D., “Completions of Boolean algebras with operators”, Mathematische Nachrichten, 46 (1970), pp. 47–55.

[1991] Monk, J. D., “Remarks on the problems in the books Cylindric Algebras, Part I and Part II and Cylindric Set Algebras”, in Algebraic logic (editors: H. Andréka, J. D. Monk, and I. Németi), North-Holland Publishing Company, Amsterdam, 1991, pp. 723–726.

[1991] Németi, I., “Algebraizations of quantifier logics, an introductory overview”, Studia Logica, 50 (1991), pp. 485–569. (A longer version of this article was published as: Preprint No. 50/1993, Mathematical Institute of the Hungarian Academy of Sciences, Budapest, 1993, 77 pp.)

[1973] Pinter, C. C., “A simple algebra of first order logic”, Notre Dame Journal of Formal Logic, 14 (1973), pp. 361–366.

[1990] Pratt, V., “Dynamic algebras as a well-behaved fragment of relation algebras”, in Algebraic logic and universal algebra in computer science (editors: C. H. Bergman, R. D. Maddux, and D. L. Pigozzi), Lecture Notes in Computer Science, vol. 425, Springer-Verlag, 1990, pp. 77–110.

[1982] Sain, I., Strong amalgamation and epimorphisms of cylindric algebras and Boolean algebras with operators, Mathematical Institute of the Hungarian Academy of Sciences, Budapest, 1982, 44 pp.

[1982a] Sain, I., “Weak products for universal algebra and model theory”, Diagrammes, 8 (1982), pp. S2–S15.

[1991] Sain, I. and Thompson, R. J., “Strictly finite schema axiomatization of quasi-polyadic algebras”, in Algebraic logic (editors: H. Andréka, J. D. Monk, and I. Németi), North-Holland Publishing Company, Amsterdam, 1991, pp. 539–571.

[1964] Sikorski, R., Boolean algebras, Ergebnisse der Mathematik und ihrer Grenzgebiete, new series vol. 25, Springer-Verlag, Berlin, 1964, x + 237 pp.

[1941] Tarski, A., “On the calculus of relations”, Journal of Symbolic Logic, 6 (1941), pp. 73–89.

[1952] Tarski, A., “A representation theorem for cylindric algebras (abstract)”, Bulletin of the American Mathematical Society, 58 (1952), pp. 65–66.

[1955] Tarski, A., “Contributions to the theory of models. III”, Koninklijke Nederlandse Akademie van Wetenschappen, Proceedings, Series A, Mathematical Sciences, 58 (=Indagationes Mathematicae, 17) (1955), pp. 56–64.

[1996] Venema, Y., Rectangular Games, Research Report No. 96-176, Mathematics Department, Victoria University of Wellington, 1996, 18 pp.