Witam!
Mam problem z pewnym zadaniem.
Mianowicie:
Niech \(\displaystyle{ R_{i} \subseteq X\times X}\) dla \(\displaystyle{ i \in I}\) oraz \(\displaystyle{ S\subseteq X\times Y}\) będą relacjami. Pokazać, że zachodzi inkluzja
\(\displaystyle{ S\circ \left( \bigcap_{i\in I}R_{i} \right) \subseteq \bigcap_{i\in I}(S \circ R_{i})}\)
oraz podać kontrprzykład, że inkluzji nie można zastąpić równością. Odpowiedź uzasadnić.
relacje zlozone, dowod inkluzji
-
kjurek
- Użytkownik
- Posty: 12
- Rejestracja: 12 lip 2011, o 16:20
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3 razy
relacje zlozone, dowod inkluzji
Ostatnio zmieniony 23 lis 2011, o 20:31 przez Jan Kraszewski, łącznie zmieniany 3 razy.
Powód: Znak należenia to \in. Skaluj nawiasy.
Powód: Znak należenia to \in. Skaluj nawiasy.
-
Qń
- Użytkownik
- Posty: 9724
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2633 razy
relacje zlozone, dowod inkluzji
Chyba raczej również \(\displaystyle{ S\subseteq X\times X}\).
Spróbuj napisać co z definicji oznacza, że \(\displaystyle{ (x,y)}\) należy do lewej, a co że do prawej strony i zwróć uwagę na kolejność kwantyfikatorów.
Q.
Spróbuj napisać co z definicji oznacza, że \(\displaystyle{ (x,y)}\) należy do lewej, a co że do prawej strony i zwróć uwagę na kolejność kwantyfikatorów.
Q.
-
BlackSlash
- Użytkownik
- Posty: 17
- Rejestracja: 6 wrz 2010, o 15:44
- Płeć: Mężczyzna
- Lokalizacja: Wawa
- Podziękował: 1 raz
relacje zlozone, dowod inkluzji
@Qń Również mam takie zadanie i \(\displaystyle{ S\subseteq X\times Y}\) więc raczej tak ma być.
Co do zadania również prosiłbym o pomoc. Ja lewą rozpisałbym tak:
\(\displaystyle{ \left \{(x,z)\in S\circ\left (\bigcap_{i\in I}R_i \right ) \right \}\Leftrightarrow \left \{\exists _{y\in S}:(x,z)\in\left (\bigcap_{i\in I}R_i \right )\wedge (z,y)\in S \right \}\Leftrightarrow\\ \Leftrightarrow \left \{\exists _{y\in S}:\forall_{i\in I} (x,z)\in R_i\wedge (z,y)\in S \right \}}\)
A prawą tak:
\(\displaystyle{ \left \{(x,z)\in \bigcap_{i\in I}\left (S\circ R_i \right ) \right \}\Leftrightarrow \left \{\forall_{i\in I}(x,z)\in S\circ R_i\right \}\Leftrightarrow \left \{\forall_{i\in I}\exists_{y\in S}:(x,z)\in R_i \wedge (z,y)\in S\right \}}\)
Teraz z prawa przestawiania kwantyfikatorów...
\(\displaystyle{ \exists_{x\in X} \forall_{y\in Y}R(x,y)\Rightarrow \forall_{y\in Y} \exists_{x\in X}R(x,y)}\)
...przekształcam lewą stronę, co daje:
\(\displaystyle{ \left \{\forall_{i\in I}\exists_{y\in S}:(x,z)\in R_i \wedge (z,y)\in S\right \}}\)
Jak widać lewa i prawa są takie same więc strona lewa zawiera się w prawej (prawa w lewej nie, bo w prawie przestawiania jest implikacja, a nie równoważność, przez co nie możemy przekształcić prawej strony do lewej, co potwierdza, że inkluzji nie można zastąpić równością).
Prosiłbym o sprawdzenie i ew. podanie jeszcze kontrprzykładu, bo nie mogę żadnego wymyślić.
Co do zadania również prosiłbym o pomoc. Ja lewą rozpisałbym tak:
\(\displaystyle{ \left \{(x,z)\in S\circ\left (\bigcap_{i\in I}R_i \right ) \right \}\Leftrightarrow \left \{\exists _{y\in S}:(x,z)\in\left (\bigcap_{i\in I}R_i \right )\wedge (z,y)\in S \right \}\Leftrightarrow\\ \Leftrightarrow \left \{\exists _{y\in S}:\forall_{i\in I} (x,z)\in R_i\wedge (z,y)\in S \right \}}\)
A prawą tak:
\(\displaystyle{ \left \{(x,z)\in \bigcap_{i\in I}\left (S\circ R_i \right ) \right \}\Leftrightarrow \left \{\forall_{i\in I}(x,z)\in S\circ R_i\right \}\Leftrightarrow \left \{\forall_{i\in I}\exists_{y\in S}:(x,z)\in R_i \wedge (z,y)\in S\right \}}\)
Teraz z prawa przestawiania kwantyfikatorów...
\(\displaystyle{ \exists_{x\in X} \forall_{y\in Y}R(x,y)\Rightarrow \forall_{y\in Y} \exists_{x\in X}R(x,y)}\)
...przekształcam lewą stronę, co daje:
\(\displaystyle{ \left \{\forall_{i\in I}\exists_{y\in S}:(x,z)\in R_i \wedge (z,y)\in S\right \}}\)
Jak widać lewa i prawa są takie same więc strona lewa zawiera się w prawej (prawa w lewej nie, bo w prawie przestawiania jest implikacja, a nie równoważność, przez co nie możemy przekształcić prawej strony do lewej, co potwierdza, że inkluzji nie można zastąpić równością).
Prosiłbym o sprawdzenie i ew. podanie jeszcze kontrprzykładu, bo nie mogę żadnego wymyślić.
Ostatnio zmieniony 24 lis 2011, o 01:12 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Nie pisz takich długich wyrażeń w LaTeXu w jednej linii.
Powód: Nie pisz takich długich wyrażeń w LaTeXu w jednej linii.
-
Jan Kraszewski
- Administrator
- Posty: 36051
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 6 razy
- Pomógł: 5341 razy
relacje zlozone, dowod inkluzji
Myślisz całkiem dobrze, a w kwestii zapisu:
1. Wymaż te nawiasy klamrowe, bo sugerują one jakieś zbiory. Są zupełnie zbędne, a mogą wprowadzać w błąd.
2. Pomyliłeś się stosując definicję złożenia, zamieniając \(\displaystyle{ y}\) z \(\displaystyle{ z}\).
3. Istnieje nie \(\displaystyle{ y\in S}\), tylko \(\displaystyle{ y\in X}\).
Poza tym
4. To, że w "prawie przestawiania" jest implikacja nie wystarcza formalnie do stwierdzenia braku równości. Kontrprzykład jest niezbędny.
JK
1. Wymaż te nawiasy klamrowe, bo sugerują one jakieś zbiory. Są zupełnie zbędne, a mogą wprowadzać w błąd.
2. Pomyliłeś się stosując definicję złożenia, zamieniając \(\displaystyle{ y}\) z \(\displaystyle{ z}\).
3. Istnieje nie \(\displaystyle{ y\in S}\), tylko \(\displaystyle{ y\in X}\).
Poza tym
4. To, że w "prawie przestawiania" jest implikacja nie wystarcza formalnie do stwierdzenia braku równości. Kontrprzykład jest niezbędny.
JK