Narysować diagram Hassego

[tweant]

Dane są zbiory \(\displaystyle{ X= \left \{ a,b,c,d \right \}}\), \(\displaystyle{ P}\) - zbiór relacji równoważności na \(\displaystyle{ X}\), \(\displaystyle{ A=\left \{ R \in P:\left | \left [ a \right ]_{R} \right |\leq 1\vee \left | \left [ b \right ]_{R} \right |\leq 1\right \}}\). Narysować diagram Hassego dla zbioru A. Jest on uporządkowany przez relację inkluzji. Wskazać element minimalny, maksymalny, najmniejszy i największy.

Miałem to zadanie na egzaminie i zupełnie nie mam pomysłu jak je rozwiązać. Zbiór a ma chyba coś wspólnego z klasami abstrakcji, ale szczerze powiedziawszy nigdy żadnej na zajęciach nie zapisaliśmy. Sam starając się je zrozumieć nie natrafiłem na taki symbol \(\displaystyle{ \left [ a \right ]_{R} \right}\). Będę wdzięczny za podpowiedź lub najlepiej rozwiązanie.

[Jan Kraszewski]

Sam starając się je zrozumieć nie natrafiłem na taki symbol \(\displaystyle{ \left [ a \right ]_{R} \right}\).

No to słabo, bo \(\displaystyle{ [a]_R}\) to klasa abstrakcji elementu \(\displaystyle{ a}\) w relacji równoważności \(\displaystyle{ R}\).

Najlepiej chyba zacząć od wypisania wszystkich elementów zbioru \(\displaystyle{ A}\).

JK

[tweant]

No i właśnie tutaj jest cały problem. Moje rozumowanie: Moc klasy abstrakcji nigdy nie jest równa 0 zatem \(\displaystyle{ \left [ a \right ]_{R} = 1}\) czyli \(\displaystyle{ a}\) jest w relacji tylko ze samym sobą, podobnie \(\displaystyle{ b}\). Zatem \(\displaystyle{ A}\) to zbiór takich relacji ze zbioru \(\displaystyle{ P}\), że tylko \(\displaystyle{ a}\) lub \(\displaystyle{ b}\) jest w sobą w relacji. Ale ja nie rozumiem jak zapisać zbiór \(\displaystyle{ P}\). Jak mogę wypisać wszystkie relacje równoważności?

[Jan Kraszewski]

Moc klasy abstrakcji nigdy nie jest równa 0 zatem \(\displaystyle{ \left [ a \right ]_{R} = 1}\) czyli \(\displaystyle{ a}\) jest w relacji tylko ze samym sobą, podobnie \(\displaystyle{ b}\).

Dobrze, ale uważaj z tym "podobnie" - tam jest warunek "lub".

Zatem \(\displaystyle{ A}\) to zbiór takich relacji ze zbioru \(\displaystyle{ P}\), że tylko \(\displaystyle{ a}\) lub \(\displaystyle{ b}\) jest w sobą w relacji. Ale ja nie rozumiem jak zapisać zbiór \(\displaystyle{ P}\). Jak mogę wypisać wszystkie relacje równoważności?

Normalnie. Wypisanie relacji równoważności jest możliwe, gdy skorzystamy z ich utożsamienia z podziałami zbioru. Zbiór \(\displaystyle{ A}\) rozpada się na dwa zbiory - tych relacji, dla których \(\displaystyle{ \left [ a \right ]_{R} = 1}\) i tych, dla których \(\displaystyle{ \left [ b \right ]_{R} = 1}\). Zajmij się pierwszym z nich (z drugim będzie analogicznie). Wiesz, że \(\displaystyle{ a}\) jest w relacji tylko same z sobą, więc pozostają Ci elementy \(\displaystyle{ b,c,d}\). Zatem wypisanie relacji z tego pierwszego kawałka zbioru \(\displaystyle{ A}\) sprowadza się do wypisania wszystkich podziałów zbioru \(\displaystyle{ \{b,c,d\}}\). To nie jest trudne (było zresztą nie tak dawno temu na forum).

JK

[tweant]

OK. Dla \(\displaystyle{ a}\) podziały zbioru \(\displaystyle{ \left\{ b,c,d\right\}}\) to:
\(\displaystyle{ \left\{ \left\{ b,c,d\right\} \right\} ,\left\{ \left\{ b,c\right\},\left\{ d\right\} \right\} , \left\{ \left\{ b,d\right\},c \right\} , \left\{ \left\{ c,d\right\},\left\{ b\right\} \right\} ,\left\{ \left\{ b\right\} ,\left\{ c\right\} ,\left\{ d\right\} \right\}}\)

Dla \(\displaystyle{ b}\) podziały zbioru \(\displaystyle{ \left\{ a,c,d\right\}}\) to:
\(\displaystyle{ \left\{ \left\{ a,c,d\right\} \right\} ,\left\{ \left\{ a,c\right\},\left\{ d\right\} \right\} , \left\{ \left\{ a,d\right\},c \right\} , \left\{ \left\{ c,d\right\},\left\{ a\right\} \right\} ,\left\{ \left\{ a\right\} ,\left\{ c\right\} ,\left\{ d\right\} \right\}}\)

I zbiór A to suma tych zbiorów?

[Jan Kraszewski]

OK. Dla \(\displaystyle{ a}\) podziały zbioru \(\displaystyle{ \left\{ b,c,d\right\}}\) to:
\(\displaystyle{ \left\{ \left\{ b,c,d\right\} \right\} ,\left\{ \left\{ b,c\right\},\left\{ d\right\} \right\} , \left\{ \left\{ b,d\right\},c \right\} , \left\{ \left\{ c,d\right\},\left\{ b\right\} \right\} ,\left\{ \left\{ b\right\} ,\left\{ c\right\} ,\left\{ d\right\} \right\}}\)

Dla \(\displaystyle{ b}\) podziały zbioru \(\displaystyle{ \left\{ a,c,d\right\}}\) to:
\(\displaystyle{ \left\{ \left\{ a,c,d\right\} \right\} ,\left\{ \left\{ a,c\right\},\left\{ d\right\} \right\} , \left\{ \left\{ a,d\right\},c \right\} , \left\{ \left\{ c,d\right\},\left\{ a\right\} \right\} ,\left\{ \left\{ a\right\} ,\left\{ c\right\} ,\left\{ d\right\} \right\}}\)

Prawie dobrze. Dwa razy napisałeś \(\displaystyle{ c}\) zamiast \(\displaystyle{ \{c\}}\).

I zbiór A to suma tych zbiorów?

No skąd. Z każdym takim podziałem związana jest jedna relacja równoważności i to one są elementami zbioru \(\displaystyle{ A}\). Możesz nawet wypisać sobie te podziały \(\displaystyle{ \{a,b,c,d\}}\), które odpowiadają relacjom z \(\displaystyle{ A}\) - jak nietrudno zauważyć, będzie ich osiem. Jak już to zrobisz, musisz zastanowić się, jak to, że relacja \(\displaystyle{ R_1}\) zawiera się w relacji \(\displaystyle{ R_2}\) (myślimy o relacjach jako o podzbiorach \(\displaystyle{ X^2}\)) przekłada się na zależność pomiędzy odpowiadającymi im podziałami (które znasz). Jak już to będziesz wiedział, będziesz gotowy do rysowania diagramu Hassego.

JK

[tweant]

Szczerze powiedziawszy to już się totalnie pogubiłem. Napisał Pan, że:

Zatem wypisanie relacji z tego pierwszego kawałka zbioru A sprowadza się do wypisania wszystkich podziałów zbioru \(\displaystyle{ \{b,c,d\}}\).

Wypisałem je. Jest 5 takich podziałów dla \(\displaystyle{ a}\) i 5 dla \(\displaystyle{ b}\).

Możesz nawet wypisać sobie te podziały\(\displaystyle{ \{a,b,c,d\}}\), które odpowiadają relacjom z \(\displaystyle{ A}\) - jak nietrudno zauważyć, będzie ich osiem.

Dlaczego i skąd akurat osiem? Dla mnie relacja to zbiór dwuelementowy. I jak to możliwe, że jedna relacja zawiera się w drugiej?

[Jan Kraszewski]

Szczerze powiedziawszy to już się totalnie pogubiłem. Napisał Pan, że:

Zatem wypisanie relacji z tego pierwszego kawałka zbioru A sprowadza się do wypisania wszystkich podziałów zbioru \(\displaystyle{ \{b,c,d\}}\).

Wypisałem je. Jest 5 takich podziałów dla \(\displaystyle{ a}\) i 5 dla \(\displaystyle{ b}\).

Ale to są podziały pomocnicze, bo singleton \(\displaystyle{ \{a\}}\) (lub singleton \(\displaystyle{ \{b\}}\)) masz już ustalony. Teraz trzeba do tych podziałów dodać te singletony i dostaniesz podziały \(\displaystyle{ \{a,b,c,d\}}\), a to one nas interesują (bo odpowiadają relacjom z \(\displaystyle{ A}\)). Będzie ich osiem, bo - jak zauważysz - po dodaniu singletonów dwa podziały powtórzą się.

Dla mnie relacja to zbiór dwuelementowy.

Jaki zbiór dwuelementowy?! Relacja to zbiór par uporządkowanych, ale co to ma wspólnego z dwuelementowością? Może masz braki na etapie zrozumienia definicji relacji.

Poza tym my cały czas jesteśmy na etapie podziałów, bo łatwiej jest wypisać. Teraz, korzystając z wiedzy o zależności pomiędzy podziałami a relacjami równoważności, zajmiemy się tymi drugimi, co jest naszym celem.

I jak to możliwe, że jedna relacja zawiera się w drugiej?

Normalnie, przecież relacje to zbiory i zawierają się jako zbiory. Cały dowcip polega na tym, by zrozumieć, jak ta zwykła zależność miedzy relacjami jako zbiorami wpływa na ich własności jako relacji równoważności i w konsekwencji, na zależności pomiędzy związanymi z nimi podziałami.

Właśnie dlatego to jest ładne zadanie, bo sprawdza, czy rozumiesz te pojęcia i umiesz nimi ze zrozumieniem operować, czy tylko wyuczyłeś się bez zrozumienia definicji i nauczyłeś się rozwiązywać schematyczne zadania.

JK

[tweant]

Teraz widzę, że dwa elementy powielają się. Jednak nie widzę jak zależność miedzy relacjami jako zbiorami wpływa na ich własności jako relacji równoważności.

Przeglądałem swoje notatki poza definicją podziału i stwierdzeniem o istnieniu dokładnie jednej relacji równoważności dla każdego podziału. Chyba nie będzie mi dane zrozumieć tej magii

[Jan Kraszewski]

To nie jest magia. Ale wymaga to trochę kreatywnego wysiłku umysłowego - nie wszystko znajdziesz w notatkach/podręczniku, istotą uczenia jest to, byś nie tylko poznał definicje/twierdzenia, ale też nauczył się stosować je w nowych dla siebie sytuacjach.

Masz zatem dwie relacje równoważności \(\displaystyle{ R_1,R_2\in A}\) takie, że \(\displaystyle{ R_1 \subseteq R_2}\). Oznacza to (z def. zawierania), że jeśli \(\displaystyle{ \left\langle x,y\right\rangle\in R_1}\), to \(\displaystyle{ \left\langle x,y\right\rangle\in R_2}\). Ale to znaczy przecież, że jeśli \(\displaystyle{ x}\) i \(\displaystyle{ y}\) są równoważne w sensie relacji \(\displaystyle{ R_1}\), to są równoważne w sensie relacji \(\displaystyle{ R_2}\). Ale stąd mamy następne spostrzeżenie: jeśli mamy klasę abstrakcji relacji \(\displaystyle{ R_1}\), to zawiera się ona w klasie abstrakcji relacji \(\displaystyle{ R_2}\). No dobrze, ale ta informacja pozwala nam już identyfikować patrząc na podziały, które z nich odpowiadają relacjom będącym w relacji zawierania: np. relacja odpowiadająca podziałowi \(\displaystyle{ \{\{a\},\{b\},\{c,d\}\}}\) zawiera się w relacji odpowiadającej podziałowi \(\displaystyle{ \{\{a\},\{b,c,d\}\}}\), a nie zawiera się w relacji odpowiadającej podziałowi \(\displaystyle{ \{\{a\},\{b,c\},\{d\}\}}\). Teraz wystarczy wypisać te 8 podziałów, oznaczyć jakoś odpowiadające im relacje równoważności i narysować diagram Hassego.

JK

[tweant]

Czy taki diagram z takim opisem jest prawidłowy?

AU

KG8jzmn.jpg (27.77 KiB) Przejrzano 191 razy

Gdzie:
\(\displaystyle{ R _{1}}\) odpowiada podziałowi \(\displaystyle{ \left\{ \left\{ b,c,d\right\} ,\left\{ a\right\}\right\}}\)
\(\displaystyle{ R _{2}}\) odpowiada podziałowi \(\displaystyle{ \left\{ \left\{ b,c\right\} ,\left\{ d\right\} ,\left\{ a\right\} \right\}}\)
\(\displaystyle{ R _{3}}\) odpowiada podziałowi \(\displaystyle{ \left\{ \left\{ b,d\right\} ,\left\{ c\right\} ,\left\{ a\right\} \right\}}\)
\(\displaystyle{ R _{4}}\) odpowiada podziałowi \(\displaystyle{ \left\{\left\{ c,d\right\} ,\left\{ b\right\} ,\left\{ a\right\} \right\}}\)
\(\displaystyle{ R _{5}}\) odpowiada podziałowi \(\displaystyle{ \left\{ \left\{ a\right\} ,\left\{ b\right\} ,\left\{ c\right\} ,\left\{ d\right\} \right\}}\)
\(\displaystyle{ R _{6}}\) odpowiada podziałowi \(\displaystyle{ \left\{\left\{ a,c,d\right\} ,\left\{ b\right\} \right\}}\)
\(\displaystyle{ R _{7}}\) odpowiada podziałowi \(\displaystyle{ \left\{\left\{ a,c\right\} ,\left\{ d\right\} ,\left\{ b\right\} \right\}}\)
\(\displaystyle{ R _{8}}\) odpowiada podziałowi \(\displaystyle{ \left\{\left\{ a,d\right\},\left\{ c\right\} ,\left\{ b\right\} \right\}}\)

[Jan Kraszewski]

Tak, jest dobrze.

JK