WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 8 | 9 || 11 |

Ясно, что мы получили тотальную булеву структуру множеств.

См. Пинус А.Г. Основы универсальной алгебры: Учебное пособие. Новосибирск: Изд-во НГТУ, 1998.

A4: Носитель АС A4 есть множество V всех векторов x трёхмерного пространства, а сигнатурные символы интерпретируются так:

f1 +, f2 (векторное умножение), f3(a) = -a, r(a, b) вектор a коллинеарен вектору b, c1, c2 0.

Операции и отношения во всех приведённых примерах, соответствующие сигнатурным символам f1, f2, f3 и r1 будут одноимёнными. Везде мы предполагали, что введенные операции и отношения имеют обычный математический смысл. Заметим, что в этих АС неявно присутствует предикат эквивалентности =, интерпретируемый как равенство.

Приведём примеры конкретных алгебраических систем различной сигнатуры.

Пример 44. 1. AC A, f, где f одноместная операция на множестве A называется унаром.

2. Поле действительных чисел R, +, ·, 0, 1 есть алгебра типа 2, 1, 0, 0. Кортеж -1 - +, ·, -,, 0, 1 нельзя рассматривать, как сигнатуру поля, т.к. операция не определена для нуля.

Кольцо K с единицей есть алгебра сигнатуры K = ·, +, -, 0, 1 типа 2, 2, 1, 0, 0.

-Группа есть алгебра типа 2, 1, 0 с носителем G и сигнатурой G =,, e.

3. Частично предупорядоченное множество P, есть модель типа 2.

4. Если одна АС может быть получена из другой удалением некоторых операций, отношений или констант, то первая АС называется редуктом второй.

Упорядоченная группа A есть АС с носителем A типа 2, 1, 2, 0 и сигнатурой -1 -, ;, e, где редукт G = A,,, e есть группа, а редукт P = A, ч.у. множество. При этом считается, что x y a x b a y b для любых x, y, a, b A.

Если при этом P цепь, то A есть линейно упорядоченная группа. Примером линейно упорядоченной группы будет структура R, +, -,, 0.

Во всех приведённых выше примерах считалось, что приведённые операции и отношения обладают известными свойствами. В общем случае эти свойства необходимо задавать.

Совокупность АС фиксированной сигнатуры называется классом алгебраических систем. Класс M АС сигнатуры называется многообразием, если существует множество тождеств сигнатуры такое, что АС сигнатуры принадлежит классу M если и только если в ней выполняются все тождества.

Например, полугруппы это многообразия сигнатуры состоящей из единственной бинарной операции · (в инфексной записи, обычно опускается), удовлетворяющие тождеству (xy)z = x(yz). Ассоциативно-коммутативные кольца с единицей это многообразия сигнатуры +, ·, -, 0, 1 типа 2, 2, 1, 0, 0 удовлетворяющие следующим тождествам :

(x + y) + z = x + (y + z) x + 0 = 0 + x = x x + (-x) = 0 x + y = y + x (x + y)z = xz + yz x(y + z) = xy + xz (xy)z = x(yz) x1 = 1x = x xy = yx.

Отметим, что алгебре можно сопоставить соответствующую адекватную модель, есn+ли каждую операцию вида fin(x,..., xn) заменить на отношение ri (x,..., xn, xn+1) n+такое, что r (x,..., xn, y) fin(x,..., xn) = y. Такая модель называется представi ляющей.

Пример 45. Пусть задана группа Z, +, -, 0. Если def def def 3 2 r1(m, n, k) = m + n = k, r2(m, n) = m = -n, r3(n) = n = 0, 3 2 то Z, r1, r2, r3 будет представляющей моделью для данной алгебры.

3.1.2 Подсистемы и прямое произведение алгебраических систем Напомним, что множество X называется устойчивым относительно отображения f : Xn X, если f(x1,..., xn) X для любого кортежа (x1,..., xn) из области определения f. Пусть A = A, Op A, Rel A алгебраическая система и B непустое подмножество A. Назовём B устойчивым относительно операций из Op A, если оно устойчиво относительно сужений на B каждой операции из Op A.

Определение 3.1. Пусть A = A, Op A, Rel A АС и = B A. АС B = B, Op B, Rel B, где Op B и Rel B сужения Op A и Rel A на B, называется подсистемой A, если множество B устойчиво относительно операций из Op A.

Подсистему алгебры называют подалгеброй, а подсистему модели подмоделью. Если B A, то соответствующую подсистему называют собственной. Тот факт, что АС B есть подсистема (собственная подсистема) АС A записывают B A (B < A).

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

Пример 46. 1. Поле рациональных чисел Q, +, ·, 0, 1 есть подалгебра поля действительных чисел (см. пример 44).

2. Если множество A собственное подмножество множества B, то алгебра множеств P(A) не является подалгеброй P(B), поскольку такое сужение не сохраняет единицу P(A).

3. Пусть F множество дифференцируемых действительных функций. Тогда унар d d F,, где операция дифференцирования, есть алгебра. Множество полиноdx dx мов будет её подалгеброй.

4. При любом натуральном n унар Z, + содержит подалгебру nZ, +.

Совокупность всех подсистем АС A будем обозначать Sub (A). Ясно, что это ч.у.

множество, упорядоченное по включению.

Утверждение 3.1. Пусть A АС и {Ai}iI некоторая совокупность её подсистем.

Тогда Ai либо пусто, либо является подсистемой.

iI Доказательство. Достаточно заметить, что пересечение носителей всех подсистем, если оно не пусто, устойчиво относительно всех операций всех подсистем.

Следствие. Если АС A имеет главные элементы, то пересечение всех её подсистем непусто.

Справедливость данного следствия вытекает из условия принадлежности главных элементов АС A любой её подсистеме.

Наименьшая подсистема АС называют её главной подсистемой. Главная подсистема, однако, существует не для любой АС: например, алгебра (кольцо целых чисел) Z, +, ·, 0 или модель Z, наименьших подсистем, очевидно, не имеют. Если же исходная АС содержит главные элементы, то они обязательно будут присутствовать во всех её подсистемах, в т.ч. и в главной.

Пусть дана АС A = A, Op A, Rel A и B A. Обозначим через B = B пересечение всех подсистем из Sub (A), содержащих B. B называют подсистемой, порождённой множеством B, а элементы B порождающими элементами. Поэтому B мы также будем записывать B = [B], Op A, Rel A. Если B конечное множество, то B есть конечнопорождённая система.

Пример 47. 1. Подкольцо чётных в кольце целых чисел порождается элементом 2.

1 2. Пусть A = { a0, a1,..., an-1 }, f1 унар, где f1 (ai) = ai+1(mod n). Тогда A порождается любым элементом своего носителя.

3. N, + = [1], +.

4. АС N, · не есть конечнопорождённая алгебра.

Итак, непустое пересечение подсистем АС всегда является её подсистемой. Чтобы снять условие непустоты пересечения подсистем, обычно в качестве подсистемы допускают и систему с пустым носителем. Объединение же подсистем АС, вообще говоря, подсистемой не является, что показывает нижеследующий Пример 48. nZ, + и mZ, + при любых целых n и m суть подсистемы Z, +, однако множество nZ mZ при некратных друг другу n и m неустойчиво по отношению к сложению, и в этом случае nZ mZ, + даже не есть АС. Например, при n = 6 и m = 10 множество { 0, ±6, ±10, ±12, ±20,... } не содержит элемента 16=6+10.

Ниже будет сформулировано условие, когда объединение подсистем будет являться подсистемой.

Определение 3.2. Совокупность S подмножеств A называется локальной, если любое конечное подмножество A содержится в некотором элементе S.

Примером локальной подсистемы множества R является совокупность интервалов вида (-n, n), n N.

Теорема 3.1. Пусть A = A, Op A, Rel A алгебраическая система и S = { Ai A | i I } локальная совокупность подмножеств её носителя A. Тогда Ai, Op A, Rel A A.

iI Доказательство. Нам достаточно показать лишь устойчивость множества S относительно операций из Op A, поскольку все остальные свойства полученной системы будут наследоваться от исходной.

Обозначим U = Ai и рассмотрим произвольную n-местную операцию операцию iI f из Op A. Для произвольного набора (a1,..., an) = a имеем: с одной стороны, a U, а с другой найдется такое множество Ai U, что a f(a) Ai. Это означает, что U устойчиво относительно f.

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

Выше мы отмечали, что совокупность Sub (A) всех подсистем АС A есть ч.у. множество. Для того, чтобы Sub (A) оказалось решёткой, необходимо показать существование наименьшей подсистемы, содержащей объединение двух произвольных подсистем A. Оказывается, это можно сделать и, таким образом, Sub (A) есть решётка. Более того, она оказывается полной решёткой (см. с. 59).

Пример 49. Продолжая рассмотрение примера 48 отметим, что наименьшей подсистемой АС Z, +, содержащей её подсистемы nZ, + и mZ, + будет [m n], +.

Например, для 6Z, + и 10Z, + это 2Z, +.

Если A и B две однотипные АС абстрактной сигнатуры с носителями A1 и Aсоответственно, то можно определить прямое произведение C = A B этих АС. Сигнатура АС C будет состоять из такого же числа тех же символов операций и отношений, но местности соответствующих символов удваиваются.

Пусть f1 и f2 одноимённые операции, а r1 и r1 одноимённые отношения из A и B соответственно. Соответствующие им операция f и отношение r в АС C = A B определяются как f(a, b) = ( f1(a), f2(b) ) и r(a, b) = ( r1(a), r2(b) ) (здесь a A и b B произвольные наборы элементов соответствующей арности.

3.2 Гомоморфизмы алгебраических систем 3.2.1 Согласованность отображений АС с операциями и отношениями Определение 3.3. Пусть A, Op A, Rel A и A, Op A, Rel A две однотипные АС, отображение из A в A, а f Op A и f Op A пара одноимённых операций арности n. Тогда говорят, что отображение согласовано с данными операциями, если (f(a1,..., an)) = f ((a1),..., (an)) и (f(A0)) = f ((A0)) (3.1) для n > 0 или n = 0 соответственно.

Пример 50. Для алгебр R {0}, · и R, + отображение a(x) = loga |x| при любом действительном a > 0, a = 1 согласовано с операциями · и + данных АС.

Определение 3.4. Пусть A, Op A, Rel A и A, Op A, Rel A две однотипные АС, отображение из A в A, а r Rel A и r Rel A пара одноимённых отношений арности m. Тогда говорят, что отображение соответственно 1) согласовано с данными отношениями, если r(a1,..., am) r ((a1),..., (am)), (3.2) 2) сильно согласовано с данными отношениями, если r ((a1),..., (am)) b1,..., bm (ak) = (bk), k = 1, m r(b1,..., bm), (3.3) A 3) полностью (или тождественно) согласовано с данными отношениями, если r(a1,..., am) r ((a1),..., (am)).

Если отображение окажется согласованным со всеми парами одноимённых операций [отношений] двух АС, то будем говорить, что согласовано с операциями [отношениями] этих АС.

Пример 51. Рассмотрим две модели типа 1 : {a1, a2}, r и {b}, r. Единственное возможное отображение из A на B задаётся равенствами (a1) = (a2) = b. Пусть r (b) = 1. Тогда:

1) если r(a1) = r(a2) = 0, то согласовано, 2) если r(a1) = 1 и r(a2) = 0, то сильно согласованно, 3) если r(a1) = r(a2) = 1, то тождественно согласованно с парой r, r одноимённых отношений рассматриваемых моделей.

3.2.2 Типы гомоморфизмов АС Определение 3.5. Пусть A = A, Op A, Rel A и B = B, Op B, Rel B две однотипные АС. Отображение : A B, согласованное с операциями этих АС называется соответственно 1) гомоморфизмом из A в B, если согласованно, 2) взаимнооднозначным (или биективным) гомоморфизмом между A и B, если биекция, согласованная, 3) сильным гомоморфизмом из A в B, если сильно согласованно, 4) изоморфизмом между A и B, если биекция, полностью согласованная с отношениями этих АС.

Вместо термина сильный для гомоморфизма иногда употребляют термин строгий.

Для алгебр понятия гомоморфизма и сильного гомоморфизма, очевидно, совпадают, а биективный (взаимнооднозначный) гомоморфизм есть изоморфизм.

Пример 52. Модель A = Z, < не изоморфна, а лишь биективно гомоморфна модели B = 2Z, : отображение (n) = 2 n есть взаимнооднозначный (не сильный) гомоморфизм из A в B, но “просто”, но не тождественно согласовано с отношениями < и.

Замечание. Отметим важное свойство сильных гомоморфизмов, которое нам понадобится в дальнейшем. Соотношение (3.3) позволяет утверждать, что если (в введённых обозначениях) справедливо r ((a1),..., (an)), то в A найдутся такие b1,..., bm из ядра отображения, что справедливо r(b1,..., bm), и, таким образом, r ((a1),..., (an)) r(b1,..., bm). Можно сказать, что мы сохранили истинность переходя от отношения r к одноименному отношению r “при движении против отображения ”.

АС A и B называют изоморфными, если существует изоморфизм между A и B, что записывают как A B. То, что гомоморфизм из A в B записывают как = Hom(A, B). Если Hom(A, B), то, как нетрудно проверить, Im B.

Понятно, что тождественное отображение любой АС на себя есть изоморфизм, если : A B изоморфизм, то и -1 : B A также изоморфизм и композиция гомоморфизмов (изоморфизмом) есть гомоморфизм (изоморфизм). Легко видеть, что отношение изоморфизма есть отношение эквивалентности на множестве алгебраических систем и, следовательно, все алгебраические системы распадаются на классы эквивалентности, содержащие изоморфные системы. Обычно изучают свойства алгебраической системы с точностью до изоморфизма. Такие свойства называют абстрактными.

Сюръективный гомоморфизм АС называют эпиморфизмом (или наложением), а инъективный гомоморфизм мономорфизмом (или вложением), т.е. также, как и соответствующе отображения. Гомоморфизм АС в себя называется эндоморфизмом. Изоморфизм АС на себя называют автоморфизмом. С каждой АС A связаны моноид эндоморфизмов End (A) и группа автоморфизмов Aut (A) (группа обратимых элементов моноида End (A)).

Класс алгебраических систем называется абстрактным, если если с каждой АС в нём лежат все системы, ей изоморфные.

Теорема 3.2. Всякий сюръективный эндоморфизм конечной системы есть изоморфизм.

Доказательство. Рассмотрим АС A = A, Op A, Rel A с конечным носителем A и наложение : A A. Нам надо показать, что тождественно согласовано с отношениями A и (A).

Пусть r произвольное отношение арности m из Rel A. Поскольку гомоморфизм, то для любого набора a1,..., am из m элементов носителя A истина импликация r(a1,..., am) r((a1),..., (am)), т.е. для её посылки и заключения могут иметь место только следующие пары истинностных значений посылки и заключения:

(0, 0), (0, 1), (1, 1). Теорема будет доказана, если выяснится, что второй случай в наших условиях не реализуется.

Наложение множества на себя является биекцией и, в силу конечности A, перестановкой его элементов конечной степени. Тогда существует натуральное d такое, что d есть тождественная перестановка. Пусть отношение r((a1),..., (am)) выполнено. Отсюда следует, что, поскольку гомоморфизм, для любого натурального t выполнено r(t(a1),..., t(am)). При t = d получаем, что выполнено и r(a1,..., am). Таким образом, r((a1),..., (am)) r(a1,..., am), и случай (0, 1) невозможен.

3.3 Конгруэнции и гомоморфные системы 3.3.1 Конгруэнции и фактор-системы Определение 3.6. Однородное отношение на множестве A называется стабильным относительно операции f местности n на A, если при n > 0 для любых элементов a1, a1,..., an, an A справедливо n aiai f(a1,..., an)f(a1,..., an ), i=а при n = 0 рефлексивно.

Аналогично может быть определено стабильное отношение произвольной арности.

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

Однородное отношение на АС A, Op A, Rel A называется стабильным на этой АС, если оно стабильно относительно любой операции из Op A. Например, полное и диагональное отношения стабильны на любой АС.

Определение 3.7. Стабильная на АС эквивалентность называется конгруэнцией на ней.

Ясно, что полное и диагональное отношения являются конгруэнциями на любой АС.

С каждой АС A связана решётка конгруэнций Con(A), которая оказывается полной подрешёткой в решётке её подсистем Sub (A). Решётка Con(A) имеет универсальные грани: это отмеченные выше диагональ и аморфная конгруэнция. Пересечение конгруэнций и совпадает с их теоретико-множественным пересечением, а объединеe ние с эквивалентным замыканием ( ) их теоретико-множественного объединения e (если и перестановочны, то как мы помним, ( ) = = ).

Теорема 3.3. Если на алгебре A все конгруэнции перестановочны, то решётка Con(A) модулярна.

Доказательство. Пусть,, Con(A) и. Для того, чтобы в решётке конгруэнций выполняется модулярный закон, достаточно показать, что выполняется включение ( ) ( ), () обратное к неравенству полумодулярности.

Заменив объединение конгруэнций на их произведение, для произвольных подалгебр A и B алгебры A имеем A( ( ))B AB X ( AX XB ) X ( AB AX XB ).

Pages:     | 1 |   ...   | 8 | 9 || 11 |






















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

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