×

Relation algebras: Concept of points and representability. (English) Zbl 0575.03040

In the axiomatization of relation algebras by Chin and Tarski certain elements are called right ideals. Aiming at applications in the relational theory of graphs and programs, we call such ideals ’points’ and investigate an additional point axiom. First we prove a point insertion theorem. Then a representation theorem for such relation algebras is deduced by inherently relational methods, simplifying the proof of a similar result from Jónsson, Maddux and Tarski. Some historical remarks are inserted and an extended bibliography is added.

MSC:

03G15 Cylindric and polyadic algebras; relation algebras
06B15 Representation theory of lattices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] de Bakker, J. W.; de Roever, W. P., A calculus for recursive program schemes, (Nivat, M., Automata, Languages and Programming (1973), North-Holland: North-Holland Amsterdam), 167-196 · Zbl 0238.68006
[2] Bednarek, A. R.; Ulam, S. M., Generators for algebras of relations, Bull. Amer. Math. Soc., 82, 781-782 (1976) · Zbl 0342.02044
[3] Bednarek, A. R.; Ulam, S. M., Some remarks on relational composition in computational theory and practice, (Karpiński, M., Fundamentals of Computational Theory. Fundamentals of Computational Theory, Lecture Notes in Computer Science, 56 (1977), Springer: Springer Berlin), 22-32 · Zbl 0367.08012
[4] Bednarek, A. R.; Ulam, S. M., Projective algebra and the calculus of relations, J. Symbolic Logic, 43, 56-64 (1978) · Zbl 0388.03026
[5] Bernays, P., Über eine natürliche Erweiterung des Relationenkalküls, (Heyting, A., Constructivity in Mathematics (1959), North-Holland: North-Holland Amsterdam), 1-14 · Zbl 0087.00902
[6] Birkhoff, G., Lattice Theory (1967), Amer. Math. Soc: Amer. Math. Soc Providence, RI · Zbl 0126.03801
[7] Brink, C., The algebra of relatives, Notre Dame J. Formal Logic, 20, 900-908 (1979) · Zbl 0394.04002
[8] Brink, C., Two axiom systems for relation algebras, Notre Dame J. Formal Logic, 20, 909-914 (1979) · Zbl 0394.03059
[9] Chin, L. H.; Tarski, A., Remarks on projective algebras, Bull. Amer. Math. Soc., 54, 80-81 (1948), (Abstract 90)
[10] Chin, L. H.; Tarski, A., Distributive and modular laws in the arithmetic of relation algebras, Univ. California Publ. Math., 1, 341-384 (1951)
[11] Copilowish, I. M., Matrix development of the calculus of relations, J. Symbolic Logic, 13, 193-203 (1948) · Zbl 0035.00503
[12] Everett, C. J.; Ulam, S., Projective algebra I, Amer. J. Math., 68, 77-88 (1946) · Zbl 0060.06307
[13] Gericke, H., Theorie der Verbände (1963), Bibliographisches Institut: Bibliographisches Institut Mannheim · Zbl 0124.25503
[14] Give’on, Y., Lattice matrices, Inform. and Control, 7, 477-484 (1952) · Zbl 0154.01103
[15] Harary, F., On complete atomic proper relation algebras, J. Symbolic Logic, 15, 197-198 (1950) · Zbl 0037.29401
[16] Henkin, L.; Monk, J. D.; Tarski, A.; Andréka, H.; Németi, I., Cylindric Set Algebras, (Lecture Notes in Mathematics, 883 (1981), Springer: Springer Berlin) · Zbl 0497.03025
[17] Howorka, E., Generators for algebras of relations, Notices Amer. Math. Soc., 24, A-4-A-5 (1977)
[18] Huntington, E. V., New sets of independent postulates for the algebra of logic, with special reference to Whitehead and Russel’s Principia Mathematica, Trans. Amer. Math. Soc., 35, 557-558 (1933) · JFM 59.0051.01
[19] Jónsson, B., Representation of modular lattices and of relation algebras, Trans. Amer. Math. Soc., 92, 449-464 (1959) · Zbl 0105.25302
[20] Jónsson, B.; Tarski, A., Boolean algebras with operators, Amer. J. Math., 74, 127-162 (1952), Part II · Zbl 0045.31601
[21] Jónsson, B., Extensions of relational structures, (Addison, J. W.; Henkin, L.; Tarski, A., The Theory of Models (1970), North-Holland: North-Holland Amsterdam), 146-157 · Zbl 0158.26301
[22] Kalicki, J.; Scott, D., Equational completeness of abstract algebras, Indag. Math., 17, 650-659 (1955) · Zbl 0073.24501
[23] Kamel, H., Relational algebra and uniform spaces, J. London Math. Soc., 29, 342-344 (1954) · Zbl 0059.01502
[24] Lorenzen, P., Über die Korrespondenzen einer Struktur, Math. Z., 60, 61-65 (1954) · Zbl 0055.02302
[25] Löwenheim, L., Über Möglichkeiten im Relativkalkül, Math. Ann., 76, 447-470 (1915) · JFM 44.0078.01
[26] Luce, R. D., A note on Boolean matrix theory, (Proc. Amer. Math. Soc., 3 (1952)), 382-388 · Zbl 0048.02302
[27] Lyndon, R. C., The representation of relational algebras, Ann. of Math. (2), 51, 707-729 (1950) · Zbl 0037.29302
[28] Lyndon, R. C., The representation of relation algebras, II, Ann. of Math. (2), 63, 294-307 (1956) · Zbl 0070.24601
[29] Lyndon, R. C., Relation algebras and projective geometries, Michigan Math. J., 8, 21-28 (1961) · Zbl 0105.25303
[30] Maddux, R., Some sufficient conditions for the representability of relation algebras, Algebra Universalis, 8, 162-172 (1978) · Zbl 0386.03033
[31] Maddux, R., Embedding modular lattices into relation algebras, Algebra Universalis, 12, 242-246 (1981) · Zbl 0415.06010
[32] Maddux, R.; Tarski, A., A sufficient condition for the representability of relation algebras, Notices Amer. Math. Soc., 23, A-477 (1976)
[33] McKenzie, R., Representations of integral relation algebras, Michigan Math. J., 17, 279-287 (1970) · Zbl 0191.01102
[34] McKinsey, J. C.C., Postulates for the calculus of binary relations, J. Symbolic Logic, 5, 85-97 (1940) · Zbl 0024.00201
[35] McKinsey, J. C.C., On the representation of projective algebras, Amer. J. Math., 70, 375-384 (1948) · Zbl 0035.01801
[36] Michael, E., A note on Peirce on Boole’s algebra of logic, Notre Dame J. Formal Logic, 20, 636-638 (1979) · Zbl 0415.03001
[37] Monk, J. D., Relation algebras and cylindric algebras, Notices Amer. Math. Soc., 8, 358 (1961)
[38] Monk, J. D., On representable relation algebras, Michigan Math. J., 11, 207-210 (1964) · Zbl 0137.00603
[39] Monk, J. D., Completions of Boolean algebras with operators, Math. Nach., 46, 47-55 (1970) · Zbl 0182.32301
[40] Ono, K., On some properties of binary relations, Nagoya Math. J., 12, 161-170 (1957) · Zbl 0079.07702
[41] Ribeiro, H., A remark on Boolean algebras with operators, Amer. J. Math., 74, 163-167 (1952) · Zbl 0045.31602
[42] Riguet, J., Relations binaires, fermetures, correspondances de Galois, Bull. Soc. Math. France, 76, 114-155 (1948) · Zbl 0033.00603
[43] Riguet, J., Sur l’extensions du calcul des relations binaires au calcul des matrices à éléments dans une algèbre de Boole complète, C.R. Acad. Sci. Paris Sér. A-B, 238, 2382-2385 (1954) · Zbl 0056.02805
[44] Schein, B. M., Relation algebras, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., 13, 1-5 (1965) · Zbl 0151.00701
[45] Schmidt, G., Programs as partial graphs I: Flow equivalence and correctness, Theoret. Comput. Sci., 15, 1-25 (1981) · Zbl 0493.68015
[46] G. Schmidt and T. Ströhlein, Relationen, Graphen und Programme, in preparation.; G. Schmidt and T. Ströhlein, Relationen, Graphen und Programme, in preparation.
[47] Schmidt, G.; Ströhlein, T., A Boolean matrix iteration in timetable construction, Linear Algebra Appl., 15, 27-51 (1976) · Zbl 0358.94049
[48] Schmidt, G.; Ströhlein, T., Kernels in bipartite graphs, (Schneider, H. J.; Göttler, H., Proc. 8th Conf. on Graphtheoretic Concepts in Computer Science (WG 82) (1982), Hanser: Hanser München), 251-256 · Zbl 0581.05026
[49] Schönfeld, W., An undecidability result for relation algebras, J. Symbolic Logic, 44, 111-115 (1979) · Zbl 0407.03019
[50] Schröder, E., (Algebra der Logik, 3. Band (1895), Teubner: Teubner Leipzig)
[51] Sobociński, B., Equational two axiom bases for Boolean algebras and some other lattice theories, Notre Dame J. Formal Logic, 20, 865-875 (1979) · Zbl 0437.06001
[52] Stone, M. H., The theory of representations for Boolean algebras, Trans. Amer. Math. Soc., 40, 37-111 (1936) · Zbl 0014.34002
[53] Tarski, A., On the calculus of relations, J. Symbolic Logic, 6, 73-89 (1941) · JFM 67.0973.02
[54] Tarski, A., Some metalogical results concerning the calculus of relations, J. Symbolic Logic, 18, 188-189 (1953)
[55] Tarski, A., Contributions to the theory of models. III, Indag. Math., 17, 56-64 (1955)
[56] Tarski, A., Equationally complete rings and relation algebras, Indag. Math., 18, 39-41 (1956) · Zbl 0073.24603
[57] Veloso, P. A.S., The history of an error in the theory of representations of relation algebras, J. Symbolic Logic, 44, 466 (1979) · Zbl 0411.68067
[58] Wiener, N., A simplification of the logic of relations, (van Heijenoort, J., From Frege to Gödel (1967), Harvard Univ. Press: Harvard Univ. Press Cambridge, MA), 224-227 · JFM 50.0335.02
[59] Wooyenaka, Y., On postulate-sets for relation algebras, Notices Amer. Math. Soc., 6, 534-535 (1959)
[60] Wostner, U., Finite relation algebras, Notices Amer. Math. Soc., 23, A-482 (1976)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.