Соответствия, отображения (функции),

БИНАРНЫЕ ОТНОШЕНИЯ И ОПЕРАЦИИ

Соответствие

Пусть A, В-множества. Соответствием из A в В на­зывается произвольное подмножество Fдекартова произведе­ния .

При этом множество Aназывается областью отправле­ния соответствия F, а B-его областью прибытия. Таким образом, всякое соответствие определяется тройкой множеств < F, A, B>, где .

Два соответствия < F, A, B> и  называют­ся равными тогда и только тогда, когда , и  . Запись  означает, что Fявляется соот­ветствием из A в В (т.е. ).

Если (а, b) , то bназывают образом элемента aпри соответствии F. Вместо записи (а,b)   часто используется aFbили .

Таким образом, множество F можно рассматривать как некоторое множество стрелок, начало которых принадле­жит области отправления соответствия, а конец - области прибытия.

Если множества А и В зафиксированы, то для задания соответствия из A в В достаточно определить множество F.

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

Примеры:

1. Пусть А = {1,2,3},В = {a, b}, F ={(1,a),(2,a),(2,b)}

2. Пусть А, Втакие же, как и в предыдущем пункте. Тогда то же множество F может быть указано как множество стрелок (рис. 3).

3. Пусть А = В = N - множество положительных целых чисел. Множество Fесть область истинности предиката " х - делитель у ", т.е. F= {(x, у) \ x - делитель у}.

§2. Отображение (функция)

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

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

Для отображений принята специальная терминология: область отправления именуется областью определения; а область прибытия - областью значений.

Подчеркнем, что отображение f: X ® Y определено лишь в том случае, когда каждый элемент х Î X имеет во множе­стве Y единственный образ у ÎY.

Это обстоятельство записывается в виде равенства y = f(x), которое обозначает, что "элемент у есть образ эле­мента х при отображении f " или "элемент х есть прооб­раз элемента у при отображении f ".

Отметим, что в общем случае для соответствия F исполь­зование равенства у = F (х) может привести к противоречию.

Например, если при соответствии F: X ® Y элемент x Î X имеет два различных образа , то запись   и приводит к абсурду .

Если множество G Í X, то через f(G) обозначается мно­жество образов всех элементов множества G:

Множество f(G)называется образом множества G при отображении f.

Пример. Пусть отображение f:R®R определяется как    и G={ x | -1< x <2}. Тогда f(G) = { y = f(x) | 0 < y < 4}

§ 3. Сужение отображения. График. Последовательность

Пусть имеем отображение f: X ® Y, и пусть G Í X.

Тогда отображение f всякому элементу из G ставит в соответствие некоторый элемент из Y, стало быть, оно опре­деляет отображение .

Отображение  в этом случае называют сужением ото­бражения f на множество G (рис. 4).

П р и м е р 1. Отображение , определенное для xÎ Z, есть сужение на Z отображения  множества R на R.

Множество пар { x, f(x) }, являющееся подмножеством про­изведения Х ´ Y, называется графиком функции f(x) (рис. 5).

П р и м е р 2. Множество пар являющееся под­множеством произведения , составляет график; показательной функции  (рис. 6).

Возьмем N - множество натуральных чисел, в качестве Y -произвольное множество.

Отображение f: N ®Y называется последовательностью элементов из Y.

Таким образом, последовательность f связывает каждое натуральное число п с некоторым элементом  из Y.

Последовательность f будем обозначать  или сокращенно  Здесь символы  являются образами чисел из N. Например, запись означает последовательность рациональных чисел вида .

§ 4. Типы отображений

Пусть f: X ® Y - отображение. Тогда каждому элементу х Î X соответствует единственный элемент у Î Y, с дру­гой стороны, элемент у Î Y   может быть образом нескольких элементов из X.

Например, значение -6 служит для функции образом значений -3, 1, 2. Множество элементов х Î X, име­ющих в качестве образа при отображении f один и тот же элемент у Î Y, называется множеством прообразов элемен­та у и обозначается :

Пусть В Í Y, Тогда через  обозначается множест­во всех прообразов элементов, принадлежащих множеству В,

1. Отображение f: X ® Y называется сюръективным, или сюръекцией, или отображением, на множество Y, если каждый элемент у Î Y из области его значений имеет хотя бы один прообраз, т.е. множество  не пусто для всякого элемента у Î Y.

Очевидно, что отображение f: X ® Y является сюръек­цией тогда и только тогда, когда f(X) = Y. Заметим, что в этом утверждении равенство f(X) = Y можно заменить рав­носильным ему равенством: .

Примеры:

а)    Пусть X = У = R. Отображение f, определяемое формулой , задает сюръективное отображение множества X на множество Y.

б)    Пусть X = У = R. Отображение f, определяемое фор­мулой , есть отображение R на R, поскольку любое действительное число является кубом некоторого действи­тельного числа. Напротив, если X = У = Z, то отображение множества Z в Z уже не будет сюръекцией, поскольку целое число может не быть кубом целого числа. На­пример, Æ.

в) Пусть снова X = У = R. Отображение f, определяемое формулой , есть отображение в Y. Это отображе­ние не сюръективно, т.к. отрицательные числа из Y не имеют прообразов при отображении f.

2. Говорят, что отображение f: X ® Y является взаим­нооднозначным или инъективным, если образы любых двух различных элементов различны, т.е. из неравенст­ва  вытекает .

3. Отображение f: X ® Y называют биективным или биекцией, если оно одновременно инъективно и сюръектив­но, т.е. если каждый элемент Y является образом некоторого единственного элемента из X.

Примеры:

Отображение, заданное на рисунках:

7 а) - сюръективно, но не инъективно;

7 б) - инъективно, но не является сюръекцией;

7 в) - биекция;

7 г) - не обладает ни одним из указанных свойств.

Отображение f: X ® Y, определенное равенством f(x) = х, называется тождественным, и обозначается: . Если X Í Y, то отображение f: X ® Y, определенное равенством f(x) = х, называют канонической инъекцией.

§ 5. Композиция отображений, обратимые отображения

Пусть X, Y, Z - множества f: X ® Y и g: Y ® Z - ото­бражения. Отображение h: X ® Z, определяемое формулой h(x) = g(f(x)) называется композицией, или суперпозицией, или произведением отображений f и g и обозначается через .

В том случае, когда f и g именуются функциями, называется сложной функцией.

Теорема 1. Композиция отображений обладает следую­щими свойствами:

1) если f: X ® Y, g: Y ® Z и h: Z ® W - отображе­ния, то  (ассоциативность композиции);

2) для любого отображения f: X ® Y имеют место равенства и .

Пусть f: X ® Y, g: Y ® Z и h: Z ® W,  т.е. , то . Действительно, для любого x Î X имеем:

 

 

,

т.е.  и значит ,

Пусть f: X ® Y - отображение. Тогда , т.е. . Аналогично доказывается равенство .

Замечание. Композиция отображений в общем случае не обладает коммутативностью, существуют отображения f и j,  что произведения  и одновременно определены, но не равны между собой, .

Например, пусть f: R ® R, , j: R ® R, j (x) = sin x. Тогда . С другой стороны, . Очевидно, что и - различные функции, т.е. .

Отображение f: A ® B называется обратимым, если существует отображение j: B ® A такое, что

 и                                            (*)

Отображение j, удовлетворяющее равенства (*), называется обратным к отображению f.

  Критерием обратимости отображения служит теорема 2

Теорема 2. Отображение обратимо тогда и только тогда, когда оно биективно.

Необходимость. Пусть f: A ® B - обратимое отображение. Тогда, по определению, существует отображение j: B ® Aтакое, что выполняются оба равенства (*).

Покажем, что отображение f сюръективно. Пусть . Тогда, используя равенство , получим , откуда следует, что -прообраз элемента b при отображении f. Следовательно, f - сюръективно.

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

Достаточность. Пусть f: A ® B - биективное отображение. Тогда ввиду сюръективности отображения f

.

В силу инъективности f для любого элемента мно­жество   не может содержать более одного элемента и, следовательно, оно одноэлементно.

В силу этого в дальнейшем для любого биективного ото­бражения f под символом   условимся понимать не множество, а элемент, из которого состоит это множе­ство.

Тогда соответствие j  из В в А, при котором образом произвольного элемента  является элемент , есть отображение.

Теперь для доказательства обратимости отображения f достаточно проверить справедливость равенств (*).

1 Пусть а Î А. Тогда

т.е.

2. Далее, пусть . Тогда, по определению , откуда . Следовательно, . Таким образом, f - обратимо.

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

Следствие. Если отображение f: A ® B обратимо, то оно имеет единственное обратное к нему отображение.

Доказательство. Пусть отображение f: A ® B- обратимо. Тогда, в силу теоремы 2, отображение f - биектив­но. Обозначим через отображение, обратное к f, построенное в доказательстве теоремы 2, т.е.

для любого .

Пусть - произвольное отображение, обратное к f. Тогда , , , .

Используя эти равенства и ассоциативность композиции отображений (теорема 1), получим

для произвольного .

Таким образом,   Следствие доказано. Это следствие дает основание ввести стандартное обозна­чение отображения, обратного к данному:

если f биективно, то через    обозначается отобра­жение, обратное к f.

Напомним, что для любого элемента , по определению,  - есть прообраз b при отображении f. Таким образом, равенства

  и

является определяющим для отображения .

Упражнения:

1. Пусть f: X ® Y - отображение. Докажите справедли­вость следующих импликаций:

(а) А Í В ® f(А) Í f(В) для любых подмножеств A и В множества X;

(b) C Í D ® для любых подмножеств C и D множества Y.

2. Пусть f: X ® Y - отображение, A и В - произвольные подмножества множества X. Докажите

справедливость следующих соотношений:

(а) ;

(b) ;

(c) .

3. f: X ® Y – инъекция, А Í В Í X. Докажите, что .

4. Пусть f: X ® Y – отображение, С и D – произвольные подмножества множества Y. Докажите справедливость следующих равенств:

(a) ;

(b) ;

(c) .

5. Пусть f: X ® Y – отображение. Доказать равносильность следующих утверждений:

(а) f - сюръективно;

(Ь) f(A) = В;

(с)    ( Æ).

6. Пусть  (i = 1, 2, 3) и для любого    

Найти композиции  и (i = 1, 2, 3).

7. Пусть A = {1, 2, 3, 4},

                              

Построить  и .

8. Пусть f: A → B – отображение. Докажите, что f является биекцией тогда и только тогда, когда множество   одноэлементно для любого b Î B.

9. Докажите, что отображение f: A → B инъективно тог­да и только тогда, когда для любого элемента b Î B множество  либо пусто, либо одноэлементно.

10. Какие из отображений, указанных в упражнении 6, сюръ-ективны, инъективны, биективны?

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

12. Два отображения называются однотипными, если оба они одновременно инъективны, сюръективны, либо биектив­ны.

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

13.Докажите, что если отображение f обратимо, то обрат­ное к нему отображение  биективно и имеет место равенство .

14. Докажите, что если композиция  инъективна (сюрьективна), то один из сомножителей f либо j также инъективен (сюрьективен).

15. Пусть f и g - обратимые отображения. Докажите, что если их композиция существует, то 

.

§6. Бинарные и п -арные отношения

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

Для того, чтобы увидеть подходы к определению этого по­нятия, обратимся сначала к примеру.

Пусть А = {1,2,6}. Тогда свойство "меньше" выделяет в декартовом квадрате А² подмножество S = {(1,2), (1,6), (2,6)}, состоящее из тех и только тех пар чисел, у которых первое число меньше второго.

Аналогично подмножество

F = {(1,1),(2,2),(6,6),(1,2),(1,6),(2,6)}                    (4)

характеризует свойство "делимости" чисел на множестве A. А именно, число х делит у тогда и только тогда, когда (x, y) Î F.

Таким образом, если множество  Fизвестно заранее, то для положительного ответа на вопрос "является ли число делителем b?" достаточно убедиться в том, что (а, b) Î F.

Этим рассуждением мы вплотную приблизились к понятию бинарного отношения.

Определение. Любое подмножество S Î А² декартова квадрата множества А называется бинарным отношением определенным на множестве А.

Из определения соответствия вытекает, что бинарное отношение на множестве А может быть определено как соответствие из А в А.

Если пара (x, у) Î S, где x, у  Î А, то говорят, что элементы х и у находятся в отношении S. Вместо записи (x, у) Î S используется также х Sу или S(x,у).

Отметим некоторые наиболее распространенные способу задания бинарных отношений:

1)    Бинарное отношение может быть задано перечислением его элементов.

Например, как уже отмечалось, множество F, заданное ра­венством (*), определяет бинарное отношение "делимости" на множестве А == {1, 2, 6}.

2)    Бинарное отношение можно рассматривать как область истинности двухместного предиката.

Например, отношение F, о котором говорится в пункте 1), совпадает с областью истинности предиката

Р(х,у): " x делит у".

3)    Бинарное отношение как частный случай соответствия
может быть задано с помощью стрелок.

Например, отношение F, определенное равенством (*), может быть задано следующим образом:

Такой рисунок часто называют диаграммой или графом отно­шения F.

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

3) В случае, когда бинарное отношение задается на множестве действительных чисел R, множество принадлежащих ему пар может быть изображено точками плоскости. Это дает геометрическую иллюстрацию соответствующего отношения. Например, множество пар (x, у),

для которых выполняется x > y, представляет множество точек плоскости, лежащих под прямой y = x (см. рис. 9).

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

.

Из определения вытекает, что отношение S(x, x), опреде­ляемое множеством D, является равенством.

В предыдущем примере (рис. 9) диагональю D множества S´S будет множество точек прямой у = х.

Заметим, что понятие бинарного отношения может быть распространено на более общую ситуацию. Для этого доста­точно в определении бинарного отношения заменить слова "де­картов квадрат" словами "декартова степень".

Определение. Пусть А - множество и п - произвольное натуральное число. Тогда любое подмножество  де­картовой степени множества А с показателем п называ­ется п-арным отношением на множестве А.

В частности, при n = 2 получаем определение бинарного отношения. При n = 1 отношение называется унарным.

Отметим далее, что в математических рассуждениях слова п-арное отношение и п-местный предикат часто используются как синонимы.

Проиллюстрируем эту связь для случая п = 2.

Как мы уже отмечали, область истинности любого двух­местного предиката Р(х, у) является бинарным отношени­ем. Обратно, если S - бинарное отношение на множестве А, т.е. S Í А× А, то, определив Р{х,у) как предложение пара (х у) принадлежит множеству S, мы получим предикат, область истинности которого совпадает с исходным бинарным отношением S.

Таким образом, называя бинарное отношение предикатом, мы подразумеваем при этом двухместный предикат, обла­стью истинности которого является данное отношение. Это соглашение относится и к произвольным п-арным отноше­ниям.