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 (wkrótce).