AA3-4(Posets) (1127142)
Текст из файла
ПРИКЛАДНАЯ АЛГЕБРА. Часть 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ПРИКЛАДНАЯ АЛГЕБРА.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
