Тема 14

Гъсти наредби. Теорема на Кантор за изброимите гъсти линейни наредби. Характеризация на изброимите линейни наредби. Мощност на множеството на линейните наредби на изброимо множество. Вериги от множества от реални числа.

---

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

---

Гъсти линейни наредби

Дефиниция: Казваме, че $\langle A, R \rangle$ е гъсто линейно наредено множество, ако $\langle A, R \rangle$ е линейно наредено (т.е $A$ е верига в $\langle A, R \rangle$) и между всеки 2 елемента може да се намери 3^ти:

(1)

\begin{align} (\forall x, y \in A)(x \ne y \And \langle x, y \rangle \in R \Rightarrow \exists z (x \ne z \And y \ne z \And \langle x, z \rangle \in R \And \langle z, y \rangle \in R)) \end{align}

Дефиниция: Нека $\langle A, R \rangle$ и $\langle B, S \rangle$ са частично наредени множества. Казваме, че те са изоморфни ако:

(2)

\begin{align} \exists f : A \to B : (\forall x, y)(\langle x, y \rangle \in R \iff \langle f(x), f(y) \rangle \in S) \end{align}

Т.е ако съществува биекция, която запазва наредбата. Всяка такава биекция ще наричаме изоморфизъм.

Теорема на Кантор за гъстите линейни наредби

Теорема: Всеки две гъсти линейно наредени множества без най-голям и най-малък елемент са изоморфни.
**Доказателство: Нека $\langle A, R \rangle$ и $\langle B, S \rangle$ са гъсти линейно наредени множества.
Тогава тъй като $A, B$ са изброими можем да номерираме елементите им (обърнете внимание, че номерацията няма нищо общо с наредбата им според $R, S$.

(3)

\begin{eqnarray} A &=& \{ a_0, a_1, a_2, \cdots, a_n, \cdots \} \\ B &=& \{ b_0, b_1, b_2, \cdots, b_n, \cdots \} \end{eqnarray}

Ще построим биекцията $f$ по индукция.
Нека $f_0 : f_0 (a_0) = b_0$. (начало на индукцията).
$2i+1$^ва стъпка: Избираме най-малкия индекс $n_{2i+1}$, такъв че $a_{n_{2i+1}} \notin \mathrm{Dom} f_{2i}$. Избираме най-малкото $m_{2i+1}$, такова че $b_{m_{2i+1}}$ е наредено спрямо $\mathrm{Rng} f_{2i}$ точно както $a_{n_{2i+1}}$ е наредено спрямо $\mathrm{Dom} f_{2i}$. (До момента има избрани точно $2i+1$ числа от 2^те множеста и новото $a_{n_{2i+1}}$ е точно между 2 от вече избраните ($a_x, a_y$) (или е най-малко/голямо от досега избраните). Избираме $b_{m_{2i+1}}$ да е между $f(a_x), f(a_y)$ (или респективно да е най-малкото/голямото от досега избраните). Това е възможно, защото множествата са гъсто наредени, т.е между всеки 2 числа има 3^то). Образуваме $f_{2i+1} = f_{2i} \cup \langle a_{n_{2i+1}}, b_{m_{2i+1}} \rangle$.
$2i+2$^ра стъпка: Избираме най-малкия индекс $n_{2i+2}$, такъв че $b_{n_{2i+2}} \notin \mathrm{Rng} f_{2i+1}$. Избираме най-малкия индекс $m_{2i+2}$ такъв че $a_{m_{2i+2}} \notin \mathrm{Dom} f_{2i+1}$ и е подредено спрямо $\mathrm{Dom} f_{2i+1}$ по същия начин, като $b_{n_{2i+2}}$ е подредено спрямо $\mathrm{Rng} f_{2i+1}$. Образуваме $f_{2i+2} = f_{2i+1} \cup \langle a_{m_{2i+2}}, b_{n_{2i+2}} \rangle$.

По този начин конструирахме $f_0 \subset f_1 \subset f_2 \subset \cdots f_n \subset \cdots$ като за всяко $n \in \mathbb N$ е изпълнено, че $f_n$ е изоморфизъм на $\mathrm{Dom} f_n$ и $\mathrm{Rng} f_n$. (точно заради специалните избори на $m_{2i+1}$ и $m_{2i+2}$). Така получихме че

(4)

\begin{align} f = \bigcup_{n=0}^\infty f_n \end{align}

е биекция между $A, B$ която е и изоморфизъм.

Автоморфизъм

Дефиниция(автоморфизъм): Нека $\langle A, \le \rangle$ е частично наредено множество. Казваме, че $f$ е автоморфизъм за $\langle A, \le \rangle$ ако $f$ е изоморфизъм на $\langle A, \le \rangle$ върху $\langle A, \le \rangle$.

Твърдение: Има поне $\mathcal P(\mathbb N)$ автоморфизма върху $\langle \mathbb Q, \le \rangle$.

Твърдение: Нека $A = \langle \mathcal P (\mathbb N), \subseteq \rangle$. Съществува верига в $A$ с мощност $\mathcal P (\mathbb N)$.
Доказателство: Фиксираме произволна наредба на рационалните числа $\mathbb Q : r_0, r_1, \cdots, r_n, \cdots$.
Нека $\alpha \in \mathbb R$ е произволно реално. Дефинираме $X_\alpha = \{ n | r_n \le \alpha \}$. Тогава $X_\alpha \in \mathcal P (\mathbb N)$.
Ще докажем, че за произволни $\alpha < \beta \quad \alpha, \beta \in \mathbb R$ имаме $X_\alpha \subsetneqq X_\beta$. Със сигурнос съществува рационално число $r$, такова че $\alpha < r < \beta$. Избираме неговия индекс $n_0$ в нашата фиксирана наредба ($r_{n_0} = r$). Сега вече $r_{n_0} \notin X_\alpha \And r_{n_0} \in X_\beta \Rightarrow X_\alpha \neq X_\beta$. От друга страна $\forall r_i \in \mathbb Q : r_i < \alpha \Rightarrow r_i < \beta$. Така получихме, че $X_\alpha \subseteq X_\beta$. Т.е окончателно $\alpha < \beta \Rightarrow X_\alpha \subsetneqq X_\beta$.
Образуваме $C = \{ X_\alpha | \alpha \in \mathbb R \}$. Очевидно това е верига във $A$ и има мощност $\mathbb R \sim \mathcal P (\mathbb N)$

Твърдение: Ще докажем, че всяко отворено множество $A \subseteq \mathbb R$ може да се представи като обединение на отворени, непресичащи се интервали.

Вериги

Нека $x \in A$. Тогава дефинираме следните 2 множества:

(5)

\begin{eqnarray} L_x &=& \{ y | y < x \And y \notin A \} \\ R_x &=& \{ y | y > x \And y \notin A \} \\ \end{eqnarray}

На лице е един от следните 4 случая:

• $L_x = R_x = \varnothing \Rightarrow A = \mathbb R$
• $L_x = \varnothing \And R_x \neq \varnothing$. В такъв случай $R_x$ е ограничено отдолу (от $x$). Нека $\beta = \inf R_x$. Така получихме, че $(-\infty, \beta) \subseteq A$. Допускаме, че $\beta \in A$. Понеже $A$ е отворено, то за всяка точка в него съществува отворена околност $O_\beta \subseteq A$. Но тогава $\forall \beta' > \beta \And \beta' \in O_\beta$ е по-добра долна граница на $R_x$ от $\beta$ (т.е противоречие, че $\beta = \inf R_x$).
• $L_x \neq \varnothing \And R_x = \varnothing$. Аналогично на горния случай получаваме, че $(\alpha, +\infty) \subseteq A \And \alpha \notin A$.
• $L_x \neq \varnothing \And R_x \neq \varnothing$. Тогава $\alpha = \sup L_x \quad \beta = \inf R_x$ и със сигурност $(\alpha, \beta) \subseteq A \And \alpha, \beta \notin A$.

Получихме, че за всяка точка $x$ от $A$ има единствен максимален отворен интервал, който я съдържа. Нека за всяка точка $x$ интервала е $(\alpha_x, \beta_x)$. Образуваме си множество от отворени интервали:

(6)

\begin{align} B = \{ (\alpha_x, \beta_x) | x \in A \} \end{align}

Ще докажем, че:

• $I_1, I_2 \in B \Rightarrow I_1 = I_2 \lor I_1 \cap I_2 = \varnothing$
• $\cup B = A$

Нека $I_1, I_2 \in B \And I_1 \neq I_2$. Допускаме че $\exits x_0 \in I_1 \cap I_2$. Тогава $(\alpha_{x_0}, \beta_{x_0}) = I_1 = I_2$ (това е вярно, защото ако една точка $x$ принадлежи на отворен интервал генериран от друга точка $y$, то генерирания интервал от $x$ съвпада с генерирания интервал от $y$)

Нека $x \in A$, тогава същестува интервал $(\alpha_x, \beta_x) \in B$. Т.е $x \in \cup B$.
Нека $x \in \cup B$, тогава съществува отворен интервал $I \in B : x \in I$. Но $I \subseteq A \Rightarrow x \in A$.

Дефиниция: $x$ е изолирана точка за $A \subseteq \mathbb R$, ако съществува отворена околност $O_x : O_x \cap A = \{ x \}$.
Дефиниция: $d$ е точка на натрупване за $A \subseteq \mathbb R$, ако $(\forall \epsilon > 0)(\overline{\overline{O^\epsilon(d) \cap A}} > \overline{\overline{\omega}})$
Дефиниция: $C$ е съвършенно, ако е затворено и няма изолирани точки.

Лема 0: Всяко неизброимо множество $A \subseteq \mathbb R$ има поне 1 точка на натрупване.
Доказателство: Нека $x_0 \in A$. Ако $x_0$ е точка на натрупване, тогава лемата е доказана. Нека $B = \{ \epsilon | \overline{\overline{O^\epsilon(x_0)}} \cap A \le \overline{\overline{\omega}} \}$. Ако $B = \varnothing$ тогава $x_0$ е точка на натрупване. Ако $B = \mathbb R$ тогава излиза че върху цялата права има не повече от изброимо много точки от $A$, което противоречи с условието, че $A$ е неизброимо. Тогава със сигурност същестува $\epsilon_0 = \sup B$. Ще докажем, че $\epsilon_0 \in B$. Нека $\{ x_i \}_{i=0}^{+\infty}$ е произволна редица, клоняща към $\epsilon_0$ отдолу. Тогава очевидно:

(7)

\begin{align} \overline{\overline{O^{\epsilon_0}(x_0)}} = \overline{\overline{\bigcup_i O^{x_i}(x_0)}} \le \overline{\overline{\omega \times \omega}} = \overline{\overline{\omega}} \end{align}

Нека $a = \sup A \setminus (x_0 - \epsilon_0, +\infty) \quad b = \inf A \setminus (-\infty, x_0+\epsilon_0)$. Допускаме, че и 2те не са точки на сгъстяване. Т.е съществуват околности с големини $\epsilon_0'$ и $\epsilon_0''$ съответно за 2^те точки, в които има не повече от изброимо много елементи на $A$. Тогава обаче получихме, че $O^{\epsilon_0 + \min\{\epsilon_0', \epsilon_0''\}}(x_0) \setminus A \subseteq (O^{\epsilon_0}(x_0) \setminus A) \cup (O^{\epsilon_0'}(a) \setminus A) \cup (O^{\epsilon_0''}(b) \setminus A)$, като последното по мощност е най-много изброимо. Противоречие с $\epsilon_0 = \sup B$.

Лема 1: Нека $A^C$ е множеството от точките на натрупване за $A$. Тогава то е съвършенно.
Доказателство: Първо ще докажем, че $A^C$ е затворено. Нека $a \in A \And a \notin A^C$. Тогава съществува околност $O_a$ в която има най-много изброимо много елементи на $A$. Очевидно всички тези елементи не са точки на натрупване, защото в техни достатъчно малки околности (влизащи в $O_a$ има най-много изброимо много елементи на $A$. Така получихме, че за всяка точка вън от $A^C$ има отворена околност, която също е вън от $A^C$.
Ще докажем, че в $A^C$ няма изолирани точки. Допускаме че има изолирана точка $x_0$. Тогава съществува околност $O_{x_0} : O_{x_0} \cap A^C = \{ x_0 \}$. $x_0$ е точка на натрупване за $A$ (защото принадлежи на $A^C$), следователно във всяка нейна околност има неизброимо много точки на $A$. Да разгледаме по-подробно околността $O_{x_0}$. В нея има неизброимо много точки от $A$. Следователно във $O_{x_0} \setminus x_0$ също има неизброимо много точки от $A$. От Лема 0 получаваме, че в нея има точка на натрупване $x_1$. Противоречие с допускането, че $x_0$ е изолирана точка.
Лема 2: $A \setminus A^C$ е най-много изброимо.
Доказателство: Допускаме, че $A \setminus A^C$ е неизброимо. Тогава според Лема 0 в него има поне 1 точка на натрупване. Противоречие - в $A^C$ са всички точки на натрупване на $A$.

Теорема: Нека $A$ е затворено множество в $\mathbb R$. Тогава съществува единствена двойка множества $C, B$ такива че

• $B \cap C = \varnothing$
• $A = C \cup B$
• $C$ е съвършенно
• $B$ е най-много изброимо

Доказателство: Полагаме $C = A^C$ и $B = A \setminus C$. Според Лема 1 $C$ е съвършенно и според Лема 2 $B$ е най-много изброимо.

Изоморфно влагане

Дефиниция: $f$ е изоморфно влагане на $\langle A, \le \rangle$ в $\langle B, \preccurlyeq \rangle$, ако $f$ е изоморфизъм на $\langle A, \le \rangle$ и $\langle C \subseteq B, \preccurlyeq \cap (C \times C) \rangle$ (т.е има инекция от $A$ към $B$, която запазва сравнението).

Твърдение: Нека $\langle A, \le \rangle$ е частично наредено множество. Тогава съществува изоморфно влагане на $\langle A, \le \rangle$ във $\langle \mathcal P(A), \subseteq \rangle$. (по този начин показваме, че всяка частична наредба може да се представи единствено с теоретико множествената операция 'е подмножество на'))
Доказателство: Избираме $f : A \to \mathcal P(A)$, така че

(8)

\begin{align} f(a) = \{ b | b \le a \} \end{align}

После доказваме, че тази функция запазва сравнението (т.е $a \le b \iff f(a) \subseteq f(b)$)

Решетки

Дефиниция(горна полу-решетка): Нека $\langle A, \le \rangle$ е частично наредено множество. Казваме, че $\langle A, \le \rangle$ е горна полу-решетка, ако $(\forall a, b \in A)(\exists c(c = \sup \{ a, b \})$.
Казваме, че горната решетка на $\langle A, \le \rangle$ е с единица, ако съществува $\sup A$.

Забележка: $\sup$ е просто някаква функция, която работи над множества. $\sup \{ a, b \}$ може да бъде записано и като $a \sqcup b$.
Необходими условия за $\sup$:

1. $\sup \{ a, a \} = a$ - идемпотентност
2. $\sup \{ a, b \} = \sup \{b , a \}$ - комутативност
3. $\sup \{ a, \sup \{ b, c \} \} = \sup \{ \sup \{ a, b \}, c \}$ - асоциативност
4. * $\sup \{ a, 1 \} = 1$ - единица на оператора (* - само, ако полурешетката е с единица)

Нека $\langle A, \sqcup \rangle$ удовлетворява 3^те условия. Тогава $\langle A, \le \rangle$ може да бъде дефинирано: $a \le b \leftrightharpoons a \sqcup b = b$
Доказва се, че така дефинирания оператор $\le$ е рефлексивен, комутативен и транзитивен (като се иползват свойствата на $\sup$).

Дефиниция: $A$ е долна полу-решетка, ако $(\forall a, b \in A)(\exists c(c = \inf \{ a, b \}))$.
Полурешетката е с нула, ако $\exists \inf A$.
Ще записваме $\inf \{ a, b \}$ или еквивалентното му $a \sqcap b$.
Необходими условия за $\inf$:

1. $\inf \{ a, a \} = a$ - идемпотентност
2. $\inf \{ a, b \} = \inf \{ b, a \}$ - комутативност
3. $\inf \{ a, \inf \{ b, c \} \} = \inf \{ \inf \{ a, b \}, c \}$ - асоциативност
4. * $\inf \{ 0, a \} = 0$ - нула на оператора (* - само ако полурешетката е с нула)

Дефиниция: Казваме, че $A$ е решетка ако е едновременно гора и долна полурешетка.
Необходими условия за $\langle A, \sqcup, \sqcap \rangle$:

1. 3те свойства на $\sup$
2. 3те свойства на $\inf$
3. $a \sqcap (a \sqcup b) = a$
4. $a \sqcup (a \sqcap b) = a$

Сума и произведение на частично наредени множества

Дефиниция: Нека $\langle A_1, \le_1 \rangle$ и $\langle A_2, \le_2 \rangle$ са частично наредени множества.
Нека $A_1' = A_1 \times \{ 1 \}$ и $A_2' = A_2 \times \{ 2 \}$. Също така полагаме:

(9)

\begin{align} \langle x, i \rangle \le \langle y, j \rangle \leftrightharpoons \begin{cases} x \le_1 y & i = j = 1 \\ x \le_2 y & i = j = 2 \\ x = x & i = 1\ j = 2 \\ x \ne x & i = 2 \ j = 1 \end{cases} \end{align}

Твърдение: Ако сумираме две линейно наредени множества получаваме линейно наредено
Твърдение: Ако сумираме две гъсти линейно наредени множества без пръв и последен елемент получаваме гъсто линейно наредено множество без пръв и последен елемент.

Твърдение: Нека $\langle L, \succurlyeq \rangle$ е изброимо линейно наредено множество. Тогава $\langle L, \succurlyeq \rangle$ е изоморфно вложимо във $\langle \mathbb Q, \le \rangle$.
Идея: Заместете всеки елемент от $L$ със копие на $\mathbb Q$.

Дефиниция(покоординатно умножение): Нека $\langle A_1, \le_1 \rangle$ и $\langle A_2, \le_2 \rangle$ са частично наредени множества. Тогава дефинираме $A_1 \otimes_k A_2 = \langle A_1 \times A_2, \le_k \rangle$, където

(10)

\begin{align} \langle x_1, y_1 \rangle \le_k \langle x_2, y_2 \rangle \leftrightharpoons x_1 \le_1 x_2 \And y_1 \le_2 y_2 \end{align}

Дефиниция(лексикографско произведение): Същото като покоординатно произведени, но новия оператор за сравнение се дефинира така:

(11)

\begin{align} \langle x_1, y_1 \rangle \le_l \langle x_2, y_2 \rangle \leftrightharpoons (x_1 \ne x_2 \And x_1 \le_1 x_2) \lor (x_1 = x_2 \And y_1 \le_2 y_2) \end{align}

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