2. sootvetstviya

1. Соответствия между множествами. Отображения

1

2. Основные понятия.

Пусть даны два множества:
А={а1, а2,...} и В={b1, b2,...}.
Тогда
пары
(ai,
bj )
задают
соответствие между множествами А и
В, если указано правило R, по которому
для
элемента ai множества А
выбирается элемент bj из множества В.
2

3. Основные понятия.

Например:
Х={х1, х2,...} и Y={y1, y2,...}.
Cоответствие между элементами
множеств задает точечное множество
(xi, yj ) координат точек на плоскости;
Русско
английский
словарь
устанавливает
соответствие
значений и написаний слов русского и
английского языков.
3

4. Способы задания соответствия

Теоретический
G= {(1;a), (2;b), (3;k), (4;f)}
Графический
Табличный (матричный)
1
a
b
s
f
k
2
3
4
1000
0100
0000
0001
0010
4

5.

Пусть задано соответствие R между
множествами А и В,
т. е. R: (a; b), a A, b B
Некоторому элементу а множества А
поставлен в соответствие некоторый
элемент b из множества B, который
называется образом элемента а и
записывается
b = R(a).
5

6.

Тогда а = R-1(b) — прообраз
элемента b B
который обладает
свойствами
единственности и полноты:
• каждому прообразу соответствует
единственный образ;
• образ должен быть полным, так же
как полным должен быть и прообраз.
6

7.

Например, если
А — множество
парабол,
В — множество
точек плоскости,
R — соответствие
«вершина параболы»,
то R(a) — точка, являющаяся вершиной
параболы a,
a R-1(b) состоит из всех парабол аi
вершиной в точке b
с
7

8.

Образ множества А при соответствии R
называется множеством значений этого
соответствия и обозначается R(A), если
R(A) состоит из образов всех элементов
множества А.
Запись:
R( A) b | a A, b R(a) .
8

9.

Прообраз множества В при некотором
соответствии R
называют областью
определения этого соответствия и
обозначают R-1(B), т.е.
R-1 является обратным соответствием
для R.
R ( B) a | b B, a A : R(a) b .
1
9

10.

Для описания соответствий между
множествами
используют
понятие
отображения
(функции)
одного
множества на другое.
Функцией
f
,
действующей
из
множества X в множество Y (f: X Y)
называется правило или закон, по
которому каждому элементу x X ставится
в соответствие один или несколько y Y.
10

11. Задание отображений.

Для задания отображения необходимо
указать:
• множество, которое отображается
(область
определения
данного
отображения D(f));
множество,
в
(на)
которое
отображается
данная
область
определения
(множество
значений
этого отображения E(f));
11

12. Задание отображений.

• закон или соответствие между
этими множествами, по которому для
элементов
первого
множества
(прообразов,
аргументов)
выбраны
элементы
(образы)
из
второго
множества.
Приняты записи
A B или f: A В.
f
12

13. Способ задания отображений

Способ задания отображений в виде
формул называется аналитическим.
Существуют
еще
табличный
и
графический способы.
13

14.

Для задания отображения множеств
табличным способом принято строить
таблицу, в которой первую строку
составляют
элементы
области
определения (прообразы вида а), а
вторую
строку — их образы, т. е.
элементы вида (х) при отображении
: а (а), где a A
Такой способ удобен при достаточно
мощности прообраза (не более 10).
малой
14

15.

Графическое
представление
отображения связано со стрелочными
схемами (диаграммами или графами).
Пример
графического
задания
отображения множества А ={а1, а2, а3 } в
В = {b1, b2, b3, b4, b5 }.
15

16.

Отображения f: А В и g: A В
называются равными, если
Отображения
называются
однозначными, если каждому аргументу
поставлено в соответствие не более
одного образа.
16

17.

№1
Примеры решения задач
Пусть : A B, тогда
Область определения соответствия (domain): D( )
Область значений соответствия (range):
E( )
Пусть даны множества А и В
А = { 2, 3, 8 }, В = { 1, 2, 3, 4, 5, 6, 7 },
= {(2, 2), (2, 4), (2, 6), (3, 3), (3, 6)}
Тогда D( ) = {2, 3} A и E( ) = {2, 3, 4, 6} B
17

18.

№2
Пусть дано множество студентов:
A = {Jüri, Mari, Jaan, Juhan, Kati, Mati}
и множество возможных оценок:
B = { 1, 2, 3, 4, 5}
: A B соответствие между множествами А и В, которое
сопоставляет каждому студенту его оценку.
= { (Jüri, 4), (Mari, 5),
(Jaan, 1), (Juhan, 3), (Kati,
B
A
4), (Mati, 5)}
Jüri
•1
Mari
•2
Диаграмма (граф) соответствия: Jaan
•3
Juhan
•4
Kati
•5
Mati
18

19.

№3
Пусть даны множества А и В
А = { 2, 3, 8 }
В = { 1, 2, 3, 4, 5, 6, 7 }.
Соответствием между множествами А и В
«число из А есть делитель числа из В»
A
представляется множеством
= {(2, 2), (2, 4), (2, 6), (3, 3), (3, 6)},
2
3
8
B
•1
•2
•3
•4
•5
•6
• 7 19

20. Виды отображений.

Различают два основных вида
однозначных
отображений
(функций).
По
мощности
они
делятся
на
сюръективные
и
инъективные
20

21. Виды отображений.

21

22. Инъекция

22

23. Инъекция

Примеры
1) Отображение множества студентов
данной
аудитории
на
множество
стульев - инъекция, так как разные
студенты сидят на разных стульях.
2) Отображение множества детей в
городе на множество имен не является
инъекцией, так как есть дети,
имеющие одинаковые имена
23

24. Суръекция

24

25. Сюръекция

Примеры
1) Соответствие между множеством
всех студентов и множеством групп –
сюръективное отображение, так как
каждой группе соответствует хотя бы
один студент
2) Соответствие между множеством
студентов 1 курса техникума
и множеством преподавателей
техникума не является сюръекцией,
так как есть преподаватели, которые не
25
преподают на 1 курсе.

26. Отображение множества А на множество В, при котором каждому элементу множества В соответствует единственный элемент множества

А,
называется
взаимно-однозначным
соответствием
между
двумя
множествами, или биекцией.
26

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

Функция,
которая
является
одновременно
и
инъективной,
и
сюръективной,
называется
взаимно
однозначным
соответствием,
или
биекцией.
27

28. Биекция

Примеры
1)Соответствие между множеством
государств Европы и множеством
европейских столиц - биекция
2) Соответствие между
множеством страниц учебника по
математике и множеством номеров
этих страниц - биекция
28

29.

Два множества эквивалентны, если
между
их
элементами
можно
установить биективное отображение.
Это
образом:
обозначается
следующим
A ~ B.
29

30.

Пусть множество А отображается
взаимно-однозначно на множество В,
т.е f:А В.
Тогда отображение f -1, при котором
каждому
элементу
множества
В
ставится в соответствие его прообраз
из
множества
А,
называется
обратным отображением для f и
записывается
f 1
В А
или
f -1:В А.
30

31.

Так как одному образу при биекции
соответствует в точности один
прообраз, обратное
отображение
будет определено всюду на В и
однозначно (отсюда название).
Для биекции принята запись:
31

32.

Если между элементами множеств
установлено
взаимно-однозначное
соответствие, то эти множества
имеют
одинаковое
количество
элементов.
Говорят, что они равносильны,
равномощны, или эквивалентны.
32

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

Декартово произведение множеств A и B
есть множество всех упорядоченных пар
(a, b) таких, что a A, b B.
A B={ (a, b) | a A, b B }
Множество всех векторов (а1 , а2 , а3 ,…, аn)
длины n таких , что
а1 А1 , а2 А2 , …, аn Аn
Если А1 = А2 = … = Аn , то
А1 А2 … Аn = Аn
Декартова степень
33

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

№4. Найдите декартово произведение
множеств
А={1, 2}, B={3, 4, 5}
А B = { (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5) }
№5. Х = {1,2,3}, У= {0,1}
Х У -? и У Х - ?
Не обладает свойством
коммутативности
Х У= {(1,0), (1,1), (2,0), (2,1), (3,0), (3,1)}
У Х= {(0,1), (0,2), (0,3), (1,1), (1,2), (1,3)}
34

35.

№6. Прямое произведение 2 бесконечных множеств –
числовых отрезков:
[0; 1] [1; 2]
Решение:
Все точки квадрата с вершинами
(0; 1), (0; 2), (1; 1) и (1; 2)
35

36.

Задача №7.
Х={1; 2; 3}, Y={0; 1}. Найти Х У, У Х, n(X Y), n(Y X).
Решение:
Х У= {(1; 0), (1; 1), (2; 0), (2; 1), (3; 0), (3; 1)}
У Х= {(0; 1), (0; 2), (0; 3), (1; 1), (1; 2), (1; 3)}
n(A B) = n(А) n(B)
n(X Y) = 3 2 = 6
n(Y X) = 2 3 = 6
Ответ: n(X Y) = n(Y X) = 6
36

37.

Задача №8.
Найти количество всевозможных двузначных чисел,
которые можно составить из цифр от 1 до 9.
Дано:
Решение:
А={1;2;3;4;5;6;7;8;9} n(A B) = n(А) n(B)
n(A) = 9
n(A2) = (n(А))2
2-узначное число –
упорядоченная пара n(A А) = 9 9 = 81
- кол-во 2-узначных чисел из цифр от 1
Найти:
до 9
n(A А) = n(A2) - ?
Ответ: 81
37

38.

Задача №10.
Определить длину и количество векторов прямого
декартова произведения A B C множеств
A ={1; 4; 7}, B = {0; 2}, C = {5}.
Решение:
1) Длина каждого вектора: 3
2) Количество векторов:
n(A B C) = n(A) n(B) n(C) = 3 2 1 = 6
Проверка:
A B C = {(1;0;5), (1;2;5), (4;0;5), (4;2;5), (7;0;5), (7;2;5)}
38

39.

Рассмотрим примеры отображений.
1)
Каждому
действительному
числу
поставим в соответствие его квадрат.
Отображение х х2 не является взаимно-
однозначным соответствием, так как для
любого
образа
у=х2
можно
найти
два
прообраза в области определения:
х = + у
и
х = - у.
39

40.

Рассмотрим примеры отображений.
2) Различные виды кодирования (азбука
Морзе, представление чисел в различных
системах
счисления,
шифрованные
сообщения) являются чаще всего примерами
взаимно-однозначного
соответствия между
множествами.
40