Matematyka dyskretna 2/Ćwiczenia 2: Porządki Częściowe i twierdzenie Dilworth'a

Porządki częściowe

Ćwiczenie 1

Niech $\mathbf{𝐓}=(V,E)$ będzie drzewem z wyróżnionym elementem $r\in V$ . Pokaż, że definiując dla $v,w\in V$ :

$v\le w$ wtedy i tylko wtedy, gdy ścieżka z $w$ do $r$ odwiedza wierzchołek $v$,

otrzymana para $(V,\le )$ jest zbiorem częściowo uporządkowanym.

Wskazówka

Sprawdź zwrotność, antysymetrię i przechodniość zdefiniowanej relacji.

Rozwiązanie

Sprawdzamy po kolei warunki na to, aby $(V,\le )$ był zbiorem częściowo uporządkowanym:

• zwrotość:

Każda ścieżka z $w$ do $r$ oczywiście odwiedza swój początek, czyli $w$ .

• antysymetria:

Załóżmy, że dla dwu różnych wierzchołków $v,w$ , wierzchołek $w$ leży na ścieżce z $v$ do $r$ oraz $v$ leży na ścieżce z $w$ do $r$ . Mamy więc dwie ścieżki:

$\begin{array}{rlr}& & w\to \dots \to v\to \dots \to r,\\ & & v\to \dots \to w\to \dots \to r.\end{array}$

Między dwoma wierzchołkami drzewa istnieje dokładnie jedna ścieżka. Idąc więc pierwszą z tych ścieżek z $w$ do $r$ dojdziemy do $v$ , co wobec jedyności, zmusza do przejścia później drugą ścieżką, czyli przez $w$ . Na ścieżce punkty nie mogą sie jednak powtarzać.

• przechodniość:

Załóżmy, że $u\le v$ oraz $v\le w$ , tzn. $u$ leży na jedynej ścieżce z $v$ do $r$ , a $v$ na jedynej ścieżce z $w$ do $r$ . Z jedyności ścieżek dostajemy, że fragment od $v$ do $r$ ścieżki z $w$ do $r$ , odwiedza $u$ .

Ćwiczenie 2

Pokaż, że elementy $p_1,p_2,\dots ,p_k\in P$ zbioru częściowo uporządkowanego $(P,\le )$ spełniające $p_1\le p_2\le \dots \le p_k\le p_1$ muszą być równe.

Wskazówka

Przeprowadź dowód indukcyjny ze względu na $k$ .

Rozwiązanie

Rozumowanie przeprowadzimy indukcyjnie ze względu na $k$ . Dla $k=1$ jest to oczywiste. Podobnie, gdy $p_1\le p_2\le p_1$ , to antysymetria daje $p_1=p_2$ . Niech więc $k>2$ . Nierówność $p_{k-1}\le p_k\le p_1$ daje $p_{k-1}\le p_1$ , co pozwala skrócić wyjściowy ciąg nierówności

$p_1\le p_2\le \dots \le p_k\le p_1$

do

$p_1\le p_2\le \dots \le p_{k-1}\le p_1$,

i z założenia indukcyjnego dostać

$p_1=p_2=\dots =p_{k-1}$

Jedyna brakująca równość $p_1=p_k$ wynika z $p_1=p_{k-1}\le p_k\le p_1$ .

Ćwiczenie 3

Korzystając z Twierdzenia Dilworth'a 2.1 pokaż, że każdy zbiór częściowo uporządkowany o $rs+1$ elementach zawiera łańcuch o liczności $r+1$ lub antyłańcuch o liczności $s+1$ .

Wskazówka

Rozumowanie jest analogiczne do użytego w wyprowadzaniu tego faktu z Dualnego Twierdzenia Dilworth'a.

Rozwiązanie

Niech $\mathbf{𝐏}=(P,\le )$ będzie posetem, w którym każdy łańcuch jest liczności co najwyżej $r$ , a każdy antyłańcuch jest liczności co najwyżej $s$ . Twierdzenie Dilworth'a 2.1 dostarcza pokrycia łańcuchami

$P=C_1\cup \dots \cup C_{s^{\prime }}$,

gdzie $s^{\prime }\le s$ jest mocą łańcucha o maksymalnej liczności. Ponieważ $\left|C_i\right|\le r$ , to

$\left|P\right|=\left|C_1\right|+\dots +\left|C_{s^{\prime }}\right|\le r{s}^{\prime }\le rs$

Sprzeczność ta pokazuje, że jeśli $\mathbf{𝐏}$ ma co najmniej $rs+1$ elementów, to musi zawierać łańcuch o liczności $r+1$ lub antyłańcuch o liczności $s+1$ .

Ćwiczenie 4

Pokaż, że dla zbioru częściowo uporządkowanego $\mathbf{𝐏}=(P,\le )$ , rodzina ${ℳ}{𝒜}\left(\mathbf{𝐏}\right)$ antyłańcuchów zbioru $\mathbf{𝐏}$ o maksymalnej liczności wraz z relacją zdefiniowaną poprzez:

$A\le B$ wtedy i tylko wtedy, gdy każdy element $b\in B$ leży nad jakimś elementem $a\in A$ ,

tworzy kratę.

Wskazówka

Dla $A,B\in {ℳ}{𝒜}\left(\mathbf{𝐏}\right)$ zbiór elementów maksymalnych w $A\cup B$ jest kresem górnym $A,B$ , a zbiór elementów minimalnych w $A\cup B$ jest kresem dolnym $A,B$ .

Rozwiązanie

By skrócić zapisy niektórych wypowiedzi, dla podzbioru $X\subseteq P$ zbioru częściowo uporządkowanego $\mathbf{𝐏}=(P,\le )$ definiujemy stożek górny oraz stożek dolny zbioru $X$ odpowiednio jako

$\begin{array}{rl}X\Uparrow & =\{p\in P:\text{ istnieje }x\in X\text{ taki, że }x\le p\},\\ X\Downarrow & =\{p\in P:\text{ istnieje }x\in X\text{ taki, że }p\le x\}.\end{array}$

A zatem definicję relacji $\le$ w zbiorze ${ℳ}{𝒜}\left(\mathbf{𝐏}\right)$ możemy przeformułować następująco:

$A\le B$ wtedy i tylko wtedy, gdy $B\subseteq A\Uparrow$ .

Zauważmy też, że

• dla antyłańcuchów $X,Y\subseteq P$ , jeśli $X\subseteq Y\Uparrow$ , to także $X\Uparrow \subseteq Y\Uparrow$ .

Istotnie, niech $p\in X\Uparrow$ , tzn. $x\le p$ dla pewnego $x\in X$ . Ale wobec $x\in X\subseteq Y\Uparrow$ wiemy, że istnieje $y\in Y$ takie, że $y\le x$ . A zatem $p\ge y\in Y$ , czyli $p\in Y\Uparrow$ .

• gdy $X$ jest antyłańcuchem, to $X$ składa się, że wszystkich elementów minimalnych stożka $X\Uparrow$ .
• dla antyłańcuchów $X,Y\subseteq {ℳ}{𝒜}\left(\mathbf{𝐏}\right)$ spełniających $X\subseteq Y\Uparrow$ zachodzi też $Y\subseteq X\Downarrow$ .

Dla dowodu niewprost, niech $y\in Y-X\Downarrow$ . Oznacza to, że nie istnieje $x\in X$ taki, że $y\le x$ . W przypadku, gdy $y$ byłby nieporównywalny z żadnym elementem z $X$ , to $X\cup \left\{y\right\}$ byłby antyłańcuchem, i to większym od antyłańcucha $X$ , wbrew temu, że $X$ jest najbardziej liczny. Musi więc istnieć $x_0\in X$ takie, że $x_0\le y$ . Ale teraz $x_0\in X\subseteq Y\Uparrow$ oznacza, że $x_0\ge y_0$ dla pewnego $y_0\in Y$ . Mamy więc $y_0\le x_0\le y$ dla dwu elementów $y_0,y$ antyłańcucha $Y$ , czyli $y=y_0\le x$ . To jednak daje $y\in X\Downarrow$ , wbrew założeniu o $y$ .

Pokażemy najpierw, że $({ℳ}{𝒜}\left(\mathbf{𝐏}\right),\le )$ jest częściowym porządkiem. Tak więc kolejno sprawdzamy warunki:

• zwrotność:

Ponieważ $A\subseteq A\Uparrow$ , to $A\le A$ .

• antysymetria:

Niech teraz $A,B\in {ℳ}{𝒜}\left(\mathbf{𝐏}\right)$ spełniają $A\subseteq B\Uparrow$ i $B\subseteq A\Uparrow$ . Wtedy $A\Uparrow \subseteq B\Uparrow$ , więc i zbiory $A,B$ muszą być równe, jako zbiory elementów minimalnych odpowiednio w $A\Uparrow$ i $B\Uparrow$ .

• przechodniość:

Niech $A,B,C\in {ℳ}{𝒜}\left(\mathbf{𝐏}\right)$ spełniają $A\subseteq B\Uparrow$ oraz $B\subseteq C\Uparrow$ . Druga inkluzja daje $B\Uparrow \subseteq C\Uparrow$ , a zatem $A\subseteq B\Uparrow \subseteq C\Uparrow$ .

Wiemy więc, że $({ℳ}{𝒜}\left(\mathbf{𝐏}\right),\le )$ jest zbiorem częściowo uporządkowanym. Aby pokazać, że $({ℳ}{𝒜}\left(\mathbf{𝐏}\right),\le )$ jest kratą uzasadnimy, że zbiory opisane we wskazówce są kresami.

• kres dolny:

Niech $C$ będzie zbiorem elementów minimalnych zbioru $A\cup B$ . tworzy kres dolny elementów $A,B$ w porządku $({ℳ}{𝒜}\left(\mathbf{𝐏}\right),\le )$ . Nietrudno zauważyć, że $A\cup B\subseteq C\Uparrow$ , co implikuje, że $C\le A$ jak i $C\le B$ . Niech teraz $D\in {ℳ}{𝒜}\left(\mathbf{𝐏}\right)$ będzie ograniczeniem dolnym dla $A$ i $B$ , tzn. $A\subseteq D\Uparrow$ oraz $B\subseteq D\Uparrow$ . Wtedy $C\subseteq A\cup B\subseteq D\Uparrow$ , czyli $D\le C$ , a zatem $C$ jest największym ograniczeniem dolnym dla $A,B$ w posecie $({ℳ}{𝒜}\left(\mathbf{𝐏}\right),\le )$ .

• kres górny:

Na mocy obserwacji, że dla $X,Y\in {ℳ}{𝒜}\left(\mathbf{𝐏}\right)$ warunki $X\subseteq Y\Uparrow$ i $Y\subseteq X\Downarrow$ są równoważne (i opisują porządek $X\le Y$ w ${ℳ}{𝒜}\left(\mathbf{𝐏}\right)$ ) uzasadnienie, że zbiór elementów maksymalnych w $A\cup B$ jest kresem górnym dla $A,B$ , można przeprowadzić analogiczne jak dla kresu dolnego.

1. Poset ${\mathbf{𝐏}}^{\prime }$

Ćwiczenie 5

Wymiar częściowego porządku $\mathbf{𝐏}=(P,\le )$ to minimalny rozmiar rodziny ${ℛ}=\{{\mathbf{𝐋}}_1,{\mathbf{𝐋}}_2,\dots ,{\mathbf{𝐋}}_k\}$ liniowych porządków ${\mathbf{𝐋}}_i=(P,{\le }_i)$ spełniających warunek

$\le ={\le }_1\cap {\le }_2\cap \dots \cap {\le }_k$

Znajdź wymiar posetu ${\mathbf{𝐏}}^{\prime }=(P^{\prime },\le )$ przedstawionego na rysunku 1. Znajdź poset o wymiarze $3$ . Odpowiedź uzasadnij.

Wskazówka

Poset ${\mathbf{𝐏}}^{\prime }$ ma wymiar $2$ . Rozważ co się stanie, gdy dołożymy jeszcze zależność $v<u$ .

Rozwiązanie

2. Poset ${\mathbf{𝐏}}^{″}$

Na zbiorze $P^{\prime }$ zdefiniujmy liniowe ${\mathbf{𝐋}}_1=(P^{\prime },{\le }_1)$ oraz ${\mathbf{𝐋}}_2=(P^{\prime },{\le }_2)$ jako:

$\begin{array}{rlr}{\mathbf{𝐋}}_1:& & x{\le }_{1}u{\le }_{1}w{\le }_{1}t{\le }_{1}v{\le }_{1}s,\\ {\mathbf{𝐋}}_2:& & v{\le }_{2}w{\le }_{2}s{\le }_{2}x{\le }_{2}t{\le }_{2}u.\end{array}$

Nietrudno sprawdzić, że $\le ={\le }_1\cap {\le }_2$ , a więc poset ${\mathbf{𝐏}}^{\prime }=(P^{\prime },\le )$ ma wymiar co najwyżej $2$ . Oczywiście nie może mieć on wymiaru $1$ , bo posety wymiaru jeden są łańcuchami.

Rozważmy teraz poset ${\mathbf{𝐏}}^{″}=(P^{″},{\le }^{″})$ przedstawiony na rysunku 2.

Załóżmy, że ${\mathbf{𝐏}}^{″}$ ma wymiar $2$ . Istnieją więc dwa liniowe porządki ${\mathbf{𝐋}}^{\prime }{\text{'}}_1=(P^{″},{\le }^{\prime }{\text{'}}_1)$ oraz ${\mathbf{𝐋}}^{\prime }{\text{'}}_2=(P^{″},{\le }^{\prime }{\text{'}}_2)$ takie, że ${\le }^{″}={\le }^{\prime }{\text{'}}_1\cap {\le }^{\prime }{\text{'}}_2$ . Ponieważ $d{\le }^{″}a$ , to w obu liniowych rozszerzeniach ${\mathbf{𝐋}}^{\prime }{\text{'}}_1$ oraz ${\mathbf{𝐋}}^{\prime }{\text{'}}_2$ zachodzi:

$\begin{array}{rlr}{\mathbf{𝐋}}^{\prime }{\text{'}}_1:& & d{\le }^{\prime }{\text{'}}_{1}a,\\ {\mathbf{𝐋}}^{\prime }{\text{'}}_2:& & d{\le }^{\prime }{\text{'}}_{2}a.\end{array}$

Element $e$ jest mniejszy od $a$ , ale nieporównywalny z $d$ , więc bez straty ogólności możemy założyć, że

$\begin{array}{rlr}{\mathbf{𝐋}}^{\prime }{\text{'}}_1:& & e{\le }^{\prime }{\text{'}}_{1}d{\le }^{\prime }{\text{'}}_{1}a,\\ {\mathbf{𝐋}}^{\prime }{\text{'}}_2:& & d{\le }^{\prime }{\text{'}}_{2}e{\le }^{\prime }{\text{'}}_{2}a.\end{array}$

Element $c$ jest większy niż $e$ , ale nieporównywalny z $a$ oraz $d$ , więc jedyną możliwością umieszczenia $c$ jest

$\begin{array}{rlr}{\mathbf{𝐋}}^{\prime }{\text{'}}_1:& & e{\le }^{\prime }{\text{'}}_{1}c{\le }^{\prime }{\text{'}}_{1}d{\le }^{\prime }{\text{'}}_{1}a,\\ {\mathbf{𝐋}}^{\prime }{\text{'}}_2:& & d{\le }^{\prime }{\text{'}}_{2}e{\le }^{\prime }{\text{'}}_{2}a{\le }^{\prime }{\text{'}}_{2}c.\end{array}$

Z kolei $f$ musi być pod $c$ , i jako nieporównywalny ze zbiorem $\{a,d,e\}$ może więc być umieszczony tylko w następujący sposób:

$\begin{array}{rlr}{\mathbf{𝐋}}^{\prime }{\text{'}}_1:& & f{\le }^{\prime }{\text{'}}_{1}e{\le }^{\prime }{\text{'}}_{1}c{\le }^{\prime }{\text{'}}_{1}d{\le }^{\prime }{\text{'}}_{1}a,\\ {\mathbf{𝐋}}^{\prime }{\text{'}}_2:& & d{\le }^{\prime }{\text{'}}_{2}e{\le }^{\prime }{\text{'}}_{2}a{\le }^{\prime }{\text{'}}_{2}f{\le }^{\prime }{\text{'}}_{2}c.\end{array}$

Element $b$ powinien być nad $d$ oraz $f$ , a być nieporównywalny z elementami $a,c,e$ , co już jest niemożliwe. Nie istnieją więc dwa takie rozszerzenia liniowe, które w przecięciu dają ${\mathbf{𝐏}}^{″}$ .

Nietrudno jednak sprawdzić, że dla liniowych porządków ${\mathbf{𝐋}}^{″}{\text{'}}_1=(P^{″},{\le }^{″}{\text{'}}_1)$ , ${\mathbf{𝐋}}^{″}{\text{'}}_2=(P^{″},{\le }^{″}{\text{'}}_2)$ , oraz ${\mathbf{𝐋}}^{″}{\text{'}}_3=(P^{″},{\le }^{″}{\text{'}}_3)$ zadanych przez:

$\begin{array}{rlr}{\mathbf{𝐋}}^{″}{\text{'}}_1:& & e{\le }^{″}{\text{'}}_{1}f{\le }^{″}{\text{'}}_{1}c{\le }^{″}{\text{'}}_{1}d{\le }^{″}{\text{'}}_{1}b{\le }^{″}{\text{'}}_{1}a,\\ {\mathbf{𝐋}}^{″}{\text{'}}_2:& & d{\le }^{″}{\text{'}}_{2}e{\le }^{″}{\text{'}}_{2}a{\le }^{″}{\text{'}}_{2}f{\le }^{″}{\text{'}}_{2}c{\le }^{″}{\text{'}}_{2}b.\\ {\mathbf{𝐋}}^{″}{\text{'}}_3:& & f{\le }^{″}{\text{'}}_{3}d{\le }^{″}{\text{'}}_{3}b{\le }^{″}{\text{'}}_{3}e{\le }^{″}{\text{'}}_{2}a{\le }^{″}{\text{'}}_{3}c.\end{array}$

mamy ${\le }^{″}={\le }^{″}{\text{'}}_1\cap {\le }^{″}{\text{'}}_2\cap {\le }^{″}{\text{'}}_3$ . A zatem poset ${\mathbf{𝐏}}^{″}=(P^{″},{\le }^{″})$ ma wymiar $3$ .

Ćwiczenie 6

Na zbiorze liczb naturalnych $\mathbb{\mathbb{N}}$ zdefiniujmy częściowy porządek $⊑$ poprzez:

$a⊑b$ wtedy i tylko wtedy, gdy $a$ dzieli $b$ .

Udowodnij, że $({\mathbb{\mathbb{N}}}_{+},⊑)$ jest kratą.

Wskazówka

Korzystając z definicji największego wspólnego dzielnika i najmniejszej wspólnej wielokrotności pokaż, że:

• $a\wedge b=$ NWD $(a,b)$ ,
• $a\vee b=$ NWW $(a,b)$ .

Pamiętaj, że $1⊑a⊑0$ , dla dowolnego $a\in \mathbb{\mathbb{N}}$ .