Porządek liniowy

Z Wikipedii

Ilustracja porządku liniowego

Porządek liniowy – częściowy porządek będący zarazem łańcuchem, czyli w którym każde dwa elementy rozpatrywanego zbioru są porównywalne.

Spis treści

1 Definicja formalna
2 Pojęcia
3 Przykłady
4 Własności
5 Działania na zbiorach liniowo uporządkowanych
- 5.1 Iloczyn leksykograficzny
- 5.2 Ultraprodukt
6 Porządki liniowe z dodatkową strukturą
7 Zobacz też

[edytuj] Definicja formalna

Porządek liniowy to porządek częściowy $\preccurlyeq$ na danym zbiorze $X$ , spełniający warunek

$\forall_{a, b \in X}\; a \preccurlyeq b \or b \preccurlyeq a$ .

Parę uporządkowaną $(X, \preccurlyeq)$ nazywa się wtedy zbiorem liniowo uporządkowanym lub też zbiorem całkowicie uporządkowanym.

[edytuj] Pojęcia

Niech $(X, \preccurlyeq)$ będzie zbiorem uporządkowanym liniowo oraz $A \subseteq X$ . Zgodnie z ustaloną tradycją, przez $\prec$ oznaczamy ostrą wersję porządku, tzn. relację zdefiniowaną przez

$x \prec y \iff x \preccurlyeq y \and x \neq y$ .

Mówimy, że $(X, \preccurlyeq)$ jest porządkiem bez końców, jeśli w $X$ nie ma ani największego ani najmniejszego elementu, tzn. jeśli zachodzi

$\forall_{x\in X}\; \exists_{y\in X}\; x \prec y$ oraz $\forall_{x\in X}\; \exists_{y\in X}\; y \prec x$ .

Powiemy, że $A$ jest gęstym podzbiorem $X$ , jeśli jest

$\forall_{x,y\in X, x \prec y}\; \exists_{z\in A}\; x \prec z \prec y$ .

$(X, \preccurlyeq)$ jest porządkiem gęstym, jeśli $X$ jest gęstym podzbiorem $X$ .
Zbiór $A$ jest ograniczony z góry, jeśli

$\exists_{x\in X}\; \forall_{a\in A} a \preccurlyeq x$ .

$(X, \preccurlyeq)$ jest porządkiem relatywnie zupełnym, jeśli każdy niepusty i ograniczony z góry podzbiór $X$ ma kres górny. Wtedy także każdy niepusty podzbiór ograniczony z dołu ma kres dolny.

[edytuj] Przykłady

Relacje większe lub równe na zbiorze liczb całkowitych, wymiernych czy rzeczywistych są porządkami liniowymi.
Szczególnym przypadkiem porządku liniowego jest dobry porządek.
Porządek leksykograficzny $\leq_{\rm lex}$ na płaszczyźnie $\mathbb R^2$ jest porządkiem liniowym:

$(x_1,y_1)\leq_{\rm lex} (x_2,y_2) \iff x_1<x_2 \or x_1=x_2 \and y_1\leq y_2$ .

[edytuj] Własności

Jeśli $\sqsubseteq$ jest porządkiem liniowym na zbiorze $X$ oraz $Y\subseteq X$ , to obcięcie $\sqsubseteq\upharpoonright Y$ porządku $\sqsubseteq$ do zbioru $Y$ jest porządkiem liniowym (na $Y$ ).
Georg Cantor udowodnił następujące twierdzenie: każdy przeliczalny gęsty porządek liniowy bez końców jest izomorficzny ze zbiorem liczb wymiernych (z naturalnym porządkiem).
Przypuśćmy że $(X,\sqsubseteq)$ jest gęstym porządkiem liniowym bez końców. Wówczas istnieje relatywnie zupełny porządek liniowy bez końców $(Y,\leq)$ taki że

$X\subseteq Y$ i obcięcie $\leq \upharpoonright X$ zgadza się z $\sqsubseteq$ oraz $X$ jest gęstym podzbiorem $Y$ .

Porządek $(Y,\leq)$ jest jedyny z dokładnością do izomorfizmu.

[edytuj] Działania na zbiorach liniowo uporządkowanych

[edytuj] Iloczyn leksykograficzny

Niech $(S, \preceq)\,$ będzie zbiorem uporządkowanym liniowo i dobrze. Niech $(X_s, \le_s)\,$ będzie zbiorem uporządkowanym liniowo, dla każdego $s \in S$ , oraz niech $X := \prod_{s\in S} X_s$ będzie iloczynem kartezjańskim. W $X\,$ definiujemy porządek liniowy, zwany iloczynem leksykograficznym porządków $\le_s\,$ , jak następuje:

Definicja. Niech $\delta := \delta(x,y)\in S\,$ będzie pierwszym elementem w $S\,$ , dla którego $x_\delta \ne y_\delta\,$ , dla dowolnych $x,y\in X\,$ ; wtedy:

$x < y\ \Leftrightarrow \ x_\delta < y_\delta$

Koniec definicji.

Okazuje się, że iloczyn leksykograficzny skończonej rodziny zachowuje dobry porządek: iloczyn leksykograficzny skończonej rodziny zbiorów uporządkowanych liniowo i dobrze jest zbiorem uporządkowanym liniowo i dobrze. Natomiast iloczyn leksykograficzny nieskończonej rodziny zbiorów liniowo uporządkowanych, z których każdy jest co najmniej dwuelementowy, nigdy nie jest uporządkowany dobrze.

[edytuj] Ultraprodukt

Niech $S\,$ będzie dowolnym zbiorem nieskończonym. Niech $\emph{F}\,$ będzie dowolnym maksymalnym filtrem (czyli ultrafiltrem) w $S\,$ , o pustym przecięciu. Niech ponadto $(X_s, \le_s)\,$ będzie zbiorem uporządkowanym liniowo, dla każdego $s \in S$ , oraz niech $X_\emph{F}$ będzie ultraproduktem rodziny zbiorów $(X_s)_{s\in S}\,$ , względem ultrafiltru $\emph{F}\,$ . W ultraprodukcie $X\,$ definiujemy porządek liniowy jak następuje:

$x_{_\emph{F}}\le y_{_\emph{F}}\ \Leftrightarrow\ \{s\in S : x_s \le y_s\} \in \emph{F}$

dla dowolnych $x,y \in \prod_{s\in S}\,X_s$ , gdzie $x_{_\emph{F}}$ oznacza klasę elementu $x := (x_s)_{s\in S}$ .

[edytuj] Porządki liniowe z dodatkową strukturą

W wielu dziedzinach matematyki rozważa się relację porządku liniowego jako "dodatek" do innych struktur albo jako "narzędzie" do konstruowania przykładów rozważanych struktur.

[edytuj] Przedziałowe algebry Boole'a

Przypuśćmy że $(X,\sqsubseteq)$ jest porządkiem liniowym w którym istnieje element najmniejszy. Dla $x,y\in X\cup\{\infty\}$ niech $[x,y)=:\{z\in X:x\sqsubseteq z\sqsubset y\}$ będzie lewostronnie domkniętym przedziałem w $X$ .

Niech ${\mathcal F}$ będzie rodziną złożoną ze zbioru pustego oraz tych wszystkich podzbiorów $X$ które mogą być przedstawione jako $[x_0,y_0)\cup\ldots\cup [x_k,y_k)$ dla pewnych elementów $x_0,y_0,\ldots,x_k,y_k\in X\cup\{\infty\}$ spełniających nierówności $x_0\sqsubset y_0\sqsubset x_1\sqsubset y_1\sqsubset \ldots\sqsubset x_k\sqsubset y_k$ , $k\in {\mathbb N}$ . Wówczas ${\mathcal F}$ jest ciałem podzbiorów $X$ . Algebra Boole'a $({\mathcal F},\cup,\cap,{}^\prime,\emptyset,X)$ jest nazywana algebrą przedziałową wyznaczoną przez $(X,\sqsubseteq)$ .

[edytuj] Topologia porządkowa

Niech $(X,\sqsubseteq )$ będzie jest porządkiem liniowym. Dla $x,y\in X\cup\{-\infty,\infty\}$ niech $(x,y)=:\{z\in X:x\sqsubset z\sqsubset y\}$ będzie przedziałem otwartym w $X$ . Wówczas rodzina

${\mathcal B}=\big\{(x,y):x\sqsubset y\big\}\cup\big\{(-\infty,x):x\in X\big\}\cup\big\{(x,\infty): x\in X\big\}\cup\{X\}$

pokrywa $X$ i jest zamknięta na skończone przekroje. Dlatego też ${\mathcal B}$ jest bazą pewnej topologii $τ$ na $X$ . Topologię tę nazywamy topologią porządkową lub czasami topologią przedziałową. Topologia porządkowa zawsze spełnia aksjomat Hausdorffa (T₂) i jest nawet przestrzenią T₅.^[1]

[edytuj] Porządki liniowe na strukturach algebraicznych

W algebrze rozważa się czasami struktury algebraiczne, dodatkowo wyposażone w relację porządku liniowego w pewnym sensie zgodnego z operacjami algebraicznymi.

Grupa liniowo uporządkowana to trójka $(G,\circ,\leq)$ taka że

$(G,\circ)$ jest grupą, $\leq$ jest porządkiem liniowym na $G$ , oraz

dla dowolnych $a,b,c\in G$ , jeśli $a\leq b$ to zarówno $a\circ c \leq b\circ c$ jak i $c\circ a\leq c\circ b$ .

Ciało uporządkowane to $(F,+,\cdot,0,1,\leq)$ gdzie

$(F,+,\cdot,0,1)$ jest ciałem, $\leq$ jest porządkiem liniowym na $F$ , oraz

dla dowolnych $a,b,c\in F$ ,