DU4 inklúzie - LS 2017/18

[Martin Sleziak]

Pravdepodobne budem opakovať nejaké veci, ktoré sú aj v starších topicoch:
viewtopic.php?t=1056
viewtopic.php?t=534
Aj tak tu ale niečo napíšem.
Zadanie: http://msleziak.com/vyuka/2017/temno/du04.pdf

Toto je presne skopírované z jednej d.ú. (vynechal som iba tabuľku, v ktorej bola overená záverečná tautológia):

\begin{align*}
A\cap B \subseteq C &\Leftrightarrow A\subseteq C \lor B\subseteq C\\
(\forall z) (z\in A\cap B \Rightarrow z\in C) &\Leftrightarrow ((\forall z) z\in A \Rightarrow z\in C) \lor ((\forall z)z\in B\Rightarrow z\in C)\\
(z\in A\land z\in B \Rightarrow z\in C) &\Leftrightarrow (z\in A \Rightarrow z\in C) \lor (z\in B\Rightarrow z\in C)\\
[(a\land b)\Rightarrow c] &\Leftrightarrow [(a\Rightarrow c)\lor(b\Rightarrow c)]
\end{align*}
Ekvivalencia je pravdivá.

Ľahko sa dá presvedčiť, že $A=\{1,2\}$, $B=\{1,3\}$ a $C=\{1\}$ je kontrapríklad na tvrdenie, ktoré by tu malo byť dokázané.
Kde je v uvedenom argumente chyba?

Spoiler:

Všimnite si, že medzi druhým a tretím riadkom zmizli kvantifikátory.
S patričným zdôvodnením by to celé fungovalo o.k., ak by bola pravda že
$$(\forall z)P(z) \lor (\forall z) Q(z)\Leftrightarrow (\forall z) (P(z)\lor Q(z)).$$
To však neplatí, teda si nemôžeme dovoliť nahradiť výrok
$$((\forall z) z\in A \Rightarrow z\in C) \lor ((\forall z)z\in B\Rightarrow z\in C)$$
výrokom
$$(\forall z)((z\in A \Rightarrow z\in C) \lor (z\in B\Rightarrow z\in C)).$$

Veľmi podobné úvahy používali aj tí z vás, ktorí tvrdili že majú dôkaz, že $A\subseteq B\cup C$ je ekvivalentné s $(A\subseteq B) \lor (A\subseteq C)$. (Tu už nechám na vás, aby ste našli kontrapríklad.)

[Martin Sleziak]

A asi sa tu oplatí zopakovať to, čo som už hovoril viackrát: Nebojte sa veci zapísať slovne.
Síce postupnosť niekoľkých ekvivalencií vyzerá vcelku elegantne - a ak je aj správne, tak z takéhoto zápisu človek, ktorý ho číta, asi celkom dobre pochopí čo ste chceli povedať. Ale určite by nebolo dobré, aby ste sa len naučili písať postupnosti symbolov, o ktorých sa vám zdá že by možno mohli byť správne a ktoré sa podobajú na niečo čo ste videli inde. (Inak povedané, bolo by dobré aby ste rozumeli dôkazu, ktorý ste zapísali. Ak lepšie rozumiete slovenému zápisu, napíšte dôkaz radšej slovne.)

Ako príklad môžeme ukázať jednu z implikácií z predošlého tvrdenia. (Tú, ktoré naozaj platí.)

Ak $A\subseteq C$ a $B\subseteq C$, tak $A\cap B\subseteq C$.

Spoiler:

Dôkaz.Nech $x\in A\cap B$. To znamená, že $x\in A$ a súčasne $x\in B$. Pretože $A\subseteq C$, tak z $x\in A$ vyplýva aj $x\in C$.

Ukázali sme, že každý prvok z $A\cap B$ patrí do $C$, a teda platí inklúzia $A\cap B\subseteq C$. $\square$

Iná možnosť dôkazu: Najprv ukážeme, že platí $A\cap B\subseteq A$. Ak vieme, že platí niečo takéto, tak z $A\cap B\subseteq A$ a $A\subseteq C$ vyplýva $A\cap B\subseteq C$.

Skúste sa zamyslieť nad tým, či by ste nejako podobne vedeli ukázať: Ak $A\subseteq C$ a $B\subseteq C$, tak $A\cup B\subseteq C$. (Toto je vlastne polovica z úlohy, ktorá bola v jednej skupine.)