A FINITE AXIOMATIZATION OF LOCALLY SQUARE CYLINDRIC-RELATIVIZED SET ALGEBRAS^{1} Preliminary draft version.

H. Andréka September, 1995.

Abstract. We give a finite set of equations defining the class G_{n} of locally square cylindricrelativized set algebras (of dimension n) if n is finite. For infinite n, we give an axiomatization of the equational theory of G_{n}. Here G_{n} denotes the class of all cylindric-relativized set algebras of dimension n with unit a union of Cartesian spaces.

Let n be an ordinal. We will deal with algebras of n-ary relations. A cylindric-relativized set algebra of dimension n is an algebra of n-ary relations, we do not recall its definition here. Crs_{n} denotes the class of all cylindric-relativized set algebras of dimension n, and Gs_{n} ⊆ G_{n} ⊆ D_{n} ⊆ Crs_{n} are subclasses of Crs_{n} defined by making restrictions on the biggest element (unit) of the algebra, we briefly recall their definitions below.

Let 𝔄 be a cylindric-relativized set algebra of dimension n with unit V. Then 𝔄 ∈ D_{n} iff for every s ∈ V and every finite nonpermutational transformation τ of n, also s ∘ τ is in V. 𝔄 ∈ G_{n} iff V is a union of Cartesian spaces. 𝔄 ∈ Gs_{n} iff V is a disjoint union of Cartesian spaces.

For a class K of algebras, IK denotes the class of all isomorhic copies of elements of K.

Let n be finite. In this paper we give a finite equational axiom system for G_{n}. It was already known that IG_{n} is a variety (Németi [N86]), moreover it is a canonical variety, i.e. it is closed under perfect extensions (Andréka-Goldblatt-Németi [AGN]). These will also follow from the theorem in the present paper because the axiomatization we give contains only positive equations. If n is infinite, then we do not know weather IG_{n} is a variety or not. More on IG_{n} can be found in [AGN, MV, N86, N95, N96].

We note that ICrs_{n}, ID_{n}, IGs_{n} are all varieties, ICrs_{n} and IGs_{n} are not finitely axiomatizable for n ≥ 3, and a finite axiomatization for ID_{n} is given in [AT]. These are all distinct classes, equations distinguishing them are given in [N86, N95]. A rich material on these classes can be found besides the above cited references e.g. in [HMTAN, HMTII, M95,N85].

Let n be a finite number and let i, j < n. Let Ax_{ij} be the following equation:

x ≤ c_{i}c_{j}(s_{j}^{i}c_{j}x · s_{i}^{j}c_{i}x · ∏_{k<n,k≠i,j} s_{i}^{k}s_{j}^{i}s_{k}^{j}c_{k}x).

In the above, ∏ is the grouped version of ·, and s_{j}^{i}(x) = c_{i}(d_{ij} · x) if i ≠ j and s_{i}^{i}(x) = x. We will see from the proof of the next theorem that Ax_{ij} intuitively says that for any sequence in the unit, we can also put into the unit the sequence we obtain from it by interchanging its i’th and j’th elements. From the equation Ax_{ij} we will only use its following consequence:

1This work has been supported by the Hungarian National Foundation for Scientific Research Grants No T16448, T7255.

x ≠ 0 → s_{j}^{i}c_{j}x · s_{i}^{j}c_{i}x · ∏_{k<n,k≠i,j} s_{i}^{k}s_{j}^{i}s_{k}^{j}c_{k}x ≠ 0.

Intuitively, this ensures that if a sequence is in x, then its permuted version can be put into s_{j}^{i}c_{i}x · . . ..

To extend these equations for infinite n, assume now that n is any ordinal, possibly infinite. For all i, j < n and all finite subsets Γ of n let Ax_{ijΓ} denote the following equation:

x ≤ c_{i}c_{j}(s_{j}^{i}c_{j}x · s_{i}^{j}c_{i}x · ∏_{k∈Γ,k≠i,j} s_{i}^{k}s_{j}^{i}s_{k}^{j}c_{k}x).

Let Ax_{n} be the set of all Ax_{ij}, for i, j < n, and let Ax′_{n} = {Ax_{ijΓ} : i, j < n, Γ ⊆ n, Γ finite }. We will simply write Ax and Ax′ if there is no danger of confusion. IG_{n}, HG_{n} denote the classes of all isomorphic copies and all homomorphic images of elements of G_{n}, respectively.

THEOREM.

(i) IG_{n} = {𝔄 ∈ ID_{n} : 𝔄 ⊧ Ax}, if n is finite, n ≥ 3.

(ii) HG_{n} = {𝔄 ∈ ID_{n} : 𝔄 ⊧ Ax′} for all n ≥ 3.

(iii) IG_{2} = {𝔄 ∈ ID_{n} : 𝔄 ⊧ x − d_{01} ≤ c_{0}c_{1}(−d_{01} · s_{1}^{0}c_{1}x · s_{0}^{1}c_{0}x)}.

Proof: Let n ≥ 2.

First we show that G_{n} ⊧ Ax′. Let 𝔄 ∈ G_{n} with unit V, x ∈ A and let s ∈ x. Let i, j, k < n. Let z = s ∘ [i, j], where [i, j] : n → n is the permutation of the set n = {k : k < n} which interchanges i and j and leaves all the other elements fixed. Then z ∈ V and it is easy to check that s ∈ c_{i}c_{j}({z}), z ∈ s_{j}^{i}c_{j}x, z ∈ s_{i}^{j}c_{i}x, z ∈ s_{i}^{k}s_{j}^{i}s_{k}^{j}c_{k}x. This shows that 𝔄 ⊧ Ax_{ijΓ} for all i, j < n and for all finite Γ ⊆ n. This shows G_{n} ⊧ Ax′. The same argument shows that G_{2} satisfies the indicated equation (notice that if s ∈ x − d_{01}, then s_{0} ≠ s_{1}, and so z also is in −d_{01}).

To show the other direction of (i)-(iii), we first assume that n is finite n ≥ 2. Let 𝔄 ∈ D_{n} with unit V, and assume that 𝔄 ⊧ Ax.

By the proof of the representation theorem in [AT], we may assume that V satisfies the following

(*) For all repetition-free sequences s, z ∈ V, the ranges of s and z are different. This means, in other words, that if s ∈ V, then no other permuted version of s is in V. We note that for any D_{n}-unit V it is true that (**) If s ∈ V is not repetition-free and i, j ∈ n, then s ∘ [i, j] ∈ V. This means, in other words, that if s ∈ V has a repetition (i.e. is not repetition-free), then all permuted versions of s are in V. Using that V is a D_{n}-unit, this also means that s ∘ τ ∈ V for all τ : n → n, or still in other words, ^{n}Rgn(s) ⊆ n (if s ∈ V has repetitions).

The idea of the following proof is that we can “throw in” the permuted versions of the repetition-free sequences in V such that “𝔄 will not change”. Ax_{ij} will tell us “where to put the new sequence s ∘ [i, j]”.

Assume that 𝔄 ∈ D_{n} has unit V such that the following holds: (***) For all repetition-free sequences s ∈ V, either s ∘ τ ∈ V for all bijections τ : n → n or

else s ∘ τ ∉ V for all bijections τ : n → n which are not the identity on n.

Of course, (*) implies (***).

Let s ∈ V be a repetition-free sequence such that “no permuted version of s is in V ”. Let S = {z_{0}, z_{1}, …, z_{N}} be a listing of all the permuted versions of s—i.e. S = {s ∘ τ : τ is a bijection of n}— such that

z_{0} = s

z_{i} = z_{j} ∘ [k, ℓ] for some j < i, k, ℓ < n.
z_{i} ≠ z_{j} if i ≠ j.

Such a listing is possible. Then V ∪ S also satisfies (***). We will “represent” 𝔄 on V ∪ S, i.e. we will show that 𝔄 is isomorphic to an 𝔄′ with unit V ∪ S. Then we will be done by an induction.

We may assume that 𝔄 is atomic and every repetition-free sequence in the unit of 𝔄 is in an atom, because of the following. All the axioms listed here are positive in the wider sense (i.e. complementation − occurs only in front of some constant terms) and the defining axioms of D_{n} are also positive, so we may pass on to the perfect extension and represent that. Also, the representation for D_{n} given in [AT] is such that every sequence in the unit is in some atom (i.e. the unit is the union—and not only the supremum—of the atoms).

We say that an atom of 𝔄 is repetition-free if it is below no d_{ij} (i.e. if it is below ∏_{i<j<n} −d_{ij}). Let a be an arbitrary repetition-free atom of 𝔄 and let i, j < n, i ≠ j.

Let now n ≥ 3 and let

b ≤ s_{j}^{i}c_{j}a · s_{i}^{j}c_{i}a · ∏_{k≠i,j} s_{i}^{k}s_{j}^{i}s_{k}^{j}c_{k}a

be an atom. Such an atom exists by 𝔄 ⊧ Ax. We will show that b is repetition-free.

We will work in the atom-structure of 𝔄 for a while. I.e. let At be the set of all atoms of 𝔄, let E_{ij} = {x ∈ At : x ≤ d_{ij}} and let T_{i} = {⟨x, y⟩ : x, y ∈ At, c_{i}x = c_{i}y}. Let E_{ijk} = E_{ij} ∩ E_{jk}. We will freely use the following properties of atom-structures:

a ∈ E_{ij}, aT_{k}b imply b ∈ E_{ij} if k ≠ i, j.

a, b ∈ E_{ij}, aT_{i}b imply a = b.
E_{ij} ∩ E_{jk} ⊆ E_{ik} = E_{ki}.
For any a ∈ At and i, j < n, i ≠ j there is a unique b ∈ At such that aT_{i}b ∈ E_{ij}.

First we show that b ∈ E_{ij} would imply that a ∈ E_{ij}. Let k < n, k ≠ i, j. Then b ≤ s_{i}^{k}s_{j}^{i}s_{k}^{j}c_{k}a, and this means that there are atoms x, y, z of 𝔄 such that bT_{k}x, x ∈ E_{ik}, xT_{i}y, y ∈ E_{ij}, yT_{j}z, z ∈ E_{jk}, zT_{k}a, see Figure 1.

b  a
|  |
| k  k |
|  |
E_{ik} ∋ x  z ∈ E_{jk}
∖  /
∖i  j/
∖  /
y
E_{ij}

Figure 1

Now, b ∈ E_{ij} implies x ∈ E_{ijk}, which implies that y = x, y ∈ E_{ijk} which imply that z = y, z ∈ E_{ijk}, which imply that a ∈ E_{ij}.

Next we show that b ∈ E_{ik} would imply that a ∈ E_{jk}. By b ≤ s_{i}^{j}c_{i}a there is an atom x such that bT_{j}x ∈ E_{ij}, xT_{i}a, see Figure 2.

b  a
∖  /
∖j  i/
∖  /
x

E_{ij}

Figure 2

Now b ∈ E_{ik} implies x ∈ E_{ijk} which implies that a ∈ E_{jk}. Finally we show that b ∈ E_{kℓ} would imply a ∈ E_{kℓ} for all k ≠ ℓ, j, i ≠ k, ℓ. Let x be an atom as in Figure 2. Then b ∈ E_{kℓ} implies that x ∈ E_{kℓ} which implies that a ∈ E_{kℓ}. Thus b is repetition-free, because a is repetition-free.

Assume now that n ≥ 2 and i, j ≤ n, i ≠ j. For any repetition-free atom a choose a repetition-free atom b below s_{j}^{i}c_{j}a · s_{i}^{j}c_{i}a · ∏_{k≠i,j} s_{i}^{k}s_{j}^{i}s_{k}^{j}c_{k}a and let

f_{ij}(a) = b.

Such a b exists, because if n ≥ 3, then we have seen this above, and if n = 2, then this holds by the axiom we required to hold.

Let now s be the repetition-free sequence we chose at the beginning of this proof, and recall the definition of S = {z_{0}, z_{1}, …, z_{N}}. We will define a sequence a_{0}, a_{1}, …, a_{N} of repetitionfree atoms. Let a be an atom such that s ∈ a. Such an atom exists by our assumption.

Let

a_{0} = a.

Assume that a_{ℓ} has been defined for all ℓ < i. Let ℓ < i and m ≠ j be such that z_{i} = z_{ℓ}∘[m, j]. (If there are several such ℓ, m, j, then we just select one such triple.) Now we define

a_{i} = f_{mj}(a_{ℓ}).

We are ready to define the new representation of 𝔄.: For any x ∈ A define x′ as

x′ = x ∪ {z_{i} : a_{i} ≤ x, i < N}.

(Intuitively, this means that “we put the sequences z_{i} into the atoms a_{i}”.)

Then V′ = V ∪ S, so the unit of the new representation will be V ∪ S as desired. We have to show that the function x ↦ x′ is an embedding of 𝔄 into the full set algebra with unit V ∪ S. Let us denote this function x ↦ x′ by h.

Clearly, h is a one-to-one Boolean embedding, and h(d_{ij}) = d_{ij} for all i, j < n. To show that h respects the cylindrifications c_{k}, first we prove an auxiliary statement.

\underline{Notation:} If z is an n-sequence and k, ℓ < n, then z(k/z_{ℓ}) denotes the sequence which agrees everywhere with z except on k, where it is the same as z_{ℓ}.

LEMMA. Assume that z ∈ S and z ∈ x′, x ∈ At. Let k, ℓ < n, k ≠ ℓ. Then for all b ∈ At we have that

(*) z(k/z_{ℓ}) ∈ b iff xT_{k}b ∈ E_{kℓ}.

Proof: By z ∈ S there is an m ≤ N such that z = z_{m}. We will prove by induction on m.

Assume that m = 0. Then by z_{0} = s ∈ V, (*) is true because 𝔄 is a set algebra on V.

Assume that (*) is true for all k, ℓ < n and for all m < p. We will show that (*) is true for p, too. Let z_{p} = z_{m} ∘ [i, j] be such that m < p and a_{p} = f_{ij}(a_{m}). There are such m, i, j by the definition of a_{p}. Then x = a_{p} by z_{p} ∈ x′, and also z_{m} ∈ a_{m}.

First we prove that xT_{k}b ∈ E_{kℓ} imply that z(k/z_{ℓ}) ∈ b.

\underline{Case 1} k ≠ i, j and ℓ = i or ℓ = j. Assume first that ℓ = j.

By a_{p} = f_{ij}(a_{m}) we have that a_{p} ≤ s_{i}^{k}s_{j}^{i}s_{k}^{j}c_{k}(a_{m}). Since in D_{n} the so called Merry Go Round equation s_{i}^{k}s_{j}^{i}s_{k}^{j}c_{k}x = s_{j}^{k}s_{i}^{j}s_{k}^{i}c_{k}x is true, then we also have that x = a_{p} ≤ s_{j}^{k}s_{i}^{j}s_{k}^{i}c_{k}(a_{m}). Thus there are atoms d, e, b^{+} such that xT_{k}b^{+}, b^{+} ∈ E_{kj}, b^{+}T_{j}e, e ∈ E_{ij}, eT_{i}d, d ∈ E_{ki}, dT_{k}a_{m}. By xT_{k}b ∈ E_{kj} then b^{+} = b (by the basic properties of atomstructures). See Figure 3.

w = z_{m} ∋ a_{m}  x ∈ z_{m} ∘ [i, j] = z_{p} = z
|  |
| k  k |
|  |
E_{ki} ∋ d b ∈ E_{kj}
∖  /
∖i  j/
∖  /

e E_{ij}

Figure 3

Let w = z_{m} and recall that z = z_{p}. Then w(k/w_{i}) ∈ d by our induction hypothesis, and therefore w(k/w_{i})(i/w_{j}) ∈ e because 𝔄 is a set algebra. But then w(k/w_{i})(i/w_{j})(j/w_{i}) ∈ b, again because 𝔄 is a set algebra (notice that w_{i} is the k’th member of the sequence w(k/w_{i})(i/w_{j})). Finally notice that z(k/z_{j}) = w(k/w_{i})(i/w_{j})(j/w_{i}).

The case ℓ = i is completely similar, except that we do not have to use the Merry Go Round equation.

\underline{Case 2} k ≠ i, j and ℓ ≠ i, j.

Then z(k/z_{ℓ}) = z(k/z_{j})(k/z_{ℓ}) and therefore we will use the previous case. Let b^{+} ∈ E_{kj} be such that xT_{k}b^{+}. Such a b^{+} exists by basic properties of atomstructures. Then by Case 1 we have that z(k/z_{j}) ∈ b^{+}, and then z(k/z_{j})(k/z_{ℓ}) ∈ b, because 𝔄 is a set algebra, z(k/z_{j}) ∈ V and b^{+}T_{k}b ∈ E_{kℓ}.

\underline{Case 3} k = i and ℓ = j.

By a_{p} ≤ f_{ij}(a_{m}) we have that a_{m} ≤ s_{j}^{i}c_{i}(a_{p}), see Figure 4.

w ∋ a_{m}  x = a_{p}
∖  /
∖j  i/
∖  /
b
E_{ij}

Figure 4

Now, w ∈ a_{m} implies, by the induction hypothesis, that w(j/w_{i}) ∈ b. But w(j/w_{i}) = z(i/z_{j}).

The case k = i, ℓ ≠ i, j is as above. The case k = j is completely analogous.

Thus we have seen that xT_{k}b ∈ E_{kℓ} imply that z(k/z_{ℓ}) ∈ b. To see the other direction, assume that z(k/z_{ℓ}) ∈ b. There is a b^{+} such that xT_{k}b^{+} ∈ E_{kℓ}, and we have seen that z(k/z_{ℓ}) ∈ b^{+} for this b^{+}. Then b = b^{+} because distinct atoms are disjoint from each other, and so bT_{k}x since b^{+}T_{k}x. QED(Lemma)

Now we are ready to show that h is a homomorphism w.r.t. c_{i}. Let j < n, j ≠ i. We will use that two sequences z and w differ only at i if and only if z(i/z_{j}) = w(i/w_{j}).

To show that h is a homomorphism w.r.t. c_{i} amounts to showing (i)-(ii) below for all atoms a, b and sequences z, w ∈ V ∪ S:

(i) z ∈ a, w ∈ b and z(i/z_{j}) = w(i/w_{j}) imply that aT_{i}b (ii) z ∈ a and aT_{i}b imply that z(i/z_{j}) = w(i/w_{j}) for some w ∈ b. To prove (i)-(ii), let a, b be two atoms, and let aT_{i}a^{+} ∈ E_{ij}, bT_{i}b^{+} ∈ E_{ij}. Then z ∈ a

implies z(i/z_{j}) ∈ a^{+} if z ∈ S by the previous lemma, and if z ∈ V, then this is so since 𝔄 is a set algebra and z(i/z_{j}) ∈ V. Similarly, w ∈ b implies w(i/w_{j}) ∈ b^{+} for all w ∈ V ∪ S.

Proof of (i): Assume z ∈ a, w ∈ b, z(i/z_{j}) = w(i/w_{j}). Then z(i/z_{j}) ∈ a^{+} and w(i/w_{j}) ∈ b^{+} by the above, hence a^{+} = b^{+}, which implies that aT_{i}b by the definition of a^{+}, b^{+}.

Proof of (ii): Assume z ∈ a, aT_{i}b. Then z(i/z_{j}) ∈ a^{+}. Further, aT_{i}b implies that a^{+} = b^{+}. So z(i/z_{j}) ∈ b^{+}. Now since b^{+}T_{i}b, z(i/z_{j}) ∈ V, and since 𝔄 is a set algebra, z(i/z_{j}) ∈ b^{+} implies that w(i/w_{j}) = z(i/z_{j}) for some w ∈ b.

By the above we have see that h is an embedding of 𝔄 into the full set algebra on V ∪ S, i.e. 𝔄 “can be represented on V ∪ S.” Now repeating the above procedure along a transfinite induction we get a representation of 𝔄 on G(V) = {^{n}Rng(s) : s ∈ V }. Since G(V) is a union of Cartesion spaces, this shows that 𝔄 ∈ IG_{n}.

Let n be infinite. Now [N95 , Lemma 4.13(ii)] implies that Ax′ is an axiomatization of the equational theory of G_{n}, as follows. Let e be an equation that holds in G_{n}. We want to show that it follows from Ax′. Let Γ be a finite subset of n which strictly contains all the indices occurring in e (i.e. Γ contains some other index, too). By [N95, Lemma 4.13(ii)] then G_{Γ} ⊧ e. Then Ax_{Γ} ⊧ e, since Γ is finite. By Ax_{Γ} ⊆ Ax′ then Ax′ ⊧ e. Since IG_{n} is closed under subalgebras and direct products, the variety generated by G_{n} is HG_{n}. QED(Theorem)

References

AGN. Andréka,H. Goldblatt,R. Németi,I., Relativised quantification: some canonical varieties of sequence-set

algebras. Submitted. AT. Andréka,H. and Thompson,R.J., A Stone-type representation theorem for algebras of relations of higher

rank, Trans. Amer. Math. Soc. 309,2 (1988), 671-682. HMTII. Henkin,L. Monk,J.D. and Tarski,A., Cylindric Algebras. Part II. North-Holland, 1985. HMTAN. Henkin,L. Monk,J.D. Tarski,A. Andréka,H. and Németi,I., “Cylindric Set Algebras,” Lecture Notes in

Mathematics Vol 883, Springer-Verlag, Berlin, 1981, pp. vi + 323. MV. Marx.M. and Venema.Y., Multi-dimensional Modal Logic. Kluwer Academic Publisher, to appear. M95. Monk,J.D., Lectures on cylindric set algebras. In: Algebraic Methods in Logic and in Computer Science,

(Proc. Banach Semester Fall’ 1991). Banach Center Publications Vol 28, Institute of Mathematics, Polish Academy of Sciences, Warsaw 1993. Ed: C. Rauszer. pp.253-290.

N85. Németi,I., Cylindric-relativized set algebras have strong amalgamation, J. Symbolic Logic 50 (1985),

689-700. N86. Németi,I., Free algebras and decidability in algebraic logic. Doctoral Dissertation with the Academy,

Budapest, 1986. (In Hungarian.) N95. Németi,I., Decidable versions of first order logic and cylindric-relativized set algebras. In: Logic Collo-

quium’92 (Proc. Veszprém, Hungary 1992), eds: Csirmaz,L. and Gabbay,D. M. and de Rijke, M., Studies in Logic, Language and Computation, CSLI Publications, 1995. pp.177-241.

N96. Németi,I., Fine-structure analysis of first order logic. Arrow Logic and Multi-Modal Logic, M. Marx, L. Polos, and M. Masuch eds, CSLI Publications, Stanford, California, 1996. pp.221-247.

Keywords. 1980 Mathematics subject classifications: 03G15, 06, 08

H. Andréka : Mathematical Institute of the Hungarian Acad. of Sci., Budapest, Pf.127, H–1364, Hungary