2.1. Определения и примеры |
|
|
|
|
|
47 |
|||
|
|
|
|
|
|
|
|
|
|
²¯x1 |
x2 ²¯ |
|
|
|
|
|
|
|
|
x1 |
11 |
02 |
03 |
04 |
|
|
|||
±° |
±° |
¢ |
x |
x |
x |
x |
|
||
|
2 |
0 |
1 |
0 |
0 |
|
|
||
q |
q |
x |
|
|
|
||||
²¯x3 |
x4 ²¯ |
x4 |
0 |
0 |
0 |
1 |
|
|
|
q |
q |
x3 |
0 |
0 |
1 |
0 |
|
|
|
±° |
±° |
|
|
|
|
|
|
|
|
Рис. 2.2. Диагональное (единичное) отношение
3. Полное отношение представляется полным графом. Все элементы матрицы полного отношения – единицы.
²¯x1¼- |
x2²¯ |
|
q |
*} |
q |
±° |
|
?±°O |
6 |
~ |
²¯ |
|
||
²¯N i-+ |
||
xq3 |
|
xq4 |
±° |
|
±° |
M £ M |
x1 |
x2 |
x3 |
x4 |
x1 |
1 |
1 |
1 |
1 |
x2 |
1 |
1 |
1 |
1 |
x3 |
1 |
1 |
1 |
1 |
x4 |
1 |
1 |
1 |
1 |
Рис. 2.3. Полное отношение (полный граф)
Соответствие является обобщением понятия Отображения бинарного отношения на тот случай, когда отношение является подмножеством прямого
произведения различных множеств.
Определение. Соответствие ¡ (гамма) между множествами M и L определено, если задано отношение R µ M £ L, где
R = fhx; yijx 2 M; y 2 Lg.
¡ определяет соответствие элементов множества M элементам множества L. При этом говорят, что R — отношение соответствия ¡, M — область определения, а L — область значений ¡.
Соответствие, обратное ¡, обозначается ¡¡1, где L — область определения, а M — область значений ¡¡1.
Определение. Отображением множества M во множество L называется такое соответствие, которое каждому x 2 M сопоставляет по крайней мере один y 2 L.
Обозначение ¡ : M 7!L указывает на то, что ¡ отображает множество M на (во) множество L. При этом говорят, что элемент y 2 L есть образ элемента x 2 M, а x — прообраз (переменная, аргумент) y.
Примеры 2.5.
1. M = fa; b; c; dg; L = fA; B; C; D; Eg;
48 |
Глава 2. Бинарные отношения |
|
|
a b c d
A B C D E
Рис. 2.4. Отображение ¡ : M 7!L
¡a = fBg, ¡b = fDg, ¡c = fB; Eg, ¡d = fEg:
B есть образ a, D есть образ b, B есть образ c, E есть образ c, E есть образ d.
Из любого x 2 M на графе исходит по крайней мере одна дуга, то есть 8x 2 M j¡xj > 1, значит это соответствие есть отображение. 2. Примеры записи отображений. f : A 7!B, ® : R2 7!R (R – множество действительных чисел). J
Определение. Отображение M на L ¡ : M 7!L называется сюръективным (сюръекцией), если любой y 2 L имеет по крайней мере один прообраз, то есть 8y 2 L j¡¡1yj > 1:
В этом случае говорят, что M отображается на L.
Пример 2.6. M = fa; b; c; d; e; fg; L = fA; B; C; Dg;
¡a = fAg, ¡b = fAg, ¡c = fCg, ¡d = fBg, |
¡e = fA; B; Dg, ¡f = fC; Dg; |
|||
¡¡1A = fa; b; eg, ¡¡1B = fd; eg, ¡¡1C = fc; fg, ¡¡1D = fe; fg. |
||||
a |
b |
c |
d |
e f |
A B C D
Рис. 2.5. Сюръекция
Каждый элемент L имеет прообраз, следовательно ¡ — сюръекция. J
Определение. Отображение ¡ : M 7!L называется инъективным (инъекцией), если для каждого элемента y 2 L существует не более одного прообраза (либо y вообще не имеет прообраза), то есть 8y 2
Lj¡¡1yj 6 1:
Вэтом случае говорят, что M отображается в L.
2.1. Определения и примеры |
49 |
|
|
|
|
Пример 2.7. M = fa; b; c; dg; L = fA; B; C; D; E; F g; ¡a = fBg, ¡b = fCg, ¡c = fF g, ¡d = fD; Eg;
¡¡1A = ?, ¡¡1B = fag, ¡¡1C = fbg, ¡¡1D = fdg, ¡¡1E = fdg, ¡¡1F = fcg.
|
a |
b |
c |
d |
|
||||
|
|
r |
|
r |
r@@¢¢ |
|
r |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
¢ |
¢ @ |
|
@ |
|
Ar |
|
|
|
|
|
|
Fr |
||
|
? |
|
? |
¢® |
|
|
? @R |
||
Br |
Cr |
Dr |
Er |
||||||
Рис. 2.6. Инъекция
В каждый y 2 L входит самое большее одна дуга – отображение инъективное. J
Определение. Если отображение ¡ : M 7!L одновременно сюръективно и инъективно, то есть 8y 2 L j¡¡1yj = 1, то оно называется
биективным.
Пример 2.8.
M = fa; b; c; dg; L = fA; B; C; D; E; F g;
¡a = fA; Bg, ¡b = fCg, ¡c = fD; F g, ¡d = fEg;
¡¡1A = fag, ¡¡1B = fag, ¡¡1C = fbg, ¡¡1D = fcg, ¡¡1E = fdg, ¡¡1F = fcg.
a |
b |
c |
d |
|
r |
r |
|||
r |
r |
¢@
¢@
¢@
¢ |
|
|
|
@ |
|
¢ |
? |
? |
? |
? @R |
|
¢® |
Br |
Cr |
Dr |
Er |
Fr |
Ar |
Рис. 2.7. Биекция
В каждый y 2 L входит одна и только одна дуга – отображение биективное. J
Определение. Отображение ¡ : M 7!L, такое, что 8x 2 M j¡xj = 1; называется функцией.
50 |
Глава 2. Бинарные отношения |
|
|
Другими словами, функцией M в L называется такое отображение, которое каждому x 2 M сопоставляет один и только один y 2 L.
Функция может быть сюръективной, инъективной, или биективной.
Примеры 2.9.
r@£r |
r |
r |
rC |
£r |
£@ |
|
C £ |
||
£ |
@ |
|
£C |
|
£ |
|
@ |
£ C |
|
£ |
|
@ £ |
C |
|
£ |
²r |
£@ |
C |
|
°£ |
? |
|
CW |
|
£° |
|
|||
r |
r |
@R6r |
||
Рис. 2.8. Сюръективная функция
r |
r |
r |
r |
r® r° |
r |
N r |
r? r |
Рис. 2.9. Инъективная функция
r r r r r
? |
® |
® |
w |
r |
? |
r |
r6 |
r |
|
r |
Рис. 2.10. Биективная функция
Если функция ¡ биективна, то обратная ей ¡¡1 тоже биективна. В этом случае говорят о взаимно однозначном соответствии.
З а м е ч а н и е. Некоторые авторы определяют отображение как функцию, то есть 8x 2 M j¡xj = 1. Мы же определили для отображения 8x 2 M j¡xj > 1, для функции 8x 2 M j¡xj = 1. I