Porządek liniowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Ilustracja porządku liniowego

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

Definicje[edytuj | edytuj kod]

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 \or 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 \and 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 zachodzi
    \forall_{x\in X}\; \exists_{y\in X}\; x \prec y oraz \forall_{x\in X}\; \exists_{y\in X}\; y \prec x;
  • 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[edytuj | edytuj kod]

(x_1,y_1)\leqslant_{\rm lex} (x_2,y_2) \iff  x_1<x_2 \or (x_1=x_2 \and y_1\leqslant y_2).

Własności[edytuj | edytuj kod]

  • 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[edytuj | edytuj kod]

Iloczyn leksykograficzny[edytuj | edytuj kod]

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 \ne 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[edytuj | edytuj kod]

Information icon.svg Zobacz też: 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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,{}^\prime,\varnothing,X) jest nazywana algebrą przedziałową wyznaczoną przez (X,\sqsubseteq).

Topologia porządkowa[edytuj | edytuj kod]

Information icon.svg Osobny artykuł: 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 (T2) i jest nawet przestrzenią T5.[1]

Struktury algebraiczne[edytuj | edytuj kod]

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

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.

Zobacz też[edytuj | edytuj kod]

Przypisy

  1. Steen-Seebach, Counterexamples in topology