Примеры 5 – 9

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

п.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 называется суммой и обозначается через

Sa_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”)