ДИСКРЕТНАЯ МАТЕМАТИКА

Лекция 2. Основные алгебраические структуры

1. Алгебры

Пусть Х - непустое множество. Внутренней операцией  множества Х называется функция :ХⁿХ, где число n – арность операции. Внутренняя операция арности 2 называется бинарной, арности 1 - унарной. Бинарную операцию  обозначают некоторым символом (+, , _* и др.) и вместо (x,y) пишут, например, x_*y или просто xy.

Одноосновной алгеброй или просто алгеброй называется множество (обозначим его Х) с системой заданных на нем операций.

Внутренняя бинарная операция _* (далее для краткости – просто операция), заданная на алгебре с основным множеством Х, называется:

1) ассоциативной, если для любых x,y,zХ

x_*(y_*z)=(x_*y)_*z;

2) коммутативной, если для любых x,yХ

x_*y=y_*x.

2. Группоиды, полугруппы и группы

Множество G с одной внутренней бинарной операцией _* называется группоидом, обозначается (G;_*). Элемент еG называется нейтральным или единичным относительно операции _*, если g_*е=е_*g=g для любого элемента gG.

Таблицей Кэли группоида (G;_*), где G={g₁,…,g_n}, называют квадратную таблицу, у которой строки и столбцы "занумерованы" элементами g₁,…,g_n и на пересечении строки g_i и столбца g_j записан результат операции g_i*g_j, i,j{1,…,n}.

Подмножество G группоида (G;_*) называется подгруппоидом, если оно замкнуто относительно операции _*, то есть если g,gG, то и g_*gG.

Элементы g и g группоида G коммутируют (или перестановочны), если g_*g=g_*g. Группоид (G;_*) называется коммутативным, если операция _* на G коммутативна.

В группоиде имеется не более одного единичного элемента е. Действительно, если е – другая единица группоида, то е=е_*е=е.

Группоид (G;_*) с заданной на нём ассоциативной операцией _* называется полугруппой.

Идемпотентом полугруппы G называется ее элемент i со свойством: i_*i=i. Множество всех идемпотентов полугруппы G обозначим E(G). Полугруппа G называется унипотентной, если E(G)=1.

Полугруппу с единичным элементом называют моноидом (или полугруппой с единицей). Моноидом является, например, N - множество натуральных чисел относительно умножения.

Элемент g моноида G с единицей е называется обратимым, если найдётся элемент gG, для которого g_*g=g_*g=е, такие элементы g и g называются взаимно обратными.

Если в моноиде G для элемента g имеется обратный элемент g, то он единственный (обозначается g^-1). В самом деле, если g - другой элемент обратный к g, то, используя ассоциативность операции, имеем:

g=g_*е=g_*(g_*g)=(g_*g)_*g=е_*g=g.

Если в моноиде G для элементов g и h имеются обратные элементы g^-1 и h^-1, то обратным к элементу g_*h является элемент h^-1_*g^-1.

Группой называется моноид G, все элементы которого обратимы. Иначе, множество G – группа с внутренней бинарной ассоциативной операцией _*, относительно которой в G имеется единица и для каждого элемента имеется обратный. Группу можно рассматривать как унипотентную полугруппу. Действительно, если в группе i_*i=i, то умножив обе части на i^-1, получаем i=е.

Подполугруппой полугруппы G называется ее подмножество G, являющееся полугруппой, обозначается GG. Подгруппой полугруппы или группы G называется ее подмножество G, являющееся группой, обозначается GG.

Подполугруппа (подгруппа) G называется собственной, если G - собственное подмножество полугруппы (группы) G.

Операция _* полугруппы G индуцирует операцию на подмножествах X,Y полугруппы G:

XY=X_*Y={xy: xX, yY}.

Так как эта операция внутренняя на 2^G, то тем самым определена полугруппа 2^G, при этом если G - моноид с единицей e, то 2^G - моноид с единицей {e}.

Множество всех элементов моноида G, имеющих обратные элементы, образует максимальную подгруппу моноида G, называемую группой обратимых элементов моноида G (обозначается I_G). Если G – группа, то I_G=G. Если G – моноид, то единица подгруппы не обязана совпадать с единицей моноида.

Группу с коммутативной операцией называют коммутативной или абелевой. В зависимости от полугрупповой (групповой) операции, сложения или умножения, полугруппу (группу) называют аддитивной или мультипликативной. Порядок конечной полугруппы или группы G (то есть число элементов в G) обозначается символом G или ordG.

Пример 1. Группы:

а) множество R действительных чисел относительно сложения и множество R\{0} относительно умножения;

б) множество Z целых чисел относительно сложения;

в) множество Q рациональных чисел относительно сложения и множество Q\{0} относительно умножения. w

Пример 2. Полугруппы, не являющиеся группами:

а) множество N натуральных чисел относительно умножения;

б) множество Z целых чисел относительно умножения. w