WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 9 | 10 ||

Здесь X некоторая подалгебра A.

Покажем теперь, что в данных условиях AB можно заменить на XB. Действительно, AX в силу влечёт AX, что, в свою очередь, эквивалентно XA в силу симметричности конгруэнций. Вместе с AB это означает, что справедливо XA AB, т.е. X2B или XB.

Таким образом, X ( AB AX XB ) X ( AX XB XB ) X ( AX X( )B ) A[ ( )]B.

С заменой это эквивалентно ().

Теорема 3.4. Ядро гомоморфизма АС есть конгруэнция на ней.

Доказательство. Пусть гомоморфное отображение АС с носителем A. Поскольку ядро Ker есть эквивалентность, нам достаточно показать его стабильность относительно операций данной АС.

Рассмотрим произвольную операцию f данной АС. Пусть местность f есть n.

Если n > 0, то возьмём a1, a1..., an, an A такие, что ai(Ker )ai, иначе (ai) = (ai ) для всех i = 1, n. Поскольку гомоморфизм, имеем:

(f(a1,..., an)) = f ((a1),..., (an)) = = f ((a1 ),..., (an )) = (f(a1,..., an )), т.е. f(a1,..., an) Ker f(a1,..., an ).

Если n = 0, то заметим, что ядро гомоморфизма рефлексивное отношение, стабильное по определению.

Пусть на АС A = A, Op A, Rel A задана конгруэнция. Легко видеть, что результаты операций из Op A и истинность отношений из Rel A не изменятся при замене элемента a на какой-либо другой из класса эквивалентности [a]. Это позволяет корректно определить на фактор-множестве A/ одноимённые относительно sgnt A операции и отношения. Операция f, одноимённая операции f Op A арности n, задаётся равенством def def f([a1],..., [an]) = [f(a1,..., an)] или f((A/)0) = [f(A0)] (3.4) при n > 0 и n = 0 соответственно. Отношение r, одноимённое отношению r Rel A арности m задаётся равенством def r ([a1],..., [am]) = a1,..., am ( aiai, i = 1, m ) r(a1,..., am ). (3.5) A Полученные множества операций и отношений на A/ будем обозначать OpA/ и OpA/ соответственно. Таким образом, фактор-система A/ = A/, OpA/, RelA/ будет корректно определённой АС, однотипной с A. При этом ясно, что естественное отображение nat(A, ) будет сильным гомоморфизмом из A в A/ с ядерной эквивалентностью.

Замечание. Из сказанного следует, что теорема 3.4 допускает обращение: если конгруэнция на АС A, то естественное отображение nat(A, ) есть гомоморфизм (на её фактор-систему).

Пример 53. Если A алгебра с носителем A, то A/ A, а A/ одноэлементная = A A алгебра. Таким образом, каждая алгебра имеет одноэлементную фактор-алгебру.

Для алгебр справедлива Теорема 3.5 (Биркгофа). Класс алгебр является многообразием, если и только если он замкнут относительно взятия подалгебр, прямых произведений и гомоморфных образов.

3.3.2 Теоремы о гомоморфизмах и изоморфизмах АС Нижеследующая теорема описывает ситуацию, когда в качестве конгруэнции на АС берётся ядро гомоморфизма.

Теорема 3.6 (О гомоморфизмах алгебраических систем). Пусть гомоморфизм из АС A = A, Op A, Rel A в АС B = B, Op B, Rel B. Тогда:

1) отображение, задаваемое правилом ([a]Ker ) = (a), есть биективный гомоморфизм из A/Ker в Im B;

2) если гомоморфизм сильный, то изоморфизм между A/Ker и Im.

Доказательство. По теореме об основном свойстве отображений существует вложение A/Ker B такое, что диаграмма A B nat (Ker) A/Ker коммутативна. Это отображение задаётся правилом ([a]Ker ) = (a). (3.6) Для доказательства утверждения 1) теоремы нам надо показать согласованность отображения с операциями и отношениями АС A/Ker и B.

Рассмотрим произвольную тройку одноимённых операций f Op A, f Op B и f Op A/Ker. Пусть их арность равна n. При n > 0 имеем (3.4) (3.6) (f([a1]Ker,..., [an]Ker )) = ([f(a1,..., an)]Ker ) = (3.1) (3.6) = (f(a1,..., an)) = f ((a1),..., (an)) = = f (([a1]Ker ),..., ([an]Ker )), (3.7) для любого набора элементов a1,..., an из A, а при n = (3.4) (3.6) (3.1) (f((A/Ker )0)) = ([f(A0)]Ker ) = (f(A0)) = f ((A0)) = f (([A0])Ker ).

Это означает согласованность с f и f, и, следовательно, со всем множеством операций систем A/Ker и B.

Теперь рассмотрим произвольную тройку одноимённых отношений r Rel A, r Rel B и r Rel A/Ker. Пусть их арность равна m. Для любого набора элементов a1,..., am из A имеем:

(3.5) r([a1]Ker,..., [am]Ker) (3.2) a1,..., am ai (Ker)ai, i = 1, m r(a1,..., am ) A r ((a1 ),..., (am )) (3.6) r ((a1),..., (am)) r (([a1]Ker),..., ([am]Ker)). (3.8) Это означает согласованность с r и r, и, следовательно, со всем множеством отношений систем A/Ker и B.

Итак, показано, что есть мономорфизм из A/Ker в B и, следовательно, биективный гомоморфизм в Im.

Для доказательства утверждения 2) теоремы заметим, что если гомоморфизм силь(3.2) ный, то следование в (3.8) можно обратить (см. замечание на с. 74) и, следовательно, заменить на. В результате получим, что отображение сильно согласовано с r Rel A/Ker и r Rel B и, следовательно, со всем множеством отношений систем A/Ker и Im B. Поскольку отображение биективо, то сильная согласованность означает согласованность тождественную и изоморфизм между A/Ker и Im.

Было установлено, что если гомоморфизм сильный, то Im A/Ker, или, = другими словами, образ сильного гомоморфизма АС изоморфен фактор-системе по его ядру. С учётом замечания на с. 77, полученный результат можно переформулировать и так: совокупность всех сильно гомоморфных образов АС с точностью до изоморфизма совпадает с множеством всех фактор-система по различным конгруэнциям. Ясно, что для алгебр уточнение сильного в обоих случаях можно опустить.

Пример 54. 1. Рассмотрим две однотипные алгебры A = N0, +, B = {+1, -1}, · и отображение носителя A на носитель B, задаваемое правилом (n) = (-1)n.

Имеем:

(m + n) = (-1)m+n = (-1)m · (-1)n = (m) · (n), т.е. гомоморфизм из A в B. Далее m(Ker )n m n, A/Ker = {[0], [1]}, B, ([1]) = (1) = -1, ([0]) = (0) = +1.

2. Пусть : L L сюръективный гомоморфизм решётки L в решётку L. Тогда по теореме о гомоморфизмах существует такой изоморфизм решёток L и L/Ker, что ((a)) = (a) для всех a L, где естественный гомоморфизм решётки L на её фактор-решётку L/Ker.

Пусть однородное на множестве A отношение, то его сужение на подмножество B A есть B2. В этом случае легко видеть, что если конгруэнция на A и B A, то B2 конгруэнция на B.

Следствием теорем о гомоморфизмах АС и о фактормножествах является полезная Теорема 3.7 (О факторсистемах). Пусть гомоморфизм из АС A = A, Op A, Rel A в АС B = B, Op B, Rel B и эквивалентность на A такая, что Ker. Тогда:

1) отображение, задаваемое правилом ([a]) = (a), есть эпиморфизм из A/ на Im B;

2) если гомоморфизм сильный, то и сильный гомоморфизм между A/ и Im.

Доказательство. По теореме о фактормножествах существует отображение A/ B такое, что диаграмма A B nat () A/ коммутативна. Это отображение задаётся правилом ([a]) = (a). (3.9) Для доказательства утверждения теоремы надо показать согласованность отображения с операциями и отношениями АС A/ и B. Это проводится аналогично доказательству теоремы 3.6.

Пусть f OpA, f OpB и f OpA/ тройка одноимённых операций арности n. Для любого набора элементов a1,..., an из A при n > 0 будем иметь цепочку равенств, аналогичную (3.7) с заменами Ker и (3.6) (3.9). Также и для n = 0. Это означает согласованность с f и f, и, следовательно, со всем множеством операций систем A/ и B.

Теперь рассмотрим произвольную тройку одноимённых отношений r RelA, r RelB и r RelA/ арности m. Для любого набора элементов a1,..., am из A будем иметь цепочку соотношений, аналогичную (3.8) с заменами Ker и (3.6) (3.9). Это означает согласованность с r и r, и, следовательно, со всем множеством отношений систем A/ и B.

Итак, показано, что есть гомоморфизм из A/ в B и, следовательно, эпиморфизм в Im.

Если гомоморфизм сильный, то соответствующую импликацию в последних соотношениях можно обратить. В результате получим, что отображение сильно согласованно с r Rel A/ и r Rel B и, следовательно, сильный гомоморфизм из A/Ker в Im.

Теорема 3.8 (Первая об изоморфизмах алгебраических систем). Пусть АС A с носителем A имеет подсистему B с носителем B, конгруэнция на A, = nat(A, ) и = B2 конгруэнция на B. Тогда существует взаимнооднозначный гомоморфизм фактор-системы B/ на Im, где сужение на B.

Доказательство. Рассмотрим диаграмму A/ A сужение сужение Im B nat (B, ) B/ Сужение сильного гомоморфизма = nat(A, ) на B A есть гомоморфизм B. По теореме 3.6 о гомоморфизме АС отображение, задаваемое правилом ([x]Ker ) = (x) взаимооднозначный гомоморфизм B/Ker на Im.

Замечание. При сужении области задания свойство гомоморфизма быть сильным может быть потеряно, так что гомоморфизм, вообще говоря, не сильный. Поэтому, в общем случае нельзя утверждать, что изоморфизм, и в данной 1-й теореме об изоморфизме АС речь, строго говоря, идёт лишь о биективном гомоморфизме. Однако, если A алгебра, то будет изоморфизмом, с чем связано традиционное название теоремы.

Пример 55. Рассмотрим АС A = N0, +, и её подсистему B = 2N, +,. Пусть mn m n. Ясно, что конгруэнция на A, A/ = {[1], [0]},, и = nat(A, )(n) равно [1] при нечётном n и [0] при чётном.

Далее пусть сужение на B. Тогда Im = {[0]},,, = (2N)2 = и B/ = {[0]},, Im.

= Вторая теорема об изоморфизмах АС связана с дробными эквивалентностями (см.

c. 21).

Теорема 3.9 (Вторая об изоморфизмах алгебраических систем). Пусть A АС, а и две конгруэнции на ней, причём. Тогда ( A/ ) /(/) A/.

= Доказательство. Рассмотрим диаграмму A nat nat A/ A/ nat (/) (A/)/(/) Зададим отображение правилом ([a]) = [a]. Тогда сильный гомоморфизм из A/ в A/. По теореме 3.6 отображение, задаваемое правилом ([[x]]/) = (x), есть изоморфизм между ( A/ ) /(/) и A/.

Приведём без доказательства ещё одну теорему.

Теорема 3.10 (О соответствии). Если A АС с носителем A и Con(A), то решётка L = { | Con(A), } изоморфна решётке Con(A/), при этом изоморфизм задаётся равенством () = nat(/).

Укажем только, что здесь L и Con(A/) полные решётки (см. с. 59).

3.4 Многоосновные системы Понятие АС может быть расширено. Например, если операции из Op A частичные, то говорят о частичной АС.

Другим возможным направлений расширения понятия АС является задание элементов сигнатуры не на одном, а на нескольких носителях. Так появляется понятие многоосновной (многосортной, гетерогенной, полидоменной) системы. Рассмотрим некоторые примеры многоосновных алгебр.

Действие группы на множестве. Пусть дана группа G = G,, e. Действие группы G на непустом множестве T (обозначение G : T ) обычно определяют как гомо морфизм из G в симметрическую группу Symm T преобразований T (заметим, что при заданных группе G и множестве T можно, вообще говоря, построить различные действия G на T ). Мы дадим иное, как представляется, более простое определение действия группы на множестве.

Рассмотрим структуру из пяти элементов D = G, T,,, e, у которой редукт G,, e есть группа G, а операция G T T подчиняется соотношениям e t = t, (g h) t = h (g t) для любых g, h G и t T. Легко видеть, что указанные соотношения гарантируют, что соответствующее отображение G в Symm T будет являться гомоморфизмом.

Введённая структура D представляет собой пример двухосновной алгебры с двумя бинарными операциями. Она имеет два носителя: G и T, причём групповая операция определена парах элементов из G, а операция на парах элементов (g, t), где g G, а t T. Константа e есть главный элемент D.

Конечные автоматы. Конечном детерминированным автоматом с начальным состоянием называется шестёрка объектов A = S, X, Y,,, s0, где S, X, Y конечные непустые множества, называемые соответственно множествами состояний, входных и выходных сигналов, функция переходов S X S, функция выходов S X Y и s0 S начальное состояние.

Конечные автоматы являются примером трёхосновной алгебры, имеющей три носителя ( S, X и Y ), две бинарные функции (, ) и главный элемент (s0 ).

Линейное пространство. Пусть L непустое множество и M = L, +, 0 абелева группа (модуль). Пусть K поле с носителем K, операцию сложения в котором будем обозначать тем же символом +, что и у модуля M, а символ операции умножения опускать при записи. Единицу поля K будем обозначать, как обычно, 1.

Введем новую операцию ·, действующую из K L в L и подчиняющуюся правилам:

1. 1 · x = x (унитальность), 2. (µ) · x = µ · ( · x) (ассоциативность),3. ( + µ) · x = · x + µ · x, 4. · (x + y) = · x + µ · x (дистрибутивные законы).

для любых, µ K, x, y L.

Линейное пространство L элементов L над полем K можно определить как АС L = L, +, {f(x)}K, 0. Это пример АС бесконечного типа.

В то же время ясно, что L можно мыслить как двухосновную алгебру с носителями L и K конечного типа.

Более формально, в качестве носителя в многоосновных системах выступают наборы множеств A = (Ai)iS, где Ai множества, называемых иногда доменами, а S множество сортов доменов. Будем называть такие наборы множеств комплектами. Заметим, что комплект множеств множеством не является. При фиксированном множестве S будем говорить о S-комплектах.

Для S-комплекта покомпонентно (“посортно”) определяются понятие подкомплекта.

Покомпонентно определяются декартово произведение, а также образ и прообраз при рассмотрении отображений : A B S - комплектов A и B. Также покомпонентно определяется умножение отображений. Ядром рассмотренного отображения будет являться набор = (i)iS ядер отображений i : Ai Bi.

Набор эквивалентностей = (i)iS комплекта A = (Ai)iS определяет факторdef комплект A/ = (Ai/i)iS. Ясно, что при этом для комплектов оказывается справедливым аналог теоремы 1.20 об основном свойстве отображений.

При определении многосортных алгебраических систем аналогом понятия арности операции или отношения служит их тип.

Тип многосортной операции f есть кортеж элементов множества сортов S вида t = (s1,..., sn; s0). Операция f вышеуказанного типа t на комплекте A = (Ai)iS это отображение f : As... As As.

1 n Тип нульарной операции, выделяющая элемент во множестве As, есть t = (s0).

Тип многосортного отношения r есть кортеж элементов множества сортов S вида t = (s1,..., sm). Отношение r вышеуказанного типа t на комплекте A = (Ai)iS это отображение r : As... As {1, 0}.

1 n Для данного комплекта A = (Ai)iS совокупности Op A и Rel A есть объединение t t непересекающихся совокупностей операций Op A и Rel A типов t.

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

Строго говоря, данный закон не есть закон ассоциативности, поскольку операции умножения поля и · различны.

Список литературы 1. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем.

М.: Наука, 1997.

2. Биркгоф Г. Теория решёток. М.: Наука, 1984.

3. Биркгоф Г., Барти Т. Современная прикладная алгебра. М.: Мир, 1976.

4. Гретцер Г. Общая теория решёток. М.: Мир, 1982.

5. Гуров С.И. Элементы теории упорядоченных множеств и универсальной алгебры:

Учебное пособие. М.: Издательский отдел ф-та ВМиК МГУ, 2002.

6. Кук Д., Бейз Г. Компьютерная математика. М.: Наука, 1990.

7. Кон П. Универсальная алгебра. М.: Мир, 1968.

8. Курош А.Г. Общая алгебра (лекции 1969–1970 учебного года). М.: Наука, 1974.

9. Лидл Р., Пильц Г. Прикладная абстрактная алгебра: Учебное пособие. Екатеринбург: Изд.-во Урал. ун.-та, 1996.

10. Мальцев А.И. Алгебраические системы. М.: Наука, 1970.

11. Плоткин Б.И. Универсальная алгебра, алгебраическая логика и базы данных. М.:

Наука, 1991.

12. Салий В.Н. Решётки с единственными дополнениями. М.: Наука, 1984.

13. Скорняков Л.А. Элементы теории структур. М.: Наука, 1970.

14. Скорняков Л.А. Элементы общей алгебры. М.: Наука, 1983.

15. Стенли Р. Перечислительная комбинаторика. М.: Мир, 1990.

16. Яглом И.М. Булева структура и её модели. М.: Сов. радио, 1980.

Pages:     | 1 |   ...   | 9 | 10 ||






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.