2. Полугруппы и группы, аксиоматика. Циклическая группа.

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

Полугруппой называется алгебра с одной бинарной операцией

М; *.

Здесь для операции * установлена только одна аксиома - аксиома ассоциативности А₁.

А₁: a*(b*c) = (a*b)*c.

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

Абелевой полугруппой называется алгебра такого же вида, но уже с двумя аксиомами: А₁ (ассоциативности) и А₂ (коммутативности)

А₂: a*b = b*a.

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

Моноидом или полугруппой с единицей, называется полугруппа, для которой наряду с аксиомой ассоциативности А₁ принята аксиома А'₃ о существовании нейтрального элемента е, такого, что

А₃: е*а = а.

Такой нейтральный элемент называется левой единицей. Можно эту аксиому выразить иначе, как А"₃: а*е = а. Тогда нейтральный элемент должен называться правой единицей. Если же операция * коммутативна, т.е. кроме аксиом А₁ и А₃ принята аксиома А₂, то нейтральный элемент будет называться просто единицей и е*а = а*е = а.

Называя нейтральный элемент единицей, мы заметно сближаем полугрупповую операцию * с обычным умножением, ведь единица играет роль нейтрального элемента в обычном умножении. Если мы хотим свести полугрупповую операцию к сложению, то должны называть нейтральный элемент нулем, соответственно левым, правым или просто нулем: е+а = а+е = а. Сводя операцию * к умножению мы получаем мультипликативную полугруппу, а к сложению - аддитивную.

Некоторые полугруппы можно получить неоднократным применением операции * к элементам некоторого подмножества М₀М. В этом случае подмножество М₀ называется семейством образующих полугруппы, а элементы: аМ₀ называются образующими. В дискретной математике роль образующих играют символы или буквы некоторого алфавита, который по определению должен быть подмножеством носителя М.

Алфавит чаще всего определяется как конечное множество, тогда как носитель бывает бесконечным.

Иногда семейство образующих состоит из одного единственного элемента, а все остальные элементы носителя М получаются многократным применением операции *. В этом случае полугруппа называется циклической, а её элементы называются степенями образующей а₀. Примером циклической группы является множество натуральных чисел, определенное, как N; *, где образующая а₀ = 1, а операция * сведена к инкременту (прибавлению единиц).

Группой называется алгебра М; * , у которой для операции * приняты аксиомы А₁, А'₃ или А"₃ и дополнительно - аксиома А₄ о существовании обратного элемента а^-1, такого, что

А'₄: а^-1 *а = е; или А"₄: a*a^-1 = e.

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

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