Глухов М. М. Алгебра том 1, страница 8

Подсчитаем число т. Выберем сначала наименьшее число из М1, пусть это есты,. Чисел, меньших чем г,„„во множестве 1, и существует ровно г,„, — 1 и все они лежат в Мг, поскольку в М1 г~, — наименьшее. Таким образом, число г~, из М1 с числами из Мг образует г~, — 1 инверсий. Теперь возьмем в М число г „следующее по величине за г „и таким же образом найдем число инверсий, которые образует г,„, с элементами из Мг.

Так как все числа, меньшие его, кроме г „лежат в Мг, то получим число г, — 2. Продолжая этот процесс, найдем: т = (га, — 1) + (гар 2) + ... + (га, — й) = (г1+ ... + г~) — (1+ ... + й). П У т в е р ж д е н и е 3. Если в перестановке з б Р(1, и) имеется ~ инверсий, то от нее можно перейти к перестпановке зо = (1,..., и) с помощью последовательности из 1 транс~озиций соседних элементпов. (Докажите в качестве упражнения, используя указанный в начале параграфа способ подсчета числа инверсий.) 38 39 Задачи 1. Сколько различных бинарных отношений можно задать на множестве из 5 элементов. Сколько среди них отношений эквивалентности? 2. Является ли бинарное отношение р отоношением эквивалентности на множестве А: а) А = 1Ч/(1); арЬ с=» =Ы Е А: И ~а, И~ Ь; б) А = К; арЬ ~ ~а — Ь| Е Я; в) А = Р(1, п); 8р8' ~ У(8) = У(8'); г) А = Р(1, п); 8рз' ~ Б(8) = Б(8').

3. На множестве А4, где А = (0,1), заданы бинарные отношения р1, р2 так, что для а = (а1, а2, аз, а4),,В = (,В1 „В2„Вз„В4) Е А: ар1~3 с=~ ~ Зг Е 1, п: а; < Д, ар2,В ~ Чг Е 1, п: а; < В,. Выяснить, являются ли они отношениями частичного порядка. 4. Сколькими способами можно расставить на книжной полке книги и различных наименований, если имеется т~ экземпляров книг Й-го наименования, Й Е 1,и, при условии, что книги одного наименования неразличимы? 5. Сколько в множестве А" существует наборов, содержащих не менее п — 1, и — 2 различных элементов, если ~А~ = и? 6. Сколько существует последовательностей из нулей и единиц, в которых встечается ровно р нулей и ровно о единиц? Сколько из них не содержат рядом стоящих единиц? 7.

Сколькими способами, с учетом порядка слагаемых, можно представить натуральное число и в виде Й натуральных слагаемых? 8. Сколько существует различных инъективных, сюръективных и биективных отображений множества из т элементов в множество из и элементов? 9. Доказать равенства: й а) ,'~', С,'„Сп ' = С~~,+„, т, и, й е 1Ч; й < т; й < и; а=о и б) ~; гС„' = и . 2" а=О 10.

Пусть перестановки 81, 82 из Р(1, п) содержат соответственно ~1, ~2 инверсий. Доказать, что от 81 к 82 можно перейти с помощью ~1 + ~~ транспозиций. Глава Ш ОСНОВНЫЕ АЛГЕБРАИЧЕСКИЕ СТР~КТ~РЫ ~ 1. Бинарные операции и их свойства Как было отмечено в ~ 1 главы 1, бинарной операцией на множестве А называют отображение А2 в А.

Если ~: А2 ~ А — бинарная операция на А и (а, 6) Е А2, то образ пары (а, 6) при отображении ~ называют значением оиерации ~ на элементах а, Ь или результатом применения операции ~ к элементам а, Ь, и обозначают в виде Да, Ь), или а~Ь (например, а+ Ь, а Ь, а 0 Ь и т. д.). Особо подчеркнем, что значение операции определено однозначно для любых элементов а, Ь из А и обязательно принадлежит А. Приведем примеры бинарных операций.

П р и м е р 1. Известные из средней школы правила сложения и умножения чисел задают бинарные операции на любом из множеств ~ 1~о ~,<2,1~. П р и м е р 2. Правило нахождения разности чисел задает бинарные операции на множествах Ж, Я, К и не задает операции на множествах 1Ч и 1Чо. 2 П р и м е р 3. Пусть ~~, ~г — отображения множества (1, и) в 1, и, определенные равенствами: Яа, 6) = шах(а,Ь), Яа,Ь) = 1п1п(а,Ь). Так как для любых элементов а, Ь из 1, п максимум и минимум однозначно определены и содержатся в 1, и, то отображения ~1, ~~, являются бинарными операциями на множестве 1, и. П р и м е р 4.

Рассмотрим множество М всех подмножеств фиксированного множества М. Так как пересечение и объединение любых двух подмножеств из М являются вполне определенными подмножествами из М, то пересечение и объединение множеств являются бинарными операциями на М. 40 41 П р и м е р 5. Пусть П(М) — множество всех преобразований фиксированного непустого множества Л~Х (т. е. множество всевозможных отображений множества М в себя). Бинарными операциями на множестве П(М) являются введенные в ~ 2.1 умножение и композиция отображений. П р и м е р 6. Обозначим через В(М) множество всех бинарных отношений на непустом множестве М. Для каждой пары отношений р1, рг из В(М) определим отношение р, положив Ча, Ь Е М: (арЬ ~ Зс Е М: (ар1с)й(сргЬ)).

Отношение р называется произведением отношений р1,рг, и обозначается через р1рг. Умножение отношений есть бинарная операция на множестве В(М). Из приведенных примеров видно, сколь разнообразными по своей природе могут быть бинарные операции на множествах. В связи с этим для облегчения изучения множеств с операциями их классифицируют по свойствам операций. О п р е д е л е н и е 1.

Бинарная операция * на множестве М называется ассоциативной, если для любых элементов а, Ь, с е М выполняется равенство: (а*Ь) *с= а*(Ь*с). Ассоциативными являются все операции из примеров 1, 3, 4, 5, 6. Для операции примера 1 это известно из средней школы, для операции примеров 3, 4 это очевидно. Для операции примера 5 это следует из утверждения 1.1. Для операции примера 6 это устанавливается ниже. У т в е р ж д е н и е 1. Пусть М вЂ” произвольное непустое множество.

Операция умножения бинарных отношений, определенных на множестве М, ассоциативна. П Непосредственно из определения произведения бинарных отношений следует, что каждое из соотношений: а(Р1рг)рзЬ ар1(Ргрз)6, выполняется тогда и только тогда, когда Зс, а Е М: ар1 с, срга, Ирз. Следовательно, ~р1рг)рз = р1(ргрз). П Заметим, что операции примера 2 (вычитание на множествах чисел Ж, Я, К) не ассоциативны.

Главная роль свойства ассоциативности заключается в том, что оно позволяет не расставлять скобки при оперировании со многими элементами. О п р е д е л е н и е 2. Бинарная операция * на множестве М называется коммутативной, если для любых элементов а, Ь Е М выполняется равенство: а:в Ь = Ь * а. Легко видеть, что операции примеров 1, 3, 4 коммутативны. Операции примера 2 не коммутативны. Вопрос о коммутативности операций примеров 5, 6 решается в зависимости от мощности множества М.

У т в е р ж д е н и е 2. Операции умножения и композиции на множестве преобразований П(М), а также умножения на множестве бинарных отношений В(М), коммутативны в том и только в том случае, когда ~М~ = 1. П Если )ЛХ~ = 1, то ~П(М)~ = 1, ~В(М)~ = 2, и коммутативность указанных в утверждении операций очевидна. Пусть ~М~ ) 1 и а1,аг — различные элементы из М. Определим отображения ~1, ~г. М ~ М, положив ~1(х) = а1, Ях) = аг для всех х Е М. Тогда: ® о ~гИа1) = ~1(Яа1)) = а1, (Ь о Л)(а1) = Ь(Л(а1)) = аг. Следовательно, ~1 о ~г ~ Уг о ~1, а потому и ~11г Ф ЬЛ.

Пример, показывающий некоммутативность умножения бинарных отношений на множестве М, постройте в качестве упражнения. П 3 а м е ч а н и е 1. Для отдельных элементов а, Ь Е М равенство (1) может выполняться и в том случае, когда операция * не коммутативна. Такие элементы называются перестановочными (или коммутирующими) друг с другом. Так, например, любой элемент множества М перестановочен сам с собой при любой операции к 3 а м е ч а н и е 2. Свойства ассоциативности и коммутативности операций независимы, т.

е. существуют операции, обладающие любым одним из этих свойств и не обладающих другим. Примеры ассоциативных, но не коммутативных операций уже встречались. Примером коммутативной, но не ассоциативной операции на множестве К может служить операция нахождения среднего арифметического числа для 42 43 действительных чисел Таблица 2 45 а+Ь а*Ь= 2 В том случае, когда на одном и том же множестве определены несколько операций, можно говорить о свойствах, связывающих различные операции.

О п р е д е л е н и е 3. Бинарная операция * на множестве называется лево или право дистрибутивной относительно бинарной операции о, если для любых элементов выполняется соответственно равенство: а*(Ьос) = (а*Ь) о (а*с) или (Ьо с) *а = (Ь*а) о (с*а). Если выполняются оба этих свойства, то говорят просто о дистрибутивности операции * относительно операции о. В частности, если операция * коммутативна, то правая (левая) дистрибутивность совпадает с дистрибутивностью. Так, из средней школы известно, что в числовых множествах операция умножения дистрибутивна относительно операции сложения.

Заметим, что операция сложения чисел не дистрибутивна относительно умножения. В примере 4 операция пересечения на множестве М дистрибутивна относительно операции объединения, а операция объединения дистрибутивна относительно операции пересечения. В том случае, когда операция * не коммутативна, свойства левой и правой дистрибутивности могут не совпадать.