a) $A\subseteq B\cap C$ práve vtedy, keď $A\subseteq B$ a $A\subseteq C$;
b) $A\subseteq B\cup C$ práve vtedy, keď $A\subseteq B$ alebo $A\subseteq C$;
c) $A\cup B \subseteq C$ práve vtedy, keď $A\subseteq C$ a $B\subseteq C$;
d) $A\cap B \subseteq C$ práve vtedy, keď $A\subseteq C$ alebo $B\subseteq C$.
Dôkaz
Tvrdenia v častiach a), c) platia, čiže by bolo treba uviesť nejaký dôkaz.
Môžeme uvedené tvrdenie dokazovať priamo z definície; alebo môžeme skúsiť využiť nejaké pomocné tvrdenia.
$\boxed{\Rightarrow}$ Všimnime si, že platí $B\cap C\subseteq B$ a $B\cap C\subseteq C$.a) $A\subseteq B\cap C$ práve vtedy, keď $A\subseteq B$ a $A\subseteq C$;
(Tieto tvrdenia sú vcelku jasné, prípadne sa dajú overiť na základe tautológie $b\land c\Rightarrow b$.)
Ak platí $A\subseteq B\cup C$ a súčasne $B\cup C\subseteq B$, tak dostávame, že platí aj $A\subseteq B$.
(Využili sme tranzitívnosť inklúzie, ktorú sme už dokazovali na cvičení. T.j. využili sme tvrdenie $X\subseteq Y \land Y\subseteq Z \Rightarrow X\subseteq Z$.)
Podobne dokážeme, že z $A\subseteq B\cup C$ vyplýva $A\subseteq C$.
Ukázali sme, že ak $A\subseteq B\cup C$, tak platí $A\subseteq B$ aj $A\subseteq C$. Tým je dôkaz tejto implikácie hotový.
$\boxed{\Leftarrow}$ Predpokladajme, že $A\subseteq B$ a $A\subseteq C$. Ak si teraz zoberieme ľubovoľný prvok $a\in A$, tak tento prvok patrí do $B$ (lebo $A\subseteq B$) a patrí aj do $C$ (lebo $A\subseteq C$). To znamená, že $a\in B\cap C$.
Ukázali sme, že každý prvok z $A$ patrí do $B\cap C$. Tým je dokázaná inklúzia $A\subseteq B\cap C$
Mnohí z vás snažili zadané tvrdenia dokázať prepisom na základe definície a prevedením na výrok s kvantifikátormi resp. tautológiu. Skúsme si teda jednu časť úlohy ukázať aj takto.c) $A\cup B \subseteq C$ práve vtedy, keď $A\subseteq C$ a $B\subseteq C$;
Chceme teda ukázať ekvivalenciu výrokov
$(\forall x) (x\in A\cup B \Rightarrow x\in C)$
$(\forall x) (x\in A\Rightarrow x\in C) \land (\forall x) (x\in B\Rightarrow x\in C)$.
Skúsme teda prvý výrok postupne prepisovať
$(\forall x) (x\in A\cup B \Rightarrow x\in C)$ $\Leftrightarrow$
$(\forall x) (x\in A \lor x\in B \Rightarrow x\in C)$ $\overset{(1)}\Leftrightarrow$
$(\forall x) [(x\in A \Rightarrow x\in C) \land (x\in B \Rightarrow x\in C)]$ $\overset{(2)}\Leftrightarrow$
$(\forall x) (x\in A \Rightarrow x\in C) \land (\forall x) (x\in B \Rightarrow x\in C)]$
Na mieste označenom (1) sme využili tautológiu $(a\lor b \Rightarrow c) \Leftrightarrow (a\Rightarrow c) \land (b\Rightarrow c)$.
Na mieste označenom (2) sme využili fakt, že platí $(\forall x)(P(x)\land Q(x))\Leftrightarrow (\forall x)P(x) \land (\forall x)Q(x)$. (Väčšina z odovzdaných riešení, kde bola úloha riešená podobným spôsobom, kvantifikátory vôbec neriešila.)
Kontrapríklad
Tvrdenia v častiach b) a d) neplatia, treba uviesť konkrétny kontrapríklad. (Nájsť vhodné množiny A,B,C.)
Toto tvrdenie neplatí. Jednoduchý kontrapríklad je napríklad $A=\{0,1\}$, $B=\{0\}$, $C=\{1\}$.b) $A\subseteq B\cup C$ práve vtedy, keď $A\subseteq B$ alebo $A\subseteq C$;
V odovzdaných riešeniach sa vyskytol takýto argument, ktorý by mal dokazovať, že to platí:
Problém s týmto argumentom je takýto: Na základe uvedenej tautológie by sme skutočne mohli zdôvodniť, žeNajprv overíme, že $p\Rightarrow q\lor r \Leftrightarrow (p\Rightarrow r) \lor (p\Rightarrow q)$ je tautológia.
Potom na základe toho, ak ju použijeme pre výroky $p\equiv x\in A$, $q\equiv x\in B$, $r\equiv x\in C$ dostaneme
$$(\forall x) (x\in A \Rightarrow x\in B\lor x\in C) \Leftrightarrow (\forall x) (x\in A \Rightarrow x\in B) \lor (\forall x) (x\in A \Rightarrow x\in C)$$
O tomto sa už dá ukázať, že to je ekvivalentné s pôvodným tvrdením.
$(\forall x) (x\in A \Rightarrow x\in B\lor x\in C) \Leftrightarrow (\forall x) [(x\in A \Rightarrow x\in B) \lor (x\in A \Rightarrow x\in C)]$.
Výrok, ktorý sme dostali na pravej strane však nie je to isté ako $(\forall x) (x\in A \Rightarrow x\in B) \lor (\forall x) (x\in A \Rightarrow x\in C)$.
Môžete si rozmyslieť, že vo všeobecnosti výroky
$(\forall x) (P(x)\lor Q(x))$ a $(\forall x)P(x) \lor (\forall x)Q(x)$
nie sú ekvivalentné. (Platí však jedna implikácia.)
Ani toto tvrdenie neplatí. Jednoduchý kontrapríklad môžeme dostať ak vezmeme $C=\emptyset$ a za $A$, $B$ zvolíme ľubovoľné dve neprázdne množiny. Napríklad $A=\{0\}$, $B=\{1\}$.d) $A\cap B \subseteq C$ práve vtedy, keď $A\subseteq C$ alebo $B\subseteq C$.
Dôvod, prečo neprejde argument na základe tautológie je podobný ako v časti b).
Zápisy:
V jednej z odovzdaných úloh sa vyskytol zápis tvaru
$x\in (A\subseteq B\cup C)$.
Takýto zápis nedáva zmysel.
Znak patrí ($\in$) sa môže napísať medzi prvok a množinu.
Zápis $A\subseteq B\cup C$ je výrok (je to skrátený zápis toho, že $(\forall x)(x\in A \Rightarrow x\in B\lor x\in C)$.)