Relationsalgebra

I matematik og abstrakt algebra er en relation algebra (engelsk: relationel algebra ) en residuierte boolsk algebra, som en involution (som encifret operation ), kaldet omvendt , er blevet udvidet. Det relevante eksempel på en relationel algebra til denne konceptdannelse er algebraen for alle to-cifrede relationer på et sæt (dvs. på delmængderne af det kartesiske produkt ) sammen med sammenkædningen af ​​relationer og det omvendte forhold. ${\ displaystyle 2 ^ {A ^ {2}} = {\ mathcal {P}} (A \ gange A)}$${\ displaystyle A}$${\ displaystyle A \ gange A = A ^ {2}}$

definition

De følgende aksiomer er baseret på Givant (2006, s. 283) og blev først etableret i 1948 af Alfred Tarski .

En relationel algebra er en 9- tuple , for hvilken der gælder: ${\ displaystyle (L, \ land, \ lor, \ neg, 0,1, \ circ, \ mathrm {I}, {} ^ {\ smile})}$

• ${\ displaystyle (L, \ land, \ lor, \ neg, 0,1)}$er en boolsk algebra med konjunktion , disjunktion og negation samt nul element og enhedselement :${\ displaystyle \ land}$${\ displaystyle \ lor}$${\ displaystyle \ neg}$${\ displaystyle 0}$${\ displaystyle 1}$
• ${\ displaystyle (L, \ circ, \ mathrm {I})}$er en monoid med sit eget enkelt element ,${\ displaystyle \ mathrm {I}}$
• ${\ displaystyle {} ^ {\ smile}}$er en involution kaldet en omvendt ,
• ${\ displaystyle \ forall a, b \ i {L} :( a \ circ b) ^ {\ smile} = b ^ {\ smile} \ circ a ^ {\ smile}}$, d. H. det omvendte er tro mod linket ,${\ displaystyle \ circ}$
• ${\ displaystyle \ forall a, b \ i {L} :( a \ lor b) ^ {\ smile} = a ^ {\ smile} \ lor b ^ {\ smile}}$,
• ${\ displaystyle \ forall a, b, c \ i {L} :( a \ lor b) \ circ {c} = (a \ circ {c}) \ lor (b \ circ {c})}$( Distributivitet ) og
• ${\ displaystyle \ forall a, b \ i {L} :( a ^ {\ smile} \ circ \ neg (a \ circ {b})) \ lor \ neg {b} = \ neg {b}}$, hvilket ikke betyder andet end (Peirces lov).${\ displaystyle a \ circ {b} \ leq \ neg {c} \ Leftrightarrow a ^ {\ smile} \ circ c \ leq \ neg {b} \ Leftrightarrow c \ circ b ^ {\ smile} \ leq \ neg { en}}$
  

  Illustration af Peirces lov, her med u, v, w i stedet for a, b, c

eksempel

De homogene tocifrede relationer danner forholdets algebra ${\ displaystyle R \ subseteq A \ gange A}$

${\ displaystyle {\ mathfrak {Re}} (A) = (2 ^ {A ^ {2}}, \ cap, \ cup, {} ^ {^ {-}}, \ emptyset, A ^ {2}, \ circ, \ mathrm {I} _ {A}, {} ^ {\ smile})}$ 

ved hjælp af notationerne .${\ displaystyle A ^ {2} = A \ gange A, \ \; \ 2 ^ {A ^ {2}} = {\ mathcal {P}} (A \ gange A)}$

Peirce algebra

• En yderligere udvikling af dette er den ( heterogene ) Peirce-algebra , opkaldt efter Charles Sanders Peirce - en abstrakt beskrivelse af den relationelle algebra af homogene tocifrede relationer sammen med præ / post-begrænsninger på sæt.${\ displaystyle {\ mathfrak {Re}} (A)}$

Se også

• Boolsk algebra
• Heyting algebra

Individuelle referencer og kommentarer

1. ↑ en boolsk algebra, hvis associeringsstruktur en residuierter Association (se engelsk: residuated algebra ), se: Marcel Erné: Algebraisk gitterteori , Institut for Algebra, Talteori og diskret matematik, University of Hannover
2. ^ Alfred Tarski (1948) "Abstract: Repræsentationsproblemer for forholdsalgebras," Bulletinen i AMS 54: 80.
3. ↑ Chris Brink et al. side 12
4. ↑ Ifølge Robin Hirsch, Ian Hodkinson: Relation algebras side 7, om: Third Indian Conference on Logic and its Applications (ICLA), 7. - 11. Januar 2009, Chennai, Indien. Tuplen er tilpasset ovenstående definition.
5. ↑ Af linkene (et-cifret) og (to-cifret) - strengt taget - begrænsningerne for eller menes.${\ displaystyle {} ^ {^ {-}}, {} ^ {\ smile}}$${\ displaystyle \ cap, \ cup, \ circ}$${\ displaystyle A}$${\ displaystyle A ^ {2}}$

litteratur

• Rudolf Carnap : Introduktion til symbolsk logik og dens anvendelser. Dover Publications, 1958.
• Steven Givant: Calculus of relations som et fundament for matematik . I: Journal of Automated Reasoning . bånd 37 , 2006, s. 277-322 , doi : 10.1007 / s10817-006-9062-x . 
• PR Halmos : Naiv sætteori . Van Nostrand, 1960.
• Leon Henkin , Alfred Tarski , JD Monk: Cylindric Algebras. Del 1, 1971 og Del 2, 1985, Nordholland.
• R. Hirsch, I. Hodkinson: Relationsalgebra af spil . (= Undersøgelser i logik og matematikens fundamenter . Bind 147). Elsevier Science, 2002, ISBN 0-444-50932-1 .
• Bjarni Jónsson, Constantine Tsinakis: Relationsalgebraer som resterede boolske algebraer . I: Algebra Universalis . bånd 30 , 1993, s. 469-478 , doi : 10.1007 / BF01195378 . 
• Roger Maddux: Oprindelsen af ​​relationsalgebras i udviklingen og aksiomatiseringen af ​​relationen . I: Studia Logica . bånd 50 , nr. 3-4 , 1991, s. 421-455 , doi : 10.1007 / BF00370681 ( iastate.edu [PDF]). 
• Roger D Maddux: Relationsalgebras. (= Undersøgelser i logik og grundlaget for matematik. Bind 150). Elsevier Science, 2006, ISBN 1-280-64163-0 .
• Patrick Suppes : Axiomatic Set Theory . Van Nostrand. Dover 1972, kapitel 3.
• Gunther Schmidt : Relational Mathematics. Cambridge University Press, 2010.
• Alfred Tarski: Om beregningen af ​​relationer . I: Journal of Symbolic Logic . bånd 6 , 1941, s. 73-89 , doi : 10.2307 / 2268577 . 
• Steven Givant: En formalisering af sætteori uden variabler. American Mathematical Society, Providence RI 1987, ISBN 0-8218-1041-3 .

Weblinks

• Relational Algebra (Mathepedia) (tysk)
• Yohji Akama, Yasuo Kawahara, Hitoshi Furusawa: Constructing Allegory from Relation Algebra and Representation Theorems "(WayBack)
• Richard Bird, Oege de Moor, Paul Hoogendijk: Generisk programmering med relationer og funktorer
• RP de Freitas, JP Viana: Et fuldstændighedsresultat for relationalgebra med bindemidler
• Chris Brink, Katarina Britz, Renate A. Schmidt: Peirce Algebras

• Peter Jipsen :
  • Forhold algebras (WayBack)
  • Grundlaget for relationer og Kleene Algebra
  • Computerstøttede undersøgelser af forholdsalgebras
  • Et Gentzen-system og beslutsomhed for berolige gitter

• Vaughan Pratt :
  • Oprindelsen af ​​beregningen af ​​binære relationer.
  • Den anden beregning af binære relationer.

• Uta Priss :
  • En FCA-fortolkning af Relation Algebra
  • Relationsalgebra og FCA

• Wolfram Kahl , Gunther Schmidt
  • Udforskning af (endelige) relationsalgebras ved hjælp af værktøjer skrevet i Haskell
  • RATH - Relationsalgebraværktøjer i Haskell