11. Отношение гомоморфизма на алгебраических системах. Представление отношения гомоморфизма на языке семантических сетей.

Реляционная структура А называется гомомофорной реляционной структуре В, тогда и только тогда, когда:

1. Каждому первичному элементу реляционной структуры А однозначно соответствует первичный элемент структуры В;

2. Каждому сигнатурному множеству реляционной структуры А однозначно соответствует сигнатурное множество структуры В;

3. Каждому сигнатурному отношению реляционной структуры А однозначно соответствует сигнатурное отношение структуры В;

4. Каждому сигнатурному атрибуту реляционной структуры А однозначно соответствует сигнатурный атрибут структуры В.

5. Кроме этого: если элемент е структуры А включен во множество s в рамках этой структуры, т.е. существует дуга , то однозначно соответствующий ему элемент е* реляционной структуры В, должен быть включен во множествоs*, включенное в реляционную структуру В, причем s* - элемент, однозначно соответствующий элементу s в рамках рассматриваемого отношения гомоморфизма , а также дуга включена в реляционную структуру В и также является элементом, однозначно соответствующим дугев рамках рассматриваемого отношения гомоморфизма.

Пусть даны две алгебры A= (К; ₁,..., _р) и В= (М; ₁, ..., _p) одинакового типа. Гомоморфизмом алгебры A в ал­гебру В называется отображение Г: К->М, удовлетворяющее условию

Г(_i,(k_j1, ... ,k_jl(i).))=_i(Г(k_j1), ... .Г(k_jl(i)) (2.1)

для всех i=l,..., p(i) —арность операций _i и _i,, которая у них по условию одинакова] и всех k_jr К. Смысл условия (2.1) в том, что независимо от того, выполнена ли сначала операция _i в А и затем произведено отображение Г, либо сначала произведено отображение Г, а затем в В выполнена соответствующая операция _i, результат будет одинаков.

Пример гомоморфизма

12. Отношение изоморфизма и автоморфизм алгебраических систем. Представление отношения изоморфизма и автоморфизма на языке семантических сетей.

Изоморфизмом алгебры A на алгебру В называется взаимно однозначный гомоморфизм. В этом случае существует обратное отображение Г^-1: М->К„ также взаимно однозначное. Пусть Г(k_j)=m_j, m_j M. Тогда k_j=Г^-1(m_j). Заменим в условии (2.1) левые части этих равенств на правые и применим Г^-1 к обеим частям получившегося равенства. Так как Г^-1 Г является тождественным отображением Г^-lГ(a)=a, то получим:

_i (Г-¹ (m_i1), ... , Г-¹ (m_il(i)) == Г^-1 _i (m_i1, ... , m_il(i)). (2.2)

Равенство (2.2)—это то же равенство (2.1) с заменой Г на Г^-1, элементов К. на элементы М и переменой местами _i и _i; иначе говоря, Г^-1 — это изоморфизм В на A. Итак, если существует изоморфизм A на В, то существует изоморфизм и на A; при этом алгебры A и В называются изоморфными. Мощности основных множеств изоморфных алгебр равны (при гомоморфизме это равенство может не выполняться). Если A=В, то изоморфизм называется изоморфизмом на себя, или автоморфизмом; если BA, то изоморфизм называется изоморфизмом в себя.

Отношение изоморфизма является отношением эквивалентности на множестве алгебр. Рефлексивность его очевидна, симметричность следует из существования обратного изоморфизма, а транзитивность устанавливается следующим образом: если Г₁ — изоморфизм A на В, Г₂ —изоморфизм В на С, то изоморфизмом A на С будет композиция Г₁ и Г₂. Классами эквивалентности в разбиении по отношению изоморфизма являются классы изоморфных между собой алгебр.

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

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

Пример отношения изоморфизма:

Пример отношения автоморфизма: