Расин, Алгебра

следующим образом:

Эта запись означает, что f (1) = 9, f (2) = 8, f (3) = 7, f (4) = 8. По существу, мы задали указанное отображение таблицей.

5. Пусть X – произвольное непустое множество. Всегда существует тождественное преобразование εX множества X, определенное правилом εX (x) = x для любого x X.

Между свойствами инъективности и сюръективности имеется связь. А именно, справедливо следующее утверждение.

Предложение 5.1. Пусть X и Y – произвольные непустые множества. Тогда

1)если отображение f из X в Y инъективно, то существует сюръективное отображение g из Y на X;

2)если отображение f из X в Y сюръективно, то существует инективное отображение g из Y в X;

Д о к а з а т е л ь с т в о. Пусть отображение f инъективно. Зафиксируем во множестве X элемент x0. Правило g определим следующим образом: если y E(f ) и f (x) = y, то g(y) = x, если же y 6E(f ), то g(y) = x0. Убедимся сначала, что g является отображением. Пусть g(y) = x1 и g(y) = x2. Предположив, что y E(f ), имеем f (x1) = y и f (x2) = y, откуда f (x1) = f (x2). Используя инъективность отображения f , получаем, что x1 = x2. Пусть теперь y 6E(f ). Тогда g(y) = x0, и потому x1 = x0 = x2. Таким образом, g(y) однозначно определен, и, следовательно, g является отображением. Сюръективность отображения g очевидна, поскольку для каждого x X найдется такой элемент y E(f ), что y = f (x).

Пусть f – сюръективное отображение. Тогда для каждого yY полный прообраз f −1(y) является непустым множеством. Следовательно, для произвольного y Y в полном прообразе f −1(y) можно зафиксировать элемент g(y). Тем самым получаем правило g, являющееся, как нетрудно понять, инъективным отображением.

80

5.2. Композиция отображений

Пусть даны отображения f : X −→ Y и g : Y −→ Z. Рассмотрим отображение g◦f : X −→ Z, определенное правилом g◦f (x) = g(f (x)). Это отображение называется композицией отображений f и g.

Таким образом, композиция g◦f определена, если область значений отображения f совпадает с областью определения отображения g. На самом деле, такое требование является излишним: достаточно предполагать, что множество значений отображения

fсодержится в области определения отображения g. Приведем примеры композиций отображений.

1.Пусть X = {1, 2, 3, 4}, Y = {6, 7, 8, 9}, Z = {5, 6, 7}. Рассмотрим отображения f : X −→ Y и g : Y −→ Z, определенные следующим образом

Тогда композиция g◦f : X −→ Z задается так

2. Рассмотрим отображения f : R −→ R и g : R −→ R, заданные формулами f (x) = x2, g(x) = x − 3. Тогда g◦f (x) = x2 − 3. Нетрудно понять, что в этом случае можно рассмотреть и композицию f ◦g, причем f ◦g(x) = (x − 3)2.

Пусть даны отображения

f : X −→ Y, g : Y −→ Z, h : Z −→ T.

Тогда определены отображения (h◦g)◦f и h◦(g◦f ). Читатель без труда проверит, что выполнено равенство

Обозначим через T (X) совокупность всех преобразований непустого множества X. Ясно, что для любых преобразований f, gT (X) существует композиция g◦f . Из равенства (1) очевидно вытекает

81

Предложение 5.2. Операция композиции на множестве T (X) ассоциативна.

Из предложения 5.2 следует, что если f1, f2, . . . , fn – произвольные преобразования множества X, то однозначно определена их композиция

f1◦f2◦ . . . ◦fn.

В частности, если f1 = f2 = . . . = fn = f , то определено преобразование f n. А именно,

f 1 = f, f n = f n−1◦f, если n > 2.

В дополнение к предложению 5.2 отметим, что операция композиции на множестве T (X) не является коммутативной, если множество X содержит более одного элемента. Для того чтобы убедиться в этом, достаточно рассмотреть случай, когда множество X состоит из двух элементов. Пусть для определенности X = {1, 2}. Рассмотрим следующие преобразования:

Видно, что f ◦g 6= g◦f .

Предложение 5.3. Пусть заданы отображения f : X −→ Y и g : Y −→ Z.

Тогда

(a)если f и g инъективны, то композиция g◦f инъективна;

(b)если f и g сюръективны, то композиция g◦f сюръективна;

(c)если f и g биективны, то композиция g◦f биективна.

Д о к а з а т е л ь с т в о. (a) Пусть x1, x2 X, причем x1 6= x2. Тогда, используя инъективность отображения f , получаем f (x1) 6= 6= f (x2). Из инъективности g теперь следует, что

g◦f (x1) = g(f (x1)) 6= g(f (x2)) = g◦f (x2).

82

(b)Пусть z – произвольный элемент из Z. Поскольку g сюръективно, существует такой y Y , что z = g(y). Но f тоже сюръективно, поэтому y = f (x) для некоторого x X. Стало быть, z = g(y) = g(f (x)) = g◦f (x), и сюръективность композиции доказана.

(c)следует из доказанного выше.

5.3. Отображение, обратное к данному

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

Предложение 5.4. Пусть f – инъективное отображение множества X в множество Y . Тогда существует биективное отображение g : E(f ) −→ X, удовлетворяющее равенствам

g(f (x)) = x, f (g(y)) = y

для любых x X, y E(f ).

Д о к а з а т е л ь с т в о. Для произвольного y E(f ) определим правило g:

Проверим, что правило g задает отображение из E(f ) в X. В самом деле, пусть g(y) = x1 и g(y) = x2. Это означает, что f (x1) = y и f (x2) = y. Стало быть, f (x1) = f (x2). Поскольку f – инъективное отображение, из последнего равенства следует, что x1 = x2.

Теперь покажем, что g – инъективное отображение. Предположим, что y1, y2 E(f ) и g(y1) = g(y2) = x. Из определения отображения g следует, что y1 = f (x), y2 = f (x) и, стало быть, y1 = y2. Таким образом, g инъективно.

Осталось убедиться в том, что g сюръективно. Пусть x – произвольный элемент из X и y = f (x). Отсюда вытекает, что x = g(y).

Поскольку g одновременно инъективно и сюръективно, оно биективно.

83

Пусть f – биективное отображение множества X на множество Y . Применяя в этом случае предложение 5.4, мы получим биективное отображение g : Y −→ X, причем равенства y = f (x) и x = g(y) равносильны.

Такое отображение g называется обратным к отображению f . Нетрудно видеть, что если отображение g обратно к биективному отображению f , то и f является обратным к g. В этой ситуации

отображения f и g называются взаимно обратными. Сформулируем свойства взаимно обратных отображений.

1.D(f ) = E(g);

2.D(g) = E(f );

3.f ◦g = εY ;

4.g◦f = εX .

Эти свойства непосредственно вытекают из доказательства предложения 5.4.

Предложение 5.5. Пусть дано отображение f : X −→ Y . Если существует такое отображение g : Y −→ X, что f ◦g = = εY и g◦f = εX , то f – биективное отображение и g является отображением, обратным к f .

Д о к а з а т е л ь с т в о. Пусть f ◦g = εY , g◦f = εX для некоторого отображения g : Y −→ X. Докажем сначала, что f инъективно. Если x1, x2 X и f (x1) = f (x2), то g◦f (x1) = g◦f (x2). Поскольку g◦f = εX , имеем g◦f (x1) = x1, g◦f (x2) = x2. Стало быть, x1 = x2.

Теперь убедимся, что f сюръективно. Пусть y – произвольный элемент из Y , и g(y) = x. Так как f ◦g = εY , получаем

f (x) = f (g(y)) = f ◦g(y) = εY (y) = y.

Мы проверили, что f инъективно и сюрьективно. Следовательно, f биективно.

Осталось доказать, что отображение g обратно к f . Пусть x – произвольный элемент из X и y = f (x). Отсюда

g(y) = g(f (x)) = g◦f (x) = εX (x) = x.

Таким образом, y = f (x) = x = g(y). Аналогично проверяется, что x = g(y) = y = f (x).

84

Отображение, обратное к данному биективному отображению f , как правило, обозначают через f −1

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

5.4. Множество всех отображений из X в Y

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

Предложение 5.6. Пусть X1, X2, Y – произвольные непустые множества, причем X1 ∩ X2 = . Тогда существует биективное отображение из Y X1 X2 на Y X1 × Y X2 .

Д о к а з а т е л ь с т в о. Пусть f Y X1 X2 , т. е.

f : X1 X2 −→ Y.

Определим отображения

f1 : X1 −→ Y, f2 : X2 −→ Y,

положив fi(x) = f (x), если x Xi, i = 1, 2. Нетрудно понять, что правило

ϕ(f ) = (f1, f2)

задает отображение ϕ из Y X1 X2 в Y X1 × Y X2 .

Докажем, что отображение ϕ сюръективно. Пусть fi – произвольные отображения из Xi в Y (i = 1, 2). Так как множества X1,

85

определяет отображение из X1 X2 в Y . Ясно, что

ϕ(f ) = (f1, f2)

.

Проверка инъективности отображения ϕ оставляется читателю в качестве упражнения.

Предложение 5.7. Пусть X, Y , Z – произвольные непустые

множества. Тогда существует биективное отображение из

ZY X на ZX ×Y .

Д о к а з а т е л ь с т в о. Пусть f ZY X , т. е. f : X −→ ZY .

Стало быть, для любого x X определено отображение

f (x) : Y −→ Z.

Пусть h – произвольное отображение из ZX ×Y . Для каждого xX определим отображение

g(x) : Y −→ Z

правилом g(x)(y) = h(x, y). Ясно, что h = g˜.

Предложение 5.8. Пусть X1, X2, Y – произвольные непустые множества. Если существует биективное отображение из X1 на X2, то существует и биективное отображение из Y X1 на Y X2 .

86

Д о к а з а т е л ь с т в о. Пусть f : X1 −→ X2 – биективное отображение. Тогда, как мы знаем, существует обратное к f отображение f −1. Если g – произвольное отображение из X1 в Y , то g◦f −1 является отображением из X2 в Y . Определим отображение

˜ −1

в соответствии с правилом f (g) = g◦f и убедимся, что отобра-

˜

жение f является биекцией.

Пусть g1, g2 – произвольные отображения из X1 в Y , причем

сюръективно.

Предложение 5.9. Пусть X, Y1, Y2 – произвольные непустые множества. Если существует биективное отображение из Y1 на Y2, то существует и биективное отображение из Y1X на Y2X .

Д о к а з а т е л ь с т в о. Пусть f – биективное отображение из Y1

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

Следующие два утверждения проверяются аналогично предложениям 5.8 и 5.9. Соответствующие доказательства мы опускаем.

Предложение 5.10. Пусть X1, X2, Y – произвольные непустые множества. Если существует инъективное отображение из X1 в X2, то существует и инъективное отображение из Y X1 в Y X2 .

87

Предложение 5.11. Пусть X, Y1, Y2 – произвольные непустые множества. Если существует инъективное отображение из Y1 в Y2, то существует и инъективное отображение из Y1X в Y2X .

Обозначим через 2 множество {0, 1}. Тогда 2X – множество всех отображений из множества X в двухэлементное множество. Пусть Y – произвольное подмножество из X. Определим функцию

Такое отображение hY называется характеристическим для подмножества Y . Нетрудно понять, что разным подмножествам отвечают разные характеристические функции. Поэтому справедливо следующее утверждение.

Предложение 5.12. Существует биективное отображение из булеана P(X) множества X на множество 2X .

Рассмотрим случай, когда X = {1, 2, . . . , n}. Если f – отображение из X в Y , то f однозначно определяется конечной последовательностью (кортежем) (f (1), f (2), . . . , f (n)). Отсюда вытекает, что существует биективное отображение из Y X на Y n.

5.5.Конечные и бесконечные множества

Вэтом разделе мы дадим ответ на два вопроса: что такое конечное и что такое бесконечное множество ? Существенную помощь при этом нам окажут инъективные отображения. Напомним, что в разделе 2.4 через N6n было обозначено множество {1, 2, . . . , n}.

Лемма 1. Пусть n – произвольное натуральное число, f – отображение из N6n+1 в N6n. Тогда f не является инъективным.

88

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

Если n = 1, то f отображает множество N62 = {1, 2} в множество N61 = {1}. Ясно, что такое отображение не является инъективным.

Пусть k > 1. Предположим, что для n = k утверждение выполнено. Убедимся, что оно выполняется и при n = k + 1. Пусть f – произвольное отображение из N6k+1 в N6k. Возможны два случая:

(a)для любого i 6 k справедливо неравенство f (i) 6 k − 1;

(b)существует такое j 6 k, что f (j) = k.

Рассмотрим случай (a). Тогда существует отображение

g : N6k −→ N6k−1,

заданое правилом g(i) = f (i) для каждого i 6 k. К отображению g применио предположение индукции; поэтому g не является инъективным. Отсюда cледует, что f тоже не инъективно.

Предположим, что имеет место случай (b). Если f (k + 1) = k, то f (j) = f (k + 1) = k и j 6= k + 1. Поэтому f не является инъективным. Пусть f (k + 1) = l < k. Можно считать, что кроме чисел j и k + 1 в числа k и l никакие другие числа не отображаются (иначе f очевидным образом не обладало бы свойством инъективности). Рассмотрим отображение

h : N6k+1 −→ N6k,

определенное следующим образом:

f (i), если i 6 j,{k + 1}, h(i) = l, если i = j,

n, если i = k + 1.

Ясно, что отображение h обладает свойстом (a), и потому h, а вслед за ним и f , не является инъективным.

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

1П.Л.Дирихле (1805–1859) – один из крупнейших математиков девятнадцатого столетия. Известен работами по теории чисел, математическому анализу, вариационному исчислению.

89