Relational algebra
In mathematics and abstract algebra is a relation algebra (English: relational algebra ) a residuierte Boolean algebra that an involution (as single digit operation ), called converse , has been expanded. The relevant example of a relational algebra for this concept formation is the algebra of all two-digit relations on a set (i.e. on the subsets of the Cartesian product ), together with the concatenation of relations and the inverse relation (converse relation).
definition
The following axioms are based on Givant (2006, p. 283), and were first established in 1948 by Alfred Tarski .
A relational algebra is a 9- tuple , for which applies:
- is a Boolean algebra with conjunction , disjunction and negation as well as zero element and unit element :
- is a monoid with its own element ,
- is an involution called a converse ,
- , d. H. the converse is true to the link ,
- ,
- ( Distributivity ) and
- , which means nothing else than (Peirce's law).
example
The homogeneous two-digit relations form the relation algebra
using the notations .
Peirce algebra
- A further development of this is the ( heterogeneous ) Peirce algebra , named after Charles Sanders Peirce - an abstract description of the relational algebra of homogeneous two-digit relations together with pre / post restrictions on sets.
See also
Individual references and comments
- ↑ a Boolean algebra whose association structure a residuierter Association 's (English: residuated algebra ), see: Marcel Erné: Algebraic lattice theory , Department of Algebra, Number Theory and Discrete Mathematics, University of Hannover
- ^ Alfred Tarski (1948) "Abstract: Representation Problems for Relation Algebras," Bulletin of the AMS 54: 80.
- ↑ Chris Brink et al. page 12
- ↑ According to Robin Hirsch, Ian Hodkinson: Relation algebras page 7, on: Third Indian Conference on Logic and its Applications (ICLA), 7. – 11. January 2009, Chennai, India. The tuple has been adjusted to the above definition.
- ↑ Of the links (one-digit) and (two-digit) - strictly speaking - the restrictions on or are meant.
literature
- Rudolf Carnap (1958) Introduction to Symbolic Logic and its Applications . Dover Publications.
- Steven Givant: The calculus of relations as a foundation for mathematics . In: Journal of Automated Reasoning . 37, 2006, pp. 277-322. doi : 10.1007 / s10817-006-9062-x .
- Halmos, PR , 1960. Naive Set Theory . Van Nostrand.
- Leon Henkin , Alfred Tarski , and Monk, JD, 1971. Cylindric Algebras, Part 1 , and 1985, Part 2 . North Holland.
- Hirsch R., and Hodkinson, I., 2002, Relation Algebra by Games , vol. 147 in Studies in Logic and the Foundations of Mathematics . Elsevier Science.
- Bjarni Jónsson, Constantine Tsinakis: Relation algebras as residuated Boolean algebras . In: Algebra Universalis . 30, 1993, pp. 469-78. doi : 10.1007 / BF01195378 .
- Roger Maddux: The Origin of Relation Algebras in the Development and Axiomatization of the Calculus of Relations, # 3-4 . In: Studia Logica . 50, 1991, pp. 421-455. doi : 10.1007 / BF00370681 .
- 2006. Relation Algebras , Vol. 150 in Studies in Logic and the Foundations of Mathematics . Elsevier Science.
- Patrick Suppes , 1960. Axiomatic Set Theory . Van Nostrand. Dover reprint, 1972. Chapter 3.
- Gunther Schmidt , 2010. Relational Mathematics . Cambridge University Press.
- Alfred Tarski : On the calculus of relations . In: Journal of Symbolic Logic . 6, 1941, pp. 73-89. doi : 10.2307 / 2268577 .
- Givant, Steven, 1987. A Formalization of Set Theory without Variables . Providence RI: American Mathematical Society.
Web links
- Relational Algebra (Mathepedia) (German)
- Yohji Akama, Yasuo Kawahara, Hitoshi Furusawa: Constructing Allegory from Relation Algebra and Representation Theorems "(WayBack)
- Richard Bird, Oege de Moor, Paul Hoogendijk: Generic Programming with Relations and Functors
- RP de Freitas, JP Viana: A Completeness Result for Relation Algebra with Binders
- Chris Brink, Katarina Britz, Renate A. Schmidt: Peirce Algebras