Jak wykonać dowód ?

[laser15]

Proszę o pomoc z dowodami:

a)\(\displaystyle{ 2^A \cup 2^B \subset 2^{A \cup B}}\)
b)\(\displaystyle{ 2^A \cap 2^B \subset 2^{A \cap B}}\)
c)\(\displaystyle{ 2^{A \cup B}\subset 2^A \cup 2^B}\)
d)\(\displaystyle{ 2^{A \cap B}\subset 2^A \cap 2^B}\)
e)\(\displaystyle{ 2^{A \setminus B}\subset 2^A \setminus 2^B}\)
f)\(\displaystyle{ 2^A \setminus 2^B\subset 2^{A \setminus B}}\)


Jak je wykonać? Wiem jak zrobić gdy sobie sam wymyślę zbiory, ale nie wiem jak dla dowolnych. Proszę o pomoc.-- 31 sty 2013, o 00:38 --Proszę o jakieś rady.

[rafalpw]

a) Ustalamy dowolny zbiór \(\displaystyle{ X \in 2^A \cup 2^B}\)

\(\displaystyle{ X \in 2^A \cup 2^B \Leftrightarrow X \in 2^A \vee X \in 2^B \Leftrightarrow X \subseteq A \vee X \subseteq B \Rightarrow X \subseteq A \cup B \Leftrightarrow X \in 2^{A \cup B}}\)

Zatem \(\displaystyle{ \forall_{X} X \in 2^A \cup 2^B \Rightarrow X \in 2^{A \cup B} \Leftrightarrow 2^A \cup 2^B \subseteq 2^{A \cup B}}\)

Reszta analogicznie.

[Ciastko]

A co zrobić jeśli c jest fałszywe? Tzn dostaję na egzaminie "Sprawdź czy to prawda" i jak powinienem się do tego zabrać?

[rafalpw]

Aby pokazać, że jakieś stwierdzenie jest fałszywe najłatwiej podać kontrprzykład.-- 31 sty 2013, o 23:42 --Dla przykładu c) Weźmy \(\displaystyle{ A=\left\{ 1\right\}}\)
\(\displaystyle{ B=\left\{ 2\right\}}\) Wtedy \(\displaystyle{ 2^A \cup 2^B=\left\{ \emptyset , \left\{ 1\right\},\left\{ 2\right\} \right\}}\)
a \(\displaystyle{ 2^{A \cup B}=\left\{ \emptyset, \left\{ 1\right\},\left\{ 2\right\} ,\left\{ 1,2\right\} \right\}}\)

Zatem widać, że \(\displaystyle{ 2^{A \cup B} \not\subset 2^A \cup 2^B}\)

[Ciastko]

Tak, tylko czy to wystarczy? Zrobiłem sobie dokładnie taki kontrprzykład i stwierdziłem to samo, tylko pytanie brzmi czy zawsze powinniśmy to sprawdzać i czy metodą wnioskowania tak jak ty to pokazałeś potrafilibyśmy dojść do sprzeczności (bez pokazywania kontrprzykładu).

[rafalpw]

Jak najbardziej wystarczy. Może i się da, ale po co sobie komplikować życie? Tak naprawdę zrobiliśmy formalny dowód, że nie jest to prawda. Następujący dowód będzie przeprowadzony dla naszych ustalonych wcześniej zbiorów \(\displaystyle{ A,B}\)

Twierdzenie: \(\displaystyle{ 2^{A \cup B}\subset 2^A \cup 2^B \Leftrightarrow \forall_{X}X \in 2^{A \cup B} \Rightarrow X \in 2^A \cup 2^B}\) Chcemy pokazać, że nie jest prawdziwe, czyli:

\(\displaystyle{ \neg \left(\forall_{X}X \in 2^{A \cup B} \Rightarrow X \in 2^A \cup 2^B \right) \Leftrightarrow \exists_{X}X \in 2^{A \cup B} \wedge X\not\in 2^A \cup 2^B}\)

To jest nasza teza, ale weźmy \(\displaystyle{ X=\left\{1,2 \right\}}\) Wtedy \(\displaystyle{ X \in 2^{A \cup B} \wedge X\not\in 2^A \cup 2^B}\) Zatem zdanie \(\displaystyle{ \exists_{X}X \in 2^{A \cup B} \wedge X\not\in 2^A \cup 2^B}\) jest prawdziwe, czyli zdanie \(\displaystyle{ 2^{A \cup B}\subset 2^A \cup 2^B}\) jest fałszywe, a to chcieliśmy pokazać.

[Jan Kraszewski]

Tak, tylko czy to wystarczy? Zrobiłem sobie dokładnie taki kontrprzykład i stwierdziłem to samo, tylko pytanie brzmi czy zawsze powinniśmy to sprawdzać i czy metodą wnioskowania tak jak ty to pokazałeś potrafilibyśmy dojść do sprzeczności (bez pokazywania kontrprzykładu).

Nie tylko wystarczy, ale to w większości wypadków jedyny poprawny dowód. Twoja wątpliwość wskazuje na to, że nie widzisz różnicy pomiędzy zdaniami \(\displaystyle{ (\exists x)\neg\varphi(x)}\) i \(\displaystyle{ (\forall x)\neg\varphi(x)}\).

JK

[Ciastko]

Tak, już zrozumiałem


Mam tylko pytanie, czy e jest prawdziwe?

[Jan Kraszewski]

Nie. Można nawet pokazać więcej - nie jest prawdziwe dla żadnych zbiorów. Innymi słowy, jakiekolwiek weźmiesz \(\displaystyle{ A}\) i \(\displaystyle{ B}\), będzie to dobry kontrprzykład.

JK