Частично подреден комплект
Частично подреден комплект - математическа концепция, която формализира интуитивните идеи за подреждане, подреждане в определена последователност и др. Неформално казано, набор е частично подреден, ако е посочено кои елементи последвам (Повече ▼ и т.н.) за какво. В този случай в общия случай може да се окаже, че някои двойки елементи не са свързани с релацията "следва след".
Абстрактен пример е колекцията от подмножества от набор от три елемента \ < x, y, z\>, подредени чрез включване.
Като пример "от живота" могат да бъдат посочени много хора, наредени според връзката "да бъде прародител".
Определение и примери
Поръчката, или частичен ред, на множество M имаме предвид двоично отношение \ varphi на M (дефинирано от някакъв набор R_ \ подмножество M \ пъти M), което отговаря на следните условия [1]:
- Рефлексивност: \ forall a \; (a \ varphi a)
- Преходност: \ forall a, b, c \; (a \ varphi b) \ wedge (b \ varphi c) \ Rightarrow a \ varphi c
- Антисиметрия: \ forall a, b \; (a \ varphi b) \ wedge (b \ varphi a) \ Rightarrow a = b
Извиква се множеството M, за което е посочено отношението за частичен ред частично подредени (англ. частично подреден комплект, набор ). За да бъдем съвсем точни [2], тогава частично подреден набор е двойка \ langle M, \ varphi \ rangle, където M е набор и \ varphi е частична връзка за подреждане на M .
Терминология и нотация
Отношението за частичен ред обикновено се обозначава със символа \ leqslant, подобно на отношението по-малко или равно на набор от реални числа. Освен това, ако a \ leqslant b, тогава те казват, че елементът a не надвишава б, или че а подчинен б .
Ако a \ leqslant b и a \ neq b, тогава те пишат a и казват, че a по-малко б, или че а строго подчинен б .
Понякога, за да се разграничи произволен ред на набор от добре познатата връзка „по-малко или равно“ на множество реални числа, вместо \ leqslant и да се използват съответните специални символи \ preccurlyeq и \ prec, съответно.
Строг и свободен ред
Извиква се и връзка, отговаряща на условията на рефлексивност, транзитивност и антисиметрия не е строг, или рефлексивен ред. Ако условието за рефлексивност е заменено с условието антирефлексивност:
\ forall a \; \ neg (a \ varphi a)
тогава получаваме определението строг, или антирефлексна поръчка.
Ако \ leqslant е не-строго подреждане на множеството M, тогава релацията, дефинирана като:
е строга заповед за М. И обратно, ако е строг ред, тогава връзката \ leqslant, дефинирана като
е свободна поръчка.
Следователно е все едно - да зададете свободен ред на снимачната площадка или строг ред. Резултатът е същата структура. Единствената разлика е в терминологията и обозначенията.
\ vartriangleright Както бе споменато по-горе, множеството реални числа \ mathbb е частично подредено според релацията "по-малко или равно" \ leqslant .
\ vartriangleright Нека M е множеството от всички реално оценени функции, дефинирани на сегмента [a, b], т.е. функции на формата
f \ двоеточие [a, b] \ to \ mathbb
Въвеждаме отношението на реда \ leqslant на M, както следва. Казваме, че f \ leqslant g, ако f (x) \ leqslant g (x) е валидно за всички x \ в [a, b]. Очевидно въведената релация всъщност е релация на частичен ред.
\ vartriangleright Нека M е някакъв набор. Наборът от \ mathcal
(M) от всички подмножества на M (т.нар. Boolean), частично подредени от включването M \ subseteq N .
\ vartriangleright Наборът от всички естествени числа \ mathbb е частично подреден по отношение на делимостта m \ mid n .
Свързани определения
Несравними елементи
Ако a и b са реални числа, тогава се осъществява една и само една от връзките:
Ако a и b са елементи на произволно частично подредено множество, тогава има четвърта логическа възможност: нито едно от горните три отношения не е изпълнено. В този случай се извикват елементите a и b несравним. Например, ако M е набор от реалнозначени функции на сегмента [0,1], тогава елементите f (x) = x и g (x) = 1-x ще бъдат несравними. Възможността за съществуване на несравними елементи обяснява значението на термина „Частично подреден комплект“.