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

Re: Relacje- szybkie pytanie.

Post autor: Jakub Gurak »

Z tego złożenia relacji co ja wyznaczyłem, wychodzi na to, że nawet tutaj \(\displaystyle{ S\circ S ^{-1}}\) jest relacją pełną, zgadza się :?:

Niestety, taki wynik całkowicie niweczy mój pomysł na pewien problem. :|
Jan Kraszewski
Administrator
Administrator
Posty: 34125
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: 1 maja 2020, o 20:56Z tego złożenia relacji co ja wyznaczyłem, wychodzi na to, że nawet tutaj \(\displaystyle{ S\circ S ^{-1}}\) jest relacją pełną, zgadza się :?:
Tak.

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 »

Wczoraj przeprowadziłem bardzo ciekawy dowód, że dla dowolnej rodziny \(\displaystyle{ \mathbb{B} }\) relacji z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), mamy : \(\displaystyle{ \left( \bigcup\mathbb{B}\right) _{P}= \bigcup_{R\in\mathbb{B}} R _{P} }\) prawą dziedziną sumy rodziny relacji jest suma prawych dziedzin relacji tej rodziny. Wiedząc, że zachodzi odpowiednik tej równości dla lewych dziedzin relacji (proste), czyli, że \(\displaystyle{ \left( \bigcup\mathbb{B}\right) _{L}= \bigcup_{R\in\mathbb{B}} R_L,}\) wiedząc, że zawsze \(\displaystyle{ \left( R ^{-1} \right) ^{-1}=R,}\) oraz, że dla dowolnej rodziny relacji między dwoma zbiorami, relacja odwrotna do sumy rodziny relacji jest sumą relacji odwrotnych (proste), w sposób ciekawy to udowodniłem. Oto:

CIEKAWY DOWÓD:

Niech \(\displaystyle{ X,Y}\) będą zbiorami, a \(\displaystyle{ \mathbb{B}}\) będzie rodziną relacji z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\). Wtedy:

\(\displaystyle{ \left( \bigcup\mathbb{B} \right) _{P}=\left( \left( \left( \bigcup\mathbb{B} \right) ^{-1}\right) ^{-1} \right)_{P} =\left( \left( \bigcup\mathbb{B} \right) ^{-1}\right) _{L} =\left( \bigcup_{R\in\mathbb{B}} R ^{-1} \right) _{L} }\),

i teraz na podstawie prawa odnośnie lewej dziedziny sumy rodziny relacji (chyba tak można, gdyż- co prawda, to są relacje odwrotne z \(\displaystyle{ Y}\) do \(\displaystyle{ X}\), ale skoro to zachodzi dla dowolnych dwóch zbiorów \(\displaystyle{ A,B}\) dla dowolnej rodziny relacji z \(\displaystyle{ A}\) do \(\displaystyle{ B}\), więc dla zbiorów \(\displaystyle{ X,Y}\) możemy rozważyć zbiory \(\displaystyle{ Y,X}\), i dla dowolnej rodziny relacji z \(\displaystyle{ Y}\) do \(\displaystyle{ X}\) to zachodzi, więc również dla naszej rodziny relacji odwrotnych to zachodzi ), a więc to jest równe

\(\displaystyle{ = \bigcup_{R \in \mathbb{B}} R _{L} ^{-1}= \bigcup_{R \in\mathbb{B} } R_P. \square}\) :D :lol:
Jan Kraszewski
Administrator
Administrator
Posty: 34125
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: 31 maja 2020, o 15:26Wczoraj przeprowadziłem bardzo ciekawy dowód, że dla dowolnej rodziny \(\displaystyle{ \mathbb{B} }\) relacji z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), mamy : \(\displaystyle{ \left( \bigcup\mathbb{B}\right) _{P}= \bigcup_{R\in\mathbb{B}} R _{P} }\) prawą dziedziną sumy rodziny relacji jest suma prawych dziedzin relacji tej rodziny.
No cóż, skoro twierdzisz, że wiemy, iż
Jakub Gurak pisze: 31 maja 2020, o 15:26zachodzi odpowiednik tej równości dla lewych dziedzin relacji (proste),
to ja mam dużo krótszy dowód od Twojego (choć zapewne nie uznasz go za "bardzo ciekawy"):

Dowód: Analogicznie.

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 »

Taki dowód też (chwilę potem) już przeprowadziłem. Racja, zgadzam się, w takich prostych rzeczach nie ma co kombinować.

Dzisiaj badałem różnicę dwóch relacji. Wykazałem na przykład na logikę (na prostą logikę), że różnica dwóch relacji spójnych nie może być relacją spójną (na niepustym zbiorze). Uzasadniłem też inne fakty. Przedstawię tu rezultaty tego.

Przypominam, relacja \(\displaystyle{ R}\) w zbiorze \(\displaystyle{ X}\) jest spójna, gdy dla dowolnych \(\displaystyle{ x,y\in X}\), zachodzi \(\displaystyle{ (x,y)\in R}\) lub \(\displaystyle{ (y,x)\in R.}\)

Podstawiając za \(\displaystyle{ y=x}\) łatwo się przekonać, że każda relacja spójna jest relacją zwrotną.

Oczywistym jest, że różnica dwóch relacji zwrotnych (na niepustym zbiorze \(\displaystyle{ X}\)) wręcz nie może być zwrotna (gdyż relacja zwrotna w \(\displaystyle{ X}\) musi zawierać identyczność \(\displaystyle{ I_X}\)). Mogę zatem na prostą logikę udowodnić, że również różnica dwóch relacji spójnych (w niepustym zbiorze) nie może być spójna.

Prosty dowód: Różnica dwóch relacji spójnych, a więc i dwóch relacji zwrotnych nie może być zwrotna. Zatem nie może być też spójna, bo gdyby byłaby spójna, to byłaby też zwrotna. \(\displaystyle{ \square}\) :lol:

Ciekawe, że różnica dwóch relacji symetrycznych jest relacją symetryczną. Przypominam fakt, że relacja w danym zbiorze jest symetryczna dokładnie wtedy, gdy jest równa swojej relacji odwrotnej. A zatem możemy prosto udowodnić, że różnica dwóch relacji symetrycznych jest relacją symetryczną.

Prosty dowód:

Niech \(\displaystyle{ R,S}\) będą relacjami symetrycznymi w zbiorze \(\displaystyle{ X}\). Wtedy \(\displaystyle{ R=R^{-1},S=S^{-1}}\). A zatem \(\displaystyle{ \left( R \setminus S\right) ^{-1}= R^{-1}\setminus S^{-1}= R \setminus S}\), a zatem \(\displaystyle{ R \setminus S=\left( R \setminus S\right) ^{-1}}\), czyli relacja \(\displaystyle{ R \setminus S}\) jest symetryczna. \(\displaystyle{ \square}\)

W podobny sposób można udowodnić, że różnica symetryczna dwóch relacji symetrycznych jest zawsze relacją symetryczną( to nie tylko słowa- różnica symetryczna jest operacją przemienną, relacja symetryczna w zbiorze jest symetryczna względem przekątnej, chodzi o związek, o rozumienie). A może podam dowód:

Dowód:

Niech \(\displaystyle{ R,S}\) będą relacjami symetrycznymi w zbiorze \(\displaystyle{ X}\). Wtedy \(\displaystyle{ R=R^{-1}, S=S^{-1}}\). Różnicę symetryczną \(\displaystyle{ R}\) i \(\displaystyle{ S}\) będę oznaczał jako \(\displaystyle{ R\oplus S}\). Zatem

\(\displaystyle{ \left( R\oplus S\right)^{-1}=\left[ \left( R \setminus S\right) \cup \left( S \setminus R \right) \right] ^{-1}=\left( R \setminus S\right) ^{-1} \cup \left( S \setminus R\right) ^{-1} =\left( R ^{-1} \setminus S^{-1}\right) \cup \left( S ^{-1} \setminus R^{-1}\right)=\left( R \setminus S\right) \cup \left( S \setminus R \right) =R\oplus S}\), a więc relacja \(\displaystyle{ R\oplus S}\) jest równa swojej relacji odwrotnej, a więc jest relacją symetryczną. \(\displaystyle{ \square}\)

Zastanawiałem się też dziś czy zachodzi prawo dla relacji \(\displaystyle{ R,S}\) między dwoma zbiorami \(\displaystyle{ X}\) a \(\displaystyle{ Y}\):

\(\displaystyle{ \left( R \setminus S\right)_L\stackrel {?}{=}R_L \setminus S_L ?}\)

Otóż,
Ukryta treść:    
Dla prawych dziedzin pewnie można analogicznie, ale mi się już nie chciało drążyć tematu, wpadłem za to na inne proste (i ciekawe) rozwiązanie:

(Wykażemy prawo relacji \(\displaystyle{ R,S}\) między zbiorami \(\displaystyle{ X}\) a \(\displaystyle{ Y}\): \(\displaystyle{ \left( R \setminus S \right)_P\supset R_P \setminus S_P}\)):

\(\displaystyle{ \left( R \setminus S\right) _{P}=\left( \left( \left( R \setminus S\right) ^{-1}\right) ^{-1} \right) _{P}=\left( \left( R \setminus S\right) ^{-1}\right) _{L}= \left( R ^{-1} \setminus S ^{-1} \right) _{L}\supset \left( R ^{-1}\right) _L \setminus \left( S ^{-1}\right) _L=R_P \setminus S_P ,}\)

gdzie przedostatnie przejście (inkluzja) wynika z poprzedniej udowodnionej własności.

Zauważmy na koniec, że ponieważ \(\displaystyle{ R \setminus S\subset R}\), więc również \(\displaystyle{ \left( R \setminus S\right)_P \subset R_P.}\) :lol:
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 »

Udowodniłem wczoraj, że jeśli \(\displaystyle{ X,Y}\) są zbiorami, a \(\displaystyle{ R}\) jest dowolną relacją, to lewa dziedzina dopełnienia tej relacji jest nadzbiorem dopełnienia lewej dziedziny tej relacji. Oczywiście inkluzja w drugą stronę nie musi zachodzić, łatwo można (rysując relacje na płaszczyźnie) łatwo można się o tym przekonać. Podobnie dla prawych dziedzin udowodniłem, że prawa dziedzina dopełnienia relacji zawiera dopełnienie prawej dziedziny tej relacji, i z podobnych przyczyn nie musi zachodzić równość tych dwóch zbiorów. Udowodniłem też, że dla relacji \(\displaystyle{ R,S}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\) lewa dziedzina różnicy symetrycznej \(\displaystyle{ R}\) i \(\displaystyle{ S}\) jest nadzbiorem różnicy symetrycznej lewych dziedzin tych relacji. Podobnie dla prawych dziedzin. Przedstawię teraz dowody tych ciekawych faktów.

Przypominam udowodniliśmy w poście powyżej w ukrytej treści, prawo relacji:

\(\displaystyle{ (R \setminus S)_L\supset R_L \setminus S_L.}\) Będziemy z tego korzystać.

Niech \(\displaystyle{ X,Y}\) będą zbiorami, a \(\displaystyle{ R}\) relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\). Wykażemy, że \(\displaystyle{ (R')_L\supset (R_L)'}\), czyli, że lewa dziedzina dopełnienia relacji zawiera dopełnienie lewej dziedziny relacji.

Dowód:

\(\displaystyle{ (R')_L= \left[ (X \times Y) \setminus R\right] _L\supset \left( X \times Y\right) _L \setminus R_L=X \setminus R_L=(R_L)'. \square
}\)


Oczywiście równość, jak mówiliśmy, nie musi mieć miejsca- łatwo na płaszczyźnie narysować kontrprzykład.

Wykażemy teraz podobny fakt dla prawych dziedzin. Wykorzystamy, moje chyba ulubione prawo dla relacji \(\displaystyle{ (R ^{-1})^{-1}=R}\). Przypominam prawo \(\displaystyle{ R^{-1}_P=R_L}\), co oznacza, że prawa dziedzina relacji odwrotnej jest lewą dziedziną relacji danej. Przypominam prawo \(\displaystyle{ (R')^{-1}=(R^{-1})'}\) - relacja odwrotna do dopełnienia relacji jest dopełnieniem relacji odwrotnej. Możemy zatem wykazać teraz prawo relacji:

\(\displaystyle{ (R')_P\supset (R_P)'.}\)

Dowód:

\(\displaystyle{ (R')_P=\left[ \left( (R')^{-1}\right) ^{-1}\right] _P= \left( R'\right) ^{-1} _L=\left( R ^{-1} \right) '_L, }\)

teraz korzystamy z udowodnionego powyżej prawa, że lewa dziedzina dopełnienia relacji zawiera dopełnienie lewej dziedziny ( \(\displaystyle{ R^{-1}}\) co prawda jest relacją z \(\displaystyle{ Y}\) do \(\displaystyle{ X}\), ale to było prawo dla dowolnych dwóch zbiorów dla dowolnej relacji miedzy nimi , w szczególności dla zbiorów \(\displaystyle{ X,Y}\), dla
dla pary zbiorów \(\displaystyle{ (Y,X)}\), dla relacji odwrotnej z \(\displaystyle{ Y}\) do \(\displaystyle{ X}\), zachodzi to prawo), więc otrzymujemy:

\(\displaystyle{ \left( R ^{-1} \right) '_L\supset\left( (R ^{-1} )_L\right) '=\left( R_P\right) '. \square
}\)


Oczywiście, z podobnych przyczyn jak przedtem, równość nie musi mieć miejsca.

Wykażemy teraz prawo dla relacji:

\(\displaystyle{ (R\oplus S)_L\supset R_L\oplus S_L}\), gdzie \(\displaystyle{ \oplus}\) oznacza różnicę symetryczną dwóch zbiorów, tzn. wykażemy, że lewa dziedzina różnicy symetrycznej dwóch relacji zawiera różnicę symetryczną lewych dziedzin tych relacji.

Dowód:

\(\displaystyle{ \left( R\oplus S\right) _L= \left[ \left( R \setminus S\right) \cup \left( S \setminus R\right) \right] _L=\left( R \setminus S\right) _L \cup \left( S \setminus R\right) _L\supset (R_L \setminus S_L) \cup (S_L \setminus R_L )= R_L\oplus S_L. \square}\)

Równość nie musi mieć miejsca, aby podać kontrprzykład rozważmy \(\displaystyle{ X=\left\{ 0,1,2\right\} ; Y=\left\{ 0,1,2,3,4\right\}}\); oraz relacje \(\displaystyle{ R=\left\{ \left(0,0 \right); \left(1, 1\right);\left(2, 2\right);\left(2,3 \right);\left(2,4 \right);\left(0,4 \right); \left(0,3 \right);\left(0,2 \right);\left(0, 1\right) \right\}}\) , i \(\displaystyle{ S=\left\{ \left(0,2 \right);\left(1,1 \right);\left(2,0 \right);\left(2,1 \right);\left(2,2 \right); \left(2,3 \right);\left(0,3 \right) \right\}. }\)

Wtedy \(\displaystyle{ R\oplus S=\left\{ \left(0,0 \right); \left(2,4 \right);\left(0,4 \right); \left(0,1 \right);\left(2,0 \right); \left(2,1 \right) \right\} }\), a więc \(\displaystyle{ (R\oplus S)_L=\left\{ 0,2\right\}}\), podczas gdy \(\displaystyle{ R_L\oplus S_L=\left\{ 0,1,2\right\} \oplus\left\{ 0,1,2\right\}=\emptyset \neq \left\{ 0,2\right\}. }\)

Podamy jeszcze dowód inkluzji dla prawych dziedzin, tzn. wykażemy prawo dla relacji :

\(\displaystyle{ (R\oplus S)_P\supset R_P\oplus S_P.}\)

W tym celu przypomnijmy, że mamy prawo dla relacji : \(\displaystyle{ \left( R\oplus S\right) ^{-1}= R ^{-1}\oplus S^{-1}}\)- relacją odwrotną do różnicy symetrycznej dwóch relacji jest różnica symetryczna relacji odwrotnych.
Prosty dowód:    
A zatem podajmy ten dowód:

\(\displaystyle{ (R\oplus S)_P=\left[ \left( \left( R\oplus S\right) ^{-1} \right) ^{-1} \right] _P= \left( R\oplus S\right) ^{-1}_L= \left( R^{-1} \oplus S^{-1}\right)_L }\) , teraz korzystamy z poprzednio wykazanego prawa, że lewa dziedzina różnicy symetrycznej zawiera różnicę symetryczną lewych dziedzin, a więc
\(\displaystyle{ \left( R^{-1} \oplus S^{-1}\right)_L\supset R ^{-1}_L\oplus S^{-1}_L=R_P \oplus S_P. \square}\)

W sumie to zainteresowało mnie, ile tu jest problemów do zbadania, tych podstawowych problemów związanych z relacjami, i dzisiaj z pół godziny liczyłem dokładnie, doliczyłem się \(\displaystyle{ 88}\) problemów. A to i tak to nie wszystkie, jak zobaczyłem na ważniaku, to parę zupełnie podstawowych trzeba jeszcze dodać, to już będzie około 100, jeszcze z domknięciem relacji jest 10 pytań, ale już to zbadałem, przypomniałem sobie, że paru pytań zapomniałem, może coś jeszcze zapomniałem, a mamy już około 115... Może kiedyś to wszystko zbadam. Z tych \(\displaystyle{ 88}\) większość zbadałem już, ale nie wszystkie.

A, już wiem o czym zapomniałem, o przeciwobrazach dla relacji, czy ma podobne własności jak przeciwobraz dla funkcji, może to też kiedyś zbadam... :lol: :D
Możliwości badawcze:    
Więc jest tu sporo pracy, może to kiedyś wszystko zbadam. :lol:

Większość z wymienionych już zbadałem, i większość to fakty prawdziwe są, jeśli się nie mylę. :lol:
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 »

Przypomnę może najpierw, że:

Jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ R}\) relacją w zbiorze \(\displaystyle{ X}\), to ta relacja jest przeciwprzechodnia, gdy (podaje teraz definicję), gdy spełniona jest implikacja:

\(\displaystyle{ \left( a,b\right) \in R \wedge \left( b,c\right) \in R \Longrightarrow \left( a,c\right) \not \in R.}\)

Np. możemy rozważyć taką niematematyczną relację, gdyż możemy rozważyć relację na zbiorze wszystkich ludzi, taką relację, że jedna osoba jest w relacji z drugą osobą, gdy pierwsza osoba jest ojcem drugiej. Taka relacja jest przeciwprzechodnia, gdyż jeśli jedna osoba jest ojcem drugiej osoby, a druga osoba jest ojcem trzeciej, to pierwsza osoba nie jest ojcem trzeciej osoby (gdyż jest jej dziadkiem).

Wykazałem wczoraj, że relacja \(\displaystyle{ R }\) w zbiorze \(\displaystyle{ X}\) jest relacją przeciwprzechodnią, dokladnie wtedy, gdy jest rozłączna ze złożeniem tej relacji z nią samą. Wykazałem też, że jeśli relacja \(\displaystyle{ R}\) w zbiorze \(\displaystyle{ X}\) jest przeciwprzechodnia, to relacją do niej odwrotna również jest przeciwprzechodnia. Wykazałem też, taki prosty i ciekawy fakt, że jeśli mamy dwa zbiory \(\displaystyle{ X,Y}\), oraz dowolną relację \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), to ona jest równoliczna z relacją do niej odwrotną. Wykazałem też łatwo, że jeśli mamy relację \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y,}\) będącą zbiorem skończonym, to jej lewa dziedzina, jak i jej prawa dziedzina, jest zbiorem skończonym . Przedstawię teraz dowody tych ciekawych faktów.


Niech \(\displaystyle{ X}\) będzie zbiorem, a \(\displaystyle{ R}\) niech będzie relacją z \(\displaystyle{ X}\) do \(\displaystyle{ X}\). Wykażemy, że relacja \(\displaystyle{ R}\) jest przeciwprzechodnia, dokładnie wtedy, gdy zbiory \(\displaystyle{ R\circ R}\) oraz \(\displaystyle{ R}\) są zbiorami rozłącznymi, tzn. gdy: \(\displaystyle{ \left( R\circ R\right) \cap R=\left\{ \right\} }\).

DOWÓD TEGO FAKTU:

Przypuścmy, że \(\displaystyle{ \left( R\circ R \right) \cap R \neq \left\{ \right\} }\) . Istnieje więc para \(\displaystyle{ \left( a,b\right)}\), taka, że \(\displaystyle{ (a,b)\in R\circ R}\) i \(\displaystyle{ \left( a,b\right) \in R}\). Ponieważ \(\displaystyle{ \left( a,b\right) \in R\circ R}\), więc \(\displaystyle{ (a,c)\in R}\) i \(\displaystyle{ (c,b)\in R}\), dla pewnego elementu \(\displaystyle{ c\in X}\). Ponieważ \(\displaystyle{ \left( a,c\right) \in R}\); \(\displaystyle{ \left( c,b\right) \in R}\), a \(\displaystyle{ \left( a,b\right) \in R}\), więc relacja \(\displaystyle{ R}\) nie jest przeciwprzechodnia.

Przypuścmy teraz, że zbiory \(\displaystyle{ \left( R\circ R\right)}\) i \(\displaystyle{ R}\) są rozłączne. Pokażemy, że relacja \(\displaystyle{ R}\) jest przeciwprzechodnia. W tym celu weźmy pary : \(\displaystyle{ \left( a,b\right) , \left( b,c \right) \in R}\) i pokażmy, że \(\displaystyle{ \left( a,c\right) \not\in R}\). Przypuśćmy nie wprost, że \(\displaystyle{ \left( a,c\right) \in R}\). Ponieważ \(\displaystyle{ \left( a,b\right) ; (b,c) \in R}\), to \(\displaystyle{ \left( a,c\right) \in R\circ R}\), a zatem \(\displaystyle{ (a,c) \in \left( R\circ R\right) \cap R}\), a zbiory \(\displaystyle{ R\circ R}\) i \(\displaystyle{ R}\) są rozłączne, czyli nie mają wspóllnych elementów, a tutaj para \(\displaystyle{ \left( a,c\right)}\) jest wspólnym elementem- sprzeczność. Wobec czego \(\displaystyle{ \left( a,c\right) \not\in R}\), i relacja \(\displaystyle{ R}\) jest przeciwprzechodnia\(\displaystyle{ . \square}\) :D

Wykażemy teraz, że jeśli relacja \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ X}\) jest przeciwprzechodnia ,to relacja do niej odwrotna \(\displaystyle{ R ^{-1}}\) jest również przeciwprzechodnia.
DOWÓD TEGO FAKTU::    
Zauważmy jeszcze, że relacja w zbiorze może nie być ani przechodnia ani przeciwprzechodnia. Jako kontrprzykład rozważmy zbiór: \(\displaystyle{ X= \left\{ 0,1,2\right\} }\), a jako relację \(\displaystyle{ R}\) weźmy: \(\displaystyle{ R= \left\{ \left( 0,1\right) ; \left( 1,2\right); \left( 0,2\right) ; \left( 2,0\right) \right\}}\) , wtedy \(\displaystyle{ \left( 0,1\right) ; \left( 1,2\right) \in R}\), lecz \(\displaystyle{ \left( 0,2\right) \in R}\), a więc relacja \(\displaystyle{ R}\) nie jest przeciwprzechodnia ; i nie jest przechodnia ( mamy: \(\displaystyle{ \left( 0,2\right) ; \left( 2,0\right) \in R,}\) lecz \(\displaystyle{ \left( 0,0\right) \not\in R}\) )\(\displaystyle{ .\square}\)


Rozważny teraz relację \(\displaystyle{ R}\) ze zbioru \(\displaystyle{ X}\) w zbiór \(\displaystyle{ Y}\). Wyka\(\displaystyle{ }\)żemy, że ta relacja jest równoliczna z relacją odwrotną do niej.

DOWÓD TEGO FAKTU:

Bardzo łatwo jest wykazać, że funkcja \(\displaystyle{ f: X \times Y \rightarrow Y \times X}\) , działającą w następujący sposób:

\(\displaystyle{ \left( x,y\right) \stackrel{f} {\rightarrow } \left( y,x\right) ;}\)

jest dobrze określoną bijekcją. A zatem \(\displaystyle{ X \times Y\sim Y \times X}\). Ponieważ \(\displaystyle{ R\subset X \times Y}\), to relacja \(\displaystyle{ R}\) jest równoliczna z obrazem tego zbioru przez funkcję \(\displaystyle{ f}\), czyli \(\displaystyle{ R\sim \stackrel{ \rightarrow }{f} (R)}\). Ale:

\(\displaystyle{ \stackrel{ \rightarrow }{f} \left( R\right) = \left\{ f\left( \left( x,y\right) \right)\Bigl| \ \ \left( x,y\right) \in R \right\}= \left\{ \left( y,x\right) \Bigl| \ \ \left( x,y\right) \in R\right\} = R ^{-1} }\),

czyli \(\displaystyle{ R\sim R ^{-1}. \square}\) :lol:


Wykażemy jeszcze, zgodnie z zapowiedzią, że jeśli \(\displaystyle{ R}\) jest relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), będącą zbiorem skończonym, to jej lewa dziedzina \(\displaystyle{ R_L}\) jest zbiorem skończonym, jak i jej prawa dziedzina \(\displaystyle{ R_P}\) jest zbiorem skończonym .

Podajmy najpierw dwa proste lematy.

Lemat 1Jeśli mamy relację \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), to jej lewa dziedzina jest mocy nie większej niż moc tej relacji \(\displaystyle{ R}\), czyli : \(\displaystyle{ \left| R_L\right| \le \left| R\right|.}\)

SZKIC DOWODU TEGO FAKTU:

Jeśli \(\displaystyle{ R=\emptyset}\), to \(\displaystyle{ R_L = \emptyset_L= \emptyset}\), a więc \(\displaystyle{ \left| R_L\right| \le \left| \emptyset\right| = \left| R\right| .}\)
\(\displaystyle{ }\)\(\displaystyle{ }\)
A jeśli \(\displaystyle{ R \neq \emptyset}\), to definiujemy funkcję \(\displaystyle{ f: R \rightarrow R_L}\) działającą w następujący sposób:

\(\displaystyle{ \left( x,y\right) \in R \stackrel{f}{ \rightarrow} x\in R_L}\),

i pokazujemy, bardzo prosto, że ta funkcja jest funkcją 'na'. Ponieważ \(\displaystyle{ R \neq \emptyset}\), a \(\displaystyle{ f}\) jest funkcją 'na', więc \(\displaystyle{ \left| R\right| \ge \left| R_L\right| .\square }\)

LEMAT 2. Jeśli \(\displaystyle{ R}\) jest relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), to \(\displaystyle{ \left| R_P\right| \le R}\),

czyli prawa dziedzina relacji \(\displaystyle{ R}\) jest mocy nie większej niż moc relacji \(\displaystyle{ R}\). Dowód jest analogiczny do powyższego.

Przejdźmy do naszych zadań.

Niech \(\displaystyle{ R}\) będzie relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), będącą zbiorem skończonym. Wykażemy najpierw, że zbiór \(\displaystyle{ R _L}\) jest zbiorem skończonym.

Dla dowodu wystarczy zauważyć, że mamy, na mocy lematu powyżej, mamy: \(\displaystyle{ \left| R_L\right| \le \left| R\right|}\), a relacja \(\displaystyle{ R}\) jest zbiorem skończonym , więc zbiór \(\displaystyle{ R_L}\), jako zbiór mocy nie większej niż moc skończona, jest skończony, bo gdyby był nieskończony, to relacja \(\displaystyle{ R}\) jako zbiór mocy większej lub równy od mocy nieskończonej byłby nieskończony (wynika to dość łatwo stąd, że zbiór równoliczny ze zbiorem nieskończonym jest nieskończony, i z faktu, że nadzbiór zbioru nieskończonego jest nieskończony, mogę to udowodnić :lol: ) , a więc relacja \(\displaystyle{ R}\) jest zbiorem nieskończonym -sprzeczność z założeniem .\(\displaystyle{ \square}\)


Wykażemy na koniec, zgodnie z zapowiedzią, że jeśli relacja \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\) jest zbiorem skończonym , to jej prawa dziedzina \(\displaystyle{ R_P}\) jest zbiorem skończonym .

DOWÓD TEGO FAKTU:

Ponieważ relacja \(\displaystyle{ R}\) jest zbiorem skończonym, a wiemy już, że relacja odwrotna do niej musi być z nią równoliczna, więc relacja \(\displaystyle{ R ^{-1}}\) również jest zbiorem skończonym , stosując zatem fakt udowodniony powyżej, otrzymujemy, że zbiór \(\displaystyle{ R ^{-1} _{L} }\) jest skończony. Ponieważ mamy prawo relacji \(\displaystyle{ R ^{-1}_L= R_P}\), więc również zbiór \(\displaystyle{ R_P}\) jest zbiorem skończonym\(\displaystyle{ . \square}\) 8-)
ODPOWIEDZ