3. Взаимно однозначное отображение на все множество.

Если отображение множества А в множество В является одновременно инъективным и сюръективным, то оно называется взаимно однозначным отображением множества А на множество В или биекцией А на В.

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

9. Отображение где есть, очевидно, биекция множества Z на множество четных чисел.

Если существует биекция конечного множества А на конечное множество В, то должны выполняться неравенства Следовательно, для конечных множеств А и В биекция А на В существует тогда и только тогда, когда выполняется равенство

Подсчитаем, сколько существует разных биекций множества на множество

Каждая биекция полностью описывается, своей таблицей:

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

Следовательно, первое (например, слева) место нижнего ряда таблицы можно заполнить разными способами. Если первое место уже заполнено, то независимо от того, каким элементом оно заполнено, на второе место можно поставить обозначение какого угодно из тех элементов множества В, которые остались. Аналогично третью клетку, независимо от того, какие элементы поставлены в первые две клетки, можно заполнить способами и т. д. Для предпоследнего места остаются лишь две возможности его заполнения, а для последнего — только одна. Поскольку каждая клетка заполняется независимо от остальных, существует

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

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

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

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

первых натуральных чисел.

Задавая преобразования таблицами, будем записывать их в таком упрощенном виде:

Ясно, что такое обозначение однозначно характеризует преобразование и не вызывает недоразумений. Например, если М = {1, 2, 3, 4, 5}, то

есть таблицы разных преобразований на множестве М, Читать такую таблицу, например а), следует так:

«Преобразование , заданное таблицей а),

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

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

Некоторые преобразования множества М имеют специальные названия.

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

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

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

где

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

где — разные элементы из М.

Упражнения

1. Построить графики и стрелочные схемы для отображений множества в множество заданных такими таблицами:

2. Пусть А и В - конечные множества, причем Сколько существует разных инъекций множества А в множество В?

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

4. Будет ли сюръекцией отображение из множества 5 слов русского языка в множество L букв русского алфавита, которое каждому слову ставит в соответствие его первую букву?

5. Какие свойства отличают графики и стрелочные схемы биекций от графиков и стрелочных схем произвольных отображений?

6. Сколькими способами можно расположить одноцветных ладей на шахматной доске с клетками так, чтобы никакие две из них не били друг друга?

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

8. Сколькими способами можно расположить на шахматной доске 8 одноцветных ладей так, чтобы никакая из них не стояла на белой диагонали и никакие две не били друг друга?

9. Сколько можно составить разных шестизначных чисел из цифр 0, 1, 2, 3, 4, 7, 9?

10. Сколько существует разных перестановок на множестве для которых

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

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

13. Сколькими способами можно разместить 8 одноцветных ферзей на шахматной доске так, чтобы никакие 2 из них не били друг друга?