Nonrepresentable relation algebras generated by functional elements

DOI10.1007/S00012-004-1842-8MaRDI QIDQ2577687zbMATH OpenOpenAlexFDO

Authors Roger Maddux

Publication date 6 January 2006

Published in Algebra Universalis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00012-004-1842-8

zbMATH Keywords

functional elementrelation algebrarepresentable algebra

Mathematics Subject Classification ID

Cylindric and polyadic algebras; relation algebras (03G15)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 67049
• Bifunctional-elementary relation algebras
• Functionally dense relation algebras
• Weakly representable but not representable relation algebras
• scientific article; zbMATH DE number 67045
• Undecidability of representability as binary relations
• A simple construction of representable relation algebras with non-representable completions
• The origin of relation algebras in the development and axiomatization of the calculus of relations
• scientific article; zbMATH DE number 5539272
• Completely Representable Relation Algebras

Cited in

(8)

• Non-embeddable simple relation algebras
• Functionally dense relation algebras
• A nonpermutational integral relation algebra
• Residuation algebras with functional duals
• Bifunctional-elementary relation algebras
• Splitting atoms in relational algebras
• The Structure of Relation Algebras Generated by Relativizations
• scientific article; zbMATH DE number 763537 (Why is no real title available?)

This page was built for publication: Nonrepresentable relation algebras generated by functional elements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2577687)