Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


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


Многосортная алгебра — это упорядоченная пара [math]\bigl((A_i)_{i\in I},\, \Omega\bigr)[/math], где элементы семейства множеств [math](A_i)_{i\in I}[/math] называют сортами, а множество [math]\Omega[/math], называемое многосортной сигнатурой, состоит из многосортных операций — отображений вида


[math]\omega\colon A_{i_1}\times A_{i_2}\times \ldots\times A_{i_n}\to A_{i_0}.[/math]

Операцию [math]\omega[/math] называют при этом n-арной операцией типа [math](i_0,i_1,\ldots, i_n)[/math].


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


В свете определения многосортной алгебры левый модуль над кольцом [math]\mathcal{R}[/math] может быть описан как многосортная алгебра


[math]\mathcal{M}= \bigl((A_1,A_2), +(1,1,1), 0(1), \oplus(2,2,2), \cdot(2,2,2), \bold{0}(2), \bold{1}(2), \circ(1,2,1)\bigr).[/math]

где [math]A_1=G[/math] — носитель абелевой группы [math]\mathcal{G}=(G,+,0)[/math], [math]A_2=R[/math] — носитель кольца [math]\mathcal{R}=(R,\oplus,\cdot,\bold{0},\bold{1})[/math], а [math]\circ\colon R\times G\to G[/math] — многосортная операция левого умножения элементов группы [math]\mathcal{G}[/math] на элементы кольца [math]\mathcal{R}[/math]. Ее тип указывает на то, что первым аргументом является элемент кольца, вторым — элемент абелевой группы, а результат принадлежит абелевой группе.


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


Условимся о следующей терминологии для модуля. Элементы группы [math]\mathcal{G}[/math] будем называть векторами модуля (элементами ппервого сорта"), а элементы кольца [math]\mathcal{R}[/math] — скалярами данного модуля (элементами "второго сорта").


Многосортные алгебры [math]\mathcal{A}=((A_i)_{i\in I}, \Omega)[/math] и [math]\mathcal{B}= ((B_i)_{i\in I}, \Sigma)[/math] называют однотипными, если существует биекция сигнатуры [math]\Omega[/math] на сигнатуру [math]\Sigma[/math], сопоставляющая n-арной операции некоторого типа n-арную операцию того же типа.


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




Пример 4.12. Алгебра [math]\bigl(V_3, \mathbb{R}, +(1,1,1), \cdot(1,2,1), (\cdot)(2,1,1), \times(1,1,1), \circ(2,1,1,1) \bigr)[/math] имеет в качестве первого сорта множество [math]V_3[/math] свободных геометрических векторов (в трехмерном пространстве), а в качестве второго сорта — множество действительных чисел.


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


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


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


Четвертая операция — бинарная операция [math]\times[/math] (векторного умножения векторов), а ее тип — [math](1,1,1)[/math].


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




Описание алгебраической системы как многосортной алгебры


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


Каждому отношению [math]\pi\in\Pi[/math] алгебраической системы [math]\mathcal{A}= (A,\Sigma, \Pi)[/math] сопоставим характеристическую функцию: отображение [math]\xi_{\pi}\colon A^n\to \{0;1\}[/math], такое, что


[math]\xi_{\pi}(a_1,\ldots,a_n)=1\quad \Leftrightarrow\quad (a_1,\ldots,a_n)\in\pi\,.[/math]

Тогда алгебраическую систему можно задать как многосортную алгебру с двумя сортами: носителем [math]A[/math] и "логическим (булевым)" сортом [math]B=\{0;1\}[/math], а вместо каждого n-арного отношения рассматривать его характеристическую функцию как многосортную n-арную операцию типа [math](2,1,\ldots,1)[/math] (номер 1 приписан сорту [math]A[/math], а номер 2 — сорту [math]\mathbb{B}[/math]).




Подалгебры и гомоморфизм в многосротных алгебрах


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


Семейство [math](B_i)_{i\in I}[/math] называют подсемейством семейства [math](A_i)_{i\in I}[/math] (для одного и того же множества индексов [math]I[/math]), если [math](\forall i\in I)(B_i \subseteq A_i)[/math].


Семейство [math](C_i)_{i\in I}[/math] называют объединением (пересечением) семейств [math](A_i)_{i\in I}[/math] и [math](B_i)_{i\in I}[/math], если [math](\forall i\in I)(C_i=A_i\cup B_i)[/math] (соответственно [math](\forall i\in I)(C_i=A_i\cap B_i)[/math]).


Пусть [math]\mathcal{A}=\bigl((A_i)_{i\in I}, \Omega\bigr)[/math] — многосортная алгебра и [math](B_i)_{i\in I}[/math] — подсемейство семейства [math](A_i)_{i\in I}[/math].


Подсемейство [math](B_i)_{i\in I}[/math] называют Ω-замкнутым (или замкнутым относительно операций многосортной сигнатуры [math]\Omega[/math]), если [math]b_{i_1}\ldots b_{i_n} \omega\in B_{i_0}[/math] для всякой n-арной операции [math]\omega\in\Omega[/math] типа [math](i_0,i_1,\ldots,i_n)[/math] (при произвольных [math]n,\,i_0,i_1,\ldots,i_n[/math]) и любых [math]b_{i_1}\in B_{i_1},\ldots,b_{i_n}\in B_{i_n}[/math].


Для Ω-замкнутого подсемейства [math](B_i)_{i\in I}[/math] можно тогда определить однотипную с [math]\mathcal{A}[/math] многосортную алгебру [math]\mathcal{B}=\bigl((B_i)_{i\in I}, \Omega\bigr)[/math], которую называют многосортной подалгеброй алгебры [math]\mathcal{A}[/math].


Можно показать, что пересечение любого семейства Ω-замкнутых подсемейств есть также Ω-замкнутое подсемейство. Следовательно, для произвольного подсемейства [math](C_i)_{i\in I}[/math] семейства [math](A_i)_{i\in I}[/math] существует наименьшее относительно включения Ω-замкнутое подсемейство [math](B_i)_{i\in I}[/math], содержащее подсемейство [math](C_i)_{i\in I}[/math] и называемое тогда Ω-замыканием этого подсемейства. Если Ω-замыкание подсемейства [math](C_i)_{i\in I}[/math] совпадает со всем семейством [math](A_i)_{i\in I}[/math], то первое подсемейство называют системой образующих многосортной алгебры [math]\mathcal{A}[/math].


Семейство отображений [math](h_i)_{i\in I}[/math], где [math]h_i\colon A_i\to B_i,~i\in I[/math], для однотипных многосортных алгебр


[math]\mathcal{A}=\bigl((A_i)_{i\in I}, \Omega\bigr),\qquad \mathcal{B}= \bigl((B_i)_{i\in I}, \Omega\bigr)[/math]

называют многосортным гомоморфизмом алгебры [math]\mathcal{A}[/math] в алгебру [math]\mathcal{B}[/math], если для каждой n-арной операции и [math]\omega\in\Omega[/math] типа [math](i_0,i_1,\ldots,i_n)[/math] (при произвольных [math]n,\,i_0,i_1,\ldots,i_n[/math]) и любых [math]x_{i_1}\in A_{i_1},\ldots,x_{i_n}\in A_{i_n}[/math] есть


[math]h_{i_0}(x_{i_1}\ldots x_{i_n}\omega)= h_{i_1}(x_{i_1})\ldots h_{i_n}(x_{i_n})\omega\,.[/math]

Многосортный гомоморфизм, все отображения которого суть биекции, называют многосортным изоморфизмом алгебры [math]\mathcal{A}[/math] на алгебру [math]\mathcal{B}[/math]. Очевидно, что если существует изоморфизм [math]\mathcal{A}[/math] на [math]\mathcal{B}[/math], то существует и изоморфизм [math]\mathcal{B}[/math] на [math]\mathcal{A}[/math]. Алгебры [math]\mathcal{A}[/math] и [math]\mathcal{B}[/math] называют в этом случае изоморфными многосортными алгебрами.


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


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


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




Пример 4.13. а. Рассмотрим модуль [math]\mathcal{L}_1[/math] над кольцом [math]\mathbb{Z}[/math] целых чисел и модуль [math]\mathcal{L}_2[/math] над кольцом вычетов по модулю [math]k[/math] (для некоторого целого [math]k\geqslant2[/math]). Отображение [math]h_1[/math] определим как произвольный гомоморфизм аддитивной группы векторов первого модуля в аддитивную группу векторов второго, т.е. для любых векторов ж, у первого модуля имеет место равенство


[math]h_1(x+y)=h_1(x)+h_1(y).[/math]

Отображение [math]h_2[/math] зададим как канонический гомоморфизм кольца [math]\mathbb{Z}[/math] в фактор-кольцо [math]\mathbb{Z}_k[/math]. Тогда, если для любого вектора [math]\boldsymbol{x}[/math] первого модуля и любого целого [math]\alpha[/math] выполняется равенство


[math]h_1(\alpha\circ\boldsymbol{x})= h_2(\alpha)\circ h_1(\boldsymbol{x}),[/math]
(4.3)

семейство [math](h_1,h_2)[/math] есть многосортный гомоморфизм первого модуля во второй.


В частности, пусть группа векторов модуля [math]\mathcal{L}_1[/math] есть n-я декартова степень аддитивной группы целых чисел (т.е. группа целочисленных арифметических векторов размерности [math]n[/math] по операции сложения); группу же векторов модуля [math]\mathcal{L}_1[/math] зададим как n-ю декартову степень аддитивной группы вычетов по модулю [math]k[/math] (т.е. как группу по операции сложения по модулю [math]k[/math] целочисленных арифметических векторов размерности [math]n[/math], каждая компонента которых принимает значения от 0 до [math]k-1[/math]). Обозначая через [math][x]_k[/math] остаток от деления [math]x[/math] на [math]k~(x\in \mathbb{Z})[/math], гомоморфизм [math]h_1[/math] зададим равенством [math]h_1(\boldsymbol{x})= [\boldsymbol{x}]_k[/math], где


[math]\boldsymbol{x}= (x_1,\ldots,x_n)\in \mathbb{Z}^n,\qquad \bigl([x_1]_k,\ldots, [x_n]_{k} \bigr)\in\{0,1,\ldots,k-1\}^n.[/math]


По определению, [math]h_2(\alpha)=[\alpha]_k,~ \alpha\in \mathbb{Z}[/math]. Умножение вектора на скаляр в каждом из модулей определим стандартно через умножение в соответствующем кольце, т.е. для первого модуля положим


[math]\alpha\circ \boldsymbol{x}=\alpha\cdot \boldsymbol{x}=(\alpha\cdot x_1,\alpha\cdot x_2,\ldots,\alpha\circ x_n),[/math]

где [math]\alpha\in \mathbb{Z},~ \boldsymbol{x}\in \mathbb{Z}^n[/math], a для второго —


[math]\alpha\circ \boldsymbol{x}= \alpha\odot_{k}\boldsymbol{x}= (\alpha\odot_{k}x_1, \alpha\odot_{k}x_2,\ldots, \alpha\odot_{k}x_n),[/math]

где [math]\alpha\in\{0,1,\ldots,k-1\},~ \boldsymbol{x}\in\{0,1,\ldots,k-1\}^n[/math]. Тогда


[math]h_1(\alpha\circ \boldsymbol{x})= [\alpha\cdot \boldsymbol{x}]_k= [\alpha]_k\odot_{k}[\boldsymbol{x}]_k= h_2(\alpha)\circ h_1(\boldsymbol{x}),[/math]
и равенство (4.3) выполняется.

В то же время если бы гомоморфизм [math]h_1[/math] мы задали как проектирующий, т.е. положили бы


[math]h_1(\boldsymbol{x})= h_1(x_1,x_2,\ldots,x_n)=\boldsymbol{x}_i[/math]

(для некоторого фиксированного [math]i,~ 1\leqslant i\leqslant n[/math]), тогда [math]h_1(\alpha\circ \boldsymbol{x})=\alpha\cdot x_i[/math], а


[math]h_2(\alpha)\circ h_1(\boldsymbol{x})= [\alpha]_k\odot_{k}[x_i]_k= [\alpha\cdot x_i]_k\ne\alpha\cdot x_i\,.[/math]

Таким образом, в этом случае семейство [math](h_1,h_2)[/math] не будет многосортным гомоморфизмом, при том что каждое отображение семейства будет гомоморфизмом соответственно группы и кольца.


Заметим, что, если группы векторов рассмотренных модулей взять соответственно как аддитивную группу целых чисел и аддитивную группу вычетов по модулю [math]k[/math], многосортный гомоморфизм превращается в обычный канонический гомоморфизм кольца [math]\mathbb{Z}[/math].


б. Пусть векторами левого модуля [math]\mathcal{M}_1[/math] являются векторы какого-то конечномерного линейного пространства [math]\mathcal{L}[/math] над полем действительных чисел, а скалярами модуля служат линейные операторы, действующие в этом пространстве. Пусть размерность пространства [math]\mathcal{L}[/math] равна [math]n[/math]. В качестве векторов модуля [math]\mathcal{M}_2[/math] рассмотрим линейное пространство действительных матриц-столбцов типа [math]n\times1[/math], а скаляров — квадратные матрицы n-го порядка (см. пример 2.12.г). Зафиксировав в пространстве [math]\mathcal{L}[/math] базис, зададим отображение [math]h_1[/math] так, чтобы оно каждому вектору из [math]\mathcal{L}[/math] сопоставляло столбец его координат в данном базисе, а отображение [math]h_2[/math] пусть для каждого линейного оператора, действующего в пространстве [math]\mathcal{L}[/math], дает его матрицу в том же базисе. Основываясь на известных результатах линейной алгебры, можно утверждать, что тем самым определен многосортный изоморфизм модуля [math]\mathcal{M}_1[/math] на модуль [math]\mathcal{M}_2[/math].




Замечание 4.6. Как и для обычного "односортного" случая, в теории многосортных алгебр можно доказать теоремы, аналогичные теоремам 4.3 и 4.4 и связывающие понятия многосортного гомоморфизма и многосортной фактор-силгебры. Не рассматривая этот вопрос подробно, заметим, что переход от многосортной алгебры [math]\mathcal{A}=((A_i)_{i\in I}, \Omega)[/math] к ее фактор-алгебре осуществляется на основе многосортной конгруэнции — такого семейства отношений эквивалентности [math](\rho_i\subseteq A_i^2)_{i\in I}[/math], что для любых попарно эквивалентных элементов [math]a_i,b_i\in A_i,~i\in I[/math], т.е. таких, что [math]a_i\,\rho_i\,b_i[/math], имеет место также и эквивалентность [math](a_{i_1}\ldots a_{i_n}\omega)\,\rho_{i_0}\,(b_{i_1}\ldots b_{i_n}\omega)[/math], какова бы ни была n-арная операция [math]\omega\in\Omega[/math] типа [math](i_0,i_1,\ldots,i_n)[/math]. Тогда любая такая операция может быть распространена на семейство фактор-множеств [math]\bigl((A_i/\rho_i)_{i\in I},\Omega\bigr)[/math] согласно равенству


[math][a_{i_1}\ldots a_{i_n}\omega]_{\rho_{i_0}}= [a_{i_1}]_{\rho_{i_1}}\ldots [a_{i_n}]_{\rho_{i_n}}\omega\,.[/math]

Определенную таким образом многосортную алгебру называют фактор-алгеброй исходной алгебры [math]\mathcal{A}=((A_i)_{i\in I},\Omega)[/math] относительно многосортной конгруэнции [math](\rho_i)_{i\in I}[/math].


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


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved