Niepusta rodzina relacji równoważności

[Augustyn Kaczmarek]

Niech \(\displaystyle{ \mathcal{R}}\) będzie niepustą rodziną relacji równoważności w zbiorze \(\displaystyle{ A}\) taką, że dla dowolnych \(\displaystyle{ r, s \in \mathcal{R}}\) zachodzi \(\displaystyle{ r \subseteq s}\) lub \(\displaystyle{ s \subseteq r}\).
Udowodnić, że \(\displaystyle{ s = \bigcup \mathcal{R}}\) jest relacją równoważności, oraz że \(\displaystyle{ [a]_s = \bigcup_{r \in \mathcal{R}} [a]_r}\), dla dowolnego \(\displaystyle{ a \in A}\).

1. To, że \(\displaystyle{ \bigcup \mathcal{R}}\) jest relacją równoważności można udowodnić po prostu z tego, że rodzina \(\displaystyle{ \mathcal{R}}\) jest łańcuchem (zachodzi \(\displaystyle{ r \subseteq s}\) lub \(\displaystyle{ s \subseteq r}\)) i wtedy istnieje jakaś relacja \(\displaystyle{ r \in \mathcal{R}}\) , która będzie zawierała wszystkie inne relacji z tej rodziny (czyli nie istnieje takiej relacji \(\displaystyle{ s \in \mathcal{R}}\), że \(\displaystyle{ r \subseteq s}\)). Wtedy, z definicji sumy uogólnionej, \(\displaystyle{ r = \bigcup \mathcal{R}}\) i \(\displaystyle{ r}\) jest relacją równoważności z def. \(\displaystyle{ \mathcal{R}}\).
2. Wynika z pierwszego.

Czy taki dowód ma sens? Trochę nie jestem pewien, czy ten dowód zadziała dla nieskończonej rodziny, bo w zadaniu nie jest to wyjaśnione.

[Jan Kraszewski]

Czy taki dowód ma sens?

Nie bardzo.

Trochę nie jestem pewien, czy ten dowód zadziała dla nieskończonej rodziny, bo w zadaniu nie jest to wyjaśnione.

Nie jest wyjaśnione, bo moc rodziny \(\displaystyle{ \mathcal{R}}\) nie ma nic do rzeczy - twierdzenie jest prawdziwe dla dowolnej takiej rodziny. I dlatego Twój dowód nie działa.

1. (...) wtedy istnieje jakaś relacja \(\displaystyle{ r \in \mathcal{R}}\) , która będzie zawierała wszystkie inne relacji z tej rodziny

To jest w ogólności nieprawda.

Udowodnij po prostu, że relacja \(\displaystyle{ \bigcup\mathcal{R}}\) jest zwrotna, symetryczna i przechodnia. Zwrotność jest trywialna, symetria prawie trywialna, a w dowodzie przechodniości skorzystasz z tego, że relacje tworzą łańcuch.

JK

[Augustyn Kaczmarek]

Nie jest wyjaśnione, bo moc rodziny \(\displaystyle{ \mathcal{R}}\) nie ma nic do rzeczy - twierdzenie jest prawdziwe dla dowolnej takiej rodziny. I dlatego Twój dowód nie działa.

Dziękuję za odpowiedź. Czyli mój dowód nie działa dla nieskończonej rodziny? A gdyby była skończona, czy można byłoby tak udowodnić?

Bardzo proszę sprawdzić, czy mój dowód jest dobry:
1. Tutaj udowodnię tylko przechodniość. Niech \(\displaystyle{ \left\langle a, b \right\rangle, \left\langle b, c \right\rangle \in s }\). Wtedy istnieją takie \(\displaystyle{ r_1, r_2 \in \mathcal{R}}\), że \(\displaystyle{ \left\langle a, b \right\rangle \in r_1}\) oraz \(\displaystyle{ \left\langle b, c \right\rangle \in r_2}\). Ponieważ \(\displaystyle{ \mathcal{R}}\) jest łańcuchem, to albo \(\displaystyle{ r_1 \subseteq r_2}\), albo \(\displaystyle{ r_2 \subseteq r_1}\). Bez straty ogólności załóżmy, że \(\displaystyle{ r_2 \subseteq r_1}\). Wtedy \(\displaystyle{ \left\langle a, b \right\rangle, \left\langle b, c \right\rangle \in r_1 }\) i ponieważ \(\displaystyle{ r_1 \in \mathcal{R}}\) jest przechodnia, to \(\displaystyle{ \left\langle a, c \right\rangle \in r_1 }\). Wtedy \(\displaystyle{ \left\langle a, c \right\rangle \in s }\), czyli \(\displaystyle{ s}\) jest przechodnia.
2. Niech \(\displaystyle{ a \in A}\).
\(\displaystyle{ ( \subseteq ) }\)
Weźmy dowolny element \(\displaystyle{ x \in [a]_s}\), wtedy \(\displaystyle{ x \ s \ a}\). Skoro \(\displaystyle{ s = \bigcup \mathcal{R}}\), wtedy instnieje taka relacja \(\displaystyle{ r \in \mathcal{R}}\), że \(\displaystyle{ x \ r \ a}\). A z tego wynika, że \(\displaystyle{ x \in [a]_r}\). Stąd \(\displaystyle{ x \in \bigcup_{r \in \mathcal{R}} [a]_r}\).
\(\displaystyle{ ( \supseteq ) }\)
Weźmy dowolny element \(\displaystyle{ x \in \bigcup_{r \in \mathcal{R}} [a]_r}\), wtedy \(\displaystyle{ x \in [a]_r}\) i \(\displaystyle{ x \ r \ a}\) dla jakieś relacji \(\displaystyle{ r \in \mathcal{R}}\). Wiemy, że \(\displaystyle{ r \subseteq \bigcup \mathcal{R}}\), czyli \(\displaystyle{ r \subseteq s}\) i wtedy \(\displaystyle{ x \ s \ a}\) oraz \(\displaystyle{ x \in [a]_s}\).

[Jan Kraszewski]

Czyli mój dowód nie działa dla nieskończonej rodziny? A gdyby była skończona, czy można byłoby tak udowodnić?

Tak (dokładniej: nie działa dla rodziny nieskończonej, która nie ma elementu największego względem zawierania) i tak.

Bardzo proszę sprawdzić, czy mój dowód jest dobry:

Jest dobry.

JK

[Jakub Gurak]

Dodam, że symetryczność tej sumy można udowodnić również tak:
Aby wykazać, że \(\displaystyle{ \bigcup\mathcal {R}}\) jest relacją symetryczną, to pokażmy, że jest ona równa swojej relacji odwrotnej. W tym celu wyznaczmy jej relację odwrotną.
Mamy:
\(\displaystyle{ \left( \bigcup\mathcal {R}\right) ^{-1}= \bigcup_{R \in \mathcal {R}}R ^{-1} = }\)
i ponieważ każda relacja \(\displaystyle{ R \in \mathcal{R}}\), jako relacja równoważności, jest symetryczna, więc mamy zawsze \(\displaystyle{ R=R ^{-1}, }\) a zatem, to jest równe:
\(\displaystyle{ = \bigcup_{R \in \mathcal{R}} R= \bigcup\mathcal {R};}\)
a więc relacja \(\displaystyle{ \bigcup\mathcal {R}}\) jest równa swojej relacji odwrotnej, jest więc relacją symetryczną\(\displaystyle{ .\square}\)