Relácie ekvivalencie

• reflexívna: $(\forall x\in M)$ $(x,x)\in R$;
• symetrická: $(\forall x,y\in M)$ $(x,y)\in R$ $\Ra$ $(y,x)\in R$;
• tranzitívna: $(\forall x,y,z\in M)$ $(x,y)\in R$ $\land$ $(y,z)\in R$ $\Ra$ $(x,z)\in R$
1. Overte, či relácia $R$ je relácia ekvivalencie na množine $M$.
   a) $M$ je ľubovoľná množina, $R=M\times M$;
   b) $M$ je ľubovoľná množina, $R=\{(x,x); x\in M\}$
   c) $M=\R$, $R=\{(x,y) \in M\times M; x-y\in\Z\}$;
   d) $M=\Z^2$, $R=\{((a,b),(c,d)) \in M\times M; a+d=b+c\}$;
   e) $M=\N^2$, $R=\{((a,b),(c,d)) \in M\times M; a+d=b+c\}$;
   f) $M=\R$, $R=\{(a,b) \in M\times M; \abs{a-b}\le1\}$;
   g) $M=\R$, $R=\{(x,y)\in M\times M; x^2=y^2\}$;
   h) $M=\powerset{\N}$, t.j. $M$ je množina všetkých podmnožín množiny $\N$ a $R=\{(A,B)\in M\times M; A\triangle B\text{ je konečná}\}$ (t.j. množiny $A$ a $B$ sú v relácii $R$, ak ich symetrický rozdiel $A\triangle B=(A\sm B)\cup(B\sm A)$ je konečná množina);
   i) $M=\powerset{\N}$, $R=\{(A,B)\in M\times M; \text{ existuje bijekcia z $A$ do }B\}$;
   j) $M=\Z$; $R=\{(x,y)\in M\times M; 3\mid x+2y\}$;
   k) $M=\R$, $R=\{(x,y) \in M\times M; x-y\in\Q\}$;
   l) $M=\R^2$; $R=\{((x_1,x_2),(y_1,y_2)\in M\times M; x_1=y_1)\}$;
   m) $M=\R^2$; $R=\{((x_1,x_2),(y_1,y_2)\in M\times M; x_1=y_1 \land x_2=y_2)\}$;
   n) $M=\R^2$; $R=\{((x_1,x_2),(y_1,y_2)\in M\times M; x_1=y_2 \land x_2=y_1)\}$;
   o) $M=\R^2$; $R=\{((x_1,x_2),(y_1,y_2)\in M\times M; x_1=y_1 \lor x_2=y_2)\}$;
   p) $M=\{\Zobr f{\Z}{\Z}\}$, t.j. $M$ je množina všetkých zobrazení zo $\Z$ do $\Z$; $R=\{(f,g)\in M\times M; f(1)=g(1)\}$;
   q) $M=\{\Zobr f{\Z}{\Z}\}$, t.j. $M$ je množina všetkých zobrazení zo $\Z$ do $\Z$; $R=\{(f,g)\in M\times M; f(1)=g(0)\}$;
   r) $M=G$, kde $(G,\circ)$ je grupa, $H$ je podgrupa grupy $G$ a $R=\{(x,y) \in M\times M; x\inv y \in H\}$. Sú niektoré relácii uvedených v ostatných častiach špeciálne prípady tejto relácie?
   s) $M$ je ľubovoľná množina, $\Zobr fMS$ je ľubovoľné zobrazenie a $R=\{(x,y)\in M\times M; f(x)=f(y)\}$. (=LAG1, 1.6.12(1)) Sú niektoré relácii uvedených v ostatných častiach špeciálne prípady tejto relácie?
2. Koľko existuje relácií ekvivalencie na trojprvkovej množine $\{0,1,2\}$?
3. Dokážte: Ak $R_1$ a $R_2$ sú relácie ekvivalencie na tej istej množine $M$, tak aj $R=R_1\cap R_2$ je relácia ekvivalencie na $M$. (Všimnite si, že $(a,b)\in R$ $\Lra$ $(a,b)\in R_1$ $\land$ $(a,b)\in R_2$.) Platí podobné tvrdenie aj pre zjednotenie relácií ekvivalencie?

Faktorové grupy

Ak máme komutatívnu grupu $(G,+)$ a nejakú jej podgrupu $H$, tak predpis $$x\sim y \qquad\Lra\qquad x-y\in H$$ určuje reláciu ekvivalencie na množine $G$. Množinu všetkých tried tejto ekvivalencie označíme ako $G/H$, t.j. $$G/H=\{[a]; a\in G\}.$$ Predpis $$[a]+[b]=[a+b]$$ potom určuje dobre definovanú binárnu operáciu na množine $G/H$. Dá sa dokázať, že $G/H$ s touto operáciou tvorí grupu. Túto grupu voláme faktorová grupa grupy $(G,+)$ podľa podgrupy $H$. Poznámka: Ak by sme označovali operáciu ako $\cdot$, tak by sme tú istú podmienku zapísali $x-y\in H$ ako $xy^{-1}\in H$.

Veta o faktorovom izomorfizme.

Nech $G$, $G'$ sú grupy, navyše $G$ je komutatívna. Ak $f\colon G\to G'$ je surjektívny homomorfizmus, tak $\Ker f$ je podgrupa grupy $G$ a platí $$G/\Ker f\cong G',$$ t.j. faktorová grupa $G$ podľa $\Ker f$ je izomorfná s $G'$. Poznámka: Predpoklad o komutatívnosti je tu iba preto, aby vôbec malo zmysel hovoriť o faktorovej podgrupe. Ak sa neskôr budete učiť o normálnych podgrupách, tak zistíte, že faktorové grupy sa dajú robiť aj pre nekomutatívne grupy. Vtedy to však nebude fungovať s ľubovoľnou podgrupou. Matematici by sa s tým mali stretnúť na predmete Algebra (1) v druhom ročníku. Poistní matematici na predmete Úvod do vysokoškolskej matematiky (2).
1. Ukážte, že faktorová grupa $G/H$ je izomorfná s grupou $K$. (Aspoň jednu úlohu skúste vyriešiť priamo pomocou definície faktorovej grupy a aspoň jednu úlohu pomocou vety o faktorovom izomorfizme.)
   a) $G=(\R\times \R,+)$, $H=\{(x,y); x+2y=0\}$, $K=(\R,+)$;
   b) $G=(\R\times \R,+)$, $H=\{(x,3x); x\in\R\}$, $K=(\R,+)$;
   c) $G=(\C,+)$, $H=\R$, $K=(\R,+)$;
   d) $G=(\Z_8,+)$, $H=2\Z_4=\{0,2,4,6\}$, $K=(\Z_2,+)$;
   e) $G=(\Z_8,+)$, $H=4\Z_2=\{0,4\}$, $K=(\Z_4,+)$;
   f) $G=(\C\sm\{0\},\cdot)$, $H=\R\sm\{0\}$, $K=\{c\in\C; \abs c=1\}$;
   g) $G=(\C\sm\{0\},\cdot)$, $H=\R^+=\{x\in \R; x>0\}$, $K=\{c\in\C; \abs c=1\}$;
   h) $G=(\Z,+)$, $H=4\Z=\{4z; z\in\Z\}$, $K=\Z_4$;
   i) $G=(\R\sm\{0\},\cdot)$, $H=\R^+$, $K=(\Z_2,+)$;
   j) $G=(\R^*,\cdot)$, $H=\{\pm1\}$, $K=(\R^+,\cdot)$
2. Zistite, či dané grupy sú izomorfné. V celom cvičení budeme ako $S$ označovať grupu $(\{c\in\C;\abs{c}=1\},\cdot)$ (prípadne množinu prvkov tejto grupy) a $C_n=(\{c\in\C; c^n=1\},\cdot)$
   a) $(\C\sm\{0\},\cdot)/\{c\in\C; c^n\in\R\sm\{0\}\}$, $(\C\sm\{0\},\cdot)/\R^+$ (pod $\R^+$ tu myslíme kladné reálne čísla, čiže $0\notin\R^+$), $S$
   b) $(\R,+)/\Z$, $S/C_n$, $S$
   c) $(\C\sm\{0\},\cdot)$, $(\C\sm\{0\},\cdot)/C_n$
   d) $(\{c\in\C; c^n\in\R\sm\{0\}\},\cdot)/\R^+$, $C_n$
   e) $(\{c\in\C; c^n\in\R\sm\{0\}\},\cdot)/C_n$, $\R^+$
   f) $C_{12}/C_4$, $\Z_3$
   g) $(\Z_2\times\Z_3,+)/(\Z_2\times\{0\})$, $\Z_3$
3. Nech $G$ je komutatívna grupa a $H$ je jej podgrupa. Ukážte, že zobrazenie $f(x)=x+h$ je bijekcia medzi $H$ a $[x]_H$. (T.j. pre každú triedu rozkladu $G$ podľa $H$ máme bijekciu medzi $H$ a $[x]_H$.)
4. S využitím predošlej úlohy dokážte, že ak $G$ je konečná komutatívna grupa a $H$ je jej podgrupa, tak počet prvkov $H$ delí počet prvkov $G$. (T.j. $\abs G$ je násobkom $\abs H$.) Poznámka: Táto vlastnosť platí aj pre grupy, ktoré nie sú komutatívne. Neskôr sa s ňou ešte stretnete pod názvom Lagrangeova veta.