Теория на Множествата - Тема 4

Наредени двойки. Релации. Алгебра на релациите

Наредена двойка

Ще ги бележим със $\langle x, y \rangle$. Но какво всъщност са наредените двойки? Ами това е обект, съставен от два други, като единият от двата е по-специален от другия, защото е на първо място. Другояче казано единственото условие, което трябва да изпълнява една наредена двойка, за да е такава е:

(1)
\begin{align} \langle x, y \rangle = \langle x', y' \rangle \iff x = x' \And y = y' \quad \star \end{align}

Сега ще дефинираме наредена двойка като специално множество. Все пак в теория на множествата няма нищо друго, така че нямаме голям избор.
Дефиниция0(наредена двойка): $\langle x, y \rangle \rightleftharpoons \{ \{ x, \varnothing \}, \{ y, \{ \varnothing \} \}\}$
Дефиниция1(деф на Куратовски): $\langle x, y \rangle \rightleftharpoons \{ \{x\}, \{ x, y \} \}$
Твърдение: Дефиницията на Куратовски удовлетворява условие $\star$
Доказателство:
Обратна посока: Нека $x = x'$ и $y = y'$. Ще докажем, че $\langle x, y \rangle = \langle x', y' \rangle$.
Очевидно $x = x' \Rightarrow \{x\} = \{ x' \}$ и $x = x' \Rightarrow \{x, y\} = \{ x', y \}$. $y = y' \Rightarrow \{ x', y \} = \{x', y'\}$.
Тогава $\langle x, y \rangle = \{ \{x\}, \{ x, y \} \} = \{ \{ x' \}, \{x', y\}\} = \{ \{ x'\}, \{ x', y' \}\} = \langle x', y' \rangle$.
Права посока: Нека $\langle x, y \rangle = \langle x', y' \rangle$. Ще докажем, че $x = x'$ и $y = y'$.
$\{\{x\}, \{x, y\}\} = \{ \{x'\}, \{ x', y' \}\}$. От тук $\{ x \} \in \{\{x\}, \{x, y\}\} \Rightarrow \{x\} \in \{ \{x'\}, \{ x', y' \}\}$. Ще разгледаме 2 случая:
1 сл) $\{x\} = \{x'\}$. От тук веднага получаваме, че $x = x'$, откъдето $\{ x', y' \} = \{ x, y'\}$.
$\{\{x\}, \{x, y\}\} = \{ \{x'\}, \{ x', y' \}\} = \{ \{x\}, \{x, y'\} \} \Rightarrow \{ x, y'\} = \{x, y\} \Rightarrow y = y'$.1
2 сл) $\{x\} = \{x', y'\}$. Тогава $x' \in \{ x', y' \} \Rightarrow x' \in \{ x \} \Rightarrow x = x'$. Тогава от първи случай пак $y = y'$.

Забележка: Ще работим със дефиницията на Куратовски. Другата върши същата работа, може да си докажете свойството и за нея.

Свойства:

  • $\cup \langle x, y \rangle = \{ x, y \}$
  • $\cup\cup \langle x, y \rangle = x \cup y$
  • $\langle x, y \rangle \in \mathcal{P}(\mathcal{P}(\{x, y\}))$

Теоретико множествено свойство за наредена двойка: $\mathrm{OrPr}(u) \rightleftharpoons \exists x\exists y(u = \langle x, y \rangle)$. (вероятно Ordered Pair)

Декартово произведение

Дефиниция:

(2)
\begin{align} A \times B \leftrightharpoons \{ u | u \in \mathcal{P}(\mathcal{P}(\{x, y\})) \And \exists x\exists y(u = \langle x, y \rangle \And x \in A \And y \in B ) \} \end{align}

Свойства:

  • $\varnothing \times A = \varnothing$
  • $A \times \varnothing = \varnothing$
  • $A \times B \ne B \times A$ - поне не в общия случай
  • $A \times (B \times C) \ne (A \times B) \times C$ - наредените двойки са различни
  • $A \times (B \cup C) = (A \times B) \cup (A \times C)$
  • $A \times (B \cap C) = (A \times B) \cap (A \times C)$

Докажете ги сами за упражнение

Бинарна релация

Дефиниция:
Казваме, че едно множество е бинарна релация, ако всеки един негов елемент е наредена двойка.

(3)
\begin{align} \mathrm{Rel}(A) \leftrightharpoons \forall x(x \in A \Rightarrow \mathrm{OrPr}(x)) \end{align}

Дефиниция(дефиниционно множество): $\mathrm{Dom}(A) \leftrightharpoons \{ x | x \in \cup\cup A \And \exists y(\langle x, y \rangle \in A) \}$

Дефиниция(област от стойности): $\mathrm{Rng}(A) \leftrightharpoons \{ y | y \in \cup\cup A \And \exists x (\langle x, y \rangle \in A) \}$

Твърдение: Ако $A$ е бинарна релация, то $A \subseteq \mathrm{Dom}(A) \times \mathrm{Rng}(A)$
Доказателство: Нека $u \in A$. Тогава $u = \langle x,y \rangle$, където $x \in \mathrm{Dom}(A) \And y \in \mathrm{Rng}(A)$. Следователно $u \in \mathrm{Dom}(A) \times \mathrm{Rng}(A)$

Свойства:
Ако $A_1, A_2$ са бинарни релации, то:

  • $\mathrm{Rel}(A_1 \cup A_2)$
  • $\mathrm{Rel}(A_1 \cap A_2)$
  • $\mathrm{Rel}(A_1 \setminus A_2)$

Дефиниция:(обръщане на релацията):
Нека $A$ е бинарна релация. Тогава $A^{-1} = \{ \langle x, y \rangle | \langle y, x \rangle \in A \}$ също е бинарна релация.
Свойства:

  • $(A^{-1})^{-1} = A$
  • $(A_1 \cup A_2)^{-1} = A_1^{-1} \cup A_2^{-1}$
  • $(A_1 \cap A_2)^{-1} = A_1^{-1} \cap A_2^{-1}$
  • $(A_1 \setminus A_2)^{-1} = A_1^{-1} \setminus A_2^{-1}$

Дефиниция:(композиция на бинарни релации):
Нека $\mathrm{Rel}(A) \And \mathrm{Rel}(B)$. Тогава $A \circ B \rightleftharpoons \{ \langle x, y \rangle | \exists z ( \langle x, z \rangle \in A \And \langle z, y \rangle \in B) \}$

Свойства:

  • $A_1 \circ A_2 \ne A_2 \circ A_1$
  • $A_1 \circ (A_2 \circ A_3) = (A_1 \circ A_2) \circ A_3$
  • $A \circ (B_1 \cup B_2) = (A \circ B_1) \cup (A \circ B_2)$
  • $A \circ (B_1 \cap B_2) \subseteq (A \circ B_1) \cap (A \circ B_2)$
  • $A \circ (B_1 \setminus B_2) \subseteq (A \circ B_1) \setminus (A \circ B_2)$
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License