DU1 - ZS 2014/15

[Martin Sleziak]

Čo znamená rovnosť množín?

V jednej z odovzdaných úloh sa vyskytlo tvrdenie, že pri overovaní $A\setminus B=A\setminus (A\cap B)$ vlastne treba overiť
$$(\forall x) x\in A\setminus B \Leftrightarrow (\forall x) x\in A\setminus (A\cap B).$$
V skutočnosti však overujeme
$$(\forall x) x\in A\setminus B \Leftrightarrow x\in A\setminus (A\cap B).$$
Inak povedané, to že sa množiny $X$ a $Y$ rovnajú znamená, že $$(\forall x) x\in X \Leftrightarrow x\in Y.$$
Podmienka
$$(\forall x) x\in X \Leftrightarrow (\forall x)x\in Y$$
je niečo iné. Na oboch stranách dostaneme pre ľubovoľné množiny nepravdivý výrok. Výrok $(\forall x) x\in X$ by bol pravdivý, len ak by $X$ bola množina obsahujúca všetky množiny. Množina všetkých množín však neexistuje. To sa dá odvodiť do istej miery podobne ako keď sme hovorili o Russelovom paradoxe. (Alebo si môžeme uvedomiť, že takáto množina by musela spĺňať $X\in X$, súčasne z axiómy regularity vieme $X\notin X$.)

Symetrická diferencia a spojka XOR

Ak dokazujete nejakú rovnosť o symetrickej diferencii, tak je užitočné použiť logickú spojku XOR. Takto je napríklad dokázaná identita $(A\triangle B)\triangle C=A\triangle(B\triangle C)$ v poznámkach k prednáške.

Ako ste si niektorí správne všimli v identite $A\cup B= A\triangle B\triangle(A\cap B)$ nie je jasné, či na pravej strane je $(A\triangle B)\triangle(A\cap B)$ alebo $A\triangle (B\triangle(A\cap B))$. Vieme však, že symetrická diferencia je asociatívna, obe množiny sú rovnaké.

Treba vedieť tabuľky

Objavili sa aj nejaké nesprávne vyplnené tabuľky. K tomu asi však nemám priveľa čo okomentovať - treba sa naučiť ako vyzerajú tabuľky pravdivostných hodnôt pre jednotlivé logické spojky. (Zdá sa, že problémy robí hlavne implikácia.)

De Morganove pravidlá

V jednom z riešení v dôkaze $A\setminus (B\cup C) = (A\setminus B)\setminus C$ bolo nesprávne prepísané:
$x\in A\setminus (B\cup C)$ $\Leftrightarrow$ $x\in A \land x\notin (B\cup C)$ $\Leftrightarrow$ $x\in A \land (x\notin B\land x\notin C)$
Toto nie je správne. Platí:
$x\notin (B\cup C)$ $\Leftrightarrow$ $\neg (x\in B \lor x\in C)$ $\Leftrightarrow$ $(x\notin B\land x\notin C)$

Dôkaz cez pomocné tvrdenia

Ako niekto správne poznamenal, identitu $A\cup (A\cap B)=A$ vidno skoro hneď.
Dala sa zdôvodniť tak, že platí $A\cap B\subseteq A$ (tvrdenie 2.4.7(ii)) a potom využiť, že zjednotenie množiny s jej podmnožinou je presne pôvodná množina. (T.j. ak $C\subseteq D$, tak $C\cup D=D$, pričom tento fakt tu aplikujeme pre $C=A\cap B$ a $D=A$. Toto je vlastne tvrdenie 2.4.6 resp. jeho časť.) V texte k prednáške sú obe uvedené tvrdenia dokázané, môžete sa pozrieť na dôkaz alebo sa nad ním zamyslieť samostatne - overiť tieto fakty skutočne nie je príliš ťažké.

Podobné úvahy sa dajú použiť pri dokazovaní $A\cap (A\cup B)=A$.

Vlastne vidíme iný spôsob odvodenia nejakej množinovej identity - namiesto toho, aby sme mechanicky prepísali tvrdenie na tautológiu alebo kreslili Vennove diagramy, sme najprv odvodili jednoduchšie pomocné tvrdenia. (To môže byť užitočné najmä ak sa v identite vyskytuje viac množín, napríklad už pre 4 množiny je vypísanie tabuľky s $2^4=16$ riadkami zdĺhavé a vo Vennových diagramoch sa už dá vcelku ľahko pomýliť. Takže v takých prípadoch sa oplatí zamyslieť nad tým, či sa nedá dôkaz nejako zjednodušiť.)

Z minulých rokov:
Podobné komentáre k tejto úlohe z minulých rokov si môžete pozrieť tu:
viewtopic.php?t=321
viewtopic.php?t=71