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

Определение. Будем говорить, что на множестве Х задано бинарное отношение 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. Пусть по определению соответствие _A AA,

_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.

Упражнения.

1. Проверить, что _AS = S, S_B =S S  AB.

2. Проверить, что

(S₁S₂)S₃ = S₁(S₂S₃)  S₁  AB, S₂  BC, S₃  CD.

3. Проверить, что (S ^-1) ^-1 = S  S  AB.

4. Проверить, что (S₁S₂) ^-1 = S₂^-1  S₁^-1  S₁  AB, S₂  BC.

5. Доказать, что если отображения F₁ из A в B и F₂ из B в C являются инъекциями, то F₂F₁ – инъекция.

6. Доказать, что если отображения F₁ из A в B и F₂ из B в C являются сюръекциями, то F₂F₁ – сюръекция.

7. Доказать, что если отображения F₁ из A в B и F₂ из B в C являются биекциями, то F₂F₁ – биекция.

8. Доказать, что для отображения F из A в B соответствие F ^-1 будет отображением из B в A  F – биекция. В этом случае F ^-1 - также биекция, и F F ^-1 =_A , F ^-1 F =_B .

9. Доказать, что для отображения F из A в B

уравнение Fx= b имеет  1 решения b  F – инъекция,

уравнение Fx= b имеет 1 решения b  F – сюръекция,

уравнение Fx=b имеет ровно одно решение b  F – биекция.

10. Доказать, что отображение F из A в B является инъекцией  F F ^-1 =_A.

11. Доказать, что отображение F из A в B является сюръекцией  F ^-1 F =_B.

Пусть S(X) – множество биекций множества Х. Тогда

I.  f, g S(X) f g  S(X) (из упр. 5),

II. 1.  f, g, h S(X) (f g) h = f (gh) (из упр. 2),

2.  _X S(X) (очевидно, _X – биекция из Х в Х и _X(х)=х  х X) и  f S(X) f _X = _X f = f (из упр.1). Биекция _X обозначается ещё id_X или id.

3.  f S(X)  f ^-1 S(X) и f ^-1f = f f ^-1= _X (из упр.6).

Далее множества с такими свойствами мы будем называть группами. Таким образом, S(X) - группа.