Nonrepresentable relation algebras generated by functional elements (Q2577687)

An element \(p\) of a relation algebra is said to be functional if \(\check{p};p\leq 1\)'. In a proper relation algebra, that is, when elements of an algebra are sets of pairs, functional elements correspond to graphs of functions. Functional elements of relation algebras turn out to play an important role in deciding whether a given relational algebra is representable. \textit{B. Jónsson} and \textit{A. Tarski} [``Boolean algebras with operators. II'', Am. J. Math. 74, 127--162 (1952; Zbl 0045.31601)] proved that a relation algebra is representable if its Boolean unit is the join of a finite number of functional elements. \textit{R. D. Maddux} and \textit{A. Tarski} [``A sufficient condition for the representability of relation algebras'', Notices Am. Math. Soc. 23, A-447 (1976)] strengthened this result by showing that if a Boolean unit of a relation algebra is a join of an arbitrary set of functional elements, then it is representable. \textit{A. Tarski} [``Some metalogical results concerning the calculus of relations'', J. Symb. Logic 18, 188--189 (1953)] also gave another sufficient condition of representability. He proved that if a Boolean unit of a relation algebra has the form \(\check{p};q\) for some functional elements \(p\) and \(q\), then it is representable. \textit{R. Maddux} [``Some sufficient conditions for the representability of relation algebras'', Algebra Univers. 8, 162--172 (1978; Zbl 0386.03033)] showed that the same result holds if one takes arbitrary joins \(\bigvee \{\check{p};q : \check{p};p\leq 1\)', \(\check{q};q\leq 1\)'\(\}\) of products of functional elements. These results naturally raise the following question [\textit{R. Maddux}, ``A perspective on the theory of relation algebras'', Algebra Univers. 31, 456--465 (1994; Zbl 0803.03043)]: Is a relation algebra generated by its functional elements representable? This paper gives a negative solution to this problem by constructing a finite non-representable relation algebra, which is generated by its two functional elements. It is still an open question whether a relation algebra generated by a single functional element is representable.