Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров, страница 8

Заметим, что можно было бы рассматривать алгебры (д, р) н (д, ф), где в таблице ф все Ь~ заменены на а~ (с тем же индексом), Тогда отображение Г: аг-~ам а~ ип аз-+ам а4- а4 также является изоморфизмом. 5. Булевы алгебры (см. пример 2.1,в), образованные двумя различными множествами У, У' одинаковой мощности, изоморфны: операции у них просто одинаковы, а отображением Г может служить любое взаимно одиозначное соответствие между У и У'. Отношение изоморфизма является отношением эквивалентности на множестве алгебр, Рефлексивность его очевидна, симметричность следует из существования обратного изоморфизма, а транзитивность устанавливается следующим образом: если Г~ — изоморфизм А на В, Гэ — изоморфизм В на С,то изоморфизмом А на С будет композиция Г~ и Гъ Классами эквивалентности в разбиении по отношению изоморфизма являются классы изоморфных между собой алгебр.

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

Распространенное в математике выражение чрассматривать объекты с точностью до изоморфизма» означает, что рассматриваются только те свойства объектов, которые сохраняются при изоморфизме, т. е. являются общими для всех изоморфных объектов. В частности, изоморфизм сохраняет ассоциативность, коммутативность н дястрибутивность., 2.2. ПОЛУГРУППЪ|, ГРУППЫ, РЕШЕТКИ Полугруппы, Полугриппой называется алгебра с одной ассоциативной бинарной операцией. Эта операция обычно называется умножением, поэтому результат ее применения к элементам а и Ь записывается как а Ь или аЬ. Такая запись называется мультипликативной. В частности, аа принято записывать как а', пап как а' и т.д. В общем случае аЬчьЬа. Если же умножение коммутативно, то полугруппа называется коммутативной, или абелевой. Если полугруппа содержит такой элемент е, что для любого а аег на=а, то е называется единицей.

Полугруппа с единицей называется моноидохс Единица в полугруппе всегда единственна. Действительно, если есть две единицы е, и ем то е|ез=е| и е |ет = ем следовательно, е1 = еь Композиция отображений является ассоциативной операцией. Поэтому всякое множество преобразований (отображений некоторого множества в себя), замкнутое относительно композиции, является полутрупной. рассмотрим пример. Пусть на множестве (1, 2, 3) заданы преобразования а=~ ~) и р =~ ), Их произведения имеют вид ар=-~ ) и ра= ~ ), т.е. несовпадаютса и р. Поэтому множество (а, р) не замкнуто относительно композиции и не образует полугруппы, Однако если к нему добавить преобразования Т=йт=~ ),6=ар и ~=йа то можно |1 2 3| ~2 2 3~' убедиться, что полученное множество Г=(а, р, т,б, Ц вместе с операцией композиции образует полугруцпу. Таблица Кали этой полугруппы имеет вид табл.

2.4. Если же к Г добавить тож- Таблица 2М дествениое отображение е = 112 31 31т получим полугруппу с единицей. Теорема 2.1. Любая полу- группа с единицей изоморфна некоторой полугруппе преобразований. Действительно, пусть задана полугруппа с множеством М=(е, аь аз...). Каждому элементу а~ полугруппы поставим в соответствие преобразование )~ множества М следующим образом: )~ (х) = ха| для всех х ~в М. Тогда произ- ведению ша; будет соответствовать преобразование ~ц(х) = =ха а,=)~(х)а,=),ф(х)), т.е. композиция преобразований 1'; и (ь следовательно, Условие (2.1) гомомоРфизма выполнено.

Кроме того, разным элементам соответствуют разные отображения, так как );(е) =а„~у(е) =аь и, следовательно, ~гэь)ь Таким образом, соответствие а;~(,(х) является изоморфизмом. Если любой элемент полугруппы Р= (М; о) можно представить как произведение некоторого числа элементов множества М,с:М, то множество Мэ называется порождающим множеством или системой образующих полугруппы Р, а его элементы называются образдюн1ими.

В нашем примере образующими являются а и б, так как у=йз, 6= =ай, (,=()а. В полугруппе (Ж; а) порождающим множеством служит бесконечное множество простых чисел. Если полугруппа имеет только одну образующую,, то все элементы являются степенями этой образующей. Такая полу- группа называется циклической. Циклической полугруппой является, например, полугруппа (У; +), так как все натуральные числа — это суммы некоторого количества единиц. Пусть полугруппа Р имеет конечное множество образующих (аь..., а„), Если обозначения операции опустить (как это обычно делается для умножения), то все элементы Р можно рассматривать как слова в алфавите (аь ..., а„). Некоторые различные слова могут оказаться равными как элементы. В нашем примере полугруппы преобразований выполняются, например, равенства ()з=й, ~я=ай', В коммутативной полугруппе для любых элементов а, Ь выполняются равенства аЬ=Ьа.

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

Элементы заданной так полугруппы — это слова в алфавите образующих, причем некоторые слова равны (т. е, задают один н тот же элемент) в силу определяющих соотношений. Отношение равенства слов является отношением эквивалентности. Из любого слова, используя определяющие соотношения, легко можно получить различные эквивалентные ему слова. Намного сложнее проблема: для двух данных слов выяснить, можно ли получить одно из другого, используя определяющие соотношения.

Ее исследование оказало значительное влияние на теорию алгоритмов,' Более точная постановка этой проблемы будет рассмотрена в 5 б.4. ,Труппы. Группой называется полугруппа с единицей, в которой для каждого элемента а существует элемент а — ', называемый обратным к а н удовлетворяющий условию аа-'=а-'а=е. Число элементов группы называется порядком группы. Группа, в которой операция коммутативна, называется коммутатнвной, или абелсвоб. Группа, все элеме!тты которой являются степенями одного элемента а, называется циклической.

Циклическая группа всегда абелева. Для абелевых групп часто употребляется аддитивная записгн операция обозначается как сложение, а единица обозначается О. Пример 2.3. а. Множество рациональных чисел, не содержащее нуля, с операцией умножения является абелевой группой, Обратным к элементу а является элемент 1/а. б. Множество целых чисел с операцией сложения является абелевой циклической группой.

Роль единицы здесь играет О, обратным к элементу а является элемент — тк в. Множество невырождениых квадратных матриц порядка а (с отличным от О определителем) с операцией умножения является некоммутатнвной группой. г. Множество (О, 1, 2, 3, 41 с операцией «сложение по щод 5» — конечная абелева циклическая группа. Ее единицей является О. В этой группе 3 — '=2, 1 — ' =4, д. Алгебра (О; ») из примера 2.1, е, где 0 — множество поворотов квадрата, а ~ — их композиция, является циклической группой: у= р',б=р', а=б'. Единицей в ней служит тождественное отображение а (поворот на нулевой угол); обратным к данному повороту служит поворот, дополняющий его до 2ги )3 '=6; у '=у, 6 '-13. е. Рассмотрим множество 5 всех взаимно однозначных преобразований конечного множества М в себя.

Такие преобразования называются подстановками, Алгебра Хм = =(5м,' ~1 представляет собой группу, которая называется симметрической. Поскольку число подстаповок равно числу перестановок в списке элементов М, то порядок Хм равен !М!1 Симметричная группа не является абелевой. Пусть, например, М=(1, 2, 3, 41, а= ~ ), 3 = ~ ). Тогда г! 2 3 4! ~! 2 3 4 ~2 4 3 1)' 1,4 ! 2 3 ' р (1 2 3 4) р ~1 2 3 4) — ~ (! 2 3 4) р В любой конечной группе ее операция (умножение) может быть задана таблицей Кэли, Для групп таблица Кэли имеет важную особенность: любой ее столбец содержит все элементы группы.

Действительно, если столбец а~ не содержит какого-нибудь элемента, то некоторый другой элемент а~ в нем должен встретиться дважды, скажем, в /г-й и (-й строках. Но тогда аьа;=аьа,а, а; и, следовательно, аьш а~аь Умножая обе части равенства на ас, получаем аь*=аь что неверно. Таким образом, ~-й столбец Кэли, т.

е. умножение на аь является подстановкой на множестве элементов группы. Проверив, что это соответствие является изоморфизмом (аналогичную проверку мы делали для полугрупп преобразований), получаем теорему Кэлн. Теорема 2.2. Любая конечная группа изоморфна группе подстановок на множестве ее элементов. П Из сравнения теорем о связи полугрупп с преобразованиями и групп с подстановками видно, что группа — это полугруппа взаимно однозначных преобразований, причем именно взаимная однозначность гарантирует наличие обратного преобразования.

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