3.6. Теоретико-множественные операции в ...

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

В данном разделе мы остановимся на операциях, ие являющихся аддитивными, и начнем мы с операции соединение. Пусть

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

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

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

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

Теорема 3.6.1. Если — некоторая монотонная неубывающая операция над множеством, определим итеративное замыкание операции как

Тогда:

Доказательство. Для того чтобы доказать утверждение (I), достаточно обратить внимание на то, что

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

определяемого монотонностью и, подобным же образом, если заменить А на так что

Применив к обеим частям этого соотношения монотонную операцию на основании условия (I) получаем, что

С другой стороны, поскольку а следовательно, и — неубывающие, то

так что

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

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

принимают значения от 1 до произвольное преобразование подобия.

Замечание. В отличие от случая (3.6.1) в (3.6.9) индексы могут повторяться.

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

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

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

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

Пусть задано снова 2 — «монотонный»;

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

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