Inhalt

Grundlagen der Mathematik

Bezeichnungen

Elementarmathematik

Logik

Mengenlehre

Teilmengen

Mengenoperationen

Potenzmenge

Tupel und Produktmenge

Abbildungen

Gleichmächtigkeit

Permutationen

Relationen

Äquivalenzrelationen

Teilweise Ordnungen

Relationenalgebra

Mengenoperationen und

Relationsalgebra

Transitive Hülle

Zermelo-Fraenkel-

Mengenlehre

Multimengen

Differentialgleichungen

Funktionalanalysis

Differentialgeometrie

Anbieterkennzeichnung

Weiterbildung für alle! Über 200 Fernlehrgänge an Deutschlands größter Fernschule!

Relationsalgebra

Man kann die Eigenschaften von binären Relationen rein mengentheoretisch charakterisieren.

Definitionen

Identität

Wir bezeichnen mit die identische Relation oder Identität. Da in einer Matrixdarstellung nur die Hauptdiagonale besetzt ist, spricht man auch von eine Diagonalrelation.

Mit bezeichnen wir die leere Relation und mit , die Relation bei der alle Elemente miteinander in Beziehung stehen.

Transponierte Relation

Sei eine binäre Relation. Wir bezeichnen mit R^T = R^-1 die inverse Relation oder transponierte Relation genau wenn gilt

Die Bezeichnung transponierte Relation rührt daher, dass ihre Matrixdarstellung genau der transponierten Matrix entspricht.

Relationenprodukt

Sind R und S binäre Relationen auf A, so ist auch

und

eine binäre Relation. Sie heißt die Komposition oder das Relationenprodukt von R und S. Bei dieser Schreibweise ist die Reihenfolge genau umgekehrt zu der bei der Hintereinanderausführung von Abbildungen ist.

In Anlehnung an die Potenzschreibweise und .

Satz 9ANA (Rechenregeln der Relationsalgebra)

R^TT = R
(Assoziativität des Relationenproduktes)
(I ist neutrales Element des Relationenproduktes)

Beweis

(i):

(ii): .

(iii): , also a = c und damit . ebenso.

(iv): mit und mit und .

Satz 1729 (Algebraische Darstellung der Relationseigenschaften)

Sei eine binäre Relation. Dann gilt:

R ist reflexiv ,
R ist irreflexiv ,
R ist symmetrisch ,
R ist asymmetrisch ,
R ist antisymmetrisch ,
R ist transitiv , also .

Beweis

(i) R reflexiv : .

(ii) "": R irreflexiv bedeutet es gibt kein , aus diesen Paaren besteht aber genau I, also .

"" (indirekt): Sei nun und R nicht irreflexiv, also gibt es ein für dies gilt natürlich auch , also . Widerspruch, damit ist R irreflexiv.

(iii) R symmetrisch :

: R = R^T .

(iv) "" (indirekt): R asymmetrisch und , also gibt es ein (a, b) mit und , also , Widerspruch.

"" (indirekt): Sei und R nicht asymmetrisch, dann gibt es ein (a, b) mit und , also und . Widerspruch.

(v) Mit erhalten wir:

R antisymmetrisch

(vi) "": R sei transitiv und . Nach Definition gibt es mit und , da R transitiv ist also und damit

"": Sei und und , dann ist , also R transitiv.

Scherzhafte Beispiele haben manchmal größere Bedeutung als ernste.

Michael Stifel

Druckansicht

Impressum: Wurzelzieher Mathepedia • Thomas Steinfeld • Dorfplatz 25 • 17237 Blankensee • Tel.: 01734332309 (Vodafone/D2) • Email: matһе@wυrzеlzιeher.de

Amazon.de empfiehlt: