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

Eigenschaften homogener Relationen

Im Folgenden sei $R$ eine homogene Relation auf der Grundmenge $A$ , also $R\subseteq A\times A$ .

Eigenschaft	Definition	Definition in formaler Schreibweise	Merkmale
reflexiv	Jedes Objekt der Grundmenge steht mit sich selbst in Relation.	$\forall a\in A:aRa$	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	$\forall a\in A:\neg aRa$	Im Pfeildiagramm steht kein Objekt mit sich selbst in Relation. In der Relationsmatrix ist die Hauptdiagonale komplett unbesetzt.
symmetrisch	Steht ein Objekt $a$ in Relation mit dem Objekt $b$ , dann steht auch $b$ in Relation mit $a$	$\forall a,b\in A:aRb\implies bRa$	Im Pfeildiagramm sind alle Objekte mit Doppelpfeilen verbunden. Die Relationsmatrix ist symmetrisch zur Hauptdiagonale
antisymmetrisch	Zwei verschiedene Objekte $a$ und $b$ stehen nicht gegenseitig in Relation zueinander.	$\forall a,b\in A:aRb\land bRa\implies a=b$	Im Pfeildiagramm sind keine Objekte mit Doppelpfeilen verbunden. Die Relationsmatrix ist komplementär zu Hauptdiagonale.
asymmetrisch	Steht $a$ und $b$ in Relation, dann steht nicht $b$ mit $a$ in Relation.	$\forall a,b\in A:aRb\implies \neg bRa$	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 $a$ mit $b$ und $b$ mit $c$ in Relation, dann steht auch $a$ mit $c$ in Relation.	$\forall a,b,c\in A:aRb\land bRc\implies aRc$	Im Pfeildiagramm gibt es immer eine Abkürzung (kannst du über Pfeile von Objekt $a$ über $b$ nach Objekt $c$ wandern, wobei du immer die Pfeilrichtung verfolgst, so gibt es einen direkten Pfeil von $a$ nach $c$ ).
linear oder total oder vollständig	Für jeweils zwei Objekte $a$ und $b$ stehen $a$ mit $b$ und/oder $b$ mit $a$ in Relation.	$\forall a,b\in A:aRb\lor bRa$	Im Pfeildiagramm gibt es zwischen zwei Objekten jeweils eine Verbindung.
konnex^[1] oder verbunden	Für jeweils zwei verschiedene Objekte $a$ und $b$ stehen $a$ mit $b$ und/oder $b$ mit $a$ in Relation.	$\forall a,b\in A:a\neq b\implies aRb\lor bRa$	Im Pfeildiagramm gibt es zwischen zwei verschiedenen Objekten jeweils eine Verbindung.
trichotom	Für alle $a$ und $b$ gilt genau einer der 3 Fälle: $aRb$ , $a=b$ oder $bRa$ .	$\forall a,b\in A:aRb\,{\dot {\lor }}\,a=b\,{\dot {\lor }}\,bRa$	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?

„ $x$ ist kleiner als $y$ “ für $x,y\in \mathbb {N}$
„ $x$ ist kleiner oder gleich $y$ “ für $x,y\in \mathbb {N}$
„ $x$ ist ein Teiler von $y$ “ für $x,y\in \mathbb {N}$
„ $x$ und $y$ sind ganze Zahlen“ für $x,y\in \mathbb {N}$
„ $x$ und $y$ sind ganze Zahlen“ für $x,y\in \mathbb {R}$

Relation	reflexiv	irreflexiv	symmetrisch	antisymmetrisch	asymmetrisch	transitiv	linear	konnex	trichotom
„ $x$ ist kleiner als $y$ “ für $x,y\in \mathbb {N}$		X		X	X	X		X	X
„ $x$ ist kleiner oder gleich $y$ “ für $x,y\in \mathbb {N}$	X			X		X	X	X
„ $x$ ist ein Teiler von $y$ “ für $x,y\in \mathbb {N}$	X			X		X
„ $x$ und $y$ sind ganze Zahlen“ für $x,y\in \mathbb {N}$	X		X			X	X	X
„ $x$ und $y$ sind ganze Zahlen“ für $x,y\in \mathbb {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 „ $x$ und $y$ sind gerade Zahlen“ auf der Menge $\{1,2,3,4\}$ mit der Relationsmatrix

	2	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 „ $x$ ist kleiner gleich 2 und $y$ ist beliebig“ auf der Menge $\{1,2,3,4\}$ 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 steht sowohl $1$ mit $2$ als auch $2$ mit $1$ in Relation zueinander. Deswegen ist die Relation nicht antisymmetrisch.

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

Sei $R$ eine lineare Relation über der Grundmenge $M$ . Dann gilt $\forall a\in M\,\forall b\in M:aRb\lor bRa$ . Damit gilt insbesondere auch $\forall a\in M:aRa\lor aRa$ und damit $\forall a\in M:aRa$ . Dies ist aber gerade die Definition der Reflexivität. Also ist jede lineare Relation reflexiv.

Zusammenhänge zwischen den Eigenschaften

Zwischen den Eigenschaften gibt es folgende Zusammenhänge:

[1]