Diagramy Venna
W tym artykule zajmiemy się nieco dokładniej diagramami Venna.
Diagramy Venna były tematem znakomitego artykułu „Pizza Venna” w
Delcie 03/2004.
Najpierw powiemy, co to jest niezależna rodzina zbiorów.
Przypuśćmy, że mamy daną rodzinę
podzbiorów
pewnego ustalonego zbioru
Od tej pory wszystkie rozpatrywane
zbiory będą podzbiorami tego zbioru
(będziemy go nazywać
przestrzenią
). Niech
oznacza dopełnienie zbioru
do przestrzeni
tzn.
Oznaczmy następnie
oraz
dla
Każdy zbiór postaci
gdzie
nazywamy składową
rodziny
Oczywiście każda
-elementowa
rodzina zbiorów ma
składowych. Składowymi rodziny zbiorów
będą zbiory:
Gdy wszystkie składowe rodziny są różne i niepuste, rodzinę nazwiemy niezależną.
A oto przykład rodziny niezależnej podzbiorów przestrzeni :
Rodziny niezależne są wykorzystywane w dowodach tożsamości z rachunku zbiorów. Prawdziwe jest bowiem następujące twierdzenie.
Twierdzenie. Niech i będą wyrażeniami rachunku zbiorów tzn. występują w nich tylko zbiory i oraz symbole działań na zbiorach: . Jeśli dla pewnej niezależnej rodziny podzbiorów pewnej przestrzeni zachodzi równość to ta równość zachodzi także dla dowolnych zbiorów i
Twierdzenia tego nie będziemy dowodzić, popatrzymy natomiast na przykład jego zastosowania. Udowodnimy równość Dla naszej rodziny niezależnej mamy:
Okazało się, że dla tej rodziny niezależnej zachodzi dowodzona równość. Zatem ta równość jest prawdziwa dla dowolnych zbiorów i Podobne twierdzenie jest prawdziwe dla wyrażeń zawierających więcej zbiorów. Dowód znajduje się np. w książce.
Dowody takie jak powyższy szczególnie łatwo przeprowadzić na rysunku. Rysujemy niezależną rodzinę podzbiorów pewnej przestrzeni i zaznaczamy na tym rysunku zbiory występujące po obu stronach równości. Jeśli oba zaznaczone zbiory są identyczne, to równość zachodzi dla dowolnych zbiorów. Niezależną rodzinę zbiorów najprościej narysować w następujący sposób.
Taki rysunek nazywamy diagramem Venna. Każdy z zbiorów naszej rodziny niezależnej jest narysowany w postaci pewnego podzbioru płaszczyzny (w naszym przypadku są to trzy koła), przy czym rozważana przestrzeń (u nas płaszczyzna) jest podzielona krzywymi ograniczającymi zbiory na (u nas ) części. Każda z tych części odpowiada jednej składowej (zakładamy, że części te są spójne, czyli w jednym kawałku).
W dalszym ciągu ustalimy jednolity sposób numerowania składowych. Numerem składowej
jest liczba, której kolejnymi cyframi w zapisie w systemie dwójkowym są: Na przykład, jeśli naszą rodziną niezależną jest (tzn. oraz ), to składowa
ma numer 6, gdyż liczba 6 ma zapis dwójkowy 110. Podobnie składowa
ma numer 3, gdyż liczba 3 ma zapis dwójkowy 11, czyli inaczej 011. W przypadku, gdy rodzina niezależna składa się z czterech zbiorów to składowa
ma numer 10, gdyż liczba 10 ma zapis dwójkowy 1010.
Na rysunku obok pokazany jest nasz diagram Venna dla trzech zbiorów i ze składowymi ponumerowanymi w ten sposób.
Czytelnik zechce sam sprawdzić, że zbiory po obu stronach równości
wyglądają tak, jak na Rys. 4.
Z powyższych rozważań widać, że umiejętność rysowania niezależnych rodzin zbiorów (czyli diagramów Venna) może się przydać w praktyce do dowodzenia równości w rachunku zbiorów. We wspomnianym artykule została pokazana jedna metoda rysowania diagramów Venna. Jednak diagramy dla dużych liczb były bardzo skomplikowane i mało czytelne. Powstaje naturalne pytanie, czy można narysować diagram Venna, w którym wszystkie zbiory mają stosunkowo prostą postać. Diagram Venna dla trzech zbiorów można było narysować za pomocą trzech okręgów. A czy można tak narysować cztery okręgi, by tworzyły diagram Venna dla czterech zbiorów?
Okazuje się, że jest to niemożliwe. Mianowicie za pomocą trzech okręgów można podzielić płaszczyznę na co najwyżej 8 części. Czwarty okrąg przetnie każdy z dotychczasowych okręgów w co najwyżej dwóch punktach; te punkty podzielą go zatem na co najwyżej 6 łuków. Każdy łuk dzieli jeden obszar na dwie części. Zatem cztery okręgi dzielą płaszczyznę na co najwyżej części. Nie otrzymamy zatem diagramu Venna, gdyż taki diagram dla czterech zbiorów ma mieć 16 składowych. Rozumując w podobny sposób, można pokazać, że jeśli oznacza maksymalną liczbę części, na jakie okręgów może podzielić płaszczyznę, to ciąg spełnia następujące równania rekurencyjne:
Nietrudno teraz dowieść przez indukcję, że ; dla otrzymamy Zatem żadna konfiguracja czterech okręgów na płaszczyźnie nie tworzy diagramu Venna. Oczywiście, czwarty zbiór możemy dorysować do trzech okręgów inaczej
Na rysunku 5. mamy przykład takich czterech zbiorów.
Składowe na tym diagramie Venna zostały ponumerowane zgodnie z przyjętą wyżej zasadą. Powstaje oczywiście pytanie, czy można dorysować czwarty zbiór tak, by był on zbiorem wypukłym. Gdy byłem jeszcze studentem, wydawało mi się to oczywiście niemożliwe; zresztą tak uważało wielu moich kolegów. Rysunek 6, który mimo wszystko kiedyś udało mi się narysować, wprawił mnie w zrozumiałe zdumienie.
Inny diagram Venna otrzymamy, rysując cztery elipsy.
Jeszcze inny, składający się z czterech prostokątów, można łatwo narysować samemu. Prostokąty te mają wierzchołki w punktach o następujących współrzędnych:
Gdy udało się narysować diagram Venna, w którym wszystkie cztery zbiory były wypukłe, należało spróbować zrobić to samo dla pięciu zbiorów. Do trzech kół i prostokąta udało mi się dorysować jeszcze trójkąt.
Wierzchołki trójkątów z rysunku 11 mają następujące współrzędne
Okazuje się jednak, że nie można narysować diagramu Venna złożonego z więcej niż sześciu trójkątów. Aby tego dowieść, pokażemy najpierw, że jeśli jest największą liczbą obszarów, na jakie trójkątów może podzielić płaszczyznę, to ciąg spełnia następujące równania rekurencyjne: Jeden trójkąt oczywiście dzieli płaszczyznę na dwa obszary. Przypuśćmy teraz, że mamy już trójkątów na płaszczyźnie. Następny trójkąt przecina każdy z tych trójkątów w co najwyżej 6 punktach. Te punkty przecięcia dzielą obwód tego ostatniego trójkąta na co najwyżej części; każda z tych części dzieli jeden obszar na dwie części. Zatem maksymalna liczba części, na jakie możemy podzielić płaszczyznę za pomocą trójkątów, wynosi co najwyżej (pozostawimy jako ćwiczenie przekonanie się, że można tak umieścić trójkątów na płaszczyźnie, by każde dwa przecinały się w dokładnie 6 punktach; taka konfiguracja da właśnie części). Teraz można łatwo udowodnić przez indukcję, że Można również łatwo udowodnić, że jeśli to To pokazuje, że jeśli to żadna konfiguracja trójkątów na płaszczyźnie nie tworzy diagramu Venna. Jeśli zaś to Zatem można tak umieścić 7 trójkątów na płaszczyźnie, by podzieliły one płaszczyznę na obszarów. Jednak taka konfiguracja nie będzie diagramem Venna. Mianowicie każde dwa trójkąty muszą przecinać się w sześciu punktach, a więc wierzchołki każdego trójkąta leżą na zewnątrz każdego innego. Stąd wynika, że w każdym trójkącie trzy obszary wewnętrzne, na których brzegu leżą wierzchołki, zawarte są tylko w tym jednym trójkącie, a więc stanowią części tej samej składowej. A to znaczy, że ta konfiguracja nie jest diagramem Venna.
Widzimy więc, że istnieje diagram Venna złożony z sześciu trójkątów i nie istnieją diagramy Venna złożone z trójkątów dla A jak jest z czworokątami wypukłymi? Albo z pięciokątami wypukłymi? A czy dla każdego istnieje diagram Venna złożony z wielokątów wypukłych? Odpowiedzi na niektóre tak postawione pytania są znane. Myślę jednak, że można spróbować na podobne pytania odpowiedzieć samemu. W książce znajduje się obszerny przegląd wiadomości na temat diagramów Venna. Są tam też odnośniki do wielu innych interesujących źródeł.