Пример 1.15

1. Множество {<0, 1>, <1, 1>, <3, 2>} – бинарное отношение.

2. Множество {<x, y>  x, y  действительные числа и  x  равно у} – бинарное отношение равенства двух чисел. Отношение равенства имеет специальное обозначение (=). Поэтому, вместо записи   <x, y>   =  используется запись:  x = y.

3. Отношение "меньше" (<) на множестве целых чисел можно задать через отношение  = следующим образом: <  =  {<x, y>  для целых чисел  x и y найдется положительное целое число z, такое, что x + z = y}.

Декартово произведение множеств

Декартовым произведением множеств Х и Y называется множество Х  Y, элементами  которого является все возможные упорядоченные пары <x, y>, такие, что        x  Х,  у  Y. Иначе:

Х  Y = {<x, y>  x  X и y  Y}.

Очевидно, что каждое отношение , есть подмножество декартового  произведения множеств X и Y, таких, что  D_  X, E_   Y . Если X = Y, то говорят, что   задано на множестве X. В этом случае множество пар вида <x, x>, для всех x  X,  называют диагональю множества X  X  и обозначают id_X.

Аналогично можно определить декартово произведение X₁  X₂  ...  X_n множеств X₁, X₂,.., X_n. Элементами этого множества являются n-ки (кортежи)     <x₁, x₂,..., x_n>.  Если X₁= X₂= … = X_n= X, то прямое произведение этих множеств обозначают через  Xⁿ.

Рис. 1.2. Произведение множеств

 

Пример 1.16

1.      Пусть Х = {0, 1, 2},Y = {1, 2}. 

Тогда Х  Y = {<0, 1>, <0, 2>, <1, 1>, <1, 2>,     <2, 1>, <2, 2>},  а Y  X= {<1, 0>, <1, 1>,            <1, 1>,<1, 2>, <2, 0>, <2, 1>, <2, >}.

Отметим, что в общем случае X  Y  Y  X.

2. Пусть Х – множество точек отрезка [0,1] , а Y – множество точек отрезка [1, 2]. Тогда X  Y – множество точек квадрата (рис. 1.2) с вершинами (0, 1), (0, 2), (1, 1), (1, 2).

Замечание. В связи с тем, что бинарные отношения являются множествами, то для них справедливы все понятия, определения и операции получения новых множеств через заданные множества. Так как элементами этих множеств являются пары, то могут быть введены и другие специфические определения и операции.

Композиция отношений

Обратным отношением для отношения    называется отношение:

 ^-1 = {<y, x>  <x, y>  }.

Заметим, что если    X  Y, то   ^-1  Y  X.

Композицией отношений  ₁  и   ₂    называется отношение:

₁  ₂ = {<x, z>  существует  y,  такое, что <x, y>  ₁  и  <y, z>  ₂ }.

Дополнительно любые бинарные отношения имеют следующие свойства:

1) ( ^-1) ^–1 = ; 

2) (₁  ₂) ^–1 = ₂ ^-1  ₁ ^-1.

Доказательство первого из них очевидно. Приведем доказательство второго свойства.

По определению обратного отношения и композиции отношений, имеем:

(₁  ₂) ^–1 = {<x, y>  <y, x>  ₁  ₂} =

= {<x, y>  существует  z, такое, что <y, z>   ₁ и  <z, x>  ₂} =

= {<x, y>  существует z, такое, что <x, z>  ₂ ^-1 и <z, y>  ₁ ^-1} = ₂^-1  ₁ ^-1.

1.3. Функции

           Определение функции

           Свойства функции

           Композиция функций

           Тождественное отображение

 

Определение функции

Бинарное отношение  f  называется  функцией, если из <x, y>  f  и   <x, z>  f следует, что y = z. 

Так как функции являются бинарными отношениями, которые, в свою очередь, являются множествами, то к ним применим принцип объемности, т.е. две функции f  и  g  равны, если они состоят из одних и тех же элементов. Область определения функции обозначается через D_f , а область ее значений через E_f.

Если  D_f  = X, а  E_f   Y  , то говорят, что функция  f   задана на множестве X  со значениями  во множестве Y и осуществляет отображение множества X во множество Y. Это отображение обозначается так:  f: X  Y.

Если  f – функция, то записи: <x, y>  f  или x f y заменяют записью: y = f(x), подчеркивая то, что понятие функции более узко, чем понятие бинарного отношения в связи с тем, что каждому значению x  X соответствует только одно значение y  Y.