Nonrepresentable Sequential Algebras PETER JIPSEN, Department of Mathematics and Applied Mathematics, University of Cape Town, 7700 Rondebosch, South Africa. E-mail:
[email protected] ROGER D. MADDUX, Department of Mathematics, 400 Carver Hall, Iowa State University, Ames, Iowa 50011-2066, USA. E-mail:
[email protected] Abstract The sequential calculus of von Karger and Hoare [18] is designed for reasoning about sequential phenomena, dynamic or temporal logic, and concurrent or reactive systems. Unlike the classical calculus of relations, it has no operation for forming the converse of a relation. Sequential algebras [15] are algebras that satisfy certain equations in the sequential calculus. One standard example of a sequential algebra is the set of relations included in a partial ordering. Nonstandard examples arise by relativizing relation algebras to elements that are antisymmetric, transitive, and reflexive. The incompleteness and non-finite-axiomatizability of the sequential calculus are examined here from a relation-algebraic point of view. New constructions of nonrepresentable relation algebras are used to prove that there is no finite axiomatization of the equational theory of antisymmetric dense locally linear sequential algebras. The constructions improve on previous examples in certain interesting respects and give yet another proof that the classical calculus of relations is not finitely axiomatizable.1 Keywords : sequential algebras, relation algebras, completeness, axiomatizability, representability
Definition 1.1 (von Karger [15]) Suppose sequential algebra if
A
, = hA, +, ·, −, 0, 1, ;, ., /, 1 i.
A
is a
• The reduct hA, +, ·, −, 0, 1i is a Boolean algebra, , • the reduct hA, ;, 1 i is a monoid, and, for all p, q, r ∈ A, • • •
(p;q) · r = 0 iff (p . r) · q = 0 iff (r / q) · p = 0, p;(q / r) ≤ (p; q) / r, , , 1 /p = p.1 .
If A is a sequential algebra, then the identity in the right column:
A is given the name in the left column if it satisfies
symmetric antisymmetric locally linear dense
, 1 /1 = 1 , , 1 /1 = 1 (p;q) / r = p; (q / r) + p /(r / q) , , , 1 ≤ 1 ;1
1 Full version of an invited paper presented at the 3rd Workshop on Logic, Language, Information and Computation (WoLLIC’96 ), May 8–10, 1996, Salvador (Bahia), Brazil, organised by UFPE and UFBA, and sponsored by IGPL, FoLLI, ASL.
L. J. of the IGPL, Vol. 5 No. 4, pp. 565–574 1997
565
c Oxford University Press
566
Nonrepresentable Sequential Algebras
Except for density, these concepts occur in [15]. Definition 1.2 Suppose
A = hA, +, ·, −, 0, 1, ;,˘, 1,i. A is a relation algebra if
• The reduct hA, +, ·, −, 0, 1i is a Boolean algebra, , • The reduct hA, ;, 1 i is a monoid, and, for all p, q, r ∈ A, • (p;q) · r = 0 iff (˘ p ;r) · q = 0 iff (r ; q˘) · p = 0. For more background on relation algebras and sequential algebras, we refer the reader to [5], [10], [15], [18]. In, particular the definitions above can be restated in terms of equations, so both the class of all sequential algebras and the class of all relation algebras are varieties, denoted by RA and SeA respectively. Every relation algebra is (term-equivalent to) a sequential algebra if one defines binary operations . and / by p . q = p˘;q p / q = p; q˘. (1.1) , Conversely, if the unary operation ˘ is defined by p˘ = 1 / p in a sequential algebra A, then A is term-equivalent to a relation algebra iff A satisfies the equations (1.1). In [8] it is also shown that a sequential algebra is (term-equivalent to) a relation algebra iff the equation p;(q / r) = (p;q) / r holds. From an algebraic point of view, the two varieties differ in that RA is a discriminator variety while SeA is not (see e.g., [4]). In many other respects sequential algebras are similar to relation algebras. , Suppose A = hA, +, ·, −, 0, 1, ;, ˘, 1 i is a relation algebra and u ∈ A. We say that u is , reflexive if 1 ≤ u, transitive if u;u ≤ u, symmetric if u = u ˘, , antisymmetric if u · u˘ ≤ 1 , linear if 1 = u + u˘, locally linear if u; u˘ · u ˘ ;u ≤ u + u˘, , , , dense if (u · 1 ) ≤ (u · 1 );(u · 1 ) Let
Rlu A = {x : u ≥ x ∈ A}.
Then Rlu A is closed under + and ·, contains 0, and has maximum element u. Define relative complementation on Rlu A by x−u = x · u. Then
Rlu A, +, ·, −u , 0, u is again a Boolean algebra, the one obtained by relativizing to u. Suppose u is reflexive and transitive. Then Rlu A is also closed under ; since u is transitive, and , Rlu A contains 1 since u is reflexive. Define two more binary operations . and / on Rlu A by x . y = x˘ ;y · u and x / y = x; y˘ · u. This gives a relativized reduct algebra
Sequ (A) = Rlu A, +, ·, −u , 0, u, ;, ., /, 1, . Theorem 1.3 (von Karger [15]) If A is a relation algebra and u is a reflexive and transitive element of A, then Sequ (A) is a sequential algebra.
Nonrepresentable Sequential Algebras
567
In [15] it is shown that the relativization of a relation algebra with respect to an element that is locally linear or antisymmetric (as well as transitive and reflexive) results in a sequential algebra that is locally linear or antisymmetric, respectively. The same is true for density. , Example 1.4 Let A be the finite relation algebra whose atoms are 1 , a, ˘a, b, ˘b, c, and c˘, and whose relative multiplication is determined by the following table. (The , “+” signs are omitted to save space, e.g., a; b = a + b and a; a ˘ = 1 + b + ˘b + c + c˘.) ; , 1 a b c a ˘ ˘b c˘
, 1 , 1 a b c a ˘ ˘b c˘
˘b a b c ˘a c˘ ˘b a b c ˘a c˘ , bc ab ac 1 b˘bc˘ c a˘ ab˘b a˘ ac˘ c , ˘ ˘ ab ac bc a˘ abb 1 a˘ ac˘ c bbc˘ c , ac bc ab a˘ ac˘ c b˘bc˘ c 1 a˘ ab˘b , ˘b˘ 1 b˘bc˘ c a˘ ab˘b a˘ ac˘ c c a ˘˘b a ˘c˘ , ˘ ˘ ˘ ˘ a˘ abb 1 a˘ ac˘ c bbc˘ c ˘ab a ˘c˘ b˘ c , ˘b˘ a˘ ac˘ c b˘bc˘ c 1 a˘ ab˘b ˘ac˘ c ˘a˘b
, Let u = 1 + a + b + c. Then u is transitive and reflexive, so Sequ (A) is a sequential , algebra. Its atoms are 1 , a, b, and c, and its non-Boolean binary operations are determined by the following tables. ; , 1 a b c / , 1 a b c . , 1 a b c
, 1 , 1 a b c , 1 , 1 0 0 0
, 1 , 1 a b c
a b a b b+c a+b a+b a+c a+c b+c
c c a+c b+c a+b
a b c 0 0 0 , 1 +b+c a+b a+c , a+b 1 +a+c b+c , a+c b+c 1 +a+b a b c a b c , 1 +b+c a+b a+c , a+b 1 +a+c b+c , a+c b+c 1 +a+b
Note that u is antisymmetric, dense, and linear, and that symmetric, dense, and locally linear.
Sequ (A) is therefore anti-
Problem 1. Does every sequential algebra arise in this way, i.e., is every sequential algebra S isomorphic to Sequ (A) for some relation algebra A and some transitive and reflexive element u? Problem 2. Is every locally linear sequential algebra S isomorphic to Sequ (A) for some relation algebra A and some locally linear, transitive and reflexive element u?
568
Nonrepresentable Sequential Algebras
If u is a preorder on X, then u is a transitive and reflexive element in the relation algebra Re (X) of all binary relations on X and Sequ (Re (X)) is the sequential algebra of all subrelations of u. We say that a sequential algebra is representable if it is isomorphic to a subalgebra of an algebra of the form Sequ (Re (X)), where u is a preorder on some set X. If a sequential algebra happens to be a relation algebra, then this notion of representability agrees with the standard one for relation algebras. Von Karger uses a different notion of representability, defined in terms of locally linear observation spaces. In [17], it is shown that these spaces can be extended to Brandt groupoids. Complex algebras of Brandt groupoids are representable relation algebras [7]. Hence representability defined via locally linear observation spaces implies representability in the sense used here. Our notion is more general since we do not assume local linearity. Under that assumption, however, the notions coincide. For every sequential algebra A define the unary operation c by c(x) = x + 1;x + x;1+x . 1+1 . x+x / 1+1 / x for every x ∈ A. Then c is self-conjugate: x·c(y) = 0 iff c(x) · y = 0. Every homomorphism h of a sequential algebra of A determines an ideal I = {x ∈ A : h(x) = 0}. If i ∈ I then c(i) ∈ I. On the other hand, if c(z) = z ∈ A then the function hx · z : x ∈ Ai is a homomorphism of A onto a sequential algebra whose universe is Rlz A = {y : z ≥ y ∈ A} and whose operations are obtained from those of A by relativizing to z. Andr´eka and N´emeti pointed out in a letter to the first author that the following theorem can be proved, as is done here, by imitating the proof (due to N´emeti) of Theorem [3, 5.5.10], that cylindric-relativized set algebras form a variety. Theorem 1.5 The class of representable sequential algebras is a variety. Proof. It is obvious that the class of representable sequential algebras is closed under the formation of subalgebras, and not difficult to show that it is also closed under direct products. It therefore suffices to show that every homomorphic image of a representable sequential algebra is representable. Assume that A ⊆ Sequ (Re (X)), where u is a preorder on some set X, and that I is an ideal of A determined by a homomorphism. We wish to embed A/I into a representable sequential algebra. Let E be an ultrafilter on I such that {j : i ≤ j ∈ I} ∈ E for every i ∈ I. (E exists since the sets in question have the finite intersection property.) Let ∼E be the equivalence relation defined for s, s0 ∈ I X by s∼E s0 ⇐⇒ {i ∈ I : si = s0i } ∈ E and define the equivalence class s/∼E by s/∼E = {s0 ∈ I X : s∼E s0 }. For every x ∈ A let ρ(x) = hs/∼E , s0 /∼E i : s, s0 ∈ I X ∧ {i ∈ I : hsi , s0i i ∈ x} ∈ E It is easy to check that ρ is a homomorphism of A into Seqρ(u) Re I X/∼E . Next we construct a homomorphism hx for every x ∈ A ∼ I. Let x ∈ A ∼ I. Then x 6≤ i for every i ∈ I, so there are s(x), s0 (x) ∈ I X such that hs(x)i , s0 (x)i i ∈ x · i for every i ∈ I. (1.2) S Let r(x) = {hs(x)/∼E , s0 (x)/∼E i}, z = {cn (r(x)) : n ∈ ω}, and set hx (y) = ρ(y) ∩ z for every y ∈ A. Then c(z) = z ⊆ ρ(u), so hx is a homomorphism of A into Seqz Re I X/∼E . By (1.2) we have {i ∈ I : hs(x)i , s0 (x)i i ∈ x} = I ∈ E, so r(x) ⊆ hx (x), hence hx (x) 6= ∅. Next we show that if j ∈ I then hx (j) = ∅. Suppose
Nonrepresentable Sequential Algebras 569 S j ∈ I. Since hx (j) = {ρ(j)∩cn (r(x)) : n ∈ ω}, it suffices to prove ρ(j)∩cn (r(x)) = ∅ for every n ∈ ω. We get cn (j) ∈ I from j ∈ I, so {i ∈ I : cn (j) ≤ i} ∈ E by the choice of E. However, from (1.2) we get / cn (j)} {i ∈ I : cn (j) ≤ i} ⊆ {i ∈ I : hs(x)i , s0 (x)i i ∈ so hs(x)/∼E , s0 (x)/∼E i ∈ / ρ(cn (j)), i.e., r(x) ∩ ρ(cn (j)) = ∅. Since ρ is a homomorphism and c is self-conjugate, this gives cn (r(x)) ∩ ρ(j) = ∅, as desired. For every hx . Each Ax is a repx ∈ A ∼ I, let Ax be the image of A under the homomorphism Q resentable sequential algebra, so the product B = x∈A∼I Ax is also representable. Since the ideal of hx contains I, there is a homomorphism gx : A/I → Ax such that gx (y/I) = hx (y) for every y ∈ A. In particular, gx (x/I) = hx (x) 6= ∅. Define a function f from A/I into B by f(y/I) = hgx(y/I) : x ∈ A ∼ Ii for every y ∈ A. Then f is a homomorphism and f is one-to-one since gx (x/I) 6= ∅ whenever x ∈ A ∼ I. As one referee observed, every nonrepresentable relation algebra is term-equivalent to a nonrepresentable sequential algebra. Hence the existence of nonrepresentable sequential algebras is not surprising. Furthermore, since the variety of representable relation algebras is not finitely axiomatizable, it follows that the same is true for the variety of representable sequential algebras. However, this argument does not apply to the subvariety of antisymmetric sequential algebras. Indeed, if a relation algebra A is term-equivalent to an antisymmetric sequential algebra then A must be Boolean, since , , , 1 = 1 / 1 = 1 ;˘ 1 = 1, and all Boolean relation algebras are representable. To obtain nonrepresentable antisymmetric sequential algebras we relativize nonrepresentable relation algebras to antisymmetric elements. Theorem 1.6 The equation z · (x · p;q); (y · r ;s) ≤ p;[q ;r · (p . z · q ;y) / s · p .(x;r · z / s)]; s
(1.3)
holds in every representable sequential algebra but fails in 1774 of the 3677 finite indecomposable antisymmetric sequential algebras that have exactly 4 atoms. For example, equation (1.3) fails in the 16-element sequential algebra A (defined in example 1.4) when p = a, q = a, r = a, s = b, x = c, y = b, and z = c. Proof. To check that (1.3) holds in all representable sequential algebras is a simple matter of assuming that an ordered pair hv, wi is an element of the left hand side of (1.3), which implies the existence of three other elements, and then showing that hv, wi is always an element of the right hand side. The number of nonisomorphic indecomposable sequential algebras were found by computer, and the result shows that there are many small nonrepresentable antisymmetric sequential algebras. However, it can be shown that all sequential algebras with at most 8 elements are representable. To see that (1.3) fails in A, we note that under the given assignment, the left hand side evaluates to c, while the right hand side gives a;[(b + c) · (a + b) · (a + c)];b = 0. Next we construct a sequence of relation algebras that have nonrepresentable antisymmetric sequential algebras as relative subalgebras and are also locally linear and dense. Any nonprincipal ultraproduct of these algebras will however be representable. This result implies that the equational theory of the variety of antisymmetric dense locally linear representable sequential algebras is not finitely axiomatizable.
Nonrepresentable Sequential Algebras , Example 1.7 For each n ≥ 3 let An be the relation algebra that has 2n + 1 atoms 1 , a1 , a ˘ 1 , . . . , an , ˘ an , and whose relative multiplication is such that 570
, , 1 ;ai = ai = ai ;1 , ai ;ai = ai · (a1 + . . . + an ), ai ;aj = a1 + . . . + an wherenever 1 ≤ i 6= j ≤ n. These conditions determine relative multiplication completely. For example, we can deduce that ai = a ˘i · (˘ a1 + . . . + a ˘n ) a ˘i ;˘ aj = a ˘1 + . . . + ˘an if i 6= j, a ˘i ;˘ ai = ˘ai ;ai = ai + ˘ai , ai ;˘ , aj = a ˘i ;aj = 0 if i 6= j. ai ;˘ , The element un = 1 +a1 +. . .+an is a reflexive transitive antisymmetric linear dense element of An . Therefore Sequn (An ) is a sequential algebra that is antisymmetric, dense, locally linear, and has n + 1 atoms. For example, considering the case n = 3, we find that the table for relative multiplication in Sequ3 (A3 ) is ; , 1 a1 a2 a3
, 1 , 1 a1 a2 a3
a1 a1 a2 + a3 a1 + a2 + a3 a1 + a2 + a3
a2 a2 a1 + a2 + a3 a1 + a3 a1 + a2 + a3
a3 a3 a1 + a2 + a3 a1 + a2 + a3 a1 + a2
Every diversity atom in An has a “color”, a number from 1 to n, and an “orientation”, either “up” or “down”. The orientation of ai is “up” and its color is i. The , orientation of ˘ ai is “down” and its color is i. 1 has no color and no orientation. Suppose a, b, c are diversity atoms. Then the only circumstances under which we do not have a;b ≥ c are • the orientations of a, b, c violate u3 ;u3 = u3 (e.g., a up, b up, c down) • a, b, c all have the same color
, • the identity law is violated (e.g., a = 1 but b 6= c). ˘k because u3 ;u3 = u3 , ai ;ai 6≥ ai because three atoms of the For example, ai ;aj 6≥ a , same color are involved, and ai ;1 6≥ aj when i 6= j by the identity law.
An is a nonrepresentable relation algebra. Proof. Assume, to the contrary, that An is representable. Since An is also simple, there is a set X and an isomorphism ρ that maps An onto a subalgebra of Re (X). Theorem 1.8 For 3 ≤ n,
From the properties of u it follows that ρ(un ) is a dense linear ordering without endpoints. Consequently X is infinite. We will use a special case of Ramsey’s Theorem to derive a contradiction, thus showing that An cannot be representable. To apply
Nonrepresentable Sequential Algebras
571
Ramsey’s Theorem, we show that the 2-element subsets of X can be partitioned into n disjoint sets T1 , . . . , Tn . For each i = 1, . . . , n let Ti = {{x, x0} : {hx, x0 i , hx0 , xi} ⊆ ρ(ai + ˘ai )} If 1 ≤ i < j ≤ n then the relations ρ(ai + a ˘i ) and ρ(aj + a ˘j ) are disjoint, so Ti and Tj are also disjoint. The relation ρ(ai + a ˘i ) is symmetric, so for any 2-element subset {x, x0 } of X, the symmetric binary relation {hx, x0i , hx0 , xi} is either included ˘i ) or else is disjoint from ρ(ai + a ˘i ). Thus the sets Ti form a partition of the in ρ(ai + a 2-element subsets of X. Since X is infinite, Ramsey’s Theorem implies that for some i ∈ {1, . . . , n} there is an infinite subset Y of X that is “homogeneous for Ti ”, i.e., all 2-element subsets of Y are in Ti . We only need to know that Y has three elements to get a contradiction. Choose y, y0 , y00 ∈ Y . Then {y, y0 }, {y0 , y00 }, and {y, y00 } are in Ti , so {hy, y0 i , hy0 , y00 i , hy, y00 i} ⊆ ρ(ai +˘ai ), hence hy, y00 i ∈ ρ((ai +˘ai );(ai +˘ai )·(ai +˘ai )), but this is contradictory since ˘i ); (ai + a ˘i ) · (ai + a ˘i ) (ai + a ˘i + ˘ ai ;ai + a ˘i ;˘ai ) · (ai + a ˘i ) = (ai ;ai + ai ; a ˘i · (˘ a1 + . . . + a ˘n )) · (ai + ˘ai ) = (ai · (a1 + . . . + an ) + ai + ˘ai + a =0
Theorem 1.9 For 3 ≤ n, Sequn (An ) is a nonrepresentable antisymmetric dense locally linear sequential algebra. Proof. We imitate the proof that An is a nonrepresentable relation algebra. Assume Sequn (An) has a representation ρ. Since ρ(un ) is transitive, dense, and antisymmetric, the field of ρ(un ) must be infinite. By Ramsey’s Theorem, that field has an infinite subset that is homogeneous for some color i, hence ρ(ai ;ai · ai ) 6= ∅. But ai ;ai · ai = 0, so ρ(ai ;ai · ai ) = ∅, a contradiction. Every finite nonrepresentable relation algebra A can be used to construct an equation that is satisfied by all representable relation algebras but fails in A. Such an equation can be obtained by translating into equational form the universal first-order sentence asserting that there is no subalgebra isomorphic to A. In special cases simpler equations can be found. For example, the following equation holds in all representable relation and sequential algebras but fails in both A3 and Sequ3 (A3 ) when u = w = y = a1 and v = x = z = a2 . u . v · w ;x · y / z ≤ (u .[u;y · v ;z · (u;w · v / x); (w . y · x;z)]) / z
(1.4)
Equation (1.4) is closely related to equation (1.3) and originates with Lyndon [9]. We now turn to the task of showing that the ultraproduct of the algebras An for 3 ≤ n is representable. For any relation algebra A and any n > 3, let Bn A be the set of n-by-n matrices of atoms of A that satisfy the following conditions: , (B0 ) mii ≤ 1 for all i < n, (B1 ) m ˘ ij = mji for all i, j < n,
572
Nonrepresentable Sequential Algebras
(B2 ) mij ≤ mik ;mkj for all i, j, k < n. The elements of Bn A are called (n−1)-dimensional simplices (The geometric dimension of a simplex is n − 1, one less than its size as a matrix.) For i ≤ n, two simplices m and m0 in Bn A agree up to i (in symbols m ≡(i) m0 ) if the only differences between them are confined to their ith rows and ith columns, more precisely, mkl = m0kl whenever k, l < n and k, l 6= i. A subset M of Bn A is called an n-dimensional relational basis for A if (R0 ) for every atom a of A there is a simplex m ∈ M such that m01 = a, and (R1 ) if m ∈ M , k 6= i, j < n and a, b are atoms of A for which mij ≤ a;b then there is a simplex m0 ∈ M such that m0ik = a, m0kj = b and m ≡(k) m0 . RAn is defined to be the class of all relation algebras that are subalgebras of some complete and atomic relation algebra which has an n-dimensional relational basis. It is proved in [11] that RA = RA4 ⊇ RA5 ⊇ RA6 ⊇ · · · is a decreasing sequence of varieties, and the intersection of all of them is the variety of representable relation algebras. (It is proved in [13] that the sequence is strictly decreasing.) The next result shows that, although the algebras An of example 1.7 are nonrepresentable, they do become “more representable” for larger n. Theorem 1.10 For 3 ≤ n, Bn+1 An is an (n + 1)-dimensional relational basis for hence An ∈ RAn+1 .
An,
Proof. Condition (R0 ) is easy to satisfy when M = Bn+1 An : given an atom a, define , m by mij = a if i = 0 < j ≤ n, mij = a ˘ if j = 0 < i ≤ n, and mij = 1 otherwise. To verify condition (R1 ), let m ∈ Bn+1 An , fix k 6= i, j ≤ n and choose atoms a, b such that mij ≤ a;b. We need to define m0lk for l 6= i, j, k (the remaining entries for , , m0 follow from (B0 ), (B1 ) and m ≡(k) m0 ). If a = 1 we take m0lk = mli , and if b = 1 , 0 we take mlk = mlj . The interesting case a 6= 1 6= b is handled as follows: , For p, q ≤ n with p, q 6= k, define p q iff mpq ≤ un (= 1 + a1 + · · · + an ), and , define p ≈ q iff p q and q p (iff mpq ≤ 1 ). Since un is a reflexive, transitive, linear element of An , is a linear preorder and hence ≈ is an equivalence relation. To satisfy (B2 ) we first assign the same color to m0pk , m0qk iff p ≈ q. (This is possible since there are at most n − 2 assignments to be made, and n − 2 colors available, not counting the colors of a, b.) We still have to assign orientations. If a, ˘b are both up (down), let m0lk be up (down), respectively. If a, b are both up, then i j since mij ≤ a; b ≤ un ; un = un . Let m0lk be up whenever l i, and down otherwise. This inserts k as the -successor of i in the linear preorder . The case if a, b are both down is handled dually. In all cases m0 is a simplex since (defined on {0, 1, . . . , n}) is a linear preorder and for any p, q, r ≤ n the atoms m0pq , m0qr , m0pr are never all the same color. Theorem 1.11 If E is a nonprincipal ultrafilter on the index set I = {3, 4, 5, . . .}, then • the ultraproduct of the relation algebras An by E is a representable relation algebra, and • the ultraproduct of the sequential algebras Sequn (An ) by E is a antisymmetric dense locally linear representable sequential algebra.
Nonrepresentable Sequential Algebras
573
Proof. Let ∼E be the equivalence relation on the direct product algebra B = Q n∈I An defined for arbitrary a, b ∈ B by a ∼E b iff {i ∈ I : ai = bi } ∈ E. Then ∼E is a congruence relation on the algebra B, and the quotient algebra C = B/∼E is ˜ be the product of the sequential the ultraproduct of the relation algebras An . Let B ˜ ⊆ B. Then algebras Sequn (An ) for n ∈ I, and let ≈E be the restriction of ∼E to B ˜ . Define ≈E is the E-ultrafilter congruence on B uω = hun : n ∈ Ii /∼E = {a ∈ B : a ∼E hun : n ∈ Ii}. ˜ = B ˜ /≈E is isomorphic to It is straightforward to check that the ultraproduct C Sequω (C) via the map a/≈E 7→ a/∼E . Consider an arbitrary k ≥ 3. If n ≥ k − 1 then RAn+1 ⊆ RAk , and An ∈ RAn+1 for every n ≥ 3, so {n : An ∈ RAk } ⊇ {k − 1, k, k + 1, k + 2, . . .}. E is nonprincipal, E. Every RAk T is an elementary class by [11], so C ∈ hence {n : An ∈ RAk } ∈ T RAk . This shows that C ∈ 3≤k RAk . But 3≤k RAk is the variety of representable relation algebras, so C is representable. C is also simple because simplicity has a first-order characterization for relation algebras and each An is simple. It follows that C is isomorphic to a subalgebra of an algebra Re (X) for some set X. Now C˜ is a antisymmetric dense locally linear representable sequential algebra since it is isomorphic to a relativization of C by the reflexive transitive antisymmetric dense linear element uω . Corollary 1.12 The variety of antisymmetric dense locally linear representable sequential algebras is not finitely axiomatizable. Proof. This follows from the existence of antisymmetric dense locally linear representable ultraproducts of the nonrepresentable antisymmetric dense locally linear sequential algebras Sequn (An ). The previous theorem says there are many. Of course, theorem 1.11 also shows that the variety of representable relation algebras is not finitely axiomatizable. This has already been proved and generalized in several ways, by Monk [14], Andr´eka [1], [2], J´onsson [6], and Maddux [12]. The construction in example 1.7 is simpler than previous ones in certain respects, including the sizes of the algebras and the proofs of their properties. The corollary was first proved by Andr´eka and von Karger [16] for the concept of representability via linear categories (i.e., antisymmetric locally linear observation spaces), using sequential algebras An with 3n! + n + 1 atoms instead of n + 1.
References [1] H. Andr´ eka, Weakly representable but not representable relation algebras, Algebra Universalis 32:31–43, 1994. [2] H. Andr´eka, Complexity of the equations valid in algebras of relations, Annals of Pure and Applied Logic, 1997, to appear. [3] L. Henkin, J. D. Monk, and A. Tarski, Cylindric Algebras, Part II, North-Holland, Amsterdam, 1985. [4] P. Jipsen, Discriminator varieties of Boolean algebras with residuated operators, Algebraic Methods in Logic and their Computer Science Applications (C. Rauszer, ed.), Banach Center Publications, vol. 28, Polish Academy of Sciences, 1993, pp. 239–252. [5] B. J´ onsson, Varieties of relation algebras, Algebra Universalis 15:273–298, 1982.
574
Nonrepresentable Sequential Algebras
[6] B. J´ onsson, The theory of binary relations, Algebraic Logic (Proc. Conf. Budapest 1988) (Amsterdam) (H. Andr´ eka, J. D. Monk, , and I. N´ emeti, eds.), Colloquia Mathematica Societatis J´ anos Bolyai, vol. 54, North-Holland, 1991, pp. 245–292. [7] B. J´ onsson and A. Tarski, Boolean algebras with operators, Part II, American Journal of Mathematics 74:127–162, 1952. [8] B. J´ onsson and C. Tsinakis, Relation algebras as residuated Boolean algebras, Algebra Universalis 30:469–478, 1993. [9] R. C. Lyndon, The representation of relational algebras, Annals of Mathematics 51:707–729, 1950. [10] R. D. Maddux, Some varieties containing relation algebras, Trans. Amer. Math. Soc. 272:501– 526, 1982. [11] R. D. Maddux, A sequent calculus for relation algebras, Annals of Pure and Applied Logic 25:73–101, 1983. [12] R. D. Maddux, Nonfinite axiomatizability results for cylindric and relation algebras, The Journal of Symbolic Logic 54:951–974, 1989. [13] R. D. Maddux, Relation algebras of every dimension, The Journal of Symbolic Logic 57:1213– 1229, 1992. [14] J. D. Monk, On representable relation algebras, Michigan Mathematical Journal 11:207–210, 1964. [15] B. von Karger, Sequential calculus, ProCos II: Technical Report [Kiel BvK 15/11], ChristianAlbrechts Universit¨ at zu Kiel, August 1995. [16] B. von Karger, The class of representable sequential algebras is not finitely axiomatizable, draft, 16pp., July 1994. [17] B. von Karger, Embedding sequential calculus in relational calculus, draft, 15pp., March 1994. [18] B. von Karger and C.A.R. Hoare, Sequential calculus, Information Processing Letters 53(3):123– 130, 1995.
Received 29 August 1996. Revised 15 December 1996
