Eigenschaften binärer Relationen – Serlo „Mathe für Nicht-Freaks“

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Eigenschaften homogener Relationen[Bearbeiten]

Im Folgenden sei eine homogene Relation auf der Grundmenge , also .

Eigenschaft Definition Definition in formaler Schreibweise Merkmale
reflexiv Jedes Objekt der Grundmenge steht mit sich selbst in Relation.
  • Im Pfeildiagramm ist jedes Objekt mit sich selbst verbunden.
  • In der Relationsmatrix ist die Hauptdiagonale voll besetzt.
irreflexiv Es gibt kein Objekt, welches mit sich selbst in Relation steht
  • Im Pfeildiagramm steht kein Objekt mit sich selbst in Relation.
  • In der Relationsmatrix ist die Hauptdiagonale komplett unbesetzt.
symmetrisch Steht ein Objekt in Relation mit dem Objekt , dann steht auch in Relation mit
  • Im Pfeildiagramm sind alle Objekte mit Doppelpfeilen verbunden.
  • Die Relationsmatrix ist symmetrisch zur Hauptdiagonale
antisymmetrisch Zwei verschiedene Objekte und stehen nicht gegenseitig in Relation zueinander.
  • Im Pfeildiagramm sind keine Objekte mit Doppelpfeilen verbunden.
  • Die Relationsmatrix ist komplementär zu Hauptdiagonale.
asymmetrisch Steht und in Relation, dann steht nicht mit in Relation.
  • Eine Relation ist genau dann asymmetrisch, wenn sie irreflexiv und antisymmetrisch ist.
  • Im Pfeildiagramm sind keine Objekte mit Doppelpfeilen verbunden und keine Objekte sind mit sich selbst verbunden.
  • Die Relationsmatrix ist komplementär zu Hauptdiagonale und besitzt keine Einträge in der Hauptdiagonalen.
transitiv Steht mit und mit in Relation, dann steht auch mit in Relation.
  • Im Pfeildiagramm gibt es immer eine Abkürzung (kannst du über Pfeile von Objekt über nach Objekt wandern, wobei du immer die Pfeilrichtung verfolgst, so gibt es einen direkten Pfeil von nach ).
linear oder total oder vollständig Für jeweils zwei Objekte und stehen mit und/oder mit in Relation.
  • Im Pfeildiagramm gibt es zwischen zwei Objekten jeweils eine Verbindung.
konnex[1] oder verbunden Für jeweils zwei verschiedene Objekte und stehen mit und/oder mit in Relation.
  • Im Pfeildiagramm gibt es zwischen zwei verschiedenen Objekten jeweils eine Verbindung.
trichotom Für alle und gilt genau einer der 3 Fälle: , oder .
  • Eine Relation ist genau dann trichotom, wenn sie asymmterisch und konnex ist.
  • Im Pfeildiagramm ist kein Objekt mit sich selbst verbunden und zwischen je zwei verschiedenen Objekten gibt es genau einen Pfeil.

Verständnisfrage: Welche Eigenschaften haben die folgenden Relationen?

  • ist kleiner als “ für
  • ist kleiner oder gleich “ für
  • ist ein Teiler von “ für
  • und sind ganze Zahlen“ für
  • und sind ganze Zahlen“ für

Relation reflexiv irreflexiv symmetrisch antisymmetrisch asymmetrisch transitiv linear konnex trichotom
ist kleiner als “ für X X X X X X
ist kleiner oder gleich “ für X X X X X
ist ein Teiler von “ für X X X
und sind ganze Zahlen“ für X X X X X
und sind ganze Zahlen“ für X X

Verständnisfrage: Ist jede nicht reflexive Relation irreflexiv? Wieso?

Es gibt Relationen, die weder reflexiv noch irreflexiv sind. Ein Beispiel hierfür ist die Relation „ und sind gerade Zahlen“ auf der Menge mit der Relationsmatrix

1 2 3 4
1
2 X X
3
4 X X

Verständnisfrage: Ist jede nicht symmetrische Relation antisymmetrisch? Wieso?

Es gibt Relationen, die weder symmetrisch noch antisymmetrisch sind. Ein Beispiel hierfür ist die Relation „ ist kleiner gleich 2 und ist beliebig“ auf der Menge mit der Relationsmatrix

1 2 3 4
1 X X X X
2 X X X X
3
4

Diese Relation ist weder symmetrisch noch antisymmetrisch. Die Relationsmatrix ist nämlich nicht symmetrisch mit der Hauptdiagonalen und damit ist die Relation nicht symmetrisch. Auch ist steht sowohl mit als auch mit in Relation zueinander. Deswegen ist die Relation nicht antisymmetrisch.

Verständnisfrage: Ist jede lineare Relation reflexiv? Wieso?

Sei eine lineare Relation über der Grundmenge . Dann gilt . Damit gilt insbesondere auch und damit . Dies ist aber gerade die Definition der Reflexivität. Also ist jede lineare Relation reflexiv.

Zusammenhänge zwischen den Eigenschaften[Bearbeiten]

Zwischen den Eigenschaften gibt es folgende Zusammenhänge:

Zusammenhänge zwischen den Eigenschaften binärer Relationen