3.8. Гомоморфизмы для заданной глобальной регулярности

В этом разделе мы продолжим исследование гомоморфизмов с учетом того дополнительного условия, что рассматриваемые пространства конфигураций заданы на некотором фиксированном семействе Г остовов образующих и тип соединения также фиксирован (см. Примечания А). Мы будем считать .

В этой связи особый интерес представляет изучение гомоморфизмов пространств конфигураций, сохраняющих внешние связи (в том смысле, что две конфигурации, обладающие различными внешними связями, не будут отображаться в один и тот же элемент).

Теорема 3.8.1. Рассмотрим некоторый гомоморфизм сохраняющий внешние связи, так что из следует и определим отношение на как

В таком случае — это некоторое правило идентификации, которое, следовательно, определяет на некоторую алгебру изображений индуцирует гомоморфизм изображений Н из в — «равенство»).

Доказательство. Для того чтобы доказать первую часть утверждения, необходимо проверить выполнение четырех условий определения 3.1.1 из первого тома. Очевидно, что отношение эквивалентности. Если выполняется условие то конфигурации с и с будут иметь одни и те же внешние связи, поскольку сохраняет внешние связи. Если условие выполнено, то и, следовательно, для произвольного

преобразования подобия имеет место так как гомоморфно. Таким образом, . И наконец, если регулярны и условия выполнены, то это значит, что Поскольку, однако, гомоморфно (см. условие (II) определения 3.4.1), то

и, следовательно, условие выполнено и, таким образом, выполнены все четыре условия, необходимые для того, чтобы являлось допустимым правилом идентификации.

В таком случае строго определена и связана с алгеброй отображением , переводящим некоторое изображение Отметим, что правило идентификации «равенство» в алгебре означает, что изображения состоят из отдельных конфигураций. Отметим также, что, согласно условию (3.8.1), Я определено однозначно. Естественно, мы считаем, что Итак, для любого

так что условие (I) определения 3.7.1 выполнено. Если принадлежат то из этого следует, что

где - регулярные конфигурации выбраны таким образом, что . В таком случае из соотношения (3.8.4) непосредственно следует, что

таким образом, условие (II) определения выполняется. Что и требовалось доказать.

Эта теорема позволяет нам строить гомоморфизмы изображений непосредственно по примерам гомоморфизмов конфигураций, встречавшихся нам раньше. Можно также ввести следующее ее обобщение, близкое к теореме 3.1.2 первого тома, причем модификации определяются переходом к более общему определению гомоморфизма. Мы будем считать, что пространства конфигураций и имеют одинаковую глобальную регулярность.

Рассмотрим некоторый эпиморфизм, сохраняющий внешние связи где и введем факторгруппу где нормальная подгруппа:

Введем на отношение как

Это отношение эквивалентности более грубое, чем и, следовательно, оно определяет разбиение, классы эквивалентности которого являются объединениями-изображении. Мы допускаем, что на этих классах элемент факторгруппы действует естественным образом: любой принадлежит некоторому смежному классу нормальной подгруппы и один из элементов этого смежного класса применяется к некоторому -изображению, входящему в соответствующий класс эквивалентности. Это приводит к получению единственного результата, поскольку, если два элемента множества преобразования подобия принадлежат одному смежному классу, то и, следовательно, если и два уже упоминавшихся изображения, таких что , то

В то же время соотношение (3.8.8) означает, что (см. (3.8.7)), и, следовательно, наше определение однозначно и запись имеет смысл, если ,1 — один из классов эквивалентности.

Если группа преобразований подобия, то, как это уже было сделано нами при доказательстве теоремы 3.8.1, можно показать, что правило идентификации. Пусть — алгебра изображений, которая возникает в результате.

При каких условиях можно гарантировать, что алгебра изоморфна алгебре Г? Очевидно, что отношение между и индуцируемое биективно (напомним, что предполагается сюръективным), и то же самое справедливо для отношения между факторгруппой Его гомоморфность показывается точно так же, как это было сделано в последнем доказательстве. Рассмотрим теперь (см. примечания Б).

Очевидно, что это групповой гомоморфизм. Ну а что в том смысле можно сказать относительно Если заданы некоторые и то существует , где Пусть это -изображение, содержащее и пусть смежный класс нормальной подгруппы, включающий . В таком случае

и, следовательно,

Таким образом, первое условие определения 3.7.1 выполняется.

Пусть теперь и все они принадлежат алгебре Используя снова свойство сюръективности, мы можем найти -изображения которые отображены в изображения, помеченные штрихом. Пусть и -изображения, содержащие -изображения без штриха. Если известно, что то так что

именно это и требуется для обеспечения гомоморфности . В общем случае это нам не известно, следовательно, необходимо ввести дополнительное условие.

Будем считать, что глобально свободна над сохраняет специфику связей. Последнее означает, что связи изображений удовлетворяют отношению связи только в том случае, если гомологичные (напомним, что структура внешних связей сохраняется) связи изображения удовлетворяют отношению связи Отсюда следует, что для сохраняется локальная регулярность, и, следовательно, отображение гомоморфно, а отображение это некоторый изоморфизм. Резюмируя изложенное, сформулируем следующую теорему.

Теорема 3.8.2. Пусть -некоторый эпиморфизм, сохраняющий внешние связи и отношения связи, причем алгебра глобально свободна. Определим на отношение как

В таком случае определяет правило идентификации более грубое, чем и получаемая в результате алгебра изображений изоморфна алгебре

И обратно — пусть правило идентификации, более грубое, чем и рассмотрим естественное отображение . Положим . В таком случае имеет место следующая теорема.

Теорема 3.8.3. Естественное отображение есть эпиморфизм, сохраняющий внешние связи и отношения связей.

Доказательство. Естественное отображение автоматически сюръективно. Очевидно, что для произвольного

поскольку - некоторое правило идентификации. Если, во-вторых, то отсюда следует, что

И наконец, поскольку имеет те же внешние связи, что и изображение то очевидно, что естественное отображение сохраняет внешние связи. В нашем же случае так что отношения связей сохраняются. Что и требовалось доказать.

Построим теперь алгебру изображений, полезную для слабейших регулярностей. Пусть — некоторое множество произвольной мощности и рассмотрим все функции где для конечного числа всех Х-значений. Множество таких функций образует некоторую коммутативную полугруппу относительно поточечного сложения

Пусть задана некоторая группа преобразований рассмотрим произвольное -инвариантное отношение конгруэнтности на Другими словами,

Введем алгебру «дискретный», причем если Здесь

Это соотношение имеет смысл, поскольку мы рассматриваем лишь конечные конфигурации, . В соответствии с определением 3.1.1 из первого тома допустимое правило идентификации. Действительно, оно явно представляет собой отношение эквива-, лентности и, поскольку - «свободный», можно считать, что образующие имеют нулевую арность, и, следовательно, условие (II) определения выполняется тривиально. Выполнение условия (III) следует из того факта, что отношение конгруэнтности -инвариантно. Условие (IV) выполняется, поскольку при регулярности типа «дискретная» некоторая комбинация двух конфигураций с и с сводится, в сущности, к тому, что их составы сводятся воедино как объединение непересекающихся множеств. Это означает, что

Это соответствует сложению в нашей полугруппе Естественно, в данном случае о не задает каких-либо соединений связей. Из соотношения (3.8.15), однако, следует, что, поскольку — некоторая конгруэнтность на полугруппе, то при выполнении

условий имеет место следующее:

Таким образом, некоторое правило идентификации н наша алгебра корректно определена. Такую алгебру мы называем дискретной алгеброй изображений — это название определяется следующей теоремой.

Теорема 3.8.3. Пусть некоторая произвольная алгебра изображений с регулярностью типа . В таком случае она изоморфна некоторой дискретной алгебре изображений

Доказательство. Пусть «дискретный», пометим все образующие из множества некоторой произвольной меткой X, так что . Если конечно, то может быть задано как если счетно, то и так далее для больших мощностей. Мы пренебрегаем всей информацией, содержащейся в образующих, и требуем лишь того, чтобы Х-маркировка разделяла элементы из

Все образующие из можно заменить образующими с нулевой арностью без нарушения регулярности, что часто будет удобным при работе с дискретной регулярностью. Поскольку построение комбинаций означает сложение частот, любую конфигурацию можно описывать с помощью функции построенной так, как указано выше, и удовлетворяющей соотношению (3.8.15). Определим отношение эквивалентности в полугруппе как

отсюда следует, что отношение эквивалентности -инвариаитно, поскольку -инвариантно правило идентификации является отношением конгруэнтности на полугруппе вследствие свойства (IV) определения 3.1.1 первого тома. Таким образом, обладает необходимыми свойствами и позволяет определить некоторую дискретную алгебру изображений

Рассмотрим теперь отображение индуцированное «дискретный»). Отметим, что это отображение -инвариантно и что и, следовательно, некоторый гомоморфизм. Поскольку, однако, биективно, то определено однозначно. Поскольку, с другой стороны, также является гомоморфизмом, то оно является также и некоторым изоморфизмом и Что и требовалось доказать.

Замечание. Отметим, кстати, что индексом класса образующих также можно воспользоваться. Если так что каждый класс образующих порождается единственным прототипом то в случае некоторой алгебры с «дискретным» типом регулярности действовать можно следующим образом. Пусть функции определены на и их значениями являются конечные множества (допускаются повторения) с произвольным числом элементов. Определим «сумму» как

и рассмотрим образующие конфигурации прототип, входящий в . В таком случае сложение типа (3.8.18) соответствует комбинации конфигураций. В таком случае мы можем действовать дальше так же, как и выше, с тем исключением, что теперь полугруппа другая: ее операция в (3.8.18) — бинарная. Далее эту тему мы развивать не будем.

Вместо этого займемся изучением некоторых многочленов на алгебрах изображений и некоторых теоретико-множественных операций. Начнем мы с простейшего случая, когда регулярность является столь слабой, сколь это вообще возможно, — «дискретный». Теорема 3.8.3 указывает, что без потери общности можно считать алгеброй свободных изображений над некоторым множеством А, как описано выше. В таком случае, однако,

образует коммутативный моноид, дистрибутивный относительно унарных операций Именно с помощью двух этих основных операций могут быть сформированы многочлены.

Рассмотрим пример. Пусть состоит из полуплоскостей, идентифицирует пересечения полуплоскостей. В данном случае мы не стремимся к получению простых описаний, что потребовало бы вместо этого мы выбираем просто «дискретный». В этом случае изображения представляют собой выпуклые множества и мы располагаем двумя базисными операциями: перемещения в евклидовом пространстве (преобразования подобия) и пересечение множеств.

Другим простым примером служит случай, когда состоит из функций или «дискретный», представляет собой умножение на действительную или комплексную ненулевую скалярную величину и идентифицирует суммы функций. В этом случае просто становится некоторым векторным пространством.

В случае алгебр изображений типа «дискретный» все многочлены — целые, но при переходе к более строгим регулярностям это уже на так.

В случае конфигураций, рассматривавшихся в примере 3.8.1,

где — «линейиый», и при идентифицирующем функции по их областям определения, мы располагаем лишь двумя базисными бинарными операциями в дополнение к унарной базисной операции которая имеется всегда. Так, например, мы не можем воспользоваться соединителем, предусматривающим соединение входных связей с выходными связями выходных связей с входными связями поскольку это идет вразрез с глобальной регулярностью . Мы имеем, таким образом, первый из них предусматривает конкатенацию к слева (всякий раз, когда это возможно), а второй справа (всякий раз, когда это возможно). Эти функции являются частично определенными, поскольку определен только в тех случаях, когда правая концевая точка и значение функции соответствуют левой концевой точке и значению функции Следовательно, и и правый — частично определенные базисные операции и такими же будут и построенные с их помощью многочлены. Итак, .

Рассмотрим теперь конфигурации из примера 3.8.3, где «дерево», и пусть идентифицирует упорядоченную последовательность самых нижних узлов. В таком случае допустимыми является ряд бинарных базисных операций, как, например, соединяющая входную связь с выходной связью если это возможно. Для этого необходимо, чтобы имело по крайней мере выходных связей и чтобы значение выходной связи было равно значению входной связи Выбирая еще более специальный тип соединения «бинарное дерево», мы приходим к случаю с четырьмя базисными операциями и, естественно, унарной -операцией.

В более общем случае при некотором фиксированном типе соединения 2 и двух изображениях бинарная операция в первую очередь определяет подмножества через координаты, являющиеся метками внешних связей. Эти два множества связей соединяются в соответствии с способом, который предписывается функцией без нарушения (в тех случаях, когда соответствующее соединение возможно). Эти базисные операции и операция позволяют сформировать необходимые многочлены.

Рассмотрим теперь две алгебры изображений одинаковой глобальной регулярностью; пусть эти алгебры связаны гомоморфизмом . Многочлен на определяется через базисные операции, заданные на и точно так же дело обстоит для

В таком случае соединитель может соединять а унарный -оператор, естественно, также сохраняет структуру внешних связей, и, следовательно,

определен, если определен многочлен . Кроме того, очевидно, что

Отметим, что многочлен определен как элемент пространства конфигураций только в том случае, если все последовательные операции (выполняемые в указанном порядке), которые должны быть использованы, также вполне определены.

Напомним теперь смысл операций «соединение» и «стягивание» (см. разд. 3.6), combine и span соответственно.

Теорема 3.8.4. Две операции над множествами «соединение» и «стягивание» являются константами на изображениях, если -сильное (см. Примечания В) правило идентификации:

если

Доказательство. Рассмотрим . В таком случае общий элемент а в А можно записать аналогично (3.6.1) с использованием некоторого соединителя о и преобразований подобия Построим такую же комбинацию а конфигураций Тогда а также регулярна, поскольку сильное правило идентификации, в силу условий (III) и (IV) определения 3.1.1 первого тома, а также того факта, что Проделаем то же самое для общего элемента из А. В результате первое утверждение (3.8.20) доказано.

Для доказательства второго утверждения необходимо просто повторить первое, поскольку «стягивание» представляет собой итеративное замыкание операции «соединение». Итак, обе операции над множествами являются константами на изображениях по модулю Что и требовалось доказать.

Для глобально свободной регулярности всякое правило идентификации является сильным правилом идентификации. Действительно, если условие выполняется, и если а регулярна, также должна быть регулярна, поскольку необходима лишь локальная регулярность и (внешние связи одинаковы).

В таком случае имеет смысл (по-прежнему, используя сильное сохранить те же символы для операций над множествами для изображений, что и использовались для

конфигураций, так что мы можем записывать

и функции, входящие в (3.8.21) принимают значения в .

Эта операция над множествами определенная для множеств изображений, ковариантна относительно преобразований подобия это непосредственно следует из и того факта, что является итерационным замыканием операции Кроме того, эта операция обладает свойствами, определяемыми утверждениями (I) и (II) теоремы 3.6.1, поскольку, как только что было показано, эти операции на конфигурациях являются константами на изображениях.

Введем, в частности, для следующую бинарную операцию

Теорема 3.8.5. В случае глобально свободной регулярности над множество явпяется коммутативным моноидом

относительно где операция дистрибутивна относительно преобразований подобия.

Доказательство. Рассмотрим три подмножества множества . В таком случае состоит изо всех изображений, содержащих конфшурации вида (3.6.9), причем конфигурации с выбираются из подмножеств . В этом случае, однако, это та же конструкция, что и и, следовательно, операция ассоциативна. Пустое изображение выполняет роль единичного элемента и, таким образом, коммутативность очевидна. Что и требовалось доказать.

Пример 3.8.1. Пусть образующие — полуплоскости в пространстве «дискретный», правило идентификации посредством пересечения, как и выше. В таком случае изображения представляют собой выпуклые множества. Если и состоят из одного изображения, соответственно, то В будет содержать пустое изображение, все множества, конгруэнтные или В, и пересечения произвольного числа множеств, конгруэнтных или В.

Пример 3.8.2. Пусть образующие — действительные функции на [0, 1], а осуществляет умножение на ненулевые действительные числа и идентифицирует суммы функций, появляющиеся в конфигурациях. В таком случае означает линейное замыкание двух множеств функций.

Пример 3.8.3. Пусть образующие — правила подстановки некоторого автоматного языка, — «линейный и идентифицирует

допустимые цепочки языка, обладающие одинаковыми внешними связями. В таком случае изображения представляют собой допустимые предложения данного языка. Если и А, и В состоят из некоторого единственного предложения, соответственно то включает пустую цепочку и все допустимые в данном языке предложения, которые можно построить посредством конкатенации ряда -копий и -копий.

Воспользуемся теми же, что в теореме 3.8.5, допущениями, зафиксируем А и сформируем следующую функцию:

Поскольку операция ассоциативна, правило композиции имеет вид

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

Обратимся вновь к понятию проекций конфигураций, вводившемуся в предыдущем разделе, и выясним, что происходит в том случае, когда правило индентификации идентифицирует индексы класса образующих в следующем смысле.

Определение 3.8.1. Если тип соединения «монотонный», то будем говорить, что правило идентификации отождествляет индексы класса образующих, если для утверждение означает, что

и

Замечание. Утверждение об одинаковости двух соединителей в (3.8.26) следует интерпретировать следующим образом. Запишем две конфигурации

как соединения проекций для различных значений :

В таком случае представляет соединитель, обеспечивающий соединение между собой подконфигураций конфигурации и подобным же образом соответствующий соединитель

для второй конфигурации. Внешние связи конфигураций и одинаковы разд. 3.1) — поэтому утверждение (3.8.25) имеет смысл.

Замечание 3.8.2. В частном случае Я — «дискретный», когда никакие связи не вводятся, условие (3.8.26) значения не имеет и следует рассматривать только условие (3.8.25).

В таком случае можно распространить проекции на алгебру изображений (см. раздел 3.5).

Теорема 3.8.6. Если тип соединения «монотонный-» и идентифицирует индексы класса образующих, то для любого множество

принадлежит некоторому единственному изображению в алгебре так что отображает алгебру саму в себя.

Доказательство. Рассмотрим две конфигурации изображения таких, что условие выполняется. В таком случае для любого условие (3.8.25) выполнено. Построение эквивалентно исключению из выражения (3.8.27) всех подконфигураций, индексы класса образующих которых не принадлежат множеству В, и одновременно исключению их связей. Это значит, что и можно записать как

где в обоих случаях используется один и тот же соединитель и условие выполнено, . В таком случае, однако, в соответствии с определением 3.1.1 первого тома правило отождествляет так что в выражении (3.8.29) является однозначно определенным. Что и требовалось доказать.

Следствие. При выполнении условий теоремы 3.8.6 изображения имеют следующее каноническое представление:

где .

Это утверждение непосредственно следует из последнего доказательства; если изображение, содержащее регулярную конфигурацию Значения а, входящие в (3.8.31), определяются условием

так что множество можно записать как

Представление (3.8.31) разбивает изображение на подконфигурации с постоянным индексом класса образующих: регулярность анализируется на однородных элементах.

Попытаемся дать косвенную характеризацию операторов проектирования в алгебрах изображений.

Теорема 3.8.7. Пусть тип соединения «монотонный», и пусть для любого существует некоторый эпиморфизм

В таком случае

Доказательство. Напомним, что — это алгебра подизображений и рассмотрим некоторое изображение Тогда, поскольку сюръективен (на существует (по крайней мере) одно изображение такое что . В таком случае, однако,

что доказывает утверждение (I).

Для проверки правильности утверждения (II) допустим, что изображение принадлежит одновременно обеим алгебрам подизображений и Можно в таком случае записать, что и, следовательно, поскольку и условие (3.8.34) выполняется, то

Пусть теперь разобьем с по -классам образующих:

где все регулярны, поскольку тип соединения — «монотонный». Тогда

на основании условия (IV) определения 3.1.1 первого тома. Поскольку, однако, мы предполагали, что гомоморфно, то

где для всех а, за исключением . Следовательно,

и, таким образом, условие (III) выполнено, что и требовалось доказать.