Ekvivalence a rozklady

Ekvivalence

• Ekvivalence jsou matematickým protějškem k pojmu nerozlišitelnost

• Binární relace $E$ na množině $A\ne \varnothing$ 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\mid <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 ${\iota }_X$ je největší ekvivalence na $X$

Rozklad

• Rozklad na množině je matematický protějšek shluků nerozlišitelných prvků

• Nechť $X\ne \varnothing$ je množina. Systém množin $\Pi \subseteq 2^X$ splňují

  • $Y\ne \varnothing$ pro každou $Y\in \Pi$
    • Rozklad $\Pi$ na $X$ je systém neprázdných podmnožin $Y$
  • Pro každé $Y_1,Y_2\in \Pi$ platí: pokud $Y_1\cap Y_2\ne \varnothing$, pak $Y_1=Y_2$
    • Požadujeme, aby dvě různé třídy rozkladu $\Pi$ byly disjunktní
  • $\cup \Pi =X$
    • Sjednocení všech tříd rozkladu $\Pi$ bylo rovno množině $X$ se nazývá rozklad na množině $X$.

• Množiny $Y\in \Pi$ nazýváme třídy rozkladu $\Pi$. Pro prvek $x\in X$ označíme $[x{]}_{\Pi }$ tu třídu rozkladu $\Pi$, která obsahuje $x$.

• Na množině $X$ existují dva mezní rozklady:

  • $[x{]}_{\Pi }=\{x\}$
    • Všechny třídy rozkladu $\Pi$ jsou jednoprvkové
  • $[x{]}_{\Pi }=X$
    • Máme jen jednu třídu rozkladu $\Pi$, která je rovna celé $X$

• Všechny rozklady pro $X=\{a,b,c,d\}$:

  $$\begin{array}{rlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlr}\{\{a\},\{b\},\{c\},\{d\}\}& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \{\{a,b\},\{c\},\{d\}\}& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \{\{b\},\{a,c\},\{d\}\}& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \{\{b\},\{c\},\{a,d\}\}& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \{\{a\},\{b,c\},\{d\}\}& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \{\{a,b,c\},\{d\}\}& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \{\{b,c\},\{a,d\}\}& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \{\{a\},\{c\},\{b,d\}\}& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \{\{a,c\},\{b,d\}\}& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \{\{c\},\{a,b,d\}\}& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \{\{a\},\{b\},\{c,d\}\}& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \{\{a,b\},\{c,d\}\}& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \{\{b\},\{a,c,d\}\}& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \{\{a\},\{b,c,d\}\}& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \{\{a,b,c,d\}\}& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \end{array}$$

Rozklad a Ekvivalence

• Nechť $\Pi$ je rozklad na $X$. Pak binární relace $E_{\Pi }$ na $X$ definovaná

  • $<x,y>\in E_{\Pi }$, právě když $[x{]}_{\Pi }=[y{]}_{\Pi }$ je ekvivalence příslušná rozkladu $\Pi$

• Nechť $E$ je ekvivalence na $X$. Pak systém množin ${\Pi }_E\subseteq 2^X$ definovaný

  • ${\Pi }_E=\{[x{]}_E\mid x\in X\}$ je rozklad příslušný ekvivalenci $E$

• Pro ekvivalenci $E$ na $X$ a pro rozklad $\Pi$ na $X$ máme $E_{{\Pi }_E}=E,{\Pi }_{E_{\Pi }}=\Pi$

Přirozené zobrazení

• Rozklad na množině $X$ příslušný ekvivalenci $E$ označujeme běžně $X/E$ místo ${\Pi }_E$ a někdy jej nazýváme faktorová množina $X$ podle $E$

• Jelikož $[x{]}_E=[x{]}_{\Pi E}$, říkáme, že $[x{]}_E$ je třída rozkladu množiny $X$ podle $E$

• Uvažujeme-li o vztahu množiny $X$ a rozkladu $X/E$, pak víme, že každému $x\in X$ přísluší třída rozkladu $[x{]}_E$, pro kterou $x\in [x{]}_E$

• Pro ekvivalenci $E$ na $X$ tedy můžeme uvažovat zobrazení $f_E:X\to X/E$,

  • kde $f_E(x)=[x{]}_E$ pro každý $x\in X$, a nazýváme jej přirozené (kanonické) zobrazení.

• Platí, že každé přirození zobrazení $f_E$ je surjektivní

• $f_E$ je i injektivní, právě když $[x{]}_E=\{x\}$ pro každé $x\in X$, což je právě když $E=i{d}_x$

Navigace

Předchozí: Binární relace na množině a jejich vlastnosti Následující: Uspořádání, Hasseovy diagramy Celý okruh: 1. Teoretické základy informačních technologií