Лекции.Орг


Поиск:




Примеры 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) с ассоциативной бинарной операцией *.

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

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

Примеры 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 -,, один ”,,, единый ”,,, единственный ”.

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

Примеры 5 – 9

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

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

($1Î N) (" n Î N)[ n ×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 элементов множества А, записанных в определенном порядке: а 1, а 2 ,,…, аn. Можно несколькими способами расставить скобки, которые будут указывать порядок последовательного выполнения операции * над этими элементами.

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

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

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

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

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

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

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

(" a 1, a 2,…, ak Î A)[(a 1* a 2*…* ak)*(ak +1* ak +2*…* an) =

(4)

= (a 1* a 2*…* ak * ak +1)*(ak +2 * ak +3 * …* an)].

Это действительно так. Композиции a 1* a 2*…* ak и ak +1* ak +2*…* an, по предположению, однозначно определены. Обозначим через

а = a 1* a 2*…* ak и c = ak +2* ak +3 *… * an.

Тогда

(a 1 * a 2 *…* ak) * (ak +1 * ak +2 *…* an) = a * (ak +1 * c),

(a 1 * a 2 *…* ak * ak +1) * (ak +2 * ak +3 *…* an) = (a * ak +!) * c.

В силу ассоциативности операции *, а *(аk +1 * c) = (a * ak +1) * c

и, следовательно, (a 1 * a 2 *…* ak) * (ak +1 * ak +2 *…* an) = (a 1 * a 2 *…* ak * ak +1)* (ak +2 * ak +3 *…* an).

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

(" a 1, a 2,…, an Î A)[(a 1* a 2*…* ak)*(ak +1* ak +2*…* an) =

(5)

= (a 1* a 2*…* al)*(al +1* al +2 *…* an)].

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

* (ak +2 * ak +3 *…* an) = (a 1 * a 2 *…* ak * ak +1 * ak+ 2) * (ak +3 * ak +4*…* an) =… = (a 1 * a 2 *…* ak+s -1) * (ak+s * ak+s +1 *…* an) =

= (a 1 * a 2 *…* al) * (al +1 * al+ 2 *…* an).

Итак, (a 1 * a 2 *…* ak) * (ak+ 1 * ak+ 2 *…* an) = (a 1 * a 2 *…* al) * (al +1 * al+ 2 *…* an).

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

a 1 * a 2 *…* ak и ak +1 * ak +2 *…* an (1 £ k £ n –1).

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

Но в силу равенства (5), (a 1 * a 2 *…* ak) * (ak +1 * ak +2 *…* an) =

= (a 1 * a 2 *…* ak * ak +1 *…* al) * (al +1 * al +2 *…* an). Таким образом, в обоих случаях будем иметь один и тот же результат. Поэтому, в силу принципа математической индукции, теорема верна для любого натурального числа n ³ 3.

т.д.

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

a 1 * a 2 *…* an -1 * an = (a 1 * a 2 *…* an -1) * an. (6)

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

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

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

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

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

n 1 n 2 n 1 + n 2

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

 

n 2 n 1 n 2 n 1

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

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

a 1, a 2,…, an называется произведением последовательности элементов и обозначается через

n

П аi = a 1 × a 2 ×…× an. (9)

i= 1

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

n

S ai = a 1 + a 2 +…+ an. (10)

i =1

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

a n = a × a × …× a.

 

nраз

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

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

na = a + a +…+ a.

 

n – раз

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

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

n 1 n 2 n 1 + n 2

a a = a,(7’)

 

n 1 n 2 n 1 n 2

(a) = a; (8’)

n 1 a + n 2 a = (n 1 + n 2) a, (7”)

n 1 (n 2 a) = (n 1 n 2) a. (8”)

 



<== предыдущая лекция | следующая лекция ==>
 | Общее напутствие. Верищагин Дмитрий Сергеевич
Поделиться с друзьями:


Дата добавления: 2015-10-06; Мы поможем в написании ваших работ!; просмотров: 943 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Студент может не знать в двух случаях: не знал, или забыл. © Неизвестно
==> читать все изречения...

1343 - | 945 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.01 с.