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

From Studia Informatyczne

Porządki częściowe

Ćwiczenie 1

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

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

otrzymana para \displaystyle \left( V,\leq \right) jest zbiorem częściowo uporządkowanym.

Wskazówka

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

Rozwiązanie

Sprawdzamy po kolei warunki na to, aby \displaystyle \left( V,\leq \right) był zbiorem częściowo uporządkowanym:

  • zwrotość:

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

  • antysymetria:

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


\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 \displaystyle w do \displaystyle r dojdziemy do \displaystyle v , co wobec jedyności, zmusza do przejścia później drugą ścieżką, czyli przez \displaystyle w . Na ścieżce punkty nie mogą sie jednak powtarzać.

  • przechodniość:

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

Ćwiczenie 2

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

Wskazówka

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

Rozwiązanie

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


\displaystyle p_1\leq p_2\leq \ldots \leq p_k\leq p_1


do


\displaystyle p_1\leq p_2\leq \ldots \leq p_{k-1}\leq p_1,


i z założenia indukcyjnego dostać


\displaystyle p_1= p_2= \ldots = p_{k-1}.


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

Ćwiczenie 3

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

Wskazówka

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

Rozwiązanie

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


\displaystyle P=C_1\cup\ldots\cup C_{s'},


gdzie \displaystyle s'\leq s jest mocą łańcucha o maksymalnej liczności. Ponieważ \displaystyle \left\vert C_i \right\vert\leq r , to


\displaystyle \left\vert P \right\vert=\left\vert C_1 \right\vert+\ldots+\left\vert C_{s'} \right\vert\leq rs'\leq rs.


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

Ćwiczenie 4

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

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

tworzy kratę.

Wskazówka

Dla \displaystyle A, B \in \mathscr{MA}\!\left( \mathbf{P} \right) zbiór elementów maksymalnych w \displaystyle A\cup B jest kresem górnym \displaystyle A,B , a zbiór elementów minimalnych w \displaystyle A\cup B jest kresem dolnym \displaystyle A,B .

Rozwiązanie

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


\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 \displaystyle \leq w zbiorze \displaystyle \mathscr{MA}\!\left( \mathbf{P} \right) możemy przeformułować następująco:


\displaystyle  A \leq B wtedy i tylko wtedy, gdy \displaystyle B \subseteq A\!\!\Uparrow
.


Zauważmy też, że

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

Istotnie, niech \displaystyle p\in X\!\!\Uparrow , tzn. \displaystyle x\leq p dla pewnego \displaystyle x\in X . Ale wobec \displaystyle x\in X \subseteq Y\!\!\Uparrow wiemy, że istnieje \displaystyle y\in Y takie, że \displaystyle y\leq x . A zatem \displaystyle p \geq y \in Y , czyli \displaystyle p \in Y\!\!\Uparrow .

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

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

Pokażemy najpierw, że \displaystyle \left( \mathscr{MA}\!\left( \mathbf{P} \right),\leq \right) jest częściowym porządkiem.

Tak więc kolejno sprawdzamy warunki:

  • zwrotność:

Ponieważ \displaystyle A\subseteq A\!\!\Uparrow , to \displaystyle A\leq A .

  • antysymetria:

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

  • przechodniość:

Niech \displaystyle A,B,C\in \mathscr{MA}\!\left( \mathbf{P} \right) spełniają \displaystyle A\subseteq B\!\!\Uparrow oraz \displaystyle B\subseteq C\!\!\Uparrow . Druga inkluzja daje \displaystyle B\!\!\Uparrow \subseteq C\!\!\Uparrow , a zatem \displaystyle A\  \subseteq  B \!\!\Uparrow\  \subseteq C\!\!\Uparrow .

Wiemy więc, że \displaystyle \left( \mathscr{MA}\!\left( \mathbf{P} \right),\leq \right) jest zbiorem częściowo uporządkowanym. Aby pokazać, że \displaystyle \left( \mathscr{MA}\!\left( \mathbf{P} \right),\leq \right) jest kratą uzasadnimy, że zbiory opisane we wskazówce są kresami.

  • kres dolny:

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

  • kres górny:

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



1. Poset \displaystyle \mathbf{P}'

Ćwiczenie 5

Wymiar częściowego porządku \displaystyle \mathbf{P}=\left( P,\leq \right) to minimalny rozmiar rodziny \displaystyle \mathscr{R}=\left\lbrace \mathbf{L}_1,\mathbf{L}_2,\ldots,\mathbf{L}_k \right\rbrace liniowych porządków \displaystyle \mathbf{L}_i=\left( P,\leq_i \right) spełniających warunek

\displaystyle \leq\ \ =\ \ \leq_1\ \cap\ \leq_2\ \cap\ \ldots\ \cap\ \leq_k.

Znajdź wymiar posetu \displaystyle \mathbf{P}'=\left( P',\leq \right) przedstawionego na rysunku 1. Znajdź poset o wymiarze \displaystyle 3 . Odpowiedź uzasadnij.

Wskazówka

Poset \displaystyle \mathbf{P}' ma wymiar \displaystyle 2 .

Rozważ co się stanie, gdy dołożymy jeszcze zależność \displaystyle v < u .

Rozwiązanie

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

2. Poset \displaystyle \mathbf{P}''

Na zbiorze \displaystyle P' zdefiniujmy liniowe \displaystyle \mathbf{L}_1=\left( P',\leq_1 \right) oraz \displaystyle \mathbf{L}_2=\left( P',\leq_2 \right) jako:

\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 \displaystyle \leq\ =\ \leq_1\cap\leq_2 ,

a więc poset \displaystyle \mathbf{P}'=\left( P',\leq \right) ma wymiar co najwyżej \displaystyle 2 . Oczywiście nie może mieć on wymiaru \displaystyle 1 , bo posety wymiaru jeden są łańcuchami.

Rozważmy teraz poset \displaystyle \mathbf{P}''=\left( P'',\leq'' \right)

przedstawiony na rysunku 2.

Załóżmy, że \displaystyle \mathbf{P}'' ma wymiar \displaystyle 2 .

Istnieją więc dwa liniowe porządki \displaystyle \mathbf{L}''_1=\left( P'',\leq''_1 \right) oraz \displaystyle \mathbf{L}''_2=\left( P'',\leq''_2 \right) takie, że \displaystyle \leq''\ =\ \leq''_1\cap\leq''_2 . Ponieważ \displaystyle d \leq'' a , to w obu liniowych rozszerzeniach \displaystyle \mathbf{L}''_1 oraz \displaystyle \mathbf{L}''_2 zachodzi:

\displaystyle \aligned \mathbf{L}''_1:&&d\ \leq''_1\ a,\\ \mathbf{L}''_2:&&d\ \leq''_2\ a. \endaligned

Element \displaystyle e jest mniejszy od \displaystyle a , ale nieporównywalny z \displaystyle d ,

więc bez straty ogólności możemy założyć, że


\displaystyle \aligned \mathbf{L}''_1:&&e\ \leq''_1\ d\ \leq''_1\ a,\\ \mathbf{L}''_2:&&d\ \leq''_2\ e\ \leq''_2\ a. \endaligned


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


\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 \displaystyle f musi być pod \displaystyle c , i jako nieporównywalny ze zbiorem \displaystyle \left\lbrace a,d,e \right\rbrace może więc być umieszczony tylko w następujący sposób:


\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 \displaystyle b powinien być nad \displaystyle d oraz \displaystyle f , a być nieporównywalny z elementami \displaystyle a,c,e , co już jest niemożliwe. Nie istnieją więc dwa takie rozszerzenia liniowe, które w przecięciu dają \displaystyle \mathbf{P}'' .

Nietrudno jednak sprawdzić, że dla liniowych porządków

\displaystyle \mathbf{L}'''_1=\left( P'',\leq'''_1 \right) , \displaystyle \mathbf{L}'''_2=\left( P'',\leq'''_2 \right) , oraz \displaystyle \mathbf{L}'''_3=\left( P'',\leq'''_3 \right) zadanych przez:


\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 \displaystyle \leq''\ =\ \leq'''_1\cap\leq'''_2\cap\leq'''_3 . A zatem poset \displaystyle \mathbf{P}''=\left( P'',\leq'' \right) ma wymiar \displaystyle 3 .

Ćwiczenie 6

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

\displaystyle a \sqsubseteq b wtedy i tylko wtedy, gdy \displaystyle a dzieli \displaystyle b .

Udowodnij, że \displaystyle \left( \mathbb{N}_+,\sqsubseteq \right) jest kratą.

Wskazówka

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

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

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