Многосортные алгебры

^Теория

Среди всех алгебр, рассмотренных выше, несколько особое положение занимает модуль (и, как частный случай, линейное пространство). Модуль был определен как алгебра, в сигнатусигнатуру которой входят бинарная операция сложения и бесконечное (в общем случае) множество унарных операций. Относительно операции сложения модуль является абелееой группой, а множество унарных операций имеет структуру кольца. Каждая унарная операция рассматривается как умножение (левое или правое) элементов модуля на тот или иной элемент этого кольца. Проще было бы интерпретировать такое умножение как бинарную операцию, но это не вписывается в определение бинарной операции, поскольку аргументами умножения оказываются элементы двух разных алгебр. Модуль представляет собой как бы „ симбиоз " двух алгебр: абелевой группы и кольца. Это обстоятельство наводит на мысль ввести алгебраические системы с несколькими носителями. Так возникает идея многосортной алгебры.

Многосортная алгебра — это упорядоченная пара

((A)_i)_i∈I, Ω),

где элементы семейства множеств(A)_i)_i∈I называют сортами, а множество Ω, называемое многосортной сигнатурой, состоит из многосортных операций — отображений вида

ω: A_i₁×...× A_{i_n} → A_i₀

Операцию ω называют при этом n-арной операцией типа (i₀, i₁, ..., i_n).

Задавая конкретную многосортную алгебру, условимся, что будем записывать ее в виде кортежа, в котором сначала пере- перечисляется семейство сортов (как правило, конечное), а затем — многосортные операции, образующие сигнатуру, причем после обозначения каждой операции пишется ее тип (в виде кортежа). Обратим еще раз внимание на то, что в типе операции первая компонента указывает на сорт результата операции, следующие компоненты суть номера сортов аргументов операции. Заметим, что тип нулъарной операции в многосортной алгебре есть однокомпонентный кортеж: нульарная операция типа (i) — это фиксированный элемент, принадлежащий сорту А_i.

В свете определения многосортной алгебры левый модуль над кольцом R может быть описан как многосортная алгебра

М = ((А₁А₂), +(1,1,1), 0(1), ⊕(2,2,2), ⋅ (2,2,2), 0(2), 1(2), ॰(1,2,1)),

где А₁ = G — носитель абелевой группы g = (G, +, 0), А₂ = R — носитель кольца R = (R, ⊕, ⋅, 0, 1), а ॰: R x G → G — многосортная операция левого умножения элементов группы g на элементы кольца R. Ее тип указывает на то, что первым аргументом является элемент кольца, вторым — элемент абелевой группы, а результат принадлежит абелевой группе.

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

Условимся о следующей терминологии для модуля. Элементы группы g будем называть векторами модуля (элементами „первого сорта"), а элементы кольца R — скалярами данного модуля (элементами vвторого сорта").

Многосортные алгебры

A = ((A)_i)_i∈I, Ω и B = ((B)_i)_i∈I∑)

называют однотипными, если существует биекция сигнатуры Ω сигнатуру ∑, сопоставляющая n-арной операции некоторого типа n-арную операцию того же типа.

Сигнатуры однотипных многосортных алгебр и соответ- соответствующие друг другу элементы этих сигнатур (т.е. многосорт- многосортные операции) обычно обозначают одинаково.

Пример 4.12. Алгебра

(V₃, ℝ +(1,1,1), ⋅(1,2,1), (⋅)(2,1,1), х(1,1,1), ॰(2,1,1,1))

имеет в качестве первого сорта множество V₃ свободных геометрических векторов (в трехмерном пространстве)[III], а в качестве второго сорта — множество действительных чисел.

Первая операция — бинарная операция + (сложения векторов). Результатом операции является вектор, аргументами — также векторы, поэтому она имеет тип (1,1,1).

Вторая операция — бинарная операция ⋅ (левого умножения вектора на число). Результат операции — вектор, первый аргумент — число, второй аргумент — вектор, поэтому тип операции — (1,2,1).

Третья операция — бинарная операция (⋅) (скалярного умножения векторов). Ее результатом является число, и ее тип есть (2,1,1).

Четвертая операция — бинарная операция х (векторного умножения векторов), а ее тип — (1,1,1).

Последняя, пятая операция — тернарная операция смешанного умножения векторов. Результатом операции является число, и соответственно сорт операции — (2,1,1,1). #

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

Каждому отношению π ∈ П алгебраической системы A = (A, Ω, П) сопоставим характеристическую функцию: отображение ξ_π: Aⁿ → {0,1}, такое, что

ξ_π(a₁ ,..., a_n) = 1 ⇔ (a₁ ,..., a_n) ∈π.

Тогда алгебраическую систему можно задать как многосортную алгебру с двумя сортами: носителем А и „логическим (булевым)" сортом В = {0,1}, а вместо каждого n-арного отношения рассматривать его характеристическую функцию как многосортную n-арную операцию типа (2, 1, ..., 1) (номер 1 приписан сорту А, а номер 2 — сорту В).

Рассмотрим теперь, как на многосортные алгебры распространяются понятия подалгебры и гомоморфизма.

Семейство (B)_i)_i∈I называют подсемейством семейства (A)_i)_i∈I (для одного и того же множества индексов I), если (∀_i ∈ I) (B_i ⊆ A_i.

Семейство (C)_i)_i∈I называют объединением (пересечением) семейств (A)_i)_i∈I и (B)_i)_i∈I, если (∀_i ∈ I) (C_i = A_i ∪ B_i )(соответственно (∀_i ∈ I) (C_i = A_i ∩ B_i)).

Пусть A = ((A)_i)_i∈I, Ω) — многосортная алгебра и (B)_i)_i∈I — подсемейство семейства (A)_i)_i∈I.

Подсемейство (B)_i)_i∈I называют Ω-замскнутым (или замкнутым относительно операций многосортной сигнатуры Ω), если b_i₁ ... b_{i_n} ω ∈ B_i₀ для всякой n-арной операции ω ∈ Ω типа (i₀, i₁, ..., i_n) (при произвольных n, i₀, i₁, ..., i_n) и любых b_i₁ ∈ B_i₁,..., b_{i_n} ∈ B_{i_n}.

Для Ω-замкнутого подсемейства (B)_i)_i∈I можно тогда определить однотипную с A многосортную алгебру В =((B)_i)_i∈I, Ω), которую называют многосортной подалгеброй алгебры A.

Можно показать, что пересечение любого семейства Ω-замкнутых подсемейств есть также Ω-замкнутое подсемейство. Следовательно, для произвольного подсемейства (C)_i)_i∈I семейства (A)_i)_i∈I существует наименьшее относительно включения Ω-замкнутое подсемейство(B)_i)_i∈I, содержащее подсемейство (C)_i)_i∈I и называемое тогда Ω-замыканием этого подсемейства. Если Ω-замыкание подсемейства (C)_i)_i∈I совпадает со всем семейством (A)_i)_i∈I, то первое подсемейство называю системой образующих многосортной алгебры А.

Семейство отображений (h_i)_i∈I, где h_i: A_i → B_i i∈ I, для однотипных многосортных алгебр

A = ((A)_i)_i∈I, Ω) и B = ((B)_i)_i∈I, Ω)

называют многосортным гомоморфизмом алгебры А в алгебру B, если для каждой n-арной операции ω ∈ Ω типа (i₀, i₁, ..., i_n) (при произвольных n, i₀, i₁, ..., i_n) и любых x_i₁ ∈ A_i₁,...,x_{i_n} ∈ A_{i_n}

h_i₁(x_i₁ ... x_{i_n} ω) = h_i₁(x_i₁) ... h_{i_n}(x_{i_n}) ω.

Многосортный гомоморфизм, все отображения которого суть биекции, называют многосортным изоморфизмом алгебры А на алгебру В. Очевидно, что если существует изоморфизм А на B, то существует и изоморфизм В на А. Алгебры А и В называют в этом случае изоморфными многосортными алгебрами.

Аналогично обычным алгебрам в многосортных алгебрах вводят понятия многосортного моно- и эпиморфизма.

В качестве простого примера сошлемся на понятие линей- линейного оператора (для линейных пространств над одним и тем же полем), известного из курса линейной алгебры [IV]. Оно является не чем иным, как многосортным гомоморфизмом, где отображение носителя одного поля в носитель другого является тождественным отображением.

Более сложными будут следующие примеры.

Пример 4.13. а. Рассмотрим модуль L₁ над кольцом ℤ целых чисел и модуль L₂ над кольцом вычетов по модулю k (для некоторого целого k ≥ 2). Отображение h₁ определим как произвольный гомоморфизм аддитивной группы векторов первого модуля в аддитивную группу векторов второго, т.е. для любых векторов x, у первого модуля имеет место равенство

h₁(x+y) = h₁(x) + h₁(y).

Отображение h₂ зададим как канонический гомоморфизм кольца ℤ в фактор-кольцо ℤ_k. Тогда, если для любого вектора х первого модуля и любого целого а выполняется равенство

h₁(a॰x) = h₂(α) ॰ h₁(x), (4.3)

семейство (h₁, h₂) есть многосортный гомоморфизм первого модуля во второй.

В частности, пусть группа векторов модуля L₁ есть n-я декартова степень аддитивной группы целых чисел (т.е. группа целочисленных арифметических векторов размерности n по операции сложения); группу же векторов модуля L₂ зададим как n-ю декартову степень аддитивной группы вычетов по модулю к (т.е. как группу по операции сложения по модулю к целочисленных арифметических векторов размерности n, каждая компонента которых принимает значения от 0 до k — 1). Обозначая через [x]_k остаток от деления х на k: (х ∈ ℤ), гомоморфизм h₁ зададим равенством h₁(x) = [x]_k, где x = (x₁, ..., x_n) ∈ ℤⁿ, a [x]_k = ( [x₁]_k, ..., [x_n]_k) ∈ {0,1, ..., k - 1}ⁿ. По определению, h₂(α) = [α]_k, α ∈ ℤ . Умножение вектора на скаляр в каждом из модулей определим стандартно через умножение в соответствующем кольце, т.е. для первого модуля положим

α॰x = α⋅x = (α⋅x₁, ..., α⋅x_n),

где α ∈ ℤ, x ∈ ℤⁿ, a для второго —

α॰x = α⨀_kx = (α⨀_kx₁, ..., α⨀_kx_n),

где α ∈ {0, 1, ..., k - 1}, x ∈ {0, 1 ..., k - 1}ⁿ. Тогда

h₁(α॰x) = [α⋅x]_k = [α]_k⨀_k[x]_k = h₂(α)॰ h₁(x),

и равенство (4.3) выполняется.

В то же время если бы гомоморфизм h₁ мы задали как проектирующий, т.е. положили бы

h₁(x) = h₁(x₁, ..., x_n) = x_i

(для некоторого фиксированного i, 1≤i≤n), тогда h₁(α॰x) = α⋅x_i, а

h₂(α) ॰ h₁(x) = [α]_k⨀_k[x_i]_k = [α⋅x_i]_k ≠ α⋅x_i.

Таким образом, в этом случае семейство (h₁, h₂) не будет многосортным гомоморфизмом, при том что каждое отображение семейства будет гомоморфизмом соответственно группы и кольца.

Заметим, что, если группы векторов рассмотренных модулей взять соответственно как аддитивную группу целых чисел и аддитивную группу вычетов по модулю k, многосортный гомоморфизм превращается в обычный канонический гомоморфизм кольца ℤ.

б. Пусть векторами левого модуля M₁ являются векторы какого-то конечномерного линейного пространства L над полем действительных чисел [IV], а скалярами модуля служат линейные операторы, действующие в этом пространстве. Пусть размерность пространства L равна n. В качестве векторов модуля M₂ рассмотрим линейное пространство действительных матриц-столбцов типа n х 1, а скаляров — квадратные матрицы n-го порядка. Зафиксировав в пространстве L базис, зададим отображение h₁ так, чтобы оно каждому вектору из L сопоставляло столбец его координат в данном базисе, а отображение h₂ пусть для каждого линейного оператора, действующего в пространстве L, дает его матрицу в том же базисе. Основываясь на известных результатах линейной алгебры [IV], можно утверждать, что тем самым определен многосортный изоморфизм модуля M₁ на модуль M₁.

Замечание 4.6. Как и для обычного „односортного" с случая, в теории многосортных алгебр можно доказать теоремы, аналогичные теоремам 4.3 и 4.4 и связывающие понятия многосортного гомоморфизма и многосортной фактор-алгебры. Не рассматривая этот вопрос подробно, заметим, что переход от многосортной алгебры А = ((A_i)_i∈I, Ω) к ее фактор-алгебре осуществляется на основе многосортной конгруэнции — такого семейства отношений эквивалентности (р_i ⊆ А²ⁱ)_i∈I, что для любых попарно эквивалентных элементов a_i, b_i ∈ A_i, i ∈ I, т.е. таких, что a_ip_ib_i, имеет место также и эквивалентность {a_i₁ ...{a_{i_n}ω) p_i₀ (b_i₁ ... b_{i_n}ω) какова бы ни была n-арная операция ω ∈ Ω типа (i₀, i₁, ..., i_n). Тогда любая такая операция может быть распространена на семейство фактор-множеств согласно равенству

[a_i₁ ... a_{i_n}ω] _{p_i₀} = [a_i₁]_{p_i₁} ... [a_{i_n}]_{p_{i_n}} ω.

Определенную таким образом многосортную алгебру называют фактор-алгеброй исходной алгебры A = ((A)_i)_i∈I, Ω) относительно многосортной конгруэнции (p_i)_i∈I. #

Многосортные алгебры широко используются в современном теоретическом программировании*.