71488

ОСНОВЫ УНИВЕРСАЛЬНОЙ АЛГЕБРЫ

Книга

Математика и математический анализ

Возникшая на стыке математической логики и классической алгебры универсальная алгебра в свою очередь оказала влияние как на эти разделы математики так и на более далекие области этой науки.

Русский

2014-11-07

3.93 MB

13 чел.

Министерство  образования и науки Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

51

П326

А.Г. ПИНУС

ОСНОВЫ УНИВЕРСАЛЬНОЙ

АЛГЕБРЫ

Утверждено

Редакционно-издательским советом университета

в качестве учебного пособия

для студентов факультета прикладной математики

издание третье исправленное и дополненное

НОВОСИБИРСК

2005

512(075.8)

   

    Рецензенты: В.А.Селезнев, д-р физ.-мат наук

                           В.М.Копытов, д-р физ.-мат. наук

Работа подготовлена на кафедре алгебры и математической логики

 Пинус А.Г. 

Основы универсальной алгебры: Учеб. пособие. –

Новосибирск: Изд-во НГТУ, 2005. – 137 с.

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

 Новосибирский государственный

технический университет, 2005 г

Моим сыновьям Константину

и Филиппу посвящается.

Введение

Универсальная алгебра сравнительно молодая наука, изучающая поведение функций на произвольных множествах. Её основы были заложены работами Г.Биркгофа 30-х годов. Впоследствии значительный вклад в неё внесли работы А. Тарского, А.И. Мальцева, Б. Йонсона, Р. МакКензи и многих других. Возникшая на стыке математической логики и классической алгебры, универсальная алгебра, в свою очередь, оказала влияние, как на эти разделы математики, так и на более далекие области этой науки. Развитие универсальной алгебры связано не только с решением внутренних математических проблем, но и с большим числом приложений её методов и результатов в различных областях знаний от социологии до информатики. В частности, непосредственное применение универсальная алгебра нашла в программировании, в теории баз данных и ряде других областей, получивших развитие в нынешнюю эпоху широкого применения вычислительных машин. Тем не менее, круг людей, знакомых с универсальной алгеброй и владеющих её методами, довольно узок. Сам курс универсальной алгебры читается в виде спецкурсов в довольно ограниченном числе университетов. В связи с этим, смелым и новаторским шагом было решение руководства факультета прикладной математики и информатики Новосибирского государственного технического университета и, в частности, его бывшего декана проф. В.И.Хабарова о введении этого курса в обязательную программу обучения прикладных математиков НГТУ. Чтение этого курса было предложено мне и я благодарен за это руководству факультета.

Одной из проблем, с которой я столкнулся при подготовке и чтении этого курса, отсутствие подходящей учебной литературы на русском языке. Классический учебник А.И.Мальцева "Алгебраические системы" является в настоящее время библиографической редкостью, да и материал этой книги, написанный в 60-е годы, далеко не полностью отражает современные достижения универсальной алгебры. То же можно сказать и о имеющейся на русском языке книге П.Кона "Универсальная алгебра". Учебники А.Г.Куроша "Лекции по общей алгебре" и Л.А.Скорнякова "Общая алгебра" вопросов универсальной алгебры касаются лишь косвенно. Книга Д.М.Смирнова "Многообразия алгебр" носит скорее монографический, а не учебный характер, да и изданная малым тиражом, малодоступна студентам. На английском языке можно указать на книгу Г.Гретцера "Универсальная алгебра" и С.Барриса,

Х.П.Санкапанавара "Курс универсальной алгебры", но они велики по объёму материала и недоступны для российского студенчества. Прекрасным учебником по универсальной алгебре является книга Т.Ирингера “Общая алгебра" соответствующая по объёму университетскому курсу, но, написанная на немецком языке и практически отсутствующая в России, она также является вещью в себе для студентов НГТУ.

Эти обстоятельства и подтолкнули меня на написание учебника под тот курс универсальной алгебры, который в течение нескольких лет читается мной студентам НГТУ, специализирующимся по прикладной математике. Результат перед Вами. Безусловно, на содержании курса сказались и личные пристрастия автора в широкой области универсальной алгебры, в том числе в виде включения в содержание книги главы 3, в которой представлены результаты его исследований. Автор искренне надеется, что этот учебник послужит более широкому знакомству молодых математиков с методами и результатами близкой ему науки.

А.Пинус.

Мэдисон. Висконсин.

Февраль, 1998г.

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

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

А. Пинус.

Новосибирск, Россия.

Июнь, 2004 г.

 

Глава 1. Основные понятия универсальной алгебры.

§1. Универсальные алгебры, модели и алгебраические системы.      Эквивалентность на множестве.

Как уже сказано выше, основным предметом изучения универсальной алгебры являются множества с наборами функций, определенных на этих множествах. Однако, на протяжении всего курса важную роль будут играть не только функции на множествах, но и различные отношения, определенные на этих множествах. Мы будем предполагать известным читателю, в пределах "наивного курса" понятия множества, его элемента, подмножества, декартова и прямого произведения множеств, отображения одного множества в другое, n-местной функции и n-местного отношения на множестве, мощности множества.

На протяжении всего курса мы будем отождествлять n-местное отношение определенное на множестве А с соответствующим подмножеством n-ой декартовой степени множества А. Более точно, n-местное отношение R(x1,...,xn) на множестве А сопоставляет каждому набору элементов a1,...,an множества А элементы двухэлементного множества {И;Л}: истину, либо ложь. Если R(a1,...,an)=И, то будем говорить, что отношение R истинно на элементах a1,...,an, если R(a1,...,an)=Л, то, соответственно,  R ложно на a1,...,an. В первом случае будем часто ограничиваться записью R(a1,...,an), во втором  R(a1,...,an). Каждому n-местному отношению R на множестве А мы можем сопоставить некоторое подмножество n-ой степени An множества А (как правило обозначаемое той же буквой R) и определяемое следующим образом:

a1,...,anRR(a1,...,an)=И  R(a1,...,an).

Очевидно, что это сопоставление является взаимно однозначным отображением совокупности всех n-местных отношений на множестве А на совокупность всех подмножеств n-ой декартовой степени An множества А. Как сказано выше, в дальнейшем мы, пользуясь этим сопоставлением, будем отождествлять n-местные отношения на А и подмножества множества An.

Аналогичным образом мы будем отождествлять понятие n-местной функции f на множестве А f : An A с некоторым подмножеством gr f (n+1)-ой степени множеств A – графиком этой функции: для любых a1,...,an,b из A

f(a1,...,an)=b  a1,...,an,b  gr f An+1. 

Ввиду этих двух замечаний возможно сопоставление каждой n-местной функции f : AnA на множестве А некоторого (n+1)-местного отношения Rf такого, что для любых элементов a1,...,an,b из А

f(a1,...,an)=b  Rf (a1,...,an,b) (т.е. Rf(a1,...,an,b)=И).

Очевидно, что для различных n-местных функций f и g на множестве А отношения Rf и Rg также будут различны. Однако, далеко не любое (n+1)-местное отношение на множестве А будет иметь вид отношения Rf для некоторой функции f : AnA. Необходимым и достаточным условием для этого является функциональность отношения.

(n+1)-местное отношение R на множестве А назовем функциональным, если имеет место условие

a1,...,anA   bA R(a1,...,an,b).

В дальнейшем мы довольно часто будем пользоваться стандартными сокращениями в математических текстах вида (для всех...), (существует...) и ! (существует единственный...). Таким образом, приведенное выше условие функциональности отношения R читается так: для любых элементов а1,…,аn множества A существует и единственный элемент bA такой, что R(a1,…,an,b). Нетрудно заметить, что если R (n+1)-местное функциональное отношение на A, то существует n-местная функция f на множестве A такая, что R=Rf. Таким образом, сопоставление n-местной функции f на A (n+1)-местного функционального отношения Rf является взаимно однозначным отображением совокупности всех n-местных функций на множестве A на совокупность всех (n+1)-местных функциональных отношений на A.

Одно- и двухместные функции и отношения, определенные на конечных (и небольших) множествах A, удобно задавать с помощью их так называемых таблиц Кэли. Проиллюстрируем это на примерах, избегая многословного и нудного описания. Пусть A={1,2,3} и функции f и g являются соответственно одно- и двухместной функциями на множестве A со следующими таблицами Кэли:

для f:

x

f(x)

, для g:

x \ y 

1

2

3

1

2

1

1

1

2

2

3

2

1

2

1

 

3

2

3

1

3

3

Это будет означать, что имеют место следующие равенства:

f(1)=2, f(2)=3, f(3)=2 и

g(1,1)=1, g(2,1)=1, g(3,1)=1, g(1,2)=1, g(2,2)=2,

g(3,2)=3, g(1,3)=2, g(2,3)=1, g(3,3)=3.

Если R и Q соответственно одно- и двухместное отношения на A с таблицами Кэли

для R

x

R(x)

, для Q

x \ y

1

2

3

1

И

1

И

Л

И

2

Л

2

И

И

И

3

И

3

Л

И

Л

то это, в свою очередь, означает, что имеют место R(1),R(3) и Q(1,1), Q(2,1), Q(2,2), Q(3,2), Q(1,3), Q(2,3), а для остальных ситуаций отношения R и Q ложны.

Перейдем теперь к определению понятий универсальная алгебра, модель, алгебраическая система. Важную роль при этом будет играть понятие сигнатуры списка обозначений для основных рассматриваемых (на фиксированном множестве) функций, отношений, констант. В дальнейшем мы будем, для простоты, рассматривать, как правило, лишь конечные сигнатуры, хотя это ограничение часто не является принципиальным. Под сигнатурой  мы понимаем конечный кортеж (последовательность) элементов трех типов fi(ir), pj (jm), cl (lk), где r, m, k некоторые натуральные числа, при этом каждому из элементов fi, pj будут сопоставлены некоторые положительные натуральные числа, si и qj соответственно, называемые их местностью или арностью. Итак,

 = .

Элементы fi будем называть функциональными символами сигнатуры , элементы pi  предикатными символами (или символами отношений), а   cl  константными символами сигнатуры . Фиксация сигнатуры означает, что в дальнейшем мы будем иметь дело с si-местными фиксированными функциями на некотором множестве A, обозначаемыми как fi (ir), с            qi-местными отношениями (предикатами) на том же множестве A, обозначаемыми как pj (jm) и с константами (некоторыми фиксированными элементами) из A, обозначаемыми как cl (lk). Сигнатуру будем называть функциональной, если предикатные символы  в ней отсутствуют и предикатной  если в отсутствуют символы .Под алгебраической системой A=A; сигнатуры мы будем понимать некоторое фиксированное множество A (базовое или основное множество алгебраической системы A) с фиксированным на нем набором si-местных функций fi (ir), qj-местных отношений pj (jm) и константами c0,…,ck (элементами множества A). Алгебраическую систему A=A; будем называть универсальной алгеброй, если ее сигнатура функциональна или моделью, если ее сигнатура предикатна. Заметим так же, что константы cl в сигнатуре могут отсутствовать. Функции  будем называть базовыми или основными или сигнатурными функциями (операциями) алгебраической системы A, отношения Pj  - базовыми или основными или сигнатурными отношениями (предикатами) алгебраической системы A.

Приведем ряд примеров, иллюстрирующих введенные понятия.

Пусть  = . Первый пример алгебраической системы N=N, этой сигнатуры  имеет основным множеством совокупность N={0,1,2,...,n,n+1,...} всех натуральных чисел и сигнатурные символы интерпретируются в системе N следующим образом:

для любых n,mN

f0(n,m)=n+m, f1(n,m)=nm, f2(n)=n+1,

P0(n,m)= И  n  m, c0 = 0, c1 = 1.

Мы можем на том же основном множестве N строить абсолютно иные алгебраические системы, иным образом интерпретируя сигнатурные символы. К примеру, пусть M = N; и для любых n, m  N

f0(n,m) = 0, f1(n,m) = nm, f2(n) = 2n,

P0(n,m) = И  n и m взаимно просты, с0=0, с1=0.

Другие примеры алгебраических систем этой сигнатуры получим, рассматривая, к примеру, для любого множества А алгебраическую систему A=P(A),. Здесь и далее P(A) будет обозначать совокупность всех подмножеств множества A. В качестве интерпретации сигнатурных символов в системе A выберем следующие: для любых B,C A

f0(B,C)=B C, f1(B,C)=BC, f2(B)=B.

(т.е. дополнение подмножества В в множестве А),

P0(B,C) = И  BC, c0=, c1=A.

Наконец, в качестве последнего, рассмотрим следующий пример алгебраической системы сигнатуры  : B=B,, где В  совокупность всех геометрических векторов трехмерного пространства. При этом, для любых  B

И , c0=c1=.

Еще раз подчеркнем, что единственным ограничением при построении алгебраической системы сигнатуры на любом основном множестве А является то, что функциональные символы сигнатуры должны интерпретироваться на А функциями соответствующей арности, предикатные символы - отношениями соответствующей арности на А, а константные символы - фиксированными элементами из А.

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

  1.  Частично упорядоченное множество  это любая модель A=A; сигнатуры  =, удовлетворяющая следующим условиям для любых элементов a, b, c из А:
  2.  P(a, a) - рефлексивность P,
  3.  из P(a, b) и P(b, a) следует, что a=b - антисимметричность P,
  4.  из P(a, b) и P(b, c) следует P(a, c) - транзитивность P.

Поскольку отношение P на частично упорядоченном множестве призвано интуитивно отображать сравнение элементов по принципу "больше - меньше", то в дальнейшем предикат P(x, y) будем обозначать как отношение xy.

Примеры частично упорядоченных множеств:

I. N=N, здесь отношение xy является стандартным отношением порядка: x не превышает y;

II. R=R;, здесь R - совокупность всех действительных чисел и xy - стандартное отношение порядка на R;

  1.  A=P(A);, здесь ВС (для В,СА) имеет место и тогда, когда ВС;

IV. C=N|;,здесь N|=N\{0} и nm тогда и только тогда, когда n нацело делит m.

Далее через а<b будем обозначать ситуацию когда аb и аb.

Нам будет удобно, в дальнейшем, конечные (небольшие) частично упорядоченные множества C; задавать с помощью диаграмм Хассе, в которых элементы множества С изображаются точками плоскости и отрезок, соединяющий точку а с точкой b, идущий сверху вниз, соответствует отношению покрываемости элемента b элементом а, т.е. ситуации: b<а и для любого сС из bса вытекает, что с=b или с=а.

В этом случае для с,dC отношение сd соответствует наличию ломанной идущей из точки d в точку с сверху вниз.

К примеру диаграмма Хассе:

                                       d                           e

                                     

                                       b                           c

                                                        a

описывает частично упорядоченное множество {a,b,c,d,e}; со следующей таблицей Кэли:

x\ y

a

b

c

d

e

a

И

И

И

И

И

b

Л

И

Л

И

И

c

Л

Л

И

И

И

d

Л

Л

Л

И

Л

e

Л

Л

Л

Л

И

2. Линейно упорядоченные множества или цепи это частично упорядоченные множества A=A:P удовлетворяющие дополнительному условию:

      4) для любых a,bP либо P(a, b), либо P(b, a).

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

Чтобы доказать, что данное частично упорядоченное множество C=C; не является цепью необходимо и достаточно указать в С пару несравнимых элементов, т.е. таких а,bС, что ни аb, ни bа не имеют места. Впредь свойство несравнимости элементов а,b частично упорядоченного множества C=C; будем обозначать как а||b, а ложность отношения ab – как . Таким образом, а||b – означает, что  и .

3. Решеточно упорядоченные множества это частично упорядоченные множества A=A;, удовлетворяющие условию: для любых элементов а,bА в A существуют их наименьшая верхняя (обозначаемая как supA(a,b) или просто sup(a,b) и наибольшая нижняя (infA(a,b) или inf(a,b)) грани. Напомним, что элемент сА называется верхней гранью элементов а и b, если имеют место отношения ас и bс. Элемент с называется наименьшей верхней гранью или супремумом элементов а и b,если с верхняя грань элементов а и b и для любой верхней грани d элементов а и b имеет место неравенство сd. Аналогично определяются понятия нижней грани и наибольшей нижней грани или инфинума пары элементов из A. Частично упорядоченное множество с приведенной на предыдущей странице диаграммой Хассе не является решеточно упорядоченным: элементы d и e вообще не имеют верхней грани, нижними гранями для них будут элементы a, b, c, но среди этих нижних граней нет наибольшей.

Очевидным образом любая цепь является решеточно упорядоченным множеством. Пример ||| частично упорядоченных множеств так же является решеточно упорядоченным множеством (причем, не являющимся цепью в случае когда А содержит более одного элемента). При этом для любых В,СP(А) sup(B,C)=BC и inf(B,C)=BC.

4. Решеткой будем называть универсальную алгебру A=A; сигнатуры =, удовлетворяющую условиям 1)–4). В написании этих условий будем использовать традиционные знаки , вместо f0, f1, т.е. далее вместо f0(a,b) будем писать ab,а вместо f1(a,b) - ab. Итак, в решетке для любых а,b,сА должны выполнятся условия:

    1. aa=a, aa=a - идемпотентность операций и ;

    2. ab=ba, ab=ba - коммутативность операций и ;

    3. a(bc)=(ab)c, a(bc)=(ab)c - ассоциативность операций и ;

    4. a(ab)=a, a(ab)=a - поглощаемость операций и .

Для любого множества А алгебра A=P(A);, где =, и для произвольных B,CP(A) BC=BC, BC=BC является решеткой.

() Если A=A; решёточно-упорядоченное множество, то определим двухэлементные операции и на А следующим образом: для любых а, b из А пусть ab=sup(a,b) и ab=inf(a,b). Универсальная алгебра Al=A;, является решёткой. Обратно, если B=B;, произвольная решётка, то на В определим двухместное отношение : abab=a  (что эквивалентно равенству ab=b). Частично-упорядоченное множество Bord=B; является решёточно-упорядоченным, причём для любых a, b из B . Кроме того для любой решётки C и любого решеточно упорядоченного множества A имеет место равенства (Cord)l=C и  (Al)ord=A.

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

5. Модулярной решёткой будем называть решётку A=A;,, удовлетворяющую условию: для любых а, b, с из А

(ab)(bc)=b((ab)c).

Проверьте, что решётка P(A);, является модулярной для любого множества А.

6. Дистрибутивная решётка это любая решётка A=A;,, удовлетворяющая условию: для любых элементов а, b и с из А

a(bc)=(ab)(ac).   

     Проверьте, что решётка P(A);, является дистрибутивной для любого множества А.

Любая дистрибутивная решётка A=A;, является модулярной.

    Действительно, пусть а, b, с из А, тогда b((ab)c)= (в силу дистрибутивности A) (b(ab))(bc). В силу коммутативности, ассоциативности и идемпотентности операции имеет место цепочка равенств:

b(ab)=b(ba)=(bb)a=ba=ab.

Тем самым, b((ab)c = (a b)(bc) и модулярность дистрибутивной решётки A доказана.

  7. Булевой алгеброй называется универсальная алгебра A=A; сигнатуры  =,,,0,1 (одноместная операция  обозначается далее как : f3(a)=a и 0, 1 – константные символы сигнатуры ), удовлетворяющая условиям:

  1.  A;,  дистрибутивная решётка и

для любого а из А:

  1.  0a=a, a1=a,
  2.  a(a)=1, aa=0.

Для любого множества А универсальная алгебра P(A);,,,0,1 является булевой алгеброй. Здесь под В, для В из Р(А), понимаем теоретико-множественное дополнение множества В в множестве А и 0 отождествляем с множеством , а 1 – c множеством А.

8. Полугруппой называется универсальная алгебра A=A; сигнатуры  = если она удовлетворяет условию ассоциативности операции f0. Далее, традиционным образом операцию f0  для полугруппы будем обозначать как умножение (f0(a,b)=ab). Таким образом, универсальная алгебра A=A;  является полугруппой, если для любых элементов а, b, с из А имеет место равенство a(bc)=(ab) c.

Через AA обозначим совокупность произвольных отображений множества А в себя. На AA определим операцию как обычную суперпозицию отображений. Таким образом, для f, g из AA и любого х из А имеет место равенство (fg)(x)=f(g(x)).

Универсальная алгебра A=AA;  является полугруппой.

9. Группой называется универсальная алгебра A=A; сигнатуры =,,e ( одноместная операция на А обозначаемая далее как , то есть f1(a)=a-1 и e - константный символ), если она удовлетворяет следующим условиям:

  1.  A;  полугруппа и

для любого а из А:

  1.  ae=ea=a,
  2.  aa-1=a-1a=e.

Для произвольного множества А через Bi(A) обозначим совокупность всех взаимно-однозначных отображений множества А на себя. Таким образом, Bi(A)AA. Операцию умножения  на Bi(A) определим так же как и на множестве AA. Через f 1 обозначим обратное отображение к отображению f из Bi(A). Таким образом, для х, у из А f--1(x)=yf(y)=x. Через idA обозначим тождественное отображение на А: для любого х из А idA(x)=x. Универсальная алгебра Bi(A);,--1,idA является группой.

Группа A=A;,--1,e называется абелевой (или коммутативной) если для любых а, b из А имеет место равенство ab=ba.

  1.  Кольцом называется универсальная алгебра A=A; сигнатуры +,,,0 (- одноместная функция на А, обозначаемая далее как , то есть f1(a)= – a, 0 – константный символ), если она удовлетворяет условиям:
  2.  A;+,,0  абелева группа
  3.  A;  полугруппа и

для любых а, b, с из А:

a(b+c)=(ab)+(ac),

    (b+c) a=(ba)+(ca).

Пусть Z - множество всех целых чисел и операции  константа 0 определяются на Z как традиционное сложение, умножение, взятие противоположного элемента и нуль. Тогда универсальная алгебра Z;+,,,0 является кольцом.

Как неоднократно говорилось выше, основным предметом изучения универсальной алгебры являются действия различных функций на произвольных множествах. В этом случае конкретное представление элементов этих множеств не играет принципиальной роли. Таким образом копирование или клонирование элементов универсальной алгебры, создание алгебры-близнеца не порождает, при изучении этих алгебр, существенно новой ситуации. К примеру, рассмотрим алгебру A={1,2,3}; сигнатуры = со следующей таблицей Кэли для функции f0:

x

f0(x)

1

3

2

2

3

1

Мы переобозначим (закодируем) элемент 1 как новый элемент а, элемент 2 – как b, элемент 3 как с и рассмотрим функцию f0, определённую на множестве {a,b,c} с помощью таблицы Кэли:

x

f0(x)

a

c

b

b

c

a


В этом случае новая алгебра
B={a,b,c};, полученная из алгебры A указанной кодировкой сохранит, очевидным образом, все родовые черты алгебры A, связанные с действием функции f0 на основном множестве алгебры. Таким образом, с точки зрения универсальной алгебры A и B представляют собой одну и ту же универсальную алгебру. Однако изучение алгебры A вместо алгебры B или наоборот может быть предпочтительнее с точки зрения наглядности, интуитивной прозрачности и так далее, связанной с конкретной природой множества {1,2,3} или {a,b,c}.

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

=.

Пусть A=A; и B=B;  пара произвольных алгебраических систем сигнатуры . Пусть  некоторая биекция основного множества А алгебры A на основное множество В алгебры B. Биекцию назовём изоморфизмом системы A на систему B, если выполняются следующие условия:

  1.  для любого lr, для любых элементов  из А имеет место равенство (fl())=fl((a1)( )) (здесь символ fl из левой части равенства означает функцию, интерпретирующую сигнатурный символ fl в системе A, а символ fl из правой части равенства – аналогичную функцию в системе B);
  2.  для любого lm, для любых элементов  из А, Pl()=ИPl((a1)( ))=И (здесь как и выше символ Pl слева от равенства означает отношение, интерпретирующее сигнатурный символ Pl в системе A, а справа – в системе B);
  3.  для любого lk (cl)=cl (здесь также левое cl означает элемент, интерпретирующий константный символ cl в системе A, а правое  cl  в системе B).

Очевидно, что приведенное понятие изоморфизма и соответствует интуитивному понятию копирования алгебраических систем.

Ещё раз попытаемся проиллюстрировать понятие изоморфизма алгебраических систем сигнатуры  = (см. рисунок).


  P0(A)                  (P0(A))=P0(B)

      A   f0(a1,a2)        f0((a1), (a2))= (f0(a1,a2))

          B

 a1                   (a1)

  a2       (a2)

                                                                                   

 c0       c0

A          B

здесь P0(A)={aA|P0(a)} и P0(B)={bB|P0(b)}.

Укажем несколько конкретных примеров изоморфизма алгебраических систем.

1) Пусть алгебраические системы A=N; и B={2n|nN}; имеют сигнатуру  = и таковы, что для любых a1,a2 из A, b1,b2 из B имеет место:

Здесь +, и  - традиционные сложение, умножение и отношение порядка на натуральных числах. Нетрудно заметить, что отображение :N{2n|nN}, определённое как (n)=2n, является изоморфизмом алгебраических систем A и B.

     2) Пусть алгебры A={0,1), и B=P({b}), имеют сигнатуру  =  и таковы, что  символы алгебры B определяются на P0({b}) условиями: для любых C,D{b}

Пусть символы алгебры A, определяются следующими таблицами Кэли:


для f0

x\y

0

1

0

0

1

1

1

1

для f1

x\y

0

1

   

0

0

0

1

0

1

для f2

x

f2(x)

0

1

1

0

.

Нетрудно проверить, что отображение :{0,1}P({b}) такое, что (0)=, (1)={b} является изоморфизмом алгебр A и B.

Непосредственно проверяется следующее утверждение:

()  а) тождественное отображение любой алгебраической системы A на себя является изоморфизмом A на A;

б) если  изоморфизм алгебраической системы A на систему B, то обратное отображение 1 является изоморфизмом алгебраической системы B на A;

в) если   изоморфизм алгебраической системы A на B, а   изоморфизм алгебраической системы B на C, то суперпозиция отображений и , отображение  является изоморфизмом алгебраической системы A на C.

Алгебраические системы A и B назовём изоморфными, если существует некоторый изоморфизм систем A на B. Эту ситуацию будем обозначать как AB.

Автоморфизмом алгебраической системы A будем называть любой изоморфизм этой системы на себя.

К примеру, пусть A =Z;, где Z - совокупность всех целых чисел, =+. Тогда тождественное отображение idZ множества Z на себя и отображение  : ZZ такое, что (n)= n являются автоморфизмами алгебры A и других автоморфизмов алгебры A не существует.

Для любой алгебраической системы A=A; сигнатуры и любой биекции множества А на множество В мы можем определить систему B=B; с основным множеством В так, что будет изоморфизмом системы A на систему B, полагая: для любых lr, um, k и любых элементов  из В

 = (fl(1(b1),..., 1())),

 Pu(a1,..., )=И  Pu(1(a1),..., 1())=И,

  ().

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

Отношением эквивалентности на множестве А называется двухместное отношение Q удовлетворяющее следующим условиям: для любых а, b, с из А:

1) Q(a,a) рефлексивность Q,

2) из Q(a,b) следует Q(b,a) симметричность Q,

3) из Q(a,b) и Q(b,c) следует Q(a,c) транзитивность Q.

Очевидно, что отношение равенства (Q(a,b)  a = b) является отношением эквивалентности на любом множестве А. Далее будем обозначать это отношение как A (т.е. A (a,b)  a = b). Отношение коллапса (или универсальное отношение) на А также является отношением эквивалентности на А (Q(a,b)=И для любых элементов а, b множества А).

Обозначим в дальнейшем это отношение как A. Очевидно, что для любого отношения эквивалентности Q на A имеют место включения AQA.

Пусть A={0,1,2,3} и отношения Q1 и Q2 определяются на А следующими таблицами Кэли:

для Q1

x\y

0

1

2

3

0

И

И

Л

Л

1

И

И

Л

Л

2

Л

Л

И

Л

3

Л

Л

Л

И

для Q2

x\y

0

1

2

3

0

И

И

Л

Л

1

И

И

Л

Л

2

Л

Л

И

И

3

Л

Л

И

И

Убедитесь, что оба эти отношения являются отношениями эквивалентности на А.

Пусть А произвольное множество. Набор непустых подмножеств B={Bi|iI}  назовём разбиением множества А, если выполнены следующие условия:

1) ,

2) для различных i1, i2  I   =.

Мы покажем, что в каком-то смысле понятия отношения эквивалентности на множестве А и разбиения множества А равносильны.

Пусть Q  отношение эквивалентности на А. Для любого элемента a из A классом эквивалентности Q для элемента а назовём подмножество {bA|Q(a,b)} множества А. Будем в дальнейшем обозначать это подмножество как [a]Q или a/Q.

Покажем что совокупность попарно различных классов эквивалентности Q образует разбиение множества А. Прежде всего заметим, что в силу рефлексивности отношения Q, для любого а из А имеет место включение a[a]Q. Пусть теперь [a]Q [b]Q  . Покажем, что в этом случае [a]Q=[b]Q. Достаточно показать. что имеет место включение [a]Q [b]Q, тогда в силу симметричности ситуации, будет иметь место и включение [b]Q [a]Q а, значит, и равенство [a]Q = [b]Q. Действительно, пусть d[a]Q. Так как [a]Q [b]Q  , то найдётся элемент c[a]Q  [b]Q. То есть имеет место Q(a,c) и Q(b,c). В силу симметричности отношения Q истинно отношение Q(c,a) и, значит по транзитивности Q, имеет место Q(b,a). Опять же в силу транзитивности Q, из Q(b,a) и Q(a,d) следует Q(b,d), что и доказывает включение d[b]Q. Как замечено выше последнего достаточно для доказательства равенства [a]Q=[b]Q.

Совокупность всех (попарно различных) классов эквивалентности по Q множества А назовём фактор-множеством множества А по отношению эквивалентности Q. Обозначать этот фактор-множество будем как . Таким образом, для любого элемента х включение x равносильно тому, что для некоторого а из А x=[a]Q. Заметим, что  образует разбиение множества А. Действительно, так как для любого а из А a[a]Q, то . С другой стороны, как доказано выше, если для a, b из А имеет место неравенство [a]Q [b]Q, то[a]Q [b]Q = . Это и доказывает то, что  является разбиением множества А (разбиением соответствующим эквивалентности Q).

Пусть теперь B={Bi|iI} произвольное разбиение множества А. На А определим отношение QB следующим образом: для любых a, b из А: QB(a,b)  существует iI такой, что a  Bi и b  Bi.

Предоставим читателю самому убедиться в том, что QB является отношением эквивалентности на А и, более того, имеет место:

( ) а) для любого отношения эквивалентности Q на А имеет место равенство Q =;

б) для любого разбиения B множества А имеет место равенство B=.

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

Заметим, что разбиение  состоит из одноэлементных множеств, а  состоит из одного единственного множества А.

На совокупности Eq(A) всех отношений эквивалентности на множестве А введём отношение , совпадающее с теоретико-множественным включением: для Q1,Q2Eq(A) пусть Q1  Q2тогда и только тогда, когда Q1  Q2 (как подмножества множества AA). Непосредственно замечается, что Eq(A); является частично упорядоченным множеством. Более того:

() Eq(A); решёточно-упорядоченное множество, где для любых Q1,Q2  Eq(A) отношение inf(Q1,Q2) определяется как пересечение отношений Q1 и Q2, рассматриваемых как подмножество множества AA, т.е. для любых a, b из А

inf(Q1,Q2)(a,b)  Q1(a,b) и Q2(a,b).

Наименьшая верхняя грань отношений Q1 и Q2 (sup(Q1,Q2)) в Eq(A); определяется более сложным образом:

для любых a, b из А sup(Q1,Q2)(a,b) существует конечная последовательность a = a0,a1,a2,...,a2n-1,a2n=b (необязательно различных) элементов множества А такая, что для любого i  n1 имеют место Q1(a2i,a2i+1) и Q2(a2i+1,a2i+2).

Доказательство утверждения () предоставляем читателю.

Решётку Eq(A);,, соответствующую решёточно-упорядоченному множеству Eq(A);, будем называть решёткой эквивалентностей на множестве А.

Задачи.

1. Пусть A= A; £ частично упорядоченное множество. Определим новое двухместное отношение P на A следующим образом: для любых a,bÎA пусть P(a,b) истинно тогда и только тогда, когда b£a. Покажите, что модель A;P так же является частично упорядоченным множеством. Отношение порядка P на A называется двойственным к порядку £ и обозначается как £*(a£*b Û b£a). Будет ли частично упорядоченное множество двойственное к цепи (к решеточно упорядоченному множеству) само являться цепью (решеточно упорядоченным множеством)?

2. Покажите, что частично упорядоченное множество из примера IV частично упорядоченных множеств является решеточно упорядоченным. Какие числа играют роль sup(n,m) и inf(n,m) для m,nÎ в этом частично упорядоченном множестве?

3. Докажите утверждение () из §1.

4. Пусть L  произвольное линейное пространство (над любым полем) и SubL  совокупность всех подпространств пространства L. На SubL определим операции Ù и Ú : для любых L1, L2ÎSubL пусть L1ÙL2 = L1ÇL2 и L1ÚL2 является подпространством порожденным множеством элементов L1ÈL2 пространства L. Докажите, что < SubL; Ú, Ù > является модулярной решеткой.

5. Докажите, что для любого множества A решетка R(A); È, Ç дистрибутивна.

6. Пусть L, в условиях задачи 4, двухмерное линейное пространство геометрических векторов. Докажите, что модулярная решетка Sub L;Ú, Ù не является дистрибутивной.

7. Докажите, что условие определяющее модулярность решетки A=A;Ú, Ù эквивалентно следующему: для любых a,b,cÎA, если a£b, то aÚ(bÙc) = bÙ(aÚc).

8. Докажите, что условие определяющее дистрибутивность решетки A =  A;Ú, Ù эквивалентно следующему: для любых a,b,cÎA, aÚ(bÙc) = (aÚb) Ù(aÚc).

9. Является ли решетка C, где C решеточно упорядоченное множество из примера IV частично упорядоченных множеств, модулярной, дистрибутивной?

10. Пусть B = B;Ú,Ù произвольная решетка, £  отношение порядка определенное на B с помощью решетки B стандартным образом. Покажите, что B* =B; f0,f1  решетка определяемая решеточно упорядоченным множеством B; £*, такова, что для любых a,bÎB f0(a,b) = aÙb, f1(a,b) = aÚb.

11. Пусть решетки M3 и N определяются следующими диаграммами Хассе:

 

Докажите, что решетка N не модулярна, а решетка M3 модулярна, но не дистрибутивна.

12. На множестве {0,1} определим операции сигнатуры s = Ú,Ù,Ø,0,1 следующими таблицами Кэли:

для Ú

x\y

0

1

Для Ù

x\y

0

1

для

x

x

0

0

1

0

0

0

0

1

1

1

1

,

1

0

1

,

1

0

Выберем для константного символа 0 значение 0, а для константного символа 1  значение 1. Докажите, что A = {0,1};s является булевой алгеброй.

13. Покажите, что для полугруппы R; где R  совокупность всех действительных чисел, а операция ·  традиционная операция умножения действительных чисел, невозможно доопределить операцию 1 и константу e так, что бы универсальная алгебра R;,1,e стала группой.

14. Покажите, что для полугруппы R;+, где роль полугрупповой операции умножения · играет роль традиционная операция сложения действительных чисел возможно (как?) доопределить операцию 1 и константу e так, что бы универсальная алгебра R;+,1,e стала группой.

15. Пусть A = A; ·,1,e группа. Для произвольных элементов a,b,c Î A выразите элементы (a·b)1, a·(b·c)1, ((a·b)1((c·(a1))·b))1 через произведения элементов a, b, c, a1, b1, c1.

16. Пусть A = A; ·,1,e группа. Докажите, что e единственный элемент x из A такой, что для любого a  A имеют место равенства ax = xa = a и для любого элемента b  A элемент b-1 это единственный в A элемент y такой, что by = yb = e.

17. Покажите, что если множество A содержит по крайней мере три элемента, то группа < Bi(A); ·, -1, idA > не является абелевой.

18. Докажите утверждение () из §1.

19. Докажите утверждение () из §1.

20. Пусть B1 = {Bi | iÎI } и B2 = {Cj | jÎJ} разбиения множества A. Сформулируйте на языке подмножеств Bi и Cj множества A отношение B1 £B2, имеющее место тогда и только тогда, когда имеет место отношение QB1£QB2. Опишите разбиения множества A отвечающие эквивалентностям QB1ÙQB2  и QB1ÚQB2 на языке подмножеств Bi и Cj множества A. Через Part(A) будем впредь обозначать совокупность всех разбиений множества A. Тем самым Part(A); решёточно упорядоченное множество. При этом sup(B1,B2) =A/( QB1Ú QB2), inf(B1,B2) = A/( QB1ÙQB2). Обозначая, как обычно, sup(B1,B2) как B1ÚB2, а inf(B1,B2) как B1ÙB2 получаем решетку Part(A);, разбиений множества A.

21. Докажите утверждение () из §1.

22. Пусть K некоторая совокупность алгебраических систем сигнатуры s. Докажите, что отношение изоморфности (A@B) на совокупности K является отношением эквивалентности.

23. Докажите, что частично упорядоченные множества N, R, A, C из примеров I) - IV) частично упорядоченных множеств не являются изоморфными.

24.Докажите, что для любой алгебраической системы A=A;  совокупность Aut A всех автоморфизмов системы A, относительно операций суперпозиции, взятия обратного отображения с константой idA, образует группу.

§2. Подалгебры и теоремы представлений для групп, булевых

алгебр,  дистрибутивных решеток.

К важнейшим понятиям универсальной алгебры относится понятие подалгебры. Пусть A=A; некоторая универсальная алгебра сигнатуры ,c0,...,ck. Подмножества множества А разбиваются на два принципиально различных класса: первый содержащие константы c0,...,ck алгебры A и замкнутые относительно сигнатурных функций f0,...,fr и второй не удовлетворяющие какому-либо из этих условий. Мы говорим, что подмножество B множества А замкнуто относительно функции fi(x1,..., ), если для любых b1,...,  из B значение fi(b1,..., ) так же лежит в B. На подмножествах B первого типа не составляет труда определить алгебру сигнатуры   наследницу алгебры A используя для интерпретации сигнатурных функций и констант сигнатурные функции и константы алгебры A. Подобную новую алгебру BB; и будем называть подалгеброй алгебры A. Итак, алгебра BB; является подалгеброй алгебры A=A; если выполнены следующие условия:

1) ВА;

2)  и, тем самым, для любого i  k ;

3) для любого j  r и любых b1,...,  B (b1,..., ) = (b1,..., )  и, тем самым, (b1,..., ) B. Здесь, как и во всех подобных случаях, индекс C у констант и функций ,  означает, что рассматривается интерпретация константного, функционального сигнатурного символа ci, fj в алгебре C.

К примеру, пусть  =+, A=N;+ и B = {n четноеnN}, тогда B=B;+ (и в A и в B +  это стандартное сложение натуральных чисел) будет подалгеброй алгебры A. Легко видеть, что если С произвольное конечное подмножество множества N отличное от {0} или С совокупность всех нечетных натуральных чисел, то невозможно определить подалгебру алгебры A с основным множеством С.

  Отношение теоретико-множественного включения между основными множествами подалгебр алгебры A очевидным образом является частичным порядком на множестве Sub A  множестве всех подалгебр алгебры A. Обозначим это частично упорядоченное множество как

Sub A =Sub A; .

Заметим, что сама алгебра A является подалгеброй алгебры A. С другой стороны, когда сигнатура не содержит констант, то, чисто формально, пустое подмножество удовлетворяет условиям 1)-3) и, тем самым, в случае бесконстантной сигнатуры мы будем говорить о пустой подалгебре A алгебры A. Подалгебра A наибольший элемент, а подалгебра A  наименьший элемент частично упорядоченного множества Sub A  (последнее в случае бесконстантной сигнатуры). Подалгебры алгебры A отличные от A и от A будем называть собственными подалгебрами алгебры  A.  

Для любой совокупности {Ai=Ai;  iI } подалгебр алгебры  A непосредственно проверяется, что множество  содержит все константы алгебры A и замкнуто относительно всех сигнатурных функций. Таким образом, на множестве существует подалгебра алгебры A. Обозначим  эту подалгебру как . Для любого iI  имеет место включение        Ai. Кроме того, для любой подалгебры C алгебры A, если для любого iI имеют место включения  C  Ai, то справедливо и включение  C . Иначе говоря, подалгебра является наибольшей нижней гранью совокупности подалгебр {AiiI} в частично упорядоченном множестве SubA. В частности, для любых подалгебр B, C алгебры A 

inf (B,C)=BC.

Пусть D произвольное подмножество основного множества А алгебры A и {AiiI} совокупность всех подалгебр алгебры A основные множества которых включают в себя подмножество D. Таким образом, основное множество алгебры   так же включает в себя множество D. С другой стороны, любая подалгебра B алгебры  A, включающая в себя D (одна из  Ai), будет включать в себя и подалгебру  . Тем самым,   наименьшая из подалгебр алгебры  A включающая в себя множество D. Будем обозначать эту подалгебру как DA и назовем ее подалгеброй алгебры   A  порожденной множеством D. Заметим, в частности, что для любых подалгебр B=B; и C=С; алгебры A в частично упорядоченном множестве SubA имеет место равенство

BUCA= sup(B,C).

Таким образом частично упорядоченное множество SubA  подалгебр алгебры  A является решеточно упорядоченным. Соответствующую решетку SubA; , мы будем обозначать тем же символом SubA, и называть решеткой подалгебр алгебры A.

Итак, ещё раз, для B=B; и C=С;  SubA:

BC=BUCA,

BC=BC.

Остановимся теперь более подробно на конструкции подалгебры порождённой данным множеством. Итак, пусть A=A; и DA. Рассмотрим подмножество D множества А определённое следующим образом:

D = D { fi(d1,..., )ir и d1,..., D} {c0,...,ck},

то есть D  получается добавлением к D всех констант алгебры A и всех значений сигнатурных функций на произвольных элементах из D. Очевидно, что DD. Обозначим теперь множество D как D0 и для любого натурального числа n определим подмножество Dn+1 равным (Dn). Таким образом, мы имеем дело с неубывающей бесконечной последовательностью

D = D0 D1 D2 ... Dn ... A.

Пусть D = . Покажем, что D замкнуто относительно сигнатурных функций алгебры A. Действительно, пусть d1,...,  D, тогда найдётся nN такое, что d1,...,  Dn. В силу определения Dn+1 = (Dn) , имеет место включение fi(d1,..., )Dn+1 D. Так же, в силу определения D1 , все константы алгебры A содержатся в D. Тем самым, существует подалгебра алгебры A с основным множеством D. С другой стороны, если C=C; некоторая подалгебра алгебры A включающая в себя D, без труда, индукцией по натуральному n, доказываются включения DnC для любого nN. Таким образом, C. Последнее означает, что D= является основным множеством наименьшей в SubA  подалгебры алгебры A содержащей множество D, т.е.

;=DA.

Опишем теперь строение подалгебры порожденной множеством D в иных терминах. Для этого нам понадобиться понятие терма сигнатуры . Пусть Х некоторое фиксированное счетное множество символов:    X={x0, x1,...,xn,...} множество переменных. Пусть =,c0,...,ck  фиксированная сигнатура. Термами сигнатуры будут являться конечные последовательности символов множества X {(,)}. Здесь (,) чисто технические символы скобки. Понятие терма сигнатуры будет определяться следующей индукцией по длине терма (длина терма  длина соответствующей последовательности символов):

1) переменные из Х и константы сигнатуры являются термами сигнатуры ( базис индукции определяющий самые короткие термы);

2) если и t1,...,  термы сигнатуры , то  (t1,..., ) так же терм сигнатуры (индукционный шаг);

3) любой терм сигнатуры строится за конечное число шагов согласно правилом 1), 2).

Для любого терма t сигнатуры определяется (опять же индукцией по построению терма) совокупность переменных Var(t) от которых зависит терм t :

1) Var(xi) = xi, Var(ci) =

2) Var(fi(t1,..., )) = .

Таким образом, терм t зависит от переменной хi, если эта переменная в явном виде входит в запись терма t. В случае когда Var(t) = {} мы будем употреблять запись t() или t() , обозначая через  кортеж .

К примеру, если  = ,,0,1, то следующие последовательности символов являются термами сигнатуры :

1) t1=(((x1+x2)0)+(1x3 ))x1, здесь Var(t1)={x1, x2, x3}, т.е. t1=t1(x1, x2, x3);

2) t2=(((x1+x1)0)+(1x1 ))x1, здесь Var(t2)={x1}, т.е. t2=t2(x1);

3) t3=(01)+(10), здесь Var(t3)=.

Для удобства записи в написании этих термов как и ранее, запись +(x,y) и (x,y). заменяется на традиционную (x+y) и (xy).

Нетрудно убедиться, что приведенные ниже последовательности символов не являются термами сигнатуры :

1) (x1+x2)x1x3;

2) (x1;

3) ;

4) 1+1+1+1.

       Каждому терму t(x1,...xn) сигнатуры на любой универсальный алгебре A=A; этой сигнатуры соответствует термальная функция tA()  обозначаемая далее просто как t()  и определенная индукцией по построению терма:

1) если t=t(xi)=xi , то для любого aA t(a)=a; если t=ci, то рассматриваем t как 0-местную функцию принимающую одно и то же значение  (константу).

2) если t() = fi(t1(),...,) (здесь   некоторые подмножества переменных из множества {}), то для любых a1,...,anA t(a1,...,an)=b, если fi(d1,..., )=b и t1=()=d1,..., . Здесь tj() значение термальной (более простой чем t и, тем самым, уже определенной по индуктивному предположению) функции tj() на переменных из  принимающих соответствующие значения  из элементов a1,...,an.

      К примеру, нетрудно подсчитать, что  для термов t1 ,t2 ,t3 , из приведенных выше примеров термов, на алгебре A=N;,,0,1 имеют место равенства:

1) t1(0,1,2)=0,t1(2,2,3)=6 ;

2) t2(0)=0, t2(1)=1, t2(2)=4 ;

3) t3=0.

Если вместо алгебры A рассмотрим алгебру B=P({1,2,3}); ,,,{1,2,3}, т.е. алгебру с основным множеством P({1,2,3}) на котором двухместные сигнатурные функции +,  интерпретируются как и соответственно, а константные символы 0 и 1 как и {1,2,3,}, то получаем  следующие равенства :

1) t1 ({1},{2,3},{1,3})={1},  t1({1,2,3},,{1,2})={1,2,};

2) t2(A)=A  для любого A {1,2,3}.

Индукцией по длине терма t(x1,...,xn)  нетрудно доказать, что

() для любой подалгебры B=B; алгебры A=A; и любых элементов b1,...,bnB имеет место включение t(b1,...,bn)B.

Таким образом  подалгебры замкнуты относительно термальных функций.

Пусть теперь D произвольное подмножество множества А. Определим  множество DT следующим образом:

DT={t(a1,...,an)t(x1,...,xn) произвольный терм сигнатуры , a1,...,an произвольные элементы из D}.

Множество DT содержит все константы алгебры A и замкнуто относительно сигнатурных функций. Действительно, если fi(x1,...,xn) и d1,..., DT, то найдутся термы t1(),..., и кортежи элементов   множества D такие, что d1=t1(),...,. При этом, можно считать, что совокупности переменных  попарно дизъюнктны. В этом случае,

fi(d1,..., ) = t(),

где  t() = fi(t1(),...,) терм сигнатуры . Тем самым, действительно, fi(d1,...,)DT, т.е. DT замкнуто относительно термальных функций. С другой стороны, рассматривая терм  убеждаемся в справедливости включения  DDT .

Доказанные свойства множества DT , наряду с утверждением (*), демонстрируют справедливость равенства

DT;  =DA

для любой алгебры A и любого ее подмножества D.

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

Начнем с групп. В §1 для любого множества А была определенна группа Bi(A);,1,idA  группа всех биекций множества А самого на себя. Обозначим далее эту группу как Sym A и будем называть ее симметрической группой множества А. Подалгебры произвольной группы будем далее именовать ее подгруппами. Имеет место следующая теорема представления для групп.

ТЕОРЕМА КЭЛИ. Для любой группы G = G;,1,e существует изоморфизм этой группы на некоторую подгруппу симметрической группы множества G.

Доказательство. Для любого элемента а из G через a обозначим отображение  множества G в себя определенное равенством

a(x)=ax

для любого хG. Так как х = a(a1x) = a(a1x), то отображение a, будет отображением G на G. Если a(x) = a(y), то  и, значит, х=ex=(a1a)x=a1(ax)= =a1(ay)=(a1a)y=ey=y.

Таким образом, любое отображение вида a является биекцией множества G самого на себя, т.е. aBi(G)

Так как для любого хG   e(x)=ex=x,  то e=idG.

Для любых a,bG и любого х из G

ab(x)=(ab)x=a(bx)=a(b(x))=(ab)(x)

Последнее произведение ab подразумевается как произведение в группе Sym GТаким образом имеет место

ab = ab.

В силу того, что имеют место равенства

idG(x)=x=ex=(a1a)x=a1(ax)=(a(x))=(a)(x)

и 

idG(x)=x=ex=(aa1)x=a(a1x)=a((x))=(a)(x)

является биекцией обратной к биекции a , т.е.

                                             = (a)1.

Кроме того, если для некоторых a,bG и любого хG  имеют место равенства a(x) = b(x), то, в частности, a(e) = b(e) и, значит,

a=ae=a(e)=b(e)=be=b.

Тем самым, во-первых, совокупность {aaG} являются подгруппой группы Sym G и, во-вторых, отображение : G Bi(G), определенное как

(a) = a

для любого aG, является изоморфизмом группы G=G;,1,e на подгруппу {aaG};,1, idG симметрической группы Sym G. Теорема доказана.

В §1 для любого множества А рассмотрена полугруппа AA; всех отображений множества А в себя. Обозначим эту полугруппу далее как F(A) и будем  называть ее полугруппой отображений множества А.

Аналогично доказательству теоремы Кэли с добавлением к полугруппе единицы доказывается следующая теорема представления для полугрупп.

ТЕОРЕМА 1. Для любой полугруппы S=s; существует изоморфизм этой полугруппы на некоторую подалгебру (подполугруппу) полугруппы отображений некоторого множества.

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

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

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

Аксиома выбора представляет собой следующее теоретико-множественное утверждение: для любой функции F, определенной на произвольном множестве I и принимающей в качестве  значений F(i) (iI) некоторые непустые множества, существует функция f : I   такая, что для любого iI f(i)F(i), т.е. аксиомой выбора утверждается возможность одновременного (для любого iI) выбора во множествах F(i) некоторых элементов f(i). Возможность такого выбора для конечных множеств I не вызывает сомнения. Проблематичным это становится в случае бесконечного I и произвольных непустых множеств F(i). Проблема принятия или не принятия аксиомы выбора относится к основаниям математики и не будет здесь дискутироваться. Было доказано, что аксиома выбора является  независимой  от стандартных, общепризнанных аксиом теории множеств  известных под аббревиатурой ZF-аксиом  Цермело-Френкеля, т.е. как принятие утверждения аксиомы выбора, так и принятие отрицание ее утверждения не ведут к противоречиям с аксиомами ZF. В начале этого века была широкая дискуссия вокруг возможности использования аксиомы выбора в математике, поскольку ее принятие влекло в качестве следствий некоторые парадоксальные, на первый взгляд, утверждения. Однако неприятие аксиомы выбора существенно обедняло интуитивно приемлемое содержание конкретной (не связанной с вопросами философии математики и теории множеств) математики, в том числе и алгебры. В результате аксиома выбора стала широко использоваться в конкретных математических исследованиях. Не будем чураться этого использования  и мы.

Нам потребуется некоторое эквивалентное аксиоме выбора (относительно ZF) утверждение известное под именем леммы Цорна. Доказательство эквивалентности утверждения леммы Цорна и аксиомы выбора мы опускаем, желающие могут найти его, к примеру, в книге [4].

Для формулировки  леммы Цорна нам потребуются некоторые определения. Подмножество С некоторого частично упорядоченного множества A;  называется цепью в A; , если для любых a,bC имеет место либо ab, либо ba. Иными словами подмножество С является цепью в A;  если частично упорядоченное множество C; , с порядком  индуцированным  на С порядком из A; , является цепью. Как и ранее, элемент d из А называется верхней гранью для С,  если для любого b из С имеет место неравенство bd. Элемент а частично упорядоченного множества A;  называется наибольшим, если для любого bA имеет место  неравенство ba. Элемент а множества A;   называется максимальным в A; , если в А нет элементов строго больше чем а, т.е. если для любого b из А неравенство ab влечет равенство a=b. Очевидно, что наибольший элемент частично упорядоченного множества, если он существует, единственен и является максимальным в этом множестве. В отличии от наибольших элементов множества A;  число максимальных элементов в частично упорядоченном множестве неограниченно. В то же время  максимальных элементов в частично упорядоченном множестве может и не быть. Следующие примеры призваны прояснить введенные понятия.

1). В частично упорядоченных множествах N;  и N\{0};-1 (где   обычное отношение порядка на натуральных числах, а для m,n  N\{0} отношение n 1 m означает, что n нацело делит m) нет ни максимальных, ни наибольших элементов.

2). Пусть {1,2,3,4};1 частично упорядоченное множество с  отношением порядка 1 определенным следующей таблицей Кэли:

x \ y

1

2

3

4

1

И

И

Л

Л

2

Л

И

Л

Л

3

Л

Л

И

И

4

Л

Л

Л

И

Очевидно, что это множество не имеет наибольшего элемента, а элементы 2,4 являются максимальными.

Будем говорить, что элемент а содержится в элементе b частично упорядоченного множества A; , если имеет место ab.

ЛЕММА ЦОРНА. Если любая цепь в частично упорядоченном множестве A;  обладает верхней гранью, то любой элемент этого множества содержится в некотором максимальном элементе, т.е. для любого aA существует  в А  максимальный элемент b такой, что ab.

Рассмотрим теперь произвольную булеву алгебру B=B;,,,0,1.  Непустое  подмножество С множества В называется фильтром булевой алгебры B, если выполняются  условия:

1) для  любого cC и любого bB неравенство cb влечет включение bC;

2) для любых c1,c2C имеет место включение c1c2C;

Здесь и далее под отношением порядка на булевой алгебре B имеется в виду порядок определенный на B как на решетке, т.е.

ab  ab = a  ab = b.                             

В качестве примеров фильтров в булевой алгебре B прежде всего укажем на само множество В. Кроме того, для любого элемента а из В через Fa обозначим подмножество {cBac}. Очевидно, что для любого aB множество Fa является фильтром булевой алгебры B (главным фильтром порожденным элементом а). В данном  констенте B = F0 (т.к. для любого aB 0a). Фильтры булевой алгебры B отличные от B = F0  будем называть собственными фильтрами. Заметим так же, что из неравенства a1  для любого элемента а из В следует, что любой фильтр булевой алгебры содержит единицу 1 этой булевой алгебры.

Нетрудно заметить справедливость следующего утверждения:

(**)  Любой фильтр конечной булевой алгебры является главным.

С другой стороны на любой бесконечной булевой алгебре B существует неглавные фильтры. Не  доказывая в полном объеме, проиллюстрируем это на примере булевой алгебры B=P(A);,,,, для бесконечного множества А. Пусть F={CAC конечно}. Предоставляем читателю самому убедиться в том, что F  фильтр булевой алгебры B (именуемый в дальнейшем фильтром Фреше). Так же очевидно, что F  неглавный фильтр этой алгебры.

Пусть F(B) - совокупность всех собственных фильтров булевой алгебры B. Теоретико-множественное отношение является, очевидно, частичным порядком на множестве F(B). Максимальные элементы частично упорядоченного множества F(B); будем называть ультрафильтрами булевой алгебры B.  

Прежде всего докажем, что любой фильтр булевой алгебры B содержится в некотором ультрафильтре. Для этого, в силу леммы Цорна, достаточно доказать, что любая цепь в частично упорядоченном множестве F(B);  фильтров булевой алгебры B имеет верхнюю грань. Действительно, пусть {FiiI} некоторая цепь упорядоченного множества F(B);, т.е. Fi собственные фильтры булевой алгебры B и для любых i,jI либо Fi Fj, либо Fj Fi. Положим F = . Нетрудно заметить, что F является фильтром на B. Т.к. для любого iI, 0Fi, то 0, т.е. фильтр F собственный. Очевидно, что для любого iI FiF. Итак, в частично упорядоченном множестве F(B); цепь {FiiI} имеет верхнюю грань F, а значит, каждый фильтр булевой алгебры B содержится в некотором ультрафильтре.

Сформулируем и докажем теперь иную более конструктивную характеризацию ультрафильтров.

 ЛЕММА 1. Фильтр F булевой алгебры B является ультрафильтром тогда и только тогда, когда для любого элемента а из B выполнено ровно одно условие: либо aF, либо aF.

Доказательство. Пусть F некоторый ультрафильтр булевой алгебры B. Прежде всего заметим, что ни для какого элемента а условия aF и aF не могут быть выполнены одновременно. Действительно, в противном случае 0=aaF, что противоречит собственности фильтра F. Допустим теперь, что для некоторого элемента aB ни а, ни a не входят в F. Рассмотрим множество D={abbF}. Заметим, что для любых c1,c2D элемент c1c2 так же входит в D. Действительно, существуют b1, b2 F такие, что c1= ab1, c2=ab2. Но тогда,

c1c2=(ab1)(ab2)=a((b1a)b2)=a((ab1)b2)=

=a(a(b1b2))=(aa)(b1b2) =a(b1b2)

и т.к. b1b2F то c1c2D. Заметим так же, что 0D. Иначе, найдется bF такой, что 0=ab. Но тогда a=a0=a(ab)=(aa)(ab)=1(ab)= ab, т.е. ba и, т.к. bF, то aF.  Полученное противоречие с условием, что aF, aF и доказывает требуемое: 0D.

Пусть теперь F={dBдля некоторого с из D имеет место неравенство cd}. Очевидно, что FF и aF. Предоставляем  читателю убедиться в том, что F является собственным фильтром булевой алгебры B. При этом F строго больше  F в частично упорядоченном множестве F(B);, что противоречит выбору F как ультрафильтра. Таким образом, действительно, для любого ультрафильтра F булевой алгебры B и любого элемента а из B выполняется ровно одно  из условий: либо aF, либо aF.

Докажем обратное. Пусть F фильтр булевой алгебры B и для любого aB имеет место либо aF , либо aF. Допустим, что F не ультрафильтр. Тогда найдется некоторый собственный фильтр F* включающий F и отличный от него. Пусть cF*\F, но тогда cF и, значит, 0=ccF, что противоречит собственности фильтра F*. Лемма доказана.

Мы можем, наконец, приступить к доказательству теоремы представления для булевых алгебр. Через StB будем обозначать совокупность всех ультрафильтров булевой алгебры B.

ТЕОРЕМА СТОУНА. Для любой булевой алгебры B существует подалгебра булевой алгебры P(StB);,,,,StB всех подмножеств множества StB  изоморфная булевой алгебре B.

Доказательство. Отображение BP(StB) определим следующим образом: для bB (b)={FStBbF}, т.е. (b) это совокупность всех ультрафильтров алгебры B содержащих элемент b.

В силу замеченного вслед за определением фильтров, (0)= и (1)=StB.

Пусть b1, b2,B. Покажем, что:

(b1b2)=(b1)  (b2),

(b1b2) =(b1) (b2),

(b1)= StB\(b1).

Действительно, если F(b1), то b1F, но b1b1b2 и, значит, b1b2 F, т.е. (b1)(b1b2). Точно так же имеет место включение (b2)(b1b2). Включение (b1)  (b2)  (b1b2)  доказано. Пусть теперь F(b1b2) и F(b1)  (b2), тогда b1b2F, b1F,b2F. В силу того, что F ультрафильтр, по лемме 1, b1 F , b2F и значит (b1b2)=b1b2F. Включения b1b2F, (b1b2)F противоречат лемме 1. Таким образом, (b1b2)(b1)  (b2) и первое равенство (b1b2) = (b1)  (b2) доказано.

Доказательство равенств (b1b2)= (b1)  (b2), (b1) = StB\(b1). предоставляем читателю.

Для доказательства теоремы теперь достаточно доказать, что для b1  b2 из B (b1)  (b2).

Действительно, если b1  b2 , то либо b1 b2 0, либо b2 b1 0. Допустим первое (второе рассматривается аналогично). Тогда главный фильтр  содержится в некотором ультрафильтре F и, тем самым, b1b2F. В этом случае b1b2  b1 и, значит, b1F, то есть F(b1). В то же время F(b2), т.к. в противном случае, b2F и т.к. b1b2F, то 0=b10=b1(b2b2)=(b1b2)b2F в противоречии с собственностью фильтра F.

Итак, действительно, доказано, что отображение является изоморфизмом булевой алгебры B на некоторую подалгебру булевой алгебры P(StB);,,,,StB. Теорема доказана.

Основной смысл утверждения теоремы Стоуна сводится к тому, что работая с произвольной булевой алгеброй, мы можем считать элементы булевой алгебры подмножествами некоторого фиксированного множества, а операции сигнатуры  =,,,0,1  теоретико-множественными объединением, пересечением, дополнением соответственно.

Без доказательства приведем так же следующий результат (теорему представления для дистрибутивных решеток).

ТЕОРЕМА 2. Для любой дистрибутивной решетки B существует множество А и некоторая подалгебра (подрешетка) дистрибутивной решетки P(A);, изоморфная решетке B.

Полное доказательство этого результата см., к примеру, в [5].

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

Решетки M3 и определены в задаче 12 параграфа №1.

ТЕОРЕМА ДЕДЕКИНДА-БИРКГОФА. Решетка B является модулярной тогда и только тогда, когда она не содержит подрешеток изоморфных решетке N. Решетка B является дистрибутивной тогда и только тогда, когда она не содержит подрешеток, изоморфных решеткам M3, .

Полное доказательство этого результата можно найти в [5].

Задачи.

1. Приведите примеры бесконечного числа различных подалгебр алгебры A=N;+.

2. Сколько подалгебр имеет алгебра A=P({1,2,3});,, {1,2,3}. Укажите  все эти подалгебры.

3. Пусть A{0,1,...,n 1};, где функция f0 определена на {0,1,...,n 1} по правилу f0(m)=m+1(mod n), т.е. f0(m)=m+1 для m<n 1 и f0(n 1)=0. Найдите все подалгебры алгебры A.

4. Пусть A{0,1,...,n 1};, где функция f0 определена на {0,1,...,n 1} по правилу f0(m,k)=m+k(mod n). Найдите все подалгебры алгебры A.

5. Докажите, что в решетке Sub A  подалгебр алгебры A = Z;+,-   наименьшая подалгебра 0;+,-   не имеет покрытий.

6. В алгебре AN; укажите наиболее простой общий вид элементов подалгебры порожденной множеством  {2,3,4}.

7. Подалгебра B алгебры A называется конечно порожденной, если существует конечное подмножество С основного множества алгебры A такое, что BA. Докажите, что в решетке SubA для любых двух конечно порожденных подалгебр B, C алгебры A подалгебра BC так же является конечно порожденной.

8. Пусть a,b различные элементы отличные от элементов множества целых чисел Z. Сигнатура равна . Алгебру A=Z{a,b}; определим следующими  условиями: для любых m,n из Z: f0(n,m)=n+1, f0(a,n) = f0(b,n) = n, f0(n,a) = f0(n,b) = 0, f0(a,a) = f0(b,b) = f0(a,b) = f0(b,a) = 0. Приведите примеры двух конечно порожденных подалгебр B и C алгебры A таких, что алгебра BC не является конечно порожденной.

9. Пусть сигнатура алгебры A содержит константы c0,..., . Какая подалгебра алгебры A является наименьшим элементом решетки SubA, укажите общий вид элементов этой подалгебры.

10. Докажите утверждение (*) из параграфа 2.

11. Укажите все подгруппы групп Sym{1,2} и Sym{1,2,3}.

12. Пусть  =+,,0,1 и A=Z;+,,0,1, где сигнатурные символы сигнатуры имеют традиционную интерпретацию на множестве Z всех целых чисел. Докажите, что любая термальная функция f(x) одного аргумента х на алгебре A имеет вид многочлена с натуральными коэффициентами от х.       

13. Докажите теорему 1 из параграфа 2.

14. Докажите утверждение (**) из параграфа 2.

15. Элемент а булевой алгебры B=B;,0,1 называется атомом, если a0 и для любого элемента bB либо ab=a, либо ab=0. Докажите, что элемент а является атомом булевой алгебры B тогда и только тогда, когда а минимальный элемент в частично упорядоченном множестве ненулевых элементов булевой алгебры B. Докажите, что главный фильтр Fb булевой алгебры B является ультрафильтром тогда и только тогда, когда b атом булевой алгебры B.

16. Для булевой алгебры B=P({0,…,n-1});,,,,{0,…,n-1} докажите, что число ее подалгебр совпадает с числом разбиений множества  {0,…,n-1}. Затем докажите изоморфизм решеток         Sub B и Part {0,…,n-1};.

§3. Алгебраические решетки.

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

Решетку B=B;, назовем полной, если любое подмножество C множества B обладает в B наименьшей верхней (sup C) и наибольшей нижней (inf C) гранью, т.е. в B существуют элементы a=sup C и b=inf C такие, что:

1) для любого сС справедливы неравенства bca и

2) для любых b1, a1B таких, что для произвольного сС b1сa1 имеют место неравенства b1b и aa1.

В качестве примера полной решетки укажем на решетку P(A);, для любого множества A. Действительно, если C=Bi | iI  некоторая совокупность подмножеств множества A, то sup C = и inf C =. С другой стороны, решетка A=Z;,, где для m,nZ mn=min(m,n) и mn=max(m,n) дает пример не полной решетки: само множество Z не имеет в A ни наименьшей верхней, ни наибольшей нижней грани.

Из последнего примера вытекает следующее требование к полной решетке :

любая полная решетка обладает наибольшим и наименьшим элементами. Действительно, если B=B;, полная решетка, то sup B     ( inf B ) является наибольшим ( наименьшим ) элементом этой решетки.

Далее наибольший элемент любой решетки B (если он существует) будем называть единицей этой решетки и обозначать как 1B, а наименьший - нулем 0B решетки B. Решетка обладающая единицей и нулем называется ограниченной решеткой. Таким образом, всякая полная решетка ограничена.

Следующий пример показывает, что требование ограниченности решетки слабее требования ее полноты. Пусть B=Z;, и для любых n,mN (Z \ N) mn=min(m,n) и mn=max(m,n), а для nN и mZ \ N mn=min(m,n), mn=max(m,n).Проверьте, что в этой решетке B множество N не имеет наименьшей верхней, а множество Z \ N  наибольшей нижней грани. В то же время -1=1B и 0=0B.

Большим и естественным классом полных решеток является класс решеток подалгебр SubA произвольных алгебр A. Действительно, не представляет труда убедиться в том, что:

(*) для любого множества D={C i=Ci; | iI} подалгебр алгебры A подалгебра  совпадает с inf D в решетке SubA, а подалгебра A  c sup D.

Элемент a решетки B=B;, назовем компактным, если для любого подмножества C множества B неравенство a sup С влечет существование конечного подмножества C1C такого, что a sup C1.

Пусть B=P(A);,, тогда для любого СA имеет место равенство C=sup{{d} | dC}. Тем самым, компактными элементами в решетке B являются конечные подмножества множества A и только они.

Выясним теперь, каковы компактные элементы в решетке SubA для любой универсальной алгебры A. Для любого множества B через P(B) обозначим совокупность всех  конечных подмножеств множества B. Подалгебра B=B; алгебры A называется конечно порожденной, если существует конечное подмножество DB такое, что B=DA. Для любой подалгебры C=C; алгебры A имеет место равенство

C = sup{