Reflexive Relation

Drei reflexive Relationen, als gerichtete Graphen dargestellt

Die Reflexivität einer zweistelligen Relation ${\displaystyle R}$ auf einer Menge ist gegeben, wenn ${\displaystyle xRx}$ für alle Elemente ${\displaystyle x}$ der Menge gilt, also jedes Element in Relation zu sich selbst steht. Man nennt ${\displaystyle R}$ dann reflexiv.

Eine Relation heißt irreflexiv, wenn die Beziehung ${\displaystyle xRx}$ für kein Element ${\displaystyle x}$ der Menge gilt, also kein Element in Relation zu sich selbst steht. Es gibt auch Relationen, die weder reflexiv noch irreflexiv sind, wenn die Beziehung ${\displaystyle xRx}$ für einige Elemente ${\displaystyle x}$ der Menge gilt, doch nicht für alle.

Die Reflexivität ist eine der Voraussetzungen für eine Äquivalenzrelation oder eine Ordnungsrelation; die Irreflexivität ist eine der Voraussetzungen für eine strikte Ordnungsrelation.

Formale Definition

Ist ${\displaystyle M}$ eine Menge und ${\displaystyle R\subseteq M\times M}$ eine zweistellige Relation auf ${\displaystyle M}$, dann definiert man (unter Verwendung der Infixnotation):

${\displaystyle R}$ ist reflexiv :${\displaystyle \Longleftrightarrow \forall x\in M:xRx}$

${\displaystyle R}$ ist irreflexiv :${\displaystyle \Longleftrightarrow \forall x\in M:\neg \ xRx}$

Beispiele

Reflexiv

• Die Kleiner-Gleich-Relation ${\displaystyle \leq }$ auf den reellen Zahlen ist reflexiv, da stets ${\displaystyle x\leq x}$ gilt. Sie ist darüber hinaus eine Totalordnung. Gleiches gilt für die Relation ${\displaystyle \geq }$.

• Die gewöhnliche Gleichheit ${\displaystyle =}$ auf den reellen Zahlen ist reflexiv, da stets ${\displaystyle x=x}$ gilt. Sie ist darüber hinaus eine Äquivalenzrelation.

• Die Teilmengenbeziehung ${\displaystyle \subseteq }$ zwischen Mengen ist reflexiv, da stets ${\displaystyle A\subseteq A}$ gilt. Sie ist darüber hinaus eine Halbordnung.

Irreflexiv

• Die Kleiner-Relation ${\displaystyle <}$ auf den reellen Zahlen ist irreflexiv, da nie ${\displaystyle x<x}$ gilt. Sie ist darüber hinaus eine strenge Totalordnung. Gleiches gilt für die Relation ${\displaystyle >}$.

• Die Ungleichheit ${\displaystyle \neq }$ auf den reellen Zahlen ist irreflexiv, da nie ${\displaystyle x\neq x}$ gilt.

• Die echte Teilmengenbeziehung ${\displaystyle \subset }$ zwischen Mengen ist irreflexiv, da nie ${\displaystyle A\subset A}$ gilt. Sie ist darüber hinaus eine strenge Halbordnung.

Weder reflexiv noch irreflexiv

Die folgende Relation auf der Menge der reellen Zahlen ist weder reflexiv noch irreflexiv:

${\displaystyle xRy:\Longleftrightarrow y=x^{2}}$

Grund: Für ${\displaystyle x:=1}$ gilt ${\displaystyle xRx}$, für ${\displaystyle x:=2}$ gilt ${\displaystyle \neg xRx}$.

Darstellung als gerichteter Graph

Jede beliebige Relation ${\displaystyle R}$ auf einer Menge ${\displaystyle M}$ kann als gerichteter Graph aufgefasst werden (siehe Beispiel im Bild oben). Die Knoten des Graphen sind dabei die Elemente von ${\displaystyle M}$. Vom Knoten ${\displaystyle a}$ zum Knoten ${\displaystyle b}$ wird genau dann eine gerichtete Kante (ein Pfeil ${\displaystyle a\longrightarrow b}$) gezogen, wenn ${\displaystyle aRb}$ gilt.

Die Reflexivität von ${\displaystyle R}$ lässt sich im Graphen nun so charakterisieren: Für jeden Knoten ${\displaystyle a}$ gibt es eine Schleife ${\displaystyle {\stackrel {a}{\circlearrowright }}}$. Entsprechend ist die Irreflexivität dadurch gegeben, dass es für keinen Knoten ${\displaystyle a}$ eine Schleife ${\displaystyle {\stackrel {a}{\circlearrowright }}}$ gibt.

Eigenschaften

• Mit Hilfe der identischen Relation ${\displaystyle Id_{M}}$ (die aus allen Paaren ${\displaystyle (x,x)}$ besteht) kann man die Begriffe auch so charakterisieren:

  ${\displaystyle R}$ ist reflexiv ${\displaystyle \Longleftrightarrow Id_{M}\subseteq R}$

  ${\displaystyle R}$ ist irreflexiv ${\displaystyle \Longleftrightarrow Id_{M}\cap R=\varnothing }$

• Ist die Relation ${\displaystyle R}$ reflexiv bzw. irreflexiv, dann gilt dies auch für die konverse Relation ${\displaystyle R^{-1}}$. Beispiele: die zu ${\displaystyle \leq }$ konverse Relation ist ${\displaystyle \geq }$, die zu ${\displaystyle <}$ konverse ist ${\displaystyle >}$.

• Ist die Relation ${\displaystyle R}$ reflexiv, dann ist die komplementäre Relation ${\displaystyle R^{\rm {c}}}$ irreflexiv. Ist ${\displaystyle R}$ irreflexiv, dann ist ${\displaystyle R^{\rm {c}}}$ reflexiv. Dabei ist die komplementäre Relation definiert durch

  ${\displaystyle xR^{\rm {c}}y:\Longleftrightarrow \neg xRy}$.

• Die Relation auf der leeren Menge ist als einzige Relation sowohl reflexiv als auch irreflexiv.

Siehe auch

• Reflexive Hülle
• Nichtsättigungsaxiom
• Reflexiv-transitive Hülle