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]

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]