Морфизмы алгебраических систем

Пусть даны алгебраические системы: α=<A,∑>, β=<B,∑>. Отображение φ: А→В называется гомоморфизмом системы α в систему β, если выполняются следующие условия:

1) должно выполняться согласование для функциональных символов

2) должно выполняться согласование предикатных символов

Если φ: А→В – гомоморфизм, то будем писать φ: α→β.

При гомоморфизме сохраняются действия операций и отношения.

Гомоморфизм φ: α→β, являющийся инъекцией, называется мономорфизмом (т.е. )

Гомоморфизм φ: α→β, являющийся сюръекцией, называется эпиморфизмом, и при этом система β называется гомоморфным образом системы α.

Сюръективный мономорфизм φ: α→β, для которого φ^-1 – гомоморфизм, называется изоморфизмом (φ: α≈β).

Изоморфизм φ: α→α называется автоморфизмом системы α.

Утверждения:

1) id_A: α≈α (Рефлексивность)

2) если φ: α≈β, то φ^-1: β≈α (симметричность)

3) если φ: α≈β и ψ: β≈γ, то φ•ψ: α≈γ (транзитивность)

12. Подсистемы. Термы сигнатуры ∑. Подсистема, порожденная множеством, ее структура.

Алгебраическая система α=<A,∑> называется подсистемой системы β=<B,∑>, если выполняются следующие условия:

2) для любого функционального символа , соответствующих функций и любых элементов выполняется равенство f_α(a₁,…, a_n) = f_β(a₁,…, a_n), т.е интерпретации символа f действуют одинаково на элементах из А

3) для любого предикатного символа , соответствующих предикатов Р_α, Р_β справедливо равенство , т.е. предикат Р_α содержит в точности те кортежи отношения Р_β, которые состоят из элементов множества А.

Если ∑ - функциональная (предикатная) сигнатура, то подсистема α алгебры (модели) β называется подалгеброй (подмоделью).

Теорема: Если β – алгебраическая система, , , то существует единственная подсистема с носителем В(Х), такая, что и для любой подсистемы , для которой .

Доказательство: В качестве В(Х) рассмотрим пересечение носителей А всех подсистем , содержащих Х. Т.к. , то . Единственность подсистемы β(Х) очевидна.

Подсистема β(Х) из данной теоремы называется подсистемой, порожденной множеством Х в β. Она является наименьшей подсистемой системы β, содержащей множество Х.

Для описания устройства подсистемы β(Х) определим индукцией понятие терма сигнатуры ∑:

1) переменные и константные символы из ∑ есть суть термы

2) если - n-местный функциональный символ, t₁,…, t_n – термы, то f(t₁,… t_n) – терм

3) никаких термов, кроме построенных по пп. 1,2, нет.

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

Пусть t(x₁,…, x_k) – терм из Т(∑), все переменные которого содержаться среди x₁,…, x_k_;α=<A,∑> - алгебраическая система. Значение терма t при значениях переменных x₁,…, x_k (t(a₁,..., a_k)) определяется по индукции:

1) если t – переменная x_i (константный символ с), то значение t есть a_i (c).

2) если терм t есть f(t₁,…, t_n), а t₁(a₁,…, a_k)=b₁,…, t_n(a₁,…, a_k)=b_n, то t(a₁,…, a_k)=b(t₁,…, t_n)

Теорема (о структуре подсистемы, порожденной множеством): Если β=<B,∑> - алгебраическая система, , то носитель подсистемы

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