С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 21

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 21)

у.множествоЖордан а-ДедекиндаиудовлетворяетимеетусловиюнаименьшийэлементО , то оно ранжируемо, т.е. на нём можно определитьфунгкци1{) ранга р :1. р(О) == О ;== р( а) + 12. а~ Ь ==> р(Ь)и такое множество имеетслои .Если множествоооооо- р= 2ранжируемо , то лiобойего слой (но не только!)о-р=-р= о1является антицепью.оПорядковые гомоморфизмыОпределениеч . у.5.3. Отображение ер : Р ----+ Р ' носителеймножеств называется соответственно•изотоннъt.м (.монотонным, пор.ядгковъt.м го.мо.мор­физ.мо.м), если х ~ у•==>ер( х) ~rp(y);обратно изотонны.м, еслиер(х)~ер(у)==>х~у;• антиизоmо'l-lны.м, если х ~ у ==> rp( х) ? ер(у) .Еслиеризотонно, обратно изотонна и инъектив­но, то это влоа+еение или (пор.ядгковыu) .моно.морфиз.м( Р ~ Р ').5.1 .

(III поток)241С}оръективный мономорфизм-( пор.ядгк;овыu)изо­<р.морфизм(рр 1 или рrvrvр ' ).Изоморфизм ч . у. множества в себя- {пор.ядгк;овыu)автоморфизм .Идеалы и фильтры ч.у. множествОпр еделени ежестваесли( Р,Подмножество5.4.Jэлементов ч . у. мно­~) называется его {пор.ядгк;овы.м) идеалом,(xE J)&(y~x)Подмножество=* yE J.элементов Р называется егоF( пор.яд­гк;овъt.м) филътро.м, если(х Е0F) &(х ~у)=*у ЕF.и всё ч.у. множество Р - nесобстве?-t/Н/ые поряд­ковые идеалы .Важное свойство : объединение и пересечение поряд­ковых идеалов есть порядковый идеал.Обозначение:множество всех порядковыхJ (P ) -идеалов ч.у.

множества Р .Определение 5.5. Пусть ( Р, ~) А С Р . Множества А~ и A \lА~ = { хЕ РA\l = { хЕ Рч . у. множество иVa(a~x) } иАVa(x~a) }Аназываются верхним и нижним гк;оnуса.ми множества А ,а их элементы-верхними и нижними граn.я.ми множе­ства А соответственно.Для одноэлементного множества А = {а }-а~ и а v.Глава242Понятно, что если а~ Ь , то а 6xv== (х) ==J (x)- идеал , а х6Ч.у. множества5.n ьv== [ а, Ь ].- фильтр Р ;такие идеалы и фильтры называi{)Т гл ав'Ны.ми .При мер5.2.161812896415101431121357171Рис .

5.6. Верхний и нижний конусы множества{ 2, 3}5.1 . (III поток)243Коке'чкопорождёккыu идеал:k(а1,... , ak) ~ U а,; v'ьi=lПр имер5.3.1618128964151014311213571Рис.Определение5.6.5. 7.ПустьИдеал( Р,( 6, 15)~)-ч . у. множество иА с Р.• Наименьший элемент в А 6 называется точкойверхкеu гранъю .мко:J1сестваsup А).А(символически17Глава2445.Ч.у. множества• Наибольший элемент в А v называется mо'ч/ноunuжneu граnъ1-о .мnoD~cecmвaА(символическиinf А) .Пример 5.4 (sup А и/или inf А могут не существовать).dс{ а, Ь }6=={ с, d}, но множество { с, d}не имеет инфимумаsup{ а, Ь} отсутствует.Аналогично , отсутствует inf { с, d}.==?ьа5.2Операции над ч.у. множествамиПересечение( Р, ~1 n ~2 ).сьndаР ис .5.8.ьсьсаdаdП ересечение ч . у.

множествСвойства ч . у. множеств могут не сохраняются припересечении. Н апример, << быть цепью » : если Р - цепь ,тогда Р U - также цепь , а Р nР U - тривиально упоря­доченное множество.(III поток)5.2.245Прямая сумма. Р~Р) и Qч . у. множества, причём Р n Q == 0 .р== ( Р,+ Q == ( р u Q'~Q) - два== ( Q,~р v ~Q).Справедливы соотношенияP +QrvP + R ==> QпР - прямая суммаnl -nrvR;(P +Q) ~rvP ~+ R « .экземпляров Р ,п-элементная антицепь .Диаграмма п рямой суммы состоит из двух диа­граммсоответству1-ощих ч . у.м н ожеств ,рассматривае­мых как единая диаграмма.Ч.

у. множество, не являiощееся прямой суммой некото­рых двух других ч . у. множеств, называется св.яз 'Н/Ы.М.Прямое произведение.произведениемч.у.Пр.я.мы.ммножествде'К;артовы.мили( Р, ~Р)РQ == ( Q, ~Q ) называется множествоP x Q ==( P xQ,~),где (р,q) ~ (р ' , q ') {::} (р ~ Р р , ) & ( q ~ Q q , ) .(Ь , 1)сьхоаР ис .15.9.(a,l )(Ь, О)(а, О)П рямое произведение цепей3и2иГлава246прямоеpn вп==произведениеЧ.у.

множества5.экземпляровnР:2п .ЕслиР,Qранжированы и их ранговые q)унк­ции суть рр иPQ, то Р х Q также ранжировано иp(xl, х2) == pp(xl ) + PQ(x2);Справедл ивы соотношенияР ХR~QR =?ХР ~Р хQ,pnоQ~f"'..)QхQn =?оРрf"'..)Q.о/~/оР ис.оо5. 10. Зигзаги (или заборы) Z 3 и Z 4ооооР ис .о5.11 .ооооП рямое произведениеооооZ3хZ4Тео ем а 5 01 ( О ре) о Каснсдыu частичпыu пор.ядоrк; изо­морфеп пеrк;оторому подмно ;нсеству деrк;артова произ ­ведения rцeneu .Опр еделение507 оч . у. множестваМулъ типлиrк;атив поu размерпостъюРлинейных порядковР чL1 х ...хLk.называется наименьшее числоLikтаких , существует вложение5.3. (III поток)247ооооо•••о5.3•ЛинеаризацияПринцип продолжения порядкаТео ема1.5.2(Шпильрайна-Дашника-Миллера) .Любоu частич?-lыu поря до к; .моа-к;ет бытъ продо.л­же?-l до .лu?-leu?-loгo2.'1-laто.м же .м?-lожестве.Каждыu порядок; естъ пересечепие всех своих .лu­neunъtx пpoдo.лafCenuu (л ипеариза'Циi1) .Р --+ Li ,где е(Р)-Р === L1n ... n L e(P),число всех линеаризаций ч .

у. множества Р.для конечного случая,Р ===nЕсли Р-не цепь, то вР найдутся несравнимые элементы; произвольно опре­делим порядок на них и п родолжим его по т ранзитивно ­сти . Если получившиеся ч . у. множество ещё не цепь, товыберем новую пару несравнимых элементов и посту­паем, как указано выше. Ч ерез конечное число шаговп олуч аем линейный порядок.Глава2485. Ч.у. множестваТ.

к . возможен различный выбор пар несравнимыхэлементов и при каждом выборе можно пол агать лiо­бой их порядок , то можно получить все возможные ли­нейные продолжения исходного частичного порядка .П ересечение всех таких цепей даст исходное ч.у.множество: если х ~ у , то аналогичное следование бу­дет и во всех полученных линейных порядках , а при'-'..'-'х Ф у всегда наидется пара цепеи с противоположнымих следованием, что в пересечении цепей и даст несрав­нимость этих элементов.оЛинейные продолжения ч. у. множеств: примеры ..

.ьасььсасьсаае( Р )р=3dсdсссdсdсdааьььааdааьььре (Р ) =55.3. (III поток)249dс-ьаРис.5. 12.dссdьnьааП редставление ч . у. множества пересечениемцепейоо• • •ооо• • •оР ис .5.13.Малая корона SnЬзРис.<< е(Р ) == 7>>-•е( 2 хn)Ьs5.14. Корона S sNР-полная задача, но :=1c::nn+ 1'ЧUСЛа Каталана;Глава250•Ч.у. множества5.Для зигзагов сп р аведливо представлениеLn)Oe(Z ) xnп,== tgxn.значенияZ n пр и чётных n нечетных 'liисла тшнгепса;+secx,'liисла сепшнса, а при••• е( Sп) == (n + l )!(n- 1)! ;•e(sn) n1n) ln.хх-- ·cos 2 х '•logn3ln/2J2log е + o(l) .Вероятностное пространство на линеарезацияхПри дискретных задач часто рассматриватот связанноес ч.у.

множеством Р веро.ятпостпое пространство намножестве всех е( Р) его линеаризаций, в котором каж­дая линеаризация равповеро.ятпа .В этом пространстве для элементов х, у,z, ...ч.у.множества Р рассматрив а1от события Е вида х ~ у,(х ~у) & (х ~ z) и т.д.Вероятность Pr [Е] такого события:PrТео ема[Е]==число линеаризаций, :(~)торых имеет место Е.5.3 (ХУZ-теорема) .

Пустъ ( Р, ~) - ч.у . .мно­жество их, у,zЕ Р . ТогдаPr [ х ~ у ] · Pr [ х ~ z ] ~ Pr [ (х ~ у) & ( х ~ z) ] .5.3.(IIIпоток)251Проблема сортировкиL-определить линейный порядокс помощью минимального количества вопросов << вер­но ли, что х <у вОбобщение:L ?>>.зафиксированная, но неизвестнаяL -линеаризация ч .

у. множества Р .ОптимальнаясебяпродедуранахождениеэлементовпоискахивключаетLу,длявкоторыхPr [ х <у] ~ ~·С.С. Кислицын(1968)высказал<<1/ 3 - 2/ 3 предпо­ложение >> : "любое 'Не .явл.яющеес.я 'Цеnъю 'Ч . у . м'Ноже­ство содержит пару 'Несрав'Нимых элеме'Нmов х и у ,дл.я x;omopъtx13~р r [ х~у ]~2 ".3Позднее это утверждение независимо выдвинули американские исследователи М .

Фредмаи и Н. Линал .Данное предположение до сих пор успешно противо­стоит всем попыткам его доказать и представляет собойодну из наиболее интригующих проблем комбинатор­ной теории ч.у. множеств (С . Фелснер и У.Т. Троттер).Н а сегодняшний день наиболее сильный результат :О,2764~5-v's10~Pr[x~ у] ~5+V510~ О,7236 .Ч.у. множества: спектр Определение :Spec (Р) == { Pr [а~ Ь]а, Ь Е Р}Я сно, что• поскольку Pr [ а ~ Ь ] == 1 - P r [ Ь ~ а ], спектрсимметричен относительно ~;Глава252•5.Ч.у.

множествадля всех неодноэлементных тривиально упорядо­ченныхмножеств Spec• { о,~' 1 }== { ~ };единственный.....трехэлементвыиспектр;•все••четырехэлементныеспектрыдолжныиметьвид{О , а, 1- а, 1 } , где О < а<~;Гипотеза (2002) : а~.==Размернос ть ч. у. множеств.П о теореме Ш пиль­райна ч . у. множество Р совпадает с пересечением всехе(Р) своих линеаризаций, но тот же результат можнополучить, взяв зн ачительно меньшее число линейныхпродолжений .Н апример, ч . у. множество Рьdсаимеет 6 линеаризаций, но Р == [а, Ь, с, d ]n [а, d, с, Ь] .Пусть Р - ч.у. множество и R == { L 1, ...

, Lk } совокупность цепей такая, что Рговорят, чтоОпр еделениеR== L1 n ... n Lk,тор еализует Р .5.8.Н аименьшее число линейных поряд­ков , дающих в пересечении данное ч.у. множество Рназывается егоческиdim(P)).( пор.ядrк;овоu)раз.мер'Носmъ1о(символи­5.3.(IIIпоток)253Тео ема 5.4 (Оре).

Пор.ядrк;ова.я и .мулътиплиrк;ативка.яразмеркости ttt . у . .мкоаtсества совпадают .( с, d)[1,2, 3,4,5] n [2,4, 1,3,5 ]://~/~/31/~/(a,d)4{Ь , е)~/(а, е)2dim(P ) -(с , е){b , d)5[ а, Ь, с ] х-более тонкая оценка сложности ч.у. мно­жества, чем е(Р) Размерность...имеют :1-только цепи;2-тривиально упорядоченные множества(т.е.[d, е ]размерность не может интерпретироватьсякак мера отличия данного ч.у. множестваот линейного);- Zп;-все отличные от цепей ч.у. множеств , при Ркроме3 - sз, sh и sh ~ (см. диаграммы) :оdеfаьсn - Sn.оооооооооСтандартный пример показывает,оо::( 6,Глава254Ч.у. множества5.что существуют ч.у. множества сколь угоднобольшой р азмерности.•Q5С Р-1- Q==> dim( Q)~ dim (P ), при удале­нии 1-го элемента его р азмерность уменьшаетсяне более, чем на+• dim(P1;== m ax { dim(P ), dim( Q) } ,Q)еслихотя бы одно из множеств не является цепью иdim(P+ Q)2;• dim(P х Q) ~ dim(P )• dim(P ) ~Р/2+ dim( Q);при Р? 4(теорема Хирагу­чи) .Тео ема5.5 ( « компактности » ).

Характеристики

Список файлов лекций