Dowody zbiorów

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
vaker2001
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 16 sty 2020, o 19:06
Płeć: Mężczyzna
wiek: 20

Dowody zbiorów

Post autor: vaker2001 » 16 sty 2020, o 19:26

Witam, jutro mam kolokwium poprawkowe z Logiki i Teorii Mnogości, część dotyczącą logiki umiem zrobić, jednak dowodzenie zadań mi nie wychodzi.
Największy kłopot mam z tymi zadaniami:
1.
Udowodnić, że \(\displaystyle{ A \cap B}\) jest największym zbiorem zawartym jednocześnie w \(\displaystyle{ A}\) i \(\displaystyle{ B}\). to znaczy, że każdy zbiór zawarty w \(\displaystyle{ A}\) i \(\displaystyle{ B}\) jest zawarty jednocześnie w \(\displaystyle{ A \cap B}\).
Próbowałem to zapisać w ten sposób, jednak jest on chyba błędny: \(\displaystyle{ A \cap B \Leftrightarrow A \cup B}\)
Trzeba to udowodnić stawiając tezę i założenie oraz że lewa strona jest równa prawej i na odwrót.
2.
Udowodnij, że dla dowolnych zbiorów \(\displaystyle{ X,Y,A,B}\):
\(\displaystyle{ (X \cap Y = \emptyset \vee A \cap B = \emptyset) \Rightarrow (X \times A) \cap (Y \times B) = \emptyset}\)
Tego zadania nie potrafię zrobić. Trzeba je udowodnić w ten sam sposób co poprzednie.
Ostatnio zmieniony 16 sty 2020, o 19:43 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Jan Kraszewski
Administrator
Administrator
Posty: 25991
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4350 razy

Re: Dowody zbiorów

Post autor: Jan Kraszewski » 16 sty 2020, o 20:13

vaker2001 pisze:
16 sty 2020, o 19:26
Próbowałem to zapisać w ten sposób, jednak jest on chyba błędny: \(\displaystyle{ A \cap B \Leftrightarrow A \cup B}\)
Tak, to nie ma sensu. Jest zarówno niepoprawne formalnie, jak i nie ma żadnego związku z zadaniem.
vaker2001 pisze:
16 sty 2020, o 19:26
Trzeba to udowodnić stawiając tezę i założenie oraz że lewa strona jest równa prawej i na odwrót.
A skąd. Wcale nie to trzeba zrobić.
Przede wszystkim trzeba zrozumieć zadanie.

Masz pokazać, że \(\displaystyle{ A \cap B \subseteq A, A \cap B \subseteq B}\) oraz dla dowolnego zbioru \(\displaystyle{ C}\) takiego, że \(\displaystyle{ C \subseteq A}\) i \(\displaystyle{ C \subseteq B}\) mamy \(\displaystyle{ C \subseteq A \cap B}\).
vaker2001 pisze:
16 sty 2020, o 19:26
Udowodnij, że dla dowolnych zbiorów \(\displaystyle{ X,Y,A,B}\):
\(\displaystyle{ (X \cap Y = \emptyset \vee A \cap B = \emptyset) \Rightarrow (X \times A) \cap (Y \times B) = \emptyset}\)
Tego zadania nie potrafię zrobić. Trzeba je udowodnić w ten sam sposób co poprzednie.
Zdecydowanie nie w ten sam sposób, bo to zupełnie inne zadanie.

Najprościej udowodnić to twierdzenie nie wprost.

JK

vaker2001
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 16 sty 2020, o 19:06
Płeć: Mężczyzna
wiek: 20

Re: Dowody zbiorów

Post autor: vaker2001 » 16 sty 2020, o 23:20

Jan Kraszewski pisze:
16 sty 2020, o 20:13
Masz pokazać, że \(\displaystyle{ A \cap B \subseteq A, A \cap B \subseteq B}\) oraz dla dowolnego zbioru \(\displaystyle{ C}\) takiego, że \(\displaystyle{ C \subseteq A}\) i \(\displaystyle{ C \subseteq B}\) mamy \(\displaystyle{ C \subseteq A \cap B}\).
Jak to zapisać w jednej formule? W ten sposób?
\(\displaystyle{ (A \cap B \subseteq A \wedge A \cap B \subseteq B) \Leftrightarrow (C \subseteq A \wedge C \subseteq B \Rightarrow C \subseteq A \cap B)
}\)

Nie jestem pewien co do tej implikacji.
Jan Kraszewski pisze:
16 sty 2020, o 20:13
Najprościej udowodnić to twierdzenie nie wprost.
Mógłby pan pokazać na tym zadaniu jak wygląda taki dowód?
Ostatnio zmieniony 16 sty 2020, o 23:30 przez vaker2001, łącznie zmieniany 2 razy.

Jan Kraszewski
Administrator
Administrator
Posty: 25991
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4350 razy

Re: Dowody zbiorów

Post autor: Jan Kraszewski » 16 sty 2020, o 23:26

vaker2001 pisze:
16 sty 2020, o 23:20
Jak to zapisać w jednej formule?
Tego NIE NALEŻY zapisywać w jednej formule, tylko dowieść. Masz do uzasadnienia trzy proste fakty:
1. \(\displaystyle{ A \cap B \subseteq A,}\)
2. \(\displaystyle{ A \cap B \subseteq B}\)
3. dla dowolnego zbioru \(\displaystyle{ C}\) takiego, że \(\displaystyle{ C \subseteq A}\) i \(\displaystyle{ C \subseteq B}\) mamy \(\displaystyle{ C \subseteq A \cap B}\).
A te uzasadnienia to nie są manipulacje znaczkami.
vaker2001 pisze:
16 sty 2020, o 23:20
Jan Kraszewski pisze:
16 sty 2020, o 20:13
Najprościej udowodnić to twierdzenie nie wprost.
Czyli podstawić pod \(\displaystyle{ A}\) np \(\displaystyle{ \{1,2\}}\) itp?
No skąd. Żadnego podstawiania.

Wiesz w ogóle, co to jest i na czym polega "dowód nie wprost"? Po semestrze wykładu zdecydowanie powinieneś.

JK

vaker2001
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 16 sty 2020, o 19:06
Płeć: Mężczyzna
wiek: 20

Re: Dowody zbiorów

Post autor: vaker2001 » 16 sty 2020, o 23:32

Nie wiem na czym polega dowód nie wprost, nie było mnie na tych zajęciach z przyczyn na które nie miałem wpływu, próbowałem coś zrozumieć z notatek ale nie jestem w stanie tego się nauczyć. Jeżeli ma pan czas to prosiłbym o zrobienie takiego dowodu nie wprost, wtedy wydedukuję jak taki dowód przeprowadzić.

Jan Kraszewski
Administrator
Administrator
Posty: 25991
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4350 razy

Re: Dowody zbiorów

Post autor: Jan Kraszewski » 17 sty 2020, o 00:08

vaker2001 pisze:
16 sty 2020, o 23:32
Jeżeli ma pan czas to prosiłbym o zrobienie takiego dowodu nie wprost, wtedy wydedukuję jak taki dowód przeprowadzić.
Słabo to widzę, ale dobrze.

Dowód nie wprost polega na przypuszczeniu fałszywości tezy i dojściu do sprzeczności (często jest to sprzeczność z założeniami, ale nie zawsze). Otrzymana sprzeczność świadczy o tym, że przypuszczenie o fałszywości tezy było nieuprawnione, zatem teza jest prawdziwa. Żeby poprawnie przeprowadzić dowód nie wprost należy umieć zidentyfikować tezę, umieć ją zaprzeczyć i umieć poprawnie wnioskować.
vaker2001 pisze:
16 sty 2020, o 19:26
Udowodnij, że dla dowolnych zbiorów \(\displaystyle{ X,Y,A,B}\):
\(\displaystyle{ \blue{(X \cap Y = \emptyset \vee A \cap B = \emptyset)} \Rightarrow \red{(X \times A) \cap (Y \times B) = \emptyset}}\)
(to czerwone to teza Twojego twierdzenia, natomiast na niebiesko masz założenia)

Przypuśćmy nie wprost, że \(\displaystyle{ (X \times A) \cap (Y \times B) \ne \emptyset}\). Oznacza to, że istnieje para uporządkowana \(\displaystyle{ \left\langle x,y\right\rangle\in (X \times A) \cap (Y \times B)}\) (bo tak się składa, że mamy tu do czynienia ze zbiorami par uporządkowanych). Z def. przekroju zbiorów oznacza to, że \(\displaystyle{ \left\langle x,y\right\rangle\in X \times A}\) i \(\displaystyle{ \left\langle x,y\right\rangle\in Y \times B}\). Korzystając dwukrotnie z def. iloczynu kartezjańskiego otrzymujemy \(\displaystyle{ x\in X}\) i \(\displaystyle{ y\in A}\) i \(\displaystyle{ x\in Y}\) i \(\displaystyle{ y\in B}\). Wobec tego \(\displaystyle{ x\in X\cap Y}\) i \(\displaystyle{ y\in A\cap B}\), co oznacza, że \(\displaystyle{ X\cap Y \ne \emptyset}\) i \(\displaystyle{ A\cap B \ne \emptyset}\). Ale to jest sprzeczne z założeniem \(\displaystyle{ (X \cap Y = \emptyset \vee A \cap B = \emptyset)}\). Otrzymana sprzeczność kończy dowód twierdzenia.

JK

ODPOWIEDZ