AA3-4(Posets) (PDF-лекции от Гурова)

ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЧасть IVЧастично упорядоченныемножества1 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОсновные понятия теории ч.у. множествРазделы1Основные понятия теории ч.у. множеств2Операции над ч.у. множествами3Линеаризация4Задачи c решениями5Модели Крипке6Что надо знать2 / 76ПРИКЛАДНАЯ АЛГЕБРА.

Часть IV: Частично упорядоченные множестваОсновные понятия теории ч.у. множеств3 / 76Частично упорядоченные множества: определение и примерыОпределениеПару P = h P, 6 i, где P — непустое множество, а 6 —рефлексивное, антисимметричное и транзитивное бинарноеотношение на нём, называют частично упорядоченныммножеством (сокращённо ч.у. множеством).Рефлексивность (R): x 6 x;Антисимметричность (AS): (x 6 y) N (y 6 x) ⇒ x = y;Транзитивность (T): (x 6 y) N (y 6 z) ⇒ x 6 z.Примерыh P(M ), ⊆ i — классический пример ч.у.

множества(упорядочивание множеств по включению, M 6= ∅);h N, 6 i и h N, | i — два упорядочивания одного множества.ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОсновные понятия теории ч.у. множествПредпорядкиВопрос:Пусть M — множество людей, h(x) — рост, а w(x) — весчеловека x.Определим на отношение ρ на M :xρy ⇒ (h(x) 6 h(y)) N (w(x) 6 w(y)).Является ли ρ отношением частичного порядка на M ?Ответ. Нет. ρ — рефлексивно и транзитивно, но не являетсяантисимметричным отношением: xρy N yρx 6⇒ x = y (могутнайтись два человека с одинаковым ростом и весом).Отношения со свойствами (R) и (T) называют предпорядками.defa < b = (a 6 b)N(a 6= b)4 / 76ПРИКЛАДНАЯ АЛГЕБРА.

Часть IV: Частично упорядоченные множестваОсновные понятия теории ч.у. множествЧ.у. множество P = h P, 6 i — основные понятия:если (x 6 y) ∨ (y 6 x), то x и y сравнимы (x ∼ y), иначеони несравнимы (x y);полный (линейный) порядок, если ∀x, y (x ∼ y);если в P нет ни одной пары различных сравнимыхэлементов, то это тривиально упорядоченное множество;x непосредственно предшествует y ( y непосредственноследует за x), если x 6 z 6 y ⇒ (z = x) ∨ (z = y) (x l y);{ x ∈ P | a 6 x 6 b } — интервал [ a, b ];defv1 < . . .

< vn = [v1 , . . . , vn ] — цепь n, а совокупностьпопарно несравнимых элементов — антицепь в P;цепь максимальная (насыщенная), если при добавлении кней любого элемента она перестаёт быть цепью;def> — двойственный к 6 порядок: 6d = >.5 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОсновные понятия теории ч.у. множеств6 / 76Диаграммы Хассе◦◦◦◦◦◦◦◦[[[◦[[ ◦[◦Диаграммы Хассе 4-х нетривиальных непомеченныхтрёхэлементных ч.у.

множеств.◦ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОсновные понятия теории ч.у. множеств7 / 76Диаграммы Хассе: да или нетВопрос: это диаграммы Хассе?A ◦ AAAA◦ [◦[◦◦ehh 444c hh AAA444 dhA A abОтвет. Нет! Правильно:A ◦ AAAA◦ [◦[◦◦df[[[[ cabПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОсновные понятия теории ч.у. множествЧ.у. множества: особые элементыОпределениеЭлемент u ∈ P ч.у. множества h P, 6 i называют:максимальным, если u 6 x ⇒ u = x,минимальным, если u > x ⇒ u = x,наибольшим, если x 6 u,наименьшим, если x > uдля любых x ∈ P .Элемент наибольший, если все другие элементы содержатся внём,и он максимальный, если нет элементов, содержащих его(аналогично для наименьшего и минимального элементов).8 / 76ПРИКЛАДНАЯ АЛГЕБРА.

Часть IV: Частично упорядоченные множестваОсновные понятия теории ч.у. множествОсобые элементы ч.у. множества: пример• — максимальные элементы;• — минимальный и наименьший элемент;Наибольший (1) и наименьший (0) — граничные элементы.В конечном ч.у. множестве имеется как минимум по одномумаксимальному и минимальному элементу.9 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОсновные понятия теории ч.у. множествЧ.у. множество h { 1, . . .

, 18}, | i16[[ 12 [[ 8[[96 [4' 15 [AA '10''' 14'''[A''[[''['A'''A''A'A' 13' '3 hh 11 2 [57' 17Ahhhh [''A'hhhh[ AA'A'''hh 'A A''1811 — наименьший элемент, • — максимальные.10 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОсновные понятия теории ч.у. множествРанжированные ч.у. множестваЦепное условие Жордана-ДедекиндаВсе максимальные цепи между двумя данными элементамилокально конечного ч.у.

множества имеют одинаковую длину.Если ч.у. множество удовлетворяет условиюЖордана-Дедекинда и имеет наименьший элемент 0, то оноранжируемо, т.е. на нём можно определить функцию ранга ρ:12ρ(0) = 0;a l b ⇒ ρ(b) = ρ(a) + 1и такое множество имеетслои.Если множество ранжируемо, то любойего слой (но не только!) является антицепью.11 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОсновные понятия теории ч.у. множествПорядковые гомоморфизмыОпределениеОтображение ϕ : P → Pсоответственно0носителей ч.у. множеств называетсяизотонным (монотонным, порядковым гомоморфизмом),если x 6 y ⇒ ϕ(x) 6 ϕ(y);обратно изотонным, если ϕ(x) 6 ϕ(y) ⇒ x 6 y;антиизотонным, если x 6 y ⇒ ϕ(x) > ϕ(y).Если ϕ изотонно, обратно изотонно и инъективно, то этовложение или (порядковый) мономорфизм (символическиϕP ,→ P 0 ).Сюръективный мономорфизм — (порядковый) изоморфизмϕ(символически P ∼= P 0 или P ∼= P 0 ).Изоморфизм ч.у.

множества в себя — (порядковый)автоморфизм.12 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОсновные понятия теории ч.у. множествИдеалы и фильтры ч.у. множествОпределениеПодмножество J элементов ч.у. множества h P, 6 iназывается его (порядковым) идеалом, если(x ∈ J) N (y 6 x) ⇒ y ∈ J.Подмножество F элементов P называется его (порядковым)фильтром, если(x ∈ F ) N (x 6 y) ⇒ y ∈ F.∅ и всё ч.у. множество P — порядковые идеалы.Важное свойство: объединение и пересечение порядковыхидеалов есть порядковый идеал.Обозначение: J(P ) — множество всех порядковых идеалов ч.у.множества P .13 / 76ПРИКЛАДНАЯ АЛГЕБРА.

Часть IV: Частично упорядоченные множестваОсновные понятия теории ч.у. множеств14 / 76КонусыОпределениеПусть h P, 6 i — ч.у. множество и A ⊆ P . Множества AM и AOAM = x ∈ P | ∀ a ( a 6 x) и AO = x ∈ P | ∀ a ( x 6 a)AAназываются верхним и нижним конусами множества A, а ихэлементы — верхними и нижними гранями множества Aсоответственно.Для одноэлементного множества A = {a} — aM и aO .Понятно, что если a 6 b, то aM ∩ bO = [ a, b ].xO = hxi = J(x) — идеал, а xM — фильтр P ;такие идеалы и фильтры называют главными.defКонечнопорождённый идеал: h a1 , .

. . , ak i =k[i=1ai O .ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОсновные понятия теории ч.у. множествТочные граниОпределениеПусть h P, 6 i — ч.у. множество и A ⊆ P .Наименьший элемент в AM называется точной верхнейгранью множества A (символически sup A).Наибольший элемент в AO называется точной нижнейгранью множества A (символически inf A).Пример ( sup A и/или inf A могут и не существовать){a, b}M = {c, d}, но множество {c, d}не имеет инфимума ⇒ sup{a, b} отсутствует.Аналогично, отсутствует inf{c, d}.15 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОперации над ч.у. множествамиРазделы1Основные понятия теории ч.у. множеств2Операции над ч.у.

множествами3Линеаризация4Задачи c решениями5Модели Крипке6Что надо знать16 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОперации над ч.у. множествами17 / 76Пересечениеh P, 61 i ∩ h P, 62 i = h P, 61 ∩ 62 i.cbad\bacd=cbadСвойства ч.у. множеств могут не сохраняются при пересечении.Например, «быть цепью»: если P — цепь, тогда P d — такжецепь, а P ∩ P d — тривиально упорядоченное множество.ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОперации над ч.у. множествамиПрямая суммаP = h P, 6P i и Q = h Q, 6Q i — два ч.у. множества, причёмP ∩ Q = ∅.P + Q = h P ∪ Q, 6P ∨ 6Q i.Справедливы соотношенияP +Q ∼= P +R ⇒ Q ∼= Rи(P + Q)d ∼= P d + Rd .nP — прямая сумма n экземпляров P,n1 — n-элементная антицепь.Диаграмма прямой суммы состоит из двух диаграммсоответствующих ч.у.

множеств, рассматриваемых как единаядиаграмма.Ч.у. множество, не являющееся прямой суммой некоторых двухдругих ч.у. множеств, называется связным.18 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОперации над ч.у. множествамиПрямое произведение: определениеПрямым или декартовым произведением ч.у. множествP = h P, 6P i и Q = h Q, 6Q i называется множествоP × Q = h P × Q, 6 i,где (p, q) 6 (p 0 , q 0 ) ⇔ (p 6P p 0 )N(q 6Q q 0 ).Pn — прямое произведение n экземпляров P: B n = 2n .Если P , Q ранжированы и их ранговые функции суть ρP и ρQ ,то P × Q также ранжировано и ρ(x1 , x2 ) = ρP (x1 ) + ρQ (x2 );∼ Q×PСправедливы соотношения P × Q =P ×R ∼= Q×R ⇒ P ∼= Q,Pn ∼= Qn ⇒ P ∼= Q.19 / 76ПРИКЛАДНАЯ АЛГЕБРА.