Representability of small relation algebras and involutive FL-algebras
Peter Jipsen · 2007
The variety RA of relation algebras was originally defined by Tarski as the class of algebras (A,+, 0, ·, 1, − , ; , e, ` ) such that (A,+, 0, ·, 1, − ) is a Boolean algebra, (A, ; , e, ` ) is an involutive monoid (i.e.; is associative with unit e, x` ` = x and (x;y) ` = y`;x`), ; and ` distribute over +, and x`;(x;y) − ≤ y−. The variety RRA of representable relation algebras is generated by the square relation algebras Re(U) = (P(U2),∪, ∅,∩, U2, − , ◦, idU, −1) where U is any set. Monk [5] proved that RRA is a nonfinitely ax-iomatizable subvariety of RA, and Hirsch and Hodkinson [2] proved that it is undecidable whether a finite relation algebra is a member of RRA. Never-the-less this decision has been made for many specific finite relation algebras. Here we briefly summarize the results for re-lation algebras up to size 16. For a discussion about the history of enumerating small relation algebras we refer to Maddux [4] (p. 418+). In Table 1 we give graphical representations of the 115 integral relation algebras with 16 elements or less, numbered as in [4]. Recall that for relation algebras integral means e is an atom, and since the operations involving e are the same for all integral relation algebras, this atom is omitted from the pictures. The remaining atoms of the algebra are given by vertices of a directed (hyper)graph. An arrow points from vertex a to b if a; a ` ≥ b, and a vertex a is colored black if a; a ≥ a`. A 3-hyperedge (thin lines) connects 3 vertices a, b, c if a; b ` ≥ c. Two atoms that are placed closer together represent a converse pair r, r`. With this information each picture may be decoded into an operation table for the atoms of the algebra. E.g. if the algebra 2037 has atoms labeled a, r, r ` (from top to bottom, left to right), then the picture implies that a; a ≥ a, a; r ≥ r, r; a ≥ r and r; r ≥ a. Together with the identity atom, this gives the following operation table for; on the atoms of the algebra.