1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 12
Текст из файла (страница 12)
Если С вЂ” гомннутая диаграмма, то ошображение тс. 'гс — Фи лгваешса ггорФиаиом. о о ' Д о к а з в т е л ъ с т в о. Пусть о — о' в С, покажем тс (и)— — тс [о') в У. Предположим для определенности о е= Хн Тогда (иг,..., и ) ~то (о) +ЗА =» 0 (и„..., и„) Е:-т~4"'(о). В силу леммы Зл т~с+М (и) имеет $-наследников в ~7, поэтому и, ~ е,. Следовательно, тс (о) также имеет ю-наследников.
Далее, (и,... .; ., и„) ~=:. тс (о') +о (иг, ..., и„) ~ тг~с» [о') для некоторого и ~ О+Ф(ии ..., и~ и аин и~+д, ..., и„) а=то(о). Отсюда а тс (о) — тс (о') в б; Справедливо также тс (Лс) = ((е„... '..., е„Ц = Лс. Следоввтелъно, тс — морфиэм. Таким образом, если даны две эквивалентные схемы Барда (Р, о) н (Р', о'), то мы можем предъявить замкнутую диаграмму У и морфизмы то: Р У, тд. Р' — ~ У такие, что то (о) = тв (о ).
Итак, осталось доказать обратное утверждение. Т е о р е м в 3.6. Пусшь 1 — морфина иг нешэиорой новудиаграгъии ф, не содерэсашей свободина вершин, в гамннутную дивера.вшу С. Тогда ~ о тс = то. Д о к а з а т ел ь с та о. Если о Е Уо, то то (о) с-"той(о)), поскольку всякий путь от о к Ло в [~ отображается морфизмомг в путь от ~ (о) к Лс в С с той же последоввтелъностъю пометок дуг. Для тс 0 (о)) ~ то (о) достаточно показать, что для всякого й~04"'И[))а,() д яро. М 'д дукцией по lс.
овмс~и прежде всего, что ) [о) = Леот о = Лс, поскольку г'(о) = Лс=+ (о не имеет наследников) -+ о = Ло. Таким обра- ( (еи...,г„), если о = Ло ) Предположим теперь, что то~ [г (о)) с: то (о) для всех и Е эо, и покажем тс' (/ (о)) ~то (и) для всех оЕ Уо. Если о = 49 = Ло, то 4"+и (1(о)) = ю с: то (о). Если же очь Ло, то по условию теоремы и имеет наследников. Пусть, для определенности, о имеет г'-наследников. Тогда 1 (о) имеет г'-наследников, следовательно, г'-наследников имеет и то~'~~ Д (о)).
Поэтому (и„... и„) ч= 4с'П (1 (о)) + и, ~ е; =Ф и; = ои,' для некоторых и Е= Е; и й е=Е». Пусть и- е' в ч. Тогда 1(о) - 1(о') в С, з поэтому тР+и (~(о))- т~~"~(~(й)) в П. Следовательно, (и„... ..., иг и йо и;+и..., и„) Е= тс (Г (о')), н в силу индуктивного оп предположения (и,..., йч..., и„) е= то (о'). Отсюда следует, что (и„..., ои(,..., и„) Е=то (оу), т. е. (и„..., и„) 6= то (й). Сл едет в и е 3.1.
Две схемы Верде (Ю, о) и (Б', с') эквивалентны тогда и люлько тогда, когда существуют замкнутая диаграмма С и морфигмм /: Ю-~ С; ~'. Ю'-~- С такие, ипо 1 (о) — --. Г ( '). Д о к а з а т е л ь с т в о. Необходимость уже доказана. Для достаточности воспользуемся теоремой 3.6: то (Р) = те И (о)) = тс К (о')) = то (о ). П 2.3. Прецедура распознавания. Опишем четыре операцни для конечных полуднаграмм. Первая операция — это склеивание двух вершин полуднаграммы.
Пусть Д вЂ” конечная полудиаграмма и о„и, Е= г'о. Предположим, для вершин о„о неверно, что одна иэ ннх имеет наследников, а другая —, это Ло. Тогда описанная ниже операция склеивания дает конечную полудиаграмму ~)', а также морфием й () -~ Д'. 1. Пусть Ро. получается иэ го заменой вершин ог н иг одной новой вершнной о . 2. Пусть а' — отображение из г'о в е'о, определяемое соотношением о»э если Р = ог илн Р = гм а(в) = и в противном случае.
3. Пусть Ло = И(Ло). 4, Определим и — ш' в (~' тогда н только тогда, когда 3о, о' ~ УО такие, что о - й в 9, а' (о) = и> и а' (о') = и>'. Если одна из вершин пм о имеет наследников, а другая— это Ло, то мы говорим, что операция склеивания вершин и, и оэ не удается, а результат ее применения не определен.
В противном слуше склеизанне удается (или успешно), а морфием й (~-» ()' называется регульталым этого склеивания. Эаметам, что а' — это морфием на Ч'. Л ем ма 3.2. Пусть ог и ог — вершины конечной палудиаграмми Д и пусть для некоторой пвлудиаграммы ()" существуель морФиаи ); Г)-~-Ч" такой, что 1(ег) = Г (ог). Тогда склеивание 50 вершин ог и и удается, и если Н: Д-»(~' — реаулынат склеивания, то сущеаавует мор~бием из Д' в Д'.
До к а за тельство. Если, скажем, ог имеет наследннков, то к ~ ~о1) имеет наследников. Следовательно, ~ (ог) ~ Ло-, откуда ог ~ Ло. Поэтому склеивание и, и ог удается. Морфнзм йт Д' — Д" определяется так: ~( ). о чь ов (ог = и ~с,) = ~~ог)), уИ у( ) <— Следующая операцвя, называемая унлол1нением, пытается првмененвем склеиваний преобразовать конечную полудваграмму в диаграмму. Исходной является полуднаграмма ~) .
Если она уже является диаграммой, то болыпе делать ничего не нужно. Если нет, выбираем какую-нибудь вершнну и, для которой в полудиаграмме Г где ог чь им к склеиваем о, к и . Еслн склекванне удается (с результатом д: Д -» Дг), то с полуднаграммой ~)т поступаем точно так же, как с Кг, и т.
д. Процесс, очевидно, не может продолжаться бесконечно, так как каждое скленванке уменьшает число вершин на едквнцу. Если какое-лнбо склснванне не удается, то мы говорим, что операция уплотяенкя не удается. В протнвном случае успеотные склеивания дают последовательность морфнзмов Ф Рг-~.Он Ф й-~-Огв ° ° .14в- Юв-ю-1" Оюв для некоторого т ~ О, где (3,„— конечная диаграмма. Тогда мы будем говорнть, что операция уплотнения удается (влн уснегина), а результатом ее прнмененкя объявляем морфнзм р." Дв-» -» Д, определяемый соотношением йгдг... дг„если т ~ 1, Р= есзся Заметим снова,'что р — морфнзм на ~ .
Д е м м а 3.3. Пусть существует мор~бием из конечной яолудиаграммм ф, в диаграмму Р. Тогда унлотиение Д удается, и если его реаультатп — гто морфием р: Д - Дв„то существует морФизм иа Д в Р. Д о к а з а т е л ь с т в о. Рассмотрнм применение операцнв уплотнения к Др. Еслн Д вЂ” не диаграмма, то выбирается М вершина и, для которой Если существует морфием ~з: ~,')з- Р, где .0 — диаграмма, то и Р. Следовательно, ~з(ию) = ~з(из). В силу леммы 3.2 склеивание вершин иг и оз удается, и если Иг: ф,-~-Дг — результат этого склеивания, то существует морфием Дз: Дг -ю- Р. Теперь мы можем повторить наши рассуждения для Дз и т.
д. В конце концов будет получена дкаграмма ~, а также морфизм ~: Ч' -~ Р. Д Третья операция, называемая пополнением, просто добавляет поные вершины и дуги в данную конечную диаграмму Р следующим обрааом: для каждой тройки (не обязательно различных) вершин иг, и„иэ Е= % о удовлетворяющей условию в Р, где о1 Е= Х» из 6Б Х~, В Ф 7, в Р добавлнется новая вершина и вместе с дугами Мы говорим, что операция пополнения яе удазшсл, если существует 52 такая тройка вершин ип и», о» Е= Ъ~о, что о, 1 ! гу» 6 иг — -'- и в Э Поскольку С вЂ” замкнутая диаграмма, существует едвнственнаа вершина и <=:- Ус такая, что У(п,( — "-У(пэ( о, о У(~з) в С. В этом случае мы определяем у (и) = ю. ( ) Четвертая операция, называемая эаммкакиак, пытается преобраэовать данную диаграмму в эамкиутую диаграмму, попеременно применяя операции пополнения и уплотнения.
Исходной является конечная диаграмма Р». Если она уже а»минута, тогда и делать больше ничего ие нужно. В противном случае применяемпополиеиие Р». Если пополнение успешно (скажем, с результатом а,: р» -«(3)), то прнменяем операцию уплотнения Д». Далее. если и уплотнение окаэалось успешным (скажем, с реэультатом $3, Ф» где о <Б Х„о» ~ Х» (Ф у, н либо и» = Лв, либо о» -— йо. В противном случае мы получим конечную полудиаграмму Р' такую, что Уп С Ро .
В этом случае мы говорим, что операцнв пополнения удастся (или ускгшко), а рггультатам ее прнмененикобъявляем морфием включения а: р-«р' (это уже не морфнэз» на р'). Л е м м а 3.4. Пусть сущескмует морФигм (: Р-«С из конг»кой диаграммы Р г гамккутую диаграмму С. Тогда коколкениг диаграгькм Р удается, и если а Р -«Р' — гго регультат, ° сущ у т рФ у: Р'-С. Д о к а э а т ел ь с т в о будет прямым, у определяется так. а) Если и(=- У'и, то у(о) = ~(и).
б) Если о(Б гр '~ »'о, то существуют единственная тройка. аершнн им о„и» Е= Уо, »,1~ ($,..., к), (чьу, и о, б= Х„ о»(Б Хг такие, что Рис. 3.4. Првмер дизгмм изд Хь = (О), = (1],иримеиекие окерздий земмкзиик к которой ивкогдз ве ззкзичи- кзется р ь () — Р,), то повторяем тот же самый процесс с диаграммой Рь, что и с В ,н т. д. Если применение одной иэ операций пополнения нли уплотнения не удается, то мы говорим, что операция замыкания не удается.
В противном случае, если успешные пополнения и уплотнения дают последовательность а,: Ре-о(ьье, р,: 9,— Вь,..., а,„: Р,-ь.() ь, р: ч ь-е-Р для некоторого т )~ О, где Р„„— конечная замкнутая диаграмма, то мы говорим, что операция замыкания Р, удается (или успешна), а ее результатом 1 объявляем морфием с: Ре — Р, где ар...а р, селит >1, с= ьр., если т = О. О л Заметим, что для некоторых диаграмм Ре (как„например, для приведенной на рис. 3.4) применение операции замыкания никогда ве заканчивается, так что нельзя говорить ни о том, что операция не удается, ви о том, что она успешна.
Л е м м а 3.5. Пусть суьцвствует морФизм иг конечной диаграммы Ре в некопюрую аиькнутую диаграмму. Тогда если операция вамикания диаграммы,0е заканчивается, то она успешна. Д о к а э а т е л ъ с т в о проводится аналогично доказательству леммы 3.3. < < Опишем, наконец, процедуру, называемую распогнавшьием вквиваленпьности, н покажем, что если эта процедура завершается, то она распознает эквивалентность двух данных схем Берда. Исходными для процедуры являются две схемы Верда (Р, о) и (Р', ьь'). Сначала построим диаграмму (обозначаемую Р +,0'), взяв непересекающиеся копии диаграмм Р в Р' и склеивая их выходные вершины. Пусть у обозначает очевидный морфизм В -ь- Р + .0', аналогично у' обозначает Р' -ь,0 + Р'.
Затем склеим вершины у (о) н у' (ьг). Если применение этой операции оказалось успешным, а его результат — морфиэм ь)ь Р + Р'- -м (ь, то применяем операцию уплотнения к (ь. Если применение операции уплотнения оказалось успешным, а его реэультат— это морфизм р: Ч вЂ” В, то применяем операцию замыкания к диаграмме Р. Наконец, если и эта последээья операция оказалась успешной, то мы говорим, что процедура распознаванияуспешна. Если же хотя бы одна из упомянутых операций не удается, то мы говорим, что процедура распознавания локается.
Т е о р е м а 3.7. Если процедура распознавания успеьина для .схем Берда (О, и) и (В', й), то они гквивалеьапны; если же процедура ломается, то они неэквиеаленгпни. Д о к а з а т е л ъ с т в о. Пусть процедура распознавания успешна для схем (Р, г) и (Р', о'). Тогда успешные операции, применяемые процедурой распознавания, дадут нам следующие о4 морфиэмы у: .0 Р+Р', у".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
