Лекции по прикладной алгебре. v2.0 (1127112), страница 24
Текст из файла (страница 24)
множествИдеалы и фильтры ч.у. множествОпределениеПодмножество J элементов ч.у. множества Ph P, 6 iназывается его (порядковым) идеалом, если(x ∈ J) N (y 6 x) ⇒ y ∈ J.328 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествИдеалы и фильтры ч.у. множествОпределениеПодмножество J элементов ч.у. множества Ph P, 6 iназывается его (порядковым) идеалом, если(x ∈ J) N (y 6 x) ⇒ y ∈ J.Подмножество F элементов P называется его (порядковым)фильтром, если(x ∈ F ) N (x 6 y) ⇒ y ∈ F.328 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у.
множествИдеалы и фильтры ч.у. множествОпределениеПодмножество J элементов ч.у. множества Ph 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.328 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у.
множеств329 / 432КонусыОпределениеПусть h P, 6 i — ч.у. множество и A ⊆ P . Множества AM и AOопределяемые условиямиAM = x ∈ P | ∀ a ( a 6 x) и AO = x ∈ P | ∀ a ( x 6 a)AAназываются верхним и нижним конусами множества A, а ихэлементы — верхними и нижними гранями множества Aсоответственно. Для одноэлементного множества A = {a}используются обозначения aM и aO .Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множеств329 / 432КонусыОпределениеПусть h P, 6 i — ч.у.
множество и A ⊆ P . Множества AM и AOопределяемые условиямиAM = 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 = J(x) — идеал; xM — фильтр P ; такие идеалы и фильтрыназывают главными.Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествТочные граниОпределениеПусть h P, 6 i — ч.у. множество и A ⊆ P .Наименьший элемент в AM называется точной верхнейгранью множества A (символически sup A).Наибольший элемент в AO называется точной нижнейгранью множества A (символически inf A).330 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у.
множествТочные граниОпределениеПусть 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}.330 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у. множествамиРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды331 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у. множествамиРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств332 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у. множествамиРаздел IIIОсновные понятия теории ч.у.
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать333 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у. множествами334 / 432Пересечениеh P, 61 i ∩ h P, 62 i = h P, 61 ∩ 62 i.cbad\bacd=bacdПрикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у. множествами334 / 432Пересечениеh P, 61 i ∩ h P, 62 i = h P, 61 ∩ 62 i.cbad\bacd=cbadСвойства ч.у. множеств могут не сохраняются при пересечении.Например, «быть цепью»: если P — цепь, тогда P d — такжецепь, а P ∩ P d — тривиально упорядоченное множество.Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у.
множествамиПрямая суммаP = h P, 6P i и Q = h Q, 6Q i — два ч.у. множества, причёмP ∩ Q = ∅.P + Q = h P ∪ Q, 6P ∨ 6Q i.335 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у. множествами335 / 432Прямая сумма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-элементнаяантицепь.Диаграмма прямой суммы состоит из двух диаграммсоответствующих ч.у.
множеств, рассматриваемых как единаядиаграмма.Ч.у. множество, не являющееся прямой суммой некоторых двухдругих ч.у. множеств, называется связным.Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у. множествамиПрямое произведение: определениеПрямым или декартовым произведением ч.у.
множествPh 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 ).336 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у. множествамиПрямое произведение: определениеПрямым или декартовым произведением ч.у. множествPh 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 );Справедливы соотношенияP ×R ∼= Q×R ⇒ P ∼= Q, Pn ∼= Qn ⇒ P ∼= Q,(P × Q)d ∼= P d × Qd .336 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у.
множествами337 / 432Прямое произведение: пример 1[[[(c, 1)cba×10=(a1)(b, 1)[[[[[[(a, 0)Рис. 5. Прямое произведение цепей 3 и 2(b, 0)(c, 0)Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у. множествами338 / 432Прямое произведение: пример 2[[[◦◦◦◦[[ ◦[◦◦Рис. 6. Зигзаги (или заборы) Z3 и Z4A ◦ A[A[A◦ AAAAA AAAA [ A◦ [◦◦ ◦ ◦◦[[AAAA AAAA [[[ AAA AAA◦◦◦Рис. 7. Прямое произведение Z3 × Z4◦Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у. множествамиТеорема (Оре )Каждый частичный порядок изоморфен некоторомуподмножеству декартова произведения цепей.339 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у. множествамиТеорема (Оре )Каждый частичный порядок изоморфен некоторомуподмножеству декартова произведения цепей.ОпределениеМультипликативной размерностью ч.у.
множества Pназывается наименьшее число k линейных порядков Li таких,существует вложение P ,→ L1 × . . . × Lk .339 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаГрупповые (линейные) коды340 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств341 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияРаздел IIIОсновные понятия теории ч.у.
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать342 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияПредставление P = h P, 6 i в виде пересечения цепейТеорема (Шпильрайна, принцип продолжения порядка)12Любой частичный порядок 6 может быть продолжен долинейного на том же множестве.Каждый порядок есть пересечение всех своих линейныхпродолжений (линеаризаций).P → L,P = L1 ∩ . . . ∩ Le(P) ,где e(P) — множество всех линеаризаций ч.у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
