Częściowo zamówiony zestaw - Partially ordered set

${\displaystyle \leq}$

$${\displaystyle a\leq b{\tekst{jeśli}}a<b{\tekst{lub}}a=b.}$$

Podwójne zamówienia

Podwójnego (lub przeciwnie ) częściowego względem kolejności określa się, pozwalając być

${\ Displaystyle (P, R ^ {\ tekst {op}})}$

${\ Displaystyle (P, R)}$

${\ Displaystyle R ^ {\ tekst {op}}}$

${\ Displaystyle R}$

${\ Displaystyle xR ^ {\ tekst {op}} y}$

${\ Displaystyle yRx}$

Notacja

Możemy rozważyć poset jako 3-krotkę , a nawet 5-krotkę , gdzie i są nieścisłymi relacjami rzędu częściowego, i są ścisłymi relacjami rzędu częściowego, a liczba dualna is , i jest podobnie podwójna względem siebie. ${\displaystyle (P,\leq,<)}$${\displaystyle (P,\leq,<,\geq,>)}$${\displaystyle (P,\leq)}$${\displaystyle (P,\geq)}$${\ Displaystyle (P <)}$${\ Displaystyle (P>)}$${\displaystyle (P,\geq)}$${\displaystyle (P,\leq)}$${\ Displaystyle (P <)}$${\ Displaystyle (P>)}$

Dowolna z czterech częściowych relacji porządku w danym zbiorze jednoznacznie determinuje pozostałe trzy. Można więc na zasadzie notacji napisać lub i założyć, że pozostałe relacje są odpowiednio zdefiniowane. Najczęstsze jest definiowanie za pomocą nieścisłego porządku częściowego . Niektórzy autorzy używają innych symboli niż takie, jak lub w celu odróżnienia zamówień częściowych od zamówień całkowitych. ${\displaystyle \leq,<,\geq,{\text{i}}>}$${\displaystyle (P,\leq)}$${\ Displaystyle (P <)}$${\displaystyle \leq}$${\displaystyle \leq}$${\displaystyle \sqsubseteq}$${\displaystyle \preceq}$

W odniesieniu do zamówień częściowych, nie powinny być traktowane jako

${\displaystyle \leq}$

${\displaystyle>}$

${\displaystyle>}$

${\displaystyle \leq}$

${\displaystyle \leq}$

${\displaystyle>}$

${\displaystyle \leq}$

${\displaystyle \leq}$

Przykłady

Standardowe przykłady posetów powstających w matematyce obejmują:

• W liczbami rzeczywistymi , lub w ogóle żadnego całkowicie uporządkowanego zbioru, uporządkowane według standardu o mniej niż lub równy względem ≤, to nie Dokładna kolejność częściowo.
• Na liczbach rzeczywistych zwykła relacja

Znanym przykładem zbioru częściowo uporządkowanego jest zbiór osób uporządkowanych według potomków genealogicznych . Niektóre pary ludzi są w relacji potomek-przodek, ale inne pary są nieporównywalne, a żadne z nich nie jest potomkiem drugiego.

Zamówienia na produkt kartezjański częściowo zamówionych zestawów

Rys.3 Porządek leksykograficzny włączony${\ Displaystyle \ mathbb {N} \ razy \ mathbb {N}}$

Rys.4 Zamówienie produktu włączone${\ Displaystyle \ mathbb {N} \ razy \ mathbb {N}}$

Rys.5 Odruchowe zamknięcie ścisłej bezpośredniej kolejności produktów na elementach objętych (3,3) i obejmujących (3,3) są podświetlone odpowiednio na zielono i czerwono.${\ Displaystyle \ mathbb {N} \ razy \ mathbb {N}}.$

W kolejności rosnącej siły, tj. malejących zbiorów par, trzy z możliwych cząstkowych rzędów na iloczynie kartezjańskim dwóch częściowo uporządkowanych zbiorów to (patrz Rys. 3-5):

• porządku leksykograficznego ( ,

Wszystkie trzy można podobnie zdefiniować dla iloczynu kartezjańskiego więcej niż dwóch zbiorów.

Po zastosowaniu do uporządkowanych przestrzeni wektorowych nad tym samym ciałem wynikiem jest w każdym przypadku również uporządkowana przestrzeń wektorowa.

Zobacz także zamówienia na produkt kartezjański kompletnie zamówionych zestawów .

Sumy częściowo uporządkowanych zbiorów

Innym sposobem na połączenie dwóch (rozłącznych) pozycji jest suma porządkowa (lub suma liniowa ), Z = X ⊕ Y , zdefiniowana na połączeniu zbiorów bazowych X i Y według rzędu a ≤ _Z b wtedy i tylko wtedy, gdy:

• a , b ∈ X gdzie a ≤ _X b , lub
• a , b ∈ Y z a ≤ _Y b , lub
• ∈ X i b ∈ Y .

Jeśli dwa posety są uporządkowane , to ich suma porządkowa też.

Szeregowo-równoległe rzędy częściowe są tworzone z operacji sumy porządkowej (w tym kontekście nazywanej składaniem szeregów) i innej operacji zwanej składaniem równoległym. Kompozycja równoległa to rozłączny związek dwóch częściowo uporządkowanych zestawów, bez relacji porządku między elementami jednego zestawu a elementami drugiego zestawu.

Pojęcia pochodne

W przykładach użyto posetu składającego się ze

${\displaystyle ({\mathcal {P}}(\{x,y,z\}),\subseteq)}$

${\displaystyle \{x,y,z\}}$

• a jest powiązane z b gdy a ≤ b . Nie oznacza to, że b jest również powiązane z a , ponieważ relacja nie musi być symetryczna . Na przykład jest powiązany, ale nie odwrotnie.${\ Displaystyle \ {x \}}$${\displaystyle \{x,y\}}$
• a i b są porównywalne, jeśli a ≤ b lub b ≤ a . W przeciwnym razie są nieporównywalne . Na przykład i są porównywalne, podczas gdy i nie są.${\ Displaystyle \ {x \}}$${\displaystyle \{x,y,z\}}$${\ Displaystyle \ {x \}}$${\ Displaystyle \ {y\}}$
• Całkowita kolejność lub liniowy porządek częściowy porządkowy w którym każda para elementów są porównywalne, np trychotomia ładowni. Na przykład liczby naturalne w ich standardowym porządku.
• Łańcuch jest podzbiorem poset który jest całkowicie uporządkowanym. Na przykład jest łańcuchem.${\ Displaystyle \ {\ {\, \}, \ {x \}, \ {x, y, z \} \}}$
• Antyłańcuch jest podzbiorem poset w którym żadne dwa oddzielne elementy, mogą być porównywane. Na przykład zbiór singletonów ${\displaystyle \{\{x\},\{y\},\{z\}\}.}$
• Mówi się, że element a jest ściśle mniejszy niż element b , jeśli a ≤ b i Na przykład jest ściśle mniejszy niż${\displaystyle a\neq b.}$${\ Displaystyle \ {x \}}$${\displaystyle \{x,y\}.}$
• Mówi się, że element a jest pokryty innym elementem b , napisanym a ⋖ b (lub a <: b ), jeśli a jest ściśle mniejsze niż b i żaden trzeci element c nie mieści się między nimi; formalnie: jeśli a ≤ b i są prawdziwe, a

${\displaystyle a\neq b}$

${\displaystyle a\neq c\neq b.}$

${\ Displaystyle \ {x \}}$

${\displaystyle \{x,z\}}$

${\displaystyle \{x,y,z\}.}$

Ekstrema

Rys.6 Rysunek powyżej z usuniętymi największymi i najmniejszymi elementami. W tej zredukowanej pozie, górny rząd elementów to wszystkie elementy maksymalne , a dolny rząd to wszystkie elementy minimalne , ale nie ma elementu największego ani najmniejszego .

Istnieje kilka pojęć „największego” i „najmniejszego” elementu w posecie, w szczególności: ${\displaystyle P,}$

• Największy i najmniejszy element: Element jest

${\displaystyle \{x,y\}}$

${\displaystyle \{\{x\},\{y\}\}.}$

Rys.7 Nieujemne liczby całkowite uporządkowane według podzielności

Jako inny przykład rozważmy liczby całkowite dodatnie , uporządkowane według podzielności: 1 jest najmniejszym elementem, ponieważ dzieli wszystkie inne elementy; z drugiej strony ten poset nie ma największego elementu (chociaż gdyby w posecie umieścić 0, które jest wielokrotnością dowolnej liczby całkowitej, byłby to największy element; patrz rys. 7). Ten częściowo uporządkowany zbiór nie zawiera nawet elementów maksymalnych, ponieważ każde g dzieli na przykład 2 g , które jest od niego różne, więc g nie jest maksimum. Jeśli liczba 1 jest wykluczona, zachowując podzielność jako uporządkowanie na elementach większych niż 1, to wynikowy poset nie ma najmniejszego elementu, ale każda liczba pierwsza jest dla niego elementem minimalnym. W tym posecie 60 to górna granica (choć nie najmniejsza górna granica) podzbioru, która nie ma żadnego dolnego ograniczenia (ponieważ 1 nie znajduje się w posecie); z drugiej strony 2 jest dolną granicą podzbioru potęg 2, która nie ma żadnego górnego ograniczenia. ${\ Displaystyle \ {2,3,5,10 \}}$

Mapowania między częściowo uporządkowanymi zestawami

Rys.8 Mapa zachowująca porządek, ale nie odzwierciedlająca porządku (ponieważ f ( u ) ≼ f ( v ), ale nie u v ).${\displaystyle \leq}$

Rys.9 Izomorfizm porządku między dzielnikami 120 (częściowo uporządkowane przez podzielność) a podzbiorami domkniętymi przez dzielniki {2, 3, 4, 5, 8 } (częściowo uporządkowane przez uwzględnienie zbioru)

Biorąc pod uwagę dwa częściowo uporządkowane zbiory ( S , ≤ ) i ( T , ≼ ), funkcję nazywamy

${\ Displaystyle f: S \ do T}$

${\displaystyle x,y\ws}$

${\displaystyle x\leq y}$

${\ Displaystyle f: S \ do T}$

${\ Displaystyle g: T \ do U}$

${\displaystyle g\circ f:S\do U}$

${\ Displaystyle f: S \ do T}$

${\displaystyle x,y\ws}$

${\displaystyle x\leq y.}$

${\displaystyle f}$

${\displaystyle f}$

${\ Displaystyle f (x) = f (y)}$

${\displaystyle x\leq y{\tekst{i}}y\leq x}$

${\displaystyle x=y}$

${\displaystyle \leq.}$

${\ Displaystyle f: S \ do T}$

${\ Displaystyle f: S \ do T}$

${\ Displaystyle g: T \ do U}$

${\displaystyle g\circ f}$

${\displaystyle f\circ g}$

Na przykład odwzorowanie ze zbioru liczb naturalnych (uporządkowanych przez podzielność) na

${\ Displaystyle f: \ mathbb {N} \ do \ mathbb {P} (\ mathbb {N})}$

${\displaystyle x}$

${\displaystyle y}$

${\displaystyle x}$

${\ Displaystyle y.}$

${\ Displaystyle \ {2,3 \}}$

${\ Displaystyle g: \ mathbb {N} \ do \ mathbb {P} (\ mathbb {N})}$

${\ Displaystyle \ {4 \}}$

${\displaystyle g(\mathbb {N}).}$

${\ Displaystyle \ mathbb {N}}$

${\displaystyle g.}$

Liczba zamówień częściowych

Sekwencja A001035 w OEIS podaje liczbę zamówień częściowych na zbiorze n oznaczonych elementów:

Liczba n- elementowych relacji binarnych różnych typów

Elementy	Każdy	Przechodni	Zwrotny	Przed Sprzedaż	Częściowe zamówienie	Całkowite zamówienie w przedsprzedaży	Całkowite zamówienie	Relacja równoważności
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65 536	3994	4096	355	219	75	24	15
n	2 n 2		2 n 2 − n			${\textstyle \sum _{k=0}^{n}k!}$S ( n , k )	n !	${\textstyle \sum _{k=0}^{n}}$S ( n , k )
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

Liczba ścisłych zamówień częściowych jest taka sama jak zamówień częściowych.

Jeśli zliczenie jest wykonane tylko do izomorfizmu, otrzymuje się sekwencję 1, 1, 2, 5, 16, 63, 318, ... (sekwencja A000112 w OEIS ).

Rozszerzenie liniowe

Częściowa celu w zestawie jest

${\ Displaystyle \ Leq ^ {*}}$

${\ Displaystyle X}$

${\displaystyle \leq}$

${\ Displaystyle X}$

${\displaystyle x,y\wX}$

${\displaystyle x\leq y}$

${\ Displaystyle x \ leq ^ {*} r.}$

W informatyce algorytmy znajdowania liniowych wydłużeń rzędów cząstkowych (reprezentowanych jako rzędy osiągalności skierowanych grafów acyklicznych ) nazywane są sortowaniem topologicznym .

Skierowane grafy acykliczne

Ścisłe porządki częściowe odpowiadają bezpośrednio skierowanym grafom

${\displaystyle P}$

${\displaystyle \leq}$

W kategorii teoria

Każdy poset (i każdy wcześniej uporządkowany zbiór ) może być uważany za kategorię, w której dla obiektów i istnieje co najwyżej jeden

${\displaystyle x}$

${\displaystyle y}$

${\displaystyle x}$

${\ Displaystyle y.}$

${\ Displaystyle (y, z) \ circ (x, y) = (x, z).}$

Pozycje są sobie równoważne wtedy i tylko wtedy, gdy są izomorficzne . W posecie najmniejszy element, jeśli istnieje, jest obiektem początkowym , a największy, jeśli istnieje, jest obiektem końcowym . Ponadto każdy zestaw zamówiony w przedsprzedaży jest równoważny posetowi. Wreszcie, każda podkategoria poety jest zamknięta na izomorfizm .

Porządki cząstkowe w przestrzeniach topologicznych

Jeśli jest to częściowy porządek, który również został daną strukturę

${\displaystyle P}$

${\displaystyle \{(a,b):a\leq b\}}$

${\ Displaystyle P \ razy P.}$

${\displaystyle a_{i}\do a}$

${\displaystyle b_{i}\do b}$

${\displaystyle i}$

${\displaystyle a_{i}\leq b_{i}}$

${\displaystyle a\leq b.}$

Interwały

Odstęp w poset P jest podzbiorem I z P z właściwości, że dla każdego x i y w I i dowolnego Z w P , jeżeli x ≤ z ≤ Y , a z jest również I . (Ta definicja uogólnia definicję przedziału dla liczb rzeczywistych).

Dla w ≤ b The odcinkiem [ ,

Używając odpowiedniej ścisłej relacji "<", otwarty przedział ( a , b ) jest zbiorem elementów x spełniających a < x < b (tj. a < x i x < b ). Otwarty przedział może być pusty, nawet jeśli a < b . Na przykład otwarty przedział (1, 2) na liczbach całkowitych jest pusty, ponieważ nie ma liczb całkowitych I takich, że 1 < I < 2 .

W półotwartych przedziały [ ,

Czasami definicje są rozszerzane, aby umożliwić a > b , w którym to przypadku przedział jest pusty.

Przedział I jest ograniczony, jeśli istnieją elementy takie, że

${\displaystyle a,b\wp}$

Poset nazywamy lokalnie skończonym, jeśli każdy ograniczony przedział jest skończony. Na przykład liczby całkowite są lokalnie skończone zgodnie z ich naturalnym uporządkowaniem. Porządek leksykograficzny na produkcie kartezjańskim nie jest lokalnie skończony, ponieważ

${\ Displaystyle \ mathbb {N} \ razy \ mathbb {N}}$

${\displaystyle [a,b]=\{a,b\}.}$

Ta koncepcja przedziału w porządku częściowym nie powinna być mylona z konkretną klasą porządków częściowych, zwaną rzędami przedziałów .

Zobacz też

Uwagi

Cytaty

Bibliografia

• Davey, licencjat; Priestley, HA (2002). Wprowadzenie do Krat i Porządku (2nd ed.). Nowy Jork: Cambridge University Press. Numer ISBN 978-0-521-78451-1.
• Deshpande, Jayant V. (1968). „O ciągłości częściowego porządku” . Procedury Amerykańskiego Towarzystwa Matematycznego . 19 (2): 383–386. doi : 10.1090/S0002-9939-1968-0236071-7 .
• Schmidta, Gunthera (2010). Matematyka relacyjna . Encyklopedia Matematyki i jej Zastosowania. 132 . Wydawnictwo Uniwersytetu Cambridge. Numer ISBN 978-0-521-76268-7.
• Bernd Schröder (11 maja 2016). Zbiory uporządkowane: wprowadzenie z połączeniami od kombinatoryki do topologii . Birkhäuser. Numer ISBN 978-3-319-29788-0.
• Stanley, Richard P. (1997). Kombinatoryka enumeracyjna 1 . Studia Cambridge z matematyki zaawansowanej. 49 . Wydawnictwo Uniwersytetu Cambridge. Numer ISBN 0-521-66351-2.

Zewnętrzne linki

• Sekwencja OEIS A001035 (Liczba pozycji z n oznaczonymi elementami)
• Sekwencja OEIS A000112 (Liczba częściowo uporządkowanych zestawów ("poset") z n nieoznakowanymi elementami.)