1.3.5. Гомоморфизмы и изоморфизмы

Алгебра – это множество М вместе с заданными на нем операциями {φ₁, φ₂, …, φ_m}. Обозначение алгебры:

AЛ =(M; φ₁, φ₂, …, φ_m),

где М называется основным множествам, а ∑={φ₁, φ₂, …, φ_m} - сигнатурой алгебры AЛ.

Пример 5.

Множество натуральных чисел N с операцией умножения * на нем, т.е. AЛ= {N;*).

Типом алгебры AЛ называется вектор арностей операций сигнатуры.

Множество М вместе с заданными на нем отношениями {R₁, R₂, …, R_n} называется моделью. Обозначение модели:

MО =(M; R₁, R₂, …, R_n),

где М - несущее множество, ∑={R₁, R₂, …, R_n} - сигнатура модели MО.

Пример 6.

а) Моделью MО является множество А, чисел с отношениями: «быть больше» и «меньше» MО = (А; >,<);

б) Множество людей В с отношением R - "быть менеджером" задает модель MО = (В; R).

Множество М вместе с заданными на нем операциями {φ₁, φ₂, …,φ_m} и отношениями {R₁, R₂, …, R_n} называется алгебраической системой, или алгебраической структурой. Обозначение алгебраической структуры:

АС =(M; φ₁, φ₂, …,φ_m; R₁, R₂, …, R_n).

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

Пусть между множествами А и В установлено соответствие Г – отображение А в B, т.е. Г: А → В. Это означает, что каждому элементу а из А поставлен в соответствие Г единственный элемент α из В, т.е. Г(а) = α. Пусть также на множестве А задана операция φ, на множестве В - операция ψ, обе одинаковой арности, например обе бинарные, так что a φ b = c, , и α ψ β = γ, α,β,γ . В результате получается две алгебры (А; φ) и (В; ψ).

Тогда отображение Г:А→В называется гомоморфизмом алгебры (А; φ) в алгебру (В; ψ), если выполняется условие:

Г(а φ b) = Г(a) ψ Г(b) (3.1)

Условие гомоморфизма (3.1) требует (рис. 1.9), чтобы отображение Г результата с = аφb выполнения на множестве А операции φ над элементами а и b, т.е. Г (с) = Г(а φ b), совпадало с результатом γ выполнения на множестве В операции ψ над отображениями этих элементов, т.е. над Г(а) = α и Г(b) =β.

Проверка условия гомоморфизма заключается в следующем. В соответствии с левой частью условия (3.1) сначала над элементами а и b из A должна быть выполнена операция φ, а затем результат с = а φ b выполнения операции φ отображается из А в множество В. В соответствии с правой частью условия (3.1) требуется сначала выполнить отображения элементов a и b из множества A в B, т.е. найти Г(a) =α и Г(b) = β, a затем над α и β выполнить операцию ψ (заданную на множестве В), т.е. Г(а) ψ Г(b), или α ψ β = γ. Условие (3.1) будет выполнено, если результат отображения элемента с = а φ b из А в В совпадает с элементом γ из В, т.е. если Г(с) = γ.

Если при этом отображение Г: А → В является взаимно однозначным соответствием, оно называется изоморфизмом алгебры (А; φ) на алгебру (В; ψ). В этом случае существует и обратное отображение Г^-1: В → А, также взаимно однозначное:

Г^-1(α ψ β) = Г^-1(α) φ Г^-1(β).

Отображение Г^-1 - это изоморфизм В на А. Если существует изоморфизм А на В, то существует изоморфизм В на А. При этом алгебры (А; φ) и (В; ψ) называются изоморфными.

Другими словами, если на множествах А и В заданы несколько операций соответственно (А; φ₁, φ₂, …,φ_m) и (В; ψ₁, ψ₂, …,ψ_m), отображение Г: А→ В является гомоморфизмом алгебры (А; φ₁, φ₂, …,φ_m) в алгебру (В; ψ₁, ψ₂, …,ψ_m), если условия, аналогичные (3.1), выполняются для каждой пары операций φ₁ и ψ₁, …, φ_m и ψ_m.

В силу взаимной однозначности соответствия Г: А → В при изоморфизме мощности основных множеств изоморфных алгебр равны. Поэтому проверка алгебр на изоморфизм сводится к проверке условия гомоморфизма для каждой пары операций и установления взаимной однозначности соответствия Г (равной мощности множеств А и В).

Аналогично определяется гомоморфизм (изоморфизм) множеств с отношениями - моделей (A; R₁, R₂, …, R_n) (B; R₁', R₂', …, R_n').

Пусть на множестве А задано бинарное отношение R(a,b), где a,b А, и на множестве В - бинарное отношение R'(α, β), где α,β В. Тогда отображение Г: А → В является гомоморфизмом модели (А; R) в модель (В; R'), если для любой пары элементов a, b из А такой, что а и b находятся в отношении R следует, что их отображения Г(а) = α и Г(b)= β находятся в отношении R' (рис. 1.10).

a R b влечет Г(а) R' Г(b) для любых а, b А. (3.2)

Если при этом отображение Г: А →В является взаимно однозначным соответствием, оно называется изоморфизмом модели (А; R) на модель (В; R'). В этом случае существует и обратное отображение Г^-1: В →А, также являющееся изоморфизмом: α R' β влечет Г^-1(α) R Г^-1(β) для любых α, β В. При этом модели (A: R) и (В: R’) называются изоморфными.

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

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

Пример 7.

Пусть М₁, - множество сотрудников организации и R₁ - заданное на нем отношение «быть старше»; М₂ - конечное множество натуральных чисел (ограниченное числом 75) и R₂ - заданное на нем отношение «быть больше». Гомоморфны или изоморфны модели AЛ1 =(М₁; >) и АЛ2 =(М₂;>)?

Во первых посмотрим гомоморфны ли модели. Определим отображение Г:М₁→ М₂: каждому сотруднику организации из М₁, поставим в соответствие Г число из М₂, соответствующее его возрасту (в годах). Установленное таким образом отображение Г:М₁→М₂, является гомоморфизмом моделей AЛ1 =(М₁;>) и АЛ2 =(М₂;>), так как выполняется условие (3.2): «если Иванову 37 лет то он старше Петрова 26 лет», т.е. «Иванов > Петро».

Так как Г(«Иванов») = 37 и Г(«Петров»)= 26, то и 37 > 26.

Установленное отображение Г:М₁→ М₂, не является изоморфизмом моделей AЛ1 =(М₁;>) и АЛ2 =(М₂;>), так как не является в общем случае взаимно однозначным (если в организации имеются сотрудники одною возраста, например «Петров» 26 лет и «Сидоров» 26 лет. В этом случае обратное соответствие Г^-1 не является отображением, поскольку не функционально (отсутствует единственность образа 26 на множество сотрудников организации).

Таким образом, заданные модели AЛ1 =(М₁;>) и АЛ2 =(М₂;>) гомоморфны, но не изоморфны.