Ekvivalence a rozklady

Ekvivalence jsou matematickým protějškem k pojmu nerozlišitelnost
Binární relace $E$ na množině $A \neq = \emptyset$ se nazývá ekvivalence, je-li reflexivní, symetrická a tranzitivní.
Vlastnosti:
- Reflexivní
  - Každé $x$ z $X$ je totožné s $x$ , tedy $x$ nelze rozlišit od $x$
- Symetrická
  - Pokud $x$ nelze rozlišit od $y$ , pak i $y$ nelze rozlišit od $x$
- Tranzitivní
  - Pokud $x$ nelze rozlišit od $y$ a $y$ od $z$ , pak i $x$ nelze rozlišit od $z$
Reflexivní a symetrická relace se nazývá tolerance
Tranzitivní tolerance se nazývá ekvivalence
Pro ekvivalenci $E$ na množině $X$ definujeme pro každé $x \in X$ množinu
- $[x]_{E} = {y \in X ∣< x, y >\in E}$ = třída ekvivalence prvku $x$
- $[x]_{E}$ je množina těch prvků $y \in X$ , které jsou E-ekvivalentní $x$
$< x, y >\in E$ čteme jako ” $x$ a $y$ jsou E-ekvivalentní”
Relace identity $i d_{x}$ je nejmenší ekvivalence na $X$
- $i d_{x} = {< a, a >, < b, b >, < c, c >}$
Relace kartézského součinu $ι_{X}$ je největší ekvivalence na $X$

Rozklad na množině je matematický protějšek shluků nerozlišitelných prvků
Nechť $X \neq = \emptyset$ je množina. Systém množin $Π \subseteq 2^{X}$ splňují
- $Y \neq = \emptyset$ pro každou $Y \in Π$
  - Rozklad $Π$ na $X$ je systém neprázdných podmnožin $Y$
- Pro každé $Y_{1}, Y_{2} \in Π$ platí: pokud $Y_{1} \cap Y_{2} \neq = \emptyset$ , pak $Y_{1} = Y_{2}$
  - Požadujeme, aby dvě různé třídy rozkladu $Π$ byly disjunktní
- $⋃ Π = X$
  - Sjednocení všech tříd rozkladu $Π$ bylo rovno množině $X$ se nazývá rozklad na množině $X$ .
Množiny $Y \in Π$ nazýváme třídy rozkladu $Π$ . Pro prvek $x \in X$ označíme $[x]_{Π}$ tu třídu rozkladu $Π$ , která obsahuje $x$ .
Na množině $X$ existují dva mezní rozklady:
- $[x]_{Π} = {x}$
  - Všechny třídy rozkladu $Π$ jsou jednoprvkové
- $[x]_{Π} = X$
  - Máme jen jednu třídu rozkladu $Π$ , která je rovna celé $X$
Všechny rozklady pro $X = {a, b, c, d}$ :

undefined

Vojtěch Netrh