Porządek liniowy


Porządek liniowy w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do 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.

Spis treści

Definicje | edytuj kod

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

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

Parę uporządkowaną ( X , ) {\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

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

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

  • gęstym, jeśli zachodzi x , y X , x y z A x z y ; {\displaystyle \forall _{x,y\in X,x\prec y}\;\exists _{z\in A}\;x\prec z\prec y;}
  • ograniczonym z góry, jeśli x X a A a x . {\displaystyle \exists _{x\in X}\;\forall _{a\in A}a\preccurlyeq x.}

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

  • porządkiem bez końców, jeśli w X {\displaystyle X} nie ma tak elementu najmniejszego, jak i największego, tzn. jeśli zachodzi x X y X x y {\displaystyle \forall _{x\in X}\;\exists _{y\in X}\;x\prec y} oraz x X y X y x ; {\displaystyle \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 {\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 X {\displaystyle X} jest gęstym podzbiorem X . {\displaystyle X.}

Przykłady | edytuj kod

( x 1 , y 1 ) l e x ( x 2 , y 2 ) x 1 < x 2 ( x 1 = x 2 y 1 y 2 ) . {\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 | edytuj kod

  • Jeśli {\displaystyle \sqsubseteq } jest porządkiem liniowym na zbiorze X {\displaystyle X} oraz Y X , {\displaystyle Y\subseteq X,} to zawężenie Y {\displaystyle \sqsubseteq _{Y}} porządku {\displaystyle \sqsubseteq } do zbioru Y {\displaystyle Y} jest porządkiem liniowym na Y . {\displaystyle 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 , ) {\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 ( Y , ) {\displaystyle (Y,\leqslant )} taki że X Y {\displaystyle X\subseteq Y} i zawężenie X {\displaystyle \leqslant _{X}} zgadza się z {\displaystyle \sqsubseteq } oraz X {\displaystyle X} jest gęstym podzbiorem Y . {\displaystyle Y.}
Porządek ( Y , ) {\displaystyle (Y,\leqslant )} jest jedyny z dokładnością do izomorfizmu.

Działania | edytuj kod

Iloczyn leksykograficzny | edytuj kod

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

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

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

 Zobacz też: ultraprodukt.

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

x F y F { s S : x s y s } F {\displaystyle x_{F}\leqslant y_{F}\Leftrightarrow \{s\in S\colon x_{s}\leqslant y_{s}\}\in F}

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

Zastosowania | 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 kod

Niech ( X , ) {\displaystyle (X,\sqsubseteq )} będzie porządkiem liniowym, w którym istnieje element najmniejszy. Niech dla x , y X { } {\displaystyle x,y\in X\cup \{\infty \}} symbol x , y {\displaystyle [x,y[} oznacza zbiór { z X : x z y } , {\displaystyle \{z\in X\colon x\sqsubseteq z\sqsubset y\},} tzn. przedział lewostronnie domknięty w X . {\displaystyle X.}

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

Topologia porządkowa | edytuj kod

 Osobny artykuł: topologia porządkowa.

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

B = { x , y : x y } { , x : x X } { x , : x X } { X } {\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 X {\displaystyle X} i jest zamknięta ze względu na branie przekrojów skończonych. Dlatego też B {\displaystyle {\mathcal {B}}} jest bazą pewnej topologii τ {\displaystyle \tau } na X . {\displaystyle 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 kod

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 , , ) {\displaystyle (G,\circ ,\leqslant )} taka, że ( G , ) {\displaystyle (G,\circ )} jest grupą, a {\displaystyle \leqslant } jest porządkiem liniowym na G , {\displaystyle G,} przy czym dla dowolnych a , b , c G {\displaystyle a,b,c\in G} jeśli a b , {\displaystyle a\leqslant b,} to zarówno a c b c , {\displaystyle a\circ c\leqslant b\circ c,} jak i c a c b . {\displaystyle c\circ a\leqslant c\circ b.}
  • Ciało uporządkowane to szóstka uporządkowana ( F , + , , 0 , 1 , ) , {\displaystyle (F,+,\cdot ,0,1,\leqslant ),} gdzie ( F , + , , 0 , 1 ) {\displaystyle (F,+,\cdot ,0,1)} jest ciałem, a {\displaystyle \leqslant } jest porządkiem liniowym na F , {\displaystyle F,} w którym dla dowolnych a , b , c F {\displaystyle a,b,c\in F} spełnione są warunki:
jeśli a b , {\displaystyle a\leqslant b,} to a + c b + c {\displaystyle a+c\leqslant b+c} oraz jeśli a b {\displaystyle a\leqslant b} i 0 c , {\displaystyle 0\leqslant c,} to a c b c . {\displaystyle a\cdot c\leqslant b\cdot c.}

Zobacz też | edytuj kod

Przypisy | edytuj kod

  1. Steen-Seebach, Counterexamples in topology.
Na podstawie artykułu: "Porządek liniowy" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy