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

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Gorgon24
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 31 maja 2021, o 15:25
Płeć: Mężczyzna
wiek: 24

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

Post autor: Gorgon24 »

Cześć!
Mam pewien problem, związany z przedstawieniem wszystkich relacji w diagramie. Diagram łączy 4 koła relacji, które są odpowiednio: Z(zwrotna), S(symetryczna), A(antysymetryczna) i P(przechodnia) - poglądowy obraz, na którym utknąłem (dla n = 2), znajduje się w załączniku.
Problem pojawia się wówczas, gdy dany diagram tworzy 16 podzbiorów (różnych części). Nie wiem, czy dobrze rozumiem, dla diagramu Venna 4−kołowego, ilość relacji należy policzyć 16−stoma różnymi wzorami?
Znane są wzory jedynie na ilość:
Tak naprawdę, znane są jedynie wzory na ilość relacji:
− zwrotnych,
− symetrycznych,
− antysymetrycznych,
− przechodnich (brak jawnego wzoru, istnieje liczebność dla przechodniości ciągu A006905 w bazie oeis org),
− zwrotnych i symetrycznych,
− zwrotnych i antysymetrycznych,
− symetrycznych i antysymetrycznych.
Można zatem obliczyć 6 obszarów spośród 16 podzbiorów (po podstawieniu za konkretną wartość n−elementowego zbioru). Czy da się w jakiś sposób obliczyć pozostałe z podzbiorów (ich dopełnień)?
Byłbym zobowiązany za wszelką pomoc i wskazówki! :)

Kod: Zaznacz cały

https://imgur.com/a/PA10C44
Jan Kraszewski
Administrator
Administrator
Posty: 34128
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

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

Post autor: Jan Kraszewski »

Ten diagram akurat nie jest diagramem Venna, ale poprawnie oddaje zależności pomiędzy tymi typami relacji. Jest jak widać tylko 14 obszarów "atomowych", zatem wszystkich możliwych kombinacji własności bądź ich braku jest \(\displaystyle{ 2^{14}.}\)

JK
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

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

Post autor: a4karo »

A gdzie jest obszar, w którym są elementy należące tylko do A i S?
Jan Kraszewski
Administrator
Administrator
Posty: 34128
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

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

Post autor: Jan Kraszewski »

a4karo pisze: 31 maja 2021, o 17:15 A gdzie jest obszar, w którym są elementy należące tylko do A i S?
Zauważ, że każda relacja, która jest równocześnie symetryczna i antysymetryczna, jest także przechodnia (bo jest podzbiorem relacji równości) i dlatego obszar \(\displaystyle{ A\cap S}\) jest zawarty w obszarze \(\displaystyle{ P}\).

JK
Gorgon24
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 31 maja 2021, o 15:25
Płeć: Mężczyzna
wiek: 24

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

Post autor: Gorgon24 »

Jan Kraszewski pisze: 31 maja 2021, o 17:00 Ten diagram akurat nie jest diagramem Venna, ale poprawnie oddaje zależności pomiędzy tymi typami relacji. Jest jak widać tylko 14 obszarów "atomowych", zatem wszystkich możliwych kombinacji własności bądź ich braku jest \(\displaystyle{ 2^{14}.}\)

JK
Racja. \(\displaystyle{ A\cap Z \cap P' \cap S}\) oraz \(\displaystyle{ A\cap Z' \cap P \cap S}\) to części/podzbiory zawsze puste. Stąd, pomija się 2 podzbiory z 16 możliwych.
Zatem, dla n = 0, otrzymujemy relację pustą (zwrotną, symetryczną, antysymetryczną oraz przechodnią). Wydaje mi się, że dla n = 1, otrzymamy dwie relacje (jedna - relacja pusta dla \(\displaystyle{ A\cap Z \cap P \cap S}\), a druga - \(\displaystyle{ A\cap Z \cap P' \cap S}\)). Jednak, nie bardzo wiem, jak sprawa przedstawiałaby się dla n = 2 i jej liczebność poszczególnych zbiorów.

Pozdrawiam serdecznie.
Jan Kraszewski
Administrator
Administrator
Posty: 34128
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

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

Post autor: Jan Kraszewski »

Gorgon24 pisze: 31 maja 2021, o 18:06Wydaje mi się, że dla n = 1, otrzymamy dwie relacje (jedna - relacja pusta dla \(\displaystyle{ A\cap Z \cap P \cap S}\)
Źle. Relacja pusta na zbiorze niepustym nie jest zwrotna.
Gorgon24 pisze: 31 maja 2021, o 18:06a druga - \(\displaystyle{ A\cap Z \cap P' \cap S}\)).
Też źle. Relacja pełna na zbiorze jednoelementowym jest przechodnia.
Gorgon24 pisze: 31 maja 2021, o 18:06Jednak, nie bardzo wiem, jak sprawa przedstawiałaby się dla n = 2 i jej liczebność poszczególnych zbiorów.
Dla \(\displaystyle{ n=2}\) wszystkich relacji (na zbiorze dwuelementowym) jest \(\displaystyle{ 16}\) i są to bardzo proste relacje, więc możesz je sobie wszystkie wypisać i sprawdzić, jakie mają własności.

JK
Gorgon24
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 31 maja 2021, o 15:25
Płeć: Mężczyzna
wiek: 24

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

Post autor: Gorgon24 »

Jan Kraszewski pisze: 31 maja 2021, o 19:55
Ad, 1
Rozumiem. Zatem... Czy n = 0 można interpretować jako podzbiór zbioru pustego?

Ad. 2
Rzeczywiście, źle zanotowałem. Znak apostrofu powinien być przy zbiorze Z'.

Ad. 3
Jeśli chodzi o własności poszczególnych 16-stu podzbiorów, wykonałem taką tabelkę:

Kod: Zaznacz cały

https://imgur.com/a/wAVB8FD

Jednak, patrząc na tabelkę, problem pojawia się wtedy, gdy należy dołączyć kolejny warunek (poszukiwana jest cyferka "2" z diagramu w załączniku). Dla przykładu, chciałbym wyznaczyć liczbę relacji zwrotnych, przechodnich i symetrycznych jednocześnie (czyli część wspólną Z, S, P, z dopełnieniem A'). Wówczas, można skorzystać ze wzoru na ilość zwrotnych i symetrycznych relacji: \(\displaystyle{ 2^{ \frac{n^2-n}{2} }=2}\). Jednak, jak wówczas wyznaczyć jednocześnie liczbę relacji przechodnich? Czy można posiłkować się faktem, że na podstawie bazy oeis zadanego ciągu A006905, dla n = 2, jest 13 wszystkich relacji przechodnich? Tak naprawdę, do obliczenia trzech dowolnych relacji z czterech, potrzebne jest dostawienie kolejnego warunku, zatem... w jaki sposób można zabrać się za ten problem? Być może jest to trywialne, aczkolwiek nigdy nie spotkałem się wcześniej z takim badaniem. :roll:
Jan Kraszewski
Administrator
Administrator
Posty: 34128
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

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

Post autor: Jan Kraszewski »

Gorgon24 pisze: 1 cze 2021, o 13:04Czy n = 0 można interpretować jako podzbiór zbioru pustego?
Dla \(\displaystyle{ n=0}\) masz relację na zbiorze zeroelementowym, czyli pustym.
Gorgon24 pisze: 1 cze 2021, o 13:04Jeśli chodzi o własności poszczególnych 16-stu podzbiorów, wykonałem taką tabelkę:

Kod: Zaznacz cały

https://imgur.com/a/wAVB8FD

Jednak, patrząc na tabelkę, problem pojawia się wtedy, gdy należy dołączyć kolejny warunek (poszukiwana jest cyferka "2" z diagramu w załączniku). Dla przykładu, chciałbym wyznaczyć liczbę relacji zwrotnych, przechodnich i symetrycznych jednocześnie (czyli część wspólną Z, S, P, z dopełnieniem A').
No akurat zwrotne, przechodnie i symetryczne jednocześnie to suma obszarów 1 i 2. Dlaczego chcesz wziąć "dopełnienie \(\displaystyle{ A'}\)"?
Gorgon24 pisze: 1 cze 2021, o 13:04Wówczas, można skorzystać ze wzoru na ilość zwrotnych i symetrycznych relacji: \(\displaystyle{ 2^{ \frac{n^2-n}{2} }=2}\). Jednak, jak wówczas wyznaczyć jednocześnie liczbę relacji przechodnich? Czy można posiłkować się faktem, że na podstawie bazy oeis zadanego ciągu A006905, dla n = 2, jest 13 wszystkich relacji przechodnich? Tak naprawdę, do obliczenia trzech dowolnych relacji z czterech, potrzebne jest dostawienie kolejnego warunku, zatem... w jaki sposób można zabrać się za ten problem? Być może jest to trywialne, aczkolwiek nigdy nie spotkałem się wcześniej z takim badaniem. :roll:
Dla \(\displaystyle{ n=2}\) to naprawdę nie ma co kombinować: wypisujesz wszystkie \(\displaystyle{ 16}\) relacji, dla każdej z nich sprawdzasz czy ma bądź nie ma każdą z tych czterech własności, co później przez proste zliczanie pozwoli Ci ustalić liczność każdego z tych \(\displaystyle{ 14}\) obszarów "atomowych" (z których potem możesz składać większe kawałki).

JK
Gorgon24
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 31 maja 2021, o 15:25
Płeć: Mężczyzna
wiek: 24

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

Post autor: Gorgon24 »

Dla \(\displaystyle{ n=2}\) można założyć, że ustawione są następujące pary:

1. \(\displaystyle{ \emptyset \rightarrow S, A, P}\)
2. \(\displaystyle{ \left\{ (0,0)\right\} \rightarrow Z, S, A, P}\)
3. \(\displaystyle{ \left\{ (0,1)\right\} \rightarrow A, P}\)
4. \(\displaystyle{ \left\{ (1,0)\right\} \rightarrow A, P}\)
5. \(\displaystyle{ \left\{ (1,1) \right\} \rightarrow Z, S, A, P}\)
6. \(\displaystyle{ \left\{ (0,0), (0,1) \right\} \rightarrow A, P}\)
7. \(\displaystyle{ \left\{ (0,0), (1,0) \right\} \rightarrow A, P}\)
8. \(\displaystyle{ \left\{ (0,0), (1,1)\right\} \rightarrow Z, S, A, P}\)
9. \(\displaystyle{ \left\{ (0,1), (1,0) \right\} \rightarrow S}\)
10. \(\displaystyle{ \left\{ (0,1), (1,1)\right\} \rightarrow A, P}\)
11. \(\displaystyle{ \left\{ (1,0), (1,1)\right\} \rightarrow A, P}\)
12. \(\displaystyle{ \left\{ (0,0), (0,1), (1,0) \right\} \rightarrow S}\)
13. \(\displaystyle{ \left\{ (0,0), (0,1), (1,1)\right\} \rightarrow Z, A, P}\)
14. \(\displaystyle{ \left\{ (0,0), (1,0), (1,1)\right\} \rightarrow Z, A, P}\)
15. \(\displaystyle{ \left\{ (0,1), (1,0), (1,1)\right\} \rightarrow S}\)
16. \(\displaystyle{ \left\{ (0,1), (1,0), (1,0), (1,1)\right\} \rightarrow S}\)

Byłbym zobowiązany za wszelką pomoc i dalsze wskazówki.
Ostatnio zmieniony 1 cze 2021, o 22:50 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Jan Kraszewski
Administrator
Administrator
Posty: 34128
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

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

Post autor: Jan Kraszewski »

2 i 5 źle, te relacje nie są zwrotne.
16 źle, ta relacja jest także zwrotna i przechodnia.

Poza tym dobrze.

JK
Gorgon24
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 31 maja 2021, o 15:25
Płeć: Mężczyzna
wiek: 24

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

Post autor: Gorgon24 »

Rozumiem, dziękuję za pomoc ;) Jeśli mogę spytać, czy dla \(\displaystyle{ n=3, n=4}\) (aby zaznaczyć ich liczebność na rysunku), czy można to w jakiś sposób na piechotę policzyć szybszym sposobem? Jak widać, te liczby rosną w wykładniczym tempie. Zatem, dla \(\displaystyle{ n=3}\) będzie \(\displaystyle{ 2 ^{3 ^{2} }=512}\) rozwiązań, zaś dla \(\displaystyle{ n=4}\) będzie \(\displaystyle{ 2 ^{4 ^{2} }=65536}\) rozwiązań.
Jan Kraszewski
Administrator
Administrator
Posty: 34128
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

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

Post autor: Jan Kraszewski »

Ale czym jest "to", które chcesz policzyć szybszym sposobem?

JK
Gorgon24
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 31 maja 2021, o 15:25
Płeć: Mężczyzna
wiek: 24

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

Post autor: Gorgon24 »

Mam na myśli oczywiście zbiór 3-elementowy i zbiór 4-elementowy. W celu wypisania wszystkich podzbiorów, należy wypisać uprzednio relacje binarne. A ponieważ będzie strasznie dużo podzbiorów dla większego zbioru elementowego, to czy istnieje szybszy sposób wypisania i sprawdzenia relacji tylu podzbiorów?

Dodano po 1 dniu 1 godzinie 9 minutach 14 sekundach:
Hmm... Chyba, że wystarczy wyliczyć samą ilość tych relacji dla wyższych n?? Jak sądzisz?
Jan Kraszewski
Administrator
Administrator
Posty: 34128
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

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

Post autor: Jan Kraszewski »

Tyle, że ja nadal nie wiem, co chcesz liczyć, bo wypowiadasz się dość nieprecyzyjnie. Co miałoby znaczyć

"W celu wypisania wszystkich podzbiorów, należy wypisać uprzednio relacje binarne."?

I dalej:

"A ponieważ będzie strasznie dużo podzbiorów dla większego zbioru elementowego, to czy istnieje szybszy sposób wypisania i sprawdzenia relacji tylu podzbiorów?"

Szybszy sposób wypisania czego?

To, ile jest wszystkich relacji na zbiorze \(\displaystyle{ n}\)-elementowym jest wiadome: \(\displaystyle{ 2^{n^2}}\).

JK
Gorgon24
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 31 maja 2021, o 15:25
Płeć: Mężczyzna
wiek: 24

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

Post autor: Gorgon24 »

Jan Kraszewski pisze: 3 cze 2021, o 11:53 Tyle, że ja nadal nie wiem, co chcesz liczyć, bo wypowiadasz się dość nieprecyzyjnie. Co miałoby znaczyć

"W celu wypisania wszystkich podzbiorów, należy wypisać uprzednio relacje binarne."?
Mam na myśli fakt, że przy badaniu "Ile jest relacji danego typu", np. dla \(\displaystyle{ n=2}\), 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)}\)

A następnie, wyznaczenie wszystkich możliwych relacji dla każdego z wypisanego podzbioru, czyli, np.:
1. \(\displaystyle{ \emptyset}\)\(\displaystyle{ \rightarrow Symetryczna, Antysymetryczna, Przechodnia}\)
...
16. \(\displaystyle{ (0,1), (1,0), (1,0), (1,1)}\)}\(\displaystyle{ \rightarrow Zwrotna, Symetryczna, Przechodnia}\)

Kolejnym krokiem jest naszkicowanie (na podstawie każdego z 16 wypisanych podzbiorów i opisanych dla nich relacji, dla \(\displaystyle{ n=2}\)) diagramu Venna i pokazanie każdej relacji na podstawie jej cząstkowych fragmentów (czyli tak, jak wspomniałeś - na 14 częściach "atomowych").

Jan Kraszewski pisze: 3 cze 2021, o 11:53 I dalej:

"A ponieważ będzie strasznie dużo podzbiorów dla większego zbioru elementowego, to czy istnieje szybszy sposób wypisania i sprawdzenia relacji tylu podzbiorów?"

Szybszy sposób wypisania czego?

To, ile jest wszystkich relacji na zbiorze \(\displaystyle{ n}\)-elementowym jest wiadome: \(\displaystyle{ 2^{n^2}}\).

JK
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, 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.
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?

Mam nadzieję, że odrobinę lepiej wytłumaczyłem ideę problemu.

Byłbym zobowiązany za samą podpowiedź, jak zabrać się za ten sam problem przy \(\displaystyle{ n=3}\) oraz \(\displaystyle{ n=4}\).

Pozdrawiam serdecznie.
Ostatnio zmieniony 3 cze 2021, o 13:51 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
ODPOWIEDZ