Relation

Eine Relation ${\displaystyle R}$ zwischen zwei Mengen ${\displaystyle A}$ und ${\displaystyle B}$ ist eine Teilmenge des kartesischen Produktes ${\displaystyle A\times B}$, also ${\displaystyle R\ \subseteq A\times B}$. Für ${\displaystyle (x,y)\in R}$ schreibt man auch kurz ${\displaystyle xRy}$ (und sagt: „${\displaystyle x}$ steht in der Relation ${\displaystyle R}$ zu ${\displaystyle y}$.“). Oft werden Relationen mit Symbolen wie ${\displaystyle \sim ,\ \simeq ,\ \approx ,\ <}$ und ${\displaystyle \geq }$ bezeichnet.

Beispiele

• ${\displaystyle \sim \ :=\{(x,y)\in \mathbb {Z} ^{2}|10>|x-y|\}}$. Dann gilt beispielsweise: ${\displaystyle 2\not \sim 12,\ 1\not \sim 15,\ 5\sim 5}$
• ${\displaystyle \sim \ :=\{(x,y)\in \mathbb {Z} ^{2}|(x-y)\equiv 0{\bmod {x}}\}}$. Für ${\displaystyle x=3}$ gilt dann: ${\displaystyle 2\sim 5,\ 3\sim 9,\ 4\sim 4,\ 7\not \sim 11}$
• ${\displaystyle \sim \ :=\{(x,y)\in \mathbb {R} ^{2}|\exists n\in \mathbb {Z} \colon \ x^{n}=y\}}$. Dann gilt ${\displaystyle 2\sim 4\sim 16\sim {\sqrt {2}},\ 5\sim 5\sim 625,\ 4\not \sim 8}$

Definition

Seien ${\displaystyle A\,}$ und ${\displaystyle B\,}$ Mengen, ${\displaystyle A\times B}$ ihr kartesisches Produkt und ${\displaystyle E(x,y)\,}$ eine Aussageform zweier Variablen aus ${\displaystyle A\,}$ und ${\displaystyle B\,}$. Die Menge ${\displaystyle R=\{(x,y)\in A\times B\mid E(x,y)\}}$ heißt Relation. Für ${\displaystyle (x,y)\in R}$ schreibt man auch ${\displaystyle xRy\ }$ und sagt: "${\displaystyle x\,}$ steht in der Relation ${\displaystyle R\,}$ zu ${\displaystyle y\,}$".

Äquivalenzrelation

Sei ${\displaystyle \sim }$ eine Relation auf einer Menge ${\displaystyle A\,}$. Man nennt ${\displaystyle \sim }$ Äquivalenzrelation, falls für alle ${\displaystyle a,b,c\in A}$ gilt:

• ${\displaystyle a\sim a\ }$ (Reflexivität)
• ${\displaystyle a\sim b\Rightarrow b\sim a}$ (Symmetrie)
• ${\displaystyle a\sim b\land b\sim c\Rightarrow a\sim c}$ (Transitivität)

Mit ${\displaystyle [a]:=\{b\in A|a\sim b\}}$ bezeichnen wir die Äquivialenzklasse eines Elements ${\displaystyle a\in b}$. Die Äquivalenzklassen bilden eine Partition von ${\displaystyle A}$, das heißt, sind ${\displaystyle a,b\in A}$, so gilt ${\displaystyle [a]=[b]}$ oder ${\displaystyle [a]\cap [b]=\emptyset }$. Wir bezeichnen mit ${\displaystyle A/\sim :=\{[a]|a\in A\}}$ die Menge aller Äquivalenzklassen der Relation.