Главная > Математика > Преобразования и перестановки
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 3. УМНОЖЕНИЕ ПРЕОБРАЗОВАНИЙ

В § 1 мы рассмотрели операцию образования суперпозиции функций, заданных на множестве действительных чисел. Аналогично можно строить новое преобразование по двум данным и для произвольных множеств.

Пусть М — произвольное множество, — некоторые преобразования этого множества. Произведением преобразований называется такое преобразование со множества М, которое на каждый элемент действует так:

т. е., чтобы найти образ произвольного элемента под действием преобразования , нужно сначала найти образ b элемента а под действием преобразования а потом — образ с элемента b под действием преобразования Элемент с и есть образ элемента а под действием преобразования .

Рис. 3

На языке стрелочных схем действие преобразования со на элемент можно выразить так:

Произведение преобразований будем обозначать далее через

Примеры. 1. Пусть М — множество людей, которые когда-либо жили на Земле, — преобразование множества М, которое каждому человеку ставит в соответствие его отца, а — преобразование множества М, которое каждому человеку ставит в соответствие его мать. Тогда:

а) — преобразование множества М, которое каждому человеку ставит в соответствие бабушку по отцовской линии;

б) — преобразование множества М, которое каждому человеку ставит в соответствие дедушку по отцовской линии;

в) — преобразование множества М, которое каждому человеку ставит в соответствие его дедушку по материнской линии;

г) — преобразование множества М, которое каждому человеку ставит в соответствие его бабушку по материнской линии.

2. Пусть — множество точек плоскости, — поворот плоскости вокруг фиксированной точки О на угол по часовой стрелке, а — поворот плоскости вокруг точки на угол против часовой стрелки. Тогда и и — поворот на угол против часовой стрелки (рис. 3).

Рис. 4

3. Пусть — преобразование множества действительных чисел R, которое числу ставит в соответствие число я — преобразование этого множества, которое каждое число переводит в число . Тогда — преобразование, которое каждое число переводит в число (рис. 4).

Рис. 5

Очень легко найти произведение двух преобразований, заданных стрелочными схемами. Поясним это на примере. Пусть — преобразования множества стрелочные схемы которых изображены на рис. 5. Чтобы построить стрелочную схему преобразования нужно соединить стрелками те точки правой части стрелочной схемы и левой части стрелочной схемы которые обозначают одинаковые элементы из М (на рис. 5 эти стрелки изображены штриховыми линиями).

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

Следовательно, преобразование имеет стрелочную схему, изображенную на рис. 6.

Рис. 6

Таблицу произведения перестановок

находят по такому удобному правилу:

а) переставляют столбцы в таблице так, чтобы ее верхний ряд совпадал с нижним рядом таблицы и получают

б) строят новую таблицу, первым рядом которой является первый ряд таблицы , а вторым — второй ряд таблицы

Построенная таблица и будет таблицей преобразования .

Пример 4. Пусть

Имеем

В предыдущем параграфе были рассмотрены три класса преобразований произвольного множества: инъекции, сюръекции и биекции. Оказывается, что каждый из этих классов замкнут относительно умножения преобразований, т. е. произведение инъекций снова инъекция, произведение сюръекций — сюръекция и, наконец, произведение биекций — биекция.

Действительно, пусть преобразования являются инъекциями множества М в себя и Тогда для каждой пары элементов а, будем иметь

Подействуем преобразованием на элементы а и b. По определению произведения преобразований

где Поскольку — инъекция, то . В свою очередь, поскольку — инъекция, имеем

Значит, для каждой пары имеем и является инъекцией.

Пусть теперь преобразования сюръективны. Убедимся, что для каждого элемента найдется такой элемент ЬМ, для которого Поскольку — сюръекция, найдется такой элемент что , а из сюръективности вытекает, что существует такси элемент , для которого . Элемент b искомый:

Следовательно, преобразование — сюръекция.

Отсюда сразу же получаем, что произведение биективных преобразований — преобразование биективное. В частности, для конечных множеств все три класса преобразований совпадают, т. е. произведение произвольных двух перестановок на множестве М снова является перестановкой на множестве М. Это следует также из описанного нами правила нахождения произведения перестановок.

Как известно, операции сложения и умножения чисел характеризуются рядом свойств. Например, операция сложения чисел имеет такие свойства (именно операция сложения, а не сами числа):

а) Ассоциативность. Для каждых трех чисел a, с справедливо равенство

б) Коммутативность. Для каждых двух чисел a, b выполняется равенство

в) Существует нейтральный элемент (нуль), такой, что для любого числа а

г) Для каждого числа а существует противоположное к нему число — а, такое, что

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

а) Умножение преобразований произвольного множества М имеет свойство ассоциативности. Это означает, что для каждых трех преобразований множества М справедливо равенство

Оно свидетельствует о том, что на любой элемент преобразования действуют одинаково:

Действительно, возьмем произвольный элемент и пусть . Тогда по определению (1)

Таким образом, равенство (3) выполняется для произвольного , и, следовательно, справедливо равенство (2).

На рис. 7 изображено схематично действие произведения преобразований на элемент . Произведению отвечает путь, обозначенный линией из жирных точек, а произведению — путь, обозначенный штриховой линией. Обе линии заканчиваются в точке, которая отвечает элементу , т. е. преобразования действуют на элемент а одинаково. Следовательно, операция умножения преобразований множества М ассоциативна.

б) Умножение преобразований произвольного множества не коммутативно. Это означает, что существуют такие преобразования заданного множества М, для которых

Такими преобразованиями на соответствующих множествах являются преобразования приведенные в примерах 1 и 4.

Не следует думать, что произведение преобразований всегда зависит от порядка, в котором записаны сомножители. Например, произведение преобразований, определенных в примерах 2 и 3, не зависит от порядка сомножителей. Произведение перестановок

также не зависит от порядка их записи:

в) Особую роль при умножении преобразований играют тождественное преобразование s и постоянные преобразования (напомним, что для каждого ).

Рис. 7

Преобразование играет для операции умножения преобразований ту же роль, что и единица при умножении чисел (или нуль при сложении чисел), т. е. для каждого преобразования множества М имеем

Действительно, положив по определению произведения (1) для каждого элемента будем иметь

Это и означает, что справедливо равенство (4).

Легко понять, что — единственное преобразование, для которого выполняются равенства (4).

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

Тогда произведение с одной стороны, должно равняться (когда роль единицы выполняет ), а с другой — (когда роль единицы выполняет ). Следовательно,

а потому и мы пришли к противоречию, которое свидетельствует о том, что наше допущение неверно.

Преобразования (их столько, сколько элементов имеет множество М) относительно умножения играют роль «нулей», т. е. для любого преобразования имеем

Но

(проверьте!).

Пример 5. Пусть

Тогда

Следовательно, если произвольное преобразование умножить на «нуль» справа, то получим тот же самый «нуль», а если слева, «нуль», вообще говоря, будет другой.

г) Обратным для преобразования а произвольного множества М называется такое преобразование этого множества, что справедливы равенства

Это преобразование выполняет ту же роль, что и противоположное число для операции сложения чисел или обратное число для операции умножения чисел. Так же как и обратное число (которое существует только для ), преобразование, обратное к данному, может существовать, а может и не существовать. Например, обратным к преобразованию

является преобразование

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

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

Из этих равенств и свойства ассоциативности действия умножения преобразований последовательно имеем

и мы пришли к противоречию, которое свидетельствует о том, что наше допущение неверно.

Единственное преобразование, обратное к преобразованию далее будем обозначать .

Когда же существует обратное преобразование? Исчерпывающий ответ на этот вопрос дает такая теорема.

Теорема. Преобразование, обратное к преобразованию а множества М, существует тогда и только тогда, когда а является биекцией множества М.

Доказательства. Необходимость. Пусть для преобразования а существует обратное к нему преобразование , т. е. . Тогда для каждого имеем , где Следовательно, для каждого существует элемент такой, что , и а — сюръекция.

Покажем, что преобразование а будет также инъекцией. Допустим, что это не так. Тогда найдутся различные элементы , для которых . Поэтому будем иметь

или

откуда

Мы пришли к противоречию, которое и доказывает, что а — инъекция.

Достаточность. Пусть а — биективное преобразование. Тогда для каждого существует единственный прообраз — такой элемент , что . Поэтому можно определить такое преобразование Р множества М, которое ставит в соответствие каждому элементу его прообраз у при преобразовании а:

действительно является преобразованием, так как, поскольку а — сюръекция, оно определено для каждого элемента из М. Из самого определения вытекает, что выполняются равенства

для каждого Это означает, что , т. е. — преобразование, обратное к а.

Теорема доказана.

Пользуясь этой теоремой, легко решить вопрос о существовании обратной функции. Обратной для функции называется такая функция , что .

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

Очевидно, преобразования а и взаимно обратны, т. е. каждое из них обратно к другому. Следовательно,

Примеры. 6. Пусть — поворот плоскости на угол против часовой стрелки вокруг точки О. Поскольку — биекция, существует. Легко понять, что — поворот плоскости на угол по часовой стрелке вокруг точки О.

7. Функции — биективные преобразования

множества действительных чисел R на себя. Поэтому для них существуют обратные преобразования, а именно

Следовательно, функции обратны соответственно к функциям

Функции — преобразования

множества R, которые не биективны. А поэтому для них не существует обратных. Однако можно рассмотреть ограничение функции на множество неотрицательных действительных чисел. Это функция, область определения которой есть множество причем во всех точках области определения она совпадает с функцией Это ограничение будет биективным преобразованием множества т. е. для него существует обратное преобразование Таким образом, функция обратна к ограничению функции на множество (а не к функции как часто говорят).

Вполне аналогично можно рассмотреть ограничение функции на промежуток . Это ограничение является биективным отображением множества на множество [-1, 1]. Следовательно, для него существует обратное — функция .

8. Пусть преобразование множества точек плоскости является параллельным переносом в заданном направлении на расстояние d. Ясно, что — биективное преобразование, следовательно, для него существует обратное. Это также параллельный перенос на то же самое расстояние, но в противоположном направлении.

Для преобразования конечного множества М существует обратное преобразование тогда и только тогда, когда оно является перестановкой. Пусть дана перестановка

тогда обратная к ней перестановка, как вытекает из правила умножения перестановок, будет такая:

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

будет перестановка

Для преобразований произвольного множества можно составлять и решать уравнения. Как пример рассмотрим уравнения первой степени. Пусть фпроизвольные преобразования множества М. Существуют ли такие преобразования х у этого множества, для которых выполнялись бы равенства

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

Довольно легко ответить на вопрос о существовании и единственности решения для уравнений (5) и (6), в которых «коэффициент» — перестановка.

Если — перестановка, то решения уравнений (5) и (6) существуют и единственны.

Доказывается этот факт следующим образом. Поскольку — биекция, для него существует обратное преобразование Можно поэтому рассмотреть преобразования (отметим, что, вообще говоря, так как операция умножения преобразований некоммутативна). Покажем, что будет решением уравнения (5). Для этого вычислим произведение Используя ассоциативность операции умножения преобразований и определение обратного преобразования, получим

А это и означает, что — решение уравнения (5). Аналогично доказывается, что преобразование решение уравнения (6).

Теперь докажем, что указанные решения уравнений (5) и (6) единственны. Действитедьно, если преобразования — решения уравнений (5) и (6) соответственно,

то, умножая равенство (7) слева на а равенство (8) справа на получим

т. е.

или

Эти равенства означают, что никаких других решений, кроме отмеченных ранее, уравнения (5) и (6) не имеют.

Пример 9. Пусть М = {1, 2, 3, 4},

Нетрудно проверить, что решением уравнения (5) будет перестановка

а решением уравнения (6) — перестановка

Если преобразование в уравнениях (5) и (6) — не перестановка, то эти уравнения могут иметь решения, а могут и не иметь их (см. упражнения 8 — 11).

<< Предыдущий параграф Следующий параграф >>
Оглавление