Reflexive Relation

Drei reflexive Relationen, als gerichtete Graphen dargestellt

Die Reflexivität einer zweistelligen Relation <math>R</math> auf einer Menge ist gegeben, wenn <math>x R x</math> für alle Elemente <math>x</math> der Menge gilt, also jedes Element in Relation zu sich selbst steht. Man nennt <math>R</math> dann reflexiv.

Eine Relation heißt irreflexiv, wenn die Beziehung <math>x R x</math> für kein Element <math>x</math> 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 <math>x R x</math> für einige Elemente <math>x</math> 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 <math>M</math> eine Menge und <math>R \subseteq M \times M</math> eine zweistellige Relation auf <math>M</math>, dann definiert man (unter Verwendung der Infixnotation)<ref>reflexive relation, Eintrag im nLab. (englisch)</ref>:

<math>R</math> ist reflexiv :<math>\Longleftrightarrow \forall x \in M: xRx</math>

<math>R</math> ist irreflexiv :<math>\Longleftrightarrow \forall x \in M: \neg \ xRx</math>

Beispiele

Reflexiv

Die Kleiner-Gleich-Relation <math>\le</math> auf den reellen Zahlen ist reflexiv, da stets <math>x \le x</math> gilt. Sie ist darüber hinaus eine Totalordnung. Gleiches gilt für die Relation <math>\ge</math>.

Die gewöhnliche Gleichheit <math>=</math> auf den reellen Zahlen ist reflexiv, da stets <math>x=x</math> gilt. Sie ist darüber hinaus eine Äquivalenzrelation.

Die Teilmengenbeziehung <math>\subseteq</math> zwischen Mengen ist reflexiv, da stets <math>A\subseteq A</math> gilt. Sie ist darüber hinaus eine Halbordnung.

Irreflexiv

Die Kleiner-Relation <math><</math> auf den reellen Zahlen ist irreflexiv, da nie <math>x<x</math> gilt. Sie ist darüber hinaus eine strenge Totalordnung. Gleiches gilt für die Relation <math>></math>.

Die Ungleichheit <math>\ne</math> auf den reellen Zahlen ist irreflexiv, da nie <math>x\ne x</math> gilt.

Die echte Teilmengenbeziehung <math>\subset</math> zwischen Mengen ist irreflexiv, da nie <math>A\subset A</math> 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:

<math>xRy :\Longleftrightarrow y = x^2</math>

Grund: Für <math>x:=1</math> gilt <math>xRx</math>, für <math>x:=2</math> gilt <math>\neg xRx</math>.

Darstellung als gerichteter Graph

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

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

Eigenschaften

Mit Hilfe der identischen Relation <math>Id_M</math> (die aus allen Paaren <math>(x, x)</math> besteht) kann man die Begriffe auch so charakterisieren:
<math>R</math> ist reflexiv <math>\Longleftrightarrow Id_M \subseteq R</math>

<math>R</math> ist irreflexiv <math>\Longleftrightarrow Id_M \cap R = \varnothing</math>

Ist die Relation <math>R</math> reflexiv bzw. irreflexiv, dann gilt dies auch für die konverse Relation <math>R^{-1}</math>. Beispiele: die zu <math>\le</math> konverse Relation ist <math>\ge</math>, die zu <math><</math> konverse ist <math>></math>.

Ist die Relation <math>R</math> reflexiv, dann ist die komplementäre Relation <math>R^{\rm c}</math> irreflexiv. Ist <math>R</math> irreflexiv, dann ist <math>R^{\rm c}</math> reflexiv. Dabei ist die komplementäre Relation definiert durch
<math>x R^{\rm c} y :\Longleftrightarrow \neg x R y</math>.

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

Siehe auch

Einzelnachweise