Примеры 5

ОБОБЩЕННЫЙ ЗАКОН АССОЦИАТИВНОСТИ

п.1. Полугруппы и моноиды. Пусть А – непустое множество, на котором задана бинарная операция *.

ОПРЕДЕЛЕНИЕ 1. Бинарная операция * на множестве А называется ассоциативной, если выполняется условие

(" a, b, c Î A)[(a * b)* c = a *(b * c)]. (1)

В противном случае, то есть если в А найдется по крайней мере одна тройка элементов a, b, c такая, что (a * b) * c ¹ a * (b * c), то бинарная операция * называется не ассоциативной. В случае ассоциативности бинарной операции * можно писать a * b * c без скобок.

ОПРЕДЕЛЕНИЕ 2. Полугруппой называется алгебра À = (А; *) типа (2) с ассоциативной бинарной операцией *.

Подалгебра À ₁ = (А ₁; *) полугруппы À называется подполугруппой и обозначается так À ₁p À.

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

Примеры 1 – 4

1. Так как операции сложения и умножения на основных числовых множествах N, Z, Q, R, C ассоциативны, то алгебры

(N; +), (Z; +), (Q; +), (R; +), (C; +) –

аддитивные полугруппы, а алгебры

(N; ×), (Z; ×), (Q; ×), (R; ×), (C; ×) –

мультипликативные полугруппы.

2. Подполугруппы: (N; +) p (Z; +) p (Q; +) p (R; +) p (C; +); (N; ×) p (Z; ×) p (Q; ×) p (R; ×) p (C; ×).

3. Пусть U = { A, B, C, … } – совокупность множеств одинаковой природы, а È и Ç соответственно операции объединения и пересечения множеств из U. Тогда алгебры (U; È) и (U; Ç) являются полугруппами, так как выполняются условия

(" А, В, С Í U)[(A È B) È C = A È(B È C)],

(" A, B, C Í U)[(A Ç B) Ç C = A Ç (B Ç C)].

4. Алгебра (Z; -) не является полугруппой, так как вычитание целых чисел не ассоциативная операция.

Обозначим через е нейтральный элемент из множества А, на котором задана ассоциативная операция *. Для элемента е выполняется условие

(" а Î А)[ a * e = e * a = a ]. (2)

ОПРЕДЕЛЕНИЕ 3. Алгебра À = (А; *, е) типа (2,0) с ассоциативной бинарной операцией * называется моноидом.

Моноид – термин, используемый для сокращения словосочетания,,полугруппа с единицей“, от греческого слова mwnwx -,, один ”,,, единый ”,,, единственный ”.

Любая подалгебра À ₁ = (А ₁; *, е) моноида À называется подмоноидом и обозначается À ₁ p À. Подмоноид всегда является подполугруппой с нейтральным элементом.

Примеры 5 – 9

5. Полугруппа (N; +) не образует моноида, поскольку в множестве N нет элемента (числа), удовлетворяющего условию (2).

6. Полугруппа (N; ×) образует моноид, так как в N существует элемент (число), удовлетворяющий условию (2):

($1Î N) (" n Î N)[ n ×1 = 1× n = n ].

7. Алгебры (Z; +, 0), (Q; +, 0), (R; +, 0), (C; +, 0) – аддитивные моноиды, а алгебры (Z; ×, 1), (Q; ×, 1), (R; ×, 1), (C; ×, 1) – мультипликативные моноиды.

8. Подмоноиды: (Z; +, 0) p (Q; +, 0) p (R; +, 0) p (C; +, 0); (Z; ×, 1) p (Q; ×, 1) p (R; ×, 1) p (C; ×, 1).

9. Полугруппы (U; È) и (U; Ç) образуют моноиды, так как в универсальном множестве U существуют элементы (множества), удовлетворяющие условиям (2):

($ÆÍ U)(" A Í U)[ A È Æ = Æ È A = A ], e = Æ;

($ U Í U)(" A Í U)[ A Ç U = U Ç A = A ], e = U.

п.2. Обобщенный закон ассоциативности. Нам известна роль коммутативности бинарной операции * на множестве А: она дает возможность переставлять элементы из А, над которыми выполняется эта операция, и благодаря этому упрощать формулы и рассуждения. Выясним теперь значение ассоциативности бинарной операции * на множестве А. Заметим, что требования коммутативности и ассоциативности операции * независимы друг от друга.

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

Действительно, пусть на множестве А определена бинарная ассоциативная операция * и нам даны три произвольных элемента a, b, c из этого множества. Пока мы не знаем, что следует понимать под композицией трех элементов; ведь в определении операции говорится о композиции только двух элементов, взятых в определенном порядке. Таким образом, выражения вида a * b * c пока еще не определены. Однако, мы знаем, что означают выражения (а * b)* c и а *(b * c). Первое из этих выражений – это композиция элемента а * b и элемента с, второе – композиция элемента а и элемента b * c. В силу ассоциативности операции *, обе эти композиции равны одному и тому же элементу множества А. Этот элемент естественно принять за композицию a * b * c, записанную уже без скобок. Таким образом, равенство

a * b * c = (a * b) * c = a * (b * c) (3)

можно рассматривать как определение композиции а * b * c трех элементов а, b, c, взятых в том порядке, в котором они записаны.

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

Композицию четырех элементов a, b, c, d можно вычислить следующими пятью способами:

(а * b)*(c * d), a *[ b *(c * d)], a *[(b * c)* * d ], [ a *(b * c)]* d,[(a * b)* c ]* d.

Но применяя ассоциативность операции *, легко показать, что все эти пять произведений равны.

Действительно, например, считая с * d как один элемент, получи (а * b) (c * d) = a * [ b * (c * d)]. Аналогично имеем равенства: a * [ b * (c * d)] = a * [(b * c) * d ] = [ a * (b * c)]* d =

= [(a * b) * c ] * d.

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

Докажем справедливость следующей теоремы.

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

Доказательство. Будем доказывать эту теорему методом математической индукции по числу элементов n ³ 3.

1. Для n = 3 теорема верна. Поэтому будем считать, что n > 3.

2. Предположим, что теорема верна для любого натурального числа k такого, что 3 < k < n, т.е. что результат последовательного выполнения операции * над элементами a ₁, a ₂,…, a_k множества А определен однозначно. Аналогично правилу (3) этот результат назовем композицией элементов а ₁, a ₂,…, a_k и обозначим символом a ₁ * a ₂ *…* a_k.

3. Докажем, что в таком случае теорема верна и для любого натурального числа n.

a)Для этого прежде всего докажем, что для всякого натурального числа k < n справедливо равенство

(" a ₁, a ₂,…, a_k Î A)[(a ₁* a ₂*…* a_k)*(a_k ₊₁* a_k ₊₂*…* a_n) =

(4)

= (a ₁* a ₂*…* a_k * a_k ₊₁)*(a_k ₊₂ * a_k ₊₃ * …* a_n)].

Это действительно так. Композиции a ₁* a ₂*…* a_k и a_k ₊₁* a_k ₊₂*…* a_n, по предположению, однозначно определены. Обозначим через

а = a ₁* a ₂*…* a_k и c = a_k ₊₂* a_k ₊₃ *… * a_n.

Тогда

(a ₁ * a ₂ *…* a_k) * (a_k ₊₁ * a_k ₊₂ *…* a_n) = a * (a_k ₊₁ * c),

(a ₁ * a ₂ *…* a_k * a_k ₊₁) * (a_k ₊₂ * a_k ₊₃ *…* a_n) = (a * a_k ₊_!) * c.

В силу ассоциативности операции *, а *(а_k ₊₁ * c) = (a * a_k ₊₁) * c

и, следовательно, (a ₁ * a ₂ *…* a_k) * (a_k ₊₁ * a_k ₊₂ *…* a_n) = (a ₁ * a ₂ *…* a_k * a_k ₊₁)* (a_k ₊₂ * a_k ₊₃ *…* a_n).

b) Покажем, что из справедливости равенства (4) вытекает, что для любых натуральных чисел k и l, меньших n, справедливо равенство

(" a ₁, a ₂,…, a_n Î A)[(a ₁* a ₂*…* a_k)*(a_k ₊₁* a_k ₊₂*…* a_n) =

(5)

= (a ₁* a ₂*…* a_l)*(a_l ₊₁* a_l ₊₂ *…* a_n)].

Не теряя общности рассуждений, будем считать, что l > k. Пусть l = k+s. Тогда, в силу равенства (4), получаем (a ₁ * a ₂ *…* a_k) * (a_k ₊₁ * a_k *…* a_n) = (a ₁ * a ₂ *…* a_k * a_k ₊₁) *

* (a_k ₊₂ * a_k ₊₃ *…* a_n) = (a ₁ * a ₂ *…* a_k * a_k ₊₁ * a_k+ ₂) * (a_k ₊₃ * a_k ₊₄*…* a_n) =… = (a ₁ * a ₂ *…* a_k+s _-1) * (a_k+s * a_k+s ₊₁ *…* a_n) =

= (a ₁ * a ₂ *…* a_l) * (a_l ₊₁ * a_l+ ₂ *…* a_n).

Итак, (a ₁ * a ₂ *…* a_k) * (a_k+ ₁ * a_k+ ₂ *…* a_n) = (a ₁ * a ₂ *…* a_l) * (a_l ₊₁ * a_l+ ₂ *…* a_n).

c) Предположим теперь, что в системе элементов a ₁, a ₂,…, a_n двумя любыми различными способами расставлены скобки указывающие, в каком именно порядке следует последовательно выполнять операцию *. Докажем, что в обоих случаях результат выполнения * будет один и тот же. Действительно, если мы будем последовательно выполнять операцию * в том порядке, который указан расстановкой скобок первым способом, то последним шагом будет выполнение операции * над композициями

a ₁ * a ₂ *…* a_k и a_k ₊₁ * a_k ₊₂ *…* a_n (1 £ k £ n –1).

При выполнении операции * в том порядке, который указан расстановкой скобок вторым способом, последним шагом будет выполнение операции * над композициями a ₁ * a ₂*…* a_l и a_l ₊₁ * a_l ₊₂ *…* a_n (1 £ l £ n –1).

Но в силу равенства (5), (a ₁ * a ₂ *…* a_k) * (a_k ₊₁ * a_k ₊₂ *…* a_n) =

= (a ₁ * a ₂ *…* a_k * a_k ₊₁ *…* a_l) * (a_l ₊₁ * a_l ₊₂ *…* a_n). Таким образом, в обоих случаях будем иметь один и тот же результат. Поэтому, в силу принципа математической индукции, теорема верна для любого натурального числа n ³ 3.

т.д.

Результат последовательного выполнения бинарной операции * над элементами a ₁, a ₂,…, a_n, таким образом, определяется однозначно. Поэтому символом a ₁ * a ₂ *…* a_n (n ³ 3) обозначим композицию последовательности элементов a ₁, a ₂,…, a_n из множествпаА, определяемую индуктивно следующим образом

a ₁ * a ₂ *…* a_n _-1 * a_n = (a ₁ * a ₂ *…* a_n _-1) * a_n. (6)

Cогласно этому правилу для трех и четырех элементов из А имеем a * b * c = (a * b) * c, a * b * c * d = (a * b * c) * d.

Если в композиции a ₁ * a ₂ *…* a_n все члены равны одному и тому же элементу а, то будем обозначать ее символом а и называть n–й композицией элемента а.

В моноиде (А; *, е) для любого элемента а Î А полагают еще a = е.

Применяя теорему 1 к композициям, содержащим одинаковые члены, получаем следствие.

СЛЕДСТВИЕ 1. 1. Пусть (А;*) – полугруппа, а – произвольный элемент из А. Тогда для любых натуральных чисел n ₁ и n ₂ выполняются равенства

n ₁ n ₂ n ₁ + n ₂

(* a) * (* a) = * a, (7)

n ₂ n ₁ n ₂ n ₁

* (* a) = * a. (8)

Если закон композиции – умножение, то композиция элементов

a ₁, a ₂,…, a_n называется произведением последовательности элементов и обозначается через

П а_i = a ₁ × a ₂ ×…× a_n. (9)

i= 1

При аддитивной записи композиция элементов a ₁, a ₂,…, a_n называется суммой и обозначается через

S a_i = a ₁ + a ₂ +…+ a_n. (10)

i =1

ОПРЕДЕЛЕНИЕ 4. Произведение n сомножителей, каждый из которых равен элементу а, называют n –й степенью элемента а и обозначают символом

a ⁿ = a × a × …× a.

n – раз

В моноиде (А; ×, 1 _À) для любого а Î А полагают еще а ^о = 1 _À.

ОПРЕДЕЛЕНИЕ 5. Сумму n слагаемых, каждое из которых равно элементу а, называют n – кратным элемента а и обозначают символом

na = a + a +…+ a.

n – раз

В моноиде (А; +, 0) для любого а Î А полагают еще 0 а = 0.

Формулы (7) и (8) в символах операций умножения и сложения записываются соответственно так:

n ₁ n ₂ n ₁ + n ₂

a a = a,(7’)

n ₁ ⁿ ₂ n ₁ n ₂

(a) = a; (8’)

n ₁ a + n ₂ a = (n ₁ + n ₂) a, (7”)

n ₁ (n ₂ a) = (n ₁ n ₂) a. (8”)