Äquivalenzrelation

Eigenschaften:

• reflexiv

• symmetrisch

• transitiv

Äquivalenzklasse

Was sind Äquivalenzklassen? (Mathe, Mathematik, Definition)

Definition

Sei $R$ eine Äquivalenzrelation auf A. Zu jedem $x\in A$ heißt die Menge
$\bar{x}=\{y\in A|yRx\}$ die Äquivalenzklasse von x.

Satz 3.7

Sei $A$ eine Menge und $R$ eine Äquivalenzrelation auf $A$ und $xRy$
Dann gilt: $\bar{x}=\bar{y}$

Satz 3.8

Sei $A$ eine Menge un $R$ eine Äquivalenzrelation auf $A$ und $x,y\in A$
Dann gilt: $\bar{x}=\bar{y}\text{oder}\bar{x}\cup \bar{y}=\varnothing$

Korollar

Sei $A$ eine Menge und $R$ eine Äquivalenzrelation auf $A$.
Dann ist $A$ die disjunkte Vereinigung der Äquivalenzklasse von $R$

Partition

Definition

Sei $A$ eine Menge. Die Menge $P\subseteq \mathcal{P}(A)$ heißt Partition von $A$, wenn gilt:
(P1) Für alle $M\in P$ gilt: $M\ne \varnothing$
(P2) Für alle $M,N\in P$ gilt: $M=N$ oder $M\cap N=\varnothing$
(P3) Für alle $x\in A$ gilt: Es gibt ein $M\in P$ so dass $x\in M$.

Beispiel

$A=\{1,2,3\}$ dann ist:
$\{\{1\},\{2\},\{3\}\}$ oder $\{\{1,2\},\{3\}\}$
eine Partition.
Aber $\{\{1,2\},\{2,3\}\}$ nicht.

Satz

Sei $R$ eine Äquivalenzrelation auf der Menge $A$. Sei $A/R$ die Menge aller Äquivalenzklassen von $R$. Dann gilt: $A/R$ ist eine Partition von $A$.

Satz

Sei $P$ eine Partition einer Menge $A$. Die Relation $R\subseteq A\times A$ sei gegeben durch: $xRy\iff \exists M\in P:x\in M\wedge y\in M$
Dann ist $R$ eine Äquivalenzrelation.

Link to original

Rechnen mit Äquivalenzklassen

siehe: Äquivalenzklasse

Definition 5.1

Die Relation $\sim$ auf $\mathbb{N}\times \mathbb{N}$ sei gegeben durch:
$(m,n)\sim (m^{\prime },n^{\prime }):⟺m+n^{\prime }=m^{\prime }+n$

Addition

$\overline{(a,b)}+\overline{(c,d)}=\overline{(a+c,b+d)}$

Es gilt das:

• Assoziativgesetz

• Kommutativgesetz

• Neutrales Element $\overline{(0,0)}+\overline{(a,b)}=\overline{(a,b)}$

• Inverse Element $\overline{(a,b)}+\overline{(b,a)}=\overline{(0,0)}$

Multiplikation

$\overline{(a,b)}\cdot \overline{(c,d)}=\overline{(ac+bd,ad+bc)}$

Es gilt das:

• Kommutativgesetz

• Neutrales Element $\overline{(1,0)}+\overline{(a,b)}=\overline{(a,b)}$

• Distributivgesetz $\overline{(a,b)}\cdot (\overline{(a,b)}+\overline{(a,b)})=\overline{(a,b)}\cdot \overline{(c,d)}+\overline{(a,b)}\cdot \overline{(c,d)}$

Addition und Multiplikation gilt auch mit $\sim$ also: (Satz 5.5)

$(a,b)\sim (a^{{}^{\prime }},b^{{}^{\prime }})\wedge (c,d)\sim (c^{{}^{\prime }},d^{{}^{\prime }})⟺\overline{(a+c,b+d)}=\overline{(a^{{}^{\prime }}+c^{{}^{\prime }},b^{{}^{\prime }}+d^{{}^{\prime }})}$

\overline{(ac + bd, ad + bc)} = \overline{(a^{'}c^{'} + b^{'}d^{'}, a^{'}d^{'} + b^{'}c^{'})}$$Link to original

Link to original