5. Отношения и функции

Определение. Упорядоченной парой <x,y> называется совокупность, состоящая из двух элементов x и y, расположенных в определенном порядке.

Определение. Две пары <x, y> <u, v> считаются равными тогда и только тогда, когда x=u и y=v.

Определение. Бинарным или двуместным отношением называют множество упорядоченных пар. Элементы x и y называют координатами или компонентами отношения .

Записи <x, y> и x y означают, что пара <x, y> принадлежит бинарному отношению .

Определение. Областью определения бинарного отношения называют множество D_={x | существует такое y, что x y}. Областью значений называют множество R_={y | существует такое x, что x y}.||

Примеры.

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

D_={1,2,3}, R_={2,4,3,1}={1,2,3,4}.

2. {<x, y> | x, y – действительные числа и x=y} - отношение равенства на множестве R действительных чисел (специальное обозначение «=»). D_={x | x R}, R_={y | y R}.

3. {<x, y> | для целых чисел x и y найдется положительное число z такое, что x+z=y} – отношение «меньше чем» на множестве целых чисел (специальное обозначение «<»). D_ и R_ - множества целых чисел.

Определение. Упорядоченным набором длины n или n-кой элементов называется последовательность, состоящая из n элементов x₁, x₂, x₃,…, x_n, расположенных в определенном порядке и обозначается <x₁, x₂, x₃,…, x_n>.

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

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

Определение. Пусть даны n множеств A₁, A₂,…, A_n. Множество всех наборов <x₁, x₂,…, x_n> таких, что x₁A₁,…, x_nA_n называют прямым произведением A₁, A₂,…, A_n и обозначают A₁A₂…A_n или .

Произведение одинаковых множеств обозначается Aⁿ.

При n=2 XY={<x, y> | xX, yY}.

Каждое бинарное отношение  есть подмножество прямого произведения, так что D_X и R_Y. Если X=Y то говорят, что  есть отношение на множестве X.

Примеры

1. Пусть X={0,1}, Y={x,y}. Тогда

XY={<0,x>, <0,y>, <1,x>, <1,y>};

YX={<x,0 >, <x,1>, <y,0>, <y,1>}.

2. X={1,2,3}, Y={0,1}.

XY={<1,0>,<1,1>,<2,0>,<2,1>,<3,0>,<3,1>};

YX={<0,1>,<0,2>,<0,3>,<1,1>,<1,2>,<1,3>}.

(Отметим, что XY YX.)

К отношению «=» принадлежит одна пара <1,1>.

К отношению «<» в множестве YX принадлежат все пары, кроме <1,1>. В множестве X´Y таких пар нет.

3. RR - плоскость.

4. X = {x | x [0,1]}

0

1

Y = {y | y [1,2]}

X Y = {<x, y> | x [0,1], y [1,2]} – множество точек квадрата:

x

0

1

2

1

Определение. Обратным отношением для ={<x,y> | <x,y>} называют отношение ^-1={<y,x> | <x,y>}.

Определение. Композицией отношений r₁ и r₂ называют отношение ₂₁={<x,y> | $ z такое, что <x, z>₁ и <z, y>₂}.

Свойства бинарных отношений

1. ;

2) .

Доказательство п. 2)

<y,x> <x,y>₂₁;

z : <x,z>₁ и <z,y>₂

z : <z,x>₁^-1 и <y,z>₂^-1

z : <y,z>₂^-1 и <z,x>₁^-1

<y,x> _.

_{Сравнивая с исходным соотношением убеждаемся в справедливости равенства 2).}

Пример: система линейных алгебраических уравнений AB , где A и B - матрицы. Операция умножения матрицы на вектор устанавливает соответствие каждому вектору-операнду результата операции . Это соответствие есть отношение .

_{С одной стороны}

.

С другой стороны

; .

Тем самым, .