Rachunek zbiorów
Na zbiorach mo\
emy wykonywać ró\
ne działania. Załó\
my, \
e i są zbiorami.
1. Zbiór
nazywamy sumą (mnogościową) zbiorów i . Znak sumy czytamy jako ``plus''.
2. Zbiór
nazywamy przekrojem (iloczynem mnogościowym) zbiorów i . Znak przekroju odczytujemy jako
``razy''.
3. Zbiór
nazywamy ró\
nicą (mnogościową) zbiorów i . Znak odczytujemy jako ``minus''.
Zbiory opisane wy\
ej wygodnie jest przedstawiać na diagramach Venna.
Dla wszystkich zachodzą następujące równowa\
ności.
W przypadku, gdy , zaś , dostajemy
Działania na zbiorach odpowiadają w ten sposób operacjom logicznym na funkcjach zdaniowych.
Przyjmujemy następującą definicję.
Definicja 4..1 Mówimy, \
e zbiory i są rozłączne, gdy nie mają wspólnych elementów. W tym
przypadku ich przekrój jest zbiorem pustym . Innymi słowy, zbiory i są rozłączne .
Przykład 1. Niech . Dla ka\
dego mamy:
Dlatego
czyli . Podobnie
i
czyli
Przykład 2. . Zakładamy, \
e to ró\
ne przedmioty. Wtedy
.
Okazuje się, \
e własności działań i na zbiorach odpowiadają własnościom spójników logicznych i
wyra\
onym w tautologiach na początku rozdziału 2 (tak więc zewnętrzne podobieństwo tych symboli
jest nieprzypadkowe).
Własności i .
1. (przemienność ).
2. (łączność ).
3. (rozdzielność względem ).
4. (rozdzielność względem ).
5. .
6. .
Przed przystąpieniem do dowodu tych równości (zwanych to\
samościami lub prawami rachunku zbiorów)
warto unaocznić je sobie zaznaczając odpowiednie zbiory na diagramach Venna. Dla przykładu robimy to
poni\
ej dla zbioru . Ponadto, podobnie jak w przypadku i , na
mocy łączności i mo\
emy pomijać nawiasy w wielokrotnych przekrojach i sumach.
Dowód. (1) Dla dowodu równości wystarczy udowodnić, \
e dla wszystkich mamy:
Wez
my więc dowolne . Wtedy
W pierwszej i trzeciej równowa\
ności korzystamy z definicji , w drugiej równowa\
ności korzystamy z
tautologii (przemienność ).
Dlatego , czyli .
W dowodzie stosujemy definicję i tautologię (przemienność ).
(2) W dowodzie stosujemy definicje i tautologie (łączność ) i
(łączność ). Przykładowo udowodnimy łączność . W tym celu wystarczy
pokazać, \
e dla dowolnego mamy
Rozwa\
my więc dowolne . Mamy następujący ciąg zdań równowa\
nych.
Dlatego , czego chcieliśmy dowieść.
W dowodach dalszych punktów stosujemy odpowiednio tautologie
(rozdzielność względem ),
(rozdzielność względem ),
.
Inkluzja zbiorów. Mówimy, \
e zbiór jest podzbiorem zbioru wtedy i tylko wtedy, gdy ka\
dy
element zbioru jest elementem zbioru . Fakt ten zapisujemy symbolicznie w postaci . W tej
sytuacji mówimy te\
, \
e zbiór zawiera się w zbiorze oraz \
e zbiór jest nadzbiorem zbioru .
Mamy więc
Powy\
sza równowa\
ność mo\
e być równie\
przyjęta za definicję pojęcia zawierania zbiorów. Zawieranie
zbiorów nazywamy te\
inkluzją zbiorów.
Mówimy, \
e zbiór jest podzbiorem właściwym zbioru wtedy i tylko wtedy, gdy jest podzbiorem
i jest ró\
ny od . Symbolicznie fakt ten zapisujemy w postaci . Mówimy wówczas, \
e
jest nadzbiorem właściwym zbioru . Mamy więc
Tu jest skrótem zdania .
Na przykład mamy , jak równie\
.
Wprost z definicji dostajemy, \
e i zbiór są podzbiorami zbioru . nazywamy podzbiorem
trywialnym zbioru , zaś podzbiorem niewłaściwym zbioru .
Nale\
y tu poło\
yć nacisk na poprawną terminologię: element zbioru nale\
y do zbioru , zaś
podzbiór zbioru zawiera się w zbiorze . Mo\
e się zdarzyć, \
e zbiór równocześnie zawiera się w
zbiorze (tzn. jest jego podzbiorem), jak i nale\
y do zbioru (tzn. jest jego elementem).
Przykład 1. Niech zaś . Oba zbiory i są jednoelementowe. Jedynym
elementem zbioru jest , czyli zbiór . Dlatego nale\
y do (czyli ). Nie jest jednak
prawdą, \
e zbiór zawiera się w zbiorze , nie jest on bowiem podzbiorem zbioru . Mianowicie
jedynym elementem zbioru jest zbiór pusty . I niestety ten właśnie element nie nale\
y do zbioru
(bo jedynym elementem zbioru jest właśnie zbiór oraz ).
Przykład 2. Niech , zaś . Tu nale\
y do oraz zawiera się w .
Poni\
ej podajemy własności inkluzji zbiorów i dalsze prawa rachunku zbiorów.
1. Jeśli i , to .
2. (przechodniość inkluzji) Jeśli i , to .
3. .
4. Jeśli i , to i .
5. .
6. .
7. .
8. .
9. .
Dowód. (1) Załó\
my, \
e i . Znaczy to, \
e dla ka\
dego mamy
czyli
Zatem .
(2) Załó\
my, \
e i . Poka\
emy, \
e . Na mocy definicji inkluzji, oznacza, \
e
dla wszystkich , jeśli , to . Aby tego dowieść, rozwa\
my dowolne . Skoro ,
to na mocy definicji , . Skoro , to na mocy definicji , , czego nale\
ało dowieść.
W punkcie (3) udowodnimy, \
e . W tym celu rozwa\
my dowolny element zbioru .
Na mocy definicji , nale\
y zarówno do , jak i do . W szczególności . W ten sposób
pokazaliśmy, \
e dla dowolnego mamy
czyli .
Dowody pozostałych punktów pozostawiamy jako ćwiczenie.
Przestrzeń, dopełnienie zbioru. Spójnikom logicznym i odpowiadają działania i na zbiorach.
Dotychczas nie wprowadziliśmy działania na zbiorach odpowiadającego spójnikowi negacji. Często zdarza
się, \
e rozwa\
amy podzbiory ustalonego zbioru . W takiej sytuacji zbiór nazywamy przestrzenią. W
tym kontekście negacji odpowiada tak zwane dopełnienie zbioru.
Dla zbioru zbiór nazywamy dopełnieniem zbioru (w przestrzeni ). Zatem dla
wszystkich mamy
W przypadku, gdy , mamy . Dopełnienie zbioru
zaznaczamy na diagramie Venna w następujący sposób.
U\
ywając operacji dopełnienia zbioru mo\
emy wyrazić kolejne prawa (to\
samości) rachunku zbiorów.
Mianowicie, dla zbiorów mamy:
1. .
2. .
3. .
4. (prawa de Morgana rachunku zbiorów).
5. .
Przykładowo uzasadnimy część punktu 4. Korzystając z definicji oraz prawa de Morgana dla , dla
ka\
dego mamy ciąg zdań równowa\
nych:
Zatem dla wszystkich mamy . Oba zbiory i są
podzbiorami przestrzeni . Wynika więc stąd, \
e mają te same elementy i .
Warto unaocznić sobie powy\
sze prawa rachunku zbiorów na diagramach Venna dla podzbiorów
przestrzeni . Przykładowo zaznaczymy na diagramie Venna zbiór .
Na koniec rozwa\
ań o rachunku zbiorów poznamy jeszcze operację ró\
nicy symetrycznej i zbioru
potęgowego. Ró\
nicą symetryczną zbiorów i nazywamy zbiór
Zbiorem potęgowym zbioru nazywamy zbiór
czyli zbiór wszystkich podzbiorów zbioru . Nazwę zbioru potęgowego uzasadnia następująca uwaga.
Uwaga 4..2 Jeśli jest skończonym zbiorem -elementowym, to zbiór ma elementów (tzn.
jest dokładnie ró\
nych podzbiorów zbioru ).
Dowód. Dowód przeprowadzimy na przykładzie zbioru -elementowego . Na ile
sposobów mo\
emy wybrać podzbiór zbioru ? Podzbiór jest wyznaczony przez swoje elementy,
które nale\
ą do . Zatem mamy następujące mo\
liwości:
1. mo\
e nale\
eć do lub nie.
2. mo\
e nale\
eć do lub nie.
3. mo\
e nale\
eć do lub nie.
4. mo\
e nale\
eć do lub nie.
W ka\
dym z punktów 1-4 mamy mo\
liwości, punkty 1.-4. są wzajemnie niezale\
ne. Dlatego łącznie
mamy mo\
liwości, i tyle\
ró\
nych podzbiorów zbioru .
Jako ćwiczenie sugerujemy czytelnikowi wypisanie wszystkich podzbiorów zbioru -elementowego
. Najlepsza metoda, to wypisywać kolejno podzbiory -elementowe (jest tylko jeden:
zbór pusty ), 1-elementowe, 2-elementowe, 3-elementowe i wreszcie 4-elementowe (jest tylko jeden:
cały zbiór ). Wiadomo, \
e jest dokładnie -elementowych podzbiorów zbioru -elementowego.
W szczególności zbiór potęgowy zbioru pustego ma element ( jest -elementowy).
Jedynym elementem zbioru jest zbiór pusty , który jest tu zarówno podzbiorem trywialnym, jak i
niewłaściwym.