Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 4
Текст из файла (страница 4)
УМНОЖЕНИЕ ПРЕОБРАЗОВАНИЙ В 3 1 мы рассмотрели операцию образования супер- позиции функций, заданных на множестве действительных чисел. Аналогично можно строить новое преобразование по двум данным н для произвольных ьгиожеств. Пусть М вЂ” произвольное множество, гр и ф — некоторые преобразования этого множества. 1?роизведением преобразований тр, тр называется такое преобразование ш множества М, которое на каждый элемент а ее М действует так: (а) ш = ((а)ср)хр, т.
е., чтобы найти обоаз произвольного элемента а в=М .'К((й (д) под действием преобразования (ЮФ (д)(~.~р сэ, нужно сначала найти образ Ь элемента а под действием в д преобразования гр, а потом— образ с элемента Ь под действием преобразования ф Элемент с и есть образ элемента а под К)з действием преобразования со.
Рнс. 3 На языке стрелочных схем действие преобразования ш на элемент а ее М можно выразить так: а — Ь=с, т м Произведение преобразований <р, ф будем обозначать далее через гр ф м( П р и м е р ы. ! . Пусть М вЂ” множество людей, которые когда-либо жили на Земле, хр — преобразование множества М, которое каждому человеку ставит в соответствие его отца, а тр — преобразование множества М, которое каждому человеку ставит в соответствие его мать. Тогда: а) <р.тр — преобразование множества М, которое каждому человеку ставит в соответствие бабушку по отцовской линии; б) гр гр — преобразование множества М, которое каждому человеку ставит в соответствие дедушку по отцовской линии; 13 в) ф ~р — преобразование множества М, которое каждому человеку ставит в соответствие его дедушку по материнской линии; г) ф ф — преобразование множества М, которое каждому человеку ставит в соответствие его бабушку по материнской линии.
2. Пусть М=П вЂ” множество точек плоскости, в — поворот плоскости вокруг фиксированной точки О на угол и/2 по часовой стрелке, а ф — поворот плоскости вокруг точки на угол 2п(3 против часовой стрелки. Тогда и <г ф и ф ср — поворот на угол и/б против часовой стрелки (рнс. 3). Рис. 4 3. Пусть ~р:х- х+3 — преобразование множества действительных чисел К, которое числу х ставит в соответствие число х+3, а ф: х-~-х+2 — преобразование этого множества, которое каждое число х переводит в число х+2.
Тогда ~р ф=ф ° у — преобразование, которое каждое число х переводит в число х+5 (рис. 4). ~ Рис. 5 Очень легко найти произведение двух преобразований, заданных стрелочными схемами. Поясним это на примере. Пусть ч и ф — преобразования множества М = (а, Ь, с, с(, 1), стрелочные схемы которых изображены на рис. 5. Чтобы построить стрелочную схему преобразования ~Р ф, нужно соединить стрелками те точки правой части стрелочной схемы ~Р и левой части стрелочной схемы ф которые обозначают одинаковые элементы из М (на рис.
5 эти гв стрелки изображены штриховыми лнниямп). Получаем единую схему, по которой образ произвольного элемента из М при преобразовании ~р ф находим так: из каждой точки левой части стрелочной схемы преобразования у проходим вдоль стрелок до соответствующей точки правой части стрелочной схемы преобразования ф. Получим (а)(<р ф)=а, (Ь)(ф ф)=1, (с)(!р ° ф)= ), (д) (<р ° ф) = а, (1) (~р ° ф) = а. Следовательно, преобразование !Р ф имеет стрелочную схему, изображенную на рис. 6.
Таблицу произведения ,в перестановок 'в с (! 2 3 ... п ю !р от (1 2 3 ... и! (й !з (з "° !л) г"'У находят по такому удобному пра- вилу: Рис. б а) переставляют столбцы в таб- лице ф так, чтобы ее верхний ряд совпадал с нижним рядом таблицы ~р, и получают б) строят новую таблицу, первым рядом которой является первый ряд таблицы <р, а вторым — второй ряд таблицы ф'. Построенная таблнца и будет таблицей преобразования р ф. М Пример 4.
Пусть (3 4 1 6 2 5)' ф (6 5 4 3 2 !)' Имеем (3 4 1 б 2 5) (6 ' 5 4 3 2 1) !! 2 3 4 5 6! (3 4 1 6 2 51 /1 2 3 4 5 61 )3 4 1 б 2 51 (4 3 б 1 5 2,! (4 3 6 1 5 21 ' В предыдущем параграфе были рассмотрены три класса преобразований произвольного множества: инъекции, сюрьекции и биекции. Оказывается, что каждый из этих классов замкнут относительно умножения преобразований, 20 т. е. произведение инъекций снова инъекция, произведение сюръекций — сюръекция и, наконец, произведение биекций— биекция.
Действительно, пусть преобразования ф и ф являются инъекциями множества М в себя и в = ф ф. Тогда для каждой пары элементов а, Ь он М, а~ Ь, будем иметь (а)ф ~ (6)ф, (а)ф Ф (6)ф Подействуем преобразованием ы на элементы а и Ь. По определению произведения преобразований (а)ы = ((а)ф)ф = (а1)ф (Ь)ы = ((6)ф)ф = (6,)ф где а,=(а)ф, Ь,=(6)ф. Поскольку ф — инъекция, то а,ФЬь В свою очередь, поскольку ф — инъекция, имеем (о,)фФ Ф(61)фь Значит, для каждой пары а, Ь онМ, а ~Ь, имеем (а)соФ(6)со, и оз является ннъекцией. Пусть теперь преобразования ф и ф сюръективны.
Убедимся, что для каждого элемента а ~ М найдется такой элемент Ь е- =М, для которого (6)ы = а. Поскольку ф — сюръекция, найдется такой элемент с е= М, что (с)ф=а, а из сюръектпвности ф вытекает, что существует такой элемент Ь ен М, для которого (6)ф = с. Элемент Ь искоыыйй (6)ы = ((6)ф)ф = (с)ф = а. Следовательно, преобразование и — сюръекция. Отсюда сразу же получаем, что произведение бпективных преобразований — преобразование биектнвное. В частности, для конечных множеств все три класса прсоброзм виной совпади~от, т.
е. и р извсдение п о;извольных двух перестановок на множестве М снова является перестановкой на множес1пк М. Это' следует также из описанного нами правила нахождения произведения перестановок. Как известно, операции сложения и умножения чисел характеризуются рядом свойств. Например, операция сложения чисел имеет такие свойства (именио операция сложения, а не сами числа): а) Ассоциативность.
Для каждых трех чисел а, Ь, с справедливо равенство а+(Ь+с) = (а+Ь)+с. б) Комм ут ат и в ность. Для каждых двух чисел а, Ь выполняе1ся равенство а+6=Ь+а. 21 в) Существует нейтральный элемент (нуль), такой, что для з бого числа а а+0.=0+а=а. г) Для каждого числа а существует п рати воположн ое к нему число — а, такое, что а+( — а) =О. Выясним, справедливы ли отмеченные свойства для операции умножения преобразований произвольного множества М. а) Умножение преобразований произвольного множества М имеет свойство ассоциативности. Это означает, что для каждых трех преобразований я, й, у множества М справедливо равенство (я ()) у=я (й ° у). (2) Оно свидетельствует о том, что на любой элемент аен М преобразования <р=(я ° ()) у и ~р=-я (й "р) действуют одинаково: (а) ((я й) у) = (а) (я (й у)).
(3) Действительно, возьмем произвольный элемент а ен М, и пусть (а)я =Ь, (Ь)р =с, (с)у =й. Тогда по определению (1) (а) <р = ((а) (я ° й))у = (((а)я) й)у = ((Ь) й)у = (с)у = д, (а) р = ((а)я) (р у) = (Ы ф ° у) = ((Ы р)у = (с) у = а. Таким образом, равенство (3) выполняется для произвольного а ~ М, и, следовательно, справедливо равенство (2). На рис. 7 изображено схематично действие произведения преобразований на элемент а ~ М.
Произведению я (() ° у) отвечает путь, обозначенный линией из жирных точек, а произведению (я й) у — путь, обозначенный штриховой линией. Обе линии заканчиваются в точке, которая отвечает элементу Лен М, т, е. преобразования ~р и $ действуют на элемент а одинаково. Следовательно, операция умножения преобразований множества М ассоциативна. б) Умножение преобразований произвольного множества не коммутативно. Это означает, что существуют такие преобразования д и ~р заданного множества М, для которых Такими преобразованиями на соответствующих множествах являются преобразования ср, ~р, приведенные в примерах 1 и 4.
Не следует думать, что произведение преобразований всегда зависит от порядка, в котором записаны сомножители. Например, произведение преобразований, определенных в примерах 2 и 3, не зависит от порядка сомножителей. Произведение перестановок (2 3 ! 6 5 4~ 1 (3 ! 2 4 5 6) также не зависит от порядка их записи: ! 2 3 4 5 6 (! 2 3 6 5 4~' в) Особую роль при умножении преобразований играют тождественное преобразование е и постоянные преобразования б, хы М (напомним, что (а)а=а и (а)б„=х для а У г 4 Ь-!л7Н,У ' 7' а'=ауг" 5-- ---- — + И а 1 г=(47 У т Рис.
7 каждого а~ М). Преобразование е играет для операции умножения преобразований ту же роль, что и единица при умножении чисел (или нуль прн сложении чисел), т. е. для каждого преобразования гр множества М имеем (4) Действительно, положив (а)~р=Ь, по определению произведения (1) для каждого элемента а 6= М будем иметь (а) (!р е) = ((а)ср)е = (Ь)е = Ь, (а) (е ° <р) = ((а)е) р =-(а)<р = Ь, Это и означает, что справедливо равенство (4). Легко понять, что е — единственное преобразование, для которого выполняются равенства (4).
Действительно, допустим, что существует другое преобразование е'~е, 23 такое, что для ка>идого ч> имеем е' ° «Р = Ч> ° е' = 1Р. Тогда произведение е е'=е' ° е, с одной стороны, должнэ равняться е' (когда роль единицы выполняет е), а с другой — е (когда роль единицы выполняет е'). Следовательно, е=е е'=е', а потому е=а', и мы пришли к противоречию, которое свидетельствует о том, что наше допущение неверно.
Преобразования 6„(их столько, сколько элементов имеет множество М) относительно умножения играют роль «нулей», т. е. для любого преобразования ~р имеем Ч>*бл= б«. Но бл ' >р = б(х)ч (проверьте!). М Пример б. Пусть М=(1, 2, 3, 4, б), <Р=(5 4 3 2 1). Тогда (5 4 3 2 1) (2 2 2 2 2) (2 2 2 2 2) ' (! 2 3 4 5 1 2 3 4 5 1 2 3 4 5 (2 2 2 2 2) (5 4 3 2 1) '(4 4 4 4 4) (тут 4=(2)ч>). Следовательно, если произвольное преобразование умно>кнть на «нуль» справа, то получим тот же самый «нуль», а если слева, «нуль», вообще говоря, будет другой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
