Algebra zbiorów
Wstęp 2
1. Algebra zbiorów 3
1.1. Działania algebry zbiorów 3
1.2. Inkluzja (zawieranie) i równość zbiorów 4
1.3. Metody dowodzenia własności zbiorów 5
1.4. Uniwersum i zbiór pusty 6
2. Zbiór potęgowy i inne rodziny zbiorów 11
Bibliografia 15
Wstęp
Zbiory i działania na zbiorach pełnią istotną rolę w informatyce. Przykładem zbioru
informacji gromadzonej w systemie informatycznym jest baza danych. Również
w programistyce spotykamy się ze zbiorem jako jednym z podstawowych typów
danych. Dobry programista musi umiejętnie korzystać ze struktur mających charakter
zbioru, a dobry bazodanowiec musi znać podstawowe własności działań na zbiorach,
aby umieć odpowiednio ekstrahować informacje ze swojej bazy.
Moduł trzeci przedstawia podstawowe pojęcia algebry zbiorów i ich użyteczne
również z punktu widzenia informatyki własności.
Omówimy pojęcia pierwotne teorii mnogości: zbiór i relację przynależności. Zostaną
zdefiniowanerelacjerówności i inkluzji zbiorów, a także działania teoriomnogościowe.
Przedstawione zostaną również (w większości wraz z dowodami) własności tych
działań oraz zależności między tymi własnościami.
Zdefiniujemy też pojęcie zbioru potęgowego oraz ciała zbiorów i omówimy ich
własności.
2
1. Algebra zbiorów
Pojęcia zbioru i relacji należenia są w matematyce traktowane jako pojęcia pierwotne,
czyli pozostawiane bez definicji. Gdyby przyjrzeć się bliżej problemowi definicji
zbioru, można zauważyć, że gdyby nawet udało się zdefiniować zbiór jako na przykład
grupę pewnych elementów , zrodzi się wtedy automatycznie pytanie o definicję
takiej grupy . Gdyby i to zdefiniować, trzeba byłoby użyć jakichś innych pojęć,
o definicję których znowu trzeba byłoby zadbać itp. Problem ten wiódłby oczywiście
do podobnych rozważań i sporów o definiowanie w nieskończoność. Ustalono
zatem, że dwa wyżej wspomniane pojęcia przyjmuje się za pierwotne. Pojęcia te są
odpowiednio charakteryzowane przez aksjomaty tzw. teorii mnogości (np. Zermelo-
Fraenkla).
W dalszych rozważaniach dużymi literami A, B oznaczać będziemy zbiory, małymi
zaś x, y elementy zbiorów. Przez zapis x " A rozumiemy zwyczajowo intuicję:
element x należy do zbioru A.
Przykład 1
Rozważmy następujące przykłady zbiorów:
çÅ‚ A = {a, b, 1, 0} jak można Å‚atwo zauważyć, zbiór ten ma cztery elementy. SÄ…
to: a, b, 1, 0. Możemy zatem zapisać: a " A, b " A, 1 " A, 0 " A;
çÅ‚ B = {{a}, b, {1, 0}} zbiór ten ma trzy elementy. SÄ… to: {a}, b, {1, 0}. Mimo
że {a} sam w sobie jest zbiorem (jednoelementowym), to jest on elementem
rozważanego zbioru B. Podobnie {1, 0} jest zbiorem dwuelementowym, ale
jako całość jest elementem zbioru B. Prawdą jest zatem, że {a} " B, b " B oraz
{1, 0} " B. Ale nie jest prawdą, że a " B (choć oczywiście a " {a}). Mamy też
0 " B (choć 0 " {1, 0});
çÅ‚ C = {{a, {b}}} zbiór C ma tylko jeden element. Jest nim (dwuelementowy)
zbiór {a, {b}}. Mamy zatem {a, {b}} " C. Ale nie jest prawdą, że a " C czy też
nie jest prawdą, że b " C;
çÅ‚ D = {a, {a, {b}}} zbiór D ma dwa elementy. SÄ… to: a oraz zbiór {a, {b}}.
Mamy oczywiście a " D, ale też b " D;
çÅ‚ N = {0, 1, 2, 3, 4, ...} zbiór liczb naturalnych jest zbiorem nieskoÅ„czonym;
çÅ‚ Z = {... , 4, 3, 2, 1, 0, 1, 2, 3, 4, ...} zbiór liczb caÅ‚kowitych (zbiór
nieskończony).
1.1. Działania algebry zbiorów
A B
Jeżeli A oraz B są zbiorami, to:
çÅ‚ przez zapis A *" B rozumieć bÄ™dziemy zbiór speÅ‚niajÄ…cy warunek
x " A *" B Ô! (x " A (" x " B) (element należy do zbioru A *" B wtedy
i tylko wtedy, gdy należy do jednego z nich lub do drugiego). Zbiór A *" B
nazywamy sumą zbiorów A oraz B. Interpretacja graficzna sumy zbiorów
A B
przedstawiona jest na rysunku 1;
Rysunek 1
3
çÅ‚ przez zapis A )" B rozumiemy zbiór speÅ‚niajÄ…cy warunek
A B
x " A )" B Ô! (x " A '" x " B) (element należy do zbioru
A )" B wtedy i tylko wtedy, gdy należy do jednego z nich
i jednocześnie do drugiego). Zbiór A )" B nazywamy iloczynem
lub częścią wspólną zbiorów A oraz B. Interpretacja graficzna
iloczynu zbiorów przedstawiona jest na rysunku 2;
çÅ‚ przez zapis A B rozumiemy zbiór speÅ‚niajÄ…cy warunek
A B
x " A B Ô! (x " A '" x " B) (element należy do zbioru A
Rysunek 2
B wtedy i tylko wtedy, gdy należy do pierwszego z nich i nie należy do
drugiego). Zbiór A B nazywamy różnicą zbiorów A oraz B. Interpretacja
graficzna różnicy zbiorów przedstawiona jest na rysunku 3;
A B
çÅ‚ przez zapis A ÷ B rozumiemy zbiór speÅ‚niajÄ…cy warunek
x " A ÷ B Ô! [(x " A '" x " B) (" (x " B '" x " A)]. Zbiór A ÷ B
nazywamy różnicą symetryczną zbiorów A oraz B. Interpretacja graficzna
różnicy symetrycznej zbiorów przedstawiona jest na rysunku 4;
A B
çÅ‚ przez zapis A rozumiemy zbiór speÅ‚niajÄ…cy warunek
x " A Ô! x " A Ô! Źx " A (element należy do zbioru A
A B
wtedy i tylko wtedy, gdy nie należy do zbioru A). Zbiór
Rysunek 3
A nazywamy dopełnieniem zbioru A. Interpretacja graficzna
dopełnienia zbioru przedstawiona jest na rysunku 5.
A B
A B
1.2. Inkluzja (zawieranie) i równość zbiorów
Między zbiorami rozważa się dwie podstawowe zależności: zawierania
A-B
i równości zbiorów. Powiemy, że zbiór A zawiera się w zbiorze B, co
Rysunek 4
zapisujemy A ą" B (rysunek 6), jeżeli każdy element zbioru A należy również
do zbioru B.
Formalnie możemy ten fakt zapisać następująco:
A Ä…" B Ô! " (x " A Ò! x " B).
x
Powiemy, że zbiór A jest równy zbiorowi B wtedy i tylko wtedy, gdy zbiór
A
A zawiera się w zbiorze B oraz zbiór B zawiera się w zbiorze A (każdy element
zbioru A należy do zbioru B oraz każdy element zbioru B należy do zbioru A).
Formalnie:
A = B Ô! [(A Ä…" B) '" (B Ä…" A)].
,
A
Po odpowiednich przekształceniach możemy otrzymać:
Rysunek 5
A = B Ô! [(A Ä…" B) '" (B Ä…" A)] Ô! [" (x " A Ò! x " B) '" " (x " B Ò! x " A)] Ô!1
x x
Ô! " [(x " A Ò! x " B) '" (x " B Ò! x " A)] Ô!2 " (x " A Ô! x " B).
x x
Finalnie mamy:
A = B Ô! " (x " A Ô! x " B).
x
Dla zdefiniowanych wyżej działań i zależności między zbiorami możemy
udowodnić wiele własności zbiorów i działań na zbiorach.
1
Zgodnie z prawem rachunku kwantyfikatorów ["A(x )'" "B(x)] Ô! "[A(x)'" B(x)].
x x x
Rysunek 6
2
Z prawa rachunku zdaÅ„ [(Ä… Ò! ²) '" (² Ò! Ä…)] Ô! (Ä… Ô! ²).
4
Twierdzenie 1
Dla dowolnych zbiorów A, B, C zachodzą następujące własności:
(a) A )" A = A i d e m p o t e n t n o ś ć iloczynu,
(b) A *" A = A i d e m p o t e n t n o ś ć sumy,
(c) A )" B = B )" A p r z e m i e n n o ś ć iloczynu,
(d) A *" B = B *" A p r z e m i e n n o ś ć sumy,
(e) A )" (B *" C) = (A )" B) *" (A )" C) r o z d z i e l n o ś ć i l o c z y n u w z g l ę d e m
s u m y,
(f) A *" (B )" C) = (A *" B) )" (A *" C) r o z d z i e l n o ś ć s u m y w z g l ę d e m
i l o c z y n u ,
(g) A )" (A *" B) = A p o c h Å‚ a n i a n i e ,
(h) A *" (A )" B) = A p o c h Å‚ a n i a n i e ,
(i) (A *" B) = A )" B p r a w o d e M o r g a n a algebry zbiorów,
(j) (A )" B) = A *" B p r a w o d e M o r g a n a algebry zbiorów,
(k) A )" B Ä…" A,
(l) A Ä…" A *" B.
1.3. Metody dowodzenia własności zbiorów
Udowodnimy dla przykładu własność (a) z twierdzenia 1 (idempotentności iloczynu
zbiorów):
A )" A = A.
Aby udowodnić tę własność, zgodnie z definicją równości zbiorów, należy pokazać, że:
" (x " A )" A Ô! x " A),
x
czyli dla dowolnego elementu x należy wykazać prawdziwość równoważności
x " A )" A Ô! x " A.
Wezmy zatem dowolny element x.
Rozpisując lewą stronę równoważności, otrzymujemy:
L : x " A )" A Ô! x " A '" x " A Ô!3 x " A : P
Następnie wykorzystując prawo przechodniości równoważności
[(Ä… Ô! ²) '" (² Ô! Å‚)] Ò! (Ä… Ô! Å‚) otrzymujemy finalnie:
x " A )" A Ô! x " A.
Dowód (e)
Należy pokazać, że " [x " A )" (B *" C) Ô! x " (A )" B) *" (A )" C)].
x
Wezmy dowolny element x. Mamy:
L : x " A )" (B *" C) Ô!4 x " A '" x " (B *" C) Ô!5 x " A '" (x " B (" x " C) Ô!6
Ô! (x " A '" x " B) (" (x " A '" x " C) Ô! (x " (A )" B)) ("
(x " (A )" C)) Ô! x " (A )" B) *" (A )" C) : P
3
Wykorzystujemy tu prawo idempotentnoÅ›ci koniunkcji: Ä… '" Ä… Ô! Ä….
4
Korzystamy z definicji iloczynu zbiorów: x " A )" B Ô! (x " A '" x " B).
5
Definicja sumy x " A *" B Ô! (x " A (" x " B).
6
Prawo rozdzielnoÅ›ci koniunkcji wzglÄ™dem alternatywy Ä… '" (² (" Å‚) Ô! (Ä… '" ²) (" (Ä… '" Å‚).
5
I ponownie wykorzystując przechodniość równoważności, otrzymujemy:
x " A )" (B *" C) Ô! x " (A )" B) *" (A )" C).
Dowód (g)
Należy pokazać, że " [x " A )" (A *" B) Ô! x " A].
x
Wezmy dowolny element x. Mamy:
L : x " A )" (A *" B) Ô! x " A '" x " (A *" B) Ô! x " A '" (x " A (" x " B) Ô!7 x " A : P
Korzystając z przechodniości równoważności, mamy:
x " A )" (A *" B) Ô! x " A.
Dowód (i)
Należy pokazać, że " [x " (A *" B) Ô! x " A )" B ].
x
Wezmy dowolny element x. Mamy:
L : x " (A *" B) Ô!8 Źx " (A *" B) Ô! Ź(x " A (" x " B) Ô!9 (Źx " A '" Źx " B) Ô!
Ô! x " A '" x " B Ô! x " A )" B : P
I wreszcie:
x " (A *" B) Ô! x " A )" B .
1.4. Uniwersum i zbiór pusty
Aatwo dowodzi się faktu, że nie ma (uniwersalnego) zbioru wszystkich elementów.
Założenie takie dałoby natychmiastową sprzeczność, zakłada się bowiem, że żaden
zbiór nie może należeć do siebie samego. Dlatego jeżeli rozważamy jakieś zbiory,
bardzo często przydaje się pojęcie uniwersum przestrzeni. Przestrzeń to, mówiąc
krótko, świat rzeczywistość, którą w danym momencie się rozważa (czyli tak
naprawdę jakaś część całego świata pełnej rzeczywistości). Jeżeli zastanawiamy
się nad własnościami przedziałów na osi rzeczywistej, jako uniwersum możemy
przyjąć zbiór wszystkich liczb rzeczywistych. Jeżeli mówimy o własnościach zbiorów
punktów na płaszczyznie (w układzie współrzędnych), to jako uniwersum można
przyjąć zbiór wszystkich punktów płaszczyzny. Uniwersum będzie tutaj oznaczane
jako X. Jeżeli rozważamy pewne zbiory nad pewnym uniwersum, możemy ograniczyć
pojęcie dopełnienia zbioru do dopełnienia względem uniwersum, tzn. przez zapis A
rozumieć będziemy różnicę X A. W dowodach własności związanych z uniwersum
X będziemy przyjmować, że wyrażenie x " X jest prawdziwe.
Istotną rolę w teorii mnogości spełnia także zbiór pusty. Jest to zbiór, o którym
zakłada się, że nie ma żadnych elementów. Zakładamy również, że zbiór pusty jest
tylko jeden. Zbiór pusty oznaczamy zwyczajowo jako ".
7
Prawo pochÅ‚aniania Ä… '" (² (" Ä…) Ô! Ä….
8
Definicja dopełnienia zbioru.
9
Prawo de Morgana rachunku zdaÅ„ Ź(Ä… (" ²) Ô! (Źą '" Ź²).
6
Twierdzenie 2
Rozważmy jako uniwersum zbiór X. Dla dowolnego zbioru A zawartego w zbiorze X
zachodzą następujące własności:
(a) A )" X = A,
(b) A *" X = X,
(c) A *" A = X.
Dowód (a)
Należy pokazać, że " [x " A )" X Ô! x " A].
x
Wezmy dowolny element x. Mamy:
L : x " A )" X Ô! x " A '" x " X.
Zauważmy, że prawy czynnik powyższej koniunkcji jest prawdziwy. Przypomn3my
także, że jeżeli jeden z czynników koniunkcji jest prawdziwy, to cała koniunkcja
zależy tylko od drugiego z czynników i jest jemu równoważna. Uzasadniona jest
zatem następująca równoważność:
x " A '" x " X Ô! x " A : P,
I finalnie:
x " A )" X Ô! x " A.
Dowód (c)
Należy pokazać, że " [x " A *" A Ô! x " X].
x
Wezmy dowolny element x. Mamy:
L : x " A *" A Ô! x " A (" x " A Ô! x " A (" Źx " A.
Zauważmy, że powyższa alternatywa jest prawdziwa10. Zatem uzasadniona jest
następująca równoważność:
x " A (" Źx " A Ô! x " X : P.
I finalnie:
x " A *" A Ô! x " X.
Twierdzenie 3
Dla dowolnego zbioru A zachodzą następujące własności:
(a) " Ä…" A,
(b) A )" " = ",
(c) A *" " = A,
(d) A )" A = ".
Dowód (a)
Zgodnie z definicją inkluzji (zawierania) zbiorów należy pokazać, że
" [x " " Ò! x " A].
x
10
Jest to pewne podstawienie tautologii ą (" Źą.
7
Wezmy zatem dowolny element x. Jeżeli rozważymy poprzednik powyższej
implikacji, łatwo można zauważyć, że wyrażenie x " " jest fałszywe (do zbioru
pustego nie należy żaden element). Przypomn3my z rachunku zdań, że implikacja
o fałszywym poprzedniku jest prawdziwa niezależnie od następnika. Prawdziwe jest
zatem wyrażenie: x " " Ò! x " A, co koÅ„czy dowód11.
Dowód (b)
Należy pokazać, że " [x " A )" " Ô! x " "].
x
Wezmy dowolny element x. Mamy:
L : x " A )" " Ô! x " A '" x " ".
Zauważmy, że prawy czynnik powyższej koniunkcji jest fałszywy. Przypomn3my także,
że jeżeli jeden z czynników koniunkcji jest fałszywy, to cała koniunkcja jest fałszywa.
Oczywiście, dwa dowolne fałszywe wyrażenia są sobie logicznie równoważne, zatem
uzasadniona jest następująca równoważność:
x " A '" x " " Ô! x " " : P,
I finalnie:
x " A )" " Ô! x " ".
Dowód (d)
Należy pokazać, że " [x " A )" A Ô! x " "].
x
Wezmy dowolny element x. Mamy:
L : x " A )" A Ô! x " A '" x " A Ô! x " A '" Źx " A.
Zauważmy, że powyższa koniunkcja jest fałszywa12. Zatem uzasadniona jest
następująca równoważność:
x " A '" Źx " A Ô! x " " : P.
I finalnie:
x " A )" A Ô! x " ".
Opisywane wyżej własności dotyczą przede wszystkim działań na zbiorach. Poniżej
przedstawionych jest kilka własności zależności między zbiorami.
Twierdzenie 4
Dla dowolnych zbiorów A, B, C, D zachodzą następujące własności:
(a) A Ä…" B '" B Ä…" C Ò! A Ä…" C,
(b) A Ä…" B '" C Ä…" B Ò! A *" C Ä…" B,
(c) A Ä…" B '" C Ä…" D Ò! A D Ä…" B C,
(d) A Ä…" B Ô! A *" B = B,
(e) A Ä…" B Ô! A )" B = A,
(f) A Ä…" B Ô! A B = ",
(g) A Ä…" B Ò! B Ä…" A ,
11
Zauważmy, że z tej własności wynika na mocy dowolności zbioru A własność " ą" ".
12
Jest to pewne podstawienie kontrtautologii ą '" Źą.
8
(h) C Ä…" D Ò! A D Ä…" A C,
(i) A Ä…" B Ò! A *" (B A) = B.
Dowód (a)
Załóżmy, że A ą" B oraz B ą" C. Z obu założeń otrzymujemy zgodnie z definicją
inkluzji zbiorów " [x " A Ò! x " B] oraz " [x " B Ò! x " C]. Aby udowodnić tezÄ™
x x
A Ä…" C, należy pokazać, że " [x " A Ò! x " C].
x
Wezmy więc dowolny element x i załóżmy, że x " A. Na mocy założeń mamy kolejno
x " B oraz x " C, co kończy dowód.
Dowód (b)
Załóżmy, że A Ä…" B oraz C Ä…" B. Otrzymujemy " [x " A Ò! x " B] oraz
x
" [x " C Ò! x " B]. Aby udowodnić tezÄ™ A *" C Ä…" B, należy pokazać, że
x
" [x " A *" C Ò! x " B].
x
Wezmy więc dowolny element x i załóżmy, że x " A *" C. Mamy:
x " A (" x " C.
Stosując kolejno oba założenia, otrzymujemy:
x " B (" x " B,
czyli:
x " B,
co kończy dowód.
Dowód (d)
Aby pokazać, że A Ä…" B Ô! A *" B = B, musimy udowodnić dwie implikacje:
(*) A Ä…" B Ò! A *" B = B oraz (**) A *" B = B Ò! A Ä…" B.
(*) Załóżmy, że A Ä…" B, czyli " [x " A Ò! x " B]. Aby udowodnić równość zbiorów
x
A *" B = B, wykażemy dwie inkluzje: A *" B ą" B oraz B ą" A *" B. Druga z nich jest
oczywista na podstawie jednej z własności z twierdzenia 113.
Aby udowodnić pierwszą inkluzję, załóżmy, że x " A *" B.
Mamy:
x " A (" x " B.
Teraz, korzystając z założenia dowodu (*), mamy:
x " B (" x " B
i oczywiście x " B, co kończy dowód pierwszej z inkluzji potrzebnych do
udowodnienia implikacji (*).
(**) Załóżmy, że A *" B = B, czyli " [x " A *" B Ô! x " B]. Aby udowodnić inkluzjÄ™
x
A ą" B, załóżmy, że x " A.
13
Cytowana własność jest postaci A ą" A *" B, ale oczywiście zważywszy na przemienność
sumy zbiorów oznacza to samo.
9
Wiemy, że w ogólnym przypadku A Ä…" A *" B, czyli " [x " A Ò! x " A *" B].
x
Otrzymujemy zatem:
x " A (" x " B.
Teraz, korzystając z założenia dowodu (**), mamy:
x " B,
co kończy dowód implikacji (**).
Oczywiście zważywszy na odpowiednie prawo rachunku zdań14, równoważność
A Ä…" B Ô! A *" B = B zostaÅ‚a udowodniona.
Dowód (h)
Załóżmy, że A Ä…" B, czyli " [x " A Ò! x " B]. Rozważmy dowolny element x.
x
Przypomn3my, że zgodnie z odpowiednim prawem rachunku zdań implikacja
x " A Ò! x " B jest równoważna implikacji Źx " B Ò! Źx " A, która inaczej zapisana
przybiera postać: x " B Ò! x " A . Mamy zatem:
" [x " B Ò! x " A ],
x
czyli:
B Ä…" A .
14
Prawo [(Ä… Ò! ²) '" (² Ò! Ä…)] Ô! (Ä… Ô! ²).
10
2. Zbiór potęgowy
i inne rodziny zbiorów
Czasem z pewnych powodów istnieje potrzeba rozpatrywania zbiorów, których
elementami są również zbiory. Zbiory zbiorów nazywamy rodzinami. Typowym
przykładem rodziny zbiorów jest zbiór potęgowy danego zbioru.
Zbiorem potęgowym zbioru X nazywamy zbiór P(X) wszystkich podzbiorów tego
zbioru, symbolicznie:
P(X) = {A: A Ä…" X}.
Możemy też zapisać:
A " P(X) Ô! A Ä…" X.
Dla dowolnego zbioru X jego zbiór potęgowy P(X) nie jest zbiorem pustym, bo
" " P(X) oraz X " P(X).
Przykład 1
Jeśli X1 = ", to P(X1) = {"}. Nie ma bowiem innego podzbioru zbioru pustego poza
nim samym.
Przykład 2
Niech X2 = {a, b, c}, wtedy P(X2)={", {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.
Przykład 3
Niech X3 = {{a}, {{b}, c}}. Zauważmy, że zbiór ma tylko dwa elementy.
Są to {a} oraz {{b}, c}. Zbiór potęgowy wygląda zatem następująco:
P(X3) = {", {{a}}, {{{b}, c}}, {{a}, {{b}, c}}}.
Twierdzenie 5
Dla dowolnych zbiorów A i B zachodzą poniższe własności:
(a) A, B " P(X) Ò! A )" B, A *" B, A B " P(X),
(b) X Ä…" Y Ò! P(X) Ä…" P(Y).
Dowód (a)
Niech A, B " P(X), wtedy A ą" X oraz B ą" X, ale oczywiście również zbiory A )" B,
A *" B, A B są podzbiorami zbioru X, więc A )" B, A *" B, A B " P(X).
11
Dowód (b)
Załóżmy, że X ą" Y. Mamy pokazać, iż P(X) ą" P(Y).
Wezmy zatem dowolny element A zbioru potęgowego P(X). Mamy:
A " P(X) Ô!15 A Ä…" X Ò!16 A Ä…" Y Ô!17 A " P(Y).
Ostatecznie, korzystając z praw przechodniości równoważności i implikacji, mamy:
A " P(X) Ò! A " P(Y).
Przykład 4
Rozważmy zbiór X4 = {a, b, c, d}. Zauważmy, że mamy wtedy X4 = X2 *" {d}.
Można zauważyć, że elementami zbioru potęgowego P(X4) będą wszystkie elementy
zbioru potęgowego P(X2) oraz wszystkie sumy elementów zbioru P(X2) ze zbiorem
jednoelementowym {d}. Symbolicznie mamy w naszym przypadku:
P(X4) = P(X2) *" {A *" {d} : A " P(X2)}.
W rozważanym przypadku mamy:
P(X4) = P(X2) *" {A *" {d} : A " P(X2)} =
= {", {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} *"
*" {" *" {d}, {a} *" {d}, {b} *" {d}, {c} *" {d}, {a, b} *"
{d}, {a, c} *" {d}, {b, c} *" {d}, {a, b, c} *" {d}} =
= {", {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} *"
*" {{d}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}} =
= {", {a}, {b}, {c}, {d}, {a, b}, {a, c}, {b, c}, {a, d}, {b, d},
{c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}}.
Twierdzenie 6
Jeżeli zbiór A ma n elementów, to jego zbiór potęgowy P(A) ma 2n elementów.
Dowód
Dowód przeprowadzony zostanie przez indukcję ze względu na ilość elementów
zbioru A.
B a z a i n d u k c j i rozważmy zbiór niemający elementów (n = 0). Jedynym takim
zbiorem jest oczywiście zbiór pusty ". Zauważmy również, że P(") = {"}. Zatem
w tym przypadku zbiór potęgowy faktycznie ma 20 = 1 elementów.
Z a ł o ż e n i e k r o k u i n d u k c y j n e g o załóżmy, że zbiór potęgowy zbioru
mającego k elementów ma 2k elementów.
K r o k i n d u k c y j n y rozważmy zbiór k + 1-elementowy. Możemy zapisać ten
zbiór następująco:
{a1, a2, a3, ..., ak, ak+1} (zbiór ten oznaczamy dalej jako Ak+1).
15
Z definicji zbioru potęgowego.
16
Z założenia, że X ą" Y.
17
Z definicji zbioru potęgowego.
12
Zauważmy, że zbiór ten można potraktować również jako poniższą sumę:
{a1, a2, a3, ..., ak} *" {ak+1} (inaczej możemy zapisać Ak *" {ak+1}).
Oczywiście, zbiór Ak = {a1, a2, a3, ..., ak} jest zbiorem k-elementowym, a zatem jego
zbiór potęgowy P(Ak) ma zgodnie z założeniem indukcyjnym 2k elementów. Aatwo
można zauważyć (patrz przykład 5), że zbiór potęgowy P(Ak+1) można przedstawić
następująco: P(Ak+1) = P(Ak) *" {X *" {ak+1} : X " P(Ak)}. Zbiory P(Ak) oraz {X *"
{ak+1} : X " P(Ak)} są rozłączne oraz każdy z nich ma 2k elementów. Zatem zbiór
P(Ak+1) ma 2k + 2k = 2 Å" 2k = 2k+1 elementów, co koÅ„czy dowód.
Innym dobrym przykładem rodziny zbiorów jest ciało zbiorów. Rozważmy zbiór X
oraz jego zbiór potęgowy P(X).
Rodzinę ! podzbiorów zbioru X nazwiemy ciałem zbiorów, jeżeli spełnione są
następujące warunki:
1. ! `" ".
2. Jeżeli A " !, to X A " ! (dopełnienia zbiorów należących do ! należą również
do !).
3. Jeżeli A " ! oraz B " !, to A *" B " ! (sumy zbiorów należących do ! należą
również do !).
Przykład 5
Rozważmy następujący zbiór X = {a, b, c} oraz rodzinę !1 = {{a}, {b}}.
Zauważmy, że X {a} = {b, c} " !1, a także X {b} = {a, c} " !1. Każde z tych
spostrzeżeń wystarcza, aby orzec, że !1 nie jest ciałem zbiorów. Warunek sumy
również nie jest spełniony, bowiem {a} *" {b} = {a, b} " !1.
Przykład 6
Wzbogaćmy zatem rozważaną wyżej rodzinę !1 o wskazane wyżej zbiory.
Niech !2 = {{a}, {b}, {b, c}, {a, c}, {a, b}}.
Zauważmy następujące fakty: {a} *" {b, c} = {a, b, c} = X " !2 oraz
X {a, b} = {c} " !2. Jeżeli wzbogacimy rodzinę !2 o powyższe zbiory, to rodzina
ta jeszcze nie spełnia aksjomatów ciała zbiorów, gdyż X X = " " !2. Okazuje się, że
dopiero pełny zbiór potęgowy P(X) jest ciałem zbiorów zawierającym rodzinę !1.
Przykład 7
Nie tylko zbiory potęgowe są ciałami zbiorów. Jeżeli rozważymy zbiór
X = {a, b, c, d} oraz rodzinę !3 = {", {a, c}, {b, d}, X}, to łatwo zauważyć, że
spełnia ona aksjomaty ciała zbiorów.
Zachodzą następujące własności ciał zbiorów:
Twierdzenie 7
Dla dowolnego zbioru X i dowolnego ciała zbiorów ! takiego, że ! ą" P(X) jest:
(a) jeżeli A " ! oraz B " !, to A )" B " ! (iloczyny zbiorów należących do ! należą
również do !),
13
(b) " " !,
(c) X " !.
Dowód (a)
Rozważmy zbiory A oraz B należące do rodziny !. Oczywiście ich dopełnienia
X A oraz X B również należą do !.
Także suma tych zbiorów oraz dopełnienie tej sumy musi należeć do !. Zauważmy,
że zgodnie z prawami de Morgana algebry zbiorów mamy: A )" B = (A *" B ) .
I ostatecznie uwzględniając zbiór X jako uniwersum rozważań mamy:
A )" B = X (X A *" X B), a zatem iloczyn A )" B również należy do rodziny !.
14
Bibliografia
1. Gubareni N., 2001: Logika dla studentów, Wydawnictwo Politechniki
Częstochowskiej.
2. Kuratowski K., 2004: Wstęp do teorii mnogości i topologii, PWN, Warszawa.
3. Kuratowski K., Mostowski A., 1978: Teoria mnogości, PWN, Warszawa.
4. Marek W., Onyszkiewicz J., 2003: Elementy logiki i teorii mnogości w zadaniach,
PWN, Warszawa.
5. Rasiowa H., 2004: Wstęp do matematyki współczesnej, PWN, Warszawa.
6. Słupecki J., Hałkowska K., Piróg-Rzepecka K., 1994: Logika i teoria mnogości,
Warszawa.
Bibliografia stron WWW
7. Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego.
Witryna internetowa. hżÿp://www.mimuw.edu.pl/~tiuryn/skrypt-98.ps.gz, stan
z 21.09.2005 (J. Tiuryn, Wstęp do teorii mnogości i logiki).
15
Wyszukiwarka
Podobne podstrony:
M3 4 2M3 3 9hamann m3 eFm3M3 5 2M3 4 4M3 2 6M3 8 9M3 8 7Mit M3 Dynamyte 4500 M998 89 2PVR M3ECCC Sylabus CS M3 Dwięcej podobnych podstron