Портал | Содержание | О нас | Авторам | Новости | Первая десятка | Дискуссионный клуб | Чат Научный форум --> Первая десятка "Русского переплета" Темы дня:

Президенту Путину о создании Института Истории Русского Народа. |Нас посетило 40 млн. человек | Чем занимались русские 4000 лет назад?

| Кому давать гранты или сколько в России молодых ученых?

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

Л. Н. ШЕВРИН

Уральский государственный университет, Екатеринбург

_ Я приветствую полугруппу, где бы я ее ни встретил, а встречается она повсюду. Впрочем, от друзей я слышал, что в математике попадаются объекты, отличные от полугрупп.

Эйнар Хилле

ВВЕДЕНИЕ

Высказывание, воспроизведенное в эпиграфе, принадлежит известному американскому математику Э. Хилле и содержится в предисловии к первому изданию его фундаментальной монографии "Функциональный анализ и полугруппы". Рассматриваемые в указанной монографии полугруппы - это главным образом разного рода полугруппы линейных операторов пространств, изучаемых в функциональном анализе. Соответствующая теория - аналитическая теория полугрупп возникла в 40-х годах. В ту пору, как писал Хилле в упомянутом предисловии, она представляла собой "недавнее пополнение все время растущей семьи математических дисциплин"; теперь это одна из важнейших частей функционального анализа. Вообще же понятие полугруппы - чисто алгебраическое понятие, ставшее основой развития большой области современной алгебры и участвующее в разнообразных приложениях алгебры, в том числе в приложениях в теории автоматов, теории кодов, математической лингвистике и многих других областях, включая даже биологию и социологию.

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

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

1. ПРИМЕРЫ ПОЛУГРУПП

Напомним необходимые определения. Бинарной операцией на множестве S называется отображение множества всех упорядоченных пар (x, y) элементов из S в множество S, то есть правило, сопоставляющее любой такой паре вполне определенный элемент из S - результат применения данной операции к x и y. В зависимости от выбора символа для обозначения операции указанный результат обозначается как x + y, x + y, x " y, x ╒ y, x ╥ y и т.п. Операция + называется ассоциативной, если она удовлетворяет тождеству ассоциативности (по школьной терминологии, сочетательному закону): для любых x, y, z

(x + y) + z = x + (y + z).

Полугруппой называется всякое множество с заданной на нем бинарной ассоциативной операцией. Полугруппа S с операцией + называется коммутативной, если для любых x, y k S

x + y = y + x.

Если полугрупповая операция обозначена знаком + [знаком " или отсутствием знака], то ее называют сложением [умножением] и говорят об аддитивной [мультипликативной] полугруппе.

Что значит привести пример полугруппы? Во-первых, это значит указать множество, во-вторых, задать на этом множестве бинарную операцию и, в-третьих, убедиться (доказать или вспомнить ранее установленное), что заданная операция ассоциативна. В примерах, которые последуют ниже, заинтересованному читателю как раз и предлагается либо вспомнить известное ранее о тех или иных операциях, либо провести необходимые умозаключения или выкладки, доказывающие ассоциативность соответствующих операций. Стандартные обозначения N, Z, Q и R используются для "главных" числовых множеств: всех натуральных, всех целых, всех рациональных и всех действительных чисел.

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

1.2. Мультипликативная полугруппа натуральных чисел. Это определенно вторая среди полугрупп, с которой знакомятся все изучающие математику.

1.3. Назовем сразу шесть числовых полугрупп: каждое из множеств Z, Q, R является как аддитивной, так и мультипликативной полугруппой. В средних и старших классах школы это постоянные спутники изучающих математику. Три только что упомянутые аддитивные полугруппы являются даже группами. Напомним, что группой называется полугруппа, в которой есть нейтральный элемент и каждый элемент обладает симметричным к нему элементом; элемент e называется нейтральным относительно операции +, если e + x = x + e = x для любого x из рассматриваемого множества, элемент y симметричен элементу x, если x + y = y + x = e. Нейтральный элемент аддитивной [мультипликативной] полугруппы называют нулем [единицей], симметричный элемент - противоположным [соответственно обратным].

1.4. На множестве N рассмотрим две операции D и W, заданные следующим образом:

xDy = НОД(x, y), xWy = НОК(x, y).

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

1.5. На любом множестве M действительных чисел рассмотрим две операции ╒ и ╥, заданные следующим образом:

x ╒ y = min{x, y}, x ╥ y = max{x, y}.

Обе они ассоциативны, так что мы ("перебирая" множества M ) получаем два семейства полугрупп, довольно сильно отличающихся от аддитивных и мультипликативных числовых полугрупп.

1.6. Множество всех векторов на плоскости (или в пространстве) относительно сложения является группой.

1.7. На множестве P(M ) всех подмножеств произвольного множества M рассмотрим операции пересечения < и объединения >. Обе они ассоциативны, так что перед нами еще два семейства полугрупп.

1.8. Полугруппы матриц. Множество всех квадратных матриц данного порядка с элементами, например из Z (или из Q, или из R), относительно умножения является полугруппой. Определение произведения матриц можно найти в любом вузовском учебнике алгебры; для матриц второго порядка мы напомнили его в [2, п. 2].

1.9. Полугруппы преобразований. Пусть X - произвольное непустое множество. Преобразованием множества X называется всякое отображение f этого множества в себя; любой элемент x k X переводится преобразованием f в однозначно определенный элемент f (x), называемый образом элемента x. При этом, вообще говоря, не требуется взаимной однозначности преобразования, то есть различные элементы могут иметь один и тот же образ. (Заметим, что иногда под преобразованием понимают именно взаимно однозначное отображение множества на себя; в этом смысле, например, данный термин используется в статье [3].) Множество всех преобразований множества X обозначим T (X ). По определению, преобразования f и g из T (X ) равны, f = g, если f (x) = g(x) для любого x k X.

Понятие преобразования принадлежит к числу самых важных математических понятий. Примечательно, что множество T (X ) является полугруппой относительно операции умножения (называемой также композицией или суперпозицией), определяемой следующим образом: произведением преобразований f и g называется преобразование f g, заданное условием

f g(x) = f (g(x))

для любого x k X. Другими словами, f g есть результат последовательного выполнения сначала преобразования g, затем преобразования f. Легко убедиться в ассоциативности этого умножения. Полугруппу T (X ) называют полной полугруппой преобразований (или симметрической полугруппой) на множестве X.

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

1.10. Пусть X - произвольное множество, а Y - одно из числовых множеств N, Z, Q, R. Через T (X, Y ) обозначим множество всех отображений (функций) из X в Y. На множестве T (X, Y ) можно определить операцию + (так называемое поточечное умножение функций), сопоставляя любым двум функциям их произведение f + g, заданное следующим условием: для любого x k X

f + g(x) = f (x)g(x),

где в правой части равенства осуществляется обычное умножение чисел в Y. Легко видеть, что такое умножение функций ассоциативно - имеем еще одно семейство полугрупп.

1.11. Свободные полугруппы. Пусть A - произвольное (непустое) множество. Будем здесь называть A алфавитом, а элементы A - буквами. Через FA обозначим множество всех конечных последовательностей букв из A. Зададим на FA операцию умножения, полагая

(a1 , _, am) " (b1 , _, bn) = (a1 , _, am , b1, _, bn).

Легко видеть, что эта операция (называемая иногда конкатенацией, то есть сцеплением) ассоциативна, так что FA становится полугруппой, которая называется свободной полугруппой над алфавитом A. Другое употребительное обозначение для нее - A +. Отождествляя последовательность из одной буквы с самой этой буквой и опуская в записи точку для конкатенации, получаем (a1 , a2 , _, am) = a1a2_am . В виде таких произведений, как правило, и записывают элементы свободной полугруппы и называют их словами. По определению, слова a1a2_am и c1c2_ck равны, если m = k и ai = ci при i = 1, _, m.

Свободные полугруппы наряду с симметрическими играют важную роль как в общей теории полугрупп, так и в приложениях. Их прикладная роль объясняется, в частности, тем, что во многих процессах передачи информации передаваемые сообщения представляют собой цепочки символов ("реальных" букв или слов, других кодовых знаков, электрических сигналов и т.д.) и соединение двух таких цепочек есть не что иное, как конкатенация слов в подходящей свободной полугруппе. Свободные полугруппы (главным образом над конечными алфавитами) являются исходным объектом в теории формальных языков и теории кодов, существенна их роль в теории автоматов. При этом обычно к элементам полугруппы A + добавляют так называемое пустое слово, не содержащее букв и играющее роль единицы при умножении, получается полугруппа, обозначаемая A * и называемая свободным моноидом над алфавитом A. Формальным языком называется произвольное подмножество некоторого свободного моноида.

Упомянутые выше приложения подробно рассматриваются в монографии [4], где содержится и достаточно полная (на середину 80-х годов) библиография по соответствующей проблематике. Приложениям полугрупп - от автоматов и формальных языков до некоторых биологических и социологических моделей - посвящены две главы учебного пособия [5].

1.12. Пусть M - произвольное (непустое) множество. Зададимся вопросом: можно ли превратить M в полугруппу? Другими словами, можно ли задать на M какую-нибудь ассоциативную операцию? Ответ утвердительный. Более того, если M неодноэлементно, то это можно сделать многими способами, а при бесконечном M - бесконечным числом способов. Укажем несколько таких способов.

(а) Положим x + y = x для любых x, y k M. Очевидно, введенная операция + ассоциативна. Полугруппу с такой операцией называют полугруппой левых нулей.

( б) Положим x + y = y для любых x, y k M. Этот пример полугруппы правых нулей аналогичен предыдущему.

(в) Зафиксируем элемент a k M и положим x + y = = a для любых x, y k M. И эта операция +, очевидно, ассоциативна.

(г) Пусть M конечно и его элементы пронумерованы: M = {a1 , a2 , _, an}. Зададим на M операцию +, полагая

ai + aj = amin{i, j } .

Легко убедиться, что введенная операция ассоциативна (ср. с первым примером из п. 1.5).

Обратимся еще раз к списку рассмотренных в п. 1.1-1.12 примеров полугрупп и посмотрим, какие из них коммутативны. Это все полугруппы, указанные в п. 1.1-1.7 и 1.10. В п. 1.12 полугруппы в примерах (в) и (г) коммутативны, а в примерах (а) и (б) при неодноэлементном множестве M некоммутативны, что очевидно. Основные рассмотренные в п. 1.8 и 1.9 полугруппы некоммутативны: легко найти как неперестановочные матрицы, так и неперестановочные преобразования. Что касается свободной полугруппы A +, введенной в п. 1.11, то для однобуквенного алфавита она, как легко усмотреть, коммутативна, а если A состоит из более чем одной буквы, то A + некоммутативна: так, для различных букв a и b слова ab и ba неравны.

Пусть S - полугруппа с операцией +. Подмножество H в S называется подполугруппой полугруппы S, если для любых x, y k H выполняется x + y k H, то есть, как принято говорить, H замкнуто относительно операции +. Понятно, что всякая подполугруппа произвольной полугруппы сама будет полугруппой относительно той же операции. Тем самым запас примеров полугрупп может быть значительно расширен за счет подполугрупп уже рассмотренных полугрупп.

2. ИЗОМОРФНОСТЬ ПОЛУГРУПП

Пусть S и T - полугруппы с операциями + и * соответственно. Изоморфизмом S на T называется всякое взаимно однозначное отображение j S на T, удовлетворяющее условию: для любых x, y k S

j(x + y) = j(x) * j(y).

Взаимно однозначное отображение обладает обратным к нему отображением, и если j есть изоморфизм S на T, то обратное отображение j-1 будет, как легко убедиться, изоморфизмом T на S. Полугруппы, для которых существует изоморфизм одной на другую, называются изоморфными.

Приведем несколько примеров изоморфных полугрупп. Аддитивная группа R изоморфна мультипликативной группе положительных действительных чисел. Изоморфизмом первой на вторую будет, например, отображение, сопоставляющее любому числу x k R его логарифм lg x. Аддитивная полугруппа натуральных чисел изоморфна аддитивной полугруппе четных натуральных чисел, изоморфизм первой на вторую сопоставляет любому n число 2n (заметим, что этим полугруппам изоморфна свободная полугруппа над алфавитом из одной буквы). А вот мультипликативные полугруппы всех натуральных чисел и всех четных натуральных чисел неизоморфны: в первой есть нейтральный элемент (единица), а во второй такового нет; между тем легко установить, что при изоморфизме нейтральный элемент обязан переходить в нейтральный. Заинтересованному читателю можно предложить следующие задачи, в принципе несложные, но потребующие для своего решения определенной смекалки: будут ли изоморфны: а) мультипликативные полугруппы всех натуральных чисел и всех нечетных натуральных чисел; б) две полугруппы, указанные в п. 1.4; в) полугруппы, указанные в п. 1.5, для случая, когда M = N; г) полугруппы, указанные в п. 1.5, для случая, когда M = Z; д) полугруппы, указанные в п. 1.7, для случая одного и того же множества M.

Вот три изоморфные полугруппы: группа поворотов квадрата вокруг его центра; группа, состоящая из преобразований

(о двухстрочечной записи преобразований см., например, [3]); мультипликативная группа, состоящая из комплексных чисел 1, i, -1, - i.

Любознательный читатель без труда найдет соответствующие изоморфизмы. Мультипликативная двухэлементная числовая полугруппа {0, 1} изоморфна полугруппе преобразований

Мультипликативная числовая полугруппа {1, -1}, являющаяся, очевидно, группой, изоморфна полугруппе преобразований

Двухэлементная полугруппа левых нулей (см. пример (а) в п. 1.12), состоящая из символов a и b, изоморфна полугруппе преобразований

В примерах, приведенных в предыдущем абзаце, фигурировали полугруппы, состоящие из элементов разной природы (поворотов фигуры, чисел, просто символов) и изоморфные полугруппам, состоящим из преобразований. Эти примеры являются иллюстрацией принципиального общего факта: любая полугруппа обладает таким изоморфизмом. Другими словами, справедливо следующее утверждение, подчеркивающее определенную "универсальность" полугрупп преобразований.

Теорема 1. Любая полугруппа изоморфна некоторой полугруппе преобразований.

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

Итак, пусть S - произвольная полугруппа. Будем считать, что она мультипликативная. Нужно указать такое множество X, что в полной полугруппе преобразований T (X ) найдется подполугруппа, изоморфная полугруппе S. В качестве X возьмем множество, полученное из S присоединением символа 1, не принадлежащего S. Распространим умножение в S на множество X, для чего надо определить произведения a " 1 и 1 " a для любого a k S, а также произведение 1 " 1. Положим

a " 1 = 1 " a = a, 1 " 1 = 1.

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

Теперь каждому a k S поставим в соответствие преобразование fa множества X, заданное условием: для любого x k X

fa(x) = ax

(точку как знак умножения будем преимущественно опускать). Ясно, что fa действительно является преобразованием X: ведь, согласно определению умножения на X, мы имеем ax k S и, значит, ax k X. Множество всех таких преобразований fa обозначим через F. Установим сейчас, что F есть подполугруппа в T (X ), изоморфная S, тем самым теорема будет доказана.

F - подмножество в T (X ), и нужно убедиться, что оно замкнуто относительно умножения, то есть для любых fa , fb k F найдется такой элемент c k S, что fa fb = fc . Пользуясь определением преобразований, составляющих F (формула (2)) и определением умножения преобразований (формула (1)), а также ассоциативностью умножения в X, получаем для любого x k X последовательно fa fb(x) = fa(fb(x)) = a(bx) = = (ab)x = fab(x). Мы видим, что в качестве требуемого элемента c можно взять ab.

Теперь убедимся, что отображение j, сопоставляющее каждому элементу a k S преобразование fa , будет искомым изоморфизмом S на F. По определению, j отображает S на F, надо проверить, что j взаимно однозначно, то есть из того, что j(a) = j(b), следует a = b. Так как j(a) = fa и j(b) = fb , условие j(a) = j(b) означает, что fa = fb , а это, в свою очередь, означает, что для любого x k X fa(x) = fb(x). В частности, fa(1) = fb(1) (вот где понадобилась единица!), то есть a " 1 = b " 1. Но a " 1 = a, b " 1 = b, значит, a = b.

Осталось убедиться, что для любых a, b k S

j(ab) = j(a)j(b),

то есть для любого x k X

j(ab)(x) = j(a)j(b)(x).

Сделаем это цепочкой равенств, пользуясь соответствующими определениями и ассоциативностью умножения:

j(ab)(x) = fab(x) = (ab)x = a(bx) =

= fa(fb(x)) = fa fb(x) = j(a)j(b)(x).

Теорема доказана.

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

Проиллюстрируем сейчас подобную классификацию на простом (с точки зрения алгебраиста-исследователя) примере двухэлементных полугрупп, перечислив все такие попарно неизоморфные полугруппы. В каких терминах осуществить указанное перечисление? Это можно сделать разными способами. В частности, здесь применим известный способ задания бинарной операции на конечном множестве при помощи так называемой таблицы умножения. Мы сделаем это воспользовавшись некоторыми полугруппами, уже рассмотренными в статье. А именно, зафиксируем двухэлементное множество M, состоящее из символов a1 и a2 . Через M1-M4 обозначим полугруппы, полученные из M заданием операций, описанных соответственно в примерах (а)-(г) из п. 1.12 (при этом в полугруппе M3 для определенности считаем фиксированным элемент a1), а через M5 обозначим полугруппу, полученную из M заданием следующей операции: a1 + a1 = a2 + a2 = a1 , a1 + a2 = = a2 + a1 = a2 .

Теорема 2. Любая двухэлементная полугруппа изоморфна одной из только что введенных полугрупп M1-M5 .

Легко убедиться, что полугруппы M1-M5 попарно неизоморфны. Таким образом, с точностью до изоморфизма имеется всего пять различных двухэлементных полугрупп. Одна из них, а именно M5 , есть группа.

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

Число элементов конечной полугруппы называется ее порядком. С ростом n число всех попарно неизоморфных полугрупп порядка n растет очень быстро. Представление об этом росте дает следующая таблица, где мы отмечаем и число неизоморфных групп данного порядка:

Читатель заметил, что число групп порядка n немонотонно зависит от n. Это объясняется спецификой групп, в силу которой свойства конечной группы весьма существенно зависят от того, каково разложение порядка группы на простые множители. В частности, для любого простого числа p существует с точностью до изоморфизма лишь одна группа порядка p. Можно сказать, краеугольным камнем теории конечных групп служит теорема Лагранжа, согласно которой порядок любой подгруппы в конечной группе является делителем порядка группы. Для произвольных конечных полугрупп ничего похожего нет: для любого n существуют полугруппы порядка n, имеющие подполугруппы любого меньшего порядка; таковы, например, полугруппы левых (или правых) нулей.

ЗАКЛЮЧЕНИЕ

Теория полугрупп - детище XX века. Понятие полугруппы и соответствующий термин возникли в начале века, а систематические исследования полугрупп начались в конце 20-х годов. К 60-м годам теория полугрупп сформировалась в динамично развивающуюся область алгебры с богатой проблематикой и разнообразными приложениями. В те годы появились и первые монографии, целиком посвященные алгебраической теории полугрупп [6, 7]. Представление о современном состоянии этой теории можно получить по главе IV справочника "Общая алгебра", см. [8], где содержатся детальные сведения по основным разделам теории и приводится достаточно полная (на конец 80-х годов) библиография основных источников - книг и обзорных статей. Некоторым первоначальным сведениям о полугруппах посвящен один из параграфов учебного пособия [9]. Полугруппам (в частности, их связям с автоматами) уделено внимание и в популярной книге [10].

ЛИТЕРАТУРА

1. Хилле Э., Филлипс Р. Функциональный анализ и полугруппы. М.: ИЛ, 1962. 830 с.

2. Шеврин Л.Н. Тождества в алгебре // Соросовский Образовательный Журнал. 1996. ╧ 7. С. 111-118.

3. Ольшанский А.Ю. Умножение симметрий и преобразований // Там же. ╧ 5. С. 115-120.

4. Лаллеман Ж. Полугруппы и комбинаторные приложения. М.: Мир, 1985. 440 с.

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

6. Ляпин Е.С. Полугруппы. М.: Физматгиз, 1960. 592 с.

7. Клиффорд А., Престон Г. Алгебраическая теория полугрупп. М.: Мир, 1972. Т. 1. 286 с.; Т. 2. 422 с.

8. Шеврин Л.Н. Полугруппы // Общая алгебра / Под ред. Л.А. Скорнякова. М.: Наука, 1991. Т. 2. С. 11-191.

9. Скорняков Л.А. Элементы алгебры. М.: Наука, 1986. 240 с.

10. Фрид Э. Элементарное введение в абстрактную алгебру. М.: Мир, 1979. 262 с.

* * *

Лев Наумович Шеврин, доктор физико-математических наук, профессор, зав. кафедрой алгебры и дискретной математики Уральского государственного университета, председатель правления Уральского математического общества, заслуженный деятель науки Российской Федерации, академик Академии гуманитарных наук, член редколлегий журнала "Известия вузов. Математика" и международного журнала "Semigroup Forum". Лауреат Международной премии по образованию им. Хосе Васконселоса Всемирного совета по культуре. Автор более 160 работ, в том числе нескольких обзорных статей, трех монографий, двух школьных учебников, трех научно-художественных книг по математике для маленьких детей.