Logika - Zadanie 140.

Równoważność ciągu formuł udowodnimy poprzez udowodnienie wszystkich implikacji „w prawo”.

1. A\subseteq B \Rightarrow A\cup B = B
   • Wykażmy zawieranie A\cup B \subseteq B.
   • Weźmy dowolne x \in A \cup B.
   • Z definicji sumy zbiorów mamy: x\in A \vee x \in B.
   • Rozważmy przypadek x\in B. Wtedy w sposób trywialny x\in B.
   • Wpp., x\in A. Ale ponieważ A\subseteq B, z definicji zawierania zbioru mamy: x\in B.
   • Ponieważ wybraliśmy dowolne x, udowodniliśmy zawieranie A\cup B \subseteq B.
   • Zawieranie A\cup B \supseteq B jest trywialne (a jeśli prowadzący się uprze, to powinieneś/powinnaś już sam(a) umieć to rozpisać)
   • Ponieważ prawdziwe są zawierania w obie strony, zbiory A\cup B i B są równe (przy założeniu A\subseteq B).
2. A \cup B = B \Rightarrow A\cap B = A
   • Wykażmy zawieranie A\cap B \subseteq A
   • Weźmy dowolne x \in A \cap B.
   • Z definicji przekroju zbiorów mamy: x\in A \wedge x\in B.
   • W szczególności, x \in B, a więc wobec wyboru dowolnego x, zawieranie zachodzi.
   • Wykażmy teraz A\cap B \supseteq A.
   • Weźmy dowolne x \in A.
   • Z poprzednika implikacji wiemy, że A \cup B \subseteq B, a więc w szczególności A \subseteq B (ponownie, pokazywanie tego jest zbędne)
   • Tak więc x\in B, czyli x \in A \wedge x\in B, co mieliśmy pokazać.
3. A\cap B = A \Rightarrow A \setminus B = \emptyset
   • W tym momencie prowadzący powinien się już odczepić, ale jeśli masz pecha, to wybierz dowolny x \in A\setminus B.
   • Z definicji różnicy zbiorów, należy on do A.
   • Z zawierania A\cap B \supseteq A mamy, że x\in B.
   • Tak więc x \in B \wedge x \not\in B - sprzeczność.
   • Wybierając dowolny element, doprowadziliśmy do sprzeczności, tak więc zbiór A\setminus B jest pusty.
4. A\setminus B = \emptyset \Rightarrow A\subseteq B
   • Weźmy dowolne x\in A.
   • Z dychotomii należenia, x\in B albo x \not\in B.
   • Ponieważ A\setminus B = \emptyset, \neg x\not\in B, więc x\in B.