Алгебры слов (термов) - Формационные основы универсальных алгебр

    7.1. Пусть - некоторая сигнатура, - произвольное множество, в частности пустое. Построим множество - слов (- термов) индуктивно следующим образом: 1)элементы множества являются - словами ; 2)символы нульарных операций являются - словами; 3)если - некоторая совокупность - слов и - какая-либо - арная операция, то выражение или является - словом.

Считая сигнатуру фиксированной, вместо "- слово " будем употреблять термин "слово" и обозначать через.

Приведем некоторые примеры.

7.2. Пусть, , где - бинарная, а - 0-арная операция. Тогда словами, например, являются следующие выражения:

.

7.3. , , где - тернарная, - бинарная, - унарная, а 0-нульарная операции. Тогда примерами слов являются:

.

Отметим, что, например, выражения

Словами не являются.

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

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

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

Доказательство.

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

, то

.

Следовательно, , если элементы считать принадлежащими алгебре. Таким образом доказано, что -- подалгебра алгебры и так как, то.

Теорема доказана.

7.5. Следствие. Если - алгебра, порожденная множеством, и - гомоморфизмы алгебры в алгебру и для всех, то

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

.

Следствие доказано.

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

Доказательство. Пусть, для любого. Тогда для любого слова положим

.

Как и выше, непосредственной проверкой убеждаемся в том, что - гомоморфизм. Его единственность следует из следствия 7.5.

Теорема доказана.

7.7 Теорема: Любая алгебра сигнатуры изоморфна фактор алгебре некоторой абсолютно свободной алгебры сигнатуры.

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

.

Теорема доказана.

Похожие статьи




Алгебры слов (термов) - Формационные основы универсальных алгебр

Предыдущая | Следующая