Tема 13

Линейни наредби. Операции с линейни наредби.

Свойства на вериги

Да разгледаме частично нареденото множество $\langle C, \subseteq_C \rangle$, където

(1)

\begin{align} C = \{ f | \mathrm{Func}(f) \And \mathrm{Dom}(f) \subseteq A \And \mathrm{Rng}(f) \subseteq B \} \end{align}

Твърдение: Нека $D \subseteq C$ е верига. Т.е $\forall f\forall g(f \in D \And g \in D \Rightarrow f \subseteq g \lor g \subseteq f)$. Тогава тя има горна граница.
Доказателство: Щом $D$ е верига, то за всеки 2 функции $f, g \in D$ имаме

(2)

\begin{align} f \upharpoonright (\mathrm{Dom} f \cap \mathrm{Dom} g) = g \upharpoonright (\mathrm{Dom} f \cap \mathrm{Dom} g) \end{align}

Тогава $D$ е множество от съвместими функции (горното е равносилно на това).
Тогава $\cup D$ е функция. Очевидно $\cup D$ е горна граница за $D$. (може да принадлежи, може и да не принадлежи на $D$).
Нека $D'$ е произволна горна граница на $D$. Тогава $(\forall g \in D)(g \subseteq D')$. Тогава $\cup D \subseteq D'$. От където получихме, че $\cup D$ е най-малката горна граница.

Забележка: Ако $A$ е произволно множество и $\langle A, \subseteq_A \rangle$ е частична наредба. Ако $D$ е верига в $\langle A, \subseteq_A \rangle$, то може $\cup D$ да не принадлежи на $A$.

Пример: Нека $A$ е множеството от всички крайни редици от естествени числа. Тогава веригата $D = \{ \{0\}, \{ 0, 1 \}, \{ 0, 1, 2 \}, \cdots \}$ е такава ,че нейното обединение не е от множеството (защото се получават всички естествени числа, което очевидно не е крайно множество от естествени числа).

Твърдение: Нека $\langle A, R \rangle$ е частично наредено и $C_R = \{ A_0 | A_0 \subseteq A \And A_0$ е верига в $\langle A, R \rangle \}$. Тогава всяка верига в $\langle C_R, \subseteq_{C_R} \rangle$ има супремум, който е верига в $\langle A, R \rangle$ (т.е принадлежи на $C_R$)
Доказателство: Нека $D$ е произволна верига в $\langle C_R, \subseteq_{C_R} \rangle$. Ще докажем, че $\cup D$ е верига в $\langle A, R \rangle$. Нека $x, y \in \cup D$ са произволни. Тогава:

• $\exists d_1 \in D : x \in d_1$
• $\exists d_2 \in D : y \in d_2$

Тъй като $D$ е верига в $C_R$, то $d_1$ и $d_2$ са сравними. Нека Б.О.О. $d_1 \subseteq d_2$. Тогава $x, y \in d_2$. Но $d_2 \in D \subseteq C_R$ от където получаваме, че $d_2$ е верига в $A$. Тогава $x, y$ са $R$ сравними. Така получихме, че всеки 2 елемента на $\cup D$ са $R$ сравними, от където следва, че $\cup D$ е верига в $\langle A, R \rangle$.