3.9. Представления посредством изоморфизмов изображений

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

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

Обратимся вновь к функциям реализующим отображение как и соответственно (см. определение 3.7.2).

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

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

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

Далее, применяя функцию к обеим частям (3.9.2), получаем

и, применяя затем функцию к обеим частям (3.9.3), получаем, что

Поскольку выражение (3.9.4) представляет собой условие (3.9.1), которое мы и стремились доказать, то необходимая часть теоремы доказана.

Прямая часть доказательства сложнее. Необходимо показать, что алгебра изображений с регулярностью типа («равенство», «линейный») входит в изоморфизм если условие (3.9.1) выполняется. Пусть состоит изо всех изображений алгебры связи которых, однако, изменены указанным ниже способом (при необходимости вводится дополнительная метка, позволяющая различать после изменения связей получаемые в результате изображения Пусть А — естественное отображение, установленное между алгебрами и . Пусть причем показатели связи для заданы как подмножества в алгебре

(при условии что ). В других случаях пусть

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

относительно преобразований подобия (см. разд. 3.7), то

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

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

Применяя функцию к первому соотношению, а затем используя второе, мы получаем следующее:

Поскольку, однако, то

Это, однако, значит, что, как и требовалось, а .

Если же, с другой стороны, то имеет место Это же означает в свою очередь, что так что существует некоторое изображение принадлежащее алгебре такое что и тогда, естественно, Следовательно,

так что, как и требовалось,

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

Пусть образующие являются линейными функциями заданными на интервалах пространства с невырожденным носителем (содержащим более чем одну точку) и пусть связь-1 (см. рис. 3.9.1) , связь-2 и связь-3 Пусть, используя отношение «равенство», правило отождествляет пары функций на одном и том же интервале (см. рис. 3.9.2).

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

Рис. 3.9.1

Рис. 3.9.2

Рис. 3.9.3

прообразующих -конфигурации, представленные на рис. 3.9.3(a) и имеющие арность, равную четырем; для них связь-3 должна удовлетворять условию Превратим их в образующие (см. рис. 3.9.3(б)), имеющие арность, равную двум, ориентированную регулярность, входную связь в виде вектора и выходную — в виде вектора . Правило идентифицирует вектор-функции. Новая алгебра изоморфна прежней алгебре

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

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

алгебр изображеиий, осуществляемого при помощи задания вида образующих. Введем естественное понятие простого изображения (см. примечания Б).

Определение 3.9.1. Если задана некото рая абстрактная алгебра изображений то изображение называется

простым, если его нельзя нетривиальным способом записать как .

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

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

Лемма 3.9.1. Для сильного правила идентификации количественная сложность изображений представляет собой условно супераддитивную функцию относительно

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

Поскольку действуют условия и поскольку конфигурация регулярна и эквивалентна конфигурации с, то, так как некоторое сильное правило идентификации, Если учесть определение (3.9.12), последнее означает, что

Следовательно, утверждение (3.9.13) справедливо. Если одно или оба изображения имеют бесконечную количественную сложность, прототипы выбираются таким образом, чтобы их количественная сложность превышала некоторое произвольное большое

число М. Повторяя те же рассуждения, можно убедиться в том, что что и требовалось доказать.

Рассмотрим случай и введем множество

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

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

Доказательство. Если то существуют такие, что Если то доказательство закончено. В противном случае по крайней мере одно из изображений не является простым и может быть подвергнуто разбиению. Так, например, если не простое, то существуют изображения такие, что Поскольку, однако, то из Леммы 3.9.1 мы получаем, что так что количественные сложности изображений, рассматриваемых нами, уменьшаются. Следовательно, цепь последовательных разбиений должна после некоторого конечного числа шагов закончиться и мы приходим к разбиению сформулированного в теореме типа. Что и требовалось доказать

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

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

Продолжая изучение представлений абстрактных алгебр изображений, рассмотрим теперь случай, когда локальная регулярность задается отношением связи «включение». Как и прежде, считаем, что тип соединения «линейный».

Основной результат для этого случая выражается в виде следующей теоремы.

Теорема 3.9.3. Для того чтобы алгебра была изоморфна алгебре изображений , в которой о означает «конкатенация справа», а тип регулярности — включение», «линейный»), необходимо и достаточно, чтобы выполнялись следующие условия:

и

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

так что пересечение множеств в (3.9.17) можно записать как пересечение всех где М - такие же, как в соотношении (3.9.18). Следовательно,

где задаются так же, как в соотношении (3.9.18). Следовательно,

далее, используя утверждения (3.9.17), изоморфизм и допуская, что в (3.9.17) включение имеет место, получаем

Последнее соотношение эквивалентно следующему:

Если, в другой стороны, так что то мы автоматически получаем, что

и, следовательно, изоморфизм определяет справедливость левого из соотношений (3.9.17).

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

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

здесь использовано построение из теоремы множество принадлежит пространству, отличному от

Отображение биективно и -ковариантно; последнее показывается так же, как и в случае регулярности типа

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

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

так как

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

Кроме того, в соответствии с условием (3.9.17) имеет место следующее:

Итак, мы показали, что

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

Покажем теперь, что отображение гомоморфно, так что

Левая часть соотношения (3.9.30) означает, однако, что поскольку не принадлежит никакому множеству в

и

и не может быть пустым. Воспользовавшись условием (3.9.17), мы убеждаемся в том, что или, что эквивалентно, что и требовалось доказать.

В этой теореме мы пользовались операцией определенной как

В такой записи условие (3.9.17) принимает удобную форму

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

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

Мы начнем с доказательства одного простого результата, имеющего силу для любого соединителя; он понадобится нам при доказательстве теоремы 3.9.4.

Лемма 3.9.2. Для того чтобы необходимо и достаточно, чтобы .

Доказательство. Очевидно, что, если пусто, то пусто и, следовательно, не может содержать . С другой стороны, если то оно содержит какое-то изображение, скажем так что Тогда, однако, так что утверждение леммы верно. Что и требовалось доказать.

Теперь мы в состоянии сформулировать следующую теорему.

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

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

Доказательство необходимости. Допустим, что где

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

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

На этом рисунке изображение присоединено ко второй входной связи изображения пусть, в общем случае, к входной связи. Следовательно, этот результат можно записать как (на рисунке — третья) входная связь изображения соединена с выходной связью изображения так что

Рис. 3.9.4 (см. скан)

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

Выражения (3.9.35) и (3.9.36) равны, что доказывает справедливость

следующего соотношения ассоциативности:

Соотношение ассоциативности указывает, что, если мы требуем, чтобы выполнялось равенство

то получаем в результате, что . Отношение

определяет пару поставленную в соответствие заданной паре

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

Для доказательства условия (3.9.34) обратим внимание на то, что

Отсюда, как и прежде, при получаем следующее:

Следовательно, если то Если части проверяемого условия обращаются в , так что утверждение верно.

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

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

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

здесь использованы множества определения

где Отметим, что показателем связи в (3.9.42)

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

Пусть любое Г имеет бесконечную входную арность

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

Определения (3.9.42) и (3.9.43) единственны, так как любому изображению соответствует точно одно изображение

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

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

показателю входной связи изображения

Следовательно, необходимо показать, что

Поскольку мы получаем, применяя оператор к обеим частям соотношения, что Применение оператора к отношению дает, однако,

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

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

Это означает, что или

где не пусто. В таком случае, однако, в соответствии с леммой 3.9.2,

так что Что и требовалось доказать.