PA_full (1127144), страница 23
Текст из файла (страница 23)
множества: особые элементыОпределениеЭлемент u 2 P ч.у. множества h P, 6 i называют:максимальным, если u 6 x ) u = x,минимальным, если u > x ) u = x,наибольшим, если x 6 u,наименьшим, если x > uдля любых x 2 P .Элемент наибольший, если все другие элементы содержатся внём, и он максимальный, если нет элементов, содержащих его(аналогично для наименьшего и минимального элементов).323 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествОсобые элементы ч.у. множества: пример• � максимальные элементы;• � минимальный и наименьший элемент;Наибольший (1) и наименьший (0) � граничные элементы.В конечном ч.у.
множестве имеется как минимум по одномумаксимальному и минимальному элементу.324 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множеств325 / 432Ч.у. множество h { 1, . . . , 18}, | i16181289641510143112135711 � наименьший элемент, • � максимальные.17Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествРанжированные ч.у. множестваЦепное условие Жордана-ДедекиндаВсе максимальные цепи между двумя данными элементамилокально конечного ч.у.
множества имеют одинаковую длину.Если ч.у. множество удовлетворяет условиюЖордана-Дедекинда и имеет наименьший элемент 0, то можноопределить функцию ранга ⇢:12⇢(0) = 0;a l b ) ⇢(b) = ⇢(a) + 1.Такое множество должно иметь слои.Если множество ранжируемо, то любой его слой (но нетолько!) является антицепью.326 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествПорядковые гомоморфизмыОпределениеОтображение ' : P ! P 0 носителей ч.у. множеств P и P0называется соответственноизотонным (монотонным, порядковым гомоморфизмом),если x 6 y ) '(x) 6 '(y);обратно изотонным, если '(x) 6 '(y) ) x 6 y;антиизотонным, если x 6 y ) '(x) > '(y).Если ' изотонно, обратно изотонно и инъективно, то этовложение или (порядковый) мономорфизм'(символически P ,! P 0 ).Сюръективный мономорфизм � (порядковый) изоморфизм'⇠ P 0 или P =⇠ P 0 ).(символически P =Изоморфизм ч.у.
множества в себя �(порядковый) автоморфизм.327 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествИдеалы и фильтры ч.у. множествОпределениеПодмножество J элементов ч.у. множества Ph P, 6 iназывается его (порядковым) идеалом, если(x 2 J) N (y 6 x) ) y 2 J.328 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у.
множествИдеалы и фильтры ч.у. множествОпределениеПодмножество J элементов ч.у. множества Ph P, 6 iназывается его (порядковым) идеалом, если(x 2 J) N (y 6 x) ) y 2 J.Подмножество F элементов P называется его (порядковым)фильтром, если(x 2 F ) N (x 6 y) ) y 2 F.328 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествИдеалы и фильтры ч.у. множествОпределениеПодмножество J элементов ч.у. множества Ph P, 6 iназывается его (порядковым) идеалом, если(x 2 J) N (y 6 x) ) y 2 J.Подмножество F элементов P называется его (порядковым)фильтром, если(x 2 F ) N (x 6 y) ) y 2 F.? и всё P � порядковые идеалыВажное свойство: объединение и пересечение порядковыхидеалов есть порядковый идеал.Обозначение: J(P) � множество всех порядковых идеалов ч.у.множества P.328 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у.
множеств329 / 432КонусыОпределениеПусть h P, 6 i � ч.у. множество и A ✓ P . Множества AM и AOопределяемые условиямиAM =x 2 P | 8 a ( a 6 x)Aи AO =x 2 P | 8 a ( x 6 a)Aназываются верхним и нижним конусами множества A, а ихэлементы � верхними и нижними гранями множества Aсоответственно. Для одноэлементного множества A = {a}используются обозначения aM и aO .Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у.
множеств329 / 432КонусыОпределениеПусть h P, 6 i � ч.у. множество и A ✓ P . Множества AM и AOопределяемые условиямиAM =x 2 P | 8 a ( a 6 x)Aи AO =x 2 P | 8 a ( x 6 a)Aназываются верхним и нижним конусами множества 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\bcad=bcadПрикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у.
множествами334 / 432Пересечениеh P, 61 i \ h P, 62 i = h P, 61 \ 62 i.cbad\bcad=bcadСвойства ч.у. множеств могут не сохраняются при пересечении.Например, �быть цепью�: если 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Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
