1. Понятие отображения.Отображение f множества X в множество Y считается заданным, если каждому элементу x из X сопоставлен ровно один элемент y из Y, обозначаемый f(x).
Множество X называется областью определения отображения f, а множество Y – областью значений. Множество упорядоченных пар
Гf = {(x, y) | x∈X, y∈Y, y = f(x)}
называют графиком отображения f. Непосредственно из определения вытекает, что график отображения f является подмножеством декартова произведения X×Y:
Гf ⊂ X×Y.
Строго говоря, отображение – это тройка множеств (X, Y, G) такая, что G⊂ X×Y, и каждый элемент x из X является первым элементом ровно одной пары (x, y) из G. Обозначая второй элемент такой пары через f(x), получаем отображение f множества X в множество Y. При этом G=Гf. Если y=f(x), мы будем писать f:x→y и говорить, что элемент x переходит или отображается в элемент y; элемент f(x) называется образом элемента x относительно отображения f. Для обозначения отображений мы будем использовать записи вида f: X→Y. Часто отображения задают равенством вида y=f(x), где x и y – переменные; значениями переменной x, называемой аргументом, служат элементы множества X; переменная y принимает свои значения в множестве Y. В этом случае отображения называют также функциями.
Примеры.1) Пусть X = Y – множество действительных чисел. Формула y=2x задает отображение множества X в множество Y.
2) Пусть X – множество всех треугольников на плоскости, а Y – множество действительных чисел. Сопоставляя треугольнику его площадь, получаем отображение первого множества во второе.
3) Пусть X = {1, 2, 3}, Y = {2, 3, 4}. Множество пар
G = {(1, 2), (2, 2), (3, 3)}
задает отображение f, при котором f(1)=f(2)=2, f(3)=3.
Отображение f конечного множества X = {a, b, …, c} в себя часто бывает удобно задать с помощью таблицы (матрицы), состоящей из двух строк. В первой строке располагаются элементы множества X, а под ними, во второй строке – их образы:
Например, таблица
задает отображение множества четвертей координатной плоскости в себя при повороте плоскости на 90º против часовой стрелки вокруг начала координат (естественно, вместо самих четвертей мы используем их номера). Пусть f: X→Y – отображение множества X в множество Y, а A и B – подмножества множеств X и Y соответственно. Множество
f(A)={y| y=f(x) для некоторого x∈A}
называется образом множества A. Множество
f −1(B)={x| f(x) ∈B}
называется прообразом множества B. Отображение f: A→Y, при котором x→f(x) для всех x∈A, называется сужением отображения f на множество A; сужение будет обозначаться через f|A.
Отображение вида f:X×Y→Z называют функцией двух переменных и пишут z=f(x,y). Аналогично определяются функции большего числа переменных.
Пусть имеются отображения f: X→Y и g: Y→Z. Отображение X→Z, при котором x переходит в g(f(x)), называется композицией отображений f и g и обозначается через f⋅g или просто fg. Таким образом,
(fg)(x)=g(f(x)).
Например, если отображения f, g множества действительных чисел в себя заданы формулами
f(x)=x+1, g(x)=2x,
то
(fg)(x)=g(f(x))=g(x+1)=2(x+1);
(gf)(x)=f(g(x))=f(2x)=2x+1.
2. Специальные виды отображений.Отображение множества X в X, при котором каждый элемент переходит сам в себя, x→x , называется тождественным и обозначается через idX.
Для произвольного отображения f: X→Y имеем
idX ⋅f = f⋅idY.
Отображение f: X→Y называется инъективным, если образы различных элементов также различны, то есть f(x)≠f(y) при x≠y. Отображение f: X→Y называется сюръективным (говорят также, что f – отображение X на Y) если всякий элемент y из Y является образом некоторого элемента x из X, то есть f(X)=Y. Отображение f: X→Y называется биективным, если оно одновременно инъективно и сюръективно. Биективное отображение f: X→Y обратимо. Это означает, что существует отображение g: Y→X, называемое обратным к отображению f, такое, что
g(f(x))=x и f(g(y))=y
для любых x∈X, y∈Y.Ясно, что при этом отображение f является обратным к отображению g. Отображение, обратное к отображению f, обозначается через f −1. В соответствие с определением
f f −1=idX, f −1f=idY, (f −1)−1=f.
Нетрудно видеть, что отображение биективно тогда и только тогда, когда оно обратимо. Говорят, что обратимое отображение f: X→Y устанавливает взаимно однозначное соответствие между элементами множеств X и Y, или, короче, между множествами X и Y. Инъективное отображение f: X→Y устанавливает взаимно однозначное соответствие между множеством X и множеством f(X).
Примеры. 1) Функция f:R→R>0, f(x)=ex, устанавливает взаимно однозначное соответствие множества всех действительных чисел Rс множеством положительных действительных чисел R>0. Обратным к отображению f является отображение g:R>0→R, g(x)=ln x.
2) Отображение f:R→R≥0, f(x)=x2, множества всех действительных Rна множество неотрицательных чисел R≥0 сюръективно, но не инъективно, и поэтому не является биективным.
3. Операции.Бинарной операцией на множестве X называется отображение f:X×X→X. Результат применения бинарной операции к паре (x,y) принято записывать в виде x∗y, где ∗ – символ операции. Таким образом, f: (x,y)→x∗y.
Примеры. Отображение f:R×R→R, f(x,y) = x+y, – это операция сложения на множестве действительных чисел; f:2X×2X→2X, f(A,B) = A∩B – операция пересечения на множестве подмножеств множества X.
Бинарная операция ∗ на множестве X называется:
коммутативной, если x∗y = y∗x для всех x, y из X;
ассоциативной, если (x∗y)∗z = x∗(y∗z) для всех x, y, z из X.
При записи повторенной несколько раз ассоциативной бинарной операции скобки можно опускать – результат от порядка выполнения операций не зависит. Например,
Операции сложения и умножения на множестве действительных чисел коммутативны и ассоциативны; операции объединения и пересечения подмножеств универсального множества также коммутативны и ассоциативны. Рассмотрим не столь очевидный пример.
Пример.Зададим бинарную операцию на отрезке [0; 1] формулой
x∗y = x+y–xy.
Очевидно, так определенная операция коммутативна. Покажем, что она и ассоциативна. Имеем
Бинарная операция на конечном множестве может быть задана с помощью таблицы.
Пример.Зададим на множестве X={0, 1, 2, 3, 4} операцию «умножение по модулю 5» (остаток при делении произведения на 5):
Верхняя строка и левый столбец содержат элементы множества X, которые служат метками соответствующих столбцов и строк. На пересечении строки с меткой x и столбца с меткой y находится произведение xy по модулю 5. Например, произведение 2 на 3 по модулю 5 равно 1.
y находится произведение xy по модулю 5. Например, произведение 2 на 3 по модулю 5 равно 1.
4. Характеристические функции.Пусть X – некоторое множество, и A – его подмножество. Определим отображение χA множества X в двухэлементное множество {0,1} следующим образом: χA(x)=1, если x∈A, и χA(x)=0, если x∉A. Функция χA называется характеристической функцией подмножества A.
Очевидно, A⊂B тогда и только тогда, когда χA(x)≤χB(x) для всех x. Имеется простая связь между операциями над подмножествами множества X и операциями над их характеристическими функциями:
5. Соответствия.Пусть даны множества X и Y. Будем говорить, что задано соответствие R из X в Y, если для каждого элемента x множества X указано подмножество R(x)⊂Y соответствующих ему элементов множества Y (возможно, пустое). Множество элементов x из X, для которых R(x) не пусто, будем называть областью определения соответствия R и обозначать через D(R). Множество всех тех элементов y из Y, которые принадлежат хотя бы одному множеству R(x), будем называть полным образом соответствия R и обозначать через B(R). Более общо, для произвольного A⊂X будем обозначать через R(A) и называть образом множества A множество всех тех y∈Y, которые принадлежат хотя бы одному множеству R(x) с x∈X, то есть R(A)= ∪x∈AR(x). Полный образ соответствия R совпадает с образом множества X. Нетрудно видеть, что B(R)=R(X)=R(D(R)).
Понятие соответствия обобщает понятие функции. Если каждое множество R(x) содержит ровно один элемент, то соответствие R называется функциональным. Всякое функциональное соответствие R определяет отображение множества X в множество Y, при котором произвольному элементу x множества X соответствует единственный элемент множества R(x). Ясно, что R является графиком этого отображения. Допуская небольшую вольность, будем обозначать это отображение также через R.
Примеры.1) Натуральному числу x поставим в соответствие совокупность его простых делителей. Тем самым определяется соответствие R из множества натуральных чисел в множество простых чисел. Имеем R(10)={2, 5}, R(30)={2, 3, 5}, R(7)={7}, R(1)=∅.
2) Пусть A – множество участников рынка, а T – множество товаров. Для каждого товара t указана его цена p, для каждого участника ранка a – его бюджет b. Назовем возможным планом потребления участника рынка набор товаров, суммарная стоимость которых не превосходит его бюджета. Сопоставим каждому участнику рынка a множество возможных планов потребления. Этим определяется соответствие R из A в множество всех подмножеств множества Т. Например, пусть T={t0, t1, t2, t3}, p0=–2, p1=1, p2=2, p3=3 (отрицательную цену имеет товар, который может быть продан на рынке, например, труд); A={a1, a2, a3}, b1=0, b2=2, b3=10. Тогда
Формально соответствие R из множества X в множество Y можно определить как подмножество декартова произведения X×Y, считая, что (x,y)∈R, если y∈R(x).
Рассматривая соответствия из X в Y как подмножества множества X×Y, можно говорить о том, что одно соответствие является частью другого, можно образовывать пересечение и объединение соответствий и т. п. Пусть S, R⊂X×Y – пара соответствий из X в Y. Непосредственно из определений вытекают следующие свойства соответствий:
1) S⊂R в том и только том случае, если S(x) ⊂R(x) для всех x∈R;
2) (S∩R)(x)=S(x) ∩R(x);
3) (S∪R)(x)=S(x) ∪R(x).
Пусть R⊂X×Y – соответствие из X в Y.
Сужением соответствия R на подмножество X’⊂X называется соответствие R’=R∩X’×Y. Легко видеть, что D(R’)=X’∩D(R) и R’(x)=R(x) для любого x∈X. Сужение будет иногда обозначаться через R|X’.
Соответствие из Y в X, определяемое формулой
R–1={(y,x)|(x,y)∈R},
называется обратным к соответствию R. Очевидно, x∈ R–1(y) тогда и только тогда, когда y∈ R(x). Непосредственно из определений следует, что (R–1)–1=R; D(R–1)= B(R); B(R–1)=D(R).
Если соответствие R⊂X×Y функционально, то обратное соответствие R–1 окажется функциональным лишь в том случае, когда отображение, задаваемое соответствием R, биективно; обратное соответствие задает в этом случае обратное отображение.
Для произвольного множества X обозначим через EX соответствие, определяющее тождественное отображение множества X в себя, при этом соответствии каждому элементу множества X соответствует лишь сам этот элемент, то есть EX(x)={x}. Соответствие EX задается диагональю декартова квадрата множества X:
EX = {(x,x) | x∈X} ⊂ X×X.
Мы будем называть соответствие EX тождественным или диагональным.
6. Композиция соответствий. Пусть заданы соответствия R из X в Y и S из Y в Z. Их композицией (или произведением) называется соответствие P из X в Z такое, что P(x)=S(R(x)) для всех x из X. Композиция соответствий R и S обозначается через RS. Согласно определению имеем
RS = {(x,z) | существует y∈Y, для которого (x,y)∈R и (y,z)∈S}.
Если X=Y=Z и R=S, то вместо RR пишут R2, вместо (R2)R – (R3) и т.д.
Пример.Пусть T – множество наборов товаров такое же, как в примере из предыдущего пункта. Будем считать, что набор товаров улучшается, если к нему добавляется один из товаров с положительной ценой или из него выводится товар с отрицательной ценой. Будем говорить, что набор товаров V лучше, чем набор товаров U, если V может быть получен из U несколькими последовательными улучшениями. Например, наборы {t0,t1}, {t0,t1,t2}, {t1,t2} получаются последовательными улучшениям. Обозначим через P(U) множество тех наборов, которые получаются из набора U путем его однократного улучшения. Например, P({t0,t1})={{t0,t1,t2}, {t0,t1,t3}, {t1}}; P({t1,t2,t3})=∅. Тогда P2(U) – это множество наборов, которые получаются из U двумя последовательными улучшениями, P3(U) – это множество наборов, которые получаются из U тремя последовательными улучшениями и т.д. Очевидно, P5(U)= ∅ для любого набора U. Положим S=P∪P2∪P3∪P4. Тогда S(U) – это множество наборов, которые лучше, чем набор U.
Укажем некоторые свойства композиции соответствий.
1) Диагональные соответствия играют роль единиц: для любого R⊂X×Y имеем
EXR=R=REY.
2) Композиция ассоциативна: если R⊂X×Y, S⊂Y×Z, T⊂Z×W, то
(RS)T=R(ST).
3) Если R⊂X×Y, S⊂Y×Z, то
(RS)−1=S−1R−1.
4) Композиция монотонна относительно включения: если R1, R2⊂X×Y, S⊂Y×Z, то
R1⊂ R2 влечет R1S⊂ R2S.
5) Если R1, R2⊂X×Y, S⊂Y×Z, то
(R1∪R2)S=R1S∪R2S.
Замечание.Аналог свойства 5 для пересечений, вообще говоря, неверен. Включение
(R1∩R2)S⊂R1S∩R2S
имеет место всегда, однако оно может оказаться строгим. Например, пусть
X=Y={1, 2}, Z={1};
R1={(1,1), (2,2)},
R2={(1,2), (2,1)},
S={(1,1), (2,1)}.
Тогда R1∩R2=∅, так что (R1∩R2)S=∅. С другой стороны, R1S=S и R2S=S, откуда R1S∩R2S=S.
В заключение приведем характеристику функциональных соответствий.
Теорема.Соответствие R из множества X в множество Y функционально тогда и только тогда, когда выполняются следующие соотношения:
RR−1⊃EX , R−1R⊂EY.
Доказательство. Предположим сначала, что соответствие R функционально. Тогда R состоит из пар вида (x,f(x)), x∈X, где f – отображение из X в Y. Для любого x∈X имеем (x,f(x))∈R и (f(x),x)∈R−1, и, значит, (x,x)∈RR−1. Этим доказывается первое включение. Для доказательства второго достаточно показать, что (y,y’)∈R−1R лишь в том случае, когда y=y’. В самом деле, если (y,y’)∈R−1R, то найдется x∈X такой, что (y,x)∈R−1 и (x,y’)∈R. Эти два условия означают соответственно, что y=f(x) и y’=f(x), откуда y=y’. Обратно, предположим, что выполняются соотношения из формулировки теоремы и покажем, что R функционально. Из RR−1⊃EX вытекает, что для произвольного x∈X найдется такой y∈Y, что (x,y)∈R и (y,x)∈R−1. Значит, y∈R(x) и R(x)≠∅. Следовательно, R определено на всем X, то есть D(R)=X. Далее, пусть (x,y)∈R и (x,y’)∈R. Тогда (y,x)∈R−1 и, значит, (y,y’)∈R−1R. Поскольку R−1R⊂EY, отсюда следует, что y=y’.
Замечание.Из доказательства теоремы видно, что условие RR−1⊃EX равносильно тому, что R определено на всем X. Условие R−1R⊂EY означает, что R(x) состоит ровно из одного элемента для каждого x∈D(R), то есть сужение R на D(R) – функциональное соответствие. Про соответствие R, удовлетворяющее условию RR−1⊃EX , будем говорить, что оно всюду определено, а про соответствие R, удовлетворяющее условию R−1R⊂EY, – что оно является частичным отображением (частичной функцией) и отображает D(R) в Y.
