Relacje- szybkie pytanie.

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Relacje- szybkie pytanie.

Post autor: Jakub Gurak »

Mam szybkie pytanie:

Czy dla dowolnej relacji \(\displaystyle{ R\subset X \times Y}\), wtedy \(\displaystyle{ R^{-1} \subset Y\times X }\), czy

\(\displaystyle{ R\circ R ^{-1}=I _{Y} }\) (identyczność na zbiorze \(\displaystyle{ Y}\)), oraz czy

\(\displaystyle{ R ^{-1}\circ R=I_{X}. }\) :?:

Ostatnia równość zachodzi dla funkcji różnowartościowych, czy zachodzi dla dowolnej relacji z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\) :?: Oraz druga równość czy zachodzi :?:
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Relacje- szybkie pytanie.

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 15 mar 2020, o 20:05Ostatnia równość zachodzi dla funkcji różnowartościowych, czy zachodzi dla dowolnej relacji z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\) :?: Oraz druga równość czy zachodzi :?:
Nie ma żadnego powodu, by zachodziła którakolwiek z tych równości. Popatrz na \(\displaystyle{ X=Y=\NN}\) i \(\displaystyle{ R=\{\left\langle 1,1\right\rangle \}.}\)

JK
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Relacje- szybkie pytanie.

Post autor: Jakub Gurak »

No tak, wtedy wszystkie pojawiające się relacje są równe \(\displaystyle{ R=\left\{ \left( 1,1\right) \right\}.}\)

A czy dla dowolnej funkcji \(\displaystyle{ f:X \rightarrow Y}\)

\(\displaystyle{ f^{-1}\circ f=I_{X} }\):?:

Tu \(\displaystyle{ f ^{-1}}\) oznacza tylko relację odwrotną do relacji \(\displaystyle{ f}\).

Ciężko mi rozstrzygnąć, pojęcia złożenia relacji nie czuję najlepiej.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Relacje- szybkie pytanie.

Post autor: Dasio11 »

Sprawdź dla funkcji \(\displaystyle{ \NN \to \NN}\) stale równej \(\displaystyle{ 7}\).
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Relacje- szybkie pytanie.

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 15 mar 2020, o 22:56\(\displaystyle{ f^{-1}\circ f=I_{X} }\):?:

Tu \(\displaystyle{ f ^{-1}}\) oznacza tylko relację odwrotną do relacji \(\displaystyle{ f}\).
W żadnym razie. Rozważ funkcję stałą.
Jakub Gurak pisze: 15 mar 2020, o 22:56Ciężko mi rozstrzygnąć, pojęcia złożenia relacji nie czuję najlepiej.
A spróbowałeś rozpisać z definicji, co znaczy Twoje pytanie? Od tego powinieneś zacząć.

JK
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Relacje- szybkie pytanie.

Post autor: Jakub Gurak »

Dasio11 pisze: 15 mar 2020, o 22:58 Sprawdź dla funkcji \(\displaystyle{ \NN \to \NN}\) stale równej \(\displaystyle{ 7}\).
Czyli otrzymamy \(\displaystyle{ \NN \times \NN \neq I _{\NN}, }\), tak :?:
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Relacje- szybkie pytanie.

Post autor: Dasio11 »

Tak.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Relacje- szybkie pytanie.

Post autor: Jakub Gurak »

Jan Kraszewski pisze: 15 mar 2020, o 20:54 Nie ma żadnego powodu, by zachodziła którakolwiek z tych równości. Popatrz na \(\displaystyle{ X=Y=\NN}\) i \(\displaystyle{ R=\{\left\langle 1,1\right\rangle \}.}\)
Ale za to chyba dla dowolnej relacji \(\displaystyle{ R \subset X \times Y}\), mamy

\(\displaystyle{ R\circ R ^{-1} \subset I _{Y} }\) (identyczność na zbiorze \(\displaystyle{ Y}\)), oraz

\(\displaystyle{ R ^{-1}\circ R \subset I_{X}. }\) Zgadza się :?:

Mam jeszcze szybkie pytanie:

Czy dla dowolnych relacji \(\displaystyle{ R,S,T}\) (pomiędzy zbiorami, tak żeby było to dobrze określone) mamy:

\(\displaystyle{ R\circ (S \cup T)=\left( R\circ S\right) \cup \left( R\circ T\right) }\) :?:

Jakby była wątpliwość, to definicję złozenia relacji mam tą, gdzie trzeba uważać na kolejność relacji (trzeba odwrócić kolejność tych relacji, przy złożeniu). Wiem, że zachodzi odpowiednia do tej równość, gdzie suma dwóch relacji występuje z lewej strony, czy w takiej wersji też to zachodzi :?: Potrzebuję z tej własności skorzystać.
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Relacje- szybkie pytanie.

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 30 kwie 2020, o 17:25Ale za to chyba dla dowolnej relacji \(\displaystyle{ R \subset X \times Y}\), mamy

\(\displaystyle{ R\circ R ^{-1} \subset I _{Y} }\) (identyczność na zbiorze \(\displaystyle{ Y}\)), oraz

\(\displaystyle{ R ^{-1}\circ R \subset I_{X}. }\) Zgadza się :?:
Nie, nie zgadza się. Skąd to dziwne przypuszczenie? Rozpatrz \(\displaystyle{ X=Y, R=X\times X}\).
Jakub Gurak pisze: 30 kwie 2020, o 17:25Mam jeszcze szybkie pytanie:

Czy dla dowolnych relacji \(\displaystyle{ R,S,T}\) (pomiędzy zbiorami, tak żeby było to dobrze określone) mamy:

\(\displaystyle{ R\circ (S \cup T)=\left( R\circ S\right) \cup \left( R\circ T\right) }\) :?:
(...)
Potrzebuję z tej własności skorzystać.
To ją udowodnij. To jest na ogół pierwsza rzecz, którą próbuje zrobić matematyk, jak potrzebuje jakiejś własności - udowodnić ją.

JK
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Relacje- szybkie pytanie.

Post autor: Jakub Gurak »

Jan Kraszewski pisze: 30 kwie 2020, o 20:19 Nie, nie zgadza się. Skąd to dziwne przypuszczenie? Rozpatrz \(\displaystyle{ X=Y, R=X\times X}\)
Mogę wziąć \(\displaystyle{ X= Y= \left\{ 0,1\right\}}\) :?: - będzie mi łatwiej wyznaczyć zlożenie \(\displaystyle{ \left( X \times X\right)\circ\left( X \times X\right). }\)

Myślałem, że jeśli para \(\displaystyle{ \left( a,b\right) \in R }\), to para \(\displaystyle{ \left( b,a\right) \in R ^{-1} }\) , skąd \(\displaystyle{ \left( a,a\right) \in R ^{-1}\circ R }\), skąd \(\displaystyle{ R ^{-1}\circ R \subset I _{X}}\) (bo \(\displaystyle{ \left( a,a\right) \in I _{X} }\)). Podobnie dla drugiej inkluzji. Ale już nie wiem czy to półformalne uzasadnienie jest poprawne? Jak nie jest poprawne, to gdzie jest błąd :?:
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Relacje- szybkie pytanie.

Post autor: Dasio11 »

Zawieranie \(\displaystyle{ R \circ R^{-1} \subseteq I_Y}\) zachodzi tylko wtedy, gdy \(\displaystyle{ R}\) jest funkcją częściową.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Relacje- szybkie pytanie.

Post autor: Jakub Gurak »

Jakub Gurak pisze: 30 kwie 2020, o 17:25Czy dla dowolnych relacji \(\displaystyle{ R,S,T}\) (pomiędzy zbiorami, tak żeby było to dobrze określone) mamy:

\(\displaystyle{ R\circ (S \cup T)=\left( R\circ S\right) \cup \left( R\circ T\right) }\) :?:
(...)
Potrzebuję z tej własności skorzystać.
To ją udowodnij.
Dobrze.

Niech relacje \(\displaystyle{ S,T \subset A \times B, R \subset B \times C }\).

Czy \(\displaystyle{ R\circ\left( S \cup T\right) =R\circ S \cup R\circ T. }\)

Niech \(\displaystyle{ \left( a,c\right)\in R\circ \left( S \cup T\right). }\) Tzn. przy pewnym \(\displaystyle{ b \in B,}\) mamy \(\displaystyle{ \left( a,b\right) \in S \cup T }\) oraz \(\displaystyle{ \left( b,c\right) \in R.}\) zatem \(\displaystyle{ \left( a,b\right) \in S }\) lub \(\displaystyle{ \left( a,b\right) \in T. }\) w pierwszym przypadku \(\displaystyle{ \left( a,b\right) \in S,\left( b,c\right) \in R, }\) zatem \(\displaystyle{ \left( a,c\right) \in R\circ S.}\) W drugim przypadku \(\displaystyle{ \left( a,b\right) \in T,\left( b,c\right) \in R,}\) zatem \(\displaystyle{ \left( a,c\right) \in R\circ T. }\) A zatem, w obydwu przypadkach \(\displaystyle{ \left( a,c\right) \in R\circ S \cup R\circ T, }\) co dowodzi inkluzji w prawo.

Inkluzja w lewo: niech \(\displaystyle{ \left( a,c\right) \in R\circ S \cup R\circ T. }\) Jeśli \(\displaystyle{ \left( a,c\right)\in R\circ S }\), to przy pewnym \(\displaystyle{ b\in B}\), mamy \(\displaystyle{ \left( a,b\right) \in S,\left( b,c\right)\in R.}\) wtedy \(\displaystyle{ \left( a,b\right)\in S\cup T, \left( b,c\right) \in R }\), zatem \(\displaystyle{ \left( a,c\right) \in R\circ \left( S \cup T\right),.}\) W pozostałym przypadku \(\displaystyle{ \left( a,c\right)\in R\circ T, }\) wtedy, przy pewnym \(\displaystyle{ b\in B}\), mamy \(\displaystyle{ \left( a,b\right) \in T,\left( b,c\right) \in R,}\) wtedy \(\displaystyle{ \left( a,b\right)\in S\cup T,\left( b,c\right)\in R,}\) zatem \(\displaystyle{ \left( a,c\right) \in R\circ \left( S \cup T\right). }\) Zatem druga inkluzja jest dowiedziona, więc \(\displaystyle{ R\circ \left( S \cup T\right)=R\circ S \cup R\circ T.}\) Dobrze :?:
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Relacje- szybkie pytanie.

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 30 kwie 2020, o 23:53Mogę wziąć \(\displaystyle{ X= Y= \left\{ 0,1\right\}}\) :?: - będzie mi łatwiej wyznaczyć zlożenie \(\displaystyle{ \left( X \times X\right)\circ\left( X \times X\right). }\)
Bez różnicy. Złożenie relacji pełnej z sobą samą jest zawsze relacją pełną, a dowód tego (niezależnie od tego, czym jest \(\displaystyle{ X}\)) zajmuje pół linijki.
Jakub Gurak pisze: 30 kwie 2020, o 23:53Myślałem, że jeśli para \(\displaystyle{ \left( a,b\right) \in R }\), to para \(\displaystyle{ \left( b,a\right) \in R ^{-1} }\) , skąd \(\displaystyle{ \left( a,a\right) \in R ^{-1}\circ R }\), skąd \(\displaystyle{ R ^{-1}\circ R \subset I _{X}}\) (bo \(\displaystyle{ \left( a,a\right) \in I _{X} }\)). Podobnie dla drugiej inkluzji. Ale już nie wiem czy to półformalne uzasadnienie jest poprawne?
To nie jest ani uzasadnienie, ani poprawne.
Jakub Gurak pisze: 30 kwie 2020, o 23:53Jak nie jest poprawne, to gdzie jest błąd :?:
Błąd jest w tym, że coś robisz, ale nie wiesz co. Całe wnioskowanie, które napisałeś przez słowem "skąd" jest prawdziwe, problem polega na tym, że dokładnie nic z tego nie wynika. Pokazałeś, że jeśli \(\displaystyle{ \left( a,b\right) \in R }\), to \(\displaystyle{ \left( a,a\right) \in R ^{-1}\circ R }\), tylko co z tego? To nie ma żadnego związku z \(\displaystyle{ R ^{-1}\circ R \subset I _{X}}\).
Jakub Gurak pisze: 1 maja 2020, o 01:51 Czy \(\displaystyle{ R\circ\left( S \cup T\right) =R\circ S \cup R\circ T. }\)
(...)
Dobrze :?:
Dobrze.

JK
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Relacje- szybkie pytanie.

Post autor: Jakub Gurak »

Czy jeśli \(\displaystyle{ S}\) jest relacją w danym zbiorze, relacją zwrotną i przechodnią, to czy

\(\displaystyle{ S\circ S ^{-1} \subset S \cup S ^{-1}. }\) oraz czy także
\(\displaystyle{ S ^{-1}\circ S \subset S\cup S ^{-1} .}\)

Niestety, nie mam założenia, że \(\displaystyle{ S}\) jest symetryczna( wtedy chyba problem byłby oczywisty, ale niestety). Gdy tak będzie to chyba będę w stanie udowodnić pewne ogólne twierdzenie, ale tu potrzebuje pomocy. Byłoby bardzo dobrze gdyby te dwie własności były prawdą (dla relacji \(\displaystyle{ S}\)przechodniej(i zwrotnej)).
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Relacje- szybkie pytanie.

Post autor: Jan Kraszewski »

W ogólności to zawieranie nie musi zachodzić. Rozważ relację \(\displaystyle{ S=\{\left\langle 1,1\right\rangle, \left\langle 2,2\right\rangle, \left\langle 3,3\right\rangle, \left\langle 1,2\right\rangle, \left\langle 1,3\right\rangle \}}\) na zbiorze \(\displaystyle{ X=\{1,2,3\}}\). Jest to oczywiście relacja zwrotna i przechodnia, ale \(\displaystyle{ \left\langle 2,3\right\rangle\in S\circ S^{-1} \setminus \left( S\cup S^{-1}\right) }\). Dla drugiego z zawierań kontrprzykład jest analogiczny.

JK
ODPOWIEDZ