Na tym wykładzie omówimy pojęcia zbioru i elementu zbioru, operacje na zbiorach, dowody równości zbiorów, uzupełnienie, prawa de Morgana, zbiór pusty; wspomnimy o aksjomatach teorii mnogości.
Pojęcie zbioru i pojęcie należenia do zbioru to pojęcia pierwotne, nie definiujemy ich, przyjmując, że każdy intuicyjnie je rozumie. (Z wyrażeniem pojęcie pierwotne czytelnik prawdopodobnie już się spotkał na szkolnych lekcjach geometrii – pojęciami pierwotnymi były prosta lub punkt). Zbiory najczęściej oznaczamy dużymi literami \(A, B, C, \dots X, Y, Z\). Pojawią się też w dalszych wykładach szczególne zbiory – zbiór liczb naturalnych, całkowitych, wymiernych i rzeczywistych, oznaczane odpowiednio \(\mathbb {N},\mathbb {Z}, \mathbb {Q}, \mathbb {R}\). Fakt, że element \(a\) należy do zbioru \(A\) zapisujemy \(a\in A\). Jeśli \(a\) nie należy do \(A\) piszemy \(\neg (a \in A)\) albo (częściej) \(a\notin A\). Jeśli z jakiś powodów chcemy napisać najpierw zbiór, a potem element do niego należący, piszemy \(A\ni a\).
Symbolem \(\emptyset \) oznaczamy zbiór pusty, czyli taki, do którego nie należy żaden element. Dla działań na zbiorach (zobacz poniżej) zbiór pusty odgrywa rolę podobną jak zero w arytmetyce.
Zbiory zwane były dawniej mnogościami, stąd teoria mnogości to inaczej nazwana teoria zbiorów.
Zacznijmy od definicji pewnych operacji na zbiorach i zależności między zbiorami:
Definicja 22. Niech \(A, B\) będą zbiorami.
\(\bullet \) Suma zbiorów \(A\) i \(B\) to zbiór \(A\cup B\), do którego należą wszystkie elementy zbioru \(A\), wszystkie elementy zbioru \(B\) i żadne inne.
\(\bullet \) Iloczyn (przecięcie, część wspólna) zbiorów \(A\) i \(B\) to zbiór \(A\cap B\) złożony z tych elementów zbiorów \(A\) i \(B\), które należą i do \(A\) i do \(B\).
\(\bullet \) Różnica zbiorów \(A\) i \(B\) to zbiór \(A\setminus B\), złożony z tych i tylko tych elementów zbioru \(A\), które nie należą do \(B\).
\(\bullet \) Mówimy, że zbiór \(A\) zawiera się w zbiorze \(B\), co zapisujemy \(A\subset B\) jeśli każdy element zbioru \(A\) jest też elementem zbioru \(B\).
\(\bullet \) Zbiory \(A\) i \(B\) są równe (co zapisujemy \(A=B\)) jeśli \(A\subset B\) i \(B\subset A\).
Możemy powyższą definicję zapisać także następująco:
\[ x\in A\cup B \iff x\in A \vee x\in B \]
\[ x\in A\cap B \iff x\in A \wedge x\in B \]
\[ x\in A\setminus B \iff x\in A \wedge \neg (x\in B) \]
\[ A\subset B \iff (x\in A \lra x\in B) \]
\[ A= B \iff ((x\in A \lra x\in B)\wedge (x\in B \lra x\in A) \]
Wypiszemy teraz pewne własności operacji \(\cap , \cup , \setminus \) :
Stwierdzenie 23. Niech \(A,B,C\) będą zbiorami.
1. \(A\cap B=B\cap A\) (przemienność iloczynu zbiorów)
2. \(A\cup B=B\cup A\) (przemienność sumy zbiorów)
3. \(A\cup (B\cup C)=(A\cup B)\cup C\) (łączność sumy zbiorów)
4. \(A\cap (B\cap C)=(A\cap B)\cap C\) (łączność iloczynu zbiorów)
5. \(A\cap (B\cup C)=(A\cap B)\cup (A\cap C)\) (rozdzielność iloczynu względem sumy zbiorów)
6. \(A\cup (B\cap C)=(A\cup B)\cap (A\cup C)\) (rozdzielność sumy względem iloczynu zbiorów)
7. \(A\cap B= A\setminus (A\setminus B)\)
8. \(A\cup B=A\cup (B\setminus A)\)
9. \(A\setminus (A\cap B)=A\setminus B\)
10. \(A \cap (B\setminus C)=(A\cap B)\setminus C\)
Dowód. W każdej z równości będziemy wykazywać, że \(x\) należy do prawej strony wtedy i tylko wtedy, gdy należy do lewej. Bez dodatkowych wyjaśnień korzystamy z definicji sumy, przecięcia, różnicy zbiorów. Warto zwrócić uwagę, że dowody powyższych własności są analogiczne do dowodów własności ze Stwierdzenia 10.
ad 1. \(x\in A\cap B \iff (x\in A)\wedge (x\in B) \stackrel {\textrm { \tiny \ref {stw-tautologie},2.}}{\iff } (x\in B)\wedge (x\in A)\iff x\in B\cap A \)
ad 2. \(x\in A\cup B \iff (x\in A)\vee (x\in B) \stackrel {\textrm { \tiny \ref {stw-tautologie},3.}}{\iff } (x\in B)\vee (x\in A)\iff x\in B\cup A \)
ad 3. \(x\in A\cup (B\cup C)\iff x\in A \vee (x\in B\cup C)\iff x\in A \vee (x\in B\vee x\in C)\stackrel {{\textrm {\tiny \ref {stw-tautologie},5.}}}{\iff } (x\in A \vee x\in B)\vee x\in C\iff (x\in A\cup B)\vee x\in C\iff x\in (A\cup B)\cup C\)
ad 4. \(x\in A\cap (B\cap C)\iff x\in A \wedge (x\in B\cap C)\iff x\in A \wedge (x\in B\wedge x\in C)\stackrel {{\textrm {\tiny \ref {stw-tautologie},6.}}}{\iff } (x\in A \wedge x\in B)\wedge x\in C\iff (x\in A\cap B)\wedge x\in C\iff x\in (A\cap B)\cap C\)
ad 5. \(x\in A\cap (B\cup C)\iff x\in A \wedge (x\in B \cup C)\iff x\in A \wedge (x\in B \vee x\in C)\stackrel { {\textrm {\tiny \ref {stw-tautologie},8.} }}{\iff } (x\in A \wedge x\in B)\vee (x\in A\wedge x\in C)\iff x\in (A\cap B)\cup (A\cap C)\)
ad 6. \(x\in A\cup (B\cap C)\iff x\in A \vee (x\in B \cap C)\iff x\in A \vee (x\in B \wedge x\in C)\stackrel {{\textrm {\tiny \ref {stw-tautologie},7.} }}{\iff } (x\in A \vee x\in B)\wedge (x\in A\vee x\in C)\iff x\in (A\cup B)\cap (A\cup C)\)
ad 7. \(x\in A\cap B\iff x\in A \wedge x\in B \iff (x\in A \vee \neg (x\in A))\wedge (x\in A \wedge \neg (\neg (x\in B)) \iff x\in A \wedge \neg (x\in A\wedge \neg (x\in B))\iff x\in A \wedge \neg (x\in (A\setminus B))\iff x\in A\setminus (A\setminus B),\) gdzie druga równoważność wynika z faktu, że zdanie \((x\in A \vee \neg (x\in A))\) jest zawsze prawdziwe (prawo wyłączonego środka) a zdanie \(\neg (\neg (x\in B))\) jest równoważne zdaniu \(x\in B\).
ad 8. \(x\in A\cup (B\setminus A)\iff x\in A \vee x\in (B\setminus A)\iff x\in A \vee (x\in B \wedge \neg (x\in A)) \stackrel {{\textrm {\tiny \ref {stw-tautologie},7.}}}{\iff }(x\in A\wedge x\in B)\vee (x\in A \wedge (\neg (x\in A)))\iff (x\in A\wedge x\in B)\iff x\in A\cup B,\) gdzie przedostatnia równoważność wynika z faktu, że zdanie \(x\in A \wedge (\neg (x\in A))\) jest zawsze fałszywe (por. zasada wyłączonego środka), zatem prawdziwość alternatywy zależy od drugiego ze zdań alternatywy.
ad 9. \(x\in A\wedge \neg (x\in A\cap B)\iff x\in A \wedge (x\notin A\vee x\notin B)\iff (x\in A \wedge x\notin A)\vee (x\in A \wedge x\notin B) \iff x\in A \wedge x\notin B\iff x\in A\setminus B, \) gdzie przedostatnią równoważność uzasadniamy tak jak w punkcie 8.
ad 10. \(x\in A \cap (B\setminus C)\iff x\in A\wedge (x\in B\setminus C)\iff x\in A\wedge (x\in B\wedge x\notin C)\stackrel {{\textrm { \tiny \ref {stw-tautologie},6. }}}{\iff } (x\in A\wedge x\in B)\wedge x\notin C\iff x\in A\cap B \wedge x\notin C\iff x\in (A\cap B)\setminus C.\) □
Uwaga 24. Do obrazowania pewnych zależności między zbiorami
można używać tak zwanych diagramów Venna1. Przykład takiego diagramu dla dwóch zbiorów \(A, B\) widzimy na Rysunku 2.1. Na rysunku zbiory są
w położeniu ogólnym ogólne, mogą więc na przykład posłużyć do graficznego dowodu, że \(A\setminus B=A\setminus (A\cap B)\) oraz do zobrazowania przykładu, że \(A\cup (A\setminus B)\neq
A\setminus (A\cap B)\). Więcej o ogólnym położeniu i dowodzeniu przy pomocy diagramów Venna Czytelnik może znaleźć w [3] albo na stronie
http://www.deltami.edu.pl/temat/matematyka/teoria_mnogosci/2011/02/12/Diagramy_Venna/
Rysunek 2.1:
Wykażemy teraz, że zbiór pusty jest tylko jeden. Przypomnijmy, że zbiór pusty to taki zbiór, w którym nie ma żadnego elementu. Równoważnie, możemy postawić definicję
Definicja 25. Zbiór pusty to zbiór, który zawiera się w każdym zbiorze.
Te dwa sposoby zdefiniowania zbioru pustego są równoważne. Faktycznie, jeśli w \(\emptyset \) nie ma żadnego elementu to spełniona jest implikacja \(x\in \emptyset \lra x\in A\) (poprzednik jest fałszywy). Niech teraz zbiór \(\emptyset \) zawiera się w każdym zbiorze. Gdyby istniał \(x\in \emptyset \), to biorąc zbiór \(A=\{y\}\), gdzie \(y\neq x\), dostajemy \(x\in A\) czyli \(x=y\), sprzeczność.
Stwierdzenie 26. Jest tylko jeden zbiór pusty.
Dowód. Przypuśćmy, że są dwa zbiory puste \(\emptyset _1\) i \(\emptyset _2\). Wykażemy, że są równe. Ponieważ \(\emptyset _1 \) jest zbiorem pustym, \(\emptyset _1\subset \emptyset _2\) (bo zbiór pusty zawiera się w każdym zbiorze). Analogicznie, skoro \(\emptyset _2\) jest zbiorem pustym, to \(\emptyset _2\subset \emptyset _1\). Stąd dostajemy, że \(\emptyset _1=\emptyset _2\). □
Sformułujemy teraz i wykażemy prawa de Morgana dla zbiorów.
Dowód. Dla każdej z równości wykażemy, że \(x\) należy do lewej strony wtedy i tylko wtedy, gdy \(x\) należy do prawej.
ad 1. \(x\in X\setminus (A\cup B) \iff x\in X\wedge \neg (x\in A\cup B)\stackrel {\textrm {\tiny \ref {stw-prawa de Morg zdania}.1}}{\iff } x\in X\wedge \neg (x\in A)\wedge \neg (x\in B)\iff x\in X\setminus A\wedge x\in X\setminus B\iff x\in (X\setminus A)\cap (X\setminus B)\).
ad 2. \(x\in X\setminus (A\cap B) \iff x\in X \wedge \neg (x\in A\cap B)\stackrel {{\textrm {\tiny \ref {stw-prawa de Morg zdania}.2}}}{\iff } x\in X\wedge (\neg (x\in A)\vee \neg (x\in B))\iff x\in (X\setminus A)\vee x\in (X\setminus B)\iff x\in (X\setminus A)\cup (X\setminus B)\). □
Rozważmy teraz następującą sytuację. Mamy dany, ustalony zbiór \(X\) (zwany czasem przestrzenią). Zbiory \(A,B\) są podzbiorami zbioru \(X\).
Definicja 28. Uzupełnieniem zbioru \(A\) nazywamy zbiór \(A^c:=X\setminus A=\{x\in X : x\notin A\}\).
Uwaga 29.
\[\emptyset ^c=X, \ \ X^c=\emptyset \]
Prawa de Morgana możemy teraz zapisać następująco:
Powiemy teraz kilka słów o aksjomatach teorii mnogości. Początkowo teorię mnogości rozwijano intuicyjnie (tak, jak my w tym wykładzie). Pod koniec XIX wieku zaczęło się stawać oczywiste, że takie intuicyjne podejście do tej teorii nie wystarczy. Intuicyjnie chcielibyśmy na przykład definiować zbiory przez podanie jaką własność spełniają jego elementy, przykładowo \(\{x\in \mathbb {R} : x>1 \}\) to zbiór liczb rzeczywistych większych od \(1\), ogólnie \(\{ x : \phi (x)\}\) to zbiór \(x\) spełniających własność \(\phi \). Wygląda to na pozór w porządku, ale weźmy teraz zbiór \(Z\) zdefiniowany jako zbiór tych zbiorów, które nie są swoimi elementami:
\[Z=\{A: A\notin A \}.\]
Czy sam zbiór \(Z\) jest elementem zbioru \(Z\)? Jeśli zbiór \(Z\) należy do \(Z\), to, z określenia zbioru \(Z\) mamy \(Z\notin Z\). Jeśli natomiast \(Z\notin Z\), to znowu z określenia zbioru \(Z\) mamy \(Z\in Z\). Zatem dostajemy:
\[Z\in Z\iff Z\notin Z,\]
sprzeczność. Powyższy problem zwany jest antynomią Russela2. Być może niektórym czytelnikom ta antynomia znana jest w wersji:
Fryzjer z pewnego miasta strzyże tych jego mieszkańców, którzy sami się nie strzygą. Czy fryzjer strzyże się sam?
Ta antynomia (jak i inne, o których wspomnimy w dalszych wykładach) dała impuls do stworzenia teorii mnogości opartej na aksjomatach. Obecnie, jako aksjomaty teorii mnogości przyjmuje się zestaw aksjomatów
zaproponowanych w I połowie XX wieku przez Zermelo3 i Fraenkla4. Podamy tylko niektóre z nich, zaznaczając, że nie jest to też zestaw minimalny (to znaczy możemy
niektóre aksjomaty wywnioskować z innych).
\(\bullet \) Aksjomat istnienia: Istnieje co najmniej jeden zbiór.
\(\bullet \) Aksjomat ekstensjonalności (jednoznaczności): Jeśli \(A\) i \(B\) mają te same elementy, to są identyczne.
\(\bullet \) Aksjomat zbioru pustego: Istnieje zbiór, który nie ma żadnego elementu.
\(\bullet \) Aksjomat sumy: Dla dowolnych zbiorów \(A\) i \(B\) istnieje zbiór, którego elementami są wszystkie elementy zbioru \(A\), wszystkie elementy zbioru \(B\) i żadne inne.
\(\bullet \) Aksjomat różnicy: Dla dowolnych zbiorów \(A\) i \(B\) istnieje zbiór, którego elementami są te i tylko te elementy zbioru \(A\), które nie są elementami zbioru \(B\).
\(\bullet \) Aksjomat zbioru potęgowego: Dla każdego zbioru \(X\) istnieje zbiór, oznaczany \({\cal P}(X)\) (albo \(2^X\)), którego elementami są podzbiory zbioru \(X\), czyli \({\cal P}(X)=\{Z : Z\subset X \}\).
\(\bullet \) Aksjomat wyróżniania: Dla każdej formuły \(\phi (x)\) i dla każdego zbioru \(A\) istnieje zbiór złożony dokładnie z tych elementów zbioru \(A\), które spełniają \(\phi (x)\). (Zauważmy, że stąd wynika istnienie zbioru jednoelementowego \(\{a\}\), bo \(\{a\}=\{x: x\in A \wedge x=a \}.\))
Później poznamy jeszcze aksjomat zwany aksjomatem nieskończoności. Poniżej, osobno wypiszemy jeszcze jeden aksjomat, z którego będziemy korzystać wielokrotnie. Jest aksjomat wyboru, zwany także pewnikiem
wyboru.
\(\bullet \) Pewnik wyboru: Dla każdej rodziny \(\cal R\) zbiorów niepustych i parami rozłącznych istnieje zbiór, który ma z każdym ze zbiorów z rodziny \(\cal R\) dokładnie jeden element wspólny
(czyli z każdego z tych zbiorów możemy wybrać po jednym elemencie).
Wybiegając naprzód powiedzmy, że aksjomatu tego będziemy używać w następującej wersji:
Dla każdej rodziny \(\cal R\) zbiorów niepustych istnieje funkcja \(g: {\cal R}\to \bigcup {\cal R}\), taka, że dla każdego \(R\in {\cal R}\) mamy \(g(R)\in R\).
Pojęcia funkcji i sumy rodziny zbiorów \(\bigcup {\cal R}\) pojawią się wkrótce.
1 John Venn (1834–1923), angielski matematyk, logik i filozof.
2 Bertrand Russell (1872–1970),brytyjski filozof, logik, matematyk
3 Ernst Zermelo (1871–1953), niemiecki matematyk.
4 Abraham Fraenkel (1891–1965), niemiecko-izraelski matematyk.