Тема 12

Частични наредби и морфизми между тях. Представимост на наредби чрез теоретико-множествено включване.

Частични наредби

Дефиниция: $R$ е бинарна релация върху $A$ ако $R \subseteq A \times A$.

Дефиниция: $R$ е рефлексивна бинарна релация върху $A$, ако $\forall x(x \in A \Rightarrow \langle x, x \rangle \in R)$ ($\iff \mathrm{Id}_A \subseteq R$)

Дефиниция: $R$ е иррефлексивна бинарна релация върху $A$, ако $\forall x(x \in A \Rightarrow \langle x, x \rangle \notin R)$. ($\iff \mathrm{Id}_A \cap R = \varnothing$)

Дефиниция: $R$ е антисиметрична бинарна релация ако $\forall x\forall y(\langle x, y \rangle \in R \And \langle y, x \rangle \in R \Rightarrow x = y)$. ($\iff R \cap R^{-1} \subseteq \mathrm{Id}_A$)

Дефиниция: $R$ е асиметрична бинарна релация ако $\forall x\forall y(\langle x, y \rangle \in R \Rightarrow \langle y, x \rangle \notin R)$. ($\iff R \cap R^{-1} = \varnothing$)

Дефиниция: $R$ е транзитивна бинарна релация ако $\forall x\forall y\forall z(\langle x, y \rangle \in R \And \langle y, z \rangle \in R \Rightarrow \langle x, z \rangle \in R$. ($\iff R \circ R \subseteq R$)

Дефиниция: $R$ е частична наредба върху $A$, ако е рефлексивна, антисиметрична и транзитивна.

Дефиниция: $\langle A, R \rangle$ е частично наредено множество ако $R$ е частична наредба върху $A$.

Дефиниция: $\langle A, R \rangle$ е частично наредено множество, то казваме, че $x$ и $y$ са $R$-сравними, ако $\langle x, y \rangle \in R \lor \langle y, x \rangle \in R$.

Дефиниция: $\langle A, R \rangle$ е частично наредено множество и $A_1 \subseteq A$. Тогава $\langle A_1, R \cap (A_1 \times A_1) \rangle$ наричаме индуцирана частична наредба.

Твърдение: Ако $\langle A, R \rangle$ е частично наредено множество, то $\langle A, R^{-1} \rangle$ е частично наредено множество. (обратна наредба).

Дефиниция: $\langle A, R \rangle$ е линейно наредено множество, ако $\langle A, R \rangle$ е частично наредено множество, и всеки 2 елемента от $A$, са $R$-сравними.

Дефиниция: $\langle A, R \rangle$ е частично наредено множество, то $\langle A, R \setminus \mathrm{Id}_A \rangle$ е строга частична наредба.

Твърдение: Ако $R$ е антисиметрична, тогава $R \setminus \mathrm{Id}_{\mathrm{Fld}(R)}$ е асиметрична.

Твърдение: Ако $R$ е асиметрична, тогава $R$ е иррефлексивна.

Твърдение: $\langle A, R \rangle$ е строго частично наредено множество, т.с.т.к. $R$ е асиметрична и транзитивна.
Доказателство:
Права посока: По дефиниция за пълна частична наредба съществува $\langle A, R' \rangle$ - частична наредба и $R = R' \setminus \mathrm{Id}_A$.
$R'$ е антисиметрична, следователно $R$ е асиметрична.
Ще докажем, че $R$ е транзитивна.
Нека $\langle x, y \rangle \in R \And \langle y, z \rangle \in R$. Aко $(x = y) \lor (y = z)$ тривиално получаваме $\langle x, z \rangle \in R$. Иначе $\langle x, y \rangle \in R' \And \langle y, z \rangle \in R'$. Сега според транзитивността на $R'$ получаваме $\langle x, z \rangle \in R'$. Допускаме, че $x = z$. Тогава $\langle x, y \rangle \in R \And \langle y, x \rangle \in R$. Противоречие - $R$ е асиметрична. Така окончателно $\langle x, z \rangle \in R$, с което показахме, че $R$ е транзитивна.
Обратна посока: Нека $R$ е асиметрична и транзитивна.
Тогава $R' = R \cup \mathrm{Id}_A$ а антисиметрична.
Ще докажем, че $R'$ е транзитивна. Нека $\langle x, y \rangle \in R' \And \langle y, z \rangle \in R'$. Tогава:

  • $\langle x, y \rangle, \langle y, z \rangle \in R$, от където $\langle x, z \rangle \in R \subseteq R'$.
  • $\langle x, y \rangle, \langle y, z \rangle \in \mathrm{Id}_A$, от където $x = y = z$ следователно $\langle x, z \rangle \in \mathrm{Id}_A \subseteq R'$
  • $\langle x, y \rangle \in R \And \langle y, z \rangle \in \mathrm{Id}_A$, тогава $y = z$ следователно $\langle x, y \rangle = \langle x, z \rangle \in R \subseteq R'$

С което доказахме, че $R'$ е транзитивна.
Освен това $R = R' \setminus \mathrm{Id}_A = (R \cup \mathrm{Id}_A) \setminus \mathrm{Id}_A$ заради $R \cap \mathrm{Id}_A = \varnothing$, с което показахме, че $R$ е частична наредба.

Твърдение: Ако $\langle A, R \rangle$ е частично наредено множество (строго), то $\langle A, R^{-1} \rangle$ е частично наредено множество (строго).
Доказателство:
Нека $\langle A, R \rangle$ е частично наредено.

  • $\mathrm{Id}_A \subseteq R$, тогава ${\mathrm{Id}_A}^{-1} \subseteq R^{-1}$, т.e $\mathrm{Id}_A \subseteq R^{-1}$ следва $R^{-1}$ е рефлексивна.
  • $R \cap R^{-1} \subseteq \mathrm{Id}_A$, тогава $R^{-1} \cap R \subseteq \mathrm{Id}_A$, следователно $R^{-1}$ е антисиметрична.
  • $R \circ R \subseteq R$, тогава $(R \circ R)^{-1} \subseteq R^{-1}$, следователно $R^{-1} \circ R^{-1} \subseteq R^{-1}$, следователно $R^{-1}$ е транзитивна.

Твърдение: $\langle A, R \rangle$ е частична наредба (строга) и $B \subseteq A$, то индуцираната $\langle B, R \cap (B \times B) \rangle$ е частична наредба (строга).

Дефиниции: За следващите дефиниции приемаме, че $\langle A , R \rangle$ е частична наредба, $A_0 \subseteq A$.

  • $a_0$ е горна граница на $A_0$ в $\langle A, R \rangle$ ако $\forall x (x \in A_0 \Rightarrow \langle x, a_0 \rangle \in R)$.
  • $a_0$ е долна граница на $A_0$ в $\langle A, R \rangle$ ако $a_0$ е горна граница на $A_0$ в $\langle A, R^{-1} \rangle$.
  • $A_0$ е ограничено отгоре в $\langle A, R \rangle$, ако съществува $a_0$, което е горна граница на $A_0$ в $\langle A, R \rangle$.
  • $A_0$ е ограничено отдолу в $\langle A, R \rangle$, aко $A_0$ е ограничено отгоре в $\langle A, R^{-1} \rangle$.
  • $a_0$ е най-голям елемент на $A_0$ в $\langle A, R \rangle$, ако $a_0 \in A$ и $a_0$ е горна граница на $A_0$ в $\langle A, R \rangle$.
  • $a_0$ е най-малък елемент на $A_0$ в $\langle A, R \rangle$, ако $a_0$ е най-голям елемент на $A_0$ в $\langle A, R^{-1} \rangle$
  • $a_0$ е точна горна граница на $A_0$ в $\langle A, R \rangle$, ако $a_0$ е горна граница на $A_0$ и $a_0$ е най-малък елемент в множеството от горните граници за $A_0$ в $\langle A, R \rangle$. Записваме $a_0 = \underset{\overset{R}{}}\sup A_0$.
  • $a_0$ е точна долна граница на $A_0$ в $\langle A, R \rangle$, ако $a_0$ е точна горна граница на $A_0$ в $\langle A, R^{-1} \rangle$. Записваме $a_0 = \underset{\overset{R}{}}\inf A_0$
  • $a_0$ е max елемент в $\langle A, R \rangle$, ако $a_0 \in A \And \lnot \exists a( a \ne a_0 \And \langle a_0, a \rangle \in R)$ - т.е няма елемент по-голям от $a_0$.
  • $a_0$ e min елемент в $\langle A, R \rangle$, aко е max елемент във $\langle A, R^{-1} \rangle$

Дефиниция: $R$ е частична наредба. $x \le y \leftrightharpoons \langle x, y \rangle \in R$.

Наредби чрез включване

Да разгледаме $\langle A, \subseteq \cap (A \times A) \rangle$. Т.е. $x, y \in A$ са в релация $\subseteq \cap (A \times A)$, когато $x \subseteq y$.
За краткост ще записваме $\subseteq \cap A$ като $\subseteq_A$.

Дефиниция: Ако $\langle A, R \rangle$ е частично наредено множество, то казваме, че $B \subseteq A$ е верига, ако $\langle B, R \cap (B \times B) \rangle$ е линейна наредба.

Да разгледаме частично нареденото множество $\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}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License