Teoria mnogości

Zawartość

3. Teoria mnogości#

3.1. Zbiory#

Narration

Teoria mnogości zajmuje się badaniem ogólnych właściwości zbiorów, niezależnie od natury przedmiotów, z których się one składają.

Zbiór i element zbioru to podstawowe, niedefiniowalne pojęcia teorii mnogości.

Każdy zbiór składa się ze swoich elementów i jest przez nie wyznaczony jednoznacznie.

Definicja 3.1

$x$ należy do zbioru $A$, jeśli element $x$ jest elementem zbioru $A$ i oznaczmy to przez

\[x\in A.\]

$x$ nie należy do zbioru $A$, jeśli element $x$ nie jest elementem zbioru $A$ i oznaczmy to przez

\[x\notin A.\]

Uwaga 3.1

Znak $\in$ został wprowadzony przez Giuseppe Peano i jest pierwszą literą greckiego słowa $\epsilon\sigma\tau\iota$ (czytaj: esti) oznaczającego jest.

Definicja 3.2

Zbiory $A$ i $B$ są identyczne lub równe, co piszemy jako $A = B$, jeśli

\[ \text{dla każdego $x$ zachodzi} \quad x \in A \Leftrightarrow x\in B. \]

Narration

Ponieważ każdy zbiór jest wyznaczony jednoznacznie przez swoje elementy, to $A = B$ implikuje, że $A$ i $B$ to ten sam zbiór, choć na dwa różne sposoby oznaczony lub zdefiniowany.

Definicja 3.3

Zbiór pusty, oznaczany symbolem $\emptyset$, to zbiór do którego nie należy żaden element.

Przykład 3.1

Przykłady zbiorów:

$\{a, b, c\} = \{c, a, b\} = \{a, c, a, b, a\}$ – zbiór skończony składający się z 3. elementów: $a$, $b$ i $c$
$\Set{4, 5, 6, \ldots }$ – zbiór składający się ze wszystkich liczb naturalnych począwszy od 4
$\Set{x\in\rr : x>0} = (0, +\infty)$ – zbiór zadany przez formę zdaniową
$\Set{n\in \zz : 2 | n } = \Set{ n : \text{istnieje } k\in\zz \text{ takie, że } n = 2k} = \Set{2k : k\in \zz}$ – ten sam zbiór zadany przez różne formy zdaniowe
$\Set{ \emptyset, \pi, \{1,2\}}$ – elementami zbioru mogą być zbiory; ten zawiera 3 elementy
$\Set{ \Set{\Set{\Set{1},2},3},4}$ – ten zawiera 2 elementy
$\Set{\emptyset} \neq \emptyset$ – zbiór składający się ze zbioru pustego nie jest pusty!

3.2. Antynomia Russella#

Narration

Na pierwszy rzut oka wszystko wydaje się jasne – obiekty, którymi zajmują się matematycy, to zbiory. Jednak sytuacja jest nieco bardziej skomplikowana.

Twórcą pierwszej – dziś określanej mianem intuicyjnej lub naiwnej – teorii mnogości był Georg Cantor, który zbiór określał następująco:

Zbiorem jest spojenie w całość określonych rozróżnialnych podmiotów naszej poglądowości czy myśli, które nazywamy elementami danego zbioru.

Problem z tym podejściem zauważył Bertrand Russell, który – mówiąc uproszczonym językiem – zadał pytanie:

Czy dla dowolnej formy zdaniowej $\varphi(x)$ kolekcja $\Set{x : \varphi(x)}$ jest zbiorem?

Okazało się, że to nieprawda!

Przykład 3.2 (Antynomia Russella)

Rozważmy

\[ Z = \Set{x : x\notin x} \]

i zapytajmy, czy $Z\in Z .$

Gdyby $Z \in Z$, to z definicji $Z$ musiałoby zachodzić $Z\notin Z$ – sprzeczność.

Gdyby $Z\notin Z$, to $Z$ spełnia warunek definiujący $Z$, więc $Z\in Z$ – znów sprzeczność.

Otrzymujemy

\[Z\in Z \Leftrightarrow Z \notin Z,\]

co jest niemożliwe. Zatem tak określone $Z$ nie jest zbiorem.

Antynomia Russella pokazuje, że nie każda kolekcja obiektów spełniających formę zdaniową jest zbiorem – w szczególności

Nie istnieje zbiór wszystkich zbiorów!

Aby uniknąć takich sprzeczności, formy zdaniowe wolno stosować jedynie do wyodrębniania podzbioru pewnego wcześniej ustalonego zbioru $X$:

\[\Set{x\in X : \varphi(x)},\]

czyli dokładnie ten zbiór, który zdefiniowaliśmy jako wykres formy zdaniowej.

3.3. Inkluzja zbiorów#

Definicja 3.4

Zbiór $A$ zawiera się w zbiorze $B$, lub $A$ jest podzbiorem zbioru $B$, co piszemy jako

\[A\subseteq B \qquad \text{lub} \qquad A \subset B\]

jeśli dla każdego $x$ zachodzi $x\in A \Rightarrow x\in B.$

Uwaga 3.2

Dla dowolnego zbioru $A$ zachodzi

\[\begin{aligned} \emptyset \subseteq A \qquad \text{oraz} \qquad A \subseteq A. \end{aligned}\]

Należy wyraźnie rozróżnić pojęcie przynależności elementu i inkluzji zbiorów. Na przykład:

$1 \in \nn$ oraz $\{1\} \subseteq \nn$, ale $\{1\} \notin \nn$
$\emptyset \subseteq \nn$, ale $\emptyset \notin \nn$ oraz $\{\emptyset\} \nsubseteq \nn .$

Stwierdzenie 3.1

Dla dowolnych zbiorów $A, B, C$ zachodzą następujące własności:

$A = B \Leftrightarrow (A\subseteq B \wedge B \subseteq A)$
$(A\subseteq B \wedge B\subseteq C) \Rightarrow A \subseteq C.$

Definicja 3.5

Zbiór $A$ jest właściwym podzbiorem $B$, co oznaczmy jako

\[\begin{aligned} A \subsetneq B, \qquad \text{jeśli} \qquad A \subseteq B \wedge A \neq B. \end{aligned}\]

Przykład 3.3

Niech $B = \Set{1, 3, \Set{3}, \Set{1, 2}, \emptyset, \Set{1, \emptyset}, \Set{\emptyset, \Set{\emptyset}}} .$ Wówczas:

$1\in B$ oraz $\Set{ 1 } \subseteq B$, ale $\Set{ 1 } \notin B$
$3\in B$ $\Set{ 3 } \subseteq B$ oraz $\Set{ 3 } \in B$
$\Set{1, \emptyset} \in B$ oraz $\Set{1, \emptyset} \subseteq B$
$\Set{2, 1} \in B$ ale $\Set{2,1} \nsubseteq B $
$\emptyset \subseteq B$ ale również $\emptyset \in B $
$\Set{\emptyset, \Set{\emptyset}} \in B$ ale $\Set{\emptyset, \Set{\emptyset}} \nsubseteq B.$

3.4. Działania na zbiorach#

Narration

W teorii zbiorów ograniczamy się do rozważania tylko takich zbiorów, które są podzbiorami pewnego ustalonego zbioru zwanego przestrzenią (uniwersum).

Niech $X$ będzie ustaloną przestrzenią.

Definicja 3.6

Sumę zbiorów $A$ i $B$ definiujemy jako

\[A\cup B = \{x\in X : x\in A \vee x \in B\},\]

czyli zbiór składający się ze wszystkich elementów zbioru $A$, wszystkich elementów zbioru $B$ i nie zawierający żadnych innych elementów.

Iloczyn lub przecięcie lub część wspólną zbiorów $A$ i $B$ definiujemy jako

\[A\cap B = \{x \in X : x\in A \wedge x \in B\},\]

czyli zbiór składający się z elementów zbioru $A$, które są jednocześnie elementami zbioru $B .$

Różnicę zbiorów $A$ i $B$ definiujemy jako

\[A\setminus B = A - B = \{x \in X : x\in A \wedge x \notin B\},\]

czyli zbiór składający się ze wszystkich elementów zbioru $A$, które nie są w zbiorze $B .$

Dopełnienie zbioru $A\subseteq X$ definiujemy jako zbiór

\[A' = X\setminus A \subseteq X.\]

Przykład 3.4

Dla $A = \Set{0,1,2}$, $B = \Set{0,2,4}$ w przestrzeni $X = \nn$:

\[\begin{split}\begin{aligned} A\cup B & = \Set{0,1,2,4}, & A\cap B & = \Set{0,2}, \\ A\setminus B & = \Set{1} \neq \Set{4} = B\setminus A, & \emptyset' & = X = \nn. \end{aligned}\end{split}\]

Twierdzenie 3.2

Dla dowolnych zbiorów $A, B, C$ zachodzą następujące własności:

$A\cup \emptyset = A$

$A\cap \emptyset = \emptyset$
$A, B \subseteq A \cup B$

$A \cap B \subseteq A, B $
$A\cup A = A$

$A\cap A = A \quad$ – prawa idempotentności
$A\cup B = B\cup A$

$A\cap B = B\cap A \quad$ – prawa przemienności
$(A\cup B)\cup C = A\cup (B\cup C)$

$(A\cap B)\cap C = A\cap (B\cap C) \quad$ – prawa łączności
$(A\cup B)' = A'\cap B'$

$(A\cap B)' = A'\cup B' \quad$ – prawa de Morgana
$A\cup (B\cap C) = (A\cup B)\cap (A\cup C)$

$A\cap (B\cup C) = (A\cap B)\cup (A\cap C)$

$A\cap (B\setminus C) = (A\cap B)\setminus (A\cap C) \quad$ – prawa rozdzielności

Ćwiczenie 3.1

Udowodnijmy pierwsze prawo de Morgana: $(A\cup B)' = A' \cap B' .$

Rozwiązanie

Dla dowolnego $x\in X$:

\[\begin{split} \begin{aligned} x\in (A\cup B)' & \qlq x\notin A\cup B \\ & \qlq \Negation(x\in A \vee x\in B) \\ & \qlq x\notin A \wedge x\notin B \\ & \qlq x\in A' \wedge x\in B' \\ & \qlq x\in A'\cap B'. \end{aligned} \end{split}\]

Ponieważ powyższa równoważność zachodzi dla każdego $x\in X$, to zbiory $(A\cup B)'$ i $A'\cap B'$ mają te same elementy, czyli są równe.

3.5. Zbiór potęgowy#

Definicja 3.7

Zbiorem potęgowym zbioru $A$ nazywamy zbiór wszystkich podzbiorów $A$:

\[2^A = \Set{B : B\subseteq A}.\]

Przykład 3.5

\[\begin{split}\begin{aligned} A=\emptyset & \quad \imply \quad 2^A = \Set{\emptyset}, \\ A=\Set{a} & \quad \imply \quad 2^A = \Set{\emptyset, \Set{a}}, \\ A=\Set{a,b} & \quad \imply \quad 2^A = \Set{\emptyset, \Set{a}, \Set{b}, \Set{a,b}}. \end{aligned}\end{split}\]

Uwaga 3.3

Jeśli zbiór $A$ ma $n$ elementów, to zbiór $2^A$ ma $2^n$ elementów – stąd oznaczenie.

3.6. Iloczyn kartezjański#

Narration

Niech $n\in\nn$ i $n \geq 2 .$

Definicja 3.8

Uporządkowany układ elementów $a_1, a_2, \ldots ,a_n$ zapisujemy jako $(a_1,a_2,\ldots ,a_n) .$ Dwa układy uporządkowane $(a_1,a_2,\ldots ,a_n)$ i $(b_1,b_2,\ldots ,b_n)$ uważamy za równe, co piszemy jako

\[\begin{aligned} (a_1, a_2,\ldots, a_n) = (b_1, b_2,\ldots, b_n), \qtq a_i = b_i \text{ dla } i\in\{1, \ldots, n\} . \end{aligned}\]

W przypadku $n=2$ uporządkowany układ $(x,y)$ nazywamy uporządkowaną parą .

Definicja 3.9

Iloczyn kartezjański zbiorów lub produkt zbiorów $X_1, \ldots, X_n$ definiujemy jako zbiór

\[\begin{split}\begin{aligned} X_1 \times \cdots \times X_n = \displaystyle \prod_{i=1}^n X_i = \begin{cases} \ \Set{(x_1,\ldots,x_n) : x_1\in X_1 \wedge \ldots \wedge x_n \in X_n}, & \qquad \text{jeśli } X_1, \ldots, X_n \neq \emptyset \\ \ \emptyset & \qquad \text{w p.p.} \end{cases} . \end{aligned}\end{split}\]

W przypadku, gdy przestrzenie się powtarzają stosujemy oznaczenie

\[\underbrace{X\times \cdots \times X}_{n \textrm{ razy}} = X^n .\]

Przykład 3.6

$\Set{1,2}\times\Set{3,4} = \Set{(1,3),(1,4),(2,3),(2,4)} .$
$\rr\times\rr = \rr^2$ to płaszczyzna, a $[1,3]\times[1,2]$ to prostokąt o wierzchołkach $(1,1),(1,2),(3,1),(3,2) .$
Podstawowym zbiorem, który znajduje wiele zastosowań jest $n$-wymiarowa przestrzeń rzeczywista

\[\rr^n = \Set{(x_1,\ldots,x_n) : x_i\in \rr \text{ dla } i\in\{1, \ldots, n\} }.\]

Uwaga 3.4

Jeżeli $X, Y\neq \emptyset$ oraz $X\neq Y$, to $X\times Y\neq Y\times X$, czyli iloczyn kartezjański nie jest przemienny.
Jeżeli $X, Y, Z\neq \emptyset$, to $\Paren{X \times Y} \times Z \neq X \times \Paren{ Y \times Z}$, czyli iloczyn kartezjański nie jest łaczny. Dla przykładu, jeśli $X=\Set{0}$ to

\[ \Paren{X \times X} \times X = \Set{\Paren{\Paren{0,0},0}} \neq \Set{\Paren{0,\Paren{0,0}}} = X \times \Paren{X \times X}. \]

Stwierdzenie 3.3

Jeżeli zbiór $X_i$ ma $m_i\in \nn$ elementów, dla $i \in \Set{1,\ldots, n}$, to zbiór $X_1\times\cdots\times X_n$ ma $m_1\cdots m_n$ elementów.

3.7. Działania nieskończone na zbiorach#

Narration

Niech $X\neq \emptyset$ będzie zbiorem odgrywającym rolę przestrzeni, $T\neq\emptyset$ – zbiorem indeksów (elementy zbioru $T$ nazywamy {indeksami}).

Definicja 3.10

Indeksowaną rodziną podzbiorów zbioru $X$ definiujemy jako dowolną funkcję

\[f: T \to 2^X,\qquad f(t) = A_t\subseteq X,\]

która przyporządkowuje każdemu $t\in T$ pewien podzbiór $A_t$ w $X .$

Indeksowaną rodzinę zbiorów oznaczamy przez $\quad (A_t)_{t\in T} .$

Przykład 3.7

Dla $X=\rr$, $T = \Set{2,\pi,e}$, $f(t) = A_t = \Set{n\in \nn : n < t}$, mamy:

\[\begin{aligned} A_2 & = \Set{1}, & A_{\pi} & = \Set{1,2,3}, & A_{e} & = \Set{1,2}. \end{aligned}\]
Dla $X=\rr$, $T = \nn$ przyjmujemy $A_t = \IntCO{-n,\frac 1 n} .$

Narration

Niech $(A_t)_{t\in T}$ będzie dowolną indeksowaną rodziną podzbiorów zbioru $X .$

Definicja 3.11

Uogólnioną sumę zbiorów $A_t$, $t\in T$, definiujemy jako zbiór

\[\displaystyle\bigcup_{t\in T} A_t = \{a\in X : \exists t\in T \,\, a \in A_t\}.\]

Uogólniony iloczyn zbiorów $A_t$, $t\in T$, definiujemy jako zbiór

\[\displaystyle\bigcap_{t\in T} A_t = \{a\in X :\forall t\in T \,\, a \in A_t\}.\]

Przykład 3.8

Dla $X=\rr$, $T = \Set{2,\pi,e}$, $f(t) = A_t = \Set{n\in \nn : n < t}$ mamy:

\[ \begin{aligned} \bigcup_{t\in T} A_t & = A_2 \cup A_{\pi} \cup A_e = \Set{1,2,3} & \bigcap_{t\in T} A_t & = A_2 \cap A_{\pi} \cap A_e = \Set{1} \end{aligned} \]
Dla $X=\rr$, $T = \nn$, $A_n = \IntCO{-n,\frac 1 n}$ mamy:

\[ \begin{aligned} \bigcup_{n\in \nn} A_n & = (-\infty, 1) & \bigcap_{n\in \nn} A_n & = [-1, 0]. \end{aligned} \]