4-kołowy Diagram Venna - ilość relacji danego typu

[Jan Kraszewski]

w tym celu, najlepszym sposobem jest wypisanie wszystkich relacji binarnych, a więc począwszy od:
1. \(\displaystyle{ \emptyset}\)
2. \(\displaystyle{ (0,0)}\)
3. \(\displaystyle{ (0,1)}\)
...
16. \(\displaystyle{ (0,1), (1,0), (1,0), (1,1)}\)

To nie są relacje, poprawiłem to w Twoim poprzednim poście, ale najwyraźniej nie zauważyłeś. Relacje to zbiory tych par.

Krótko mówiąc, chciałbym wykonać to samo zadanie, nie tylko dla \(\displaystyle{ n=2}\), ale również dla \(\displaystyle{ n=3}\) i \(\displaystyle{ n=4}\). A ponieważ wypisywanie samych podzbiorów oraz sprawdzenie występujących relacji w każdym z nich jest procesem dość trudnym i długim,

Długie na pewno, ale raczej żmudne niż trudne.

to czy w Twojej ocenie, należy również na diagramie 4-kołowym pokazywać w każdej cząstce ilość relacji? Czy jedynie ogólnikowo wystarczy zaznaczyć? Ogólnikowo, mam na myśli, na podstawie znanych sześciu wzorów omawianych we wstępie.

To zależy od tego, co chcesz uzyskać

Spowodowane jest to bardzo dużą ilością podzbiorów, czyli dla \(\displaystyle{ n=3}\), tych podzbiorów byłoby:
1. \(\displaystyle{ \emptyset}\)
...
512. \(\displaystyle{ (para-obiektów),(para-obiektów)(...)}\)

Zaś, dla \(\displaystyle{ n=4}\) byłoby ich (możliwych kombinacji par obiektów) \(\displaystyle{ 65536}\).

W związku z tym, nie mam pojęcia, czy według Ciebie, wystarczyłoby policzyć jedynie ilość relacji z sześciu prezentowanych wzorów i zaznaczyć jedynie wiadome części relacji na diagramie?

Ale do czego ma wystarczyć? Zrozum, że to, co musisz wypisać zależy od tego, co chcesz uzyskać - policzysz mniej, będziesz wiedział mniej, policzysz więcej, będziesz wiedział więcej. Jeżeli chcesz mieć dokładny opis, czyli wiedzieć ile jest relacji w każdej z 14 "atomowych" części, to skorzystanie z sześciu prezentowanych wzorów nie wystarczy (tym bardziej, że nie opisują one obszarów "atomowych", tylko ich sumy).

Alternatywą do wypisywania wszystkich relacji i badania po kolei ich własności jest przyjrzenie się po kolei tym 14 obszarom i próba zbadania, ile jest relacji mających stosowne własności. Łatwe jest zauważenie np., że kawałek \(\displaystyle{ S\cap A\cap Z}\) jest zawsze jednoelementowy (dla dowolnego \(\displaystyle{ n}\) - jedyna relacja o tych własnościach to relacja równości), a kawałek \(\displaystyle{ S\cap A\cap Z'}\) ma \(\displaystyle{ 2^n-1}\) elementów. Dla niedużych \(\displaystyle{ n}\) ta metoda może być szybsza (ale nie sprawdzałem).

JK

[Gorgon24]

Dziękuję za poprawki i sugestie. Oczywiście, na podstawie źródeł internetowych oraz Twoich podpowiedzi, na ten moment wiadome są liczby relacji:
1. \(\displaystyle{ A \cap S \cap Z \cap P=1}\)
2. \(\displaystyle{ A \cap S \cap Z' \cap P=8-1=7}\) (8 się wzięła ze wzoru na liczbę \(\displaystyle{ A \cap S}\))
3. \(\displaystyle{ A \cap S \cap Z \cap P=18}\) (Z bazy oeis można dopatrzeć się, że dla częściowego porządku \(\displaystyle{ A \cap Z \cap P=19}\), jednak należy odjąć od tego \(\displaystyle{ A \cap S \cap Z \cap P=1}\), ponieważ ten "kafelek" zależności na diagramie już jest policzony)
4. \(\displaystyle{ A \cap S' \cap Z \cap P'=27-19=8}\)
5. \(\displaystyle{ A' \cap S \cap Z \cap P=5-1=4}\)
6. \(\displaystyle{ A' \cap S \cap Z \cap P'=8-5=3}\)
7. \(\displaystyle{ A' \cap S' \cap Z \cap P=29-18-5=6}\) (29 to także liczba z bazy dla relacji praporządku, czyli ilości relacji zwrotnych i przechodnich)
8. \(\displaystyle{ A' \cap S' \cap Z \cap P'=64-27-4-3-6=24}\)

Natomiast, nie mam pojęcia, jak można zabrać się za ilość relacji \(\displaystyle{ A \cap P}\) oraz \(\displaystyle{ S \cap P}\). Czy da się w tym wypadku skorzystać z jakichś własności?

[Jan Kraszewski]

3. \(\displaystyle{ A \cap S \cap Z \cap P=18}\)

Zgubiłeś jakieś dopełnienie.

JK

[Gorgon24]

3. \(\displaystyle{ A \cap S \cap Z \cap P=18}\)

Zgubiłeś jakieś dopełnienie.

JK

Rzeczywiście. Powinno być: 3. \(\displaystyle{ A \cap S' \cap Z \cap P=18}\).

[Jan Kraszewski]

4. \(\displaystyle{ A \cap S' \cap Z \cap P'=\red{27}-19=8}\)

Skąd wziąłeś to \(\displaystyle{ 27}\)?

JK

[Gorgon24]

4. \(\displaystyle{ A \cap S' \cap Z \cap P'=\red{27}-19=8}\)

Skąd wziąłeś to \(\displaystyle{ 27}\)?

JK

\(\displaystyle{ 27}\) wzięło się ze wzoru na liczebność relacji zwrotnych i antysymetrycznych: \(\displaystyle{ 3 ^ \frac{n ^{2}-n}{2}=3 ^ \frac{3 ^{2}-3}{2}=27}\)

A więc samo \(\displaystyle{ 27}\) to \(\displaystyle{ Z \cap A}\).

[Jan Kraszewski]

\(\displaystyle{ 27}\) wzięło się ze wzoru na liczebność relacji zwrotnych i antysymetrycznych: \(\displaystyle{ 3 ^ \frac{n ^{2}-n}{2}=3 ^ \frac{3 ^{2}-3}{2}=27}\)

A skąd Ty taki wzór wziąłeś?

JK

[Gorgon24]

\(\displaystyle{ 27}\) wzięło się ze wzoru na liczebność relacji zwrotnych i antysymetrycznych: \(\displaystyle{ 3 ^ \frac{n ^{2}-n}{2}=3 ^ \frac{3 ^{2}-3}{2}=27}\)

A skąd Ty taki wzór wziąłeś?

JK

Jeśli mogę wstawić link, to stąd (ze strony 6):

Kod: Zaznacz cały

http://iiitdm.ac.in/old/Faculty_Teaching/Sadagopan/pdf/Discrete/Relations.pdf

Na tej stronie jest taki rozdział poświęcony "Counting Special Relations". Oczywiście, wszystko jest tam poparte dowodami na prawdziwość takich wzorów.

Stąd się właśnie wzięło pytanie, jak można policzyć ilość relacji antysymetrycznych i przechodnich oraz symetrycznych i przechodnich, bo tak naprawdę takich wzorów jawnych nie widzę.

[Jan Kraszewski]

Natomiast, nie mam pojęcia, jak można zabrać się za ilość relacji \(\displaystyle{ A \cap P}\) oraz \(\displaystyle{ S \cap P}\). Czy da się w tym wypadku skorzystać z jakichś własności?

Chyba trzeba już trochę "na palcach".

Relacja symetryczna powstaje poprzez podjęcie trzech niezależnych decyzji TAK-NIE w odniesieniu do par \(\displaystyle{ (0,1),(0,2),(1,2)}\), a potem dołożeniu dowolnego podzbioru przekątnej \(\displaystyle{ \{(n,n):n\in\{0,1,2\}\}}\). Zauważ dalej, że jeśli podejmiemy przynajmniej dwie decyzje TAK, to przechodniość wymusza zwrotność. Jeżeli dodatkowo chcemy mieć relację nieantysymetryczną, to musimy podjąć przynajmniej jedną decyzję TAK. Wreszcie, w przypadku podjęcia jednej decyzji TAK, przechodniość i brak zwrotności determinują to, co będzie na przekątnej. Zatem

\(\displaystyle{ A'\cap S\cap Z'\cap P=3.}\)

Jeżeli zrezygnujemy z rozpatrywania przechodniości, to bierzemy wszystkie relacje symetryczne, które powstają w wyniku podjęcia przynajmniej jednej decyzji TAK, którym dokładamy na przekątnej dowolny jej podzbiór niebędący całą przekątną. Zatem \(\displaystyle{ A'\cap S\cap Z'=7\cdot 7=49.}\) Stąd

\(\displaystyle{ A'\cap S\cap Z'\cap P'=49-3=46.}\)

JK

PS
Oczywiście własności niebieska i fioletowa działają tylko dla \(\displaystyle{ n=3.}\)

[Gorgon24]

Natomiast, nie mam pojęcia, jak można zabrać się za ilość relacji \(\displaystyle{ A \cap P}\) oraz \(\displaystyle{ S \cap P}\). Czy da się w tym wypadku skorzystać z jakichś własności?

Chyba trzeba już trochę "na palcach".

Relacja symetryczna powstaje poprzez podjęcie trzech niezależnych decyzji TAK-NIE w odniesieniu do par \(\displaystyle{ (0,1),(0,2),(1,2)}\), a potem dołożeniu dowolnego podzbioru przekątnej \(\displaystyle{ \{(n,n):n\in\{0,1,2\}\}}\). Zauważ dalej, że jeśli podejmiemy przynajmniej dwie decyzje TAK, to przechodniość wymusza zwrotność. Jeżeli dodatkowo chcemy mieć relację nieantysymetryczną, to musimy podjąć przynajmniej jedną decyzję TAK. Wreszcie, w przypadku podjęcia jednej decyzji TAK, przechodniość i brak zwrotności determinują to, co będzie na przekątnej. Zatem

\(\displaystyle{ A'\cap S\cap Z'\cap P=3.}\)

Jeżeli zrezygnujemy z rozpatrywania przechodniości, to bierzemy wszystkie relacje symetryczne, które powstają w wyniku podjęcia przynajmniej jednej decyzji TAK, którym dokładamy na przekątnej dowolny jej podzbiór niebędący całą przekątną. Zatem \(\displaystyle{ A'\cap S\cap Z'=7\cdot 7=49.}\) Stąd

\(\displaystyle{ A'\cap S\cap Z'\cap P'=49-3=46.}\)

JK

PS
Oczywiście własności niebieska i fioletowa działają tylko dla \(\displaystyle{ n=3.}\)

Hmm... rzeczywiście, zgadza się. Dziękuję za rozjaśnienie.

Natomiast, co do pozostałych części, wiadomo również, że liczba relacji antysymetrycznych, które nie są jednocześnie zwrotne, czyli \(\displaystyle{ A \cap S \cap Z' \cap P}\) to:
\(\displaystyle{ 3 ^{ \frac{n ^{2}-n }{2} }\cdot 2 ^{n}-3 ^{ \frac{n ^{2}-n }{2} }=3 ^{ \frac{n ^{2}-n }{2} }\cdot(2 ^{n}-1)=189 }\)

Wzór wziął się stąd, że:
Dla antysymetrii można wybrać n liczb ukośnych na \(\displaystyle{ 2^{n}}\) sposobów (albo 0 albo 1). W przypadku braku zwrotności wymagamy, aby co najmniej jeden przekątny element miał wartość 1. Tak więc, liczymy dla odwrotnego przypadku, gdy wszystkie dane przekątne są równe 0. Liczba relacji antysymetrycznych ze wszystkimi przekątnymi całkowitymi wynosi zero ( relacje, które są niezwrotne) to: \(\displaystyle{ 3 ^{ \frac{n ^{2}-n }{2} }}\).

Tak więc liczba relacji antysymetrycznych, które NIE są niezwrotne, wynosi: \(\displaystyle{ 3 ^{ \frac{n ^{2}-n }{2} }\cdot 2 ^{n}-3 ^{ \frac{n ^{2}-n }{2} }}\).

Idąc tym tropem, część wspólna wszystkich relacji, dla \(\displaystyle{ n=3}\), jest równa \(\displaystyle{ 7}\), czyli \(\displaystyle{ 189-7=182}\). Jednak, w dalszym ciągu nie jest wiadomo, ile jest relacji:
\(\displaystyle{ A \cap Z' \cap P' \cap S'}\) oraz \(\displaystyle{ A \cap Z' \cap P \cap S'}\).

[Jan Kraszewski]

Natomiast, co do pozostałych części, wiadomo również, że liczba relacji antysymetrycznych, które nie są jednocześnie zwrotne, czyli \(\displaystyle{ A \cap S \cap Z' \cap P}\) to:
\(\displaystyle{ 3 ^{ \frac{n ^{2}-n }{2} }\cdot 2 ^{n}-3 ^{ \frac{n ^{2}-n }{2} }=3 ^{ \frac{n ^{2}-n }{2} }\cdot(2 ^{n}-1)=189 }\)

To jednak nie jest \(\displaystyle{ A \cap S \cap Z' \cap P}\), bo to policzyłeś tutaj:

2. \(\displaystyle{ A \cap S \cap Z' \cap P=8-1=7}\) (8 się wzięła ze wzoru na liczbę \(\displaystyle{ A \cap S}\))

Wydaje się, że chcesz policzyć \(\displaystyle{ A \cap S' \cap Z'.}\)

Wzór wziął się stąd, że:
Dla antysymetrii można wybrać n liczb ukośnych na \(\displaystyle{ 2^{n}}\) sposobów (albo 0 albo 1). W przypadku braku zwrotności wymagamy, aby co najmniej jeden przekątny element miał wartość 1. Tak więc, liczymy dla odwrotnego przypadku, gdy wszystkie dane przekątne są równe 0. Liczba relacji antysymetrycznych ze wszystkimi przekątnymi całkowitymi wynosi zero ( relacje, które są niezwrotne) to: \(\displaystyle{ 3 ^{ \frac{n ^{2}-n }{2} }}\).

Tak więc liczba relacji antysymetrycznych, które NIE są niezwrotne, wynosi: \(\displaystyle{ 3 ^{ \frac{n ^{2}-n }{2} }\cdot 2 ^{n}-3 ^{ \frac{n ^{2}-n }{2} }}\).

Idąc tym tropem, część wspólna wszystkich relacji, dla \(\displaystyle{ n=3}\), jest równa \(\displaystyle{ 7}\), czyli \(\displaystyle{ 189-7=182}\).

Z mojego punktu widzenia nie jest to najlepiej opisane, ale też uważam, że liczność zbioru \(\displaystyle{ A \cap S' \cap Z'}\) to \(\displaystyle{ \left( 3 ^{ \frac{n ^{2}-n }{2} }-1\right) \cdot(2 ^{n}-1)}\), czyli w tym wypadku \(\displaystyle{ 182}\).

Jednak, w dalszym ciągu nie jest wiadomo, ile jest relacji:
\(\displaystyle{ A \cap Z' \cap P' \cap S'}\) oraz \(\displaystyle{ A \cap Z' \cap P \cap S'}\).

Cóż, znów trzeba próbować "na palcach"...

JK

[Gorgon24]

Jednak, w dalszym ciągu nie jest wiadomo, ile jest relacji:
\(\displaystyle{ A \cap Z' \cap P' \cap S'}\) oraz \(\displaystyle{ A \cap Z' \cap P \cap S'}\).

Cóż, znów trzeba próbować "na palcach"...

JK

Hmm... czy obliczanie "na palcach" ilości relacji podzielności miałoby sens? Mam na myśli taką sytuację:
Jeśli istnieje tylko jedna klasa \(\displaystyle{ A=\{a,b,c\}}\), to istnieje jednoznaczny porządek częściowy, co daje \(\displaystyle{ 1}\) preorder, a więc \(\displaystyle{ 1}\) relację przechodnią.

Jeśli istnieją dwie klasy, powiedzmy \(\displaystyle{ C}\) i \(\displaystyle{ C′}\), to istnieją trzy rzędy cząstkowe: \(\displaystyle{ C≤C′}\) lub \(\displaystyle{ C′≤C}\), lub te dwie klasy są nieporównywalne. Ponieważ istnieją trzy sposoby podziału \(\displaystyle{ A}\) na dwie klasy, a każdy sposób daje trzy częściowe zamówienia, istnieje \(\displaystyle{ 9}\) takich praporządków. Każde z tych preorderów ma tylko jedną klasę singleton, więc mamy \(\displaystyle{ 9⋅2^{1}=18}\) relacji przechodnich.

Ostatecznie, jeśli istnieją trzy klasy, powiedzmy \(\displaystyle{ C_1, C_2}\) i \(\displaystyle{ C_3}\), to jest \(\displaystyle{ 19}\) częściowych porządków "partial orders", co daje \(\displaystyle{ 19}\) praporządków (ponieważ istnieje unikalny sposób na podzielenie \(\displaystyle{ A}\) na trzy klasy). Zaś, co za tym idzie, ponieważ są trzy singletony klas (zbiorów jednostkowych), do relacji przechodnich \(\displaystyle{ 19⋅2^{3}=152}\). Liczba \(\displaystyle{ 19}\) wzięła się stąd, ponieważ: istnieje \(\displaystyle{ 1}\) dyskretny porządek częściowy (żadna z klas nie jest porównywalna), \(\displaystyle{ 6}\) porządków częściowych, w których jeden element jest nieporównywalny z pozostałymi dwoma (a pozostałe dwa są porównywalne), \(\displaystyle{ 3}\), w których jeden element jest poniżej pozostałych dwóch (i pozostałe dwa są nieporównywalne), \(\displaystyle{ 3}\), w którym jeden element znajduje się nad pozostałymi dwoma (a pozostałe dwa są nieporównywalne), oraz \(\displaystyle{ 6}\) rzędów liniowych.

W sumie istnieje \(\displaystyle{ 1+18+152=171}\) relacji przechodnich na \(\displaystyle{ A}\).

Jednak, czy to jest pomocna informacja do wyznaczenia omawianych podzbiorów?

Przyznam szczerze, że nie mam już pomysłów. Czy mogę liczyć na Twoją (ostatnią już) podpowiedź?

[Jan Kraszewski]

Mam na myśli taką sytuację:
Jeśli istnieje tylko jedna klasa \(\displaystyle{ A=\{a,b,c\}}\), to istnieje jednoznaczny porządek częściowy, co daje \(\displaystyle{ 1}\) preorder, a więc \(\displaystyle{ 1}\) relację przechodnią.

Jeśli istnieją dwie klasy, powiedzmy \(\displaystyle{ C}\) i \(\displaystyle{ C′}\), to istnieją trzy rzędy cząstkowe: \(\displaystyle{ C≤C′}\) lub \(\displaystyle{ C′≤C}\), lub te dwie klasy są nieporównywalne. Ponieważ istnieją trzy sposoby podziału \(\displaystyle{ A}\) na dwie klasy, a każdy sposób daje trzy częściowe zamówienia, istnieje \(\displaystyle{ 9}\) takich praporządków. Każde z tych preorderów ma tylko jedną klasę singleton, więc mamy \(\displaystyle{ 9⋅2^{1}=18}\) relacji przechodnich.

Ostatecznie, jeśli istnieją trzy klasy, powiedzmy \(\displaystyle{ C_1, C_2}\) i \(\displaystyle{ C_3}\), to jest \(\displaystyle{ 19}\) częściowych porządków "partial orders", co daje \(\displaystyle{ 19}\) praporządków (ponieważ istnieje unikalny sposób na podzielenie \(\displaystyle{ A}\) na trzy klasy). Zaś, co za tym idzie, ponieważ są trzy singletony klas (zbiorów jednostkowych), do relacji przechodnich \(\displaystyle{ 19⋅2^{3}=152}\). Liczba \(\displaystyle{ 19}\) wzięła się stąd, ponieważ: istnieje \(\displaystyle{ 1}\) dyskretny porządek częściowy (żadna z klas nie jest porównywalna), \(\displaystyle{ 6}\) porządków częściowych, w których jeden element jest nieporównywalny z pozostałymi dwoma (a pozostałe dwa są porównywalne), \(\displaystyle{ 3}\), w których jeden element jest poniżej pozostałych dwóch (i pozostałe dwa są nieporównywalne), \(\displaystyle{ 3}\), w którym jeden element znajduje się nad pozostałymi dwoma (a pozostałe dwa są nieporównywalne), oraz \(\displaystyle{ 6}\) rzędów liniowych.

W sumie istnieje \(\displaystyle{ 1+18+152=171}\) relacji przechodnich na \(\displaystyle{ A}\).

Jak mam być szczery, to nie bardzo rozumiem, co liczysz - nie wiem, co to są "klasy" czy "rzędy cząstkowe".

Ja patrzę na to tak. Zbiór \(\displaystyle{ A\cap S'\cap Z'}\) ma \(\displaystyle{ 182}\) elementy. Postaram się ustalić, ile spośród tych relacji nie jest przechodnich. Żeby relacja \(\displaystyle{ R}\) nie była przechodnia, to musi istnieć kontrprzykład, czyli takie trzy elementy \(\displaystyle{ x,y,z}\), że \(\displaystyle{ (x,y)\in R}\) i \(\displaystyle{ (y,z)\in R}\), ale \(\displaystyle{ (x,z)\notin R}\). Ponieważ rozważamy relacje, które są antysymetryczne, więc elementy \(\displaystyle{ x,y,z}\) muszą być różne. Ale trzy różne elementy można wybrać ze zbioru trzyelementowego (uwzględniając kolejność) na \(\displaystyle{ 3!}\) możliwości. Do tak wybranego kontrprzykładu możemy dołożyć cokolwiek na przekątnej (ale nie wszystko).

Wobec tego - według mnie - zbiór \(\displaystyle{ A\cap S'\cap Z'\cap P'}\) ma \(\displaystyle{ 3!\cdot 7=42}\) elementy, zatem zbiór \(\displaystyle{ A\cap S'\cap Z'\cap P}\) ma \(\displaystyle{ 182-42=140}\) elementów.

Wtedy jednak liczność zbioru \(\displaystyle{ A\cap P}\) to \(\displaystyle{ 140+1+7+18=166}\), co nie zgadza się z Twoim rachunkiem.

JK

edit: OK, już rozumiem - policzyłeś wszystkie relacje przechodnie i ich istotnie jest \(\displaystyle{ 171}\) - zmyliło mnie dwuznaczne użycie literki \(\displaystyle{ A}\)...

[Gorgon24]

edit: OK, już rozumiem - policzyłeś wszystkie relacje przechodnie i ich istotnie jest \(\displaystyle{ 171}\) - zmyliło mnie dwuznaczne użycie literki \(\displaystyle{ A}\)...

Zgadza się. Po prostu niepotrzebnie użyłem tej samej literki jako oznaczenie zbioru. Natomiast, paradoks polega na tym, że osobno, wyliczając każdy podzbiór (\(\displaystyle{ Z = 64}\), \(\displaystyle{ S = 64}\), \(\displaystyle{ A = 216}\)), wyniki się zgadzają.

\(\displaystyle{ Z=24+6+8+18+1+4+3=64}\) - zgadza się.
\(\displaystyle{ S=46+1+4+3+7+3=64}\) - zgadza się.
\(\displaystyle{ A=42+140+18+8+1+7=216}\) - zgadza się.

Jednak, po zsumowaniu tych obszarów, dla przechodniości otrzymamy:
\(\displaystyle{ P = 140+18+6+4+3+1+7=179}\), co jest sprzeczne z liczbą \(\displaystyle{ 171}\).
Zatem, czy wkradł się błąd w obliczeniach?

[Jan Kraszewski]

Jest nawet więcej.... Wydaje mi się, że potrafię uzasadnić, że zbiór \(\displaystyle{ A'\cap S'\cap Z'\cap P}\) ma sześć elementów, co dawałoby łącznie \(\displaystyle{ 1+7+18+4+6+3+140+6=185}\) relacji przechodnich, czyli o \(\displaystyle{ 14}\) za dużo. Coś zatem zostało przeoczone.

Podejrzewam, że liczba \(\displaystyle{ 42}\) jest za mała i w związku z tym liczba \(\displaystyle{ 140}\) jest za duża.

JK