Zestaw częściowo zamówiony

W matematyce , ą częściowo uporządkowanym (czasami nazywane poset od angielskiej częściowy porządek ) formalizuje i uogólnia intuicyjne pojęcie porządku lub ułożeniu między elementami zestawu . Zbiór częściowo uporządkowany to zbiór zaopatrzony w relację kolejności wskazującą, że dla pewnych par elementów jeden jest mniejszy od drugiego. Wszystkie elementy niekoniecznie są porównywalne, w przeciwieństwie do zestawu dostarczanego z całkowitym zamówieniem .

Jeśli zbiór jest skończony, mamy graficzną reprezentację częściowo uporządkowanego zbioru, diagram Hassego , co może ułatwić pracę nad nim. Jeśli zbiór jest nieskończony, możemy narysować część jego diagramu Hassego.

Definicja i przykłady

Definicja

Porządek (lub porządek częściowy) to relacja binarna na zbiorze P, który jest zwrotny , antysymetryczny i przechodni . Zauważono ≤.

Trzy poprzednie aksjomaty zostały przepisane:

1. a ≤ a (refleksyjność).
2. Jeśli a ≤ b i b ≤ a , to a = b (antysymetria).
3. Jeśli a ≤ b i b ≤ c , to a ≤ c (przechodniość).

Więc niekoniecznie jest to całkowite zamówienie .

Przykłady

• Zbiór liczb całkowitych naturalnych, z podzielnością, jest zbiorem nieskończonym, częściowo uporządkowanym.
• Zbiór osób z pokrewieństwem pochodzenia genealogicznego jest zbiorem częściowo uporządkowanym. Na przykład dwie siostry są gorsze od swojej matki, ale nie można ich porównywać.
• Zestaw częściami danego zestawu , pod warunkiem, z włączeniem, tworzy się częściowy porządek. Jeśli dany zbiór jest skończony, to jego zbiór części jest skończony (a dokładniej , mamy ). Poniższy rysunek przedstawia schemat Hassego zestawu z 3 elementami.#W=nie{\ displaystyle \ # A = n}#P.(W)=2nie{\ Displaystyle \ #P (A) = 2 ^ {n}}

• Aby wziąć konkretny przypadek (a nawet izomorficzny ) poprzedniego przykładu, grupa osób obdarzonych tą relacją może oddać krew, tworząc zbiór częściowo uporządkowany według systemów ABO i Rhesus . Elementy x , y i z w bardziej ogólnym poprzednim przykładzie są tworzone przez antygeny A, B i D (Rh +) osobnika. Na przykład osoba z grupy O + może dawać odbiorcy z grupy B +, ale żadna z nich nie może dawać ani otrzymywać od osoby z grupy A-.
• Zbiorem liczb zespolonych podanych w następującym stosunku rzędu częściowo uporządkowane: .w+jab<w′+jab′⇔{w<w′b<b′{\ Displaystyle a + ib <a '+ ib' \ Leftrightarrow \ left \ {{\ begin {matrix} a <a '\\ b <b' \ end {matrix}} \ right.}

Na przykład nie możemy porównać 1 i i . Rozkaz ten nie jest zgodny z ciała struktury o . VS{\ displaystyle \ mathbb {C}}

• Zbiór funkcji w , zaopatrzony w relację porządku si , jest częściowo uporządkowanym zbiorem nieskończonym. Intuicyjnie, jedna funkcja jest mniejsza niż inna, jeśli jej krzywa jest zawsze poniżej drugiej krzywej. Możemy uogólnić ten przykład na funkcje zbioru X w częściowo uporządkowanym zbiorze P.R{\ displaystyle \ mathbb {R}}R{\ displaystyle \ mathbb {R}}fa<sol{\ displaystyle f <g}∀x,fa(x)<sol(x){\ Displaystyle \ forall x, f (x) <g (x)}
• Zbiór przegród danego zbioru jest częściowo uporządkowany, w kolejności określonej przez uściślenie przegród: z definicji przegroda jest drobniejsza od innej, jeśli dzieli części drugiego na mniejsze części.
• Możemy dostarczyć zbiór wielomianów z n zmiennymi z relacją częściowego rzędu. Zaczynamy od porównania jednomianów z n zmiennymi w porządku leksykograficznym wywołanym przez (ten porządek leksykograficzny jest całkowity). Porównujemy dwa wielomiany i stwierdzamy, że jest on ściśle mniejszy, niż gdyby jakikolwiek niezerowy jednomian funkcji był ściśle mniejszy niż jakikolwiek niezerowy jednomian funkcji . Ta relacja porządku wielomianów jest częściowa.R[X1,...,Xnie]{\ displaystyle R [X_ {1}, ..., X_ {n}]}1<X1<X2<...<Xnie{\ displaystyle 1 <X_ {1} <X_ {2} <... <X_ {n}}P.{\ displaystyle P}Q{\ displaystyle Q}P.{\ displaystyle P}Q{\ displaystyle Q}P.{\ displaystyle P}Q{\ displaystyle Q}

Specyfika zestawów częściowo uporządkowanych

Największy element , maksymalny element i górna granica

Niech P będzie zbiorem częściowo uporządkowanym:

• Element a z P jest większym elementem, jeśli dla dowolnego elementu b z P, b ≤ a. Częściowo zamówiony zestaw może mieć tylko jeden większy element.

• Element a z P jest elementem maksymalnym, jeśli nie ma elementu b z P, takiego, że b> a. Jeśli P ma większy element, jest to unikalny maksymalny element P.

• Dla podzbioru A z P, element x z P jest górną granicą A, jeśli a ≤ x dla dowolnego elementu a z A. x niekoniecznie należy do A. Największym elementem P, s ', jaki istnieje, jest górna granica P.

Przykład  : rozważ zbiór dodatnich liczb całkowitych, uporządkowanych według dzielenia. 1 to najmniejszy element. Z drugiej strony ten zestaw nie ma większego elementu. Gdybyśmy teraz wykluczyli element 1, częściowo uporządkowany zbiór nie miałby już mniejszego elementu, ale nieskończoność elementów minimalnych: liczb pierwszych .

Jeśli E jest zbiorem częściowo uporządkowanym, niekoniecznie istnieje większy element. Jeśli E jest skończonym, częściowo uporządkowanym zbiorem, będzie zawierał co najmniej jeden maksymalny element. Jeśli E jest nieskończonym zbiorem indukcyjnym , możemy użyć lematu Zorna, aby mieć maksymalny element.

Określone warunki na największych elementach i najmniejszych elementach częściowo uporządkowanego zbioru prowadzą do definicji kraty .

Z tego samego powodu otrzymujemy najmniejszy element, elementy minimalne i dolną granicę.

Porównywalność

Jeśli a ≤ b lub a b, to a i b są porównywalne. Na powyższym diagramie Hassego {x} i {x, y, z} są porównywalne, podczas gdy {x} i {y} nie. Częściowa kolejność, w której dowolna para elementów jest porównywalna, nazywana jest porządkiem całkowitym , a zbiór nazywany jest ciągiem . Zbiór, w którym nie można znaleźć porównywalnej pary, nazywany jest antichainem (np. Zbiór {{x}, {y }, {z}} na powyższym rysunku) ≥{\ displaystyle \ geq}

Poprawa

Mówimy, że element a jest pokryty elementem b, który jest zapisywany jako a <: b, jeśli a jest ściśle mniejsze od b i nie ma elementu c wstawionego między nimi. Na przykład {x} jest pokryty przez {x, z} na powyższym rysunku, ale nie przez {x, y, z}.

Powiązania z prostymi kompleksami

Ważna klasa kompleksów upraszczających pochodzi ze skończonych zbiorów częściowo uporządkowanych. Zespół rzędu D (P) skończonego, częściowo uporządkowanego zbioru P definiujemy jako zbiór łańcuchów P. Kompleks rzędu jest w trywialnym stopniu kompleksem uproszczonym.

Badanie zbioru częściowo uporządkowanego dostarcza informacji o jego zespole porządkowym, dlatego interesujące jest badanie kompleksu upraszczającego jako zespołu porządkowego zbioru częściowo uporządkowanego.

Działanie na częściowo zamówionych zestawach

Produkt kartezjański częściowo zamówiony zestaw

Aby wyeliminować mnogość możliwych relacji kolejności w ramach częściowo uporządkowanego zbioru, możemy zdefiniować trzy różne reguły:

• Celu leksykograficznym ( , b ) ≤ ( c , d ), jeżeli < C lub ( = c i b ≤ d );
• Rząd mnożenia : ( a , b ) ≤ ( c , d ) jeśli a ≤ c i b ≤ d ;
• Zwrotny zamknięcie z bezpośrednim produktem ( , b ) ≤ ( c , d ) jeśli ( < c i b < d ) lub ( = c i b = d ).

Wszystkie te zasady dotyczą również produktów składających się z więcej niż dwóch częściowo zamówionych zestawów.

Lokalna skończoność

O częściowo uporządkowanym zbiorze E mówi się, że jest lokalnie skończony, jeśli dla wszystkich przedział jest skończony. To założenie umożliwia uogólnienie wzoru inwersji Möbiusa . x,y∈mi{\ Displaystyle x, y \ w E}[x,y]{\ displaystyle [x, y]}

Bibliografia

(en) Richard P. Stanley , Enumerative Combinatorics , vol.  1 [ szczegóły wydań ] ( prezentacja online )

Zobacz też

• Diagram Hassego
• Ideal Frink  (en)
• Zamów relację
• Krata (zamówiony zestaw)

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">