Csaba Henk

           (ekho@renyi.hu, www.renyi.hu/~ekho)

Axiomatizability properties of diagonal-free cylindric lattices, with special emphasis on

dimension two

Contents

0. Introduction 2 0.1. Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 0.2. Prerequisites, the structure of the paper . . . . . . . . . . . . . . . . . . . 2 0.3. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1. Basic definitions and their discussion 4

2. Tools for handling concrete algebras and other future schemes 12 2.1. Sketching the problems we will work on and the tools we will work with . . 12 2.2. Background for the diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3. Basic theory of ortho-cylindric relation algebras 21 3.1. Canonical representation and holes . . . . . . . . . . . . . . . . . . . . . . 21 3.2. Asymmetric equational theories . . . . . . . . . . . . . . . . . . . . . . . . 25 3.3. The elimination alternatives . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.4. The symmetric case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4. Representable asymmetric cylindric lattices of dimension two 35 4.1. Visualization of DL-congruences . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2. Axiomatizing RDf_{2}^{−} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

References 45

0. Introduction

0.1. Abstract

The present paper investigates the effect of discarding complementation from the operations of cylindric algebras (which are supposed to be diagonal-free, in order to start the story at the beginning). There are two ambiguities about the meaning of the previous sentence, both can be made exact in two different ways — thus totally we have four possibilities.

First of all, simply omitting complementation from the cylindric algebra-operations (Boolean operations and cylindrifications) we find that the algebraic operations which correspond to universal quantification (called axifications) will not be term-definable any more. Thus we have the possibility to ignore axifications or to include them as selfcontained operations. Fixing a positive integer n, in the first case we get the representable asymmetric cylindric lattices of dimension n (RDf_{n}^{−}), in the second case we get the representable symmetric cylindric lattices of dimension n (RDf_{n}^{±}) as the SP-closure of basic set algebras of dimension n.

However, these classes are not varieties, thus the description of the generated varieties (HRDf_{n}^{−}, HRDf_{n}^{−}) is a further problem.

(When we cite the following results, we will not distinguish between diagonal-included and diagonal-free versions, since they behave similarly in the investigated aspects.) Asymmetric cylindric lattices were investigated by Andréka and Németi (they proved in [AN] and [Andréka, Thm. 7.(ii)] that RDf_{n}^{−} is not a variety), Comer (he proved in [Comer] that RDf_{n}^{−} is not finitely axiomatizable for n ⩾ 3), and by Cosmadakis, Düntsch and Mikulás (they investigated database-theoretic applications of cylindric lattices in [Cosmadakis], [DM], [Düntsch]); as far as the author knows, the symmetric case has not been investigated in details.

The main results of this paper are the following:

• a finite quasi-equational axiomatization of RDf_{2}^{−} and RDf_{2}^{±} (Theorem 4.21. and Theorem ??);

• a finite equational axiomatization of HRDf_{2}^{−} (Theorem 4.3.);

• strong non-finitizability of axiomatization of HRDf_{n}^{±} for n ⩾ 2 and an equational axiomatization of HRDf_{2}^{±}.

0.2. Prerequisites, the structure of the paper

The theme of is paper belongs to the discipline of algebraic logic. It deals with algebras of relations produced in a similar way to cylindric algebras. Therefore we expect the reader to be familiar with the following prerequisites:

• the basic notions of first-order logic;

• the basic notions and theorems of universal algebra;

• formally the results are comprehensive in case of knowing the above asked material, but comprehension of motivations, analogies and examples will require the basic theory of cylindric algebras.

The reader may consult the following books:

• regarding first-order logic: [CK];

• regarding universal algebra: [BS], [ANS b];

• regarding cylindric algebras: [HMT1], [HMT2], [ANS a].

By and large, our notations and conventions will follow [HMT1], though sometimes we will deviate from these. At the beginning of each section we will summarize our special Notations, conventions introduced through that section.

The certain sections contain the following material:

In Section 1. we define the basic notions and establish some basic facts about them. After we made us able to use these notions in Section 1., at the beginning of Section

2. we sketch the problems motivating us, and after that we give a background for a tool with which we can picture finite cylindric lattices: cylindric lattice diagrams.

In Section 3. we discuss the basic properties of a kind of generalization of cylindric lattices of dimension two: of the ortho-cylindric lattices.

Using these properties, we will be able to verify the axiomatization of RDf_{2}^{−}, which is done in Section 4.

Section 5. starts with the axiomatization of RDf_{2}^{±} (quite similar to the axiomatization of RDf_{2}^{−}). Then we prove some strong non-finitizability results about axiomatization HRDf_{n}^{±} (n ⩾ 2) and the paper ends with the axiomatization of HRDf_{2}^{±}.

0.3. Acknowledgements

1. Basic definitions and their discussion

Notations, conventions.

BA will denote the class of all Boolean algebras and DL will denote the class of all distributive lattices. Whenever we speak of distributive lattices we mean bounded distributive lattices (i.e. distributive lattices with smallest element and greatest element) of similarity type ⟨∧, ∨, 0, 1⟩.

If U is a set, then 𝔓(U) denotes the powerset Boolean algebra over U, and 𝔓^{−}(U) denotes the DL-reduct of 𝔓(U).

The operators on classes of algebras – P (closure w.r.t. product algebras), S (closure w.r.t. taking subalgebras), Up (closure w.r.t. ultraproducts), and, of course, H (closure w.r.t. taking homomorphic pictures) – are meant to include isomorphic copies of algebras as well; [ ·]_{t} will stand for “reducing to subtype t”.

Boolean operations: ∖x will denote the complement of x and y ∖ x = y ∩ (∖x) will denote the difference of y and x; a single ∖ without argument will refer to the unary operation of complementation.

If n is a non-negative integer, then by k < n we mean k is a non-negative integer lesser than n.

Sometimes our notation will not distinguish between structures and their base set.

We start with introducing the notions specific to the present paper.

Sometimes a good definition amounts to half of a theorem. We will perform our definitions with this idea in mind. Therefore some of our definitions will deviate a bit from the traditional style; however, we will clarify the connection between these and their classical variants. First of all we sketch

the classical set-up as a starting point, and then the question motivating us.

In the following we will show, how the classical approach constructs a typical class of relation algebras: diagonal-free cylindric algebras of dimension n.

Definition 1.1. Let n be a positive integer, and R be an n-ary relation.

The set of the k-th co-ordinates occuring in R will be called the k-th co-ordinate set of R; in other terms, the k-th co-ordinate sets of R (k = 0, …, n − 1) are the narrowest U_{0}, …, U_{n−1} sets, for which R ⊆ U_{0} × … × U_{n−1}. R is a brick of dimension n if it is of the form U_{0} × … × U_{n−1} for some sets U_{k}, k = 0, …, n − 1.

For each k < n we define the operation c_{k}^{R} : 𝒫(R) ⟶ 𝒫(R) as follows: for arbitrary X ⊆ R

c_{k}^{R}X = {⟨u_{0}, …, u_{n−1}⟩ ∈ R | ∃v_{k} ∈ U_{k} ⟨u_{0}, …, u_{k−1}, v_{k}, u_{k+1}, …, u_{n−1}⟩ ∈ X};

we call c_{k}^{R} the k-th cylindrification (w.r.t. R). _{□}

If it is not confusing, we may omit the superscript R; in [HMT2] these operations are called generalized set-theoretic cylindrifications and are denoted by C_{k}^{[R]}.

The algebraic similarity type Df_{n} – “diagonal-free cylindric similarity type of dimension n” – consists of the Boolean operation-symbols and the c_{0}, …, c_{n−1} unary cylindrification symbols. If R is an n-ary relation, then the Df_{n}-type algebra ⟨𝔓(R), c_{k}^{R}⟩_{k<n} will be called the full diagonal-free cylindric algebra over R and will be denoted by 𝔓_{Df}(R).

In the classical approach the algebras of the form 𝔓_{Df}(B), where B is a brick, provide the generic diagonal-free cylindric algebras. The class of the unholed diagonal-free cylindric algebras of dimension n is built up from these in the following way:

UhDf_{n} =^{def} S {𝔓_{Df}(B) | B is a brick of dimension n} ,

and the representable diagonal-free cylindric algebras of dimension n are the elements of the class

RDf_{n} =^{def} SPUhDf_{n}.

In what sense are these algebras representable? We will say an algebra (of type Df_{n}) is representable over the n-ary relation R if it can be embedded in 𝔓_{Df}(R). (We will use this terminology for other similarity types as well.) For n ⩾ 2 the algebras of RDf_{n} are those algebras which can be represented over (the n-dimensional analogue of) an equivalence relation:

That is, if n ⩾ 2 and for i ∈ I R_{i} is an n-ary relation, then ∏_{i∈I} 𝔓_{Df}(R_{i}) is isomorphic with 𝔓_{Df} (R), where R is the disjoint union of the R_{i}-s (by disjoint union of relations we mean the following construction: their co-ordinate sets are made pairwise disjoint, and after the adequate co-ordinate changes we form the union of our relations thinking of them as sets of ordered pairs). (In such cases we will say that we got R by stringing the R_{i}-s to a diagonal line, and we will call this procedure the stringing method. In dimension two it is quite descriptive; our terminology suggests that how the reader should visualize it.) So an algebra of RDf_{n} is representable over an n-ary relation produced by the stringing method from bricks of dimension n (we will call such relations block-diagonal). And a binary relation R is an equivalence relation iff for suitable U_{i}-s we can get R by stringing the U_{i} × U_{i}-s to a diagonal line. (The reader can confer these with [HMT2, Def. 5.1.33. and Thm. 5.1.38./(i)]; here UhDf_{n} is denoted by ICsdf_{n} and RDf_{n} is denoted by IGsdf_{n}.)

Our aim is to investigate what happens if we deviate from the classical set-up in omitting complementation. (If we consider the correspondance between various kind of relation algebras and logical systems, then RDf_{n} (where n runs from one to infinity) is the algebraic counterpart of (equality-free) first order logic, and the algebraic reduction of omitting complementation corresponds to discarding negation from the connectives.) So we define the first subject to our investigations:

Definition 1.2. The algebraic similarity type Df_{n}^{−} – “(diagonal-free) asymmetric cylindric similarity type of dimension n” – consists of the lattice operation-symbols and the c_{0}, …, c_{n−1} unary cylindrification symbols. If R is an n-ary relation, then the Df_{n}^{−}-type algebra ⟨𝔓^{−}(R), c_{k}^{R}⟩_{k<n} will be called the full (diagonal-free) asymmetric cylindric lattice over R and will be denoted by 𝔓_{Df}^{−}(R).

The class of the unholed (diagonal-free) asymmetric cylindric lattices of dimension n is

UhDf_{n}^{−} =^{def} S {𝔓_{Df}^{−}(B) | B is a brick of dimension n} ,

and the representable (diagonal-free) asymmetric cylindric lattices of dimension n are the elements of the class

RDf_{n}^{−} =^{def} SPUhDf_{n}^{−}.

An algebra of type Df_{n}^{−} is an asymmetric relation algebra of dimension n if it can be represented over some n-ary relation. _{□}

In this paper any time we speak about cylindric lattices an related structures, we assume they are diagonal-free, this is why we parenthesized the attribute “diagonal-free”.

In case we have complementation, the algebraic operations corresponding to universal quantification can be defined by the term ∖ c_{k}(∖x) (in [HMT1] these are called inner cylindrifications and are denoted by c_{k}^{∂}). This term-definiton is not accesible in lack of complementation; in RDf_{n}^{−} we have no term-defined operation corresponding to universal quantification. Though when setting up a negation-free first-order logic we may want universal quantification to be included. So we introduce the algebraic counterpart of universal quantification as self-contained operations:

Definition 1.3. Let R be an n-ary relation with co-ordinate sets U_{k} (k < n). Then for each k < n we define the operation a_{k}^{R} : 𝒫(R) ⟶ 𝒫(R) as follows: for arbitrary X ⊆ R

a_{k}^{R}X =^{def} {⟨u_{0}, …, u_{n−1}⟩ ∈ R | ∀v_{k} ∈ U_{k} ⟨u_{0}, …, u_{k−1}, v_{k}, u_{k+1}, …, u_{n−1}⟩ ∈ X} =

∖c_{k}^{R}(∖X);

we call a_{k}^{𝒰} the k-th axification (w.r.t. 𝒰). _{□}

If it is not confusing, we may omit the superscript R.

Again we can set the analogous definitions:

Definition 1.4. The algebraic similarity type Df_{n}^{±} – “(diagonal-free) symmetric cylindric similarity type of dimension n” – consists of the lattice operation-symbols, the c_{0}, …, c_{n−1} unary cylindrification symbols, and the a_{0}, …, a_{n−1} unary axification symbols. If R is an n-ary relation, then the Df_{n}^{±}-type algebra ⟨𝔓^{−}(R), c_{k}^{R}, a_{k}^{R}⟩_{k<n} will be called the full (diagonal-free) symmetric cylindric lattice over R and will be denoted by 𝔓_{Df}^{±}(R).

The class of the unholed (diagonal-free) symmetric cylindric lattices of dimension n is

UhDf_{n}^{±} =^{def} S {𝔓_{Df}^{±}(B) | B is a brick of dimension n} ,

and the representable (diagonal-free) symmetric cylindric lattices of dimension n are the elements of the class

RDf_{n}^{±} =^{def} SPUhDf_{n}^{±}.

An algebra of type Df_{n}^{±} is a symmetric relation algebra of dimension n if it can be represented over some n-ary relation. _{□}

Just like in the RDf-case, for n ⩾ 2 the representable algebras (in both of the asymmetric and the symmetric cases) are representable over an n-ary block-diagonal relation.

For ∗ ∈ {−, ±} an alternative definition of RDf_{n}^{∗} is the following: RDf_{n}^{∗} = S[RDf_{n}]_{Df}_{n}^{∗}.

Now, before getting ahead, because of technical reasons we will have to execute the logical analysis of the notion of relation. Well, the previous sentence is half a joke. Calling the “logical analysis of the notion of relation” what we will do, is a bit exaggerating description, and the reasons for doing so are not simply technical.

What means “being a relation?” A relation is a set consisting of points – very special kind of points: n-tuples (for some n). However, the objects which modern mathematics deals with, are constructed in the spirit of a different philosophy: they follow the “structure” scheme: they consist of a base set, and there are some subsets of the base set, relations, functions on the base set, family of sets over the base set, etc. attached to this.

Here the points of the base set have no inner structure, their identity does not matter, what matters is the connection among them, which is encoded in the attached entities.

In case we intend to examine relations on their own right, it is quite an obvious idea that they should be interpreted in the above manner. What kind of connection could be among the points of a relation? “Relation” is a quasi-geometric notion: usually we imagine it as some kind of potato-shape embedded in the n-dimensional space (for the appropiate n). Then we can say things like “these points have the same k-th co-ordinate”, thus if there is given an n-ary relation, then to each k from 0 to n − 1 we can associate an equivalence on the points of the relation; and this language is rich enough to express each kind of properties of relations.

Definition 1.5. Let n be a positive integer.

A relation-imitating structure of dimension n, for short rist_{n}, is a first-order structure with similarity type ⟨≡_{0}, …, ≡_{n−1}⟩ where the ≡_{k}-s (k < n) are binary relation symbols and should be interpreted to equivalence relations. ≡_{k} is advised to be read as “the k-th projection kernel”, and its classes will be referred to as k-fibres.

A strict relation-imitating structure of dimension n, for short strist_{n}, is a relationimitating structure of dimension n which fulfils the following axiom:

(x ≡_{0} y & … & x ≡_{n−1} y) ⇒ x = y

If we do not need specifying dimension, we can use the general abbreviations rist, strist. _{□}

In a sense strict relation-imitating structures correspond to relations.

Formally, let R be an n-ary relation with co-ordinate sets U_{k} (k ∈ n). Then we can interpret ≡_{k} on R such that ⟨u_{0}, …, u_{n−1}⟩ ≡_{k} ⟨u′_{0}, …, u′_{n−1}⟩ ⟺ u_{k} = u′_{k}. Then R with these projection kernels forms a strist_{n}, and the identity of R is a one-to-one correspondence between the original relation and this strist, to which we will refer as the strist corresponding to R.

And if 𝒰 = ⟨U, ≡_{k}⟩_{k<n} is a strist_{n}, then for k < n let U_{k} be the set of the k-fibres. Consider the following relation ⊆ U_{0} × … × U_{n−1}: {⟨u/ ≡_{0}, …, u/ ≡_{n−1}⟩ | u ∈ U}. Since 𝒰 is strict, u ↦ ⟨u/ ≡_{0}, …, u/ ≡_{n−1}⟩ is a one-to-one correspondence between the original strist and this relation, to which we will refer as the relation corresponding to 𝒰.

If we have a relation R with co-ordinate sets U_{0}, …, U_{n−1}, then after executing the first correspondance on R giving a strist and then executing the second one, we get a relation R′ which is “almost the same as R”, i.e. the mapping induced by the co-ordinate changes u_{k} ↦ {those points in R the k-th co-ordinate of which is u_{k}} (u_{k} ∈ U_{k}) is a one-to one correspondece between R and R′.

And if we have a strist 𝒰, then after executing the first correspondance on 𝒰 giving a relation and then executing the second one, we get a strist 𝒰′, which is “almost the same as 𝒰”, i.e. the composition of the two one-one correspondences belonging to the transformations gives an isomorphism between 𝒰 and 𝒰′.

Thus if we introduce a notion to rists, applying it to relations makes sense, by a relation meaning the strist corresponding to him. And the notions introduced to relations usually can be naturally interpreted to rists — rists just been introduced in order to settle the linguistic frames to which we keep ourselves when we speak about relations; as we will see, this minimal concept results a behaviour quite similar to relations’. For example, we can extend the notions of cylindrification, axification to the relation-imitating context in the following way:

Definition 1.6. Let 𝒰 = ⟨U, ≡_{k}⟩_{k<n} be a rist_{n}. Then for each k < n we define the operation c_{k}^{𝒰} , a_{k}^{𝒰} : 𝒫(U) ⟶ 𝒫(U) as follows: for arbitrary X ⊆ U

c_{k}^{𝒰} X =^{def} {u ∈ U | (∃u′ ∈ U)(u ≡_{j} u′ (j ≠ k) & u′ ∈ X)} = X/ ∩_{j≠k} ≡_{j},

a_{k}^{𝒰} X =^{def} {u ∈ U | (∀u′ ∈ U)(u ≡_{j} u′ (j ≠ k) ⇒ u′ ∈ X)} = ∖c_{k}^{𝒰} (∖X),

and we call these also as cylindrification, axification. _{□}

(If it is not confusing, we may omit the superscript 𝒰; besides, if we introduce a rist 𝒰, we will refer to its base set with U.) This extension is correct: as we can see, for a relation R the old definition for c_{k}^{R}, a_{k}^{R}, and the one coming from the relation-strist correspondance give the same notion.

This way the notions 𝔓_{Df}, 𝔓_{Df}^{∗} (∗ ∈ {−, ±}) naturally extend to rists: if 𝒰 is a rist_{n}, 𝔓_{Df}(𝒰) = ⟨𝔓(U), c_{k}^{𝒰} ⟩_{k<n}, and similarly for the other two types.

If R is an n-ary relation, and U_{0}, …, U_{n−1} are its co-ordinate sets, then we could call the points of U_{0} × … × U_{n−1} ∖ R the holes of R; and we can see that if R has no holes in this sense, then R is a brick. Extending this idea to rists:

Definition 1.7. Let 𝒰 be a rist_{n}. By a hole of 𝒰 we mean an n-tuple ⟨F_{0}, …, F_{n−1}⟩ where for k < n F_{k} is a k-fibre and F_{0} ∩ … ∩ F_{n−1} = ∅.

We say 𝒰 is unholed, if it has no hole. _{□}

This extension is correct: we can see that if 𝒰 is a strist_{n}, and R is the corresponding relation with co-ordinate sets U_{0}, …, U_{n−1}, then the holes of 𝒰 are just the points of U_{0} × … × U_{n−1} ∖ R. And by the relation-strist correspondance, brick is “just the same as” unholed strist. Thus we can also say:

UhDf_{n} = S {𝔓_{Df}_{⊥}(𝒰) | 𝒰 is an unholed strist_{n}} ,

and for ∗ ∈ {−, ±},

UhDf_{n}^{∗} = S {𝔓_{Df}_{⊥∗}(𝒰) | 𝒰 is an unholed strist_{n}} .

For cylindric lattices we introduce the following alternate versions, this time also considering non-strict relation-imitating structures:

Definition 1.8. For ∗ ∈ {−, ±} let

Uh′Df_{n}^{∗} =^{def} S {𝔓_{Df}^{∗}(𝒰) | 𝒰 is an unholed rist_{n}} ,

and

R′Df_{n}^{∗} =^{def} SPUh′Df_{n}^{∗}.  _{□}

The notions “representability over a rist”, “stringing rists”, “block-diagonal rist” are clear, just like the statement that algebras of R′Df_{n}^{∗} can be represented over block-diagonal rists, so instead of going into details we give some explanation why we intoduced these comma versions:

Let ∗ ∈ {−, ±}. We will see that the notion of R′Df_{n}^{∗} is easier to handle than of RDf_{n}^{∗}: the representation of an abstractly defined algebra is easier if the representating relation-imitating structure need not be strict, moreover, this way the representation gets rid of a bunch of superfluous redundancy, and to a broad class of algebras we will be able to define a canonical representation. This is the use of the notion “relation-imitating structure” (cf. Remark 3.9.).

However, our motivations lead us to the examination of relation algebras, not of algebras over relation-imitating structures. This difficulty is solved by the observation that it is quite the same whether we represent over relations or over relation-imitating structures: UhDf_{n}^{∗} = Uh′Df_{n}^{∗} (and then, of course, RDf_{n}^{∗} = R′Df_{n}^{∗}).

The idea of the proof can be illustrated through the following example.

Consider the rist_{3} 𝒰 = ⟨ℝ, ≡_{0}, ≡_{1}, ≡_{2}⟩ where the ≡_{k}-s are the full equivalence — this means the cylindrifications map each non-empty subset to ℝ, and the axifications map each non-full subset to ∅. And 𝒰 is obviously unholed. How could we represent 𝔓_{Df}^{±}(𝒰) over a brick of dimension three?

Let f be the ℝ ⟶ 𝒫(ℝ^{3}) function which maps r to the plane given by the equation x + y + z = r. Then f is a bijection between ℝ and a partition of ℝ^{3}, so it extends to the generated complete DL’s, let this extension be φ. In other words, for X ⊆ ℝ φ(X) = ⋃_{r∈X} f(r). This φ is the desired representing function: of course, it is a DLisomorphism; and in each direction the ℝ^{3}-cylindrification of a set containing a plane of the form x + y + z = r is ℝ^{3}; and if a set consisting of planes of the form x + y + z = r contains a line being parallel with any of the x, y, z axes, then it must be ℝ^{3}, so φ preserves axifications as well.

If we have a rist 𝒰, then ≡_{0} ∩ … ∩ ≡_{n−1}= {⟨u, u′⟩ ∈ U^{2} | ∀k < n u ≡_{k} u′} is an equivalence relation; let us call the classes of this molecules. The 𝒰 of the above example consisted of one big molecule; the procedure we applied at the representation will be called “inflating the molecules into bricks”.

This is what we will do in a higher level of generality in the following Interpretation Lemma; the same method is applied at representation of algebras resulted by splitting atoms, cf. [Andréka, pp. 156-159].

Lemma 1.9. (Interpretation Lemma) For ∗ ∈ {−, ±} and n > 0 UhDf_{n}^{∗} = Uh′Df_{n}^{∗}.

Proof. UhDf_{n}^{∗} ⊆ Uh′Df_{n}^{∗} obviously.

We will prove the “⊇” direction for the case ∗ = ±; we can get the proof for the ∗ = − case simply by forgetting that what is said about axifications in the following proof.

Let 𝒰 = ⟨U, ≡_{k}⟩_{k<n} be an unholed rist_{n}; to see UhDf_{n}^{∗} ⊇ Uh′Df_{n}^{∗}, we have to represent 𝔓_{Df}^{±}(𝒰) over a brick of dimension n. So we have to find some sets U_{0}, …, U_{n−1} and a φ embedding of 𝔓_{Df}^{±}(𝒰) into 𝔓_{Df}^{±}(U_{0} × … × U_{n−1}).

If we have a rist we will treat subsets of it as rists with the restricted projection kernels. Assume that we can represent every molecule μ of 𝒰 over an n-th Cartesian power,

i.e. we have a set W and for every molecule μ an embedding φ_{μ} : 𝔓_{Df}^{±}(μ) ⟶ 𝔓_{Df}^{±}(W^{n}) with image 𝔄_{μ}. In other terms: φ_{μ} is a 𝔓^{−}(μ) ⟶ 𝔓^{−}(W^{n}) embedding and the image 𝔄_{μ} ⊧ x ≠ 0 ⇒ c_{k} x = 1, x ≠ 1 ⇒ a_{k} x = 0.

In this case we can put together these small representations to a big one, formally done in the following way:

V_{k} will denote the set of the k-fibres, and if μ is a molecule, by μ/ ≡_{k} we will mean the well defined k-fibre in which μ is contained (and not the singleton containing this fibre, as it would happen if we properly used notations). Now for U_{k} we choose V_{k} × W, and for X ⊆ U we let

φ(X) = ⋃_{μ is a molecule} {⟨⟨μ/ ≡_{0}, w_{0}⟩ , …, ⟨μ/ ≡_{n−1}, w_{n−1}⟩⟩ | ⟨w_{0}, …, w_{n−1}⟩ ∈ φ_{μ}(X ∩ μ)} .

It is easy to see that this is an embedding of 𝔓_{Df}^{±}(𝒰) into 𝔓_{Df}^{±}(U_{0} × … × U_{n−1}).

So what is remained to prove is the following: (†) if we have a set W and 𝔇 ⩽ 𝔓^{−}(W), and for k < n we define the functions c_{k}, a_{k} : 𝔇 ⟶ 𝔇 as c_{k} is the switching-on function (c_{k} 0 = 0, for x ≠ 0 c_{k} x = 1), and a_{k} is the switching-off function (a_{k} 1 = 1, for x ≠ 1 a_{k} x = 0), then 𝔄 = ⟨𝔇, c_{k}, a_{k}⟩_{k<n} can be represented over W^{n}; since if (†) is true, we can choose a W being big enough for that for every molecule μ of 𝒰 𝔓^{−}(μ) can be embedded into 𝔓^{−}(W), and then we can apply (†) in the cases 𝔇 = 𝔓^{−}(μ).

To see (†), let 𝒜 be an Abelian group on W. The “hyperplanes” of the form H_{a} = {⟨a_{0}, …, a_{n−1}⟩ | a_{0} + … + a_{n−1} = a} (where a ∈ W) form a partition of W^{n}, so the mapping ψ = ⟨Q ↦ ⋃_{a∈Q} H_{a}⟩_{Q⊆W} is an embedding 𝔓(W) ⟶ 𝔓(W^{n}). Since for any

k < n and a ∈ W, at arbitrary fixed choice of x_{j} (j ≠ k) and searching for x_{k}, the equation “x_{0} + … + x_{n−1} = a” can be solved in 𝒜, for any Q ⊆ W, Q ≠ ∅ c_{k} ψ(Q) = W^{n}. And if Q is not the maximal element of 𝔓^{−}(W), then ∖Q ≠ ∅, so a_{k}(ψ(Q)) = ∖ c_{k}(∖ψ(Q)) = ∖ c_{k}(ψ(∖Q)) = ∖W^{n} = ∅.

This means that ψ is the desired embedding of 𝔄 in the 𝔇 = 𝔓^{−}(W) case. Then, of course, its appropiate restriction is the desired embedding for any 𝔇 ⩽ 𝔓^{−}(W). This completes the proof of the lemma. _{■}

In fact, by inflating moleculas into bricks we can see that an algebra of type Df_{n}^{∗} can be represented over an n-ary relation/ block-diagonal n-ary relation/ brick iff it can be represented over a rist_{n}/ block-diagonal rist_{n}/ unholed rist_{n}.

From now on we will not use the notations Uh′Df_{n}^{∗}, R′Df_{n}^{∗}. We will speak about UhDf_{n}^{∗}, RDf_{n}^{∗}, and the definitions of the comma versions will be treated as alternate (and useful) definitions for these.

Remark 1.10. The equivalence of the two formulations – using rists and using relations – does not hold at the presence of the diagonal constants. In the diagonal-free case if we have an algebra over a relation-imitating structure, and we want to represent it over a relation (i.e. over a strict relation-imitating structure), we can do it, because the molecules has no special inner structure which could prevent it. If diagonals are also included, then the molecules “around the diagonals” can have defections which prevent regular representrations over relations (cf. [HMT2, pp. 79-84]). _{□}

Remark 1.11. We defined holes of a rist and unholedness of a rist. We also defined unholedness of an algebra (being representable over an unholed rist), though we did not define anything like a hole of an algebra. We will be able to do this in an analogous situation (for ortho-cylindric algebras), in Section 3. (cf. Definition 3.4., Remark 3.5.); at this point the usefulness of using rists will turn out. _{□}

Remark 1.12. The state of the notion of hole in cylindric algebra theory is similar to the state of the notion of prime in ring theory: primes are interesting only in those rings where division cannot be executed, i.e. which are not fields. And holes are interesting concerning those cylindric lattices, where complementation cannot be executed, i.e. which are not cylindric algebras.

For example, consider the following situation: let 𝒰 be a rist_{2} such that it cannot be decomposed by the stringing method (that is, for X ⊆ U X = c_{0} X = c_{1} X implies X = ∅ or X = U), and 𝔄 ⩽ 𝔓_{Df}(𝒰) — such algebras are ones “without superfluous holes”, since each algebra of type Df_{2}, which are representable over some rist_{2}, can be subdirectly decomposed to such ones which can be seen using the stringing method. The following three are equivalent: 𝔄 ∈ UhDf_{2}, 𝔄 ∈ RDf_{2}, and 𝔄 ⊧ c_{0} c_{1} x = c_{1} c_{0} x (and if these are fulfilled, then 𝔄 is simple). Thus if 𝔄 is not unholed (i.e., anyhow we represent 𝔄 over a rist, it must have some holes), then it is obvious from a sharp intrinsic feature: cylindrifications do not commute.

However, if 𝔄 is a cylindric lattice (whether symmetric or asymmetric), that is, 𝔄 ⩽ 𝔓_{Df}^{∗}(𝒰), where ∗ ∈ {−, ±} and 𝒰 is a rist_{2} having the above property, then only the following implications hold: 𝔄 ∈ UhDf_{2}^{∗} ⇒ 𝔄 ∈ RDf_{2}^{∗} ⇒ 𝔄 ⊧ c_{0} c_{1} x = c_{1} c_{0} x (and even subdirect irreducibility is independent from these properties). So when we examine representable cylindric lattices, we cannot exclude those 𝔄-s, which are not unholed. _{□}

2. Tools for handling concrete algebras and other future schemes

Notations, conventions.

If f is a function A ⟶ B, then f^{⊃} will denote the induced mapping 𝒫(A) ⟶ 𝒫(B), that is, for X ⊆ A f^{⊃}X = {f(x) | x ∈ X};

Compositions are meant to develop from right to left (that is, for some functions f, g (f ∘ g)(x) = f(g(x)), and similarly for relations).

2.1. Sketching the problems we will work on and the tools we will work with

This article intends to examine axiomatizability questions concerning the cylindric lattices defined in the previous section. Besides the naturally arising question – finding an axiomatization of the examined class of structures – we can pose questions concerning the possible ways of axiomatization, the complexity of axiom systems describing the class. One such question is whether can the examined class be axiomatized with a given type of formulas. The basic feature we usually claim from an algebraically relevant class of structures is axiomatizability with quantifier-free formulas. However, in our case we examine finer criteria: axiomatizability with equations (with other words, being a variety), and axiomatizability with quasi-equations (formulas of the form (&_{i} σ_{i} = τ_{i}) ⇒ σ = τ)(with other words, being a quasi-variety).

Theorem 2.1. For ∗ ∈ {−, ±} RDf_{n}^{∗} is a quasi-variety.

Proof. From the notion of representability immediately follows that RDf_{n}^{∗} = S[RDf_{n}]_{Df}_{n}^{∗}, and we know that RDf_{n} is a variety (the reader can find a proof for this in [HMT2, Thm. 5.1.43.]; or in [ANS a, Thm. 2. and Lem. 5.] there is a quite simple proof in a similar case (for BRA), using pseudo-axiomatizability). So what we have to prove is a special case of the following statement: if t ⊆ t′ are algebraic similarity types and Q is a quasi-variety of type t′, then S[Q]_{t} is also a quasi-variety.

This statement is true because of the following: We know that being a quasi-variety means being closed w.r.t. taking subalgebras, taking products and taking ultraproducts (cf. [BS], [ANS b]). Of course, S[Q]_{t} is closed w.r.t. taking subalgebras. And since Q is closed w.r.t. taking products and ultraproducts, S[Q]_{t} is also closed w.r.t. these.^{⋆} _{■}

However, for n ⩾ 2 RDf_{n}^{∗} is not a variety. (see Theorem 4.6.; a very similar result is proved in [Andréka, Thm. 7.] and in [AN]. We will immediately make more comments on this problem, after a short bypass concerning the other classic measure of the complexity of axiomatizations: the question of finite axiomatizability.

RDf_{2}^{∗} is finitely axiomatizable: in Theorem 4.21. and Theorem ?? we will give a finite quasi-equational axiomatization for RDf_{2}^{∗}.

Lemma 2.2. If 𝔄 ∈ Df_{n}, then 𝔄 is representable iff [𝔄]_{Df}_{n}^{∗} is representable (∗ ∈ {−, ±}).

⋆This theorem can be proved directly, using pseudo-axiomatizability, like in [ANS a, Thm. 2. and Lem.

Proof. Any isomorphism from 𝔄 commutes with [ ·]_{Df}_{n}^{∗}, from which follows direction (→).

Direction (←): of course [𝔄]_{Df}_{n}^{∗} ⊧ ∃!y(x ∧ y = 0 & x ∨ y = 1), so complementation can be recovered by the formula φ ≡ x ∧ y = 0 & x ∨ y = 1. If we embed [𝔄]_{Df}_{n}^{∗} into the full cylindric lattice of type Df_{n}^{∗} over some rist_{n} – let this full cylindric lattice be 𝔅 – by f, 𝔅 will be complemented as well and the same φ will recover complementation of 𝔅. Since φ is quantifier-free, the two formula-defined operations – the one which is defined on 𝔅, and the one which is inherited from [𝔄]_{Df}_{n}^{∗} by f – will coincide on Im f, so we get ⟨𝔅, ∖⟩ ⩾ ⟨Im f, ∖⟩ ≃ 𝔄, which means the representability of 𝔄. _{■}

Theorem 2.3. For n ⩾ 3 RDf_{n}^{∗} is not finitely axiomatizable (∗ ∈ {−, ±}).

Proof. Let n be at least 3. We know that the class RDf_{n} is axiomatizable, though is not finitely axiomatizable (cf. [Johnson]), and that Df_{n} is given by finitely many axioms; it means for some index-set I we can choose an 𝔄_{i} from Df_{n}∖RDf_{n} (i ∈ I) and an ultrafilter ℱ on I such that ∏_{i∈I} 𝔄_{i} / ℱ ∈ RDf_{n}.

Then by the former Lemma, for i ∈ I [𝔄_{i}]_{Df}_{n}^{∗} ∉ RDf_{n}^{∗}, though ∏_{i∈I} [𝔄_{i}]_{Df}_{n}^{∗} / ℱ ∈ RDf_{n}^{∗},

which means RDf_{n}^{∗} is not finitely axiomatizable. _{■}

Finer results in this direction – e.g. the non-existence of quantifier-free axiomatization using finitely many variables – can be adjusted from classical cylindric algebra theory (cf. [Andréka], [Jónsson]) to the present situation using Lemma 2.2. (as it is done in a very similar case in [Comer]).

Also arises the question whether the generated varieties (HRDf_{n}^{∗}) are finitely axiomatizable. For HRDf_{n}^{−} (n ⩾ 3) we do not know the answer; we will prove that HRDf_{2}^{−} can be axiomatized finitely and that for n ⩾ 2 (!) HRDf_{n}^{±} is not finitely axiomatizable (moreover, we will prove that the latter has not quantifier-free axiomatizaton using finitely many variables, and we will still give an axiomatization for this; cf. Theorems 3.20., 4.3., ??, ??) (the n = 1 cases are always trivial).

Now we would like to improve the tools with the help of which we can prove RDf_{n}^{∗} (n ⩾ 2) is not a variety. A quasi-variety is a variety iff it is closed w.r.t. taking homomorphic images. So we can prove being not variety by showing an algebra from the class and a congruence on it factorizing with which we get out of the class in question.

To show that RDf_{n}^{∗} (n ⩾ 2) is not a variety it is sufficient to show that RDf_{2}^{∗} is not a variety, since the two-dimensional case is a special case of the higher dimensional case: in type Df_{n} choosing a some way “dummy” cylindrification for c_{2}, …, c_{n−1} we get something equivalent to the two-dimensional case.

Thus we ought to find the adequate apparatus to be able to show examples and counter-examples in dimension two. We will present our algebras with a kind of diagram, which we will call cylindric lattice diagram. We will give here two examples of cylindric lattice diagrams, and then we will explain how to read it:

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

(Figure 2.4.)  (Figure 2.5.)

We will see that in dimension two the basic properties of representable cylindric lattices imply representability over some rist (which has not be unholed or block-diagonal). So first of all we intend to picture rist_{2}-s. This is easy to do: to the horizontal (0th) axis we put points representing the 0-fibres, to the vertical (1st) axis we put points representing the 1-fibres. Thus using the 0-, 1-fibres of a point of the base set as co-ordinates, we can find the appropiate place for the point in the system of co-ordinates spanned by the two axes. (In case of our rist is not strict, then we will find some positions in the system of co-ordinates where there are several points put; this does not happen in the above examples.) If it is not confusing, we may omit the axes from our diagram. We may use indices in order to be able to refer to the certain points.

The next step is to show up some way those subsets of the base set which are contained in the lattice.

We can observe that preorders (transitive and reflexive binary relations) define lattice structures over the base set: the downward sets w.r.t. the preorder (denoting the preorder by ⇾ – then u ⇾ v can be read as “u is bigger than v (by the preoder)” –, a set X is downward if it fulfils the criteria X ∋ u ⇾ v ⇒ v ∈ X) are closed w.r.t. taking unions and intersections. Moreover, any finite distributive lattice can be presented this way. So if a finite lattice of type Df_{2}^{∗} fulfils some basic requirements, it can be pictured in such a diagram: some points in a system co-ordinates, and a preoder in the points. In case of the preoder is anti-symmetric, i.e. it is a partial order – just like in our above examples –, then it can be given by the usual way, with a poset diagram on the points, pulling arrows between the neighbouring points (the arrows meant to go from “up” to “down”). This case the downward sets – the elements of the algebra – can be seen as those sets from which no arrows go out.^{⋆}

However, at this point it is not clear that putting a preorder on a rist_{2}, we define a cylindric lattice of type Df_{2}^{−} or Df_{2}^{±} or not: the lattice defined by the preorder is not necessarily closed w.r.t. cylindrifications or axifications. We will state exactly and prove the following statement: a lattice defined by a preorder is closed w.r.t. cylindrifications iff the preoder (in some sense) can be factorized with ≡_{0} and ≡_{1} (and the lattice is closed w.r.t. axifications iff the converse of the preorder can be factorized with the projection kernels). So if we define an algebra of type Df_{2}^{∗} with a cylindric lattice diagram, and we display the axes, we will also display the factors of the preorder on the axes.

Now it should be clear how and which lattices are defined by the above diagrams (Figure 2.4. defines an asymmetric cylindric lattice and Figure 2.5. defines a symmetric one), so the enterprising reader may try to prove that the lattice of Figure 2.4. is of HUhDf_{2}^{−} ∖ RDf_{2}^{−} and that the lattice of Figure 2.5. is of RDf_{2}^{±} ∖ HUhDf_{2}^{±}.

⋆We need not mind how to portray ⇾ if it is not a partial order since we will use only partial orders — cf. Theorem 3.10.

As we said, the basic counter-examples are and can be shown in dimension two; moreover, dimension two has some special properties — these motives for following the two dimensional case with peculiar attention.

Thus we will improve tools for dimension two; concerning cylindric lattices these will work only for dimension two. Yet there is a kind of generalization of cylindric lattices of dimension two and concerning them, these tools will also work. This generalization will be the concept of ortho-cylindric lattices. These are “weaker” algebras than the cylindric ones (cf. Lemma 2.8.); the reason for introducing them is to show up in what respect is dimension two special.

The following notions will be introduced directly using rists, so here we will not need claims similar to Interpretation Lemma.

Definition 2.6. Let 𝒰 be a rist_{n}. Then for each k < n we define the operations c_{k}^{⊥𝒰} , a_{k}^{⊥𝒰} : 𝒫(U) ⟶ 𝒫(U) as follows: for arbitrary X ⊆ U

c_{k}^{⊥𝒰} X =^{def} {u ∈ U | (∃u′ ∈ U)(u ≡_{k} u′ & u′ ∈ X)} = X/ ≡_{k}

and

a_{k}^{⊥𝒰} X =^{def} {u ∈ U | (∀u′ ∈ U)(u ≡_{k} u′ ⇒ u′ ∈ X)} = ∖ c_{k}^{⊥}(∖X);

we call c_{k}^{⊥𝒰} the k-th ortho-cylindrification and a_{k}^{⊥𝒰} the k-th ortho-axification (w.r.t. 𝒰). If it is not confusing, we may omit the superscript 𝒰. The notions

𝔓_{Df}_{⊥−}(𝒰)  𝔓_{Df}_{⊥±}(𝒰)
UhDf_{n}^{⊥−}  UhDf_{n}^{⊥±}
RDf_{n}^{⊥−}  RDf_{n}^{⊥±}

are to be defined similarly as we did in the cylindric case, and the names we call them are also similar — only the superscript “⊥” and the attribute “ortho-” is to be put to the appropriate place. Formally,

𝔓_{Df}_{⊥−}(𝒰) = ⟨𝔓^{−}(U), c_{k}^{⊥𝒰} ⟩_{k<n}, 𝔓_{Df}_{⊥±}(𝒰) = ⟨𝔓^{−}(U), c_{k}^{⊥𝒰} , a_{k}^{⊥𝒰} ⟩_{k<n},

and then for ∗ ∈ {−, ±}

UhDf_{n}^{⊥∗} = S {𝔓_{Df}_{⊥∗}(𝒰) | 𝒰 is an unholed rist_{n}}, RDf_{n}^{⊥∗} =^{def} SPUhDf_{n}^{⊥∗}.

Moreover, we define the class of (diagonal-free) asymmetric ortho-cylindric relation algebras of dimension n as

RelDf_{n}^{⊥−} =^{def} S{𝔓_{Df}^{−}(𝒰) | 𝒰 is a rist_{n}},

and the class of (diagonal-free) symmetric ortho-cylindric relation algebras of dimension n as

RelDf_{n}^{⊥±} =^{def} S{𝔓_{Df}^{±}(𝒰) | 𝒰 is a rist_{n}}.
□

The effect of c_{k}^{⊥} can be illustrated the following way: if p is a point of the n-dimensional space, then c_{k}{p} is the line joined to p being parallel with the k-th axis, and c_{k}^{⊥}{p} is the orthogonal hyperplane of this line put through p.

RDf_{n}^{⊥∗} ⊆ RelDf_{n}^{⊥∗}, which can be seen by the stringing method: just like in the cylindric case, every representable ortho-cylindric lattice can be represented over a block-diagonal rist. RelDf_{n}^{⊥∗} is the broadest class of algebras of type Df_{n}^{⊥∗} relevant to these investigastions.

Lemma 2.7. (Basic ortho-cylindric equations) For any k < n the DL-axioms are valid in RelDf_{n}^{⊥−} and RelDf_{n}^{⊥−} ⊧ c_{k}^{⊥} 0 = 0, x ⩽ c_{k}^{⊥} x = c_{k}^{⊥} c_{k}^{⊥} x, c_{k}^{⊥}(x ∨ y) = c_{k}^{⊥} x ∨ c_{k}^{⊥} y, c_{k}^{⊥}(x ∧ c_{k}^{⊥} y) = c_{k}^{⊥} x ∧ c_{k}^{⊥} y.

These, and the duals of these equations (i.e. the ones we get if we interchange ∧ with ∨, ⩽ with ⩾, 0 with 1, c_{k}^{⊥} with a_{k}^{⊥}) hold in RelDf_{n}^{⊥±}, moreover in this class “a_{k}^{⊥} c_{k}^{⊥} x = c_{k}^{⊥} x” and “c_{k}^{⊥} a_{k}^{⊥} x = a_{k}^{⊥} x” are also valid.

Proof. Since proving this lemma results faster and deeper understanding than reading a formal proof would result, it is left to the reader. _{■}

In the next section we will see that these equations characterize RelDf_{n}^{⊥∗}.

The equation c_{k}^{⊥}(x ∧ c_{k}^{⊥} y) = c_{k}^{⊥} x ∧ c_{k}^{⊥} y will be refered to as “the basic ortho-cylindric equation concerning intersections”.

In the following Lemma we clarify the relation between the cylindric operations and their “ortho” versions.

Lemma 2.8.

• If 𝒰 is an unholed rist_{n}, then cylindrifications over 𝒰 commute (for i, j < n c_{j} ∘ c_{i} = c_{i} ∘ c_{j}) and c_{k}^{⊥} = c_{n−1} ∘ … ∘ c_{k+1} ∘ c_{k−1} ∘ … ∘ c_{0}, a_{k}^{⊥} = a_{n−1} ∘ … ∘ a_{k+1} ∘ a_{k−1} ∘ … ∘ a_{0}.

• The ortho-operations are available in RDf_{n}^{∗} (∗ ∈ {−, ±}) in the following sense: Let 𝔄 ∈ RDf_{n}^{−}; let us define c_{k}^{⊥} on 𝔄 by the term c_{n−1} … c_{k+1} c_{k−1} … c_{0} x. Then ⟨𝔄, c_{k}^{⊥}⟩_{k∈n} can be represented over a suitable rist_{n}. The analogue statement holds in the symmetric case if we define a_{k}^{⊥} by the term a_{n−1} … a_{k+1} a_{k−1} … a_{0} x.

• If 𝒰 is a rist_{2}, then c_{0}^{⊥} = c_{1}, c_{1}^{⊥} = c_{0} and similarly for axifications, that is, in dimension two the cylindric and ortho-cylindric notions “are the same”.

Proof. The third statement is trivial. The second statement immediately follows from the first one using the stringing method. Checking the first statement is left to the reader.

■

This definition of the ortho-operations on a cylindric lattice will be referred to as the geometric or natural definition of the ortho-operations.

2.2. Background for the diagrams

In this subsection we will show how and why work the cylindric lattice diagrams. The main problem about this is finding an easy-to-check criterion helping us to decide whether a lattice over a rist_{2}, given by a preorder is closed w.r.t. cylindrifications. In a bit higher level of generality we will examine the situation where the preoder is put on a rist_{n}, and the question is that whether the belonging lattice is closed w.r.t. ortho-cylindrifications.

However, if the reader is willing to believe that those concrete diagrams by which we intend to show examples, really picture algebras, that is, the lattice belonging to the given preorder is closed w.r.t. cylindrifications, then s/he may skip this subsection and can continue reading with the following section.

Now we will turn to a special kind of ortho-cylindric lattices: complete ones. We will examine how can we “portray” operations “like ortho-cylindrification and -axification” on complete sublattices of a powerset-lattice and that if there is given a rist, how can we define complete ortho-cylindric sublattices. At the special case when the dimension of the rist is two and it is finite we will get the cylindric lattice diagrams. (Metatheorem: “Every kind of handicap a relation algebra can have can be demonstrated in finite ones.”

— this can be made a bit more exact but it is not our present business). After finishing this job we can return to ortho-cylindric lattices in general.

Let U be an arbitrary but fixed set.

Definition 2.9.

• f : 𝒫(U) ⟶ 𝒫(U) is a completely additive closure operator over U, caco for short, if it is a closure operator and for 𝒬 ⊆ 𝒫(U) f(∪𝒬) = ∪(f^{⊃}𝒬) (especially, since ∪∅ = ∅ = f^{⊃}∅, we have f(∅) = ∅).

• Let ℒ be a complete lattice; we will use the same symbols (∨, ∧) for the binary join, intesection operations and for the more general unary sup, inf operation. We will say ℒ′ is a complete sublattice of ℒ, if ℒ′ is a sublattice of ℒ′, it is complete, moreover for X ⊆ ℒ′ ∨X, ∧X are the same in ℒ′ and ℒ.

• If ⇾ is a preorder (reflexive and transitive relation) on U, then we will use the notations u ⇾ v, v ⇽ u for expressing ⟨u, v⟩ ∈⇾, and a simple ⇽ will denote the converse of ⇾; we define the downward hull mapping and the upward hull mapping (w.r.t. ⇾) Δ_{⇾}, ∇_{⇾} : 𝒫(U) ⟶ 𝒫(U) as for X ⊆ U Δ_{⇾}X = {v | ∃u ∈ X u ⇾ v} and ∇_{⇾}X = {v | ∃u ∈ X u ⇽ v}. _{□}

Lemma 2.10. All entities mentioned below are meant w.r.t. U.

• If f is a caco, then ℒ_{f} =^{def} Rng f = {X ⊆ U | f(X) = X} is a complete sublattice (of 𝔓^{−}(U));

• if ℒ is a complete sublattice, then the function f_{ℒ}, which maps to a set H ⊆ U the set ⋂{X ∈ ℒ | H ⊆ X}, is a caco;

• if f is a caco, then ⇾_{f} =^{def} {⟨u, v⟩ | f({u}) ∋ v} is a preorder;

• if ⇾ is a preorder, then f_{⇾} =^{def} Δ_{⇾} is a caco,

and the diagram

\xymatrix{preo. \ar[r]^{⟨(⇾)↦f_{⇾}⟩} & caco \ar[l]^{⟨f↦(⇾_{f})⟩} \ar[r]^{⟨f↦ℒ_{f}⟩} & comp. sl. \ar[l]^{⟨ℒ↦f_{ℒ} ⟩}}

commutes (and we can define by compositions and may use the explicitely not defined conversions between the three sorts of objects (i.e. ⟨(⇾) ↦ ℒ_{⇾}⟩ , ⟨ℒ ↦⇾_{ℒ} ⟩)).

Proof. This Lemma was claimed in order to enumerate this bunch of equivalent things, not in order to be proved: since proving this Lemma results faster and deeper understanding than reading a formal proof would result, it is left to the reader (who may also consult with [?]). _{■}

Remark 2.11. Ortho-cylindrifications are simply (restrictions of) complemented completely additive closure operators:

We say that a closure operator f : 𝒫(U) ⟶ 𝒫(U) is complemented, if for X ⊆ U f(X) = X ⇒ f(∖X) = ∖X. Of course, ortho-cylindrifications over a rist are complemented cacos. And if we take a Df_{n}^{⊥−}-type algebra 𝔄 = ⟨𝒫^{−}(U), c_{k}^{⊥}⟩_{k<n}, where the c_{k}^{⊥}-are complemented cacos over U, then – since ⇾_{c_{k}^{⊥}} is an equivalence because of

complementedness – 𝔄 = 𝔓_{Df}_{⊥−}(𝒰), where 𝒰 is the rist_{n} ⟨U, ⇾_{c_{k}^{⊥}}⟩_{k<n}. _{□}

We intend to characterize algebras of the form 𝔄 = ⟨ℒ, f↾_{ℒ} ⟩, where ℒ is a complete sublattice of 𝔓^{−}(U) and f is a caco over U. What makes this pair an algebra is the property that the f-image of an element of ℒ is also in ℒ — i.e. ℒ is closed w.r.t. f (this is a property making sense for subsets of the powerset of U and it is not to be mixed with the expression “being f-closed” making sense for subsets of U, meaning “being equal with the f-value”). For first sight in the two positions of the ordered pair ⟨ℒ, f↾_{ℒ} ⟩ by which 𝔄 is given, there stand different sort of things: one is “universe-like” and the other is “operator-like”. Though we know from the previous lemma that one can be converted to the other’s sort, so there is hope that the mentioned demand for closedness w.r.t. f can be formulated in terms of interrelations between same kind of things. In fact it is very easy: we need that the f-closures of elements of ℒ – i.e., f-closures of subsets of U of the form f_{ℒ} (X) – are also in ℒ, – that is, they are equal with their f_{ℒ} -value. So we translated the problem to the language of cacos, formally: we need f_{ℒ} ∘ f ∘ f_{ℒ} = f ∘ f_{ℒ}. That’s not all. We would like to trace the question back to something simpler; for this role, as it also turns out from Lemma 2.10., the best candidate is the elementary theory of preorders. This is done in the next Lemma:

Lemma 2.12. For f, g cacos g ∘ f ∘ g = f ∘ g ⟺ (⇽_{g}) ∘ (⇽_{f}) ⊆ (⇽_{f}) ∘ (⇽_{g}).

Proof. During the proof Lemma 2.10. will be referred to without mention.

(→): Assume w((⇽_{g}) ∘ (⇽_{f}))u, i.e. for some v u ⇾_{f} v ⇾_{g} w. Then v ∈ f({u}), w ∈ g({v}) ⊆ g(f({u})) by monotonity of closure operators. By extensivity {u} ⊆ g({u}), then by monotonity w ∈ g(f(g({u}))), which equals f(g({u})) by the assumption. It means w ∈ Δ_{⇾_{f}} g({u}), so by the definition of Δ we can take some v′ from g({u}) such that w ⇽_{f} v′; but v′ ∈ g({u}) means v′ ⇽_{g} u; so we get w ⇽_{f} v′ ⇽_{g} u, i.e. w((⇽_{f}) ∘ (⇽_{g}))u.

(←): Assume u ∈ (g ∘ f ∘ g)(X). Then u ∈ Δ_{⇾_{g}}(f ∘ g)(X), which means we can take a v such that u ⇽_{g} v ∈ (f ∘ g)(X). Iterating this procedure we will find a w and a z such that u ⇽_{g} v ⇽_{f} w ⇽_{g} z ∈ X. By our assumption we can take a v′ such that u ⇽_{f} v′ ⇽_{g} w ⇽_{g} z ∈ X. Then, using transitivity of preorders, we get u ⇽_{f} v′ ⇽_{g} z ∈ X. But then similarly like above, u ∈ (f ∘ g)({z}) ⊆ (f ∘ g)(X). Since u was an arbitrary element of (g ∘ f ∘ g)(X), we get that (g ∘ f ∘ g)(X) ⊆ (f ∘ g)(X), and from monotonity follows “⊇”. _{■}

Summarizing these in one more lemma:

Lemma 2.13. Let ℒ be a complete sublattice of 𝔓^{−}(U) and f be a completely additive closure operator over U. Then ⟨ℒ, f↾_{ℒ} ⟩ is an algebra iff (⇽_{ℒ}) ∘ (⇽_{f}) ⊆ (⇽_{f}) ∘ (⇽_{ℒ}). _{■}

The following definitions try to treat relations of a similarity type as they were functions: if r(x_{0}, …, x_{n}) is a relation of the type, then x_{0}, …, x_{n−1} are treated as “the inputs”, and x_{n} is treated as “the value”.

Definition 2.14. Let 𝔄, 𝔅 be similar first-order structures.

• we say φ : 𝔄 ⟶ 𝔅 is an algebraic homomorphism, if it is a homomorphism in the usual sense (i.e. it preserves operations and relations), and in case r is a relation of the type with arity n + 1, then for any a⃗ ∈ 𝔄^{n}, β ∈ 𝔅 : r(φ(a⃗), β) ⇒ (∃b ∈ 𝔄)(r(a⃗, b) & φ(b) = β);

• we say ϑ is an algebraic congruence of 𝔄, if it is a congruence of the algebra reduct of 𝔄, and in case r is a relation of the type with arity n + 1, then for any a⃗, a′ ∈ 𝔄^{n}, b ∈ 𝔄 : (a_{k} ϑ a′_{k} (k < n) & r(a⃗, b)) ⇒ (∃b′ ∈ 𝔄)(b′ ϑ b & r(a′, b′));

• we say 𝔅 is an algebraic substructure of 𝔄, if the algebra part of 𝔅 is a subalgebra of the algebra part of 𝔄, and in case r is a relation of the type with arity n + 1, then for any \underline{b} ∈ 𝔅^{n}, a ∈ 𝔄 : r(b⃗, a) ⇒ a ∈ 𝔅. _{□}

Remark 2.15. These notions really behave algebraically: in algebra we could define factor algebras by a congruence and the factorisation mapping was a homomorphism, kernel of homomorphisms was congruence, we claimed the homomorphism theorem, homomorphic image and pre-image of subalgebras was also a subalgebra, HSP was a closure oprator (and HSP-closedness meant closedness w.r.t. each of P, S, H) — these things all work for algebraic homomorphism, congruence, substructure. Moreover, we can say a first-order structure is algebra-like if interpretations of the relation symbols are functions: then algebraic homomorphisms preserve algebra-likeness. It may be interisting to investigate whether is there a Birkhoff-type theorem for these notions (axiomatizability of HSP-closed classes with a given sort of first-order formulas). _{□}

We will not use the algebraic notions in that generality as we defined them: mostly we will use the notion of algebraic congruence, and we will restrict ourselves to the case when the type consists of the binary relation symbol ⇾. Since in this simple type we can speak more fluently than in generality and concise draftings are easier to memorize than composite ones, we repeat the definition in this special case (for sake of conciseness we will not even declare who is element of whom):

In type ⟨⇾⟩ ϑ is an algebraic congruence, if ϑ is an equivalence relation and a′ ϑ a ⇾ b ⇒ ∃b′ a′ ⇾ b′ ϑ b, or pictured in a diagram:

[figure: •; ϑ; •; •; ϑ; ∘]

Lemma 2.16. If ⇾ is a binary relation and ϑ is an equivalence on some set, then ϑ is an algebraic congruence of ⇾ iff (⇽) ∘ ϑ ⊆ ϑ ∘ (⇽).

Proof. It is exactly the element-free reading of that what can be seen on the above diagram. _{■}

Now we are ready to state the main result of this subsection:

Theorem 2.17. Let ⟨U, ≡_{k}⟩_{k<n} be a rist, ⇾ be a preorder on U. Then

i) ℒ_{⇾} is closed w.r.t. c_{k}^{⊥} (k < n) (i.e. ⟨ℒ_{⇾}, c_{k}^{⊥} ↾_{ℒ_{⇾}} ⟩_{k<n} is a relation algebra of type Df_{n}^{⊥−}) iff ≡_{k} is an algebraic congruence of ⇾ (k < n);

ii) ℒ ⇾ is closed w.r.t. c_{k}^{⊥} and a_{k}^{⊥} (k < n) (i.e. ⟨ℒ_{⇾}, c_{k}^{⊥} ↾_{ℒ_{⇾}} , a_{k}^{⊥} ↾_{ℒ_{⇾}} ⟩_{k<n} is a relation algebra of type Df_{n}^{⊥±}) iff ≡_{k} is an algebraic congruence of ⇾ and ⇽ as well (k < n).

Proof. i): Since c_{k}^{⊥} is a caco, by Lemma 2.13., ⟨ℒ_{⇾}, c_{k}^{⊥} ↾_{ℒ_{⇾}} ⟩_{k<n} forms an algebra iff for any k < n (⇽) ∘ (⇽_{c_{k}^{⊥}}) ⊆ (⇽_{c_{k}^{⊥}}) ∘ (⇽); however, ⇾_{c_{k}^{⊥}}=≡_{k}, thus the above condition can be transcripted as (⇽) ∘ (≡_{k}) ⊆ (≡_{k}) ∘ (⇽); by Lemma 2.16. this means that ≡_{k} is an algebraic congruence of ⇾.

ii): ℒ_{⇾} is closed w.r.t. a_{k}^{⊥} iff ∖^{⊃}ℒ_{⇾} is closed w.r.t. c_{k}^{⊥}. X ∈ ∖^{⊃}ℒ_{⇾} ⟺ ∖X ∈ ℒ_{⇾} ⟺ Δ_{⇾}(∖X) = ∖X ⟺ ∇_{⇾}X = X ⟺ Δ_{⇽}X = X, which means ∖^{⊃}ℒ_{⇾} = ℒ_{⇽}. So ℒ_{⇾} is closed w.r.t. the a_{k}^{⊥}-s iff ℒ_{⇽} is closed w.r.t the c_{k}^{⊥}-s, that is, iff ⟨ℒ_{⇽}, c_{k}^{⊥} ↾_{ℒ_{⇽}} ⟩_{k<n} forms an algebra; cf. i). _{■}

Thus – since in every dimension two “cylindrifications and ortho-cylindrifications are the same” – if we have a cylindric lattice diagram, we can check immediately whether it is defines an asymmetric (symmetric) relation algebra, by checking wheter the projection kernels are algebraic congrueces of the pictured preorders (and their converses).

We advise the reader to check immediately that Figure 2.4. defines an asymmetric relation algebra and Figure 2.5. defines a symmetric one.

Remark 2.18. We may ask how general tools cylindric lattice diagrams are for picturing cylindric lattices (cylindric relation algebras).

If we have a finite algebra of type Df_{2}^{∗} such that it can be represented over a rist_{2}, then it can be pictured by a cylindric lattice diagram, because (as it follows from those written in Subsection 3.1.) this case we may suppose the finiteness of the underlying rist_{2}, and sublattices of the powerset lattice of a finite set are complete sublattices.

In fact, Theorem 2.17. mutatis mutandis can be referred to higher dimensional cylindric relation algebras as well, since if 𝒰 is a rist_{n}, then c_{k}^{𝒰} = c_{k}^{⊥𝒰′} , where 𝒰′ is the rist_{n} on the same base set with ∩_{j≠k} ≡_{j} as k-th projection kernel (k < n); – but this is the point where the structure of the space we live in has an influence on the matter: it is not as easy to present poset diagrams on the points of some high-dimensional discrete cube! — though the enterprising reader may try to make ones like those which can be seen on chemistry lessons made of small sticks and balls. _{□}

3. Basic theory of ortho-cylindric relation algebras

Notations, conventions.

If X is a binary relation on an algebra, the congruence of generated by X will be denoted with ⟦X⟧; if additional info is necessary (e.g. we generate in a subalgebra or in a reduced type), that will be given as subscription.

We will denote the full congruence by 1 and the identic one by 0.

If ϑ, γ are equivalences on a set U, then by ϑ ∨ γ we mean the equivalence generated by ϑ ∪ γ (we remind the reader that if we have an algebra 𝔄 on U, and ϑ, γ ∈ Con𝔄, then ϑ ∨ γ ∈ Con𝔄 as well).

3.1. Canonical representation and holes

In the following paragraphs we will always speak of asymmetric ortho-cylindric relation algebras because the presence of axifications will not effect the validness of most of our arguments and it is more comfortable dealing with only one type of operation. At the end of this section we will discuss how to convert the results to the symmetric case. However, one of the theorems in this section losts its validity in the symmetric case.

It will be easier to speak in terms of congruences than of subsets, so we will not speak of ultrafilters of a DL, but of 2-congruences, i.e. ones which have two classes. If 𝔇 is a DL, we will denote the set of the two-congruences of 𝔇 by Con_{2}𝔇.

We remind the reader to the Stone-Birkhoff theorem: if 𝔇 ∈ DL, then the function ˜( ·) : 𝔇 ⟶ 𝔓^{−}(Con_{2}𝔇), for which ã = {τ ∈ Con_{2}𝔇 | a τ 1}, embeds 𝔇 in 𝔓^{−}(Con_{2}𝔇). ( ˜( ·) will be called Birkhoff’s embedding.)

If Γ is a binary relation on a DL 𝔇, then – according to that whether exists a 2congruence of 𝔇 containing Γ or not – we say that Γ is extendable or non-extendable (onto 𝔇). Of course, Γ is non-extendable iff ⟦γ⟧ = 1, that is, iff 0 ⟦Γ⟧ 1.

Lemma 3.1. Consider H, L ⊆ 𝔇 ∈ DL.

Then (L × {0}) ∪ (H × {1}) is extendable iff finite intersections from H can neither be smaller than, nor equal with finite joins from L.

Proof. The reader may consider that this is the DL-version of the well-known fact that a subset of a Boolean algebra can be extended to an ultrafilter iff finite intersections of elements taken from the subset cannot be 0. _{■}

Definition 3.2. We will refer to the equations mentioned in Lemma 2.7. by Bocy. Let 𝔄 be an (a non-trivial) algebra of type Df_{n}^{⊥−} satisfying Bocy. When 2-congruences of 𝔄 are mentioned, they are meant to be DL-congruences. We will refer by Con_{2,DL}𝔄 to the set Con_{2}[𝔄]_{DL}. We will call x ∈ 𝔄 k-closed if c_{k}^{⊥} x = x, and 𝔄_{k} will denote the sublattice of the k-closed elements (it is always a sublattice but not necessarily a subalgebra). If τ_{k} ∈ Con_{2,DL}𝔄_{k}, we will refer to the set {τ ∈ Con_{2,DL}𝔄 | τ↾_{𝔄_{k}} = τ_{k}} briefly as F_{τ_{k}}. _{□}

We remind the reader that in 𝔓_{Df}_{⊥−}(𝒰) for X ⊆ U c_{k}^{⊥} X is the union of those k-fibres, which intersect X.

Theorem 3.3. (Representation Theorem) RelDf_{n}^{⊥−} = Mod Bocy (especially RelDf_{n}^{⊥−} is a variety).

Proof. Because of Lemma 2.7., we have to prove that if 𝔄 ⊧ Bocy, then 𝔄 ∈ RelDf_{n}^{⊥−}.

So let 𝔄 ⊧ Bocy. Let ˜( ·) be Birkhoff’s embedding [𝔄]_{DL} ⟶ 𝔓^{−}(Con_{2,DL}𝔄). We will define projection kernels on Con_{2,DL}𝔄 making this mapping a Df_{n}^{⊥−}-embedding: for k < n and τ, τ′ ∈ Con_{2,DL}𝔄, let τ ≡_{k} τ′ be iff τ and τ′ coincide in 𝔄_{k} ( τ↾_{𝔄_{k}} = τ′↾_{𝔄_{k}} ).

In the following we will prove that ˜( ·) is an 𝔄 ⟶ 𝔓_{Df}_{⊥−} (⟨Con_{2,DL}𝔄, ≡_{k}⟩_{k<n}) homomorphism. Let k < n. First we prove that image of k-closed elements is k-closed; it means we have to prove that if there is given a k-closed element x_{k} and τ, τ′ ∈ Con_{2,DL}𝔄_{k} such that τ′ ≡_{k} τ ∈ x̃_{k}, then τ′ ∈ x̃_{k} as well. τ ≡_{k} τ′ means τ↾_{𝔄_{k}} = τ′↾_{𝔄_{k}}, τ ∈ x̃_{k} means x_{k} τ 1. Since x ∈ 𝔄_{k}, this latter means ⟨x, 1⟩ ∈ τ↾_{𝔄_{k}} = τ′↾_{𝔄_{k}} ⊆ τ′, so x τ′ 1, that is, τ′ ∈ x̃_{k}. Briefly, we could say that on 𝔄_{k} ˜( ·) commutes with c_{k}^{⊥}.

Since a ⩽ c_{k}^{⊥} a and ˜( ·) is a DL-homomorphism, ã ⩽ c̃_{k}^{⊥} a as well, so using what we established above, by applying c_{k}^{⊥} on both sides, and using idempotency and monotonity of c_{k}^{⊥}, we get c_{k}^{⊥} ã ⩽ c̃_{k}^{⊥} a. So for proving that ˜( ·) commutes with c_{k}^{⊥} in general, we have to show that c_{k}^{⊥} ã ⩾ c̃_{k}^{⊥} a.

This means that any time c̃_{k}^{⊥} a intersects a k-fibre, ã intersects it as well. Let τ_{k} ∈ Con_{2,DL}𝔄_{k}. Since τ_{k} is extendable onto 𝔄, for an x_{k} ∈ 𝔄_{k} x̃_{k} intersects the k-fibre F_{τ_{k}} iff x_{k} τ_{k} 1. So we have to show that c_{k}^{⊥} a τ_{k} 1 implies that ã intersects F_{τ_{k}}, that is, for some τ ∈ Con_{2,DL}𝔄 a τ 1, τ↾_{𝔄_{k}} = τ_{k}. We will try to extend the relation τ_{k} ∪ {⟨a, 1⟩} to a 2-congruence of 𝔄.

Suppose this attempt fails. Considering that 0/τ_{k} is closed w.r.t. finite joins and that 1/τ_{k} is closed w.r.t. finite intersections, by Lemma 3.1. we get that this case we can find x_{k}, y_{k} ∈ 𝔄_{k} such that x_{k} τ_{k} 1, y_{k} τ_{k} 0 and a ∧ x_{k} ⩽ y_{k}. Then apply c_{k}^{⊥} to both sides: by monotonity of c_{k}^{⊥} and by the equation of Bocy concerning intersection we get that c_{k}^{⊥} a ∧ x_{k} ⩽ y_{k}; but the left side is congruent with 1 modulo τ_{k}, and the right side is congruent with 0 modulo τ_{k}; it is a contradiction.

This finishes the proof of the theorem. _{■}

We are ready to put down what a hole is.

Definition 3.4. If 𝔄 is an algebra of type Df_{n}^{⊥−}, then by a representation of 𝔄 we mean a pair ⟨𝒰, φ⟩, where 𝒰 is a rist_{n}, and φ is an embedding of 𝔄 in 𝔓_{Df}_{⊥−}(𝒰); however, by an abuse of language, usually the image of φ will be attributed as “representation”. If 𝒰 and 𝒰′ are rists, and f : 𝒰 ⟶ 𝒰′, we will say f is an isomorphism between the two representations, if it is an isomorphism between 𝒰 and 𝒰′, and φ′ = f^{⊃} ∘ φ. (We may use this terminology in other similarity types as well, as it stand for reason; for example, for DL’s, based on “isomorphism of sets”, i.e., bijections.)

Let 𝔄 ∈ RelDf_{n}^{⊥−}. A canonical representation of 𝔄 is a representation, which is isomorphic with the generic canonical representation, which is the one we found in the Representation Theorem, that is: ⟨⟨Con_{2,DL}𝔄, ≡_{k}⟩_{k∈n} , ˜( ·)⟩, where τ ≡_{k} τ′ iff τ↾_{𝔄_{k}} = τ′↾_{𝔄_{k}}, and

˜( ·) is Birkhoff’s embedding. Usually we do not distinguish between isomorphic representations, so we may use definite article (we may speak of “the canonical representation”).

By a hole of 𝔄 we mean (a tuple encoding) a hole of the underlying rist of the generic canonical representation, i.e. a tuple ⟨τ_{0}, …, τ_{n−1}⟩ such that τ_{k} ∈ Con_{2,DL}𝔄_{k} (k < n) and τ_{0} ∪…∪τ_{n−1} is non-extendable onto 𝔄. (This occurs exactly if the tuple of fibres ⟨F_{τ_{k}}⟩_{k<n} in the generic canonical representation is a hole in the sense of Definition 1.7.) _{□}

Remark 3.5. We claim that this hole-notion is sufficient: the underlying rist of the canonical representation has no superfluous holes; especially – as we would expect – 𝔄 is unholed iff it has no holes. Namely if ⟨τ_{0}, …, τ_{n−1}⟩ is a hole, then by Lemma 3.1. (and using that 0/τ_{k} is closed w.r.t. finite joins and 1/τ_{k} is closed w.r.t. finite intersections) we can find x_{k}, y_{k} ∈ 𝔄_{k} : x_{k} τ_{k} 1, y_{k} τ_{k} 0 (k < n) such that x_{0} ∧ … ∧ x_{n−1} ⩽ y_{0} ∨ … ∨ y_{n−1}. Since x_{k} τ_{k} 1 and y_{k} τ_{k} 0, x_{k} ⩽̸ y_{k}.

In general, if there is given x_{k}, y_{k} ∈ 𝔄_{k} : x_{k} ⩽̸ y_{k} (k ∈ n), x_{0}∧…∧x_{n−1} ⩽ y_{0}∨…∨y_{n−1}, then this configuration “punches” any concrete representation: suppose 𝔄 is represented over some rist_{n} 𝒰 (we will not use different notation for the represented elements). Since a k-closed set contains a k-fibre or they are disjoint, x_{k} ∖ y_{k} consists of k-fibres. Let

F_{k} ⊆ x_{k}∖y_{k} a k-fibre (k < n). Then F_{0}∩…∩F_{n−1} ⊆ ⋂_{k∈n}(x_{k}∖y_{k}) = ∅, so ⟨F_{0}, …, F_{n−1}⟩

is a hole of 𝒰.

By the way we can suppose x_{k} > y_{k}: if it is not so originally, we can replace the y_{k}-s by y_{k} ∧ x_{k} — applying the distributive law we can see that x_{0} ∧ … ∧ x_{n−1} ⩽ (y_{0} ∧ x_{0}) ∨ … ∨ (y_{n−1} ∧ x_{n−1}) also holds.

So we succeded interpret holes as intrinsic, isomorphism-invariant features of orthocylindric relation algebras. _{□}

Especially we got the following

Theorem 3.6. (Axiomatization of UhDf_{n}^{⊥−})

UhDf_{n}^{⊥−} = Mod (Bocy ∪
{c_{0}^{⊥} x_{0} ∧ … ∧ c_{n−1}^{⊥} x_{n−1} ⩽ c_{0}^{⊥} y_{0} ∨ … ∨ c_{n−1}^{⊥} y_{n−1} ⇒
(c_{0}^{⊥} x_{0} ⩽ c_{0}^{⊥} y_{0} or … or c_{n−1}^{⊥} x_{n−1} ⩽ c_{n−1}^{⊥} y_{n−1})})  (∗)
■

In Section 2. we interpreted ortho-cylindrifications in cylindric lattices by a term function (natural definition of c_{k}; cf. Lemma 2.8.). This definition corresponds with our geometric intuition. However, we can define ortho-cylindrifcations on cylindric lattices in a syntactically much more simple way: by c_{k}^{⊥} = c_{k}. This kind of ortho-cylindrifications also satisfy Bocy. If later on we would like to refer back to the latter definition, it will be called the syntactic definition of ortho-cylindrifications.

Corollary 3.7. (Axiomatizing classes of algebras in dimension one) By the syntactic definition of ortho-cylindrifications we can treat cylindric and orthocylindric algebras as they were of the same similarity type. Let us act this way. Then RDf_{1}^{−} = RDf_{1}^{⊥−} = UhDf_{1}^{⊥−} = Mod Bocy (especially these classes are varieties).

Proof. Since for n = 1 (∗) is a tautology, UhDf_{1}^{⊥−} = Mod Bocy; so UhDf_{1}^{⊥−} is a variety, which implies RDf_{1}^{⊥−} = UhDf_{1}^{⊥−}.

The syntactical definition identifies UhDf_{1}^{−} with those ortho-cylindric lattices, which can be represented over a rist_{1} with one molecule. Every rist_{1} is available by stringing rist_{1}-s with one molecule to a diagonal line; so every algebra of RDf_{1}^{⊥−} is a subdirect product of UhDf_{1}^{−}-algebras. That is, RDf_{1}^{⊥−} = RDf_{1}^{−}. _{■}

Remark 3.8. Consider BAO’s, where the extra-Boolean operations are complemented additive closure operators. Theorem 3.3. is also valid for these, because of the following:

BA’s can be thought of as special DL’s: complemented ones; a complemented closure operator – thought of as an abstract ortho-cylindrification – satisfies Bocy; if we allow infinitely many ortho-cylindrifications, Theorem 3.3. still preserves its validity.

So Theorem 3.3. claims that such BAO’s can be embedded in a complete atomic BAO, where the extra-Boolean operations are complemented completely additive closure operators. This is a special case of the well-known theorem which says every BAO has a perfect extension (cf. [JT], [HMT1, pp. 430-434], [ANS b, pp. 67-71]). The odd thing about this special case is the simplicity of the construction of the perfect extension, given in Definition 3.4., verified in Theorem 3.3. This special case is still quite broad: for example, all CA’s belong to this.

The reason for producing the perfect extension as we did in Theorem 3.3. is that this way we could easily make an underlying rist for the perfect extension, and we found a pleasant way for defining the holes of an algebra.

To see further connections between such BAO’s and ortho-cylindrifications, we refer the reader back to Remark 2.11. _{□}

Remark 3.9. At the definition and verification of the notions “canonical representation” and “hole” we could see an advantage of using rists (compared with relations): they were easy to work with. It is a technical reason for using rists; however, there are conceptional reasons as well to do so: if we have an algebra over a rist, and we represent it over a relation (over a strict rist), it is quite accidental and irrelevant, how the certain molecules are represented; it gives no information about the structure of the algebra. In the diagonalfree case (!) the submolecular structure of the algebras is simply a DL-structure (cf. Remark 1.10.). If we used relations instead of rists, we could not even define canonical representation, since there is no distinguished way to represent molecules over relations. Using rists means forgetting the superfluous part of representing over relations. _{□}

Now we would like to know, “how does a canonical representation look like”, that is: if we have an algebra given by a cylindric lattice diagram, how can we decide whether it is the canonical representation, or not?

The answer sounds quite natural, however, verifying this answer is a long and quite technical process, so we will omit the verification; all the more because subsequent reference to this answer can be avoided.

Theorem 3.10. If an algebra of RelDf_{n}^{⊥−} is given by a (finite) cylindric lattice diagram, then this representation is a canonical one iff the preorder pictured in the diagram is a partial order. _{■}

Thus it is worth to use and speak of only such cylindric lattice diagrams where the attached preorder is a partial order.

By the way, with the help of Remark 3.5. and Theorem 3.10. we may see that the lattices given by Figures 2.4., 2.5. really has holes and the holes occuring in the rists over which they are given are not accidental and are not the outcome of an awkward way of representing.

3.2. Asymmetric equational theories

Definition 3.11. Let 𝔄 ∈ RelDf_{n}^{⊥−}.

Those elements of 𝔄 which are k-closed for all k < n, form a subalgebra; this subalgebra will be called the discrete subalgebra or spine of 𝔄 and it will be denoted by 𝔄_{sp}. We say 𝔄 is 2-spined if 𝔄_{sp} = {0, 1}. It is a first-order property: 𝔄 is 2-spined iff 𝔄 ⊧ (x = c_{0}^{⊥} x = … = c_{n−1}^{⊥} x) ⇒ (x = 0 or x = 1). We will refer to (the singleton of) this formula by 2sp. _{□}

Lemma 3.12. UhDf_{n}^{⊥−} ⊧ 2sp.

Proof. The proof is left to the reader. _{■}

From the possible drawings of subdirect decomposition we will use that one by which a subdirect decomposition is such a subset of the congruence lattice the intersection of which is the identic congruence.

Lemma 3.13. If 𝔄 ∈ RelDf_{n}^{⊥−} is subdirectly irreducible, then it is 2-spined.

Proof. Assume 𝔄 ∈ RelDf_{n}^{⊥−} is not 2-spined. Let a ∈ 𝔄_{sp}, a ≠ 0, 1. Consider the following equivalences: for ∗ ∈ {∧, ∨} let x ϑ_{∗} y iff x ∗ a = y ∗ a; these are congruences — of course, they are compatible with the lattice operations, and since a ∈ 𝔄_{sp}, we can see by Bocy that for all x and ∗ ∈ {∧, ∨} c_{k}^{⊥}(x ∗ a) = c_{k}^{⊥} x ∗ a.

ϑ_{∧}, ϑ_{∨} are not identic, since a ϑ_{∧} 1, a ϑ_{∨} 0. Moreover ϑ_{∧}, ϑ_{∨} form a subdirect decomposition: if x ϑ_{∧} y and x ϑ_{∨} y, then x = (a∨x)∧x = (a∨y)∧x = (a∧x)∨(y ∧x) = (a ∧ y) ∨ (x ∧ y) = (a ∨ x) ∧ y = (a ∨ y) ∧ y = y.

This means 𝔄 is subdirectly reducible. _{■}

Now consider the following situation: we take some 2-spined ortho-cylindric lattices being presented over rists and we string them to a diagonal line. During this procedure a bunch of holes are arising: the reader can imagine that the underlying set lies in a cube like a lace of pearls stringed to its diagonal, and all the points in the rest of the brick are holes. However, these holes has no much importance and they are easy to get rid of: it can be proven that decomposing the stringed lattice to the 2-spined pieces does not effect quasi-equational theory, that is, a quasi-equation is valid in the stringed lattice iff it is valid in all of 2-spined pieces.

These holes behaved very passively and peacefully and no protesting voice could be heard during their elimination, since everyone detested them: they appeared everywhere and intruded to one’s day-by-day life without having anything worth to say. There are other kind of holes with quite an opposite character: they are agressive and shrill and eliminating them is not possible without getting irremediable wounds.

In fact we could count on their presence: the basic ortho-cylindric equations do not speak about any connexion between the ortho-cylindrifications, and it seems to be quite probable that being over unholed rists is such a specific situation that it effects the equational theory.

We will give the equations which set the ortho-cylindrifications in order and tune them in; these will be the consonance equations:

for k, l ∈ n c_{l}^{⊥} c_{k}^{⊥} (⋀_{j≠k} c_{j}^{⊥} x_{j}) = c_{k}^{⊥} (⋀_{j≠k} c_{j}^{⊥} x_{j}) ,

i.e. “c_{k}^{⊥} (⋀_{j≠k} c_{j}^{⊥} x_{j}) ∈ 𝔄_{sp}”. We will refer to the consonace equations by Cns.

“𝔄 ⊧ Cns” can be read as “𝔄 is consonant”.

Lemma 3.14. RDf_{n}^{⊥−} ⊧ Cns.

Proof. It is enough to prove the equations in UhDf_{n}^{⊥−}. Since proving this results faster and deeper understanding than reading a formal proof would result, it is left to the reader.

■

The consonance equations are really ortho-cylindric equations: for n ⩾ 3 cylindrifications in cylindric lattices do not fulfil them. The two-dimensional case is worth for a few words: this case they look like c_{k}^{⊥} c_{1−k}^{⊥} c_{k}^{⊥} x = c_{1−k}^{⊥} c_{k}^{⊥} x (i.e., “c_{1−k}^{⊥} c_{k}^{⊥} x ∈ 𝔄_{sp}”); — these are equivalent with the equation about commuting, i.e. c_{0}^{⊥} c_{1}^{⊥} x = c_{1}^{⊥} c_{0}^{⊥} x: consonance evidently follows from commuting, and using the consonance equations we get c_{0}^{⊥} c_{1}^{⊥} x ⩽ c_{0}^{⊥} c_{1}^{⊥} c_{0}^{⊥} x = c_{1}^{⊥} c_{0}^{⊥} x and similarly in the other direction. In higher dimensions consonance implies commuting (this will follow from Theorem 3.20.), though commuting does not imply consonance (consider the syntactic interpretation of ortho-cylindrification on cylindric lattices). Actually in dimension two consonance of a 2-spined algebra means that there is no element of the algebra which “sticks under the holes” from some direction. What do we mean by that?

We give two examples by two cylindric lattice diagrams.

[figure: ∘; •; ■; ∘; ∘; •; ■; •]

(Figure 3.15.)  (Figure 3.16.)

We advise the reader to follow how the discussed phenomena are realised in these examples as s/he reads the following paragraphs.

Let 𝒰 be a rist_{n}. We can “patch its holes”: let H denote the set of the holes of 𝒰; we embed 𝒰 in the unholed rist 𝒰^{+} which is defined on U ∪ H as it stands for reason: points of U are linked by the projection kernels if they were linked originally, the holes ⟨F_{0}, …, F_{n−1}⟩, ⟨F′_{0}, …, F′_{n−1}⟩ are linked by ≡_{k} iff F_{k} = F′_{k}, and u ≡_{k} ⟨F_{0}, …, F_{n−1}⟩ iff F_{k} = u/ ≡_{k} (in the examples the hole-symbolizing extra points of 𝒰^{+} are denoted by “∘”-s).

Now let us apply this patching method to a rist_{2} 𝒰; as follows, the Df_{2}^{⊥−}-operations are applied w.r.t. 𝒰^{+}.

We say X ⊆ U sticks under the holes from the vertical direction, if X ⊆ c_{0}^{⊥} H, and sticks under the holes from horizontal direction, if X ⊆ c_{1}^{⊥} H. Checking the definitions, we may see the following: X ⊆ U sticks under the holes from vertical direction, iff c_{0}^{⊥} c_{1}^{⊥} X ≠ 1 (and similarly for the other direction). Especially if 𝔄 ⩽ 𝔓_{Df}^{−}(𝒰), and 𝔄 is 2-spined, then 𝔄 is consonant iff no elements of 𝔄 stick under the holes from some of the two direction.

If 𝒰 is finite and 𝔄 is given by a partial order ⇾, then it is easy to see that there is an element of 𝔄 who sticks under the holes from vertical direction, iff c_{0}^{⊥} H contains a ⇾-minimal element of U, and similarly for horizontal direction. Thus we can check whether algebras of two dimension, given by a cylindric lattice diagram, are consonant or not: first we decompose it to 2-spined pieces, and then we check whether in these pieces minimal elements exist in the (ortho-)cylinders of the holes. (In higher dimensions consonance is a harder question.)

In Figure 2.4. and Figure 2.5. the pictured lattices are 2-spined; we can see a hole, but there is no minimal element in the column of the hole or in the row of the hole – thus these lattices are consonant. The lattice pictured in Figure 3.15. has holes and ■ sticks under the holes (from both direction), however, the algebra is not 2-spined; decomposing it to two-spined pieces we get two-element lattices (they can be pictured in a diagram like this: “•”), which are consonant, so the original lattice is consonant. And in Figure 3.16. we can see a two-spined non-consonant algebra – in this algebra again ■ sticks under a hole.

Now we will examine the power of consonace equations.

Lemma 3.17. Bocy ∪ Cns ∪ 2sp ⊧ c_{0}^{⊥} x_{0} ∧ … ∧ c_{n−1}^{⊥} x_{n−1} = 0 ⇒ (x_{0} = 0 or … or x_{n−1} = 0).

Proof. Assume we found a model of Bocy ∪ Cns ∪ 2sp 𝔄 and for k < n x_{k} ∈ 𝔄_{k} ∖ {0} such that x_{0} ∧ … ∧ x_{n−1} = 0. We will show that if for some k < n x_{0} ∧ … ∧ x_{k} = 0, then also x_{0} ∧ … ∧ x_{k−1} = 0: from this emerges a contradiction, because by iterating the procedure finally we get that x_{0} = 0.

So assume that for some k < n x_{0} ∧ … ∧ x_{k} = 0. Applying c_{k}^{⊥} to both sides we get that c_{k}^{⊥}(x_{0} ∧ … ∧ x_{k}) = 0; then by the Bocy-equation concerning intersection c_{k}^{⊥}(x_{0} ∧ … ∧ x_{k−1}) ∧ x_{k} = 0.

By a consonance equation c_{k}^{⊥}(x_{0} ∧ … ∧ x_{k−1}) ∈ 𝔄_{sp} (literally in the equation there are x_{j}-s from 𝔄_{j} intersected for all j ≠ k, but we can add 1 as an intersection factor for j = k+1, …, n−1). 𝔄 is two-spined, so c_{k}^{⊥}(x_{0}∧…∧x_{k−1}) ∈ {0, 1}. c_{k}^{⊥}(x_{0}∧…∧x_{k−1}) = 1 is not possible, because then 0 = c_{k}^{⊥}(x_{0} ∧ … ∧ x_{k−1}) ∧ x_{k} = 1 ∧ x_{k} = x_{k} would occur. So we can avoid the immediate contradiction only by c_{k}^{⊥}(x_{0} ∧ … ∧ x_{k−1}) = 0. Then by the extensivity of c_{k}^{⊥} x_{0} ∧ … ∧ x_{k−1} = 0 holds. That is what we needed. _{■}

As an easy application, we will introduce and axiomatize the following class of algebras, the representable diagonal-free ortho-cylindric algebras:

RDf_{n}^{⊥} =^{def} SP{⟨𝔓(U), c_{k}^{⊥}⟩_{k<n} | ⟨U, ≡_{k}⟩_{k<n} is an unholed rist},

so here complementation is also included. We will denote the set of the Boolean axioms by Bax.

Theorem 3.18. (Axiomatization of RDf_{n}^{⊥}) RDf_{n}^{⊥} = Mod(Bax ∪ Bocy ∪ Cns).

Proof. Of course RDf_{n}^{⊥} ⊧ Bax ∪ Bocy ∪ Cns.

Let 𝔄 ⊧ Bax ∪ Bocy ∪ Cns.

Since “BA’s are special DL’s”, all the results we have are valid in this case as well. So by Lemma 3.13. we can restrict ourselves to the case when 𝔄 is 2-spined. (We remind the reader that subdirect decompositions preseve equational theory in that sense according to which an equation is valid in 𝔄 if it is valid in all of the subdirect factors.) We will prove that 𝔄 has no holes.

Assume the contrary. Then for k < n we can find τ_{k} ∈ Con_{2,DL}𝔄_{k} such that their set-theoretic union does not extend in 𝔄. Since 𝔄 is an (extra-)Boolean algebra, it means that for k < n we can find x_{k} ∈ 𝔄_{k} such that x_{k} τ_{k} 1, x_{0} ∧ … ∧ x_{n−1} = 0. Then by Lemma 3.17. one of the x_{k}-s were 0. But x_{k} τ_{k} 1. Then τ_{k} is not a 2-congruence. It is a contradiction. _{■} Remark 3.19. As a special case we got the established axiomatization of RDf_{2} (cf. [HMT2, Thm. 5.1.47.]). Though we are at page 28 yet, if we have wanted to prove this axiomatization directly, we could have been quite short: as background for the axiomatization (done effectively in Lemma 3.17. and Theorem 3.18.), we need only the Interpretation Lemma (Lemma 1.9.), the Representation Theorem (Theorem 3.3.), and the 2-spinedness of subdirectly irreducible algebras. _{□}

Theorem 3.20. (Axiomatization of the variety generated by RDf_{n}^{⊥−}) HRDf_{n}^{⊥−} = Mod(Bocy ∪ Cns)

Proof. We know that HRDf_{n}^{⊥−} ⊧ Bocy ∪ Cns.

To see the other direction, it is enough to prove for the 2-spined case. Let 𝔄 be a 2spined algebra such that 𝔄 ⊧ Bocy ∪ Cns. We can suppose 𝔄 is a subalgebra of 𝔓_{Df}_{⊥−}(𝒰) for some rist_{n} 𝒰 = ⟨U, ≡_{k}⟩_{k<n}. We “patch the holes of U” (as we described this method after Figures 3.15., 3.16.), let 𝒰^{+} be the resulting unholed rist_{n} containing 𝒰 (and its base set will be denoted by U^{+}). Let 𝔅 = 𝔓_{Df}_{⊥−}(𝒰^{+}). 𝔅 ∈ UhDf_{n}^{⊥−}, so it is enough to show that 𝔄 ∈ HS𝔅; besides 𝔅 is a consonant 2-spined algebra.

We will define a suitable subalgebra of 𝔅 (called 𝔄^{+}) and we will show that relativizing to U (i.e., x ↦ x ∩ U) is a homomorphism of 𝔄^{+} onto 𝔄.

Let A denote the universe of 𝔄. A ⊆ 𝒫(U^{+}). 𝔄^{+} will be simply the subalgebra of 𝔅 generated by A. It is trivial that if relativizing to U is a homomorphism of 𝔄^{+}, then it is onto. For getting ahead, we should describe how 𝔄^{+} looks. Let Br = {c_{0}^{⊥𝒰^{+}} x_{0} ∩ … ∩ c_{n−1}^{⊥𝒰^{+}} x_{n−1} | x_{0}, …, x_{n−1} ∈ A} (Br is the set of A-bricks).

We claim that every element of 𝔄^{+} is of the form a∪ξ_{1} ∪…∪ξ_{m} for some a ∈ A, m ⩾ 0, ξ_{i} ∈ Br (the set of such elements will be denoted by Ã).

Of course, Ã ⊆ 𝔄^{+}, Ã is closed w.r.t. (binary) join, and ∅, U^{+} ∈ Ã.

Now we should see that Ã is closed w.r.t. intersection. Applying the distributive law on the Ã-elements (a ∪ ξ_{1} ∪ … ∪ ξ_{m}) ∩ (b ∪ η_{1} ∪ … ∪ η_{ℓ}) we get join members of the form a∩b, ξ_{i}∩η_{j}, a∩η_{j}, ξ_{i}∩b. We need that these join members are in Ã. Since A, Br is closed w.r.t. intersections, the first two kind of join members are in Ã. We must prove that for a ∈ A, Br ∋ ξ = c_{0}^{⊥𝒰^{+}} x_{0}∩…∩c_{n−1}^{⊥𝒰^{+}} x_{n−1}: a∩ξ ∈ Ã. For x ∈ A by the definition of 𝒰^{+} and c_{k}^{⊥}: c_{k}^{⊥𝒰} x = c_{k}^{⊥𝒰^{+}} x∩U. So a∩ξ = a∩U ∩ξ = a∩(c_{0}^{⊥𝒰^{+}} x_{0} ∩ U)∩…∩(c_{n−1}^{⊥𝒰^{+}} x_{n−1} ∩ U) =

a ∩ c_{0}^{⊥𝒰} x_{0} ∩ … ∩ c_{n−1}^{⊥𝒰} x_{n−1} ∈ A ⊆ Ã.

Our next aim is to see that Ã is closed w.r.t. c_{k}^{⊥𝒰^{+}} . Since c_{k}^{⊥𝒰^{+}} is additive, it is enough to see that for a ∈ Ã, ξ ∈ Br: c_{k}^{⊥𝒰^{+}} a, c_{k}^{⊥𝒰^{+}} ξ ∈ Ã. c_{k}^{⊥𝒰^{+}} a is in Br, so it is in Ã.

Let ξ = c_{0}^{⊥𝒰^{+}} x_{0} ∩ … ∩ c_{n−1}^{⊥𝒰^{+}} x_{n−1}, where the x_{k}-s are in A ∖ {∅}. Then c_{k}^{⊥𝒰^{+}} ξ = c_{k}^{⊥𝒰^{+}} x_{k} ∩ c_{k}^{⊥𝒰^{+}} (⋂_{j≠k} c_{j}^{⊥𝒰^{+}} x_{j}). Since 𝔅 ⊧ Bocy ∪ Cns ∪ 2sp, and the x_{j}-s are not empty,

by Lemma 3.17., c_{k}^{⊥𝒰^{+}} (⋂_{j≠k} c_{j}^{⊥𝒰^{+}} x_{j}) ∈ 𝔅_{sp} ∖ {∅} = {U^{+}}, so c_{k}^{⊥𝒰^{+}} ξ = c_{k}^{⊥𝒰^{+}} x_{k} ∈ Ã.

So we have seen that Ã is the universe of 𝔄^{+}. The time has come to see that relativizing to U (denoted by (∩U)) is a homomorphism.

As every relativization, it is a DL-homomorphism. For seeing that it preserves c_{k}^{⊥} as well, since c_{k}^{⊥} is additive, it is enough to show this in those cases when the argument is an element of A and when it is an element of Br. We noted that for x ∈ A c_{k}^{⊥𝒰} x = (c_{k}^{⊥𝒰^{+}} x)∩U, and since this case x = x∩U, it exactly means that c_{k}^{⊥} and (∩U) commutes on A.

Our only debt is to show that c_{k}^{⊥} and (∩U) commutes on Br. (This is the heart of the theorem: consider that up to this point we did not use the consonance of 𝔄.) What we need is that for x_{k} ∈ A ∖ {∅} (k ∈ n)

c_{k}^{⊥𝒰} (c_{0}^{⊥𝒰^{+}} x_{0} ∩ … ∩ c_{n−1}^{⊥𝒰^{+}} x_{n−1} ∩ U) = c_{k}^{⊥𝒰^{+}} (c_{0}^{⊥𝒰^{+}} x_{0} ∩ … ∩ c_{n−1}^{⊥𝒰^{+}} x_{n−1}) ∩ U.

The left side can be transcribed to c_{k}^{⊥𝒰^{+}} (c_{0}^{⊥𝒰^{+}} x_{0} ∩ … ∩ c_{n−1}^{⊥𝒰^{+}} x_{n−1} ∩ U) ∩ U. We will prove that the two sides are equal even if we omit the outer intersection with U, i.e.

c_{k}^{⊥𝒰^{+}} (c_{0}^{⊥𝒰^{+}} x_{0} ∩ … ∩ c_{n−1}^{⊥𝒰^{+}} x_{n−1} ∩ U) = c_{k}^{⊥𝒰^{+}} (c_{0}^{⊥𝒰^{+}} x_{0} ∩ … ∩ c_{n−1}^{⊥𝒰^{+}} x_{n−1})

holds. Applying the Bocy-equation concerning intersections on the right side of this last equation we get

(c_{k}^{⊥𝒰^{+}} x_{k}) ∩ c_{k}^{⊥𝒰^{+}} (⋂_{j≠k} c_{j}^{⊥𝒰^{+}} x_{j});

since 𝔅 is a 2-spined consonant algebra and the x_{j}-s are not empty, by Lemma 3.17.

c_{k}^{⊥𝒰^{+}} (⋂_{j≠k} c_{j}^{⊥𝒰^{+}} x_{j}) = U^{+},

so the right side is simply c_{k}^{⊥𝒰^{+}} x_{k}.

Applying that Bocy-equation once more we get that the left side is

(c_{k}^{⊥𝒰^{+}} x_{k}) ∩ c_{k}^{⊥𝒰^{+}} (⋂_{j≠k} c_{j}^{⊥𝒰^{+}} x_{j} ∩ U) = (c_{k}^{⊥𝒰^{+}} x_{k}) ∩ c_{k}^{⊥𝒰^{+}} (⋂_{j≠k} c_{j}^{⊥𝒰} x_{j});

so the equality of the two sides means that

c_{k}^{⊥𝒰^{+}} (⋂_{j≠k} c_{j}^{⊥𝒰} x_{j}) ⩾ c_{k}^{⊥𝒰^{+}} x_{k}.  (1)

Since for x ∈ A c_{k}^{⊥𝒰^{+}} c_{k}^{⊥𝒰} x = c_{k}^{⊥𝒰^{+}} x, if we prove

c_{k}^{⊥𝒰} (⋂_{j≠k} c_{j}^{⊥𝒰} x_{j}) ⩾ c_{k}^{⊥𝒰} x_{k},  (1’)

then we can verify (1) as well by applying c_{k}^{⊥𝒰^{+}} on both sides of (1’). Again, since 𝔄 is a 2-spined consonant algebra and the x_{j}-s are not empty, by Lemma 3.17. the left side of (1’) is U, which means (1’) is valid. So the relativization is homomorphism of the ortho-cylindrifications as well. _{■}

We have seen that the algebra pictured by Figure 2.4. is consonant; so by Theorem 3.20. this algebra is in HUhDf_{2}^{−}. However, using the general construction give in Theorem 3.20. the reader may try to find an unholed algebra which has a homomorphism onto the algebra of Figure 2.4.

Since “RDf_{2}^{−} = RDf_{2}^{⊥−}”, we gained an equational axiomatization for the variety generated by representable cylindric lattices of dimension two. (We state this result formally in the next section, which is about representable cylindric lattices of dimension two: see Theorem 4.3.)

3.3. The elimination alternatives

In this subsection we will give a general necessary and sufficient condition for being in RDf_{n}^{⊥}.

Lemma 3.21. Assume that ℒ, ℒ′ are complete lattices, and

[figure: ℒ′; g; ℒ; f]

is a Galois connection (that is, f, g are antimonotone and f ∘ g, g ∘ f are extensive). (In order to make our notations more perpicuous, we will use the notations f(ϑ) = \overline{ϑ} (ϑ ∈ ℒ), g(ϑ′) = \overline{ϑ′} (ϑ′ ∈ ℒ′).) Then

i) g∘f, f ∘g are closure operators, where the closed elements in ℒ′ are exactly the ones of the the form \overline{ϑ} (ϑ ∈ ℒ) and vice versa, and f, g are dual isomorphisms between the lattice of closed elements in ℒ and in ℒ′;

ii) for X ⊆ ℒ (or X ⊆ ℒ′)

⋀_{ϑ∈X} \overline{ϑ} = \overline{⋁_{ϑ∈X} ϑ},  (2)

and

iii)  \overline{⋁_{ϑ∈X} \overline{ϑ}} = ⋀_{ϑ∈X} \overline{\overline{ϑ}}, and
iv)  ⋁_{ϑ∈X} \overline{ϑ} ⩽ \overline{⋀_{ϑ∈X} ϑ}.

Proof. The reader may find these in [?]. _{■}

We call a lattice ℒ strongly dual atomic if every element of the lattice is the intersection of some dual atoms. For ϑ ∈ ℒ L(ϑ) will denote the set of the dual atoms greater than or equal with him. Then “ℒ is strongly dual atomic” means that ϑ = ⋀ L(ϑ).

The set of dual atoms will be denoted by Dat.

Lemma 3.22. (A generalization of the distributive law) Let ℒ be a complete strongly dual atomic distributive lattice, and for i ∈ I let ϑ_{i0}, …, ϑ_{i,n−1} ∈ L. Then

⋁_{i∈I} ⋀_{k<n} ϑ_{ik} = ⋀_{k⃗∈n^{I}} ⋁_{i∈I} ϑ_{ik_{i}}  (gdl)

Proof. Consider that

[figure: 𝔓^{−}(Dat); ⋀; ℒ; L]

forms a Galois connection. We will also use here the notations \overline{Y} = ⋀ Y (Y ∈ 𝔓^{−}(Dat)) and \overline{ϑ} = L(ϑ) (ϑ ∈ ℒ).

Because of being strongly dual atomic, if ϑ ∈ ℒ

\overline{\overline{ϑ}} = ϑ.  (3)

Then from Lemma 3.21. iii) and (3) follows that for X ⊆ ℒ

\overline{⋃_{ϑ∈X} \overline{ϑ}} = ⋀_{ϑ∈X} ϑ.  (4)

Now assume X is finite, say, X = {ϑ_{0}, …, ϑ_{n−1}}. Then for τ ∈ Dat

τ ∈ L ( ⋀_{k<n} ϑ_{k}) ⟺ τ ⩾ ⋀_{k<n} ϑ_{k} ⟺ τ ∨ ( ⋀_{k<n} ϑ_{k}) = τ ⟺ ⋀_{k<n}(τ ∨ ϑ_{k}) = τ.

If so, τ ⩾ ϑ_{j} must be for some j, because otherwise all the joins “τ ∨ ϑ_{k}” would be strictly greater than τ, i.e. all of them would be 1, and then τ = ⋀_{k<n}(τ ∨ ϑ_{k}) = 1 would occur, which is a contradiction. This means τ ∈ L(ϑ_{j}), anyway τ ∈ ⋃_{k<n} L(ϑ_{k}). Hence L (⋀_{k<n} ϑ_{k}) ⊆ ⋃_{k<n} L(ϑ_{k}), that is, ⋃_{k<n} \overline{ϑ}_{k} ⊇ \overline{⋀_{k<n} ϑ_{k}}. From this and Lemma 3.21. iv) follows

⋃_{k<n} \overline{ϑ}_{k} = \overline{⋀_{k<n} ϑ_{k}}.  (5)

So using these rules and the distributivity law for sets:

⋁_{i∈I} ⋀_{k<n} ϑ_{ik} =^{(3)} \overline{\overline{⋁_{i∈I} ⋀_{k<n} ϑ_{ik}}} =^{(2)} \overline{⋂_{i∈I} \overline{⋀_{k<n} ϑ_{ik}}} =^{(5)} \overline{⋂_{i∈I} ⋃_{k<n} \overline{ϑ}_{ik}} =

\overline{⋃_{k⃗∈I^{n}} ⋂_{i∈I} \overline{ϑ}_{ik_{i}}} =^{(2)} \overline{⋃_{k⃗∈I^{n}} \overline{⋁_{i∈I} ϑ_{ik_{i}}}} =^{(4)} ⋀_{k⃗∈I^{n}} ⋁_{i∈I} ϑ_{ik_{i}}

■

We recall that a variety is semi-simple if its subdirectly irreducible algebras are simple (cf. [BS]).

Corollary 3.23. Let t′ ⊆ t be algebraic types, let V be a congruence-distributive semisimple variety of type t′ and and K be a class of algebras of type t such that [K]_{t′} ⊆ V. Then (gdl) is valid in congruence lattices of algebras of K.

Proof. First we prove that (gdl) is valid in the congruence lattices of algebras of V. Let 𝔄 ∈ V. We will prove that Con𝔄 is strongly dual atomic (by hypothesis it is distributive). Let ϑ ∈ Con𝔄. Then ϑ is the intersection of some ∧-irreducible congruences. But because of semi-simplicity, every ∧-irreducible congruence is a dual atom in Con𝔄 (for τ ∈ Con𝔄 𝔄/τ is subdirectly irreducible iff τ is ∧-irreducible, and 𝔄/τ is simple iff τ is a dual atom). So ϑ is intersection of dual atoms. (In fact, we have seen that “the congruence lattices are strongly dual atomic” is just semi-simplicity said in lattice-theoretic terms.)

Now let 𝔄 ∈ K. Then Con𝔄 ⊆ Con_{t′}𝔄, and both Con𝔄, Con_{t′}𝔄 are complete sublattices of the partition lattice of the universe of 𝔄. So Con𝔄 is a complete sublattice of Con_{t′}𝔄. In the latter (gdl) holds, since the t′-reduct of 𝔄 is in V. Then Con𝔄 inherits (gdl) from Con_{t′}𝔄. _{■}

Corollary 3.24. In congruence lattices of algebras of RelDf_{n}^{⊥−} (gdl) is valid.

Proof. The previous Corollary should be applied in the K = RelDf_{n}^{⊥−} and V = DL case.

■

The following definition is motivated by Definition 3.4., Remark 3.5. and Theorem 3.6. In the next theorem we will use this stuff without further reference. (∗) will refer to that formula given in Theorem 3.6., which is labeled by this symbol.

Definition 3.25. Let 𝔄 ∈ RelDf_{n}^{⊥−}.

If y_{k}, x_{k} ∈ 𝔄_{k}, y_{k} < x_{k} (k < n) and x_{0} ∧ … ∧ x_{n−1} ⩽ y_{0} ∨ … ∨ y_{n−1}, we will say that the x_{k}, y_{k}-s form a hole configuration χ (formally we can interpret χ as the sequence ⟨⟨y_{k}, x_{k}⟩⟩_{k<n}), and the sequence ⟨⟦⟨y_{k}, x_{k}⟩⟧⟩_{k<n} will be called the elimination alternative of χ denoted by e(χ) = ⟨e_{0}(χ), …, e_{n−1}(χ)⟩. We will denote the set of the hole-configurations by Hc.

If Γ ⊆ 𝔄^{2}, Γ^{∗} will denote the DL-congruence of 𝔄 generated by Γ (thus Γ^{∗} and ⟦Γ⟧_{DL} are two notations for the same thing). _{□}

In the proof of the following theorem we will use Corollary 4.9. The proof of this statement is quite an elementary, but the proof uses some notions, which fit into the the subject of Section 4.

Theorem 3.26. Let 𝔄 ∈ RelDf_{n}^{⊥−}. Then 𝔄 ∈ RDf_{n}^{⊥−} iff every elimination alternative in 𝔄 is a subdirect decomposition.

Proof.

• First we prove that 𝔄 ∈ RDf_{n}^{⊥−} iff

Q = { ⋁_{χ∈Hc} e_{k_{χ}}(χ) | k⃗ ∈ n^{Hc}}

is a subdirect decomposition.

(→) Assume that 𝔄 ∈ RDf_{n}^{⊥−}. Then we can find a subdirect decomposition G ⊆ Con𝔄 such that for all ϑ ∈ G 𝔄/ϑ is unholed.

Let ϑ ∈ G arbitrary. Assume y_{k} < x_{k} ∈ 𝔄_{k} (k < n) form a hole configuration χ, that is, x_{0} ∧ … ∧ x_{n−1} ⩽ y_{0} ∨ … ∨ y_{n−1}. This is valid in 𝔄/ϑ as well with the x_{k}/ϑ, y_{k}/ϑ-s. However, since 𝔄/ϑ is unholed, (∗) holds in 𝔄/ϑ, so for some k y_{k}/ϑ ⩾ x_{k}/ϑ. Since y_{k} < x_{k}, this means y_{k}/ϑ = x_{k}/ϑ, i.e. ϑ ⩾ e_{k_{χ}}.

Thus for all χ ∈ Hc we can find an index k_{χ} ∈ n for which ϑ ⩾ e_{k_{χ}}(χ). So we get ϑ ⩾ ⋁_{χ∈Hc} e_{k_{χ}}(χ) ∈ Q; since ϑ was taken arbitrarily, Q is downward cofinal in G. It means that Q is also a subdirect decomposition.

(←) We will prove that factorizing 𝔄 with an element of Q provides an unholed algebra. Let ϑ = ⋁_{χ∈Hc} e_{k_{χ}}(χ) be. For k < n let Γ_{k} = {χ_{k} | χ ∈ Hc, k_{χ} = k} ⊆ (𝔄_{k})^{2} be;

of course, ϑ = ⟦Γ_{0} ∪ … ∪ Γ_{n−1}⟧. Let ϑ_{k} = ϑ↾_{𝔄_{k}} be. Clearly ϑ ⊇ ϑ_{0}^{∗} ∨ … ∨ ϑ_{n−1}^{∗}. On the other hand, for k < n ϑ_{k} ⊇ Γ_{k}, and by Corollary 4.9., ϑ_{0}^{∗} ∨ … ∨ ϑ_{n−1}^{∗} ∈ Con𝔄, so ϑ ⊆ ϑ_{0}^{∗} ∨ … ∨ ϑ_{n−1}^{∗}. We got ϑ = ϑ_{0}^{∗} ∨ … ∨ ϑ_{n−1}^{∗}.

Let ( ·)′ denote the Con_{DL}(𝔄/ϑ) ⟶ Con_{DL}𝔄 natural embedding (that is, for γ ∈ Con_{DL}(𝔄/ϑ), a, b ∈ 𝔄 a γ′ b ⟺ (a/ϑ) γ (b/ϑ)). Its image is {η ∈ Con_{DL}𝔄 | η ⩾ ϑ}; on this set we can define its inverse, ( ·)^{∘}. We will also use this notation for the Con_{DL}(𝔄_{k}/ϑ_{k}) ⟶ Con_{DL}𝔄_{k} natural embeddings (where the image is {η_{k} ∈ Con_{DL}𝔄_{k} | η_{k} ⩾ ϑ_{k}}).

Now assume 𝔄/ϑ has a hole, i.e. assume that τ_{k} ∈ Con_{2,DL}(𝔄/ϑ)_{k} = Con_{2,DL} (𝔄_{k}/ϑ_{k}) (k < n) and τ_{0}^{∗} ∨…∨τ_{n−1}^{∗} = 1. So τ′_{k} ⩾ ϑ_{k}, and then τ′_{0}^{∗} ∨…∨τ′_{n−1}^{∗} ⩾ ϑ_{0}^{∗} ∨…∨ϑ_{n−1}^{∗} = ϑ. It means that “τ′_{0}^{∗} ∨…∨τ′_{n−1}^{∗} is a DL-congruence of 𝔄/ϑ”, saying it more precisely, it can be factorised to a congruence of 𝔄/ϑ by ( ·)^{∘}. Thus (τ′_{0}^{∗} ∨ … ∨ τ′_{n−1}^{∗})^{∘} is a DL-congruence of 𝔄/ϑ out of joke, and it contains τ_{k} for all k < n, so by our assumption it is 1. We go back to Con_{DL}𝔄 by ( ·)′, and we get that τ′_{0}^{∗} ∨ … ∨ τ′_{n−1}^{∗} = 1. So the tuple of the τ′_{k}-s is a hole. Then we can find y_{k} < x_{k} ∈ 𝔄_{k} such that y_{k} τ′_{k} 0, x_{k} τ′_{k} 1 (k < n) and they form a hole-configuration χ. Let k = k_{χ} be. From τ′_{k} ⩾ ϑ_{k} and x_{k} ϑ y_{k} follows x_{k} τ′_{k} y_{k}. However, y_{k} τ′_{k} 0, x_{k} τ′_{k} 1, which means 0 τ′_{k} 1. It is a contradiction.

• We will prove that Q is a subdirect decomposition iff the elimination alternatives are all subdirect decompositions.

The proof consists of applying (gdl) to the elimination alternatives: by (gdl)

⋁_{χ∈Hc} (e_{0}(χ) ∧ … ∧ e_{n−1}(χ)) = ⋀ Q

— the left side is the identic congruence (that is, Q is a subdirect decomposition) iff all of its join members are the identic congruence (that is, all elimination alternatives are subdirect decompositions). _{■}

3.4. The symmetric case

Now we are at the end of the section. We digress on the symmetric case in a few words. In order to not to spend too much time with this, we may omit declarations: as it is usual, τ will be a 2-congruence, k is a natural number smaller than n, etc. We hope that the reader is accustomed to these stereotypic declarations and it will not be confusing. (We will make a reference to a yet non-proved statement again: to Lemma 4.2.)

We will use the word Bocy as it includes the axioms concerning ortho-axifications. In the following we will discuss briefly what happens with the certain results of this section, if ortho-axifications are also included.

Theorem 3.3. (Representation Theorem) : The most important fact that in models of Bocy an element is c_{k}^{⊥}-closed iff a_{k}^{⊥}-closed. So the expression “k-closed” is not ambiguous, and we can define the canonical representation in the same way. We claim that Birkhoff’s embedding preserves a_{k}^{⊥} as well.

We know it is a homomorphism on the asymmetric reduct, especially we know that the representation of k-closed elements is also k-closed. It means representation of k-closed elements includes a k-fibre or is disjoint from it. Over any rist a_{k}^{⊥} x is the union of those k-fibres, which are included in x. So we have to see that the representation of an element includes a k-fibre iff the representation of its k-th ortho-axis includes that k-fibre. If the representation of the k-th axis includes a k-fibre, then the representation of the element also includes that k-fibre, since x ⩾ a_{k}^{⊥} x.

We should see the other direction. “x̃ includes the k-fibre F_{τ_{k}}” means that any time the restriction of τ to 𝔄_{k} is τ_{k}, then x τ 1. The intersection of those τ-s, whose restriction to 𝔄 is τ_{k}, is just τ_{k}^{∗}, so x̃ includes the k-fibre iff x τ_{k}^{∗} 1. This latter means that we can find an x_{k} τ_{k} 1 and an y_{k} τ_{k} 0 such that (x ∧ x_{k}) ∨ y_{k} = (1 ∧ x_{k}) ∨ y_{k} (cf. Lemma 4.2.), i.e. x ∨ y_{k} ⩾ x_{k}. Applying a_{k}^{⊥} on both sides we get the same for a_{k}^{⊥} x, which means (a_{k}^{⊥} x) τ 1, so ã_{k}^{⊥} also includes that fibre.

Since canonical representation works in the symmetric case as well, here we can use the same hole-notion and we get the same result. So Theorem 3.6. preserves its validity in the symmetric case. This implies that Corollary 3.7. also preserves its validity.

If 𝔄 is a symmetric relation algebra, then its canonical representation and the canonical representation of its asymmetric reduct is the same (Birkhoff’s embedding is the representating mapping in both cases). So the symmetric version of Theorem 3.10. is a true statement.

And then comes the only non-trivial problem about ortho-axifications: their equality theory — it is not true that consonant symmetric relation algebras are representable! So Theorem 3.20. losts its validity if the ortho-axifications are included. We will discuss this this phenomenon in Section ??

Theorem 3.26.: Since symmetric relation algebras also have DL-reduct, and their holes has the same properties as holes of asymmetric relation algebras, the proof of the theorem which says an algebra is representable iff all the elimination alternatives are subdirect decompositions, is word-by-word the same as in the asymmetric case (as one can see, the yet unproved Corollary 4.9. is also valid in the symmetric case).

To sum it up:

Theorem 3.27. We get true statements if in Theorem 3.3., Theorem 3.6., Corollary 3.7., Theorem 3.10., or in Theorem 3.26. we substitute the superscript “−” with “±”. _{■}

4. Representable asymmetric cylindric lattices of dimension two

Notations, conventions.

Boolean operations: ⊕ will stand for symmetric difference; if X, Y ⊆ U, then let the coincidence of X and Y be the set X ≎ Y = {u ∈ U | u ∈ X ⟺ u ∈ Y }, or abstractly, x ≎ y = ∖(x ⊕ y) = (x ∧ y) ∨ ((∖x) ∧ (∖y)).

When we write “A ⊂ B” we mean that “A = B” is excluded.

4.1. Visualization of DL-congruences

Let 𝔇 be a distributive lattice, and ⟨U, φ⟩ be a representation of 𝔇. With relativization we may produce congruences from subsets of U: if X ⊆ U, we define the congruence ϑ_{X} as for a, b ∈ 𝔇 let a ϑ_{X} b iff φ(a) ∩ X = φ(b) ∩ X, or with other words, φ(a) ≎ φ(b) ⊇ X. On the other hand, we may produce subsets of U from binary relations on 𝔇: for Γ ⊆ 𝔇^{2} let

L_{φ}(Γ) = ⋂_{⟨a,b⟩∈Γ}(φ(a) ≎ φ(b)), D_{φ}(Γ) = U ∖ L_{φ}(Γ) = ⋃_{⟨a,b⟩∈Γ}(φ(a) ⊕ φ(b)).

— we will call these the living set and the dead set of Γ (w.r.t φ), respectively. From Stone duality (which can be adapted to DL’s this way) we know the following:

for Γ ⊆ 𝔇^{2} D_{φ}(Γ) = D_{φ}(Γ^{∗}) (i.e. L_{φ}(Γ) = L_{φ}(Γ^{∗})); there are further useful properties but not every representation has them; so we will say a representation ⟨U, φ⟩ is a nice representation if it has the following properties: D_{φ} embeds Con𝔇 to 𝔓^{−}(U), and for a congruence ϑ ϑ = ϑ_{L_{φ}(ϑ)}. We know that canonical representations are nice, and every representation of a finite DL is nice (cf. [?]). By the way, restricting a nice representation to a sublattice, we get a nice representation of that sublattice; this does not hold for canonical representations.

This is a kind of visualization of DL-congruences: this way abstract DL congruences and their interrelations can be pictured just like subsests of a universe and set-operations on them are pictured with shapes in a Venn diagram.

Remark 4.1. The mappings “relativizing to subsets of U” and L_{φ} forms a Galois connection between 𝔓^{−}(U) and 𝔓^{−}(𝔇^{2}). The reader may consider that in case U is Con_{2}𝔇 and φ is Birkhoff’s embedding, this Galois connection is an extension of the one mentioned in the proof of (gdl) (Lemma 3.22.), with ℒ = Con𝔇 and Dat = Con_{2}𝔇. _{□}

Now we fix a nice representation of 𝔇, and we identify the elements of 𝔇 with their represented versions; moreover, we omit the subscript φ, and we will write purely L, D. (And any time we speak of living/dead sets, if it does not give rise to ambiguities, we may omit the subscript referring to the representation.)

As the first application of this apparatus, we prove the following lemma, which we have already applied in the last section:

Lemma 4.2. Let 𝔇′ ⩽ 𝔇, τ ∈ Con_{2}𝔇′. Then for a, b ∈ 𝔇 a τ^{∗} b iff for some x, y ∈ 𝔇′, y τ 0, x τ 1 (a ∧ x) ∨ y = (b ∧ x) ∨ y.

Proof. In the proof we will use set-operation symbols (∩, ∪) instead of abstract latticeoperation symbols (∧, ∨), since we identified elements with their represented versions.

If a τ^{∗} b, then a, b are equlaized by a finite part of τ, that is, we can find x_{1}, …, x_{r} τ 1 and y_{1}, …, y_{s} τ 0 such that ⟨a, b⟩ ∈ ⟦({x_{1}, …, x_{r}} × {1}) ∪ ({y_{1}, …, y_{s}} × {0})⟧. However, declaring x = ∩_{i}x_{i}, y = ∪_{j}y_{j}, we get the same congruence generating with ⟨x, 1⟩ and ⟨y, 0⟩. L({⟨x, 1⟩ , ⟨y, 0⟩}) = x ∖ y, so ⟨a, b⟩ ∈ ⟦⟨x, 1⟩ , ⟨y, 0⟩⟧ iff a ∩ x ∖ y = b ∩ x ∖ y; by adding y to both sides, we get equivalently that (a ∩ x) ∪ y = (b ∩ x) ∪ y. _{■}

The notions and observations made in this subsection will be automaticly used in the cylindric context, which makes sense if we think of the DL-reduct.

4.2. Axiomatizing RDf_{2}^{−}

First of all, terminology conversions:

We will work in type ⟨∧, ∨, 0, 1, c_{0}, c_{1}⟩.

Since in dimension two c_{0}^{⊥} = c_{1} and c_{1}^{⊥} = c_{0} (cf. Lemma 2.8.), we will speak about cylindrifications but we may apply on them the theorems about ortho-cylindrifications.

If 𝔄 is an algebra of type Df_{2}^{−} such that c_{0}, c_{1} are closure operators, we will say x ∈ 𝔄 is k-closed, if it is closed w.r.t. c_{k} (k = 0, 1) (of course, 𝔄_{k} will denote the set of k-closed elements). This makes an important difference:

Let 𝒰 be a rist_{2}. To make our terminology more descriptive, 0-fibres will be referred to as columns, and 1-fibres will be referred to as rows. According to the the present terminology we say X ⊆ 𝒰 is 0-closed, if it is closed w.r.t. c_{0}^{𝒰}, that is, if it is the union of some rows — although this means X is closed w.r.t. c_{1}^{⊥𝒰}, so in the old sense this would mean the 1-closedness of X.

Moreover we will use Bcy (“basic cylindric equations”) instead of Bocy (of course, it is meant as we can get Bcy from Bocy by substituting ortho-cylindrifiactions with cylindrifications).

We state here a version of an ortho-cylindric result being adjusted to the 2-dimensional cylindric context:

Theorem 4.3. (Axiomatization of the variety generated by RDf_{2}^{−}) HRDf_{2}^{−} = Mod(Bcy ∪ Cns)

Proof. Cf. Theorem 3.20., Lemma 2.8. _{■}

Now we present an important example:

\begin{aligned}•_{2} & [figure] & • & [figure] & • & [figure] & •_{1} & [figure] & • & [figure] & • & [figure] & • & [figure] & [figure] & [figure] & •_{0} & • & • & [figure] & • & [figure] & •_{0} & •_{1} & [figure] & •_{2} & [figure] \\ & (Figure 4.4.) \end{aligned}

4.2. Axiomatizing RDf_{2}^{−} 37

The asymmetric algebra given in the diagram will be referred to as 𝔄^{20}; of course, we refer to the rist_{2} pictured the diagram by 𝒰 = ⟨U, ≡_{0}, ≡_{1}⟩, and to the partial order by ⇾ (the reader may check that the conditions of Theorem 2.17. i) are fulfilled, thus the diagram really defines an asymmetric algebra) . For i = 0, 1, 2 the column over •_{i} of the 0th (horizontal) axis (the i-th column) will be denoted by C_{i}, and the row at the height of •_{j} of the 1st (vertical) axis (the j-th row) will be denoted by R_{j}. The i-th element of the j-th row (the only element of C_{i} ∩ R_{j}) will be denoted by u_{ij}.

Lemma 4.5. 𝔄^{20} ∈ HRDf_{2}^{−} ∖ RDf_{2}^{−}.

Proof. We can see that 𝔄^{20} is 2-spined. Thus – according to those observations we made between Figure 3.16. and Lemma 3.17. – 𝔄^{20} is consonant, since there is no element sticking under the hole. Thus by Theorem 4.3. 𝔄^{20} is in HRDf_{2}^{−}.

However, we can see a hole of 𝔄^{20} in the position ⟨2, 2⟩; we can immediately find a hole configuration to this hole: the one formed by y_{0} = R_{0} ∪ R_{1}, y_{1} = C_{0} ∪ C_{1}, x_{0} = x_{1} = U; then the corresponding elimination alternative consist of the congruences e_{0} = ⟦⟨y_{0}, U⟩⟧ and e_{1} = ⟦⟨y_{1}, U⟩⟧. We have to see that D(e_{0}) ∩ D(e_{1}) ≠ ∅, because then – by the nicety of the given representation – e_{0} ∧ e_{1} ≠ 0, that is, the elmination alternative ⟨e_{0}, e_{1}⟩ is not a subdirect decompositon; then by Theorem 3.26. 𝔄^{20} ∉ RDf_{2}^{−}.

e_{1} ⊇ ⟨y_{1}, U⟩^{∗}, so D(e_{1}) ⊇ D({⟨y_{1}, U⟩}) = C_{2}. We get similarly that D(e_{0}) ⊇ R_{2}. From this follows that the “hook-shaped set” C_{0} ∪ {u_{12}} is congruent with C_{0} modulo e_{1}; then so are their 1st (vertical) cylinders, C_{0} ∪ C_{1} and C_{0}. So C_{1} = (C_{0} ∪ C_{1}) ⊕ C_{0} ⊆ D(e_{1}). (We can say “the hook got caught in the eliminated row”.) Thus ⟨R_{0}, R_{0} ∪ {u_{11}}⟩ ∈ e_{1}; applying c_{0} to both co-ordinates, we get ⟨R_{0}, R_{0} ∪ R_{1}⟩ ∈ e_{1}, so R_{1} ⊆ H(e_{1}). Then u_{21} ∈ C_{2} ∩ R_{1} ⊆ D(e_{1}) ∩ D(e_{0}).

Alternatively, the reader may find out how to substitute the variables to the second quasi-equation given in the axiomatization of RDf_{2}^{−} to refute it in 𝔄^{20} (see Theorem 4.21.; the validity of this quasi-equation in RDf_{2}^{−} is proved in Lemma 4.18.); — the above reasoning suggests the reader how and which elements of 𝔄^{20} may have a role in such a quasi-equation. _{■}

From this, after getting through some technical manoeuvres follows

Theorem 4.6. For n ⩾ 2 RDf_{n}^{⊥−} and RDf_{n}^{−} are not varieties.

Proof. The geometric idea behind the follwing arguments is the following: a rist_{2} can be thougth of as a rist_{n}, where ≡_{2}, …, ≡_{n−1} are the full equivalence (still more intuitively, a subset of the two-dimensional space can be thought of as a subset of the n-dimensional space, since the two-dimensional space can be embedded in the n-dimensional space).

If 𝔄^{∗} is an algebra of RDf_{n}^{⊥−} or of RDf_{n}^{−} for some n ⩾ 2, then [𝔄]_{Df}_{2}^{−} ∈ RDf_{2}^{−} (if 𝔄^{∗} is ortho-cylindric, this makes sense using the syntactic definition of cylindrifications: c_{k} = c_{k}^{⊥}), as it immediately follows from the following observation:

Let 𝒰 be an unholed rist_{n}; then [𝔓_{Df}_{⊥−}(𝒰)]_{Df}_{2}^{−} and [𝔓_{Df}^{−}(𝒰)]_{Df}_{2}^{−} are in RDf_{2}^{−}; — the first one is representable, since ⟨U, ≡_{0}, ≡_{1}⟩ is still unholed, and the second one is representable, since it is isomorphic with ∏_{i} 𝔓_{Df}^{−}(𝒰_{i}), where the 𝒰_{i}-s are the classes of the equivalence (∩_{k≠0} ≡_{k}) ∨ (∩_{k≠1} ≡_{k}) = ∩_{k≠0,1} ≡_{k}, being made to a rist_{2} with the restrictions of ≡_{0}, ≡_{1} (of course, the 𝒰_{i}-s are unholed).

Now let 𝔄 ∈ HRDf_{2}^{−} ∖ RDf_{2}^{−}. If we can define c_{0}^{⊥} = c_{0}, c_{1}^{⊥} = c_{1}, c_{2}^{⊥}, …, c_{n−1}^{⊥} (respectively, c_{2}, …, c_{n−1}) on 𝔄 such that the resulting algebra 𝔄^{∗} is in HRDf_{n}^{⊥−} (respectively, HRDf_{n}^{−}), then – since 𝔄^{∗} cannot be in RDf_{2}^{−} – we can see RDf_{n}^{⊥−} (respectively, RDf_{n}^{−}) is not closed w.r.t. taking homomorphic images, hence it is not variety.

We may assume that our algebra 𝔄 is 2-spined: if it were not, some of its subdirect irreducible factors should also be non-representable, and, of course, this factor is 2-spined (cf. Lemma 3.13.), or we can say directly 𝔄 = 𝔄^{20}.

Thus we can choose a surjective homomorphism φ : 𝔅 ⟶ 𝔄, where 𝔅 ⩽ 𝔓_{Df}^{−}(𝒰) for some unholed rist_{2} 𝒰: for example, we may represent 𝔄 over some rist_{2}, and then we get φ, 𝔅 and 𝒰 by patching the holes of this rist_{2}, as we did in the proof of Theorem 3.20.; in case of 𝔄^{20} it is easy to see how these things look like. We enrich 𝒰 to a rist_{n} 𝒰^{∗} with n − 2 piece of full equivalences as projection kernels. Of course, 𝒰^{+} is still unholed.

These new projection kernels induce n−2 pieces of new ortho-cylindrifications on 𝔅 – all of them will be the switching-on function (the one which maps each element to 1, except for 0, which stays fix) –, giving us 𝔅^{∗} ∈ RDf_{n}^{⊥−}. Since Ker φ has the substitution property w.r.t. the switching-on function (the reader may consider that φ(b) = 0 ⇒ b = 0), we may push out the Df_{n}^{⊥−}-structure of 𝔅^{∗} to 𝔄 by φ, getting this way the desired 𝔄^{∗} ∈ HRDf_{n}^{⊥−}.

We proceed similarly in the cylindric case: this time first we assume 𝒰 is a strict rist_{2} (which we can do because of the Interpretation Lemma (Lemma 1.9., by inflating the molecules into bricks), or in case of 𝔄^{20} 𝒰 will be strict automatically). This case the new projection kernels of 𝒰^{∗} induce n − 2 pieces of new, identic cylindrifications on 𝔅, giving us 𝔅^{∗} ∈ RDf_{n}^{−}. Pushing out the Df_{n}^{−}-structure of 𝔅^{∗} to 𝔄 by φ, we get this way the desired 𝔄^{∗} ∈ HRDf_{n}^{−}.

A similar result (using different methods) can be found in [Andréka, Thm.7./(ii)]. Now we return to the case of 𝔄^{20} for a moment: here, widening the starting dead set

x_{0} ⊕ y_{0} by applying cylindrifications on the hook-shaped sets twice, we could see D(e_{0}) is big enough to make e_{0} ∧e_{1} non-identic. We get a similar sample of non-representability, if we interchange the two axes; then, of course, x_{1} ⊕y_{1} will be widened in two steps, showing D(e_{1}) is big. Now consider the algebra pictured on Figure 2.4., which we will call 𝔄^{11}. Referring to elements of 𝔄^{11} in the same way as we did in case of 𝔄^{20}, the reader may see that both starting dead sets x_{k} ⊕ y_{k} are widened once by applying cylindrifications on hook-shaped sets, thus we can see D(e_{0}) ∩ D(e_{1}) is not empty.

These are the basic samples of non-representability. In the rest of the section we will search for similar configurations in the general non-representable case, and examine the connection between these configurations and quasi-equational theory.

Let 𝔄 be an algebra of type Df_{2}^{−} such that 𝔄 ⊧ Bcy, though 𝔄 is not representable. We may assume 𝔄 is given over a rist_{2} 𝒰, and the identic representation of 𝔄 is nice. (Thus we will use set-operation symbols (∩, ∪) instead of abstract ones, and we may apply any set operation on elements of 𝔄, and we may apply cylindricification on sets out of 𝔄.)

By Theorem 3.26. we can find a hole configuration x_{0}, y_{0} ∈ 𝔄_{0}, y_{0} ⊂ x_{0}, x_{1}, y_{1} ∈ 𝔄_{1}, y_{1} ⊂ x_{1}, x_{0} ∩ x_{1} ⊆ y_{0} ∪ y_{1} such that the corresponding elimination alternative e (i.e. e_{k} = ⟦⟨y_{k}, x_{k}⟩⟧, k = 0, 1) is not a subdirect composition, that is, e_{0} ∧ e_{1} ≠ 0, which means D(e_{0}) ∩ D(e_{1}) ≠ ∅. We intend to describe (a part of) the set D(e_{0}) ∩ D(e_{1}). For this aim we need some kind of characterization of e_{0}, e_{1}.

Definition 4.7. Let t′, t′′ ⊆ t be algebraic types, 𝔛 be an algebra of type t, and Q ⊆ 𝔛^{2}. Then let

Op_{t′′}(Q) =^{def}

{⟨f(x_{1}, …, x_{n}), f(y_{1}, …, y_{n})⟩ | f is an n-ary operation of type t′′, ⟨x_{i}, y_{i}⟩ ∈ Q}

□

Lemma 4.8. Let 𝔛, t, t′, Q be as above. For n ⩾ 0 we recursively define the following relations:

• γ_{0} = ⟦Q⟧_{t′};

• γ_{n+1} = γ_{n} ∨ ⟦Op_{t∖t′}(γ_{n})⟧_{t′}.

Then ⋁_{n⩾0} γ_{n} = ⟦Q⟧.

Proof. The proof is left to the reader. _{■}

[ Before getting ahead, we pay off one debt: we prove a corollary of Lemma 4.8. which

was used in the proof of Theorem 3.26.

Corollary 4.9. Let 𝔄 ∈ RelDf_{n}^{⊥−}. Let ϑ ∈ Con𝔄 and ϑ_{k} = ϑ↾_{𝔄_{k}} (k < n).

Then ϑ′ = ϑ_{0}^{∗} ∨ … ∨ ϑ_{n−1}^{∗} ∈ Con𝔄.

Proof. We will apply Lemma 4.8. with 𝔛 = 𝔄, t = Df_{n}^{⊥−}, t′ = DL, Q = ϑ_{0} ∪ … ∪ ϑ_{n−1} case. Of course, ⟦Q⟧ ⊇ ϑ′. To see the other direction, we will prove by induction that for m ⩾ 0 γ_{m} ⊆ ϑ′.

We know this for m = 1. Assume that the statement holds for all m − 1 – we need the statement for m.

By our assumption γ_{m−1} ⊆ ϑ′ ⊆ ϑ; since ϑ is a congruence of the complete type, Op_{c_{0}^{⊥},... ,c_{n−1}^{⊥}}(γ_{m−1}) ⊆ ϑ as well. On the other hand, Op_{c_{0}^{⊥},... ,c_{n−1}^{⊥}}(γ_{m−1}) ⊆ (𝔄_{0})^{2} ∪ … ∪ (𝔄_{n−1})^{2}, so Op_{c_{0}^{⊥},... ,c_{n−1}^{⊥}}(γ_{m−1}) ⊆ ϑ_{0} ∪ … ∪ ϑ_{n−1}.

Thus γ_{m} = γ_{m−1} ∨ ⟦Op_{c_{0}^{⊥},... ,c_{n−1}^{⊥}}(γ_{m−1})⟧_{DL} ⊆ γ_{m−1} ∨ ⟦ϑ_{0} ∪ … ∪ ϑ_{n−1}⟧_{DL} = ϑ′. _{■}

]

We apply the lemma in the 𝔛 = 𝔄, t = Df_{2}^{−}, t′ = DL cases, and in the R = {⟨x_{0}, y_{0}⟩}, R = {⟨x_{1}, y_{1}⟩} cases; because of the two R-s, we will denote the corresponding relations with γ_{00}, …, γ_{0n}, …, and with γ_{10}, …, γ_{1n}, …, respectively.

In 𝔄^{11} for k = 0, 1 e_{k} = γ_{k1}, in 𝔄^{20} e_{0} = γ_{02} and e_{1} = γ_{10}. We advise the reader to search the dead sets of the γ_{kn}-s in 𝔄^{11} and 𝔄^{20}.

Definition 4.10. A k-hook is a pair π = ⟨p, q⟩ such that 𝔄_{k} ∋ p ⊂ q ∈ 𝔄. p is called the stem of the hook (sπ), q ∖ p is the head of the hook (hπ), and q is the body of the hook (bπ). (We may use this terminology for any ⟨p, q⟩ ∈ 𝔄^{2}.) In a natural way, if π is a pair in 𝔄, and x ⊆ U, and ∗ is a binary Boolean operation, by x ∗ π we mean the pair ⟨x ∗ sπ, x ∗ bπ⟩, and by c_{k} π we mean ⟨c_{k} sπ, c_{k} bπ⟩, and so on.

A congruence is k-generated, if it can be generated by a relation on 𝔄_{k}. _{□}

The importance of hooks is the following: k-generated Df_{2}^{−}-congruences can be DLgenerated by cylinders of some hooks.

For example, in 𝔄^{20} c_{0} ⟨y_{0}, U⟩ , c_{1} ⟨C_{0}, C_{0} ∪ {u_{12}}⟩ , c_{0} ⟨R_{0}, R_{0} ∪ {u_{11}}⟩ DL-generate e_{0}.

Consider the following situation in 𝔄^{20}: let p = {u_{00}, u_{10}, u_{11}}, π = ⟨C_{0}, C_{0} ∪ C_{1}⟩, R = R_{1}. π is an 1-hook with 1-closed body. The reader may observe that R ∩ p ∩ sπ = ∅ ≠ R∩p∩bπ. This configuration is useful when we compute e_{0}, because with the help of it we can see immediately that R ⊆ D(e_{0}) (provided we know π ∈ e_{0}): ⟨p ∩ sπ, p ∩ bπ⟩ ∈ π^{∗}, so ⟨c_{0}(p ∩ sπ), c_{0}(p ∩ bπ)⟩ ∈ e_{0}, and then R ⊆ c_{0}(p ∩ sπ) ⊕ c_{0}(p ∩ bπ) ⊆ D(e_{0}).

The following lemma – in fact, the engine of the present axiomatization – claims the existence of such a configuration in a quite general situation.

Lemma 4.11. Let π_{1}, …, π_{r} be 1-hooks such that π_{i} = c_{1} π_{i}, let g = ⟦π_{1}, …, π_{r}⟧_{DL}, and for some row R, p ∈ 𝔄 let D(g) ⊇ R ∩ p ≠ ∅.

Then for some 1 ⩽ i_{0} ⩽ r and for a q ∈ 𝔄_{1} π = π_{i_{0}} ∩q has the following two properties: R ∩ p ∩ sπ = ∅ ≠ R ∩ p ∩ bπ, and π is a hook.

(The statement is also valid with 0-hooks, with a column instead of a row, and with q ∈ 𝔄_{0}.)

Proof. ∅ ≠ R ∩ p ∩ D(g) = ⋃_{1⩽i⩽r} (R ∩ p ∩ hπ_{i}), so for some i_{0} R ∩ p ∩ hπ_{i_{0}} ≠ ∅; for such an i_{0} let ν_{1} = π_{i_{0}}. We will sketch an algorithm, which stops after finitely many steps and produces us the desired π.

For 1 ⩽ i ⩽ r let φ_{i} be the following function (defined on pairs from 𝔄) : φ_{i}(η) = R ∩ p ∩ hπ_{i} ∩ sη. In the following the quantifiers will be over the i-s from 1 to r. And then the algorithm:

• let m = 1;

• until ∀i φ_{i}(ν_{m}) = ∅ do: pick an i_{m} for which φ_{i_{m}}(ν_{m}) ≠ ∅, let ν_{m+1} = π_{i_{m}} ∩ sν_{m}, and let m = m + 1;

• return π = ν_{m} and stop.

First we prove that the algorithm stops after finitely many steps.

Let us call π_{i_{m}} the m-th witness – then a π_{i} can act as a witness only once: sν_{m+1} ⊆ sπ_{i_{m}}, so ∅ = sν_{m+1} ∩ hπ_{i_{m}} ⊇ φ_{i_{m}}(ν_{m+1}), which means that π_{i_{m}} is not a witness for m + 1; and since for m′ > m + 1 sν_{m+1} ⊇ sν_{m′}, ∅ = φ_{i_{m}}(ν_{m+1}) ⊇ φ_{i_{m}}(ν_{m′}) – so π_{i_{m}} can never be a witness after the m-th step. And we have only finitely many π_{i}-s – so the number of steps is bounded by the number of π_{i}-s.

It is trivial that all ν_{m}-s are in g: ν_{1} is one of the π_{i}-s, so it is in g, and the other ν_{m}-s are gained by intersection from a π_{i} ∈ g and an element of 𝔄, and such elements are also in g. Let q be the number of the step, where the algorithm stops, that is, ∀i φ_{i}(ν_{q}) = ∅. Of course, ⟨v, w⟩ = ν_{q} ∩ u ∈ g.

Let t be last value of m, that is, π = ν_{t}. An induction to m shows us that π = π_{i_{0}} ∩ ⋂_{j=1}^{t} sπ_{i_{j}}, so q = ⋂_{j=1}^{q} sπ_{i_{j}} is a good choice.

What is remained to see is R ∩ p ∩ sπ = ∅ ≠ R ∩ p ∩ bπ.

R∩p∩sπ = R∩p∩D(g)∩sν_{t} = ⋃_{1⩽i⩽r} (R ∩ p ∩ hπ_{i} ∩ sν_{t}) = φ_{1}(ν_{t})∪…∪φ_{r}(ν_{t}) = ∅. If t = 1, then R ∩ p ∩ bπ = R ∩ p ∩ bν_{1} ⊇ R ∩ p ∩ hν_{1} ≠ ∅, by the choice of ν_{1}. If t ⩾ 2, then R ∩ p ∩ bπ = R ∩ p ∩ bν_{t} = R ∩ p ∩ bπ_{i_{t−1}} ∩ sν_{t−1} ⊇ φ_{i_{t−1}}(ν_{t−1}) ≠ ∅. So

the algorithm works.

Of course, the statement stays valid if we interchange 0 and 1. _{■}

Definition 4.12. The pathologic case, that a hook is simultaneously a 0-hook and a 1-hook, that is, its stem is in the spine of the algebra, may occur; though usually such hooks are not interesting (they can be relevant only in non-consonant algebras). So we will suppose that the hooks are indexed with 0 or 1 according to that what kind of hooks they may and expected to be; thus the following notation is well-defined: if π is a k-hook, then let c π = c_{k} π (and c π will also be a k-hook).

We will say π′ is linked to π, if they are hooks with different indices (i.e., π is a 0-hook and π′ is a 1-hook or vica versa), and hπ′ ⊆ h c π. The transitive and reflexive closure of the relation “is linked to” will be called accessibility: if π is a hook, then π is accessible from π in 0 steps; and if π′ is accessible from π in n − 1 steps, and π′′ is linked to π′, then π′′ is accessible from π in n steps, or for short, n-accessible. π′ is accessible from π, if it is n-accessible from π for some n. We will also speak of the notion of (⩽n)-accessibility, and (<n)-accessibility, as it stands for reason.

We introduce the following DL-conruences: for k = 0, 1, ℓ ⩾ 0 let

Γ_{kℓ} = ⟦c π | π is (⩽ℓ)-accessible from ⟨y_{k}, x_{k}⟩⟧_{DL}
□

For example, in 𝔄^{20} ⟨C_{0}, C_{0} ∪ {u_{12}}⟩ and ⟨R_{0}, R_{0} ∪ {u_{11}}⟩ are accessible from ⟨y_{0}, U⟩ in one and two steps, respectively.

We advise the reader to follow the reasoning in the following lemma with 𝔄 = 𝔄^{20}, p = {u_{00}, u_{10}, u_{11}}, F = R_{1}, t = 1, η_{1} = ⟨C_{0}, C_{0} ∪ {u_{12}}⟩, ℓ = 2. (This case the ν given in the proof will be ⟨R_{0}, R_{0} ∪ {u_{11}}⟩.)

Lemma 4.13. Let F be a fibre (a column or a row), p ∈ 𝔄, and k < 2, ℓ, t ⩾ 1.

If ∅ ≠ F ∩ p ⊆ D(c η_{1}, …, c η_{t}), where the η_{i}-s are hooks being (<ℓ)-accessible from ⟨y_{k}, x_{k}⟩, then F ⊆ D(Γ_{kℓ}).

Proof. Of course, we prove by induction (the statement trivially holds for ℓ = 0) and we will discuss the step from ℓ = 2n − 1 to 2n, if k = 0 (then the proof for the other cases consist of manipulating the indices). Accessibility will mean accessibility from ⟨y_{0}, x_{0}⟩.

Now let F be a column C. If for some i η_{i} is an m-accessible 1-hook (m < 2n), and C ∩ p intersects h c_{1} η_{i}, then C ⊆ h c_{1} η_{i} ⊆ D(Γ_{0,2n}), so this case we are ready.

Since D(c η_{1}, …, c η_{t}) = h c η_{1} ∪ … ∪ h c η_{t}, assuming the contrary we get C ∩ p ⊆ h c_{0} η′_{1} ∪ … ∪ h c_{0} η′_{r}, where η′_{1}, …, η′_{r} are the 0-hooks from {η_{1}, …, η_{t}}. By definition of m-accessibility, if a 0-hook is m-accessible from another 0-hook (this case from ⟨y_{0}, x_{0}⟩), then m must be even, hence all the η′_{i}-s are (< 2n − 1)-accessible. So by the induction hypothesis C ⊆ D(Γ_{0,2n−1}) ⊆ D(Γ_{0,2n}); we are ready again.

Now let F be a row R. Just like above, the case when R ∩ p intersects a 0-hook from the η_{i}-s, is a trivial one; so remains the only interesting case:

Assume C∩p ⊆ h c_{0} η′_{1}∪…∪h c_{0} η′_{r}, where η′_{1}, …, η′_{r} are the 1-hooks from {η_{1}, …, η_{t}}. First consider that (†) if π is an m-accessible k-hook, q ∈ 𝔄_{k}, and π ∩ q is a hook (i.e.

its head is not empty), then π ∩ q is also m-accessible: the m − 1-accessible hook π′ for which hπ ⊆ h c π′, also satisfies h(π ∩ q) ⊆ h c π′.

Then we apply Lemma 4.11. with π_{i} = c_{1} η′_{i} (i = 1, …, r), thus we get a 1-hook π = π_{i_{0}} ∩ q, q ∈ 𝔄_{1} such that R ∩ p ∩ sπ = ∅ ≠ R ∩ p ∩ bπ. Say, η′_{i_{0}} is m-accessible, where m < 2n. By applying the equation of Bcy concerning intersections, introducing π′ = η′_{i_{0}} ∩ q, we get π = c_{1} π′. Of course, π′ is a 1-hook, so by (†), π′ is also m-accessible.

Let ν = ⟨c_{0}(p ∩ sπ), c_{0}(p ∩ sπ) ∪ (p ∩ bπ)⟩. hν = p ∩ bπ ∖ c_{0}(p ∩ sπ) ⊆ bπ; and sπ ∩ hν = sπ ∩ p ∩ bπ ∖ c_{0}(p ∩ sπ) = ∅. So hν ⊆ bπ ∖ sπ = hπ = h c_{1} π′, which means that ν is (m + 1)-accessible iff it is hook, that is, iff hν ≠ ∅.

By the choice of π, R∩p∩bπ ≠ ∅, so R∩bν ≠ ∅. On the other hand, R∩p∩sπ = ∅, so R ∩ c_{0}(p ∩ sπ) = ∅, that is, R ∩ sν = ∅. It means R ∩ hν ≠ ∅.

This has two immediate consequences: ν is a hook, so it is (m + 1)-accessible; and R ⊆ h c_{0} ν. Since m + 1 ⩽ 2n, this means R ⊆ h c_{0} ν ⊆ D(Γ_{0,2n}).

This is what we wanted. _{■} Corollary 4.14. For k = 0, 1

e_{k} = ⟦c π | π is accessible from ⟨y_{k}, x_{k}⟩⟧_{DL}

Proof. With a trivial induction reasoning we may see that if π is ℓ-accessible from ⟨y_{k}, x_{k}⟩, then c π ∈ e_{k}: let π be linked to the (ℓ − 1)-accessible π′, and assume c π′ ∈ e_{k}; then hπ ⊆ h c π′ ⊆ D(e_{k}), so π ∈ e_{k}, and then, since e_{k} is a Df_{2}^{−}-congruence, c π ∈ e_{k} as well.

To see the “⊆” direction, we will show that for ℓ ⩾ 0 γ_{kℓ} ⩽ Γ_{kℓ}.

We prove by induction. Assuming that γ_{k,ℓ−1} ⩽ Γ_{k,ℓ−1}, we can see γ_{kℓ} ⩽ Γ_{kℓ} if we show that Op_{c_{0},c_{1}}(γ_{k,ℓ−1}) ⊆ Γ_{kℓ}.

Let ⟨p, q⟩ ∈ γ_{k,ℓ−1}; we have to show that for k = 0, 1 ⟨c_{k} p, c_{k} q⟩ ∈ Γ_{kℓ}, that is, D(Γ_{kℓ}) ⊇ c_{k} p ⊕ c_{k} q. We will show it fibre-by-fibre. So let F ⊆ c_{k} p ⊕ c_{k} q be a kfibre. By the induction hypothesis ⟨p, q⟩ ∈ Γ_{k,ℓ−1}; then for some t ⩾ 1 we can take the (<ℓ)-accessible hooks η_{1}, …, η_{t} such that ⟨p, q⟩ ∈ ⟦η_{1}, …, η_{t}⟧_{DL}.

F intesects exactly one of p, q; say this one is p. Then ∅ ≠ F ∩ p ⊆ p ⊕ q ⊆ D(η_{1}, …, η_{r}), so by Lemma 4.13. D(Γ_{kℓ}) ⊇ F. _{■}

Definition 4.15. If π⃗ is a sequence of hooks (the indexing goes from 0 to r, which may be non-negative integer or infinity), then we will say that π⃗ is a k-chain of hooks, or for short, k-chain (k = 0, 1), if π_{0} is a k-hook, and π_{n+1} is linked to π_{n}. If π is a hook, fπ = h c π will be called the flag of π. If π⃗ is a k-chain of hooks, the flag of this chain is fπ⃗ = ⋃_{n=0}^{r} fπ_{n}. If χ = ⟨χ_{0}, χ_{1}⟩ = ⟨⟨y_{k}, x_{k}⟩⟩_{k=0,1} is a hole-configuration, and π⃗ is a k-chain of hooks, we will say that π⃗ is a k-chain starting from the hole-configuration χ, if π_{0} = ⟨y_{k}, x_{k}⟩. If π⃗ and π′ are chains, n, m ⩾ 0 and fπ_{n} ∩fπ′_{m} ≠ ∅, then we will say π⃗ and π′ meets at n, m. If χ is a hole-configuration and u ∈ U, we will say that u is accessible from χ in horizontal direction, or accessible from χ_{0}, if exists a 0-chain π⃗ starting from χ such that u ∈ fπ⃗; we define analogously accessibility in vertical direction (accessibility from χ_{1}). _{□}

Up to this point we worked with a fix hole-configuration ⟨⟨y_{k}, x_{k}⟩⟩_{k=0,1}, but we did not name it. From now on we will call our hole-configuration χ. For the sake of simplicity, we will say “the hole χ” instead of “the hole-configuration χ”.

For example, in 𝔄^{20} ⟨y_{0}, U⟩ , ⟨C_{0}, C_{0} ∪ {u_{12}}⟩ , ⟨R_{0}, R_{0} ∪ {u_{11}}⟩ form a 0-chain starting from the hole configuration of the algebra.

The following corollary is meant to be the corollary of Corollary 4.14.

Corollary 4.16. If u ∈ U, then u ∈ D(e_{k}) ⟺ u is accessible from χ_{k}.

Proof. (←) Let π⃗ be a k-chain starting from χ such that u ∈ fπ⃗. Since π⃗ consists of hooks being accessible from χ_{k}, fπ⃗ ⊆ D(e_{k}).

(→) Let u ∈ D(e_{k}). By Corollary 4.14. for some ℓ ⩾ 0 u is in the flag of a hook π_{ℓ}, which is ℓ-accessible from χ_{k}. Then we take a hook π_{ℓ−1}, which is (ℓ − 1)-accessible from χ_{k}, and π_{ℓ} is linked to π_{ℓ−1}. And so on. Iterating the procedure we get a k-chain starting from χ. _{■}

Since D(e_{0})∩D(e_{1}) ≠ ∅, by the above corollary we will find a 0-chain π^{0} and a 1-chain π^{1} starting from our hole, which meet somewhere. We are on to describe this situation in first-order language.

Definition 4.17. Let k < 2. Let v⃗ = ⟨v_{0}, v_{1}, …⟩ an infinite sequence of variables. We define recursively the following sequence of terms:

• σv⃗ ; k0 = c_{k} v_{0};

• σv⃗ ; kn = c_{(k+n)_{mod 2}}(σv⃗ ; k,n−1 ∧ v_{n}).

If σ is a term with n variables, and p⃗ is a sequence in 𝔄 with lenght at least n, then by σ(p⃗) we mean that element of 𝔄 which is gained by substituting the first n member of π⃗ into σ (we suppose the variables in σ are ordered). If π⃗ is a sequence of hooks, then by sπ⃗, bπ⃗, b c π⃗ we mean the sequence of the stems/bodies/bodies of cylinders of the members of π⃗.

With a slight abuse of language, in the following lemma x_{0}, x_{1}, y_{0}, y_{1} will be variables and not the members of our hole-configuration in our non-representable algebra. _{□}

Lemma 4.18. Let v⃗ = ⟨v_{0}, v_{1}, …⟩ and w⃗ = ⟨w_{0}, w_{1}, …⟩ two infinite sequences of variables. Then for n, m ⩾ 0

RDf_{2}^{−} ⊧ c_{0} x_{0} ∧c_{1} x_{1} ⩽ c_{0} y_{0} ∨c_{1} y_{1} ⇒ σv⃗ ; 0n(v_{0}/x_{0})∧σw⃗ ; 1m(w_{0}/x_{1}) ⩽ σv⃗ ; 0n(v_{0}/y_{0})∨σw⃗ ; 1m(w_{0}/y_{1}) .

Proof. It is enough prove the validity of this quasi-equation in unholed algebras. Let 𝔄 be unholed and x_{k}, y_{k} ∈ 𝔄_{k} (k = 0, 1) (we may suppose the chosen x_{k}, y_{k} are k-closed, since in the formula these occur only under a k-closure). By (∗) (in Theorem 3.6.) if for the x_{k}-s, y_{k}-s the premise of our quasi-equation holds, then for some k < 2 x_{k} ⩽ y_{k}; we may suppose x_{0} ⩽ y_{0}. Then by a trivial induction according to the construction of the terms σv⃗ ; 0ℓ, we get that σv⃗ ; 0n(v_{0}/x_{0}) ⩽ σv⃗ ; 0n(v_{0}/y_{0}) (independently of the choice of the v_{ℓ}-s for ℓ > 0), from which trivially follows the statement. _{■}

Lemma 4.19. If π^{0}, π^{1} are a 0-chain and an 1-chain in 𝔄, starting from the hole ⟨⟨y_{k}, x_{k}⟩⟩_{k=0,1}, and they meet at n, m, then

𝔄 |̸= c_{0} x_{0} ∩ c_{1} x_{1} ⊆ c_{0} y_{0} ∪ c_{1} y_{1} ⇒ σv⃗ ; 0n(b c π^{0}) ∩ σw⃗ ; 1m(b c π^{1}) ⊆ σv⃗ ; 0n(sπ^{0}) ∪ σw⃗ ; 1m(sπ^{1})

Proof. The premise of the quasi-equation is fulfilled, since x_{k}-s, y_{k}-s form a hole configuration. Thus we have to see the conclusion is not fulfilled.

By induction we can prove that for each ℓ ⩽ n the σv⃗ ; kℓ(b c π^{k}) ⊇ fπ_{ℓ}^{k}, and σv⃗ ; kℓ(sπ^{k}) ⊆ sπ_{ℓ}^{k}. The details of this are left to the reader. So the falsehood of the conclusion follows from the falsehood of fπ_{n}^{0} ∩ fπ_{m}^{1} ⊆ sπ_{n}^{0} ∪ sπ_{m}^{1}. This latter formula is equivalent with (fπ_{n}^{0} ∖ sπ_{n}^{0}) ∩ (fπ_{m}^{1} ∖ sπ_{m}^{1}) = ∅. Since the flag and the stem of a hook are disjoint, the left side is same as fπ_{n}^{0} ∩ fπ_{m}^{1}; and the intersection of these is not empty, since the two chains meet at n, m. Hence the conclusion of the quasi-equation is false in 𝔄. _{■}

Thus we proved that the formulas given in Lemma 4.18. (and Bcy) axiomatize RDf_{2}^{−}: they are valid in RDf_{2}^{−}, and taking 𝔄, the general non-representable model of Bcy, we find one of these formulas false in 𝔄. However, this is an infinite axiomatization; a finite part of this will be suitable as well, because of the following lemma:

Lemma 4.20. (Finitization Lemma) If π^{0} is a 0-chain and π^{1} is a 1-chain starting from the hole χ, and they meet somewhere, then we can find an another hole χ′, and a 0-chain ν^{0}, a 1-chain ν^{1} starting from the hole χ′ such that they meet at n_{0}, n_{1} where n_{0} + n_{1} = 2.

Proof. The reader may easily see that a 0- and a 1-chain starting from a hole cannot meet at 0, 0; 0, 1, or 1, 0 (if x_{0}∩x_{1} ⊆ y_{0}∪y_{1} with some k-closed x_{k}, y_{k}, then (x_{0}∖y_{0})∩(x_{1}∖y_{1}) = (x_{0} ∖ y_{0}) ∩ c_{0}(x_{1} ∖ y_{1}) = c_{1}(x_{0} ∖ y_{0}) ∩ (x_{1} ∖ y_{1}) = ∅). So n_{0} + n_{1} cannot be smaller than two.

Let π^{0} and π^{1} be 0-and 1-chains starting from χ = ⟨⟨y_{k}, x_{k}⟩⟩_{k=0,1}, meeting at m_{0}, m_{1}, where m_{0} + m_{1} ⩾ 3. We will show that this case we can find an another hole χ′, and a 0-chain ν^{0}, 1-chain ν^{1} which meet at n_{0}, n_{1} and which start from the hole χ′ and n_{0} + n_{1} < m_{0} + m_{1} (and then iterating the procedure at last we find the promised n_{0}, n_{1}). One of the m_{k}-s is at least two, we may suppose m_{0} ⩾ 2.

If fπ_{2}^{0}∩fπ_{0}^{1} ≠ ∅, then we found a meeting at 2,0. Then we are ready. If fπ_{2}^{0}∩fπ_{0}^{1} = ∅, then we claim that χ′ = ⟨⟨sπ_{2}^{0}, b c_{0} π_{2}^{0}⟩ , ⟨y_{1}, x_{1}⟩⟩ is a hole configuration: since π_{2}^{0} is a 0hook, sπ_{2}^{0}, b c_{0} π_{2}^{0} ∈ 𝔄_{0} and sπ_{2}^{0} ⊂ b c_{0} π_{2}^{0}; besides we have to see b c_{0} π_{2}^{0} ∩x_{1} ⊆ sπ_{2}^{0} ∪y_{1}; this is equivalent with (b c_{0} π_{2}^{0} ∖ sπ_{2}^{0}) ∩ (x_{1} ∖ y_{1}) = ∅; here the first intersection factor is fπ_{2}^{0}, and the second is fπ_{0}^{1}, hence this latter equation holds, and χ′ is a hole configuration. Since the 1-closed pair in χ′ is the same as in χ, we may let ν^{1} = π^{1} – this is a 1-chain starting from χ′. And let ν_{ℓ}^{0} = π_{ℓ+2}^{0}; – thus we get a 0-chain starting from χ′. Since m_{0} ⩾ 2, π_{m_{0}}^{0} is also a member of ν^{0} (namely, ν_{m_{0}−2}^{0}), so ν^{0} and ν^{1} will meet at m_{0} − 2, m_{1};

— the sum of these two numbers is definitely smaller than m_{0} + m_{1}. _{■}

So in a non-representable algebra we will find a 0-chain and a 1-chain starting from some hole, and meeting at 1, 1; 0, 2, or 2, 0. The latter two cases are not essentially different. 𝔄^{11} is an example of the 1, 1-case and 𝔄^{20} is an example of the 2, 0-case.

Now we have the finite quasi-equational axiomatization for RDf_{2}^{−}:

Theorem 4.21. (Axiomatization of RDf_{2}^{−}) The following quasi-equations axiomatize RDf_{2}^{−}: the basic cylindric equations (Bcy),

c_{0} x_{0} ∧ c_{1} x_{1} ⩽ c_{0} y_{0} ∨ c_{1} y_{1} ⇒ c_{0}(c_{1} x_{1} ∧ v) ∧ c_{1}(c_{0} x_{0} ∧ w) ⩽ c_{0}(c_{1} y_{1} ∧ v) ∨ c_{1}(c_{0} y_{0} ∧ w),

c_{0} x_{0} ∧ c_{1} x_{1} ⩽ c_{0} y_{0} ∨ c_{1} y_{1} ⇒ c_{0}(c_{1}(c_{0} x_{0} ∧ v) ∧ v′) ∧ c_{1} x_{1} ⩽ c_{0}(c_{1}(c_{0} y_{0} ∧ v) ∧ v′) ∨ c_{1} y_{1},

and the formula we get interchanging 0 and 1 in the second one.

Proof. We sum up the arguments wich led us to this axiomatization.

By Lemmas 2.7. and 4.18. these formulas are valid in RDf_{2}^{−}.

On the other hand, if a non-representable algebra 𝔄 models Bcy, then by Lemma 1.9., Theorem 3.3., Remark 3.5. and Theorem 3.26. we can find a hole-configuration χ such that its elimination alternative ⟨e_{0}, e_{1}⟩ is not a subdirect decomposition, that is, e_{0} ∧ e_{1} ≠ 0. Then using Theorem 3.3. and Subsection 4.1., we can take a nice representation, where we will find D(e_{0}) ∩ D(e_{1}) ≠ ∅. Taking u ∈ D(e_{0}) ∩ D(e_{1}), by Corollary 4.16. u is accessible from χ with a 0-chain of hooks and with a 1-chain of hooks as well. So these two chains meet. Then by Lemma 4.20. we can also find a hole with 0,1-chains starting from it such that these chains meet at n_{0}, n_{1}, where n_{0} +n_{1} = 2. With the help of Lemma 4.18. we can describe this situation in first-order language, as the falling of certain quasi-equations; these quasi-equations are given in the present theorem. _{■}

References

[Andréka] H. Andréka: Complexity of equations valid in algebras of relations; Part I.: strong non-finitizability, Annals of Pure and Applied Logic 89 (1997) 149-209.

[AN] H. Andréka, I. Németi: Representable positive cylindric algebras do not form a variety. Preprint, Matemathical Institute, Hungarian Academy of Sciences, 1991.

[ANS a] H. Andréka, I. Németi, I. Sain: Algebraic Logic, in.: Handbook of Philosophical Logic, to appear.

[ANS b] H. Andréka, I. Németi, I. Sain: Universal Algebraic Basics for Algebraic Logic (preliminary draft version). Manuscript.

[BS] S. Burris, H.P. Sankappanavar: A course in universal algebra, GTM, Springer-Verlag, New York, 1981;

[CK] C.C. Chang, H.J. Keisler: Model Theory, North-Holland, 1990.

[Comer] S.D. Comer: A remark on representable positive cylindric algebras, Algebra Universalis 28 (1991) 150-151.

[Cosmadakis] S.S. Cosmadakis: Database theory and cylindric lattices, in.: A.K. Chandra (Ed.), Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 411-420, Los Angeles, CA. IEEE Computer Society Press, 1987.

[Düntsch] I. Düntsch: A note on cylindric lattices, in.: Algebraic methods in logic and in computer science, 231–238, Warsaw, 1991.

[DM] I. Düntsch, Sz. Mikulás: Cylindric structures and dependencies in relational databases. Preprint.

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

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

[Johnson] J.S. Johnson: Nonfinitizability of classes of representable poliadic algebras, J. Symbol. Logic 34 (1969) 344-352.

[Jónsson] B. Jónsson: The theory of binary relations, in.: Algebraic Logic, Colloq. Math. Soc. Janos Bolyai, vol. 54, North-Holland, Amsterdam, 1991, pp. 245-292.

[JT] B. Jónsson, A. Tarski: Boolean algebras with operators I.-II., Amer J. Math. vol. 73, 74 (1951, 1952), 891-939, 127-162.