ГЛАВА 8. ЭЛЕМЕНТЫ ОБЩЕЙ АЛГЕБРЫ

Алгебраические операции

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

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

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

Среди известных бинарных операций, производимых не над числами, отметим векторное умножение векторов пространства, умножение квадратных матриц порядка п, композицию отображений множества X всебя, теоретико-множественное объединение и пересечение множеств.

Как видим, фактическое задание алгебраической операции на множестве может быть произведено различными методами. Возможно также непосредственное перечисление всех результатов операции для конечных множеств. Его удобно описать с помощью так называемой таблицы Кэли. Слева и сверху квадратной таблицы выписывают все элементы множества. На пересечении строки, соответствующей элементу а, и столбца, соответствующего элементу b, записывают результат операции над а и b. Из двух приведенных таблиц Кэли
(табл. 8.1. и 8.2.) вторая — таблица для операции конъюнкции на множестве {И, Л}.

Таблица 8.1.

Таблица 8.2.

Будем употреблять следующую терминологию и символику: операцию называть умножением, а результат применения операции к элементам а и b — произведением ab. Это мультипликативная терминология. Иногда естественнее и удобнее использовать аддитивную терминологию и символику: операцию называть сложением, а результат ее выполнения — суммой а +b элементов а и b.

Если для любых элементов а и b множества М справедливо равенство ab = ba, то операцию называют коммутативной. Коммутативны, например, сложение и умножение чисел, сложение матриц одного порядка и т. д. Некоммутативными операциями являются векторное произведение векторов, произведение матриц порядка п при
n ≥2 и др.

Если для любых элементов а, b, с множества М справедливо равенство а(bс) = (ab)c, то операцию называют ассоциативной. Ассоциативны, например, сложение и умножение целых чисел, умножение матриц, композиция отображений, а также операции, определенные таблицами Кэли. Неассоциативной операцией является векторное умножение векторов пространства.

В ряде случаев множество М, на котором определена алгебраическая операция, обладает единичным элементом, т.е. таким элементом е, что ае = еа = а для всех а из М. Единичный элемент единственен, так как если существует еще один элемент е' с этим же свойством, то ее' = е и ее' = е', откуда е = е'. При аддитивной записи единичный элемент называется нулевым и обозначается 0.

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

Если операция ассоциативна, то можно однозначно говорить о произведении любого конечного числа элементов, взятых в определенном порядке. Пусть дана упорядоченная система из п элементов множества М: а₁, а₂,..., а_n, в которой некоторым образом расставлены скобки, указывающие на порядок выполнения операции.

Теорема. Если операция, определенная на М, ассоциативна, то результат ее последовательного применения к п элементам множества не зависит от расстановки скобок.

Доказательство проведем индукцией по числу множителей п. Для п = 3 утверждение теоремы следует из закона ассоциативности. Докажем это для п множителей, предполагая, что для меньшего числа множителей утверждение верно. В этом случае достаточно доказать, что для любых k и l, где 1 ≤ k, l ≤ n-1, (a₁...a_k)(a_k+1...a_n) = (a₁...a_l)(a_l+1...a_n), так как внутри скобок расстановка их несущественна по индуктивному предположению. Для этого покажем, что обе части равенства совпадают с произведением элементов a₁,...,a_n, взятых в следующем фиксированном порядке: (... ((a₁a₂) a₃)... a_n-1) a_n (это произведение называется левонормированным произведением элементов a₁,..., a_n). Действительно, при k = п-1 имеем (a₁... a_n-1) a_n = (... (a₁a₂) ... a_n-1) a_n, т.е. левонормиро-ванное произведение. При k < п-1 ввиду ассоциативности получаем
(а₁... a_k) (a_k+1... a_n) = (a₁... a_k)((а_k+1 … a_n-1) a_n) = ((a₁...a_k)(a_k+1...a_n-1)) a_n = (...((... (a₁a₂)... a_k) a_k+1)... a_n-1) a_n, т.е. снова имеем левонормированное произведение. К такому же виду приводится и правая часть доказываемого равенства.

В силу теоремы при записи и вычислении произведения а_1…a_n скобки не ставят, а следят только за порядком множителей, и то лишь в случае, если операция некоммутативна. В частности, при a₁ = a₂ =... = =a_n = а произведение aa … a обозначают символом aⁿ и называют n-й степенью элемента. Если множество М обладает единичным элементом, то полагают а° = е.

Из теоремы вытекают соотношения

a^maⁿ = a^m+n; (a^m) ⁿ = a^nm, m, nЄN.

В аддитивной символике степеням соответствуют кратные
na = a + a + ...+ а и выполняются соотношения

та + па = (т+п)а; п(та)= (пт)а, т, nЄN.

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

Полугруппы и моноиды

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

Примеры

1. Пусть X — произвольное множество, М(Х) —множество всех отображений X в себя. Тогда относительно операции композиции отображений М (X) — моноид, он некоммутативный. Обозначим его М(Х, О, е_х).

2. Множество квадратных матриц порядка п относительно умножения матриц — некоммутативный моноид с единичным элементом — единичной матрицей, а относительно сложения матриц — коммутативный моноид с единичным элементом — нулевой матрицей. Обозначим их соответственно (M_n(R),•,E), (M_n(R),+,0).

3. Множество целых чисел — коммутативный моноид как относительно сложения, так и умножения. Обозначим их соответственно (Z, +, 0), (Z, •, 1). Множество целых чисел, делящихся на n(n>1),— коммутативная полугруппа без единицы относительно умножения. Обозначим ее (nZ, •).

4. Пусть A = {a₁,..., а_n}— конечное множество символов — алфавит. Конечная последовательность символов называется словом в алфавите А. На множестве П слов в алфавите А введем бинарную операцию—«приписывание», т.е. если ,то . Тогда П — полугруппа. Она называется свободной полугруппой, порожденной множеством А.

5. Множество {X₁, X₂, Х₃, Х₄} относительно операции, заданной таблицей Кэли (см. табл. 8.1.),— коммутативный моноид, единичный элемент которого Х₁.

Подмножество П' полугруппы П называется подполугруппой, если аbЄП' для всех а, bЄП'. В этом случае говорят также, что подмножество П' замкнуто относительно рассматриваемой операции. Очевидно, подполугруппа П' сама является полугруппой относительно операции в П. Если М — моноид и подмножество М' не только замкнуто относительно операции, но и содержит единичный элемент, то М' называется подмоноидом М.

Например, множество чисел, кратных п, — подполугруппа в полугруппе целых чисел относительно умножения (Z, •, 1) и подмоноид в (Z, +,0). В полугруппе П слов в алфавите А подмножество слов в алфавите А΄ А также подполугруппа.

Элемент а моноида М с единичным элементом е называется обратимым, если для некоторого элемента b выполняется равенство ab=ba=e. Элемент b называется обратным а и обозначается a^-1. Обратный элемент единственен. Действительно, если еще и ab'=b'a=e, то b'=eb^΄=(ba)b'=b(ab')=be=b.

Нетрудно видеть, что (а^-1)^-1=а. Кроме того, если а, b обратимы, то (аb)^-1 = b^-1a^-1, так как (ab) (b^-la^-1)=a(bb^-1)a^-1 = аеа^-1=аа^-1=е, и аналогично (b^-la^-1) (ab)=e, т. е. элемент ab тоже обратим.

Множество всех обратимых элементов моноида образует подмоноид, так как содержит единичный элемент и замкнуто относительно операции: если а и b обратимы, то b^-la^-1 — элемент, обратный ab.

Рассмотрим проблему тождества слов в полугруппах.

Пусть S={s_1,...., s_n} — подмножество элементов полугруппы П такое, что любой элемент из П может быть представлен как произведение элементов из S. Тогда множество S называется системой образующих полугруппы П. Например, для свободной полугруппы П, порожденной алфавитом A = {a₁,..., а_n}, само множество А является системой образующих; для полугруппы целых чисел относительно сложения (Z, +, 0) системой образующих является множество {-1, 1, 0}, а для полугруппы целых чисел относительно умножения (Z, •, 1) образующими являются все простые числа и единица.

Следует заметить, что далеко не все произведения элементов множества S будут различными элементами полугруппы П. В общем случае вопрос о равенстве таких произведений довольно сложен.

Будем рассматривать полугруппы, порожденные конечным множеством своих элементов. Они называются конечно-порожденными.

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

Каждая полугруппа П может быть задана образующими

a_1, a_2,…, a_n (8.2.1.)

(алфавит полугруппы) и определяющими соотношениями

A_i=B_i (i=1, 2,…) (8.2.2.)

где A_i и B_i — слова в алфавите (8.2.1.).

Элемент полугруппы, т.е., слово в алфавите (8.2.1), называют словом полугруппы П.

Элементарным преобразованием полугруппы П называется переход от слова вида XA_iY к слову XB_iY (или обратно), где X,Y, - произвольные слова полугруппы П, а A_i=B_i; — одно из определяющих соотношений (8.2.2).

Элементарные преобразования представляются в виде схем

X A_i Y→X B_i Y; X B_i Y→X A_i Y.

К схемам элементарных преобразований относятся также тавтологические переходы вида Х→Х. Графическое совпадение двух слов X и Y обозначают Х ō Y.

Соотношения (8.2.2.) определяют равенство слов в полугруппе П, которое связано с элементарными преобразованиями полугруппы П следующим образом. Два слова X и Y полугруппы П равны в П тогда и только тогда, когда можно указать последовательность элементарных преобразований полугруппы П

X ō X₀→X₁→...→X_i→X_i+1→…→X_k ō Y,

переводящую слово X в слово У.

Для свободной полугруппы с алфавитом (8.2.1.) множество определяющих соотношений пусто; два слова равны тогда и только тогда, когда они графически совпадают.

Полугруппу (Z, +, 0) целых чисел относительно сложения можно задать образующими {—1, 1, 0} и определяющими (в аддитивной записи) соотношениями:

1+(-1)=0; (-1) + 1=0.

Проблема тождества слов в полугруппе заключается в следующем: указать алгоритм, который по любым двум словам устанавливал бы, равны они в полугруппе П или нет. Доказано, что эта проблема алгоритмически неразрешима. Простым примером полугруппы с неразрешимой проблемой тождества слов является полугруппа с образующими а, b, с, d, e и определяющими соотношениями ас=са, ad=da, bс=сb, bd=db, еса=cе, edb=de, сса=ссае.

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: