Теория на множеството - домашно

Това са условията и решенията на задачите от първото домашно сезон 2008/2009 година, зима


страницата се нуждае от дописване/преглеждане


Задача 1

Нека $A, B, C$ са множества, такива че $B \in \mathcal P(A)$ и

(1)
\begin{align} \forall x(x \in C \iff (\exists y \in B)(x = A \setminus y)) \end{align}

Докажете, че $A \setminus \cup B = \cap C$ и $A \setminus \cap B = \cup C$.

Лема 1:

(2)
\begin{eqnarray} \mbox{1. }A \setminus \cup B &=& \bigcap_{b \in B} A \setminus b \\ \mbox{2. }A \setminus \cap B &=& \bigcup_{b \in B} A \setminus b \end{eqnarray}

Доказателство:
1. Нека $a \in A \setminus \cup B$

(3)
\begin{eqnarray} &\iff& a \in A \And a \notin \cup B \\ &\iff& a \in A \And (\forall b \in B)(a \notin b) \\ &\iff& (\forall b \in B)(a \in A \And a \notin b) \\ &\iff& (\forall b \in B)(a \in A \setminus b) \\ &\iff& a \in \bigcap_{b \in B} A \setminus b \end{eqnarray}

2. Нека $a \in A \setminus \cap B$

(4)
\begin{eqnarray} &\iff& a \in A \And a \notin \cap B \\ &\iff& a \in A \And (\exists b \in B)(a \notin b) \\ &\iff& (\exists b \in B)(a \in A \And a \notin b) \\ &\iff& (\exists b \in B)(a \in A \setminus b) \\ &\iff& a \in \bigcup_{b \in B} A \setminus b \end{eqnarray}

Решение на 1ва задача:
Първо ще докажем, че $C = \{ A \setminus b | b \in B \}$.
Нека $c \in C$. Тогава $(\exists y \in B)(c = A \setminus y)$, т.е $c \in \{ A \setminus b | b \in B \}$.
Нека $c \in \{ A \setminus b | b \in B \}$. Тогава $(\exists b \in B)(c = A \setminus b)$, т.е $c \in C$.

Сега, използвайки лемата лесно доказваме 2те равенства:

(5)
\begin{eqnarray} A \setminus \cup B &=& \underset{b \in B}\bigcap A \setminus b = \cap C \\ A \setminus \cap B &=& \underset{b \in B}\bigcup A \setminus b = \cup C \end{eqnarray}

Задача 2

Нека $A$ и $B$ са непразни множества.
Докажете, че:
1. ако $A \times B = C \times D$ то $A = C \And B = D$;
2. ако $(A \times B) \cup (B \times A) = C \times C$, то $A = B = C$.

Решение на 2ра задача:
1. Ще докаем чрез влагане в двете посоки.
Нека $a \in A$ и $b \in B$ са произволни. Тогва:

(6)
\begin{eqnarray} \langle a, b \rangle \in A \times B &\Rightarrow& \langle a, b \rangle \in C \times D\\ &\Rightarrow& a \in C \And b \in D \\ &\Rightarrow& A \subseteq C \And B \subseteq D \end{eqnarray}

Така доказахме, че ако $A \neq \varnothing \And B \neq \varnothing \And A \times B = C \times D$, то $A \subseteq C \And B \subseteq D$. Т.е $C, D$ са непразни множества, за които е изпълнено $C \times D = A \times B$. Сега прилагаме същото заключение, но този път за $C$ и $D$ и получаваме, че $C \subseteq A \And D \subseteq B$. Окончателно $A = C \And B = D$.
2. Ще докажем чрез влагане в двете посоки.
$| \subseteq |$ Нека $a \in A$ и $b \in B$ са произволни. Тогава:

(7)
\begin{eqnarray} \langle a, b \rangle \in A \times B &\Rightarrow& \langle a, b \rangle \in C \times C \\ &\Rightarrow& a \in C \And b \in C \\ &\Rightarrow& A \subseteq C \And B \subseteq C \end{eqnarray}

$| \supseteq |$ Нека $c \in C$ е произволно. Тогава:

(8)
\begin{eqnarray} \langle c, c \rangle \in C \times C &\Rightarrow& \langle c, c \rangle \in (A \times B) \cup (B \times A) \\ &\Rightarrow& (\langle c, c \rangle \in A \times B) \lor (\langle c, c \rangle \in B \times A) \\ &\Rightarrow& c \in A \And c \in B\\ &\Rightarrow& C \subseteq A \And C \subseteq B \end{eqnarray}

Окончателно получихме $C = A \And C = B$, т.e $A = B = C$.

Задача 3

Нека за всяко естествено число $n$, $F_n$ е множество. Дефинираме:

(9)
\begin{eqnarray} \underset{n=\infty}{\mathrm{Lim}\ \sup} F_n &=& \bigcap_{n=0}^{\infty}\bigcup_{k=0}^{\infty}F_{n+k} \\ \underset{n=\infty}{\mathrm{Lim}\ \inf} F_n &=& \bigcup_{n=0}^{\infty}\bigcap_{k=0}^{\infty}F_{n+k} \end{eqnarray}

Докажете, че:

(10)
\begin{align} \bigcap_{n=0}^{\infty} F_n \subseteq \underset{n=\infty}{\mathrm{Lim}\ \inf} F_n \subseteq \underset{n=\infty}{\mathrm{Lim}\ \sup} F_n \subseteq \bigcup_{n=0}^{\infty} F_n \end{align}

Дайте пример за такава редица от множества $F_n$, че и 3те включвания да са строги.

Решение на 3та задача:
(i) Ще докажем, че $\bigcap_{n=0}^{\infty} F_n \subseteq \underset{n=\infty}{\mathrm{Lim}\ \inf} F_n$

(11)
\begin{eqnarray} a \in \underset{n}\bigcap F_n &\Rightarrow& (\forall n)(a \in F_n) \\ &\Rightarrow& (\exists n = 0)(\forall k)(a \in F_{n+k}) \\ &\Rightarrow& a \in \bigcup_{n=0}^{\infty}\bigcap_{k=0}^{\infty}F_{n+k} \\ &\Rightarrow& a \in \underset{n=\infty}{\mathrm{Lim}\ \inf} F_n \end{eqnarray}

(ii) Ще докажем, че $\underset{n=\infty}{\mathrm{Lim}\ \inf} F_n \subseteq \underset{n=\infty}{\mathrm{Lim}\ \sup} F_n$

(12)
\begin{eqnarray} a \in \bigcup_{n=0}^{\infty}\bigcap_{k=0}^{\infty}F_{n+k} &\Rightarrow& (\exists n = n_0)(\forall k)(a \in F_{n+k}) \\ &\Rightarrow& (\forall n \ge n_0)(a \in F_n) \\ &\Rightarrow& (\forall n)(\exists k = n_0)(a \in F_{n+k}) \\ &\Rightarrow& a \in \bigcap_{n=0}^{\infty}\bigcup_{k=0}^{\infty}F_{n+k} \\ &\Rightarrow& a \in \underset{n=\infty}{\mathrm{Lim}\ \sup} F_n \\ \end{eqnarray}

(iii) Ще докажем, че $\underset{n=\infty}{\mathrm{Lim}\ \sup} F_n \subseteq \bigcup_{n=0}^{\infty} F_n$

(13)
\begin{eqnarray} a \in \underset{n=\infty}{\mathrm{Lim}\ \sup} F_n &\Rightarrow& (\forall n)(\exists k)(a \in F_{n+k}) \\ &\Rightarrow& (\exists n)(a \in F_n) \\ &\Rightarrow& a \in \bigcup_{n=0}^{\infty} F_n \\ \end{eqnarray}

Нека $a \in \underset{n=\infty}{\mathrm{Lim}\ \sup} F_n$. Тогава $(\forall n\exists k)(a \in F_{n+k})$. Тривиално $(\exists n)(a \in F_n)$ от където $a \in \bigcup_{n=0}^{\infty} F_n$.
(iv) Пример за строго влагане:

(14)
\begin{eqnarray} F_0 &=& \{ c \} \\ F_1 &=& \{ a, b \} \\ F_2 &=& \{ a \} \\ F_3 &=& \{ a, b \} \\ &\vdots& \\ F_{2n} &=& \{ a \} \\ F_{2n+1} &=& \{ a, b \} \\ &\vdots& \end{eqnarray}

Лесно се проверява, че 4те множества са $\varnothing \subset \{a\} \subset \{a, b \} \subset \{ a, b, c \}$.

Задача 4

Нека $C \subseteq A$ и $B \subseteq D$. Докажете, че ако $C \cup D \sim C$, то $A \cup B \sim A$.
Решение на 4та задача:
Нека $f : C \cup D \to C$ е инекция. Съществуването идва от $C \cup D \sim C$. Тогава дефинираме $g : A \cup B \to A$

(15)
\begin{align} g(x) = \begin{cases} f(x) & x \in C \cup B \\ x & x \in A \setminus (C \cup B) \end{cases} \end{align}

1. Първо да се убедим, че дефиницията е коректна:
1.1) $C \cup B$ е подмножество на дефиниционното $A \cup B$. Също така $f$ е дефинирана върху $C \cup B$, и резултата и е в $C$ което е подмножество на функционалното множество $A$.
1.2) $A \setminus (C \cup B)$ е подмножество на $A$ и заедно с първия случай покрива напълно дефиниционната област $A \cup B$. Също така резултата е пак в $A \setminus (C \cup B)$, т.е подмножество на функционалната област $A$.
2. Да проверим инективността на функцията - двата й клона по отделно са инективни.
2.1) В първия клон функционалните стойности са подмножество на $C$ (според дефиницията на $f$.
2.2) Във втория клон функционалните стойности са от $A \setminus (C \cup B)$, за което е изпълнено $(A \setminus (C \cup B)) \cap C = \varnothing$, т.е функционалните стойности на двата клона са от непресичащи се множества. Следователно $g$ е инекция на $A \cup B$ върху $A$. Следователно $\overline{\overline{A \cup B}} \le \overline{\overline{A}}$. От друга страна $\overline{\overline{A}} \le \overline{\overline{A \cup B}}$ (използваме инекцията идентитет), и по теоремата на Кантор-Шрьодер-Берщраин получаваме $A \cup B \sim A$.

Задача 5

Разглеждаме редици от цели положителни числа. Нека $\{ a_n \}_{n=0}^{+\infty}$ и $\{ b_n \}_{n=0}^{+\infty}$ са две редици. Ще казваме, че редицата $\{ b_n \}_{n=0}^{+\infty}$ е по-бърза от $\{ a_n \}_{n=0}^{+\infty}$ ако $\underset{n \to +\infty}\lim \frac{a_n}{b_n} = 0$.

  1. Докажете, че за всяка редица съществува по-бърза от нея редица
  2. Нека $H$ е множество от редици от цели положителни числа, удовлетворяващи условието: за всяка редица $\alpha$ съществува редица $\beta \in H$, която е по-бърза от $\alpha$. Докажете, че $H$ е неизброимо множество.

Решение на 5та задача:
1. Нека $\bar a = \{ a_n \}_{n=0}^{+\infty}$ е редица от цели положителни числа. Тогава редицата $\bar b = \{ na_n \}_{n=0}^{+\infty}$ също е редица от цели положителни числа, и е по-бърза от $\bar a$.
2. Релацията "e по-бърза" е релация на строга частична наредба. (иррефлексивна, асиметрична, транзитивна - доказва се с елементарни действия с $\lim$).
Очевидно множеството $H$ е безкрайно, защото моделите на строга частична наредба са безкрайни. Тогава остава $H$ да е изброимо или $H$ да е неизброимо. Ще докажем, че $H$ не е изброимо, чрез допускане на противното и използване да диагонален метод: нека фиксираме някаква наредба на елемените на $H : h_0, h_1, h_2, \cdots, h_n, \cdots$.

(16)
\begin{matrix} h_0 & : & h_{0,0} & h_{0,1} & h_{0,2} & \cdots & h_{0, n} & \cdots \\ h_1 & : & h_{1,0} & h_{1,1} & h_{1,2} & \cdots & h_{1, n} & \cdots \\ h_2 & : & h_{2,0} & h_{2,1} & h_{2,2} & \cdots & h_{2, n} & \cdots \\ & & \vdots & \vdots & \vdots & \ddots & \vdots & \\ h_n & : & h_{n,0} & h_{n,1} & h_{n,2} & \cdots & h_{n, n} & \cdots \\ & & \vdots & \vdots & \vdots & & \vdots & \ddots \\ \end{matrix}

Образуваме си редицата $\bar p = \{ p_n \}_{n=0}^{+\infty}$, така че $p_n = \underset{i \le n}\max\{ h_{i, n} \} + 1$. Според допускането има индекс $n_0 \in \mathbb N$, такъв че $h_{n_0}$ е по-бърза от $\bar p$. Обаче $\forall n > n_0 : p_n > h_{n_0,n} \Rightarrow \underset{n \to +\infty}\lim \frac{p_n}{h_{n_0,n}} \ge 1$. T.e доказахме, че всяка редица с индекс по-голям от $n_0$ не е по-бърза от $\bar p$. Т.е получихме, че има поне една, но не повече от краен брой редици от $H$, който са по-бързи от $\bar p$. Нека вземем една такава редица по-бърза редица $\bar h_{p_1}$. Съществува редица, по-бърза от нея - да я кръстим $\bar h_{p_2}$. Така образуваме безкрайната редица $\{ h_{p_i} \}_{i=1}^{+\infty}$, като всяка редица е по-бърза от предходната. Тогава всяка редица е по-бърза и от $\bar p$. Противоречие - показахме, че имама не повече от краен брой по-бързи редици от $\bar p$ в $H$.

Задача 6

Нека $\langle A, \le \rangle$ е решетка, т.е. такова частично наредено множество, че за произволни $x$ и $y$ от $A$ съществуват $\inf\{ x, y \}$ и $\sup \{ x, y \}$. Докажете, че:

(17)
\begin{align} a \le c \Rightarrow \sup\{ a, \inf\{ b, c \} \} \le \inf \{ \sup \{ a, b \}, c \} \end{align}

Решение на 6та задача:
Нека

(18)
\begin{eqnarray} X &=& a \sqcup (b \sqcap c) \\ Y &=& (a \sqcup b) \sqcap c \end{eqnarray}

Да разгледаме

(19)
\begin{eqnarray} X \sqcup b &=& (a \sqcup (b \sqcap c)) \sqcup b \\ &=& a \sqcup (b \sqcup (b \sqcap c)) \\ &=& a \sqcup b \end{eqnarray}

Сега да разпишем в $X \sqcap Y$:

(20)
\begin{eqnarray} X \sqcap Y &=& X \sqcap ((a \sqcup b) \sqcap c) \\ &=& X \sqcap ((X \sqcup b) \sqcap c) \\ &=& (X \sqcap (X \sqcup b)) \sqcap c \\ &=& X \sqcap c \end{eqnarray}

Ще докажем, че $X \sqcap c = X$, като докажем еквивалентното му $X \sqcup c = c$:

(21)
\begin{eqnarray} X \sqcup c &=& (a \sqcup (b \sqcap c)) \sqcup c \\ &=& a \sqcup (c \sqcup (b \sqcap c)) \\ &=& a \sqcup c \\ &=& c \end{eqnarray}

Показахме, че $X \sqcup c = c$, което е равносилно на $X \le c$, което от своя страна е равносилно на $X \sqcap c = X$. Така получихме, че $X \sqcap Y = X \sqcap c = X$, следователно $X \le Y$, с което задачата е доказана!

Задача 7

Докажете, че автоморфизмите в $\langle \mathbb Z, \le \rangle \oplus \langle \mathbb Z, \le \rangle$ са изброимо много.

Решение на 7ма задача:
Нека $A = \langle \mathbb Z, \le \rangle \oplus \langle \mathbb Z, \le \rangle = \{ \langle x, y \rangle | x \in \mathbb Z \And y \in \{ 1, 2 \} \}$.
Нека $f : A \to A$ е произволен автоморфизъм. Ще разгледаме няколко възможни случая за $f(\langle 0, 1 \rangle)$:
1. $f(\langle 0, 1 \rangle) = \langle x_0, 1 \rangle \quad x_0 \in \mathbb Z$
Ще докажем, че $f(\langle x, 1 \rangle) = \langle x + x_0, 1 \rangle \quad \forall x \in \mathbb Z \quad \star$, като използваме две индукции по $x$.
1.1 Ще докажем, че $f(\langle x, 1 \rangle) = \langle x + x_0, 1 \rangle \quad \forall x \in \mathbb N$
База Очевидно е вярно при $x = 0$
Индукционна хипотеза Допускаме, че твърдението е вярно за $x = \overline{1,n-1}$, т.е $f(\langle x, 1 \rangle) = \langle x + x_0, 1 \rangle)$
Индукционна стъпка Ще докажем, че твърдението е вярно за $n$:
$f(\langle n, 1 \rangle) > f(\langle n-1, 1 \rangle) = \langle n-1+x_0, 1 \rangle$ - защото $f$ е автоморфизъм и запазва реда.
Разглеждаме следните два случая за $f(\langle n, 1 \rangle)$:
1.1.1 $f(\langle n, 1 \rangle) = \langle y, 1 \rangle \quad y \ge n + x_0$. Ако $y > n + x_0$ получаваме противоречие, защото $\langle n, 1 \rangle = f^{-1} (\langle y, 1 \rangle) > f^{-1}(\langle n+x_0, 1 \rangle) > f^{-1}(\langle n-1+x_0) = \langle n-1, 1 \rangle$ което очевидно е невъзможно, защото излиза, че $f^{-1}(\langle n+x_0, 1 \rangle)$ е между два последователни елемента в $\langle \mathbb Z, \le \rangle \oplus \langle \mathbb Z, \le \rangle$. Така в този случай остава единствено $y = n + x_0$.
1.1.2 $f(\langle n, 1 \rangle) = \langle z, 2 \rangle \quad z \in \mathbb Z$ - аналогично на предния случай получаваме $\langle n-1, 1 \rangle = f^{-1}(\langle n-1+x_0, 1 \rangle) < f^{-1}(\langle n+n_0, 1 \rangle) < f^{-1}(\langle z, 2 \rangle) = \langle n, 1\rangle$.
С това доказахме, че $f(\langle n, 1 \rangle) = \langle n+x_0, 1 \rangle$.
1.2 $f(\langle -x, 1 \rangle) = \langle -x + x_0, 1 \rangle \quad \forall x \in \mathbb N$ - доказва се абсолютно аналогично на горния случай.
До сега намерихме (за 1 случай), че $f(\langle x, 1 \rangle) = \langle y, 1 \rangle$, т.е доказахме, че първата 'част' от множеството $A$ отива във първата част при автоморфизма. Ако разгледаме същите случай за $f(\langle 0, 2 \rangle)$ ще се убедим, че втората 'част' отива във втората. Колко различни автоморфизма се получават по този начин? Както видяхме ако фиксираме нулата на коя да е от частите, останалите елементи се фиксират също. Общо можем по $\omega \times \omega$ начин да изберем 2 точки, в които се изобразяват нулите на 2те части. Т.е това прави $\omega$ на брой автоморфизми във този случай. Очевидно всеки 2 от тях са различни, защото имат по поне един различен елемент (именно нулата на едната от 2те (или и 2те) части).
2. $f(\langle 0, 1 \rangle) = \langle x_0, 2 \rangle \quad x_0 \in \mathbb Z \quad \star\star$.
Ще докажем, че не съществува автоморфизъм $f$, за който е изпълнено $\star\star$.
Със сигурност $f(\langle 0, 2 \rangle) = \langle x_1, 2 \rangle \quad x_1 > x_0$, защото $\langle 0, 2 \rangle > \langle 0, 1 \rangle$. Сега обаче получихме, че между $f(\langle 0, 1 \rangle)$ и $f(\langle 0, 2 \rangle)$ има краен брой елементи (именно $x_1 - x_0 - 1$). Обаче между $\langle 0, 1 \rangle$ и $\langle 0, 2 \rangle$ има $\omega$ на брой елементи. Противоречие!

Така получихме че броя на автоморфизмите в $A$ е точно $\omega$ - т.е изброимо много.

Задача 8

Нека $f, g_1, g_2, \cdots, g_k \in \mathbb Q^\omega$. Казваме, че $f$ е сума на $g_1, g_2, \cdots, g_k$, ако за всяко естествено число $n$ е в сила равенството

(22)
\begin{align} f(n) = g_1(n) + g_2(n) + \cdots + g_k(n) \end{align}

a) Докажете, че за всяка $f \in \mathbb Q^\omega$ съществуват три биекции $g_1, g_2, g_3 \in \mathbb Q^\omega$, такива че $f$ е сума на $g_1, g_2, g_3$.
b) Дайте пример за $f \in \mathbb Q^\omega$, която не може да се получи като сума на 2 биекции $g_1, g_2 \in \mathbb Q^\omega$.

Задача 9

Нека $\alpha$ е ординал. Докажете, че:

(23)
\begin{align} \mathrm{Lim}(\alpha) \iff \alpha = \cup \{ \beta | \beta < \alpha \} \end{align}

Лема 2:

(24)
\begin{align} \alpha = \cup \alpha \iff (x \in \alpha \Rightarrow \mathrm{S}(x) \in \alpha) \end{align}

Доказателство на лемата:
$| \Rightarrow |$ Нека $\alpha = \cup \alpha$. Нека $x \in \alpha$ е произволно. Тогава $x \in \cup \alpha$, т.е съществува елемент $y \in \alpha$, за който е изпълнено $x \in y \in \alpha$. Използваме, че елементите на ординал са пак ординали : $x < y < \alpha$. Сега използваме свойството на ординалите : $x < y \Rightarrow \mathrm{S}(x) \le y$. Така получаваме $\mathrm{S}(x) < \alpha$, което е равносилно на $\mathrm{S}(x) \in \alpha$. Т.е показахме, че $x \in \alpha \Rightarrow \mathrm{S}(x) \in \alpha$.
$| \Leftarrow \subseteq |$ Нека $x \in \alpha \Rightarrow \mathrm{S}(x) \in \alpha$. Нека $a \in \alpha$ е произволен елемент. Тогава $\mathrm{S}(a) \in \alpha$. Получаваме $a \in \mathrm{S}(a) \in \alpha$, следователно $a \in \cup \alpha$.
$| \Leftarrow \supseteq |$ Нека $b \in \cup \alpha$. Тогава съществува елемент $c \in \alpha$, такъв че $b \in c \in \alpha$. Това е равносилно на $b < c < \alpha \Rightarrow b < \alpha$, от където заключваме $b \in \alpha$.

Решение на 9та задача:
$| \Rightarrow |$ Нека $\mathrm{Lim}(\alpha)$ и нека $\beta \in \alpha$. Тогава $\beta < \alpha \Rightarrow \mathrm{S}(\beta) \le \alpha$. Понеже $\alpha$ е гранично, не съществува елемент $x$, за който $\mathrm{S}(x) = \alpha$. Така заключаваме, че $\mathrm{S}(\beta) < \alpha$, т.е че $\mathrm{S}(\beta) \in \alpha$. Получихме, че $\beta \in \alpha \Rightarrow \mathrm{S}(\beta) \in \alpha$. От лемата заключаваме, че $\alpha = \cup \alpha$, но $\alpha = \{ \beta | \beta \in \alpha \} \iff \{ \beta | \beta < \alpha \}$, с което правата посока е доказана!

$| \Leftarrow |$ Нека $\alpha = \cup \{ \beta | \beta < \alpha \} \iff \alpha = \cup \alpha$. Допускаме, че $\lnot \mathrm{Lim}(\alpha)$. Тогава $(\exists \beta)(\mathrm{S}(\beta) = \alpha)$. Но $\beta \in \mathrm{S}(\beta) = \alpha \Rightarrow \beta \in \alpha \overset{\underset{L}{}}\Rightarrow \mathrm{S}(\beta) \in \alpha$. Получихме, че $\mathrm{S}(\beta) = \alpha \And \mathrm{S}(\beta) \in \alpha$. Противоречие! Допуснатото е невярно. Следователно $\mathrm{Lim}(\alpha)$.

Задача 10

С трансфинитна рекурсия дефинираме $V(\alpha)$ така:

(25)
\begin{align} V(\alpha) = \begin{cases} \varnothing & \alpha = 0 \\ \mathcal{P}(V(\beta)) & \mathrm{S}(\beta) = \alpha \\ \cup \{ V(\beta) | \beta < \alpha \} & \mathrm{Lim}(\alpha) \end{cases} \end{align}

Докажете, че:
а) $\mathrm{Trans}(V(\alpha))$
б) $\alpha < \beta \Rightarrow V(\alpha) \subseteq V(\beta)$
в) $\alpha \in V(\mathrm{S}(\alpha))$
г) $\alpha \notin V(\alpha)$

Решение на 10та задача:
а) Ще докажем с използване на трансфинитна индукция.

  • $\alpha = 0$. По дефиниция $V(\alpha) = \varnothing$, което очевидно е транзитивно.
  • $\alpha = \mathrm{S}(\beta)$. Нека $x, y$ са произволни, такива че $x \in y \in V(\alpha) = \mathcal{P}(V(\beta))$. Тогава $x \in y \subseteq V(\beta)$, но $V(\beta) \subseteq \mathcal{P}(V(\beta))$ по дефиницията за транзитивност, т.е $x \in y \subseteq \mathcal{P}(V(\beta)) \Rightarrow x \in \mathcal{P}(V(\beta)) = V(\alpha)$. Т.е доказахме транзитивността на $V(\alpha)$.
  • $\mathrm{Lim}(\alpha)$. Нека $x \in y \in V(\alpha) = \cup \{ V(\beta) | \beta < \alpha \}$. Със сигурност съществува $\beta < \alpha$, такова че $x \in y \in V(\beta)$. Но $V(\beta)$ е транзитивно по индукционната хипотеза, така че $x \in V(\beta)$. Следователно и $x \in \cup \{ V(\beta) | \beta < \alpha \}$. Т.е получихме, че $V(\alpha)$ е транзитивно.

б) Ще докажем с използване на трансфинитна индукция с основа $\alpha$. Т.е ще докажем, че при фиксирано $\alpha$ е вярно, $(\forall \beta > \alpha)(V(\beta) \supseteq V(\alpha))$.

  • $\beta = \alpha$. Тогава очевидно $V(\alpha) = V(\beta) \Rightarrow V(\alpha) \subseteq V(\beta)$
  • $\beta = \mathrm{S}(\gamma) > \alpha$. $V(\alpha) \subseteq V(\gamma) \subseteq \mathcal{P}(V(\gamma)) = V(\beta)$.
  • $\mathrm{Lim}(\beta) \And \beta > \alpha$. $V(\beta) = \cup \{ V(\gamma) | \gamma < \beta \} \And V(\alpha) \subseteq V(\gamma) \subseteq V(\beta)$, за някое $\gamma < \beta$.

в) Ще докажем с трансфинитна индукция по $\alpha$

  • $\alpha = 0 = \varnothing$. Имаме $V(\mathrm{S}(\alpha)) = \mathcal{P}(V(\alpha)) = \mathcal{P}(V(0)) = \mathcal{P}(\varnothing) = \{ \varnothing \}$. Очевидно $\varnothing \in \{ \varnothing \}$, с което базовата стъпка е доказана.
  • $\alpha = \mathrm{S}(\beta)$. Имаме $\beta \in V(\mathrm{S}(\beta))$. От транзитивността получаваме $\beta \subseteq V(\mathrm{S}(\beta))$. Тогава $\mathrm{S}(\beta) = \beta \cup \{ \beta \} \subseteq V(\mathrm{S}(\beta)) \Rightarrow \alpha = \mathrm{S}(\beta) \in \mathcal{P}(V(\mathrm{S}(\beta)) = V(\mathrm{S}(\alpha))$.
  • $\mathrm{Lim}(\alpha)$. Ще докажем, че $\alpha \subseteq V(\alpha)$. Нека $\beta \in \alpha$. Прилагаме индукционната хипотеза, и горното свойство и получаваме $\beta \in V(\mathrm{S}(\beta)) \subseteq V(\alpha)$. Следователно $\alpha \subseteq V(\alpha) \Rightarrow \alpha \in \mathcal{P}(V(\alpha)) = V(\mathrm{S}(\alpha))$.

г) Ще докажем, че ако $\alpha \in V(\alpha)$ то със сигурност съществува по-малко от $\alpha$, за което също е изпълнено.

  • $\exists \beta : \mathrm{S}(\beta) = \alpha$. $\alpha \in V(\alpha) = V(\mathrm{S}(\beta)) = \mathcal{P}(V(\beta))$. Тогава $a \subseteq V(\beta)$. Но $\beta \in \mathrm{S}(\beta) = \alpha$, следователно $\beta \in V(\beta)$
  • $\mathrm{Lim}(\alpha)$. $\alpha \in V(\alpha) = \cup \{ V(\beta) | \beta < \alpha \}$. Тогава съществува $\beta < \alpha : \alpha \in V(\beta)$, от транзитивността $\alpha \subseteq V(\beta)$ и $\beta \in \alpha$, следователно $\beta \in V(\beta)$

Сега остава да допуснем, че съществува $\alpha : \alpha \in V(\alpha)$. Тогава има и най-малко ординално число с това свойство - нека го наречем $\alpha_0$. Според доказаното по-горе или $\alpha_0 = 0$ или противоречие (защото има и по-малко). Но за $\alpha_0 = 0$ очевидно не е изпълнено ($\varnothing \notin \varnothing$), противоречие! Допуснатото е невярно! Следователно $\alpha \notin V(\alpha)$ за всеки ординал $\alpha$.

Задача 11

Докажете, че всяко едно от следващите две твърдения е равносилно с аксиомата за избора.

(26)
\begin{eqnarray} (i) & & \forall R(\mathrm{Rel}(R) \Rightarrow \exists f(\mathrm{Func}(f) \And f \subseteq R \And \mathrm{Dom}(f) = \mathrm{Dom}(R))) \\ (ii) & & \forall f(\mathrm{Func}(f) \Rightarrow \exists g(\mathrm{Rng}(f) = \mathrm{Rng}(g) \And g \subseteq f \And (\forall x \in \mathrm{Dom}(g))(\forall y \in \mathrm{Dom}(g))(x \ne y \Rightarrow g(x) \ne g(y)))) \end{eqnarray}

Решение на 11та задача:
(i) =>| Нека $R$ е релация. От аксиомата за избора съществува функция $f : \mathcal{P}(R) \setminus \{ \varnothing \} \to R$, такава че $C_f (R, f)$.
Нека $\infty \notin R$.
Ще дефинираме с трансфинитна рекурсия множествената операция $F$ по следния начин:

(27)
\begin{align} F(\alpha) = \begin{cases} f(R \upharpoonright (\mathrm{Dom}(R) \setminus \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha)))) & R \upharpoonright (\mathrm{Dom}(R) \setminus \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha))) \ne \varnothing \\ \infty & \mathrm{else} \\ \end{cases} \end{align}

Ще докажем следните свойства за $F$:

  • $\alpha_1 < \alpha_2 \And F(\alpha_2) \ne \infty \Rightarrow F(\alpha_1) \ne \infty$
  • $\alpha_1 < \alpha_2 \And F(\alpha_1) = \langle x_1, y_1 \rangle \And F(\alpha_2) = \langle x_2, y_2 \rangle \Rightarrow x_1 \ne x_2$
  • Нека $\alpha_1 < \alpha_2 \And F(\alpha_2) \ne \infty$. От тук по дефиницията на $F$ получаваме $R \upharpoonright (\mathrm{Dom}(R) \setminus \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha_2))) \ne \varnothing$. Обаче:
(28)
\begin{eqnarray} \alpha_1 &<& \alpha_2 \\ \alpha_1 &\in& \alpha_2 \\ \alpha_1 &\subseteq& \alpha_2 \\ F \upharpoonright \alpha_1 &\subseteq& F \upharpoonright \alpha_2 \\ \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha_1)) &\subseteq& \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha_2)) \\ \mathrm{Dom}(R) \setminus \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha_1)) &\supseteq& \mathrm{Dom}(R) \setminus \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha_2)) \\ R \upharpoonright (\mathrm{Dom}(R) \setminus \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha_1))) &\supseteq& R \upharpoonright (\mathrm{Dom}(R) \setminus \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha_2))) \ne \varnothing \\ \end{eqnarray}

Получихме $R \upharpoonright (\mathrm{Dom}(R) \setminus \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha_1))) \ne \varnothing$. от където и $F(\alpha_1) \ne \infty$.

  • Нека $\alpha_1 < \alpha_2 \And F(\alpha_1) = \langle x_1, y_1 \rangle \And F(\alpha_2) = \langle x_2, y_2 \rangle$. Тогава $F(\alpha_1) = f(R \upharpoonright (\mathrm{Dom}(R) \setminus \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha_1))))$. Тъй като $\alpha_1 < \alpha_2$ имаме, че
(29)
\begin{eqnarray} \langle x_1, y_1 \rangle &\in& \mathrm{Rng}(F \upharpoonright \alpha_2) \\ x_1 &\in& \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha_2)) \\ x_1 &\notin& \mathrm{Dom}(R) \setminus \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha_2)) \\ x_1 &\notin& \mathrm{Dom}(R \upharpoonright (\mathrm{Dom}(R) \setminus \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha_2))) \\ \end{eqnarray}

Но имаме $\langle x_2, y_2 \rangle \in R \upharpoonright (\mathrm{Dom}(R) \setminus \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha_2))$. Тогава със сигурност $x_1 \ne x_2$.

Със сигурност съществува $\alpha : F(\alpha) = \infty$. Иначе излиза че съществува множество $R$, което е изоморфно със всички ординали (което е невъзможно, защото множество на всички ординали не съществува).
Тогава съществува и $\alpha_0 = \mu\alpha[ f(\alpha) = \infty]$. Сега вече според аксиомната схема за замяната $F \upharpoonright \alpha_0$ е функция. Нека я означим със $g$, и нека $\mathrm{Rng}(g) = h$

  • $h \subseteq R$ - очевидно, защото $g(\alpha) = f(R \upharpoonright (\mathrm{Dom}(R) \setminus \mathrm{Dom}(F \upharpoonright \alpha))$, от където $g(\alpha) \in R$.
  • $\mathrm{Func}(h)$ - използваме второто свойство от по-горе и получаваме, че няма двойки от вида $\langle x, y_1 \rangle, \langle x, y_2 \rangle, y_1 \ne y_2$, такива че $\langle x, y_1 \rangle, \langle x, y_2 \rangle \in h$. И понеже е подмножество на релация, получаваме че е функция.
  • $\mathrm{Dom}(h) = \mathrm{Dom}(R)$. Допускаме противното - именно, че съществува $x \in \mathrm{Dom}(R)$, за което $x \notin \mathrm{Dom}(h)$. Но тогава излиза $x \in R \upharpoonright (\mathrm{Dom}(R) \setminus \mathrm{Dom}(\mathrm{Rng}(F \upharpoonright \alpha_0)))$, защото $h = \mathrm{Rng}(F \upharpoonright \alpha_0)$, което противоречи с избора на $\alpha_0$.

(ii) =>| Нека $f$ е функция. И нека $h : \mathcal{P}(f) \setminus \{ \varnothing \} \to f$ е функция за избора на $f$. Нека $\infty \notin f$. Дефинираме формулната операция $F$ със трансфинитна рекурсия по следния начин:

(30)
\begin{eqnarray} X_\alpha &=& \{ \langle x, y \rangle | \langle x, y \rangle \in f \And y \notin \mathrm{Rng}(\mathrm{Rng}(F \upharpoonright \alpha)) \} \\ F(\alpha) &=& \begin{cases} h(X_\alpha) & X_\alpha \neq \varnothing \\ \infty & \mathrm{else} \\ \end{cases} \end{eqnarray}

Ще докажем следните свойства:

  • $\alpha_1 < \alpha_2 \And F(\alpha_2) \neq \infty \Rightarrow F(\alpha_1) \neq \infty$. Нека $\alpha_1 < \alpha_2 \And F(\alpha_2) \neq \infty$, тогава от дефиницията на $F(\alpha_2)$, имаме че $X_{\alpha_2} \neq \varnothing$. Но $\mathrm{Rng}(\mathrm{Rng}(F \upharpoonright \alpha_1)) \subseteq \mathrm{Rng}(\mathrm{Rng}(F \upharpoonright \alpha_2))$, от където $X_{\alpha_2} \subseteq X_{\alpha_1}$, от където очевидно $X_{\alpha_1} \neq \infty$.
  • $\alpha_1 < \alpha_2 \And F(\alpha_1) = \langle x_1, y_1 \rangle \And F(\alpha_2) = \langle x_2, y_2 \rangle \Rightarrow y_1 \neq y_2$. Очевидно, ако $F(\alpha_1) = \langle x_1, y_1 \rangle$, то $y_1 \in \mathrm{Rng}(\mathrm{Rng}(F \upharpoonright \alpha_2))$, от където получаваме, че в $y_1 \notin \mathrm{Rng}(X_{\alpha_2})$, т.е няма как $\mathrm{Snd}(F(\alpha_2)) = y_1$.
  • $\exists \alpha : F(\alpha) = \infty$ - ако не съществува тогава има биекция между $f$ и множеството на всички ординали (което не съществува). Тогава дефинираме $\alpha_0 = \mu\alpha[F(\alpha) = \infty]$, и според аксиомната схема за замяната получаваме $F \upharpoonright \alpha_0$ е функция.
  • $g = \mathrm{Rng}(F \upharpoonright \alpha_0) \subseteq f$. Очевидно $F(\alpha) \in f$ за всяко $\alpha < \alpha_0$, защото $X_\alpha \subseteq f$, а $h$ е функция за избора на $f$.
  • $\mathrm{Func}(g)$. Очевидно от горното свойство.
  • $\mathrm{Rng}(g) = \mathrm{Rng}(f)$. Ако допуснем противното, именно че $\exists y \in \mathrm{Rng}(f) : y \notin \mathrm{Rng}(g)$, тогава излиза, че $\exists u = \langle x, y \rangle \in f \And u \in X_{\alpha_0}$. Противоречие с дефиницията на $\alpha_0$.

Окончателно получихме, че съществува биекция $g$, подфункция на $f$, за която $\mathrm{Rng}(g) = \mathrm{Rng}(f)$.

Сега остава да докажем обратната посока, именно че от (i) и (ii) следва аксиомата за избора.
(i) <=| Нека $A$ е произволно множество. Тогава съществува релацията $R = \{ \langle x, y \rangle | x \in \mathcal{P}(A) \And y \in x \}$. Нека $f$ е такава, че $\mathrm{Func}(f) \And f \subseteq R \And \mathrm{Dom}(f) = \mathrm{Dom}(R)$. Очевидно $f$ е функция на избора за $A$.
(ii) <=| Нека $A$ е произволно множество. Нека $\infty \notin \mathcal{P}(A)$. Дефинираме функцията $f : A \times \mathcal{P}(A) \to \mathcal{P}(A) \cup \{ \infty \} \setminus \{ \varnothing \}$ по следния начин:

(31)
\begin{align} f(\langle x, y \rangle) = \begin{cases} y & x \in y \\ \infty & \mathrm{else} \end{cases} \end{align}

Нека $g$ е биекция, за която $\mathrm{Rng}(g) = \mathrm{Rng}(f)$. Тогава $g^{-1}$ е функция на избора за $A$.

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