Pair-dense relation algebras

Author:
Roger D. Maddux

Journal:
Trans. Amer. Math. Soc. **328** (1991), 83-131

MSC:
Primary 03G15; Secondary 08B99, 68Q99

DOI:
https://doi.org/10.1090/S0002-9947-1991-1049616-1

MathSciNet review:
1049616

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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 (with allowed). In a simple pair-dense relation algebra, every pair is either a "point" (an algebraic analogue of ) or a "twin" (a pair which contains no point). In fact, every simple pair-dense relation algebra is completely representable over a set iff , where is the number of points of and is the number of twins of .

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 is completely representable over iff , where is the number of points of . 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 may be characterized as a simple complete point-dense semiassociative relation algebra whose set of points has the same cardinality as .

Semiassociative relation algebras may not be associative, so the equation may fail, but it does hold if any one of , or is . In fact, any rearrangement of parentheses is possible in a term of the form , in case one of the is . This result is proved in a general setting for a special class of groupoids.

**[CT51]**Louise H. Chin and Alfred Tarski,*Distributive and modular laws in the arithmetic of relation algebras*, Univ. of California Publ. Math. (N.S.)**1**(1951), 341-384. MR**0043763 (13:312f)****[D1856]**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.**[D1864]**-,*On the syllogism, no*. IV,*and on the logic of relations*, Trans. Cambridge Philos. Soc.**10**(1864), 331-358.**[D66]**-,*On the syllogism, and other logical writings*, edited, with an Introduction by Peter Heath, Yale Univ. Press, New Haven, Conn., 1966, pp. xxxi+355. MR**0230587 (37:6147)****[HMT71]**Leon Henkin, J. Donald Monk, and Alfred Tarski,*Cylindric algebras*, Part I, North-Holland, Amsterdam, 1971. MR**781929 (86m:03095a)****[HMT71]**-,*Cylindric algebras*, Part II, North-Holland, Amsterdam, 1985. MR**781930 (86m:03095b)****[J82]**Bjarni Jónsson,*Varieties of relation algebras*, Algebra Universalis**15**(1982), 273-298. MR**689767 (84g:08023)****[JT48]**Bjarni Jónsson and Alfred Tarski,*Representation problems for relation algebras*, Abstract 89, Bull. Amer. Math. Soc.**54**(1948), pp. 80 and 1192.**[JT51]**-,*Boolean algebras with operators*, Part I, Amer. J. Math.**73**(1951), 891-939. MR**0044502 (13:426c)****[JT52]**-,*Boolean algebras with operators*, Part II, Amer. J. Math.**74**(1952), 127-162. MR**0045086 (13:524g)****[K55]**John L. Kelley,*General topology*, Van Nostrand, London, 1955. Reprint by Springer-Verlag, New York, 1975. MR**0070144 (16:1136c)****[L50]**Roger C. Lyndon,*The representation of relational algebras*, Ann. of Math. (2)**51**(1950), 707-729. MR**0037278 (12:237a)****[L56]**-,*The representation of relation algebras*. II, Ann. of Math. (2)**63**(1956), 294-307. MR**0079570 (18:106f)****[L61]**-,*Relation algebras and projective geometries*, Michigan Math. J.**8**(1961), 21-28. MR**0122743 (23:A83)****[Ma78]**Roger D. Maddux,*Some sufficient conditions for the representability of relation algebras*, Algebra Universalis**8**(1978), 162-172. MR**0460210 (57:205)****[Ma78a]**-,*Topics in relation algebras*, Doctoral dissertation, Univ. of California, Berkeley, 1978, pp. iii+241.**[Ma81]**-,*The equational theory of**is undecidable*, J. Symbolic Logic**45**(1980), 311-316. MR**569401 (81e:03060)****[Ma82]**-,*Some varieties containing relation algebras*, Trans. Amer. Math. Soc.**272**(1982), 501-526. MR**662049 (84a:03079)****[Ma83]**-,*A sequent calculus for relation algebras*, Ann. Pure Appl. Logic**25**(1983), 73-101. MR**722170 (85h:03067)****[Ma89]**-,*Nonfinite axiomatizability results for cylindric and relation algebras*, J. Symbolic Logic**54**(1989), 951-974. MR**1011183 (90f:03099)****[MT76]**Roger D. Maddux and Alfred Tarski,*A sufficient condition for the representability of relation algebras*, Notices Amer. Math. Soc.**23**(1976), A-447.**[Me87]**Elliott Mendelson,*Introduction to mathematical logic*, 3rd ed., Wadsworth and Brooks/Cole, Monterey, 1987. MR**874751 (88b:03001)****[Mo64]**J. Donald Monk,*On representable relation algebras*, Michigan Math. J.**11**(1964), 207-210. MR**0172797 (30:3016)****[Mo70]**-,*Completions of Boolean algebras with operators*, Math. Nachr.**46**(1970), 47-55. MR**0277369 (43:3102)****[N85]**Istvan Németi,*Logic with**variables has Gödel's incompleteness property--thus free cylindric algebras are not atomic*, Ann. Pure Appl. Logic (submitted).**[N86]**-,*Free algebras and decidability in algebraic logic*, Doctoral dissertation, Hungarian Academy of Sciences, Budapest, 1986.**[P33]**Charles Sanders Peirce,*Collected papers*, Vol. III, edited by Charles Hartshorne and Paul Weiss, Harvard Univ. Press, Cambridge, 1933, pp. xiv+433. MR**0110632 (22:1508)****[S1895]**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.**[SS85]**Gunter Schmidt and Thomas Ströhlein,*Relation algebras*:*concept of points and representability*, Discrete Math.**54**(1985), 83-92.**[T41]**Alfred Tarski,*On the calculus of relations*, J. Symbolic Logic**6**(1941), 73-89. MR**0005280 (3:130e)****[T53]**-,*Some metalogical results concerning the calculus of relations*, J. Symbolic Logic**18**(1953), 188-189.**[T53a]**-,*A formalization of set theory without variables*, J. Symbolic Logic**18**(1953), 189.**[T55]**-,*Contributions to the theory of models*. III, Nederl. Akad. Wetensch. Proc. Ser. A Math. Sci.**58**(1955), 56-64. MR**0066303 (16:554h)****[TG87]**Alfred Tarski and Steven Givant,*A formalization of set theory without variables*, Colloq. Publ., vol. 41, Amer. Math. Soc., Providence, R.I., 1987. MR**920815 (89g:03012)****[WR 10]**Alfred North Whitehead and Bertrand Russell,*Principia mathematica*, Vol. I, Cambridge Univ. Press, 1910, pp. xv+666.

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
03G15,
08B99,
68Q99

Retrieve articles in all journals with MSC: 03G15, 08B99, 68Q99

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1991-1049616-1

Keywords:
Relation algebra,
semiassociative relation algebra,
representable,
completely representable,
associativity,
groupoid

Article copyright:
© Copyright 1991
American Mathematical Society