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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned && w\to \ldots \to v \to \ldots \to r,\\ && v\to \ldots \to w \to \ldots \to r. \endaligned}

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{MA}\!\left( \mathbf{P} \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle A, B \in \mathscr{MA}\!\left( \mathbf{P} \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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned X\!\!\Uparrow&=\left\lbrace p\in P :\ \textrm{ istnieje } \displaystyle \ x\in X\ \textrm{ taki, że } \displaystyle \ x\leq p \right\rbrace,\\ X\!\!\Downarrow&=\left\lbrace p\in P :\ \textrm{ istnieje } \displaystyle \ x\in X\ \textrm{ taki, że }\displaystyle \ p\leq x \right\rbrace. \endaligned}

A zatem definicję relacji $\le$ w zbiorze Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{MA}\!\left( \mathbf{P} \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle X,Y\subseteq \mathscr{MA}\!\left( \mathbf{P} \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{MA}\!\left( \mathbf{P} \right),\leq \right) } jest częściowym porządkiem. Tak więc kolejno sprawdzamy warunki:

• zwrotność:

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

• antysymetria:

Niech teraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle A, B \in \mathscr{MA}\!\left( \mathbf{P} \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle A,B,C\in \mathscr{MA}\!\left( \mathbf{P} \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{MA}\!\left( \mathbf{P} \right),\leq \right) } jest zbiorem częściowo uporządkowanym. Aby pokazać, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{MA}\!\left( \mathbf{P} \right),\leq \right) } 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{MA}\!\left( \mathbf{P} \right),\leq \right) } . Nietrudno zauważyć, że $A\cup B\subseteq C\Uparrow$ , co implikuje, że $C\le A$ jak i $C\le B$ . Niech teraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle D\in\mathscr{MA}\!\left( \mathbf{P} \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{MA}\!\left( \mathbf{P} \right),\leq \right) } .

• kres górny:

Na mocy obserwacji, że dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle X,Y \in \mathscr{MA}\!\left( \mathbf{P} \right) } warunki $X\subseteq Y\Uparrow$ i $Y\subseteq X\Downarrow$ są równoważne (i opisują porządek $X\le Y$ w Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{MA}\!\left( \mathbf{P} \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.

<flash>file=Cw poset m.swf|width=250|height=150</flash>

<div.thumbcaption>1. Poset ${\mathbf{𝐏}}^{\prime }$

Ćwiczenie 5

Wymiar częściowego porządku $\mathbf{𝐏}=(P,\le )$ to minimalny rozmiar rodziny Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{R}=\left\lbrace \mathbf{L}_1,\mathbf{L}_2,\ldots,\mathbf{L}_k \right\rbrace } 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

<flash>file=Cw poset korona.swf|width=250|height=150</flash>

<div.thumbcaption>2. Poset ${\mathbf{𝐏}}^{″}$

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \mathbf{L}_1:&&x\ \leq_1\ u\ \leq_1\ w\ \leq_1\ t\ \leq_1\ v\ \leq_1\ s,\\ \mathbf{L}_2:&&v\ \leq_2\ w\ \leq_2\ s\ \leq_2\ x\ \leq_2\ t\ \leq_2\ u. \endaligned}

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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \mathbf{L}''_1:&&d\ \leq''_1\ a,\\ \mathbf{L}''_2:&&d\ \leq''_2\ a. \endaligned}

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \mathbf{L}''_1:&&e\ \leq''_1\ d\ \leq''_1\ a,\\ \mathbf{L}''_2:&&d\ \leq''_2\ e\ \leq''_2\ a. \endaligned}

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \mathbf{L}''_1:&&e\ \leq''_1\ c\ \leq''_1\ d\ \leq''_1\ a,\\ \mathbf{L}''_2:&&d\ \leq''_2\ e\ \leq''_2\ a\ \leq''_2\ c. \endaligned}

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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \mathbf{L}''_1:&&f\ \leq''_1\ e\ \leq''_1\ c\ \leq''_1\ d\ \leq''_1\ a,\\ \mathbf{L}''_2:&&d\ \leq''_2\ e\ \leq''_2\ a\ \leq''_2\ f\ \leq''_2\ c. \endaligned}

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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \mathbf{L}'''_1:&&e\ \leq'''_1\ f\ \leq'''_1\ c\ \leq'''_1\ d\ \leq'''_1\ b\ \leq'''_1\ a,\\ \mathbf{L}'''_2:&&d\ \leq'''_2\ e\ \leq'''_2\ a\ \leq'''_2\ f\ \leq'''_2\ c\ \leq'''_2\ b.\\ \mathbf{L}'''_3:&&f\ \leq'''_3\ d\ \leq'''_3\ b\ \leq'''_3\ e\ \leq'''_2\ a\ \leq'''_3\ c. \endaligned}

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}}$ .