Axiomatization of identity-free equations valid in relation algebras (Q1913874): Difference between revisions

Two new finite axiom systems are given for the identity-free equations valid in a relation algebra. They consist of the identity-free axioms of a relation algebra (i.e., the axioms distinct \(x\circ 1'= 1'\circ x=x\)) and one of the axioms \(x\leq x\circ ((y^\cup \circ y^-)^- \cdot (y^{-\cup} \circ y)^-)\), \(x\leq x\circ ((y^\cup \circ y^-)^- \cdot (z^\cup \circ z^- )^-)\); the latter axioms cannot be replaced by \(x\leq x\circ (y^\cup \circ y^-)\). This answers problems raised by Tarski and Jónsson. Further, let \(\text{RRA}^{\circ,\cup}\) be the class of all algebras of binary relations, up to isomorphism, whose operations are the Boolean ones, relation composition and the operation of taking converses, and let \(\text{RRA}^\circ\) be defined similarly but without the operation \({}^\cup\). Then \(\text{RRA}^{\circ, \cup}\) is finitely axiomatizable over \(\text{RRA}^\circ\).