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\lt 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\gt x[/math] zamiast [math]x\lt 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.

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]

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.

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\lt 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.

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.

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]