Тема 7

Равномощни множества. Теоретико-множествени свойства еквивалентност

Свойства на функции

Първо ще разгледаме няколко свойства на функциите, който ще помагат за по-нататък.

Нека $f : A \to B$:

  • $f[\cup X] = \cup \{ f[x] | x \in X \}$
  • $f[\cap X] \subseteq \cap \{ f[x] | x \in X \}$

Доказателство(на първото свойство):
Първо ще докажем, че $f[\cup X] \subseteq \cup \{ f[x] | x \in X \}$.
Нека $a$ е произволен елемент от $f[\cup X]$. Тогава съществува елемент $b \in \cup X$, такъв че $f(b) = a$.
Това означава, че съществува елемент $x_0 \in X$, такъв че $b \in x_0$. От тук директно получаваме $f(b) \in f[x_0] \subseteq \cup \{ f[x] | x \in X \}$.
Сега да докажем обратната посока: $\cup \{ f[x] | x \in X \} \subseteq f[\cup X]$.
Нека $a \in \cup \{ f[x] | x \in X \}$. Тогава съществува $x_0 \in X : a \in f[x_0]$. От тук $\exists b : b \in x_0 \And f(b) = a$. Тогава $b \in \cup X$, от където получаваме и $a \in f[\cup X]$.

Доказателство(на второто твърдение):
Нека $a \in f[\cap X]$. Тогава съществува елемент $b \in \cap X$, за който $f(b) = a$. Това означава, че за всеки елемент $x \in X$ трябва $b \in x$. Тоест $(\forall x \in X)(f(b) \in f[x])$. Така окончателно получихме $a \in \cap \{ f[x] | x \in X \}$.
Намерете контра пример за обратната посока.

Обратна функция

Твърдение:
Нека $\mathrm{Func}(f)$. Тогава $\mathrm{Func}(f^{-1}) \iff f$ е инекция.
Забележка: Функциите са частен случай на бинарни релации, така че обърнатата (т.е степен -1) е просто обръщане на всички наредени двойки от релацията. Една релация е фукция ако няма 2 наредени двойки със еднакъв първи елемент.

Доказателство:
Щом $\mathrm{Func}(f^{-1})$, тогава $\forall x \forall x' \forall y (\langle x, y \rangle \in f^{-1} \And \langle x', y \rangle \in f^{-1} \Rightarrow x = x')$. Т.е ако обърнем релацията и наредените двойки: $\forall x \forall x' \forall y (\langle y, x \rangle \in f \And \langle y, x' \rangle \in f \Rightarrow x = x')$. Това е точно дефиницията за инекция, от където получаваме, че $f$ е инекция.
Абсолютно аналогично се доказва обратната посока.

Нека $f : A \to B$. И нека $B_1 \subseteq \mathrm{Rng}(f)$.

(1)
\begin{eqnarray} f^{-1}[B_1] &=& \{ x | f(x) \in B_1 \} \\ &=& \mathrm{Rng}(f^{-1} \cap (B_1 \times A)) \end{eqnarray}

Обърнете внимание, че за горното равенство не е нужно $f^{-1}$ да бъде функция - на долния ред просто пресичаме обърнатата релация със декартово произведение. Ще използваме това за да докажем следните 2 свойства (аналогични на разгледаните до момента):

  • $f^{-1}[\cup Y] = \cup \{ f^{-1}[y] | y \in Y \}$
  • $f^{-1}[\cap Y] = \cap \{ f^{-1}[y] | y \in Y \}$

Доказателство:
Нека $a \in f^{-1}[\cup Y]$. Тогава $a \in \mathrm{Rng}(f^{-1} \cap ((\cup Y) \times A))$, тоест съществува наредена двойка $\langle b, a \rangle$, такава че $\langle b, a \rangle \in f^{-1} \cap ((\cup Y) \times A)$. От тук получаваме, че $b \in \cup Y$, т.е $\exists y_0 (b \in y_0 \in Y)$. Така получихме, че $\langle b, a \rangle \in f^{-1} \cap (y_0 \times A)$, от където $a \in \mathrm{Rng}(f^{-1} \cap (y_0 \times A))$. Окончателно получихме $a \in \cup \{ f^{-1}[y] | y \in Y \}$.
Абсолютно аналогично се доказва обратната посока и другото свойство.

Свойство: Композицията на биективни функции е биективна функция: Ако $f : A \to B \And g : B \to C$ са биекции, то $h = f \circ g : A \to C$ също е биекция.
Доказва се елементарно.

Равномощни множества

Дефиниция:
Множествата $A$ и $B$ ще наричаме равномощни, ако съществува биекция $f : A \to B$.
Записваме $A \sim B$, или $\bar{\bar A} = \bar{\bar B}$.

Обърнете внимание, че това е теоретикомножествено свойство, защото съществуването на биекция е просто съществуване на множество, изпълняващо дадени свойства (които вече сме дефинирали).

Свойства

  • $A \sim A$
  • $A \sim B \Rightarrow B \sim A$
  • $A \sim B \And B \sim C \Rightarrow A \sim C$

Доказателството е директно с използване на дефиницията и свойствата на биекцията, които доказахме преди малко. Обърнете внимание че тези свойства са точно свойствата на релация на еквивалентност - т.е всички множества се разбиват на групи на еквивалентност. (т.е на групи, в който всички множества са еквивалентни).

  • $A \sim \varnothing \Rightarrow A = \varnothing$
  • $A \sim A \times \{ a \}$ - дефинираме биективна функция $f(x) = \langle x, a \rangle$
  • $A \sim A_1 \And B \sim B_1 \And A \cap B = A_1 \cap B_1 = \varnothing \Rightarrow A \cup B \sim A_1 \cup B_1$

Ще докажем последното свойство:
От $A \sim A_1$ имаме, че съществува биективна функция $f : A \to A_1$.
От $B \sim B_1$ имаме, че съществува биективна функция $g: B \to B_1$.
Да образуваме множеството $h = f \cup g$.
От $A \cup B = \varnothing$ получаваме, че $h$ е функция (защото ако допуснем че има двойка $\langle x, y \rangle, \langle x, y' \rangle \in h$ то тези двойки са или едновременно от $f$ или едновременно от $g$, от където получаваме, че $y = y'$)
От $A_1 \cup B_1 = \varnothing$ получаваме, че $h$ е биекция. (със аналогични на горните разсъждения).
Така окончателно получихме биекция от $A \cup B \to A_1 \cup B_1$.

Дефиниция: Нека $A$ и $B$ са множества. Тогава дефинираме ${}^AB \leftrightharpoons \{ f\ |\ f : A \to B \}$. Това е множеството на всички функции от $A$ към $B$.

Твърдение: Нека $A \sim A_1 \And B \sim B_1$. Тогава ${}^AB \sim {}^{A_1}B_1$

Доказателство: Доказателството ще извършим на следните стъпки:

  • Ще построим функция $F : {}^AB \to A_1 \times B_1$
  • Ще докажем, че $F(h)$ е функция за всяко $h \in {}^AB$ (т.е, че $F : {}^AB \to {}^{A_1}B_1$)
  • Ще докажем, че $F$ е инективна
  • Ще докажем, че $F$ е сюрективна

Така от последните 2 получаваме съществуването на биекция между ${}^AB$ и ${}^{A_1}B_1$, с което твърдението е доказано.

Нека $h : A \to B$ е произволна функция. Дефинираме:

(2)
\begin{align} F(h) = \{ \langle f(x), g(y) \rangle | \langle x, y \rangle \in h \} \end{align}
  • Да докажем, че $F(h)$ е функция: Нека $b_1 = \langle x_1, y_1 \rangle \in F(h) \And b_2 = \langle x_1', y_1' \rangle \in F(h)$. Ще докажем, че от $y_1 \ne y_1' \Rightarrow x_1 \ne x_1'$. От дефиницията на $F$ имаме, че съществува $a_1 = \langle x, y \rangle \in h : b_1 = \langle f(x), g(y) \rangle = \langle x_1, y_1 \rangle$. По същия начин и за $b_2$ : $\exists a_2 = \langle x', y' \rangle \in h : b_2 = \langle f(x'), g(y') \rangle = \langle x_1', y_1' \rangle$. От $y_1 \ne y_1' \Rightarrow g(y) \ne g(y') \Rightarrow y \ne y' \Rightarrow x \ne x' \Rightarrow f(x) \ne f(x') \Rightarrow x_1 \ne x_1'$ (използваме, че $f, g$ са биекции и $h$ е функция).
  • Да докажем, че $F$ е инекция: Нека $h_1, h_2 \in {}^AB$. Ще докажем, че от $h_1 \ne h_2 \Rightarrow F(h_1) \ne F(h_2)$. От $h_1 \ne h_2$ имаме, че съществува поне един елемент от едното множество, който не е елемент на другото. Т.е Б.О.О. избираме $\langle x, y \rangle \in h_1 : \langle x, y \rangle \notin h_2$. От дефиницията на $F$ получаваме, че $\langle f(x), g(y) \rangle \in F(h_1)$. Допускаме, че $\langle f(x), g(y) \rangle \in F(h_2)$, тогава $\langle x, y \rangle \in h_2$ - противоречие. Тогава $\langle f(x), g(y) \rangle \notin F(h_2) \Rightarrow F(h_1) \ne F(h_2)$
  • Да докажем, че $F$ е сюрекция: Нека $h'$ е произволна функция от ${}^{A_1}B_1$. Образуваме си множеството $h = \{ \langle f^{-1}(x_1), g^{-1}(y_1) \rangle | \langle x_1, y_1 \rangle \in h' \}$. Първо ще докажем, че $h \in {}^AB$, т.е че $h$ е функция от $A$ до $B$. Нека $\langle f^{-1}(x), g^{-1}(y) \rangle, \langle f^{-1}(x'), g^{-1}(y') \rangle \in h$. Допускаме, че $g^{-1}(y) \ne g^{-1}(y')$. Тогава $y \ne y' \Rightarrow x \ne x' \Rightarrow f^{-1}(x) \ne f^{-1}(x')$, т.е получихме, че $h$ е функция. Сега очевидно $F(h) = h'$, с което доказахме, че $F$ е сюрекция.

Твърдение: $A \sim B \Rightarrow \mathcal{P}(A) \sim \mathcal{P}(B)$

Твърдение: ${}^A2 \sim \mathcal{P}(A)$

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License