Морфизмы алгебраических систем
Пусть даны алгебраические системы: α=<A,∑>, β=<B,∑>. Отображение φ: А→В называется гомоморфизмом системы α в систему β, если выполняются следующие условия:
1) должно выполняться согласование для функциональных символов
2) должно выполняться согласование предикатных символов
Если φ: А→В – гомоморфизм, то будем писать φ: α→β.
При гомоморфизме сохраняются действия операций и отношения.
Гомоморфизм φ: α→β, являющийся инъекцией, называется мономорфизмом (т.е. )
Гомоморфизм φ: α→β, являющийся сюръекцией, называется эпиморфизмом, и при этом система β называется гомоморфным образом системы α.
Сюръективный мономорфизм φ: α→β, для которого φ-1 – гомоморфизм, называется изоморфизмом (φ: α≈β).
Изоморфизм φ: α→α называется автоморфизмом системы α.
Утверждения:
1) idA: α≈α (Рефлексивность)
2) если φ: α≈β, то φ-1: β≈α (симметричность)
3) если φ: α≈β и ψ: β≈γ, то φ•ψ: α≈γ (транзитивность)
12. Подсистемы. Термы сигнатуры ∑. Подсистема, порожденная множеством, ее структура.
Алгебраическая система α=<A,∑> называется подсистемой системы β=<B,∑>, если выполняются следующие условия:
1)
2) для любого функционального символа , соответствующих функций
и любых элементов
выполняется равенство fα(a1,…, an) = fβ(a1,…, an), т.е интерпретации символа f действуют одинаково на элементах из А
3) для любого предикатного символа , соответствующих предикатов Рα, Рβ справедливо равенство
, т.е. предикат Рα содержит в точности те кортежи отношения Рβ, которые состоят из элементов множества А.
Если ∑ - функциональная (предикатная) сигнатура, то подсистема α алгебры (модели) β называется подалгеброй (подмоделью).
Теорема: Если β – алгебраическая система, ,
, то существует единственная подсистема
с носителем В(Х), такая, что
и
для любой подсистемы
, для которой
.
Доказательство: В качестве В(Х) рассмотрим пересечение носителей А всех подсистем , содержащих Х. Т.к.
, то
. Единственность подсистемы β(Х) очевидна.
Подсистема β(Х) из данной теоремы называется подсистемой, порожденной множеством Х в β. Она является наименьшей подсистемой системы β, содержащей множество Х.
Для описания устройства подсистемы β(Х) определим индукцией понятие терма сигнатуры ∑:
1) переменные и константные символы из ∑ есть суть термы
2) если - n-местный функциональный символ, t1,…, tn – термы, то f(t1,… tn) – терм
3) никаких термов, кроме построенных по пп. 1,2, нет.
Таким образом, термом является любое функциональное выражение, составленное с помощью сигнатурных функциональных символов. Множество всех термов сигнатуры ∑ обозначается через Т(∑).
Пусть t(x1,…, xk) – терм из Т(∑), все переменные которого содержаться среди x1,…, xk; α=<A,∑> - алгебраическая система. Значение терма t при значениях переменных x1,…, xk (t(a1,..., ak)) определяется по индукции:
1) если t – переменная xi (константный символ с), то значение t есть ai (c).
2) если терм t есть f(t1,…, tn), а t1(a1,…, ak)=b1,…, tn(a1,…, ak)=bn, то t(a1,…, ak)=b(t1,…, tn)
Теорема (о структуре подсистемы, порожденной множеством): Если β=<B,∑> - алгебраическая система, , то носитель подсистемы
Доказательство: Индукцией по числу шагов построения терма t получаем, что если и
, то
для любой подсистемы
, содержащей Х. Поэтому достаточно показать, что множество
замкнуто относительно операций системы β. Пусть
. Тогда
, поскольку
.
Таким образом, носитель подсистемы β(Х) состоит из всех элементов, которые получаются при подстановке элементов из Х в термы.