Porządek liniowy

Linear_ordering2.svg Porządek liniowy to taki częściowy porządek $\sqsubseteq$ na danym zbiorze $X$ , że dla wszystkich $a, b$ ze zbioru $X$ mamy $a\sqsubseteq b$ lub $b\sqsubseteq a$ .

Innymi słowy, porządek liniowy to taki porządek częściowy który jest łańcuchem, tzn w którym każde dwa elementy są porównywalne.

Jeśli $\sqsubseteq$ jest porządkiem liniowym na zbiorze $X$ , to para uporządkowana $(X,\sqsubseteq)$ jest nazywana zbiorem liniowo uporządkowanym albo też zbiorem całkowicie uporządkowanym.

Przykłady i dodatkowe pojęcia

Relacje większe-lub-równe na zbiorze liczb całkowitych, wymiernych czy rzeczywistych mogą stanowić przykłady porządków liniowych.
Szczególnym przypadkiem porządku liniowego jest dobry porządek.
Porządek leksykograficzny na płaszczyźnie jest porządkiem liniowym. Przypomnijmy, że porządek leksykograficzny $\leq_{\rm lex}$ na ${\mathbb R}^2$ jest zdefiniowany przez warunek

(x_1,y_1)\leq_{\rm lex} (x_2,y_2)

wtedy i tylko wtedy gdy

x_1 lub x_1=x_2 i y_1\leq y_2 .

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

x\sqsubset y

wtedy i tylko wtedy gdy

x\sqsubseteq y

oraz

x\neq y

. (O ostrych i słabych porządkach zobacz też tutaj.)

Mówimy że $X$ jest porządkiem bez końców, jeśli w $X$ nie ma ani największego ani najmniejszego elementu, tzn jeśli $(\forall x\in X)(\exists y\in X)(x\sqsubset y)$ oraz $(\forall x\in X)(\exists y\in X)(y\sqsubset x)$ .
Powiemy że $A$ jest gęstym podzbiorem $X$ jeśli dla każdych $x,y\in X$ takich że $x \sqsubset y$ można znaleźć $z\in A$ spełniające warunek $x\sqsubset z\sqsubset y$ .

Mówimy że

(X,\sqsubseteq)

jest porządkiem gęstym jeśli

X

jest gęstym podzbiorem

X

Zbiór $A$ jest ograniczony z góry jeśli istnieje element $x\in X$ taki że $(\forall a\in A)(a\sqsubseteq x)$ .
Powiemy $(X,\sqsubseteq)$ jest porządkiem zupełnym jeśli każdy niepusty i ograniczony z góry podzbiór $X$ ma kres górny.

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$ ).
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 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.

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.

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)$ .

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

\tau

X

. Topologię tę nazywamy topologią porządkową lub czasami topologią przedziałową.

Porzadki liniowe na strukturach algebraicznych

W algebrze rozważa się czasami struktury algebraiczne które dodatkowo są 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$ ,
- jeśli $a\leq b$ to $a+c \leq b+c$ , oraz
- jeśli $a\leq b$ i $0\leq c$ to $a\cdot c \leq b\cdot c$ .

Zobacz także

Teoria mnogości