Pair-dense relation algebras.

*(English)*Zbl 0746.03055Summary: The central result of this paper is that every pair-dense relation algebra is completely representable. A relation algebra is said to be pair-dense if every nonzero element below the identity contains a “pair”. A pair is the relation algebraic analogue of a relation of the form \(\{\langle a,a\rangle\), \(\langle b,b\rangle\}\) (with \(a=b\) allowed). In a simple pair-dense relation algebra, every pair is either a “point” (an algebraic analogue of \(\{\langle a,a\rangle\})\) or a “twin” (a pair which contains no point). In fact, every simple pair-dense relation algebra \(\mathfrak A\) is completely representable over a set \(U\) iff \(| U|=\kappa+2\lambda\), where \(\kappa\) is the number of points of \(\mathfrak A\) and \(\lambda\) is the number of twins of \(\mathfrak A\).

A relation algebra is said to be point-dense if every nonzero element below the identity contains a point. In a point-dense relation algebra every pair is a point, so a simple point-dense relation algebra \(\mathfrak A\) is completely representable over \(U\) iff \(| U|=\kappa\), where \(\kappa\) is the number of points of \(\mathfrak A\). This last result actually holds for semiassociative relation algebras, a class of algebras strictly containing the class of relation algebras. It follows that the relation algebra of all binary relations on a set \(U\) may be characterized as a simple complete point-dense semiassociative relation algebra whose set of points has the same cardinality as \(U\).

Semiassociative relation algebras may not be associative, so the equation \((x;y)\); \(z=x\); \((y;z)\) may fail, but it does hold if any one of \(x\), \(y\), or \(z\) is 1. In fact, any rearrangement of parentheses is possible in a term of the form \(x_ 0;\cdots;x_{\alpha-1}\), in case one of the \(x_ \kappa\)’s is 1. This result is proved in a general setting for a special class of groupoids.

A relation algebra is said to be point-dense if every nonzero element below the identity contains a point. In a point-dense relation algebra every pair is a point, so a simple point-dense relation algebra \(\mathfrak A\) is completely representable over \(U\) iff \(| U|=\kappa\), where \(\kappa\) is the number of points of \(\mathfrak A\). This last result actually holds for semiassociative relation algebras, a class of algebras strictly containing the class of relation algebras. It follows that the relation algebra of all binary relations on a set \(U\) may be characterized as a simple complete point-dense semiassociative relation algebra whose set of points has the same cardinality as \(U\).

Semiassociative relation algebras may not be associative, so the equation \((x;y)\); \(z=x\); \((y;z)\) may fail, but it does hold if any one of \(x\), \(y\), or \(z\) is 1. In fact, any rearrangement of parentheses is possible in a term of the form \(x_ 0;\cdots;x_{\alpha-1}\), in case one of the \(x_ \kappa\)’s is 1. This result is proved in a general setting for a special class of groupoids.

##### MSC:

03G15 | Cylindric and polyadic algebras; relation algebras |

20L05 | Groupoids (i.e. small categories in which all morphisms are isomorphisms) |

##### Keywords:

complete representability; pair-dense relation algebra; point-dense relation algebra; semiassociative relation algebras
PDF
BibTeX
XML
Cite

\textit{R. D. Maddux}, Trans. Am. Math. Soc. 328, No. 1, 83--131 (1991; Zbl 0746.03055)

Full Text:
DOI

##### References:

[1] | Louise H. Chin and Alfred Tarski, Distributive and modular laws in the arithmetic of relation algebras, Univ. California Publ. Math. (N.S.) 1 (1951), 341 – 384. · Zbl 0045.31701 |

[2] | Augustus De Morgan, On the symbols of logic, the theory of the syllogism, and in particular of the copula, and the application of the theory of probabilities to some questions in the theory of evidence, Trans. Cambridge Philos. Soc. 9 (1856), 79-127. |

[3] | -, On the syllogism, no. IV, and on the logic of relations, Trans. Cambridge Philos. Soc. 10 (1864), 331-358. |

[4] | Augustus De Morgan, ”On the syllogism” and other logical writings, Edited, with an introduction, by Peter Heath, Yale University Press, New Haven, Conn., 1966. · Zbl 0168.00106 |

[5] | Leon Henkin, J. Donald Monk, and Alfred Tarski, Cylindric algebras. Part I, Studies in Logic and the Foundations of Mathematics, vol. 64, North-Holland Publishing Co., Amsterdam, 1985. With an introductory chapter: General theory of algebras; Reprint of the 1971 original. Leon Henkin, J. Donald Monk, and Alfred Tarski, Cylindric algebras. Part II, Studies in Logic and the Foundations of Mathematics, vol. 115, North-Holland Publishing Co., Amsterdam, 1985. · Zbl 0576.03042 |

[6] | Leon Henkin, J. Donald Monk, and Alfred Tarski, Cylindric algebras. Part I, Studies in Logic and the Foundations of Mathematics, vol. 64, North-Holland Publishing Co., Amsterdam, 1985. With an introductory chapter: General theory of algebras; Reprint of the 1971 original. Leon Henkin, J. Donald Monk, and Alfred Tarski, Cylindric algebras. Part II, Studies in Logic and the Foundations of Mathematics, vol. 115, North-Holland Publishing Co., Amsterdam, 1985. · Zbl 0576.03042 |

[7] | Bjarni Jónsson, Varieties of relation algebras, Algebra Universalis 15 (1982), no. 3, 273 – 298. · Zbl 0545.08009 |

[8] | Bjarni Jónsson and Alfred Tarski, Representation problems for relation algebras, Abstract 89, Bull. Amer. Math. Soc. 54 (1948), pp. 80 and 1192. · Zbl 0045.31505 |

[9] | Bjarni Jónsson and Alfred Tarski, Boolean algebras with operators. I, Amer. J. Math. 73 (1951), 891 – 939. · Zbl 0045.31505 |

[10] | Bjarni Jónsson and Alfred Tarski, Boolean algebras with operators. II, Amer. J. Math. 74 (1952), 127 – 162. · Zbl 0045.31601 |

[11] | John L. Kelley, General topology, D. Van Nostrand Company, Inc., Toronto-New York-London, 1955. · Zbl 0066.16604 |

[12] | Roger C. Lyndon, The representation of relational algebras, Ann. of Math. (2) 51 (1950), 707 – 729. · Zbl 0037.29302 |

[13] | Roger C. Lyndon, The representation of relation algebras. II, Ann. of Math. (2) 63 (1956), 294 – 307. · Zbl 0070.24601 |

[14] | R. C. Lyndon, Relation algebras and projective geometries, Michigan Math. J. 8 (1961), 21 – 28. · Zbl 0105.25303 |

[15] | Roger Maddux, Some sufficient conditions for the representability of relation algebras, Algebra Universalis 8 (1978), no. 2, 162 – 172. · Zbl 0386.03033 |

[16] | -, Topics in relation algebras, Doctoral dissertation, Univ. of California, Berkeley, 1978, pp. iii+241. |

[17] | Roger Maddux, The equational theory of \?\?\(_{3}\) is undecidable, J. Symbolic Logic 45 (1980), no. 2, 311 – 316. · Zbl 0435.03010 |

[18] | Roger Maddux, Some varieties containing relation algebras, Trans. Amer. Math. Soc. 272 (1982), no. 2, 501 – 526. · Zbl 0515.03039 |

[19] | Roger Maddux, A sequent calculus for relation algebras, Ann. Pure Appl. Logic 25 (1983), no. 1, 73 – 101. · Zbl 0528.03016 |

[20] | Roger D. Maddux, Nonfinite axiomatizability results for cylindric and relation algebras, J. Symbolic Logic 54 (1989), no. 3, 951 – 974. · Zbl 0686.03035 |

[21] | Roger D. Maddux and Alfred Tarski, A sufficient condition for the representability of relation algebras, Notices Amer. Math. Soc. 23 (1976), A-447. |

[22] | Elliott Mendelson, Introduction to mathematical logic, 3rd ed., The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1987. · Zbl 0681.03001 |

[23] | Donald Monk, On representable relation algebras, Michigan Math. J. 11 (1964), 207 – 210. · Zbl 0137.00603 |

[24] | J. Donald Monk, Completions of Boolean algebras with operators, Math. Nachr. 46 (1970), 47 – 55. · Zbl 0182.32301 |

[25] | Istvan Németi, Logic with \( 3\) variables has Gödel’s incompleteness property–thus free cylindric algebras are not atomic, Ann. Pure Appl. Logic (submitted). |

[26] | -, Free algebras and decidability in algebraic logic, Doctoral dissertation, Hungarian Academy of Sciences, Budapest, 1986. |

[27] | Charles Sanders Peirce, Collected papers, Edited by Charles Hartshorne and Paul Weiss. 6 vols. I: Principles of philosophy. II: Elements of logic. III: Exact logic. IV: The simplest mathematics. V: Pragmatism and pragmaticism. VI: Scientific metaphysics, The Belknap Press of Harvard University Press, Cambridge, Mass., 1960. · Zbl 0173.00105 |

[28] | F. W. K. Ernst Schröder, Vorlesungen über die Algebra der Logik (exakte Logik), Vol. III, Algebra und Logik der Relative, Part I, Leipzig, 1895, pp. viii+649. Reprint by Chelsea, Bronx, 1966. |

[29] | Gunter Schmidt and Thomas Ströhlein, Relation algebras: concept of points and representability, Discrete Math. 54 (1985), 83-92. · Zbl 0575.03040 |

[30] | Alfred Tarski, On the calculus of relations, J. Symbolic Logic 6 (1941), 73 – 89. · Zbl 0026.24401 |

[31] | -, Some metalogical results concerning the calculus of relations, J. Symbolic Logic 18 (1953), 188-189. |

[32] | -, A formalization of set theory without variables, J. Symbolic Logic 18 (1953), 189. |

[33] | Alfred Tarski, Contributions to the theory of models. III, Nederl. Akad. Wetensch. Proc. Ser. A. 58 (1955), 56 – 64 = Indagationes Math. 17, 56 – 64 (1955). · Zbl 0058.24702 |

[34] | Alfred Tarski and Steven Givant, A formalization of set theory without variables, American Mathematical Society Colloquium Publications, vol. 41, American Mathematical Society, Providence, RI, 1987. · Zbl 0654.03036 |

[35] | Alfred North Whitehead and Bertrand Russell, Principia mathematica, Vol. I, Cambridge Univ. Press, 1910, pp. xv+666. · Zbl 0552.01011 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.