Tekst źródłowy strony Zbiory uporządkowane

''Zbiorem uporządkowanym (częściowo) nazywamy parę <math>\left( X, R\right)</math>, gdzie <math>X</math> jest zbiorem, a  <math>R\subset  X\times X</math> jest relacją:''

1. Zwrotną, tzn. dla dowolnego <math>x\in X</math> zachodzi <math>\left( x,x\right) \in R. </math>

2. Antysymetryczną, tzn. spełnia warunek <math>\left( x,y\right) \in R  \wedge \left( y,x\right)  \in R \Longrightarrow x=y.</math>

3. Przechodnią, tzn. spełnia warunek  <math>\left( x,y\right) \in R  \wedge \left( y,z\right)  \in R \Longrightarrow \left( x,z\right) \in R.</math>

''Jeżeli dodatkowo relacja jest spójna, tzn. dla dowolnych <math>x,y\in X,</math> zachodzi <math>\left( x,y\right) \in R</math> lub <math>\left( y,x\right) \in R</math>, to wtedy parę <math>\left( X, R\right)</math>, nazywamy zbiorem liniowo uporządkowanym. Mówimy wtedy, że <math>R</math> jest liniowym porządkiem na <math>X</math>, oraz że zbiór <math>X</math> jest liniowo uporządkowany przez <math>R</math>. Podobnie dla zbioru uporządkowanego, relację nazywamy porządkiem (częściowym) na zbiorze <math>X.</math>''

Często oznaczamy relację porządku przez  <math>\le</math>( lub symbolami podobnymi np.<math>\preccurlyeq, \sqsubseteq</math>). Dla zbioru uporządkowanego <math>\left( X, \le \right)</math>, dla dowolnego <math>x\in X</math> zachodzi <math>x \le x,</math> bo relacja porządku jest zwrotna.  Zatem dla elementów <math>x,y\in X</math>, oznaczamy <math>x<y</math> gdy <math>x \le y</math> i <math>x\neq y,</math> i mówimy, że <math>x</math> jest silnie mniejszy od <math>y.</math> Podobnie dla innych oznaczeń relacji porządku. W zbiorze uporządkowanym <math>\left( X,\le\right)</math>,  będziemy czasem pisać <math>y\ge x</math> zamiast <math>x\le y</math>, oraz <math>y>x</math> zamiast <math>x<y.</math>

Warto zobaczyć jaką postać przyjmują wymagania stawiane zbiorom liniowo uporządkowanym, gdy relację liniowego porządku oznaczymy przez <math>\le</math>, (i  gdy będziemy pisać zamiast <math>\left( x,y\right) \in R,</math> będziemy pisać <math>x\left( R\right) y.</math> O zwrotności już pisałem, jako <math>x\le x</math>, dla dowolnego <math>x\in X.</math> Antysymetria przyjmuję postać:  jeżeli <math>x\le y</math> i <math>y\le x</math>, to <math>x=y</math>. Przechodniość przyjmuję postać: jeżeli <math>x\le y</math> i <math>y\le z</math>, to <math>x\le z.</math> Spójność zapisujemy jako: dla dowolnych <math>x,y\in X</math> ma zachodzić <math>x\le y</math> lub <math>y\le x</math>. Nietrudno więc zauważyć, że te własności są spełnione w zbiorach liczbowych z naturalnym porządkiem. Nasza definicja zbioru liniowego uporządkowanego jest więc uogólnieniem znanych własności porządkowych na zbiorach liczbowych. Nie zapominajmy jednak, że formalnie jest to zbiór wraz z relacją, która ma dokładnie wymienione własności.

Uwaga. Zbiór pusty jest liniowo uporządkowany przez relację pustą. Wynika to z faktu, ze własności zwrotności, antysymetrii, przechodniośći i spójności mają być spełnione dla dowolnych elementów zbioru uporządkowanego, czyli w tym wypadku zbioru pustego- a każde zdanie postaci <math>\bigwedge\limits_ {x,y\in\left\{ \right\} } \alpha \left( x,y\right)</math> jest prawdą

''Niech <math>\left( X, \le \right)</math> będzie zbiorem uporządkowanym. niech <math>A \subset X, a\in X</math>. Element <math>a</math> nazywamy elementem najmniejszym zbioru <math>A</math> względem porządku  <math>\le</math>,  gdy <math>a\in A</math>, oraz gdy dla dowolnego <math>x\in A</math>, zachodzi <math>a \le x.</math>''

Tzn. element najmniejszy zbioru <math>A</math>, to taki element <math>A</math>, który jest  mniejszy lub równy (względem rozpatrywanego porządku) od każdego elementu tego zbioru <math>A</math>.

Analogicznie możemy zdefiniować ''element największy zbioru <math>A \subset X</math>, jako taki element <math>a\in A</math>, który jest większy lub równy od każdego elementu tego zbioru, tzn. dla dowolnego <math>x\in A</math> zachodzi <math>x \le a.</math>''

'''Fakt 0.''' ''Jeśli w zbiorze uporządkowanym <math>\left( X, \le \right)</math> podzbiór <math>A \subset X</math> ma element najmniejszy/ największy, to jest on jedynym elementem najmniejszym/największym w <math>A</math>.''

Dowód:

Przypuśćmy, że <math>a,b</math> są elementami najmniejszymi w <math>A</math>. Pokażemy, że <math>a=b</math>. Elementy najmniejsze w <math>A</math> należą do <math>A</math>- <math>a,b\in A</math>. Ponieważ  jednak <math>a</math> jest elementem najmniejszym <math>A</math>, to jest on mniejszy od każdego elementu w tym zbiorze, więc również <math>a \le b</math>. Podobnie, ponieważ <math>b</math> jest elementem najmniejszym <math>A</math>, to podobnie <math>b \le a.</math> Ponieważ <math>a \le b</math> i <math>b \le a,</math> to z antysymetrii porządku <math>a=b.</math> Dowód dla elementów największych jest analogiczny.<math>\square</math>


Przykład: Rozważmy zbiór liczb naturalnych <math>\mathbb{N}</math> uporządkowany ( to należy pokazać) relacją podzielności |, tzn. 

<math>a|b \Longleftrightarrow \hbox{ istnieje liczba naturalna } c \hbox{ taka, że } a \cdot c=b.</math>

Równoważnie to oznacza, że (dla <math>a \neq 0</math>) iloraz  <math>\frac{b}{a}</math>   jest pewną liczbą naturalną <math>c</math>. Wykażemy, że <math>\left( \mathbb{N},|\right)</math> jest zbiorem uporządkowanym, a potem, że <math>0</math> jest elementem największym, a <math>1</math> jest elementem najmniejszym (tak przekornie wychodzi- ale nie względem naturalnego porządku, tylko względem naszego porządku <math>|</math>).

Zwrotność. Niech <math>n\in\mathbb{N}.</math> Wtedy możemy dobrać <math>c=1</math>, i otrzymać <math>n \cdot 1=n</math>, a więc <math>n|n</math>. Relacja <math>|</math> jest więc zwrotna  (zwróć uwagę co się dzieje dla <math>n=0</math>, jak działa to proste rozumowanie).

Przechodniość. Niech <math>x,y,z \in\mathbb{N}</math> będą takie, że <math>x|y</math> oraz, że <math>y|z</math>. Pokażemy, że <math>x|z</math>. Nasze założenia oznaczają, że <math>x \cdot c _{1} =y</math> dla pewnej liczby naturalnej <math>c _{1}</math>, oraz, że <math>y \cdot c _{2}=z</math> dla pewnej liczby naturalnej <math>c _{2}</math>. Wobec czego <math>x \cdot \left( c _{1} \cdot c _{2}  \right) =\left( x \cdot c _{1}\right)  \cdot  c _{2}=y \cdot c _{2}=z.</math> Ponieważ iloczyn dwóch liczb naturalnych jest liczbą naturalną, więc  możemy dobrać <math>c _{3}= c _{1} \cdot c _{2}</math>, tak aby <math>x \cdot \left( c _{1} \cdot c _{2}  \right) =z</math>, a więc <math>x|z.</math>

Antysymetria. Weźmy dowolne liczby naturalne <math>n,m</math>, dla których <math>n|m</math> i <math>m|n.</math> Nasze założenia oznaczają, że <math>n \cdot c _{1} =m</math> dla pewnej liczby naturalnej <math>c _{1}</math>, oraz, że <math>m \cdot c _{2}=n</math> dla pewnej liczby naturalnej <math>c _{2}.</math> Wobec czego <math>n \cdot  \left( c _{1} \cdot c _{2}  \right) =\left( n \cdot c _{1}\right) \cdot c _{2} =m \cdot c _{2}=n.</math>

Rozważymy teraz dwa przypadki. Jeśli <math>n \neq 0</math>, to wtedy <math>n \cdot  \left( c _{1} \cdot c _{2}  \right) =n =n \cdot 1</math>, a więc z prawa skreśleń dla liczb naturalnych otrzymujemy, że <math>c _{1} \cdot c _{2} =1</math>, i ponieważ <math>c_{1},c_{2}</math> są to liczby naturalne, to <math>c_{1}=1=c_{2}</math>, a więc <math>n \cdot 1 =m</math>, czyli <math>n=m</math>.

Jeśli <math>n=0</math>, to wtedy <math>0=0\cdot c _{1} =n \cdot c _{1} =m</math> , czyli <math>m=0=n</math>, więc <math>n=m.</math> Relacja <math>|</math> jest więc antysymetryczna.

Zatem <math>\left( \mathbb{N},|\right)</math> jest zbiorem uporządkowanym. '''W tym''' zbiorze uporządkowanym elementem największym jest <math>0</math>, a najmniejszym <math>1</math>.

Niech <math>n\in\mathbb{N}</math>. Wtedy możemy dobrać <math>c=0</math>, i otrzymać <math>n \cdot 0=0</math>, a więc <math>n|0</math>. Ponieważ każda liczba naturalna dzieli <math>0</math> (czyli każda liczba naturalna jest mniejsza, względem relacji podzielności, od <math>0</math>), to <math>0</math> jest elementem największym (względem <math>|</math>- relacji podzielności.) W tym zbiorze uporządkowanym <math>1</math> jest elementem najmniejszym. Niech <math>n\in\mathbb{N}</math>. Wtedy możemy dobrać <math>c=n</math>, i otrzymać <math>1 \cdot n=n</math>, a więc <math>1|n</math>. Ponieważ <math>1</math> dzieli każdą liczbę naturalną (czyli <math>1</math> jest mniejszy, względem relacji podzielności, od każdej liczby), to <math>1</math> jest elementem najmniejszym.


[[Plik:Zbiory_uporządkowane-_funkcje.JPG|300px|thumb|right|]]
Kolejny przykład. Niech <math>X</math> będzie niepustym ustalonym zbiorem. Niech <math>a,b\in\mathbb{R},</math> będą takie, że <math>a<b.</math> Niech <math>Y=\left[ a,b\right]  \subset \mathbb{R}</math>. W zbiorze funkcji z <math>X</math> do <math>Y</math>, czyli <math>Y^X</math>, wprowadzamy relację <math>R</math>:

<math>f\left( R\right) g \Longleftrightarrow \hbox{ dla dowolnego } x\in X: f\left( x\right)  \le g\left( x\right).</math>

Wykażemy, że <math>R</math> jest relacją porządku na <math>Y^X</math>. Geometrycznie ten porządek oznacza, że funkcja <math>f</math> jest mniejsza od funkcji <math>g</math>, gdy wykres funkcji <math>f</math> w każdym punkcie leży poniżej (lub na równi) niż wykres funkcji <math>g</math> (zobacz ilustrację obok). 

Zwrotność. Niech <math>f\in \left( Y=\left[ a,b\right]\right)  ^{X}</math>. Niech <math>x\in X</math>. Wtedy niewątpliwie <math>f\left( x\right)=f\left( x\right)</math>, a więc ze zwrotności naturalnego porządku na liczbach rzeczywistych <math>f\left( x\right) \le f\left( x\right)</math>, Z dowolności wyboru <math>x\in X</math>, oznacza to, że <math>f\left( R\right) f</math>. Relacja <math>R</math> jest więc zwrotna.

Antysymetria. Załóżmy, że <math>f\left( R\right) g</math> i <math>g\left( R\right) f</math>. Zatem dla dowolnego <math>x\in X</math> mamy <math>f\left( x\right)  \le g\left( x\right),</math> oraz dla każdego <math>x\in X</math>, mamy  <math>g\left( x\right)  \le f\left( x\right).</math> Niech <math>x\in X.</math> Wtedy <math>f\left( x\right)  \le g\left( x\right) ,</math> oraz <math>g\left( x\right)  \le f\left( x\right).</math> Z antysymetrii naturalnego porządku na liczbach rzeczywistych, otrzymujemy, że <math>f\left( x\right)= g\left( x\right)</math>, Z dowolności wyboru <math>x\in X</math>, oznacza to, że <math>f=g</math>. Relacja <math>R</math> jest więc antysymetryczna.

Przechodniość. Załóżmy, że <math>f\left( R\right) g</math> i <math>g\left( R\right) h</math>. Zatem dla dowolnego <math>x\in X</math> mamy <math>f\left( x\right)  \le g\left( x\right),</math> oraz dla każdego <math>x\in X</math>, mamy  <math>g\left( x\right)  \le h\left( x\right).</math> Niech <math>x\in X.</math> Wtedy <math>f\left( x\right)  \le g\left( x\right) ,</math> oraz <math>g\left( x\right)  \le h\left( x\right).</math>  Z przechodniości porządku <math>\le</math> otrzymujemy, że <math>f\left( x\right) \le  h\left( x\right)</math>, Z dowolności wyboru <math>x\in X</math>, oznacza to, że <math>f\left( R\right) h</math>. Relacja <math>R</math> jest więc przechodnia.

Zatem <math>\left( \left[ a,b\right]  ^{X},R\right)</math> jest zbiorem uporządkowanym. Elementem najmniejszym jest funkcja <math>f_0</math> stale równa <math>a</math>, a elementem największym funkcja <math>f_1</math> stale równa <math>b</math>, tzn.

<math>f_{0}\left( x\right)=a, \hbox{  dla każdego }  x\in X.</math>

<math>f_{1}\left( x\right)=b, \hbox{  dla każdego }  x\in X.</math>

Mamy bowiem, dla dowolnej funkcji <math>f</math> z <math>X</math> do <math>\left[ a,b\right]</math>, oraz dla dowolnego <math>x\in X</math> (bo są to funkcje o wartościach w <math>Y=\left[ a,b\right]</math>), mamy <math>f\left( x\right) \in \left[ a,b\right]</math>, a więc  <math>f_{0}\left( x\right)=a\le f\left( x\right) \le b=f_{1}\left( x\right)</math>, zatem ( z dowolności <math>x\in X</math>) <math>f _{0} \left( R\right) f</math>, oraz <math>f\left( R\right) f _{1}</math>, czyli <math>f_0</math> jest elementem najmniejszym, oraz <math>f_{1}</math> jest elementem największym.


Jeśli <math>\left( X, \le \right)</math> jest zbiorem uporządkowanym, a dla elementów <math>x,y\in X</math>, zachodzi <math>x \le y</math> lub <math>y\le x</math>, to mówimy, że elementy <math>x,y</math> są porównywalne. W  zbiorze liniowo uporządkowanym, każde więc dwa elementy są porównywalne. Jednak ogólniej, tzn. w zbiorze uporządkowanym tak być nie musi. Przyjęło się przyjmować w teorii mnogości, że zbiór jest uporządkowany, jeśli tylko '''niektóre''' jego elementy dadzą się porównać (np. każdy element <math>x</math> jest porównywalny z samym sobą- na mocy zwrotności porządku). Istnieje bowiem wiele zbiorów, wraz z relacją, która jest relacją porządku na tym zbiorze, ale nie jest liniowym porządkiem na tym zbiorze (bo nie jest spójna). Rzeczywiście, poprzednie dwa przykłady o tym świadczą. Nie będę mówił, że naturalnym jest, że relacja podzielności jest porządkiem na <math>\mathbb{N}</math>. Ale zobacz ciekawy przykład drugi- zbiór funkcji. Co więcej, naturalnym jest dla mnie (i nie tylko), że zbiory mogą być mniejsze lub większe pod względem inkluzji. I okazuję się właśnie, że dla ustalonego zbioru <math>X</math>, jego zbiór potęgowy (czyli zbiór jego wszystkich podzbiorów) jest uporządkowany przez inkluzję, ale niekoniecznie liniowo. Zbiory mogą być nieporównywalne przez inkluzję. Jest to zatem, nie jeden przykład na to, lecz cała rodzina  przykładów. Pokażemy nawet jeszcze więcej.

'''Twierdzenie 1.''' ''Niech <math>X</math> będzie dowolnym ustalonym zbiorem, i niech <math>Y \subset P\left( X\right)</math> ( czyli <math>Y</math> jest zbiorem niektórych podzbiorów <math>X</math>). Zdefiniujmy relację <math>\sqsubseteq</math> na zbiorze <math>Y</math>:''

<math>A\sqsubseteq B \Longleftrightarrow   A \subset B.</math>

''Wykażemy, że <math>\left( Y,\sqsubseteq\right)</math> jest zbiorem uporządkowanym.''

Dowód:

Zwrotność. Dla dowolnego zbioru <math>A</math>, mamy <math>A \subset A</math>. więc również dla elementów <math>A\in Y</math>, mamy <math>A\subset A</math>, a więc <math>A\sqsubseteq A</math>. Relacja jest więc zwrotna.

Przechodniość. Weźmy dowolne zbiory <math>A,B,C\in Y</math>, dla których <math>A\sqsubseteq B</math> i <math>B\sqsubseteq C</math>. Oznacza to, że <math>A \subset B</math> i <math>B\subset C</math>. Daje to <math>A\subset C</math>, a więc <math>A\sqsubseteq C</math>. Relacja jest więc przechodnia.

Antysymetria. Weźmy dowolne zbiory <math>A,B\in Y</math>, dla których <math>A\sqsubseteq B</math> i <math>B\sqsubseteq A</math>. Oznacza to, że <math>A \subset B</math> i <math>B\subset A</math>. Daje to <math>A=B</math>. Antysymetria jest więc pokazana.

Zatem <math>\left( Y,\sqsubseteq\right)</math> jest zbiorem uporządkowanym. Jest to jednak niekoniecznie liniowo zbiór uporządkowany. Kontrprzykładem będzie: <math>X=\left\{ 0,1\right\}</math>, <math>Y=P\left( X\right)</math>, <math>A=\left\{ 0\right\}</math>, <math>B=\left\{ 1\right\}</math>. Wtedy <math>A \not\subset B</math> oraz <math>B\not\subset A. \square</math>
 
Będziemy  używać symbolu  <math>\subset</math> dla oznaczenia relacji  <math>\sqsubseteq</math> zdefiniowanej w poprzednim twierdzeniu.  Zwracamy przy tym uwagę, że nie ma czegoś takiego jak relacja  <math>\subset</math>, gdyż musiałaby ona być określona pomiędzy dwoma dowolnymi zbiorami, a więc  w zbiorze wszystkich zbiorów, który nie istnieje. W przypadku jednak, gdy rozważamy jedynie podzbiory ustalonego zbioru  <math>X</math>, możemy mówić o relacji bycia podzbiorem.

== Elementy maksymalne i minimalne==

''Niech <math>\left( X, \le \right)</math> będzie zbiorem uporządkowanym. Element <math>a\in X</math> nazywamy maksymalnym, gdy dla dowolnego <math>x\in X</math> zachodzi: 

<math>a \le x \Longrightarrow x=a.</math>''

Tzn. element <math>a</math> jest maksymalny, gdy jeśli <math>x</math> jest większy lub równy od <math>a</math>- elementu maksymalnego, to musi ten <math>x</math> być równy temu elementowi maksymalnemu, a więc nie ma elementów silnie większych od elementu maksymalnego. Podobnie definiujemy elementy minimalne.

''W zbiorze uporządkowanym <math>\left( X, \le \right)</math>, element <math>a\in X</math> nazywamy elementem minimalnym, gdy dla dowolnego <math>x\in X</math> zachodzi: 

<math>x \le a \Longrightarrow x=a.</math>''

Tzn. element <math>a</math> jest minimalny, gdy nie ma silnie mniejszych od niego elementów, a więc gdy element <math>x</math> jest słabo mniejszy od elementu minimalnego, to musi być mu równy.
[[Plik:Zadanie-element_maksymalny.JPG|300px|thumb|right| ]]
Przykład. Podamy przykład  zbioru uporządkowanego, w którym istnieje element maksymalny, który nie jest elementem największym. 

Rozważmy zbiór <math>X= \{0,1\}</math> uporządkowany <math>R=\left\{ \left( 0,0\right) \left( 1,1\right)\right\}</math>. Łatwo sprawdzić, że <math>R</math> jest porządkiem.  Wtedy obydwa elementy (<math>0</math> i <math>1</math>) są maksymalne, a żaden z nich nie jest największy, bo są nieporównywalne.

Istnieje też zbiór uporządkowany, w którym istnieje dokładnie jeden element maksymalny, który nie jest elementem największym. Niech <math>T</math> będzie elementem takim, że  <math>T\notin \mathbb{N}.</math>  Niech  <math>X=\mathbb{N} \cup \{T\}</math>. Zbiór <math>X</math> uporządkujemy relacją  <math>R=\le \cup \{(T,T)\}</math>, gdzie <math>\le</math> jest naturalną relacją porządku w  <math>\mathbb{N}</math>. Zobacz ilustrację obok- do zbioru liczb naturalnych dodaliśmy jeden element <math>T</math> porównywalny tylko z samym sobą. Ponieważ <math>\le</math> jest porządkiem na <math>\mathbb{N}</math>, więc  łatwo sprawdzić, że  <math>R</math> jest porządkiem na <math>X</math>. Wtedy <math>T</math> jest elementem maksymalnym (bo jedyny element, który jest z nim porównywalny to on sam, a więc nie może istnieć żaden większy). W dodatku <math>T</math> nie jest elementem największym, bo na przykład nie jest większy od <math>0</math>. Nie ma drugiego elementu maksymalnego, gdyż musiałby być liczbą naturalną. Dla każdej liczby naturalnej natomiast istnieje liczba naturalna od niej  istotnie większa (czyli liczba naturalna nie może być elementem maksymalnym).

A więc widać, że pojęcia: element maksymalny a element największy, mogą znaczyć co innego. Przyczyną takiego stanu rzeczy, są właśnie elementy nieporównywalne, a dokładniej warunki  <math>x\not\le y</math>, a <math>y\le x</math>, nie muszą być równoważne, bo elementy <math>x,y</math> mogą być nieporównywalne. Jednak w '''liniowym''' zbiorze uporządkowanym (gdzie każde dwa elementy są porównywalne) pojęcia element największy a maksymalny, oraz symetrycznie- element najmniejszy a minimalny się pokrywają. Mówi o tym następny fakt.

''' Fakt 2.''' ''W zbiorze liniowo uporządkowanym <math>\left( X, \le\right)</math>  element jest maksymalny/minimalny, wtedy i tylko wtedy, gdy jest największy/najmniejszy.''

Czyli w zbiorze '''liniowo''' uporządkowanym terminy element maksymalny a element największy już znaczą to samo. Symetrycznie dla elementów minimalnych a najmniejszych- w '''liniowym''' zbiorze uporządkowanym te pojęcia znaczą to samo.

Dowód:

<math>\Longleftarrow</math> Gdyby istniał element <math>a</math>, który jest największy, ale nie jest maksymalny, to z ostatniego istniałby element <math>b</math> silnie większy od <math>a</math>. Ale <math>a</math> jest elementem największym, zatem <math>b</math> jest silnie większy od największego, a tak być nie może. Sprzeczność.

<math>\Longrightarrow</math> Niech <math>a</math> będzie maksymalny. Pokażemy, że <math>a</math> jest największy. Ustalmy zatem dowolny element <math>b\in X</math>. Przypuśćmy niewprost, że  <math>b\not\le a</math>. Ponieważ porządek jest liniowy, więc elementy <math>a, b</math> '''są porównywalne''', i  <math>b\not\le a</math>,  więc musi być <math>a \le  b</math>, a skoro tak, to z maksymalności  <math>a</math> mamy <math>a=b</math>. Ponieważ <math>b\not\le a=b</math>, to otrzymujemy sprzeczność ze zwrotnością porządku.<math>\square</math>- Dowód dla elementów najmniejszych, minimalnych jest symetryczny.

== Diagramy Hassego ==
[[Plik:Diagram_Hassego.JPG|300px|thumb|right|Przykład diagramu Hassego]]
Skończone zbiory uporządkowane wygodnie jest czasem przedstawiać na grafach, tzw. 
'''diagramach Hassego.''' Zobacz ilustrację obok. Odczytujemy,że '''w tym''' zbiorze uporządkowanym <math>3<4,4<5,3<5,2<1,4<6,3<6.</math> Ogólnie, element <math>x</math> jest mniejszy od elementu <math>y</math>, jeśli element <math>x</math> można połączyć drogą z elementem <math>y</math>, idąc cały czas w górę( bądź na ukos). Dlatego '''tutaj''' <math>2\not<3,4,5,6.</math>
[[Plik:Diagram_Hassego-_element_najmniejszy_i_najw..JPG|300px|thumb|right|]]
Na diagramie Hassego odczytujemy, że element jest najmniejszy, kiedy wszystkie elementy na tym diagramie dochodzą do niego (w dół). Podobnie odczytujemy element największy (tylko w górę). Zobacz ilustrację obok- tu <math>1</math> jest elementem najmniejszym, a <math>0</math> jest elementem największym- jest to diagram Hassego dla relacji podzielności na zbiorze <math>\{ 0,1,2,3,4,5,6\}.</math>

== Supremum i infimum ==

''Niech <math>\left( X, \le\right)</math> będzie zbiorem uporządkowanym, <math>A \subset X</math> oraz   <math>x\in X</math>. Mówimy, że   <math>x</math> jest ograniczeniem górnym zbioru   <math>A</math>, gdy dla dowolnego <math>a\in A,</math> mamy  <math>a\le x.</math>''

Czyli ograniczenie górne zbioru <math>A</math>, to taki element zbioru <math>X</math>, który jest większy lub równy od każdego elementu tego zbioru <math>A</math>.

''Niech <math>A \subset X</math> oraz   <math>x\in X</math>. Mówimy, że  <math>x</math> jest ograniczeniem dolnym zbioru <math>A</math>, gdy dla dowolnego <math>a\in A,</math> mamy <math>x \le a.</math>''

Podobnie ograniczenie dolne zbioru <math>A</math>, to taki element, który jest mniejszy lub równy od każdego elementu tego zbioru <math>A</math>.
[[Plik:Supremum i infimum.JPG|300px|thumb|right|Supremum i infimum]]
''Niech <math>\left( X, \le\right)</math> będzie zbiorem uporządkowanym, <math>A \subset X</math>. Element <math>a\in X</math> nazywamy supremum zbioru <math>A</math>, gdy:''

1.''<math>a</math> jest ograniczeniem górnym zbioru <math>A</math>.'' 
2. ''jeśli <math>b\in X</math> jest ograniczeniem górnym zbioru <math>A</math>, to  <math>a\le b.</math>''

Czyli supremum zbioru <math>A</math>, to jego ograniczenie górne- najmniejsze z możliwych.

''Niech <math>A \subset X</math>. Element <math>a\in X</math> nazywamy infimum zbioru <math>A</math>, gdy:''

1.''<math>a</math> jest ograniczeniem dolnym zbioru <math>A</math>.'' 
2. ''jeśli <math>b\in X</math> jest ograniczeniem dolnym zbioru <math>A</math>, to   <math>b\le a.</math>''

Czyli infimum zbioru <math>A</math> to jego ograniczenie dolne- największe z możliwych. Zobacz ilustrację obok.

Łatwo zauważyć, że supremum, o ile istnieje, jest jedyne (bo jest to pewnego rodzaju element najmniejszy). Jeżeli istnieje supremum dla zbioru <math>A,</math> będziemy je oznaczać <math>\bigvee A</math>.

Tak jak w przypadku supremum, infimum, o ile istnieje, jest jedyne( bo jest to pewnego rodzaju element największy).  Jeżeli istnieje infimum dla zbioru <math>A</math>, będziemy je oznaczać <math>\bigwedge A.</math>

Poniżej podaję prosty fakt.

'''Fakt 3.''' ''W zbiorze uporządkowanym <math>\left( X, \le\right)</math>, oraz dla zbioru <math>B \subset X</math>, jeśli element <math>b</math> jest elementem największym /najmniejszym<math>B</math>, to <math>b</math> jest supremum/infimum  zbioru <math>B</math>.''

Czyli element największy zbioru <math>B \subset X</math>, jest jego supremum. Symetrycznie- element najmniejszy zbioru <math>B \subset X</math> jest jego infimum.

Dowód:

Niech <math>B \subset X</math>, przypuśćmy, że element <math>b</math> jest elementem największym w<math>B</math>. Pokażemy, że <math>b</math> jest również supremum <math>B</math>. Ponieważ <math>b</math> jest elementem największym w <math>B</math>, to jest on większy od każdego elementu w tym zbiorze. Zatem <math>b</math> jest ograniczeniem górnym dla <math>B</math>. Pozostaje pokazać, że to jest najmniejsze ograniczenie górne dla zbioru <math>B</math>. Niech <math>c</math> będzie ograniczeniem górnym <math>B</math>. Jest ono więc większe od każdego elementu <math>B</math>. A ponieważ <math>b</math> jest elementem największym <math>B</math>, to niewątpliwie <math>b\in B</math>. Zatem <math>b \le c</math>. Z dowolności wyboru <math>c</math>,otrzymujemy, że  <math>b</math> jest najmniejszym ograniczeniem górnym zbioru <math>B</math>, a więc  <math>b</math> jest supremum zbioru <math>B</math>. <math>\square</math> Dowód dla elementów najmniejszych, infimum jest symetryczny.

Przykład. Dla dowolnego zbioru <math>X</math>, jego zbiór potęgowy   <math>\mathcal{P}(X)</math> jest uporządkowany przez inkluzję. Czy dla dowolnej niepustej rodziny   <math>\mathbb{A} \subset \mathcal{P}(X)</math> istnieje supremum i infimum?

Pokażemy, że dla dowolnej rodziny   <math>\mathbb{A}\subset \mathcal{P}(X)</math>, mamy  <math>\bigcup  \mathbb{A}= \bigvee  \mathbb{A}</math> oraz (jeśli dodatkowo rodzina jest niepusta), to:  <math>\bigcap  \mathbb{A}= \bigwedge  \mathbb{A}.</math>

Zauważmy najpierw, że <math>\bigcup  \mathbb{A}, \bigcap  \mathbb{A}\subset X</math>, zatem <math>\bigcup  \mathbb{A}, \bigcap  \mathbb{A} \in \mathcal{P}(X).</math> Pokażemy, że <math>\bigcup  \mathbb{A}</math> spełnia warunki bycia supremum dla <math>\mathbb{A}.</math>

1. Niech <math>B\in\mathbb{A}.</math> Z własności sumy <math>B \subset \bigcup  \mathbb{A}.</math> Wobec dowolności <math>B</math>, oznacza to, że <math>\bigcup  \mathbb{A}</math> jest ograniczeniem górnym rodziny <math>\mathbb{A}.</math>

2. Niech <math>C \subset X</math>, będzie ograniczeniem górnym rodziny <math>\mathbb{A}</math>, pod względem inkluzji. Oznacza to, że <math>B\subset C</math>, dla dowolnego zbioru <math>B\in\mathbb{A}</math> Zatem każdy zbiór <math>B\in\mathbb{A}</math> jest podzbiorem <math>C</math>, to również <math>\bigcup  \mathbb{A}</math> jest podzbiorem <math>C</math>, czyli <math>\bigcup  \mathbb{A}\subset C</math>. Wobec dowolności <math>C</math>, otrzymujemy, że <math>\bigcup  \mathbb{A}=\bigvee  \mathbb{A}.</math>

Niech  <math>\mathbb{A} \subset \mathcal{P}(X)</math> będzie niepustą rodziną podzbiorów <math>X</math>. Pokażemy, że <math>\bigcap  \mathbb{A}= \bigwedge  \mathbb{A}.</math> Pokażemy, że <math>\bigcap  \mathbb{A}</math> spełnia warunki bycia infimum dla <math>\mathbb{A}.</math>

1. Niech <math>B\in\mathbb{A}.</math> Z własności iloczynu  <math>B \supset \bigcap  \mathbb{A}</math> , a więc <math>\bigcap  \mathbb{A} \subset B.</math> Wobec dowolności <math>B</math>, oznacza to, że <math>\bigcap  \mathbb{A}</math> jest ograniczeniem dolnym rodziny <math>\mathbb{A}.</math>

2. Niech <math>C \subset X</math>, będzie ograniczeniem dolnym rodziny <math>\mathbb{A}</math>, pod względem inkluzji. Oznacza to, że <math>C\subset B</math>, dla dowolnego zbioru <math>B\in\mathbb{A}.</math> Zatem zbiór <math>C</math>  zawiera się w każdym zbiorze rodziny <math>\mathbb{A}</math>(niepustej) , to również <math>C</math> zawiera się w iloczynie tej rodziny, czyli  <math>C\subset \bigcap  \mathbb{A}</math>. Wobec dowolności <math>C</math>, otrzymujemy, że <math>\bigcap  \mathbb{A}= \bigwedge  \mathbb{A}.</math>

W zbiorze uporządkowanym podzbiór może nie mieć supremum/infimum, i to z różnych przyczyn. Np. rozważmy zbiór <math>\{0,1\}</math> uporządkowany przez <math>R=\left\{ \left( 0,0\right) ,\left( 1,1\right)\right\}. </math> Wtedy cały zbiór <math>\{0,1\}</math> nie ma supremum, bo <math>0</math> nie ogranicza z góry <math>1</math>, i <math>1</math> nie ogranicza z góry <math>0</math>. Kolejny przykład będzie dotyczył liniowego porządku. Rozważmy zbiór <math>\mathbb{N}</math> z naturalnym porządkiem, wtedy cały <math>\mathbb{N}</math> nie ma supremum, gdyż takie supremum musiałoby być liczbą naturalną będącą ograniczeniem górnym <math>\mathbb{N}</math>, czyli największą liczbą naturalną, a taka nie istnieje. Wobec czego tutaj <math>\mathbb{N}</math> nie ma supremum. Tak, zbiory nieograniczone z góry nie mogą mieć supremum, gdyż supremum z definicji jest ograniczeniem górnym. Jednak takie zbiory nieskończone jak <math>\mathbb{N}</math> mogą mieć supremum, w pewnych zbiorach uporządkowanych( bo mogą być ograniczone z góry), o czym się jeszcze przekonamy. Podobne zależności dostrzegamy dla infimum zbioru.

== Łańcuchy i antyłańcuchy ==

''W zbiorze uporządkowanym <math>\left( X,  \le \right)</math> zbiór <math>A\subset X</math> nazywamy łańcuchem, gdy każde dwa elementy <math>A</math> są porównywalne w sensie rozpatrywanego porządku  <math>\le</math>.''

''W zbiorze uporządkowanym <math>\left( X,  \le \right)</math> zbiór <math>A\subset X</math> nazywamy antyłańcuchem, gdy żadne dwa różne elementy <math>A</math> nie są porównywalne. Tzn. dla dowolnych <math>a,b\in A</math>zachodzi: 

<math>a \le b \rightarrow a=b.</math>''

Ćwiczenie: Czy antyłańcuch może być łańcuchem?

Rozwiązanie: Dla niepustego zbioru uporządkowanego <math>\left( X,  \le \right)</math> każdy jednoelementowy  podzbiór  jest  antyłańcuchem, jak i  łańcuchem.
 
Odnotujmy dwa proste fakty. Dla dowolnego zbioru uporządkowanego <math>\left( X,  \le \right)</math> każdy jego podzbiór <math>Y\subset X</math> jest również uporządkowany przez <math>\le \cap  \left( Y\times Y\right)</math>, czyli przez relację  <math>\le</math> zawężoną do elementów <math>Y</math>. Czyli każdy podzbiór zbioru uporządkowanego jest również uporządkowany. Wynika to z faktu, że własności zwrotności, antysymetrii, i przechodniości są spełnione w zbiorze uporządkowanym <math>\left( X,  \le \right)</math> dla dowolnych elementów <math>X</math>, więc będą spełnione również dla dowolnych elementów <math>Y</math>, jako podzbioru, stąd łatwo sprawdzić, że <math>\left( Y,  \le \cap  \left( Y\times Y\right) \right)</math> jest zbiorem uporządkowanym. Kolejny fakt mówi, że dla dowolnego zbioru <math>X</math> relacja identyczności na <math>X</math> jest relacją porządku. Łatwo sprawdzić, że jest zwrotna i przechodnia. Aby sprawdzić antysymetrię niech <math>\left( x,y\right)  \in I_{X}</math> oraz <math>\left( y,x\right)  \in I_{X}</math>. Założenie <math>\left( x,y\right)  \in I_{X}</math> oznacza, że <math>x=y</math>. W ten zabawnie prosty sposób sprawdziliśmy antysymetrię, więc relacja identyczności jest relacją porządku na zbiorze <math>X</math>.

Dla każdego zbioru uporządkowanego <math>\left( X,  \le \right)</math>, zarówno zbiór jego  wszystkich łańcuchów, jak i zbiór jego antyłańcuchów jest uporządkowany przez inkluzję, w myśl twierdzenia 1. Łatwo można pokazać, że zawsze istnieje najmniejszy pod względem inkluzji łańcuch i antyłańcuch- pusty podzbiór <math>X</math>. Fakt, że w każdym zbiorze uporządkowanym możemy znaleźć maksymalny łańcuch (podobnie antyłańcuch) jest prawdziwy, przy założeniu aksjomatu wyboru. Będziemy o tym pisać w następnym rozdziale. Natomiast za chwilę opiszemy w prosty sposób kiedy w zbiorze uporządkowanym jest największy  łańcuch (i  największy antyłańcuch).

Przykład. Rozważmy zbiór <math>X=\left\{ 0,1,2,3,4,5,6\right\}</math> uporządkowany relacją podzielności. Wtedy maksymalnymi łańcuchami pod względem inkluzji są:

<math>\left\{ 0,1,5\right\},</math>
<math>\left\{ 0,1,2,4\right\},</math>
<math>\left\{ 0,1,2,6\right\},</math>
<math>\left\{ 0,1.3,6\right\}.</math>

A maksymalnymi antyłańcuchami są:

<math>\left\{ 0\right\},</math>
<math>\left\{ 1\right\} ,</math>
<math>\left\{ 4,5,6\right\},</math>
<math>\left\{ 2,3,5\right\},</math>
<math>\left\{ 3,4,5\right\}.</math>

''W zbiorze uporządkowanym <math>\left( X,  \le \right)</math> istnieje największy pod względem inkluzji łańcuch dokładnie wtedy, gdy porządek jest liniowy.''

Dowód: <math>\Leftarrow</math> Jeśli <math>\left( X,  \le \right)</math> jest zbiorem liniowo uporządkowanym, to łatwo się przekonać, że cały zbiór <math>X</math> jest łańcuchem. Ponieważ każdy łańcuch ze swej natury jest podzbiorem <math>X</math>, czyli jest mniejszy pod względem inkluzji od <math>X</math>, to łańcuch <math>X</math> jest największy.

<math>\Rightarrow</math> Przypuśćmy nie wprost, że porządek nie jest liniowy. Istnieją wtedy dwa elementy nieporównywalne <math>x</math> i <math>y</math>. Łatwo się przekonać, że zbiory jednoelementowe <math>\left\{ x\right\}</math> ,<math>\left\{ y\right\}</math> są łańcuchami, zatem są podzbiorami największego łańcucha. Ale wtedy w tym największym łańcuchu znajdują się elementy <math>x,y</math>. Czyli w takim łańcuchu są elementy nieporównywalne <math>x</math> i <math>y</math>- sprzeczność  z definicją łańcucha.<math>\square</math>

''W zbiorze uporządkowanym <math>\left( X,  \le \right)</math> istnieje największy pod względem inkluzji antyłańcuch dokładnie wtedy, gdy porządek jest relacją identyczności na <math>X</math>.''

Dowód:

<math>\Leftarrow</math> Jeśli <math>\le= I_{X}</math>, to łatwo się przekonać, że cały zbiór <math>X</math> jest antyłańcuchem. Ponieważ każdy antyłańcuch ze swej natury jest podzbiorem <math>X</math>, czyli jest mniejszy pod względem inkluzji od <math>X</math>, to antyłańcuch <math>X</math> jest największy.

<math>\Rightarrow</math>  Przypuśćmy, że <math>\le \neq  I_{X}.</math> Pokażemy, że nie istnieje wtedy największy antyłańcuch. Przypuśćmy dla dowodu nie wprost, że istnieje i nazywa się <math>A</math>. Ponieważ <math>\le</math> nie jest relacją identyczności na <math>X</math>, więc relacja ma w sobie parę <math>\left( x,y\right)</math> , gdzie <math>x \neq y.</math> Oznacza to, ze elementy <math>x,y</math> są porównywalne, i różne. Wtedy łatwo się przekonać, że zbiory jednoelementowe <math>\left\{ x\right\}</math> ,<math>\left\{ y\right\}</math> są antyłańcuchami, zatem są podzbiorami największego antyłańcucha <math>A</math>. Ale wtedy w tym największym antyłańcuchu znajdują się elementy <math>x,y</math>. Czyli w takim antyłańcuchu są rózne elementy porównywalne <math>x</math> i <math>y</math>- sprzeczność z definicją antyłańcucha.<math>\square</math>

== Liniowe porządki ==

[[Plik:Rozszerzenie.JPG|300px|thumb|right| Rozszerzenie porządku]]
''Niech <math>\left( X, \le _{X}\right) , \left( Y, \le _{Y}\right)</math> zbiory uporządkowane. Porządek <math>\le _{Y}</math> nazywamy rozszerzeniem porządku  <math>\le_{X}</math>, gdy dla dowolnych <math>a,b\in X</math> spełniony jest warunek:

<math>a\le _{X}b \Longrightarrow a\le _{Y}b.</math>'' 

Tzn. jeśli <math>a</math> jest mniejszy ( lub równy) od <math>b</math> względem danego porządku (na <math>X</math>),to tymbardziej musi <math>a</math> być mniejsze(lub równe) od <math>b</math> względem porządku rozszerzającego. Dla liniowych porządków wygląda to tak, że porządek rozszerzający jest szerszy- zobacz ilustrację obok.

[[Plik:Liniowe porządki.JPG|300px|thumb|right|Suma liniowych porządków]]
'''Twierdzenie:'''

''Niech <math>X</math> będzie dowolnym ustalonym zbiorem. Niech <math>S</math> będzie pewnym zbiorem złożonym z liniowych porządków( samych relacji) określonych na pewnych podzbiorach <math>X</math>, takim, że dla dowolnych dwóch liniowych porządków w <math>S</math> jeden jest rozszerzeniem drugiego, to wtedy dla relacji  <math>\bigcup S</math>, zachodzi <math>\left( \bigcup S\right) _{L}=\left( \bigcup S\right) _{P}</math> i <math>\bigcup S</math> jest liniowym porządkiem na tym zbiorze.''

Tzn. suma rodziny liniowych porządków na podzbiorach <math>X</math>, i jeśli wiemy, że dla dowolnych dwóch takich liniowych porządków jeden jest rozszerzeniem drugiego, to wtedy suma rodziny takich liniowych porządków jest liniowym porządkiem na swoim polu- zobacz ilustrację obok.

Dowód:

Aby wykazać, że  <math>\left( \bigcup S\right) _{L}=\left( \bigcup S\right) _{P}</math> wykażemy inkluzję w obydwie strony.

Aby pokazać, że <math>\left( \bigcup S\right) _{L} \subset \left( \bigcup S\right) _{P}</math>, to niech <math>x\in \left( \bigcup S\right) _{L}</math>. Oznacza to , że <math>\left( x,y\right) \in  \bigcup S</math> przy pewnym <math>y</math>. To z kolei zapisujemy <math>x\left( \bigcup S\right) y,</math> a więc <math>x \le y</math> dla pewnego liniowego porządku <math>\le</math> z <math>S</math>. Porządek taki jest zwrotny, więc <math>x \le x</math>, a więc otrzymujemy, że <math>x\left( \bigcup S\right) x</math>, lub inaczej <math>\left( x,x\right)  \in \bigcup S</math>, i ponieważ <math>x</math> jest prawą współrzędna pary z relacji <math>\bigcup S</math>, to <math>x\in\left( \bigcup S\right) _{P}</math>, i <math>\left( \bigcup S\right) _{L} \subset \left( \bigcup S\right) _{P}.</math>

Dowód inkluzji w drugą stronę jest analogiczny. A więc <math>\left( \bigcup S\right) _{L}=\left( \bigcup S\right) _{P}.</math> Oznaczmy ten zbiór jako <math>X _{\bigcup S}</math> . Wykażemy, że <math>\bigcup S</math> jest liniowym porządkiem na tym zbiorze.

Zwrotność. Niech <math>x\in X _{\bigcup S}</math>. Należy pokazać,  że <math>\left( x,x\right)  \in \bigcup S</math>, lub inaczej że <math>x\left( \bigcup S\right) x,</math> czyli, że <math>x \le x</math> dla pewnego liniowego porządku  <math>\le</math>  z <math>S</math>. Ale każdy liniowy porządek jest zwrotny, więc powyższy fakt jest prawdziwy. Relacja <math>\bigcup S</math> jest więc zwrotna.

Antysymetria. Niech <math>\left( x,y\right)  \in \bigcup S</math> i <math>\left( y,x\right)  \in \bigcup S</math>. Pokażemy, że <math>x=y</math>. Równoważnie możemy zapisać  nasze założenia jako <math>x\left( \bigcup S\right) y,</math> i <math>y\left( \bigcup S\right) x.</math>  Pierwszy warunek oznacza, że <math>x \le y</math> dla pewnego liniowego porządku  <math>\le</math>  z <math>S.</math>  Drugi warunek oznacza, że <math>y \le' x</math> dla pewnego liniowego porządku  <math>\le'</math>  z <math>S</math>  ( niekoniecznie tego samego). Ale wiemy, że dla dowolnych dwóch liniowych porządków z <math>S</math> jeden jest rozszerzeniem drugiego, więc jeśli <math>\le'</math> jest rozszerzeniem <math>\le</math>, to z warunku <math>x \le y</math> wynika, że <math>x \le' y,</math> mamy <math>y \le' x</math>, i ponieważ liniowy porządek  <math>\le'</math> jest antysymetryczny, to dostajemy <math>x=y</math>, co należało pokazać. W drugim przypadku <math>\le</math> jest rozszerzeniem <math>\le'</math>, i wtedy z warunku <math>y \le' x</math> wynika, że <math>y \le x</math>, mamy <math>x \le y</math>, i ponieważ liniowy porządek  <math>\le</math> jest antysymetryczny, to dostajemy <math>x=y</math>, co należało pokazać. Antysymetria jest więc pokazana.

Przechodniość. Niech <math>\left( x,y\right)  \in  \bigcup S, \left( y,z\right)  \in  \bigcup S.</math> Pokażemy, że <math>\left( x,z\right)  \in  \bigcup S.</math> Nasze założenia możemy inaczej zapisać jako: <math>x\left( \bigcup S\right) y,</math> oraz <math>y\left( \bigcup S\right) z.</math> Wnioskujemy, że <math>x \le y</math> dla pewnego liniowego porządku <math>\le</math>  z <math>S</math>, oraz, że  <math>y \le' z</math> dla pewnego liniowego porządku <math>\le'</math> z <math>S</math>. Dla porządków  <math>\le</math>,  <math>\le'</math> jeden jest rozszerzeniem drugiego, więc jeśli <math>\le'</math> jest rozszerzeniem <math>\le</math>, to z faktu <math>x \le y</math> wynika, że <math>x \le' y</math>, mamy, że <math>y \le' z</math>, więc z przechodniości liniowego porządku <math>\le'</math> otrzymujemy, że <math>x \le' z</math>, a więc <math>x\left( \bigcup S\right) z</math>, czyli <math>\left( x,z\right)  \in  \bigcup S.</math> W pozostałym przypadku musi być <math>\le</math>  rozszerzeniem <math>\le'</math>, a wtedy z faktu <math>y \le' z</math> wynika, że <math>y \le z</math>, mamy założenie, że <math>x \le y</math>, więc z przechodniości liniowego porządku  <math>\le</math>, dostajemy, że <math>x \le z</math>, i również w tym przypadku <math>\left( x,z\right)  \in  \bigcup S.</math> Relacja <math>\bigcup S</math> jest więc przechodnia.

Dowód spójności jest niestety bardzo żmudny, więc go pomijamy. Wykazaliśmy, że <math>\bigcup S</math> jest  porządkiem na  swoim polu. Tego twierdzenia użyjemy tylko chyba raz w dowodzie twierdzenia Zermelo. To, że ten porządek jest liniowy nie będzie nam wtedy konieczne. <math>\square</math>