Dowód relacji równoważności wtw gdy...

[Matys015]

Witam

Muszę udowodnić, że \(\displaystyle{ R \cup S}\) (\(\displaystyle{ R}\) i \(\displaystyle{ S}\) są relacjami równoważności na tym samym zbiorze) jest relacją równoważności wtedy i tylko wtedy, gdy \(\displaystyle{ R \cup S = RS}\)

Formuła będzie wyglądać : \(\displaystyle{ R \cup S \Leftrightarrow R \cup S = RS}\)
Dowód chcę przeprowadzić przez dwie implikacje.

1) L \(\displaystyle{ \Rightarrow}\) P
czyli mam : \(\displaystyle{ R \cup S \Rightarrow R \cup S = RS}\)
Zakładam prawdziwość \(\displaystyle{ R \cup S}\) i próbuję udowodnić \(\displaystyle{ R \cup S = RS}\).
\(\displaystyle{ =}\) rozbije na dwie inkluzje i będę mieć : \(\displaystyle{ R \cup S \subseteq RS}\).
Dalej to zawieranie mogę rozpisać : \(\displaystyle{ R \cup S \Rightarrow RS}\).
No i teraz moje pytanie, jak mogę udowodnić tą jedną inkluzję ? Bo mogę wziąść dowolne \(\displaystyle{ \left\langle a,c \right\rangle}\) i wtedy : \(\displaystyle{ \exists b aSb \wedge bRc}\), ale co dalej ? Brakuje mi pomysłu jak dalej ruszyć, no chyba że to co napisałem jest niedobrze.

[Jan Kraszewski]

Formuła będzie wyglądać : \(\displaystyle{ R \cup S \Leftrightarrow R \cup S = RS}\)

A co to ma być?

JK

[Matys015]

Wydawało mi się, że budując wyrażenie na podstawie treści do czegoś bym doszedł. W takim razie mogę liczyć na wskazówkę ?

[Jan Kraszewski]

Ale to nie ma sensu, napisałeś, że zbiór jest równoważny funkcji zdaniowej.

Masz pokazać, że dla relacji równoważności \(\displaystyle{ R,S}\):

1. jeśli \(\displaystyle{ R\cup S}\) jest relacją równoważności, to \(\displaystyle{ R\cup S=RS}\)

oraz

2. jeśli \(\displaystyle{ R\cup S=RS}\), to \(\displaystyle{ R\cup S}\) jest relacją równoważności.

Jak definiujesz złożenie relacji?

JK

[kociol878]

Czy złożenie relacji \(\displaystyle{ RS}\) powinno wyglądać tak?
\(\displaystyle{ \exists b \left\langle a,b\right\rangle \in S \wedge \left\langle b,c \right\rangle R}\)

[Jan Kraszewski]

To zależy, funkcjonują dwie równoprawne definicje (ta, którą podałeś, jest jedną z nich), dlatego pytam się, której używa Matys015.

JK

[Matys015]

Chciałbym użyć tą definicje : \(\displaystyle{ \exists b \left\langle a,b\right\rangle \in S \wedge \left\langle b,c \right\rangle \in R}\)

Ale do niczego nie mogę dojść. Chcąc udowodnić 1) to zakładam, że \(\displaystyle{ R \cup S}\) jest relacją równoważności i chcę pokazać \(\displaystyle{ R\cup S=RS}\). Żeby udowodnić równość, korzystam z dwóch inkluzji. Ale nie wiem jak to dalej rozpisać, czy muszę wziąć dowolną parę, czy w jakiś inny sposób ?

[Jan Kraszewski]

Załóżmy, że \(\displaystyle{ R \cup S}\) jest relacją równoważności.

1. \(\displaystyle{ R \subseteq RS}\)
Ustalmy dowolne \(\displaystyle{ \left\langle x,y\right\rangle\in R}\). Wiemy, że \(\displaystyle{ S}\) jest zwrotna, zatem \(\displaystyle{ \left\langle x,x\right\rangle\in S}\). Wobec tego...

2. \(\displaystyle{ S \subseteq RS}\)
Jak w 1.

3. \(\displaystyle{ RS \subseteq R\cup S}\)
Ustalmy dowolne \(\displaystyle{ \left\langle x,y\right\rangle\in RS}\). Istnieje zatem \(\displaystyle{ t}\) takie, że \(\displaystyle{ \left\langle x,t\right\rangle\in S}\) i \(\displaystyle{ \left\langle t,y\right\rangle\in R}\). Ale \(\displaystyle{ R \subseteq R\cup S}\) i \(\displaystyle{ S \subseteq R\cup S}\) i \(\displaystyle{ R\cup S}\) jest przechodnia, zatem...

JK

[Matys015]

Bardzo dziękuję

[kociol878]

Ja mam jeszcze pytanie do implikacji w drugą stronę. Zakładając \(\displaystyle{ R \cup S = RS}\) , mam pokazać że \(\displaystyle{ R \cup S}\) jest zwrotna, symetryczna i przechodnia ?

[Jan Kraszewski]

\(\displaystyle{ R\cup S}\) jest zwrotna i symetryczna zawsze (gdy \(\displaystyle{ R,S}\) - relacje równoważności). Pozostaje zatem pokazanie przechodniości.

JK

[kociol878]

No fakt, zwrotność i symetrię mam od razu załatwioną, natomiast co do przechodniości, \(\displaystyle{ R \subseteq R \cup S, S \subseteq R \cup S}\) oraz \(\displaystyle{ \exists b . aSb \wedge bRc}\). Czy to mi załatwi przechodniość ?

[Jan Kraszewski]

natomiast co do przechodniości, \(\displaystyle{ R \subseteq R \cup S,S \subseteq R \cup S}\) oraz \(\displaystyle{ \exists b . aSb \wedge bRc}\). Czy to mi załatwi przechodniość ?

Zakładasz, że \(\displaystyle{ R\cup S=RS}\) i pokazujesz, że \(\displaystyle{ R\cup S}\) jest przechodnia. To wymaga chwilki pokombinowania (tzn. mnie to zajęło chwilę czasu).

JK

[kociol878]

Pokombinowałem trochę i doszedłem do czegoś a mianowicie rozpisując z definicji przechodności:
\(\displaystyle{ x R \cup S y \wedge y R \cup S z \Rightarrow x RS z}\)
Tu skorzystałem z założenie że \(\displaystyle{ R\cup S=RS}\). Dalej rozpisując to wyszło coś takiego:
\(\displaystyle{ (x R y \vee x S y) \wedge (y R z \vee y S z) \Rightarrow \exists y (x R y \wedge y S z)}\)
Czy takie coś wystarczy?

[Jan Kraszewski]

\(\displaystyle{ (x R y \vee x S y) \wedge (y R z \vee y S z) \Rightarrow \exists y (x R y \wedge y S z)}\)
Czy takie coś wystarczy?

A dlaczego takie coś miałoby być prawdą?

JK