Je $(\mathcal P(X),\triangle)$ grupa?

[Martin Sleziak]

Minulý týždeň som zadal takúto úlohu - napíšem k nej niečo, keď bude po termíne.$\newcommand{\powerset}[1]{\mathcal{P}(#1)}$

Pre množinu $X=\{0,1\}$ zoberme množinu $\powerset X$ všetkých podmnožín množiny $X$. Pre $A,B\subseteq X$ uvažujme symetrickú diferenciu
$$A\triangle B=(A\setminus B)\cup(B\setminus A).$$
Je $(\powerset X,\triangle)$ komutatívna grupa? Svoje tvrdenie zdôvodnite!

Ale aspoň stručne k otázke, ktorú som dostal mailom.

chcel som sa iba spýtať ohľadom úlohy pre LAG
dobrovoľné cvičenia, symetrická diferencia a či tvorí grupu s P(X), na dokázanie asociatívnosti by sa mohli využiť rôzne vety z množinovej teórie, ale aby sme ich mohli využiť, musíme v úlohe rozpísať dôkazy všetkých viet ktoré by sme chceli použiť, keďže sme ich nepreberali na prednáškach?

Asi taká všeobecná (a očividná) poznámka - k čomu človek má písať do domácej úlohy (alebo písomky) aj zdôvodnenie je vždy niečo, čo treba aspoň trochu rozumne odhadnúť. A úroveň potrebných detailov sa môže líšiť napríklad aj v závislosti od toho, či s nejakou témou iba začínať (a vyučujúci chce vidieť, či ste zvládli základné veci), alebo či to je vec, s ktorou ste už robili veľakrát.

Konkrétne k tomuto príkladu:
* Napríklad sa pýtame, či $\triangle$ je asociatívna operácia - k tomu by som chcel nejaké zdôvodnenie. (V podstate akýmkoľvek rozumným spôsobom.)
* Ale ak napríklad budete používať to, že množina a jej doplnok majú prázdny prienik - toto by som bral ako dosť očividný fakt; úplne v pohode bez zdôvodnenia. Alebo napríklad $X\cap (Y \cup Z)= (X\cap Y) \cup (X\cap Z)$ tiež v pohode beriem bez dôkazu.
* Toto nie je žiadne poriadne kritérium ale: Snažím sa zadávať úlohy, ktoré nie sú strašne zdĺhavé. Čiže ak by Vám riešenie vychádzalo tak, že rozpisujete dôkazy na niekoľko strán, tak sa pravdepodobne nastala niektorá z týchto vecí: A) Dokazujete aj niečo, čo by nebolo treba - a v pohode to budem brať, keď to prehlásite ako fakt. B) Možno niečo robíte komplikovanejšie, než by sa to dalo urobiť.

Určite nemám problém uznať to, že to je síce úloha o grupe - ale treba tam nejako využívať prácu s množinami, čiže vlastne niečo z iného predmetu prípadne zo strednej školy.

Keď už píšem niečo o tejto úlohe, tak upozorním aj na to, že som zadanie napísal tak, že množina $X$ je dvojprvková. Potom $\powerset X$ je konečná množina - a pomerne malá. Takže ak by ste chceli, viete si vypísať aj celú tabuľku operácie. (Ale na druhej strane, možno zvládnete napísať aj dôkaz, ktorý funguje pre ľubovoľnú množinu $X$ a tabuľku nijako nebudete potrebovať.)

[Martin Sleziak]

Zadal som túto úlohu pre konkrétnu množinu.
V skutočnosti by sme to však vedeli zdôvodniť aj pre ľubovoľnú množinu. (Pozrieme sa aj na všeobecné riešenie a aj to, či vieme nejako využiť, že ide o dvojprvkovú množinu.)$\newcommand{\Z}{\mathbb Z}\newcommand{\sm}{\setminus}\newcommand{\emps}{\emptyset}\newcommand{\powerset}[1]{\mathcal P(#1)}$

Je to grupa pre ľubovoľné $X$.
Chceme overiť, či $(\mathcal P(X),\triangle)$ je grupa.
Vlastne ide o prácu s množinami a množinovými operáciami.

Binárna operácia.
Ak $A,B\subseteq X$, tak aj $A\triangle B\subseteq X$.

Spoiler:

Toto je asi dosť evidentné, ale ak by chcel človek detailnejšie rozpísať prečo to platí, tak máme
\begin{gather*}
A\sm B\subseteq A \subseteq X\\
B\sm A\subseteq B \subseteq X
\end{gather*}
Čiže $A\setminus B$ aj $B\setminus A$ sú podmnožiny množiny $X$ a potom aj pre ich zjednotenie platí
$$(A\setminus B)\cup(B\setminus A)\subseteq X.$$

Komutatívnosť.
Priamo z definície vidno, že $A\triangle B=B\triangle A$, t.j. táto operácia je komutatívna. (Pri overovaní NP a IP sa nám teda už bude stačiť pozerať na jedno poradie.)

Spoiler:

Pretože zjednotenie je komutatívne, platí
\begin{gather*}
(A\setminus B)\cup(B\setminus A)=(B\setminus A)\cup(A\setminus B)\\
A\triangle B=B\triangle A
\end{gather*}

Neutrálny prvok.
Pre každú množinu $A$ platí
$$A\triangle\emps=A,$$
teda $\emps$ je neutrálny prvok.

Spoiler:

$A\triangle\emps=(A\setminus \emps)\cup(\emps\setminus A)=A\cup\emps=A$

Inverzný prvok.
Inverzný prvok k $A$ je $A$.

Spoiler:

$A\triangle A=(A\setminus A)\cup(A\setminus A)=\emps\cup\emps=\emps$

Asociatívnosť.
Pre ľubovoľné množiny platí
$$A\triangle (B\triangle C)=(A\triangle B)\triangle C.$$
Dôkaz sa dá robiť viacerými spôsobmi; dal som k tomu samostatný topic: viewtopic.php?t=2117

[Martin Sleziak]

Pre dvojprvkovú množinu to je $\mathbb Z_2\times\mathbb Z_2$.$\newcommand{\Z}{\mathbb Z}\newcommand{\sm}{\setminus}\newcommand{\emps}{\emptyset}\newcommand{\powerset}[1]{\mathcal P(#1)}$

Ja som túto úlohu zadal pre $X=\{0,1\}$.
V tomto prípade máme $\powerset X=\{\emps,\{0\},\{1\},X\}$.
(Všeobecne, ak mám konečnú $n$-prvkovú množinu, tak $\powerset X$ má $2^n$ prvkov.)

Vieme teda vypísať celú tabuľku.
$$\begin{array}{|c|c|c|c|c|}
\hline
\triangle & \emps & \{0\} & \{1\} & X \\\hline
\emps & \emps & \{0\} & \{1\} & X \\\hline
\{0\} & \{0\} & \emps & X & \{1\} \\\hline
\{1\} & \{1\} & X & \emps & \{0\} \\\hline
X & X & \{1\} & \{0\} & \emps \\\hline
\end{array}$$

Z tabuľky vidíme na prvý pohľad komutatívnosť.
Takisto ľahko skontrolujeme aj to, že každý prvok je inverzný sám k sebe.
Z tabuľky nejako ľahko nevidno asociatívnosť.
Ale už sme videli nejaké príklady štvorprvkových grúp, konkrétne sme sa stretli s grupami $(\Z_4,+)$ aj $(\Z_2\times\Z_2,+)$.
Môžeme porovnať našu tabuľku s tabuľkami týchto grúp. V $\Z_4$ neplatí, že každý prvok je inverzný sám k sebe. Ale $\Z_2\times\Z_2$ má túto vlastnosť.
$$\begin{array}{|c|c|c|c|c|}
\hline
+ & (0,0) & (1,0) & (0,1) & (1,1) \\\hline
(0,0) & (0,0) & (1,0) & (0,1) & (1,1) \\\hline
(1,0) & (1,0) & (0,0) & (1,1) & (0,1) \\\hline
(0,1) & (0,1) & (1,1) & (0,0) & (1,0) \\\hline
(1,1) & (1,1) & (0,1) & (1,0) & (0,0) \\\hline
\end{array}$$

Spoiler:

$$
\begin{array}{cc}
\begin{array}{|c|c|c|c|c|}
\hline
\triangle & \emps & \{0\} & \{1\} & X \\\hline
\emps & \emps & \{0\} & \{1\} & X \\\hline
\{0\} & \{0\} & \emps & X & \{1\} \\\hline
\{1\} & \{1\} & X & \emps & \{0\} \\\hline
X & X & \{1\} & \{0\} & \emps \\\hline
\end{array}
&
\begin{array}{|c|c|c|c|c|}
\hline
+ & (0,0) & (1,0) & (0,1) & (1,1) \\\hline
(0,0) & (0,0) & (1,0) & (0,1) & (1,1) \\\hline
(1,0) & (1,0) & (0,0) & (1,1) & (0,1) \\\hline
(0,1) & (0,1) & (1,1) & (0,0) & (1,0) \\\hline
(1,1) & (1,1) & (0,1) & (1,0) & (0,0) \\\hline
\end{array}
\end{array}
$$

Ak porovnáme tieto tabuľky, vidíme, že sú "v podstate rovnaké". (Inak povedané, sú to izomorfné štruktúry.)

Spoiler:

Toto je izomorfizmus zodpovedajúci poradiu, v akom sme prvky zapísali do týchto dvoch tabuliek:
\begin{align*}
\emps&\mapsto(0,0)\\
\{0\}&\mapsto(1,0)\\
\{1\}&\mapsto(0,1)\\
X&\mapsto(1,1)
\end{align*}

Vieme, že asociatívnosť platí pre sčitovanie v $\Z_2\times\Z_2$.
Keďže operácia v ľavej tabueľke je "taká istá", tiež musí byť asociatívna.

[Martin Sleziak]

Vypisovanie možností$\newcommand{\Z}{\mathbb Z}\newcommand{\sm}{\setminus}\newcommand{\emps}{\emptyset}\newcommand{\powerset}[1]{\mathcal P(#1)}$

Viacerí ste sa túto úlohu snažili riešiť tak, že ste prechádzali jednotlivé možnosti.

Skúsim napísať niečo aj k tomu, ako sa dalo pri takomto postupe nejaké možnosti si ušetriť.

Ako ste si viacerí všimli, veľmi ľahko viem vybaviť prípad, keď niektorý z našich troch prvkov je neutrálny prvok. A vďaka komutatívnosti prípad, keď tam mám trikrát ten istý prvok.

Spoiler:

Overujem rovnosť $x\cdot(y\cdot z)=(x\cdot y)\cdot z$.
Ak moja operácia má neutrálny prvok $e$ a niektorý z týchto troch prvkov sa rovná $a$, tak táto rovnosť platí, zostane nám tam súčin zvyšných dvoch prvkov.
\begin{align*}
e\cdot(y\cdot z)&=y\cdot z\\
(e\cdot y)\cdot z&=y\cdot z\\
x\cdot(e\cdot z)&=x\cdot z\\
(x\cdot e)\cdot z&=x\cdot z\\
x\cdot(y\cdot e)&=x\cdot y\\
(x\cdot y)\cdot e&=x\cdot y
\end{align*}

V prípade $x=y=z$ zasa dostávam
$$x\cdot(x\cdot x)=(x\cdot x)\cdot x,$$
čo platí pre ľubovoľnú komutatívnu operáciu. (Iba sme tu vymenili poradie v akom násobím prvky $x$ a $x\cdot x$.)

Chcem spomenúť, že sme si vedeli ušetriť aj o niečo viac; kvôli stručnosti a prehľadnosti sa mi hodí veci si označiť trochu inak.

Máme nejakú štvorprkovú množinu $G=\{e,a,b,c\}$ s operáciu $\cdot$.
Pre túto operáciu platí
\begin{gather*}
a^2=b^2=c^2=e\\
ab=ba=c\\
ac=ca=b\\
bc=cb=a
\end{gather*}
V posledných troch riadkoch vystupujú prvky $a$, $b$, $c$ úplne symetricky.
Teda stručne ich vieme povedať aj tak, že ak $x$, $y$, $z$ sú tri rôzne prvky z $G$ také, že $x\ne e$, tak pre ne platí $x\cdot y=z$.

S týmto pozorovaním vieme vybaviť vždy viacero prípadov naraz.
Pri asociatívnosti sa pozeráme na súčin troch prvkov pri dvoch rôznych uzátvorkovaniach.
Už sme si rozmysleli, že to funguje ak niektorý z týchto troch prvkov je neutrálny prvok.
Treba už len teda vyriešiť prípady, keď tam máme iné prvky ako neutrálny. (Ale musíme nezabudnúť na to, že sa tu prvky môžu aj opakovať.)

1. Vyskytne sa tam ten istý prvok trikrát.
O tomto prípade sme si už rozmysleli, že vyplýva z komutatívnosti.
Ale pre takúto operáciu vieme aj spočítať
\begin{align*}
x\cdot(x\cdot x)=x\cdot e=x\\
(x\cdot x)\cdot x=e\cdot x=e
\end{align*}

2. Vyskytne sa tam niektorý prvok dvakrát.
\begin{align*}
x\cdot(x\cdot y)=x\cdot z=y\\
(x\cdot x)\cdot y=e\cdot y=y\\
x\cdot(y\cdot x)=x\cdot z=y\\
(x\cdot y)\cdot x=z\cdot x=y\\
y\cdot(x\cdot x)=y\cdot e=y\\
(y\cdot x)\cdot x=z\cdot x=y
\end{align*}
Pri treťom až šiestom riadku som vlastne vďaka komutatívnosti mohol zdôvodniť, že to je to isté ako niektorý z výrazov v prvých dvoch riadkoch.
Konkrétne z komutatívnosti vidím, že
\begin{gather*}
x\cdot(x\cdot y)=(x\cdot y)\cdot x=(y\cdot x)\cdot x=x\cdot(y\cdot x)\\
(x\cdot x)\cdot y=x\cdot(x\cdot y)
\end{gather*}

Ale zdalo sa mi o trochu prehľadnejšie to vypísať takto.

3. Sú to tri rôzne prvky.
\begin{align*}
x\cdot(y\cdot z)=x\cdot x=e\\
(x\cdot y)\cdot z=z\cdot z=e
\end{align*}

[Martin Sleziak]

$\mathbb Z_2$ nám môže pomôcť aj pri všeobecnom prípade.$\newcommand{\Z}{\mathbb Z}\newcommand{\sm}{\setminus}\newcommand{\emps}{\emptyset}\newcommand{\powerset}[1]{\mathcal P(#1)}$

Toto asi nie je v tomto okamihu až také veľmi dôležité. Ale pokojne sa môžete zamyslieť aj nad niečím takýmto, ak sa vám to zdá zaujímavé. (S podobnými vecami sa ale ešte určite stretnete aj inde, čiže teraz to nie je až také podstatné. Ak ste na tom tak, že máte problémy s inými vecami z tohto predmetu, radšej preskočte niečo takéto, čo je v tomto okamihu skôr "navyše".)

Už sme videli, že pre dvojprvkovú množinu bola takáto grupa izomorfná so $(\Z_2)^2$.
Aj pre ľubovoľnú množinu $X$ vieme definovať grupu, ktorú by sme nazvali $(\Z_2)^X$.
Pozostáva zo všetkých zobrazení $f\colon X\to\Z_2$, pričom operáciu definujeme po súradniciach. T.j. pre dve funkcie $f,g\colon X\to\Z_2$ definujeme $f+g\colon X\to\Z_2$ ako
$$(f+g)(x)=f(x)+g(x).$$
(Na pravej strane je sčitovanie v $\Z_2$, t.j. funkčné hodnoty sčítame modulo $2$.)
Takéto niečo som už spomenul na inom mieste - aj so zdôvodnením, že to je naozaj grupu: viewtopic.php?t=2110

Dá sa rozmyslieť, že aj všeobecne platí $(\mathcal P(X),\triangle)\cong((\Z_2)^X,+)$.

A izomorfizmus bude do istej miery vyzerať podobne ako v konečnom prípade.

Pre podmnožinu $A\subseteq X$ a pre ľubovoľný prvok $x\in X$ máme dve možnosti: Tento prvok buď patrí alebo nepatrí do $A$.
Podľa toho zvolíme na "$x$-tej súradnici" nulu alebo jednotku.

Formálnejšie: Pre množinu $A$ zadefinujme funkciu $\chi_A\colon X\to\{0,1\}$ predpisom:
$$\chi_A(x)=
\begin{cases}
1, & \text{ak }x\in A, \\
0 & \text{ak }x\notin A.
\end{cases}
$$
S takouto funkciou sa ešte veľakrát stretnete, zvykne sa jej hovoriť charakteristická funkcia.

Dostali sme teda zobrazenie
\begin{gather*}
\varphi \colon \powerset{X} \to (\Z_2)^X\\
\varphi \colon A \mapsto \chi_A
\end{gather*}

Mali by sme sa presvedčiť, či to je izomorfizmus.

Že to je bijekcia môžeme overiť z definície - skontrolujeme injektívnosť a surjektívnosť.

Spoiler:

Ak platí $\chi_A=\chi_B$, tak máme
$$A=\{x\in X; \chi_A(x)=1\}=\{x\in X; \chi_B(x)=1\}=B.$$
Overili sme teda injektívnosť.

Majme teraz ľubovoľnú funkciu $f\colon X\to\{0,1\}$. Definujme $$A=\{x\in X; f(x)=1\}.$$
Rozmyslime si, že $\chi_A=f$.

Pýtame sa na rovnosť dvoch funkcií, stačí nám overiť, či sa zhodujú funkčné hodnoty, t.j. či pre každé $x\in X$ platí
$$\chi_A(x)=f(x).$$

Využijeme, že $f$ nadobúda iba hodnoty $0$ a $1$.
Ak $f(x)=1$, tak $x\in A$ a máme aj $\chi_A(x)=1$.
Ak $f(x)=0$, tak $x\notin A$, a teda $\chi_A(x)=0$.

V oboch prípadoch rovnosť $\chi_A(x)=f(x)$ platí.

Našli sme vzor pre ľubovoľné $f\in(\Z_2)^2$, máme teda i surjektívnosť.

Alebo tak, že si všimneme, že zobrazenie $\psi\colon(\Z_2)^X\to \powerset{X}$ určené predpisom
$$\psi(f)=\{x\in X; f(x)=1\}.$$
je inverzné zobrazenie k zobrazeniu $\varphi$.

Spoiler:

\begin{gather*}
\psi(\varphi(A))=\psi(\chi_A)=\{x\in X; \chi_A(x)=1\}=A\\
\varphi(\psi(f))=\chi_{\{x\in X; f(x)=1\}} \overset{(*)}= f
\end{gather*}
Pričom rovnosť označenú hviezdičkou môžeme zdôvodniť takto: Stačí nám overiť, či sa tieto funkcie zhodujú v každom bode definičného oboru, t.j. či pre každé $x\in X$ platí
$$\chi_{\{x\in X; f(x)=1\}}(x)=f(x).$$
Pritom vieme, že $f$ môže nadobúdať iba hodnoty $0$ a $1$.
Ak $f(x)=1$, tak dostaneme aj $\chi_{\{x\in X; f(x)=1\}}(x)=1$. (Keďže $x$ patrí do množiny v dolnom indexe.)
Ak $f(x)=0$, tak platí aj $\chi_{\{x\in X; f(x)=1\}}(x)=0$. (Tentokrát $x$ do tejto množiny nepatrí.)
V oboch prípadoch sa funkčné hodnoty zhodujú.

Vlastne obe možnosti boli založené na tom, že sme si uvedomili, že množina $A$ je funkciou $\chi_A$ jednoznačne určená. Pozostáva z tých bodov, kde je funkčná hodnota rovná jednotke.
Inak povedané, využívame rovnosť
$$A=\{x\in X; \chi_A(x)=1\}.$$


Ešte nás zaujíma, či je to homomorfizmus. T.j. vlastne chceme overiť toto:
\begin{gather*}
\varphi(A\triangle B)=\varphi(A)+\varphi(B)\\
\chi_{A\triangle B}=\chi_A+\chi_B
\end{gather*}
Pre istotu ešte pripomeniem, že sčitovanie na pravej strane je sčitovanie modulo 2 a funkcie sčitujeme "po súradniciach" resp. "po bodoch".

Spoiler:

Chceme skontrolovať, či $\chi_{A\triangle B}(x)=\chi_A(x)+\chi_B(x)$.
Môžeme rozobrať jednotlivé prípady podľa toho, či $x$ leží v $A$ resp. v $B$.
$$\begin{array}{|c|c|c|c|c|c|}
\hline
& & \chi_A(x) & \chi_B(X) & \chi_A(x)+\chi_B(x) & \chi_{A\triangle B}(x) \\\hline
x\in A & x\in B & 1 & 1 & 0 & 0 \\\hline
x\in A & x\notin B & 1 & 0 & 1 & 1 \\\hline
x\notin A & x\in B & 0 & 1 & 1 & 1 \\\hline
x\notin A & x\notin B & 0 & 0 & 0 & 0 \\\hline
\end{array}$$