Трансверзали на фамилии от множества. Минимални трансверзали

Малко пояснения за по-лесно схващане
Трансверзала (която вече сме учили в стереометрията) е права свързваща две кръстосани прави. Всеки две кръстосани прави имат безброй много трансверзали.
Фамилия от множества е множество съдържащо като елементи други множества, съответно трансверзала на тези множества ще е множество което пресича всяко множество от фамилията.

Дефиниция трансверзала

Нека $\mathfrak{X}$ е фамилия от множества. Казваме, че множеството $X$ е трансверзала за фамилията $\mathfrak{X}$, ако за $(\forall y \in \mathfrak{X})(y \cap X \neq \varnothing)$

НДУ за трансверзали

$\mathfrak{X}$ има трансверзали $\iff (\forall x \in \mathfrak{X})(x \neq \varnothing)$

Доказателство:
$|\Rightarrow|$ Нека $Y$ е трансверзала за $\mathfrak{X}$. Избираме произволен елемент $x \in \mathfrak{X}$ тогава $x \cap Y \neq \varnothing$, в частност $x \neq \varnothing$
$|\Leftarrow|$ Нека $(\forall x \in \mathfrak{X})(x \neq \varnothing)$.
Дефинираме $Y \rightleftharpoons \underset{x \in \mathfrak{X}}{\bigcup}x$.
Твърдим, че $Y$ е трансверзала за $\mathfrak{X}$. Нека $y \in \mathfrak{X}$, тогава $y \subseteqq Y , \ y \cap Y = y \neq \varnothing$ следователно $Y$ е трансверзала.

Минимална трансверзала

Нека $\mathfrak{X}$ е фамилия от множества. За едно множество $Y$ ще казваме, че е минимална трансверзала за $\mathfrak{X}$ ако:

(1) $Y$ е трансверзала за $\mathfrak{X}$
(2') за всяко $a \in Y$ е вярно, че $Y \setminus \{ a\}$ не е трансверзала за $\mathfrak{X}$ (махайки произволен елемент на $Y$ получаваме не-трансверзала)
(2'') за всяко $Y_1 \subset Y, \ Y_1 \neq Y$ множеството $Y_1$ не е трансверзала за $\mathfrak{X}$ (всяко същинско подмножество на $Y$ не е трансверзала)

Както може би се досещате, $\mbox{2}' \iff \mbox{2}''$

Твърдение НДУ за минимална трансверзала

Нека $Y$ е трансверзала за $\mathfrak{X}$, следните две условия са еквивалентни

  1. $Y$ е минимална трансверзала
  2. За всяко $a \in Y , \exists x_a \in \mathfrak{X}$, такова че $x_a \cap Y = \{a\}$

Доказателство:
$1 \Rightarrow 2$
Нека $Y$ e минимална трансверзала за $\mathfrak{X}$. Следователно съществува елемент $x_0 \in \mathfrak{X}$, такъв че $x_0 \cap Y \setminus \{a\} = \varnothing$. Да вземем един такъв елемент1 $x_0$. За него имаме $x_0 \cap Y \neq \varnothing$ следователно $x_0 \cap Y = \{a\}$, тоест $x_a \leftrightharpoons x_0$

$1 \Leftarrow2$
Нека за $\forall a \in Y, \exists x_a \in \mathfrak{X}$, такова че $x_a \cap Y = \{a\}$
Нека $a \in Y$ тогава избираме $x_a \in \mathfrak{X}$, така че $x_a \cap Y = \{a\}$
Да разгледаме $(Y \setminus \{a\}) \cap x_a = \varnothing$ тогава $Y \setminus \{a\}$ не е трансверзала за $\mathfrak{X}$, $a$ e случайно следователно
$Y$ e мин. трансверзала за $\mathfrak{X}$.

Наблюдение (съществуват фамилии без минимална трансверзала)

Въпрос: Съществува ли минимална трансверзала за всяка фамилия от множества $\mathfrak{X}$?
Отговор: Не.
Пример:
$\mathfrak{X} = \{ \{k| n \leq k \}| n \in \mathbb{N} \}$ - на човешки език: $\mathfrak{X} = \{ [0, +\infty), [1, +\infty), \cdots, [n, +\infty), \cdots \}$ (Разглеждаме само интервали от естествени числа, не реални!).
Това $\mathfrak{X}$ няма минимална трансверзала

Доказателство: Да допуснем, че $Y_0$ e мин. трансверзала за $\mathfrak{X}$.
Да разгледаме произволно $a \in Y_0$. За него съществува $x_a \in \mathfrak{X}$, такова че $x_a \cap Y_0 = \{a\}$ (от горното твърдение).
От друга страна, понеже $x_а \in \mathfrak{X}$ знаем, че $x_a = [n_0,+\infty)$, за някое $n_0 \in \mathbb{N}$.

Както виждате $x_a$ съдържа всички естествени числа, по-големи от $n_0$, и даже от $a$. Понеже $x_a \cap Y_0 = \{a\}$, то в $Y_0$ няма по-големи елементи от $a$ - ако имаше те щяха да принадлежат и на $x_a$ и следователно и на сечението им.
Сега тривиално получаваме, че $Y \cap [a+1, +\infty) = \varnothing$, и понеже $[a+1, +\infty) \in \mathfrak{X}$ следователно $Y_0$ не е трансверзала. Противоречие! Следователно не съществува минимална трансверзала за $\mathfrak{X}$.

Теорема за минимална трансверзала

Нека $\mathfrak{X}$ е фамилия от изброимо много крайни непразни множества. Тогава $\mathfrak{X}$ има минимална трансверзала.
Забележка: Теоремата е вярна и за фамилии с по-голяма мощност (от изброима), но не ни достигат знания да го докажем, а и не ни трябва за по-нататък.

Доказателство: Нека $X_0, X_1, X_2, \cdots, X_n, \cdots$ са всички елементи на $\mathfrak{X}$2, и $Y_0 = \bigcup_{i=0}^{\infty} X_i$ е обединението на всички тях. Тогава $Y_0$ е най-много изброимо и нека $x_0, x_1, \cdots, x_n, \cdots$ са неговите елементи (т.е това са всъщност всички елементи на $X_0, X_1, \cdots, X_n, \cdots$ записани в редичка).
С индукция относно $n$ ще дефинираме реда $Y_0, Y_1, \cdots$:
Вече дефинирахме $Y_0$.
Приемаме, че $Y_n$ е дефинирано.
Дефинираме $Y_{n+1}$ по следния начин:

(1)
\begin{align} Y_{n+1} = \begin{cases} Y_n & \mbox{if } Y_n \setminus \{x_n\} \mbox{ is not a transversal for } \mathfrak{X} \\ Y_n \setminus \{x_n\} & \mbox{if } Y_n \setminus \{x_n\} \mbox{ is a transversal for } \mathfrak{X} \end{cases} \end{align}

Грубо казано изхвърляме елементите, които не са критични за трансверзалата - колкото по-нататък се движим по редицата, толкова повече елементи сме изхвърлили (евентуално).
Така получаване редица със следното свойство $Y_0 \supseteqq Y_1 \supseteqq Y_2 \supseteqq \cdots \supseteqq Y_n \supseteqq Y_{n+1} \supseteqq \cdots$ и за всяко $n$ имаме, че $Y_n$ е трансверзала за $\mathfrak{X}$.
Сега си избираме сечението на всички елементи от редицата: $Y \rightleftharpoons \bigcap_{i=0}^{\infty} Y_i$. Твърдим, че $Y$ е мин. трансверзала за $\mathfrak{X}$. Достатъчно е да докажем, че $Y$ е трансверзала за $\mathfrak{X}$ - това, че е минимална следва от построението и сечението на $Y_n$.
Доказателство, че $Y$ е трансверзала за $\mathfrak{X}$:
Нека $X \in \mathfrak{X}$ е произволно. Тогава съществува $n_0 \in \mathbb{N}$, такова че $X = X_{n_0}$ (всички елементи на $\mathfrak{X}$ са номерирани).
$X_{n_0}$ е крайно множество по условие. Нека то е образувано от елементите $\{ x_{n_0^0}, x_{n_0^1}, \cdots, x_{n_0^p} \}$.3. Да си изберем такова $n_1$, че $(\forall i \in \{ 0, 1, \cdots, p\})(n_1 > n_0^i)$. (просто взимаме максимума им и прибавяме единица) - по друг начин казано $(\forall n \ge n_1)(x_n \notin X_{n_0})$.
Сега остава да разгледаме $Y_{n_1}$ - то е трансверзала следователно $Y_{n_1} \cap X_{n_0} \ne \varnothing$, и от друга страна $Y_{n_1} \cap X_{n_0} = Y \cap X_{n_0}$, защото елементите след $Y_{n_1}$ в редицата се различават от $Y_{n_1}$ евентуално от премахване на някои $x_i$, които със сигурност не са от $X_{n_0}$ - на всяка стъпка след $n_1$вата евентуално ще махаме $x$ със индекс по-голям или равен на $n_1$, а индексите на всички $x$ от $X_{n_0}$ бяха по-малки от $n_1$ заради избора на $n_1$.
Следователно доказахме, че $X \cap Y \ne \varnothing$ за произволно $X \in \mathfrak{X}$. Следователно $Y$ е трансверзала за $\mathfrak{X}$.

Теорема за пълнотата на резолютивната изводимост

Нека $S$ е неизпълнимо множество от дизюнкти, тогава $S \overset{r}\vdash \blacksquare$

Доказателство:
Нека $S$ е неизпълнимо. Да допуснем, че $S \nvdash \blacksquare$, следователно $\blacksquare \notin S^*$. Значи всеки елемент $D$ на $S^*$ e крайно непразно множество от литерали.
От теоремата за мин. трансверзали знаем, че $S^*$ има минимална трансверзала. Нека $A$ е минимална трансверзала за $S^*$.
В $A$ не съществува контрарна двойка литерали. Да допуснем, че има - тогава от необходимото условие за мин трансверзала, получаваме, че съществуват $D_1, D_2 \in S^*$, такива че $D_1 \cap A = \{ P \}$ и $D_2 \cap A = \{ \lnot P \}$. Не е трудно да се види, че $D = \mathcal{R}_P(D_1, D_2) \cap A = \varnothing$, и $D \in S^*$, което противоречи на факта, че $A$ е трансверзала.
След като се убедихме, че няма контрарна двойка литерали може да дефинираме булева интерпретация на променливите, която зависи от присъствието им в $A$. По конкретно:

(2)
\begin{align} I(P) = \begin{cases} \mathrm{true} & P \in A \\ \mathrm{false} & P \notin A \\ \end{cases} \end{align}

Т.е даваме положителна стойност на всички литерали без отрицание, участващи в $A$. Сега ще докажем, че $I \models S^*$.
Нека $D \in S^*$ е произволен дизюнкт. Понеже $D \cap A \ne \varnothing$, то съществува поне един литерал $L \in D \cap A$. Да разгледаме два случая за $L$:
(1) $L = P$ - т.е $L$ е съждителна променлива. От дефиницията на $I$ заключаваме, че $I(P) = \mathrm{true}$, следователно и $I \models D$.
(2) $L = \lnot P$ - т.е $L$ е отрицание на съждителна променлива. $\lnot P \in A$, следователно $P \notin A$, т.е $I(P) = \mathrm{false}$, от където $I \models D$.
Както виждате и в двата случая $I \models D$, за произволен дизюнкт $D \in S$.
Доказахме, че $I \models S$. Противоречие - $S$ е неизпълнимо. Следователно $S \overset{r}\vdash \blacksquare$.

Забележка: Всъщност доказахме едната посока на теоремата за пълнота - другата е доказана в предната лекция.

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