Matematyka.pl

Podać przykład takiej niepustej relacji przechodniej (i też przykład nieprzechodniej) \(\displaystyle{ r}\) w zbiorze \(\displaystyle{ \mathbb{N}}\), że relacja \(\displaystyle{ r^{\exists}}\) określona w zbiorze \(\displaystyle{ \mathcal{P}(\mathbb{N})}\) warunkiem:

Nie zgubiłeś gdzieś drugiej połowy zdania?

Bardzo przepraszam, troche nie tak napisałem. Ale nie wiem, jak zmienić swój post?

W zadanku chodziło o to, że \(\displaystyle{ r}\) - przechodnia (bez nieprzychodniej). I trzeba znalesć \(\displaystyle{ r^{\exists}}\) w dwóch przypadkach: kiedy \(\displaystyle{ r^{\exists}}\) przechodnia i nieprzechodnia.

Załóżmy, że \(\displaystyle{ r}\) jest relacją przechodnią. Jeśli \(\displaystyle{ r^{\exists}}\) ma być nieprzechodnia, to muszą istnieć zbiory \(\displaystyle{ X, Y, Z \subseteq \mathbb{N}}\), takie że \(\displaystyle{ X \mathrel{r^{\exists}} Y}\) i \(\displaystyle{ Y \mathrel{r^{\exists}} Z}\), ale \(\displaystyle{ \neg (X \mathrel{r^{\exists}} Z)}\). Z definicji oznacza to, że:

\(\displaystyle{ \bullet}\) \(\displaystyle{ x_0 \mathrel{r} y_0}\) dla pewnych \(\displaystyle{ x_0 \in X}\), \(\displaystyle{ y_0 \in Y}\);

\(\displaystyle{ \bullet}\) \(\displaystyle{ y_1 \mathrel{r} z_0}\) dla pewnych \(\displaystyle{ y_1 \in Y}\), \(\displaystyle{ z_0 \in Z}\);

\(\displaystyle{ \bullet}\) \(\displaystyle{ \neg (x \mathrel{r} z)}\) dla każdych \(\displaystyle{ x \in X}\), \(\displaystyle{ z \in Z}\).

W takiej sytuacji niemożliwe jest, by \(\displaystyle{ y_0 = y_1}\), bo wtedy \(\displaystyle{ x_0 \mathrel{r} y_0 = y_1 \mathrel{r} z_0}\), więc z przechodniości mielibyśmy \(\displaystyle{ x_0 \mathrel{r} z_0}\), co przeczyłoby trzeciemu warunkowi. A skoro to my mamy znaleźć zbiory o powyższych własnościach, to najprościej przyjąć \(\displaystyle{ X = \{ x_0 \}}\), \(\displaystyle{ Y = \{ y_0, y_1 \}}\) oraz \(\displaystyle{ Z = \{ z_0 \}}\).

W ten sposób otrzymujemy przykład: relacja \(\displaystyle{ r = \{ (1, 2), (3, 4) \}}\) jest przechodnia, a \(\displaystyle{ r^{\exists}}\) jest nieprzechodnia, bo \(\displaystyle{ \{ 1 \} \mathrel{r^{\exists}} \{ 2, 3 \}}\) i \(\displaystyle{ \{ 2, 3 \} \mathrel{r^{\exists}} \{ 4 \}}\), ale \(\displaystyle{ \neg ( \{ 1 \} \mathrel{r^{\exists}} \{ 4 \} )}\).


Aby \(\displaystyle{ r^{\exists}}\) była przechodnia, najprościej za \(\displaystyle{ r}\) przyjąć relację pełną. Można wykazać, że w ogólności \(\displaystyle{ r^{\exists}}\) jest przechodnia dokładnie wtedy, gdy \(\displaystyle{ r = A \times B}\) dla pewnych \(\displaystyle{ A, B \subseteq \mathbb{N}}\).

Aby \(\displaystyle{ r^{\exists}}\) była przechodnia, najprościej za \(\displaystyle{ r}\) przyjąć relację pełną. Można wykazać, że w ogólności \(\displaystyle{ r^{\exists}}\) jest przechodnia dokładnie wtedy, gdy \(\displaystyle{ r = A \times B}\) dla pewnych \(\displaystyle{ A, B \subseteq \mathbb{N}}\).

Czyli można wziąć dowolną pełną relację \(\displaystyle{ r}\)? Czy mógłby Pan podać przykład takiej relacji?

Też nie rozumiem jak udowodnić, że

w ogólności \(\displaystyle{ r^{\exists}}\) jest przechodnia dokładnie wtedy, gdy \(\displaystyle{ r = A \times B}\) dla pewnych \(\displaystyle{ A, B \subseteq \mathbb{N}}\)

? I też czy znaczy to, że dla dowolnej \(\displaystyle{ r}\) \(\displaystyle{ r^{\exists}}\) jest przechodnia?

Awram pisze: ↑30 lis 2023, o 19:09Czyli można wziąć dowolną pełną relację \(\displaystyle{ r}\)? Czy mógłby Pan podać przykład takiej relacji?

Jest tylko jedna relacja pełna, więc tu nie masz żadnego wyboru - relacja pełna na zbiorze \(\displaystyle{ X}\) to relacja \(\displaystyle{ r=X\times X.}\)

Awram pisze: ↑30 lis 2023, o 19:09I też czy znaczy to, że dla dowolnej \(\displaystyle{ r}\) \(\displaystyle{ r^{\exists}}\) jest przechodnia?

Widzę, że masz pewne kłopoty z odczytywaniem treści matematycznej: skoro jest napisane, że relacja \(\displaystyle{ r^{\exists}}\) jest przechodnia dokładnie wtedy, gdy \(\displaystyle{ \red{r = A \times B}}\) dla pewnych \(\displaystyle{ \red{A, B \subseteq \mathbb{N}}}\), to znaczy to, że czerwony warunek określa jednoznacznie, dla których relacji \(\displaystyle{ r}\) relacja \(\displaystyle{ r^{\exists}}\) jest przechodnia. Twoje pytanie sugeruje, że wydaje Ci się, iż każda relacja na zbiorze \(\displaystyle{ \NN}\) spełnia czerwony warunek, co oczywiście nie jest prawdą.

JK

Jan Kraszewski pisze: ↑30 lis 2023, o 19:33 Widzę, że masz pewne kłopoty z odczytywaniem treści matematycznej: skoro jest napisane, że relacja \(\displaystyle{ r^{\exists}}\) jest przechodnia dokładnie wtedy, gdy \(\displaystyle{ \red{r = A \times B}}\) dla pewnych \(\displaystyle{ \red{A, B \subseteq \mathbb{N}}}\), to znaczy to, że czerwony warunek określa jednoznacznie, dla których relacji \(\displaystyle{ r}\) relacja \(\displaystyle{ r^{\exists}}\) jest przechodnia. Twoje pytanie sugeruje, że wydaje Ci się, iż każda relacja na zbiorze \(\displaystyle{ \NN}\) spełnia czerwony warunek, co oczywiście nie jest prawdą.

Teraz rozumiem więcej. Dziękuje!

Dodano po 36 sekundach:
Mam coś takiego dla (a):
(a) Jeśli \(\displaystyle{ r^{\exists}}\) ma być przechodnia, to muszą istnieć zbiory \(\displaystyle{ X, Y, Z \subseteq \mathbb{N}}\), takie że \(\displaystyle{ (X \mathrel{r^{\exists}} Y)}\), i \(\displaystyle{ (Y \mathrel{r^{\exists}} Z)}\), i \(\displaystyle{ (X \mathrel{r^{\exists}} Z)}\). Z definicji oznacza to, że:
1. \(\displaystyle{ x_0 \mathrel{r} y_0}\) dla pewnych \(\displaystyle{ x_0 \in X}\), \(\displaystyle{ y_0 \in Y}\);
2. \(\displaystyle{ y_0 \mathrel{r} z_0}\) dla pewnych \(\displaystyle{ y_0 \in Y}\), \(\displaystyle{ z_0 \in Z}\);
3. \(\displaystyle{ x_0 \mathrel{r} z_0}\) dla pewnych \(\displaystyle{ x_0 \in X}\), \(\displaystyle{ z_0 \in Z}\).
Żeby \(\displaystyle{ r^{\exists}}\) była przechodnia, najprościej przyjąć \(\displaystyle{ X = \{ x_0 \}, Y = \{ y_0, y_0 \} }\) oraz \(\displaystyle{ Z = \{ z_0 \}}\). W ten sposób otrzymujemy przykład:
Relacja \(\displaystyle{ r = \{(2, 1), (1, 3)\}}\) jest przechodnia i \(\displaystyle{ r^{\exists}}\) jest przechodnia, bo \(\displaystyle{ \{2\} \mathrel{r^{\exists}} \{1, 1\}}\), i \(\displaystyle{ \{1, 1\} \mathrel{r^{\exists}} \{3\}}\), i \(\displaystyle{ \{2\} \mathrel{r^{\exists}} \{3\}}\).
Czy moje rozumowanie jest poprawne?

Awram pisze: ↑30 lis 2023, o 20:45Mam coś takiego dla (a):
(a) Jeśli \(\displaystyle{ r^{\exists}}\) ma być przechodnia, to muszą istnieć zbiory \(\displaystyle{ X, Y, Z \subseteq \mathbb{N}}\), takie że \(\displaystyle{ (X \mathrel{r^{\exists}} Y)}\), i \(\displaystyle{ (Y \mathrel{r^{\exists}} Z)}\), i \(\displaystyle{ (X \mathrel{r^{\exists}} Z)}\).

Nie. Definicja przechodniości relacji mówi co innego, w szczególności jest inny kwantyfikator.

Awram pisze: ↑30 lis 2023, o 20:45Żeby \(\displaystyle{ r^{\exists}}\) była przechodnia, najprościej za \(\displaystyle{ r}\) przyjąć relację pełną (czyli na zbiorze \(\displaystyle{ X}\) to relacja \(\displaystyle{ r = X \times X}\)). W ten sposób otrzymujemy przykład:
Relacja \(\displaystyle{ r = \{(1, 1)\}}\) jest przechodnia i \(\displaystyle{ r^{\exists}}\) jest przechodnia, bo \(\displaystyle{ \{1\} r^{\exists} \{1\}}\), i \(\displaystyle{ \{1\} r^{\exists} \{1\}}\), i \(\displaystyle{ \{1\} r^{\exists} \{1\}}\).
Czy moje rozumowanie jest poprawne?

Nie bardzo ma to sens. Piszesz, że za \(\displaystyle{ r}\) przyjmujesz relację pełną, a potem zaraz dodajesz: "W ten sposób otrzymujemy przykład:" i podajesz inną relację \(\displaystyle{ r}\)... Tak się składa, że oba podane przez Ciebie przykłady relacji są dobre, tzn. każda z podanych przez Ciebie relacji \(\displaystyle{ r}\) jest przechodnia i związana z nią relacja \(\displaystyle{ r^{\exists}}\) też jest przechodnia, ale te relacje nie mają ze sobą nic wspólnego, podczas gdy to, co napisałeś sugeruje, że mają...

Poza tym to, co napisałeś na początku sugeruje, że nie wiesz, jak uzasadnić przechodniość relacji \(\displaystyle{ r^{\exists}}\). I znów tak się składa, że uzasadnienie dotyczące przechodniości relacji \(\displaystyle{ \{(1, 1)\}^\exists}\) jest bliskie prawdy, ale obawiam się, że nie wiesz dlaczego, więc można to uznać za przypadkową zbieżność...

JK

Troche zrobiłem inaczej. Czy to teraz jest dobrze?
(a) Jeśli \(\displaystyle{ r^{\exists}}\) ma być przechodnia, to muszą istnieć zbiory \(\displaystyle{ X, Y, Z \subseteq \mathbb{N}}\), takie że \(\displaystyle{ (X \mathrel{r^{\exists}} Y)}\), i \(\displaystyle{ (Y \mathrel{r^{\exists}} Z)}\), i \(\displaystyle{ (X \mathrel{r^{\exists}} Z)}\). Z definicji oznacza to, że:
1. \(\displaystyle{ x_0 \mathrel{r} y_0}\) dla pewnych \(\displaystyle{ x_0 \in X}\), \(\displaystyle{ y_0 \in Y}\);
2. \(\displaystyle{ y_0 \mathrel{r} z_0}\) dla pewnych \(\displaystyle{ y_0 \in Y}\), \(\displaystyle{ z_0 \in Z}\);
3. \(\displaystyle{ x_0 \mathrel{r} z_0}\) dla pewnych \(\displaystyle{ x_0 \in X}\), \(\displaystyle{ z_0 \in Z}\).
Żeby \(\displaystyle{ r^{\exists}}\) była przechodnia, najprościej przyjąć \(\displaystyle{ X = \{ x_0 \}, Y = \{ y_0, y_0 \} }\) oraz \(\displaystyle{ Z = \{ z_0 \}}\). W ten sposób otrzymujemy przykład:
Relacja \(\displaystyle{ r = \{(2, 1), (1, 3)\}}\) jest przechodnia i \(\displaystyle{ r^{\exists}}\) jest przechodnia, bo \(\displaystyle{ \{2\} \mathrel{r^{\exists}} \{1, 1\}}\), i \(\displaystyle{ \{1, 1\} \mathrel{r^{\exists}} \{3\}}\), i \(\displaystyle{ \{2\} \mathrel{r^{\exists}} \{3\}}\).

Wiem, że nie tym sposobem z relacją pelną, ale w tym, w ktorym było zrobiono (b).

Awram pisze: ↑30 lis 2023, o 20:45Mam coś takiego dla (a):
(a) Jeśli \(\displaystyle{ r^{\exists}}\) ma być przechodnia, to muszą istnieć zbiory \(\displaystyle{ X, Y, Z \subseteq \mathbb{N}}\), takie że \(\displaystyle{ (X \mathrel{r^{\exists}} Y)}\), i \(\displaystyle{ (Y \mathrel{r^{\exists}} Z)}\), i \(\displaystyle{ (X \mathrel{r^{\exists}} Z)}\). Z definicji oznacza to, że:
1. \(\displaystyle{ x_0 \mathrel{r} y_0}\) dla pewnych \(\displaystyle{ x_0 \in X}\), \(\displaystyle{ y_0 \in Y}\);
2. \(\displaystyle{ y_0 \mathrel{r} z_0}\) dla pewnych \(\displaystyle{ y_0 \in Y}\), \(\displaystyle{ z_0 \in Z}\);
3. \(\displaystyle{ x_0 \mathrel{r} z_0}\) dla pewnych \(\displaystyle{ x_0 \in X}\), \(\displaystyle{ z_0 \in Z}\).
Żeby \(\displaystyle{ r^{\exists}}\) była przechodnia, najprościej przyjąć \(\displaystyle{ X = \{ x_0 \}, Y = \{ y_0, y_0 \} }\) oraz \(\displaystyle{ Z = \{ z_0 \}}\).

Do niczego. To nieprawda.

Awram pisze: ↑30 lis 2023, o 20:45 W ten sposób otrzymujemy przykład:
Relacja \(\displaystyle{ r = \{(2, 1), (1, 3)\}}\) jest przechodnia i \(\displaystyle{ r^{\exists}}\) jest przechodnia, bo \(\displaystyle{ \{2\} \mathrel{r^{\exists}} \{1, 1\}}\), i \(\displaystyle{ \{1, 1\} \mathrel{r^{\exists}} \{3\}}\), i \(\displaystyle{ \{2\} \mathrel{r^{\exists}} \{3\}}\).
Czy moje rozumowanie jest poprawne?

Jest zupełnie błędne, bo dla relacji \(\displaystyle{ r = \{(2, 1), (1, 3)\}}\) relacja \(\displaystyle{ r^{\exists}}\) nie jest przechodnia: masz \(\displaystyle{ \{2\}r^{\exists}\{1\}}\) i \(\displaystyle{ \{1\}r^{\exists}\{3\}}\), ale \(\displaystyle{ \neg \{2\}r^{\exists}\{3\}}\).

Awram pisze: ↑30 lis 2023, o 21:17Wiem, że nie tym sposobem z relacją pelną, ale w tym, w ktorym było zrobiono (b).

Obawiam się, że zupełnie nie zrozumiałeś tego, co zostało tam zrobione. W szczególności masz duże problemy ze zrozumieniem kwantyfikatorów.

JK

Wtedy jaki przykład powinien być w (a)? Nie rozumiem.

Zostało to już kilka razy napisane. Ale dopóki nie zrozumiesz definicji, to reszta starań nie będzie miała sensu. W szczególności musisz zrozumieć definicję przechodniości relacji. Znasz ją?

No tak. To jest \(\displaystyle{ \forall x, y, z \in \mathbb{N} (x \; r \; y \wedge y \; r \; z \rightarrow x \; r \; z)}\). Ale gdy weźmiemy \(\displaystyle{ r = \left\{ \left( 1, 1\right) \right\} }\), to skąd wziąć \(\displaystyle{ z}\)? Czy możemy wziąć \(\displaystyle{ r = \left\{ \left( 1, 1\right), \left( 1, 1\right) \right\} }\)?

Awram pisze: ↑30 lis 2023, o 21:35 No tak. To jest \(\displaystyle{ \forall x, y, z \in \mathbb{N} (x \; r \; y \wedge y \; r \; z \rightarrow x \; r \; z)}\).

To jest warunek przechodniości relacji \(\displaystyle{ r.}\) A Ty masz problem z przechodniością relacji \(\displaystyle{ r^\exists.}\)

Awram pisze: ↑30 lis 2023, o 21:35Ale gdy weźmiemy \(\displaystyle{ r = \left\{ \left( 1, 1\right) \right\} }\), to skąd wziąć \(\displaystyle{ z}\)? Czy możemy wziąć \(\displaystyle{ r = \left\{ \left( 1, 1\right), \left( 1, 1\right) \right\} }\)?

Po pierwsze, \(\displaystyle{ \left\{ \left( 1, 1\right), \left( 1, 1\right) \right\}= \left\{ \left( 1, 1\right) \right\}.}\)
Po drugie, co Ty w ogóle chcesz brać? Jeżeli chcesz uzasadnić przechodniość relacji \(\displaystyle{ r}\), to musisz sprawdzić WSZYSTKIE trójki \(\displaystyle{ x,y,z\in\NN}\) dla których spełnione są OBA warunki \(\displaystyle{ x \; r \; y}\) i \(\displaystyle{ y \; r \; z}\). Jeżeli za każdym razem okaże się, że \(\displaystyle{ x \; r \; z}\), to relacja będzie przechodnia. To jest dowód ogólny, więc zazwyczaj nie używamy w nim konkretnych elementów, bo jest za dużo możliwości do sprawdzenia, tylko przedstawiamy rozumowanie ogólne ("na literkach"). Natomiast relacja \(\displaystyle{ r=\left\{ \left( 1, 1\right) \right\}}\) jest pod tym względem wyjątkowa, bo JEDYNYMI liczbami \(\displaystyle{ x,y,z\in\NN}\) dla których spełnione są OBA warunki \(\displaystyle{ x \; r \; y}\) i \(\displaystyle{ y \; r \; z}\) są \(\displaystyle{ x=y=z=1}\), zatem sprawdzając ten jeden przykład (bo wtedy oczywiści zachodzi \(\displaystyle{ x \; r \; z}\)) sprawdzasz w tym wypadku wszystkie możliwości - to bardzo unikalna sytuacja.
Po trzecie - powtarzam - masz problem z relacją \(\displaystyle{ r^\exists.}\)

JK

Jan Kraszewski pisze: ↑30 lis 2023, o 21:50 Po drugie, co Ty w ogóle chcesz brać? Jeżeli chcesz uzasadnić przechodniość relacji \(\displaystyle{ r}\), to musisz sprawdzić WSZYSTKIE trójki \(\displaystyle{ x,y,z\in\NN}\) dla których spełnione są OBA warunki \(\displaystyle{ x \; r \; y}\) i \(\displaystyle{ y \; r \; z}\). Jeżeli za każdym razem okaże się, że \(\displaystyle{ x \; r \; z}\), to relacja będzie przechodnia. To jest dowód ogólny, więc zazwyczaj nie używamy w nim konkretnych elementów, bo jest za dużo możliwości do sprawdzenia, tylko przedstawiamy rozumowanie ogólne ("na literkach"). Natomiast relacja \(\displaystyle{ r=\left\{ \left( 1, 1\right) \right\}}\) jest pod tym względem wyjątkowa, bo JEDYNYMI liczbami \(\displaystyle{ x,y,z\in\NN}\) dla których spełnione są OBA warunki \(\displaystyle{ x \; r \; y}\) i \(\displaystyle{ y \; r \; z}\) są \(\displaystyle{ x=y=z=1}\), zatem sprawdzając ten jeden przykład (bo wtedy oczywiści zachodzi \(\displaystyle{ x \; r \; z}\)) sprawdzasz w tym wypadku wszystkie możliwości - to bardzo unikalna sytuacja.

Ale mnie trzeba podać jeden przykład, gdy \(\displaystyle{ r^{\exists}}\) jest przechodnia. Dlatego, jak zrozumiałem, trzeba podać \(\displaystyle{ r}\), która będzie przechodnia, i potem z tego powinno wynikać, że \(\displaystyle{ r^{\exists}}\) też przechodnia. (tak było w odpowiedzi Dasio11 dla punkta b)

Przeczytałem jeszcze raz posty, i zobaczyłem to: relacja \(\displaystyle{ r^{\exists}}\) jest przechodnia dokładnie wtedy, gdy \(\displaystyle{ r = A \times B}\) dla pewnych \(\displaystyle{ {A, B \subseteq \mathbb{N}}}\). Czy mogę podać \(\displaystyle{ r}\) jako \(\displaystyle{ \left\{ 1\right\} \times \left\{ 1\right\} }\), i wtedy \(\displaystyle{ r = (1, 1)}\), i z tego wynika, że \(\displaystyle{ r^{\exists}}\) też przechodnia?