Дискретно-непрерывная математика (стр. 18 )

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

1.13. Основные определения полугрупп и групп

Полугруппы. Напомним некоторые определения. Полугруппой называется алгебра с одной ассоциативной бинарной операцией. Эта операция обычно называется умножением, поэтому результат ее применение к элементам а и b записывается как а∙b или ab. Такая запись называется мультипликативной. В частности, аа принято записывать как а2, ааа как а3 и т. д. В общем случае ab≠bа. Если же умножение коммутативно, то полугруппа называется коммутативной, или абелевой. Если полугруппа содержит такой элемент е, что для любого а ае=еа=а, то е называется единицей. Полугруппа с единицей называется моноидом. Единица в полугруппе всегда единственна. Действительно, если есть две единицы e1 и е2, то e1e2 = е1 и e1e2 = е2 итак, e1 = е2.

Композиция отображений является ассоциативной операцией. Поэтому всякое множество преобразований (отображений некоторого множества у себя), замкнутое относительно композиции, является полугруппой. Рассмотрим пример. Пусть на множестве {1, 2, 3} заданы преобразования

и

Их произведения имеют вид

и

Т. е., не совпадают с α и β. Поэтому множество { α, β } не замкнуто относительно композиции и не образует полугруппы. Однако если к нему прибавить преобразования

, и ,

то можно убедиться, что получено множество Г={ α, β, γ, δ, ζ} вместе с операцией композиции образует полугруппу. Таблица Кели этой полугруппы имеет вид:

Таблица 1.15

Если же к Г прибавить тождественное отображение

,

получим полугруппу с единицей.

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

Действительно, пусть задана полугруппа с множеством М ={е, а1, а2 ...}. Каждому элементу аі полугруппы поставим в соответствие преобразования fi множества М следующим образом: fi(х)=xai для всех

х М. Тогда произведению aiаj будет соответствовать преобразование

fij (х)=xaiаj= fi(х)аj= fj (fi (x)),

т. е. композиция преобразований аj и fj; следовательно, условие (1.74) гомоморфизма выполнено. Кроме того, разным элементам М соответствуют разные отображения, так как fj(е)=аі, fj(е)=аj и, следовательно, fi≠fj. Таким образом, соответствие ai →fi(х) является изоморфизмом.

Если любой элемент полугруппы Р(М, ) можно представить как произведение некоторого числа элементов множества М0M, то множество М0 называется порождающим множеством, или системой, образующих полугруппы Р, а его элементы называются образующими. В нашем примере образующими являются α и β, так как γ = β2, δ = αβ, ζ= βα. В полугруппе (N; •) порождающим множеством, служит бесконечное множество простых чисел. Если полугруппа имеет только одну образующую, то все элементы являются степенями этой образующей. Такая полугруппа называется циклической. Циклической полугруппой является, например, полугруппа (N; +), так как все натуральные числа — это суммы некоторого количества единиц. Пусть полугруппа Р имеет конечное множество образующих {а1, ..., ап}. Если обозначения операции опустить (как это обычно делается для умножения), то все элементы Р можно рассматривать как слова в алфавите {al,...,ап}. Некоторые различные слова могут оказаться равными как элементы. В нашем примере полугруппы преобразований выполняются, например, равенства β3=β , βα=αβ2. В коммутативной полугруппе для любых элементов а, b выполняются равенства ab=bа. Такие равенства называются определяющими соотношениями. Если же в полугруппе нет определяющих соотношений, т. е. любые два различных слова являются различными элементами полугруппы, то полугруппа называется свободной.

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

Группы. Группой называется полугруппа с единицей, в которой для каждого элемента а существует элемент а-1, который называют обратным к а и удовлетворяющий условию аа-1=а-1а=е. Число элементов группы называется порядком группы. Группа, в которой операция коммутативна, называется коммутативной, или абелевой. Группа, все элементы которой явдяются степенями одного элемента а, называется циклической. Циклическая группа всегда абелева. Для абелевых групп часто употребляется аддитивная запись: операция обозначается как сложение, а единица обозначается 0.

В любой конечной группе ее операция (умножение) может быть задана таблицей Кели. Для групп таблица Кели имеет важную особенность: любой ее столбец содержит все элементы группы. Действительно, если столбец аі не содержит какого-нибудь элемента, то некоторый другой элемент аj в нем должен встретиться дважды, скажем, в k-й и l-й строках. Но тогда akai=аj, аlаi=аj и, следовательно, akai=аlаi. Умножая обе части равенства на аi-1, получаем ak=аl, что неверно. Таким образом, i-й столбец таблицы Кели, т. е. умножение на аі, является подстановкой на множестве элементов группы. Проверив, что это соответствие является изоморфизмом (аналогичную проверку мы делали для полугрупп преобразований), получаем теорему Кели.

Теорема 2. Любая конечная группа изоморфна группе подстановок на множестве ее элементов.

Из сравнения теорем о связи полугрупп с преобразованиями и групп с подстановками видно, что группа — это полугруппа взаимнооднозначных преобразований, причем именно взаимная однозначность гарантирует наличие обратного преобразования. Можно сказать, что в группе при любом числе умножений не теряется информация об исходном элементе: если известно, на что умножали, всегда можно узнать, чтò умножали. Для полугруппы это верно не всегда. Используя терминологию дискретных систем (например, конечных автоматов, о которых будет идти речь в пособии „Дискретная математика. Автоматы”), то же самое можно сказать следующим образом. Пусть имеется дискретная система с конечным числом состояний S = {s1, ..., sn}, на вход которой может быть подано входное воздействие из множества {х1 ..., хт}. Всякое входное воздействие однозначно переводит состояние системы в некоторое другое состояние и, следовательно, является преобразованием множества S. Последовательности воздействие — это композиции преобразований; следовательно, множество всех последовательностей является полугруппой с образующими {х1, .,., хт}. Если такая полугруппа оказывается группой, то это означает, что по любой входной последовательности и заключительному состоянию системы можно однозначно определить начальное состояние системы.

1.14. Алгебраичные системы

1.14.1. Законы композиции

1. Композиция объектов. В математике и ее приложениях большое значение имеют отношение, которые ставят в соответствие пары каких-либо объектов (а, b) третий объект с. Примерами таких отношений являются действия над числами. В общем случае отношение может представлять собой некоторую операцию не только между числами, но и между объектами любой природы. При этом запись а b=с, или a b=c, означает, что а в композиции с b дает с. Символ (или ) обозначает операцию, объекты а и b называют операндами, а объект с - результатом операции или композицией объектов а и b.