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.

Definicje

Porządek liniowy to porządek częściowy ${\displaystyle \preccurlyeq }$ na danym zbiorze ${\displaystyle X}$ spełniający warunek spójności^[1]:

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

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

${\displaystyle x\prec y\iff x\preccurlyeq y\land x\neq y.}$

Podzbiór ${\displaystyle A}$ zbioru ${\displaystyle X}$ nazywa się

• gęstym, jeśli zachodzi

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

• ograniczonym z góry, jeśli

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

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

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

  ${\displaystyle \forall _{x\in X}\;\exists _{y\in X}\;y\preccurlyeq x}$ oraz ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle X}$ jest gęstym podzbiorem ${\displaystyle 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 ${\displaystyle \leqslant _{\mathrm {lex} }}$ na płaszczyźnie ${\displaystyle \mathbb {R} ^{2}}$ jest porządkiem liniowym:

${\displaystyle (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 ${\displaystyle \sqsubseteq }$ jest porządkiem liniowym na zbiorze ${\displaystyle X}$ oraz ${\displaystyle Y\subseteq X,}$ to zawężenie ${\displaystyle \sqsubseteq _{Y}}$ porządku ${\displaystyle \sqsubseteq }$ do zbioru ${\displaystyle Y}$ jest porządkiem liniowym na ${\displaystyle Y.}$
• Georg Cantor udowodnił następujące twierdzenie^{[potrzebny przypis]}: 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 ${\displaystyle (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 ${\displaystyle (Y,\leqslant )}$ taki że

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

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

Działania

Iloczyn leksykograficzny

Niech ${\displaystyle (S,\preceq )}$ będzie zbiorem uporządkowanym liniowo i dobrze. Niech ${\displaystyle (X_{s},\leqslant _{s})}$ będzie zbiorem uporządkowanym liniowo dla każdego ${\displaystyle s\in S}$ oraz niech ${\displaystyle X:=\prod _{s\in S}X_{s}}$ będzie iloczynem kartezjańskim. Iloczynem leksykograficznym porządków ${\displaystyle \leqslant _{s}}$ nazywa się porządek liniowy w ${\displaystyle X}$ zdefiniowany wzorem

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

gdzie ${\displaystyle \delta :=\delta (x,y)\in S}$ będzie pierwszym elementem w ${\displaystyle S,}$ dla którego ${\displaystyle x_{\delta }\neq y_{\delta }}$ dla dowolnych ${\displaystyle 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

 Zobacz też: ultraprodukt.

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

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

dla dowolnych ${\displaystyle x,y\in \prod _{s\in S}\;X_{s},}$ gdzie ${\displaystyle x_{F}}$ oznacza klasę elementu ${\displaystyle 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 ${\displaystyle (X,\sqsubseteq )}$ będzie porządkiem liniowym, w którym istnieje element najmniejszy. Niech dla ${\displaystyle x,y\in X\cup \{\infty \}}$ symbol ${\displaystyle [x,y[}$ oznacza zbiór ${\displaystyle \{z\in X\colon x\sqsubseteq z\sqsubset y\},}$ tzn. przedział lewostronnie domknięty w ${\displaystyle X.}$

Niech ${\displaystyle {\mathcal {F}}}$ będzie rodziną złożoną ze zbioru pustego oraz tych wszystkich podzbiorów ${\displaystyle X,}$ które mogą być przedstawione w postaci ${\displaystyle [x_{0},y_{0}[\cup \dots \cup [x_{k},y_{k}[}$ dla pewnych elementów ${\displaystyle x_{0},y_{0},\dots ,x_{k},y_{k}\in X\cup \{\infty \}}$ spełniających nierówności ${\displaystyle x_{0}\sqsubset y_{0}\sqsubset x_{1}\sqsubset y_{1}\sqsubset \dots \sqsubset x_{k}\sqsubset y_{k},}$ gdzie ${\displaystyle k\in \mathbb {N} .}$ Wówczas ${\displaystyle {\mathcal {F}}}$ jest ciałem podzbiorów ${\displaystyle X.}$ Algebra Boole’a ${\displaystyle ({\mathcal {F}},\cup ,\cap ,',\varnothing ,X)}$ jest nazywana algebrą przedziałową wyznaczoną przez ${\displaystyle (X,\sqsubseteq ).}$

Topologia porządkowa

 Osobny artykuł: topologia porządkowa.

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

${\displaystyle {\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 ${\displaystyle X}$ i jest zamknięta ze względu na branie przekrojów skończonych. Dlatego też ${\displaystyle {\mathcal {B}}}$ jest bazą pewnej topologii ${\displaystyle \tau }$ na ${\displaystyle 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₅^[2].

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

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

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

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

oraz

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

Przypisy