Porządek liniowy

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

Ilustracja porządku liniowego

Definicje

Porządek liniowy to porządek częściowy $\preccurlyeq$ na danym zbiorze $X$ spełniający warunek spójności:

$\forall _{a,b\in X}\;a\preccurlyeq b\lor b\preccurlyeq a.$

Parę uporządkowaną $(X,\preccurlyeq )$ nazywa się wtedy zbiorem liniowo uporządkowanym lub też zbiorem całkowicie uporządkowanym. Symbol $\prec$ będzie oznaczał porządek ostry, tzn. relację zdefiniowaną wzorem

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

Podzbiór $A$ zbioru $X$ nazywa się

• gęstym, jeśli zachodzi

  $\forall _{x,y\in X,x\prec y}\;\exists _{z\in A}\;x\prec z\prec y;$

• ograniczonym z góry, jeśli

  $\exists _{x\in X}\;\forall _{a\in A}a\preccurlyeq x.$

Mówi się, że $(X,\preccurlyeq )$ jest

• porządkiem bez końców, jeśli w $X$ nie ma tak elementu najmniejszego, jak i największego, tzn. jeśli nie zachodzi

  $\forall _{x\in X}\;\exists _{y\in X}\;y\preccurlyeq x$ oraz $\forall _{x\in X}\;\exists _{y\in X}\;x\preccurlyeq y;$

• 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.
• porządkiem gęstym, jeśli $X$ jest gęstym podzbiorem $X.$

Przykłady

• Relacje niewiększości 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 $\leqslant _{\mathrm {lex} }$ na płaszczyźnie $\mathbb {R} ^{2}$ jest porządkiem liniowym:

$(x_{1},y_{1})\leqslant _{\mathrm {lex} }(x_{2},y_{2})\iff x_{1}<x_{2}\lor (x_{1}=x_{2}\land y_{1}\leqslant y_{2}).$

Własności

• Jeśli $\sqsubseteq$ jest porządkiem liniowym na zbiorze $X$ oraz $Y\subseteq X,$ to zawężenie $\sqsubseteq _{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,\leqslant )$ taki że

  $X\subseteq Y$ i zawężenie $\leqslant _{X}$ zgadza się z $\sqsubseteq$ oraz $X$ jest gęstym podzbiorem $Y.$

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

Działania

Iloczyn leksykograficzny

Niech $(S,\preceq )$ będzie zbiorem uporządkowanym liniowo i dobrze. Niech $(X_{s},\leqslant _{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. Iloczynem leksykograficznym porządków $\leqslant _{s}$ nazywa się porządek liniowy w $X$ zdefiniowany wzorem

$x<y\Leftrightarrow x_{\delta }<y_{\delta },$

gdzie $\delta :=\delta (x,y)\in S$ będzie pierwszym elementem w $S,$ dla którego $x_{\delta }\neq y_{\delta }$ dla dowolnych $x,y\in X.$

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.

Ultraprodukt

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

$x_{F}\leqslant y_{F}\Leftrightarrow \{s\in S\colon x_{s}\leqslant y_{s}\}\in F$

dla dowolnych $x,y\in \prod _{s\in S}\;X_{s},$ gdzie $x_{F}$ oznacza klasę elementu $x:=(x_{s})_{s\in S}.$

Zastosowania

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.

Przedziałowe algebry Boole’a

Niech $(X,\sqsubseteq )$ będzie porządkiem liniowym, w którym istnieje element najmniejszy. Niech dla $x,y\in X\cup \{\infty \}$ symbol $[x,y[$ oznacza zbiór $\{z\in X\colon x\sqsubseteq z\sqsubset y\},$ tzn. przedział lewostronnie domknięty 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 w postaci $[x_{0},y_{0}[\cup \dots \cup [x_{k},y_{k}[$ dla pewnych elementów $x_{0},y_{0},\dots ,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 \dots \sqsubset x_{k}\sqsubset y_{k},$ gdzie $k\in \mathbb {N} .$ Wówczas ${\mathcal {F}}$ jest ciałem podzbiorów $X.$ Algebra Boole’a $({\mathcal {F}},\cup ,\cap ,',\varnothing ,X)$ jest nazywana algebrą przedziałową wyznaczoną przez $(X,\sqsubseteq ).$

Topologia porządkowa

Niech $(X,\sqsubseteq )$ będzie jest porządkiem liniowym. Niech dla $x,y\in X\cup \{-\infty ,\infty \}$ symbol $]x,y[$ oznacza przedział otwarty w $X,$ tzn. zbiór postaci $\{z\in X:x\sqsubset z\sqsubset y\}.$ Wówczas rodzina

${\mathcal {B}}=\left\{]x,y[\colon x\sqsubset y\right\}\cup \left\{]-\infty ,x[\colon x\in X\right\}\cup \left\{]x,\infty [\colon x\in X\right\}\cup \{X\}$

pokrywa $X$ i jest zamknięta ze względu na branie przekrojów skończonych. Dlatego też ${\mathcal {B}}$ jest bazą pewnej topologii $\tau$ na $X.$ Topologię tę nazywa się topologią porządkową lub topologią przedziałową. Topologia porządkowa zawsze spełnia aksjomat Hausdorffa (T₂) i jest nawet przestrzenią T₅.

Struktury algebraiczne

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 ,\leqslant )$ taka, że $(G,\circ )$ jest grupą, a $\leqslant$ jest porządkiem liniowym na $G,$ przy czym

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

• Ciało uporządkowane to szóstka uporządkowana $(F,+,\cdot ,0,1,\leqslant ),$ gdzie $(F,+,\cdot ,0,1)$ jest ciałem, a $\leqslant$ jest porządkiem liniowym na $F,$ w którym dla dowolnych $a,b,c\in F$ spełnione są warunki:

jeśli $a\leqslant b,$ to $a+c\leqslant b+c$

oraz

jeśli $a\leqslant b$ i $0\leqslant c,$ to $a\cdot c\leqslant b\cdot c.$