---
title: "Teoria mnogości"
lecture_number: 2
has_solutions: true
has_exercises: true
---

```{include} ../_includes/sagecell-loader.md
```

# Teoria mnogości

## 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** {index}`zbiór` i **element zbioru** {index}`zbiór; element`
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.
:::

:::{prf:definition}

$x$ **należy** {index}`zbiór; należenie` do zbioru $A$, jeśli element $x$ jest elementem zbioru $A$
i oznaczmy to przez

```{math}
x\in A.
```

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

```{math}
x\notin A.
```

:::

:::{prf:remark}

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

:::{prf:definition}

Zbiory $A$ i $B$ są **identyczne** {index}`zbiór; identyczny` lub
**równe**, {index}`zbiór; równy`
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.
:::

:::{prf:definition}

**Zbiór pusty**, {index}`zbiór; pusty` oznaczany symbolem **$\emptyset$**,
to zbiór do którego nie należy żaden element.
:::

:::{prf:example}

Przykłady zbiorów:

1. $\{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$_
2. $\Set{4, 5, 6, \ldots }$ -- _zbiór składający się ze wszystkich liczb naturalnych począwszy od 4_
3. $\Set{x\in\rr : x>0} = (0, +\infty)$ -- _zbiór zadany przez formę zdaniową_
4. $\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_
5. $\Set{ \emptyset, \pi, \{1,2\}}$ -- _elementami zbioru mogą być zbiory; ten zawiera 3 elementy_
6. $\Set{ \Set{\Set{\Set{1},2},3},4}$ -- _ten zawiera 2 elementy_
7. $\Set{\emptyset} \neq \emptyset$ -- _zbiór składający się ze zbioru pustego nie jest pusty!_

:::

## 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:

```{epigraph}
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:

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

Okazało się, że to nieprawda!
:::

::::{prf:example} Antynomia Russella
:label: mat1-rem-russell

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

```{math}
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

:::{container} center-text
**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$:

```{math}
\Set{x\in X : \varphi(x)},
```

czyli dokładnie ten zbiór,
który zdefiniowaliśmy jako **wykres formy zdaniowej**. {index}`forma zdaniowa; wykres`
::::

## Inkluzja zbiorów

:::{prf:definition}

Zbiór $A$ **zawiera się** {index}`zbiór; zawieranie` w zbiorze $B$,
lub $A$ **jest podzbiorem** {index}`zbiór; podzbiór` zbioru $B$,
co piszemy jako

```{math}
A\subseteq B \qquad \text{lub} \qquad A \subset B
```

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

:::{prf:remark}

Dla dowolnego zbioru $A$ zachodzi

```{math}
\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 .$

:::

:::{prf:proposition}

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

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

:::

:::{prf:definition}

Zbiór $A$ jest **właściwym podzbiorem** {index}`zbiór; podzbiór właściwy` $B$,
co oznaczmy jako

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

:::

:::{prf:example}

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.$
  :::

## 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ą** {index}`zbiór; przestrzeń`
(**uniwersum**). {index}`zbiór; uniwersum`

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

:::{prf:definition}

**Sumę** {index}`zbiór; suma` zbiorów $A$ i $B$ definiujemy jako

```{math}
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** {index}`zbiór; iloczyn`
lub **przecięcie** {index}`zbiór; przecięcie`
lub **część wspólną** {index}`zbiór; część wspólna`
zbiorów $A$ i $B$ definiujemy jako

```{math}
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ę** {index}`zbiór; różnica` zbiorów $A$ i $B$ definiujemy jako

```{math}
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** {index}`zbiór; dopełnienie`
zbioru $A\subseteq X$ definiujemy jako zbiór

```{math}
A' = X\setminus A \subseteq X.
```

:::

:::{prf:example}

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

```{math}
\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}
```

:::

:::{prf:theorem}

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

1. $A\cup \emptyset = A$

   $A\cap \emptyset = \emptyset$

2. $A, B \subseteq A \cup B$

   $A \cap B \subseteq A, B $

3. $A\cup A = A$

   $A\cap A = A \quad$
   -- _prawa idempotentności_

4. $A\cup B = B\cup A$

   $A\cap B = B\cap A \quad$
   -- _prawa przemienności_

5. $(A\cup B)\cup C = A\cup (B\cup C)$

   $(A\cap B)\cap C = A\cap (B\cap C) \quad$
   -- _prawa łączności_

7. **$(A\cup B)' = A'\cap B'$**

   **$(A\cap B)' = A'\cup B' \quad$**
   -- _prawa de Morgana_

8. **$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_
:::

::::{exercise}
:label: m-lec-02-ex-01
:class: [exercise]

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

:::{solution-without-reference}
:class: [solution] dropdown

Dla dowolnego $x\in X$:

$$
\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}
$$

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.
:::

## Zbiór potęgowy

:::{prf:definition}

**Zbiorem potęgowym** {index}`zbiór; potęgowy` zbioru $A$ nazywamy zbiór
wszystkich podzbiorów $A$:

```{math}
2^A = \Set{B : B\subseteq A}.
```

:::

:::{prf:example}

```{math}
\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}
```

:::

:::{prf:remark}

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

## Iloczyn kartezjański

:::{narration}

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

:::{prf:definition}

**Uporządkowany układ** {index}`układ uporządkowany`
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

```{math}
\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ą** {index}`para uporządkowana`.
:::

:::{prf:definition}

**Iloczyn kartezjański zbiorów** {index}`zbiór; iloczyn kartezjański`
lub **produkt zbiorów** {index}`zbiór; produkt` $X_1, \ldots, X_n$
definiujemy jako zbiór

```{math}
\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}
```

W przypadku, gdy przestrzenie się powtarzają stosujemy oznaczenie

```{math}
\underbrace{X\times \cdots \times X}_{n \textrm{ razy}}  = X^n .
```

:::

:::{prf:example}

1. $\Set{1,2}\times\Set{3,4} = \Set{(1,3),(1,4),(2,3),(2,4)} .$
2. $\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) .$
3. Podstawowym zbiorem, który znajduje wiele zastosowań jest
   $n$-wymiarowa przestrzeń rzeczywista

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

:::

:::{prf:remark}

1. 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.

2. 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}.
   $$

:::

:::{prf:proposition}

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.
:::

## 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}).
:::

:::{prf:definition}

**Indeksowaną rodziną podzbiorów** {index}`indeksowana rodzina podzbiorów`
zbioru $X$ definiujemy jako dowolną funkcję

```{math}
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} .$
:::

:::{prf:example}
:label: example-rodzinypodzbiorow

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

   ```{math}
   \begin{aligned}
   A_2 & = \Set{1},
   &
   A_{\pi} & = \Set{1,2,3},
   &
   A_{e}   & = \Set{1,2}.
   \end{aligned}
   ```

2. 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 .$
:::

:::{prf:definition}

**Uogólnioną sumę zbiorów** {index}`zbiór; uogólniona suma` $A_t$, $t\in T$, definiujemy jako
zbiór

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

**Uogólniony iloczyn zbiorów** {index}`zbiór; uogólniony iloczyn` $A_t$, $t\in T$, definiujemy jako
zbiór

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

:::

:::{prf:example}

1. 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}
   $$

2. 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}
   $$

:::