Соответствия. Функции. Отношения

Определение. Будем говорить, что на множестве Х задано бинарное отношение R, если " x, y Î X мы можем определить (по какому-нибудь правилу) находятся эти элементы в отношении R или нет.

Определим понятие отношения более строго.

Введем понятие декартова (прямого) произведение A´B произвольных множеств A и B.

По определению A´B = { (a, b), a Î A, bÎ B}. Аналогично определяется декартово произведение 3-х, 4-х и произвольного числа множеств. По определению A´A´ …´A = Aⁿ.

Определения.

1. Соответствием S из множества A в множество B называется подмножество S Í A´B. Тот факт, что элементы aÎ A, bÎ B находятся в соответствии S, мы будем записывать в виде (a, b) Î S или в виде aSb.

2. Естественным образом для соответствий S₁ и S₂ определяются S₁∩S₂ и S₁U S₂ – как пересечение и объединение подмножеств. Как и для любых подмножеств определяется понятие включения соответствий S₁ Í S₂. Так S₁ Í S₂ Û

из a S₁b Þ a S₂b.

3. Для соответствий S₁ Í A´B и S₂ Í B´C определим композицию соответствий S₁*S₂ Í A´С. Будем считать, что для элементов aÎ A, сÎ С по определению a S₁*S₂ с Û $ bÎ B такой, что a S₁ b и b S₂ с.

4. Для соответствия S Í A´B определим соответствие

S ^-1 Í B´A так: по определению bS ^-1a Û a S b.

5. Пусть по определению соответствие D_AÍ A´A,

D_A={(a,a), aÎ A}.

6. Соответствие F из множества A в множество B называется функцией, определенной на A, со значениями в B (или отображением из A в B), если " aÎ A $! bÎ B такой, что aFb. В этом случае будем писать также aF = b или, более привычно, Fa = b. В этом определении функция отождествляется со своим графиком. В наших обозначениях aF₁*F₂ с можно записать в виде с = (aF₁)F₂ . Композиция F₂ F₁ функций означает по определению, что (F₂ F₁)(a)= F₂(F₁ (a)). Таким образом, F₂ F₁ = F₁*F₂ .

7. Для отображения F из A в B образом подмножества A₁Í A

называется подмножество F(A₁)= {F(a)| aÎ A₁} Í B, а прообразом подмножества B₁ Í B называется подмножество

F ^-1(B₁)= { aÎ A | F(a) Î B₁ } Í A.

8. Отображение F из A в B называется инъекцией, если из

a₁ ¹ a₂ Þ Fa₁ ¹ Fa₂.

9. Отображение F из A в B называется сюръекцией, если

" bÎ B $ aÎ A такой, что Fa = b.

10. Отображение F из A в B называется биекцией или взаимнооднозначным отображением, если F – инъекция и сюръекция одновременно.

11. Биекция конечного (а иногда и бесконечного) множества называется подстановкой.

12. Бинарным отношением на множестве Х называется подмножество R Í X´X. Тот факт, что элементы x, y Î X находятся в отношении R, мы будем записывать в виде (x, y) Î R или в виде xRy.