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

Пары задают соответствие между множествами A и B, если указано правило R, по которому для элемента множества A выбирается элемент из множества B.
Пусть для некоторого элемента a множества A поставлен в соответствие некоторый элемент b из множества B, который называется образом элемента a и записывается . Тогда - прообраз элемента .
Соответствия между множествами

Соответствия
Соответствие между множествами А и В определяется заданным правилом, согласно которому элементам одного множества сопоставляются элементы другого множества.
Соответствием между множествами А и В называется подмножество ϕ их прямого произведения:
ϕ ⊂ A × B и ϕ : A → B
Про элементы x ∈ A и y ∈ B говорят, что они находятся в соответствии ϕ , если пара (x,y) ∈ ϕ.
ϕ : x → y, x ∈ A, y ∈ B.
Если ( x, y) ∈ ϕ , то иногда пишут x ϕ y ,
y называют образом x, а x - прообразом y.

Пусть ϕ ⊂ A × B и ϕ : A → B, тогда
Область определения соответствия (domain):
Область значений соответствия (range):
D(ϕ) = { a ∈ A | ∃b ∈ B: (a,b) ∈ ϕ } ⊂ A
R(ϕ) = { b ∈ B | ∃a ∈ A: (a,b) ∈ ϕ } ⊂ B
Пример:
Пусть даны множества А и В
А = { 2, 3, 8 }, В = { 1, 2, 3, 4, 5, 6, 7 },
ϕ = {(2, 2), (2, 4), (2, 6), (3, 3), (3, 6)}
Тогда D(ϕ) = {2, 3} ⊂ A и
R(ϕ) = {2, 3, 4, 6} ⊂ B

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

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

Классификация соответствий:
Соответствие ϕ ⊂ A×B всюду определенное, если D(ϕ) = A.
Соответствие ϕ ⊂ A×B на всю область значений определенное,
если R(ϕ) = B.
•
•
•
•
•
•
•
ϕ
A
B
•
•
•
•
•
•
•
ϕ
A
B

ϕ -1 ° ϕ = { (b,b) | b∈B }
Соответствие ϕ ⊂ A×B однозначное, если
∀ a ∈ D(ϕ) ∃! b ∈ R(ϕ) : (a,b) ∈ ϕ
Свойство:
если соответствие ϕ ⊂ A×B – однозначное, то
•
•
•
•
•
•
•
•
ϕ
A
B

Образ множества A при соответствии R называется множеством значений этого соответствия и обозначается , если состоит из образов всех элементов множества А:
Прообраз множества B при некотором соответствии R называют областью определения этого соответствия и обозначают т.е.
является обратным соответствием для R.

Для описания соответствий между множествами используют понятие отображения (функции) одного множества на другое.

Функциональные БО
Бинарное отношение
называется функциональным, если каждому элементу x из X такому, что
соответствует один и только один элемент y из Y.
Все элементы (упорядоченные пары) функционального бинарного отношения имеют различные первые координаты.
Отличительной особенностью матрицы функционального отношения является то, что в каждом ее столбце содержится не более одного единичного элемента. Граф функционального отношения характеризуется тем, что из каждой вершины может выходить только одна дуга.

Функция (отображение)
Определение
Всюду определенное функциональное отношение называется называется функцией или отображением множества X в Y: то есть каждому элементу ставится в соответствие единственный элемент .
- прообраз элемента , .
- образ элемента ,
Замечание
Образ всегда единственный, прообразов может быть несколько.

Пример
А={1,2,3}, B={e,f,g}
G={(1,e), (2,e)} ⊆ A×B
Образы и прообразы
G
образы
прообразы

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

Отображение
Отношение Отношение
Не отображение Отображение

Функция. Пример.
Пусть А = {-2, -1, 0, 1, 2}, a B = {0, 1, 2, 3, 4, 5}.
Отношение f ⊆ A × B определяется как f = {(-2, 5), (-1, 2), (0, 1),
(1, 2), (2, 5)}. Отношение f – функция А из В, так как f ⊆ A × B и каждый из элементов А присутствует в качестве первой компоненты упорядоченный пары из f ровно один раз.
Область определения?
Область значений?
Образ множества {1,2}?
Прообраз множества {5}?

Функция. Пример.
Пусть А = {-2, -1, 0, 1, 2} и В = {0, 1, 2, 3, 4, 5}.
Функция f : A → B определена соотношением f (x) = x2 + 1.
Если Е = {1, 2}, то f(E) = {b : (a, b) ∈ f для некоторого а из Е } =
= {b : b = f(a) для некоторого а из Е } = {2, 5}
является образом Е при отображении f.
Если F = {0, 2, 3, 4, 5}, то f -1(F) = {b : существует а ∈ А такое, что f(a) = b} = {-1, 1, -2, 2} -
является прообразом F, где -1 ∈ f -1 (F), так как f(-1) = 2,
1 ∈ f -1 (F), так как f(1) = 2,
-2 ∈ f -1 (F), так как f(-2) = 5
и 2 ∈ f -1 (F), так как f(2) = 5.
Элементы 0, 3 и 4 не вносят никаких элементов в f -1 (F), поскольку они не принадлежат области значений функции f.

Отображение множеств
Определение
А) Пусть . Образом множества A называют множество .
Б) Пусть . Прообразом множества B называют множество .

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

При записи подразумевается, что отображение f определено всюду на A, т.е. A – полный прообраз отображения f, хотя для B такое свойство полноты не подразумевается.
Однозначным называется отображение, где каждому аргументу поставлено в соответствие не более одного образа.
Отображения можно задавать:
а) аналитически ( с помощью формул);
б) графически ( с помощью стрелочных схем);
в) с помощью таблиц.

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

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

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

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

свойства
Определения
Отображение называется сюръективным, если
.
Б) Отображение называется инъективным, если для любых справедлива импликация
(т.е. «разные элементы переходят в разные»).
В) Отображение называется биективным, если оно сюръективно и инъективно.

Свойства функций.
Функция f называется отображением “на” или сюръективной функцией, или сюръекцией, если для каждого b ∈ B существует некоторое а ∈ А такое, что f(a) = b.
Иначе: всё множество B является областью значений.
Пример.
Не сюръективна Сюръективная

Суръекция

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

Свойства функций.
Функция f : A → B называется инъективной, или инъекцией, если из f(a) = f(a' ) следует а=а'.
Иначе: для любого элемента из области значений существует только 1 прообраз.
Пример.
Не инъективна Инъективная

Инъекция

Инъекция
Отображение множества студентов данной аудитории на множество
стульев - инъекция, так как разные студенты сидят на разных стульях.
2) Отображение множества детей в Вашем городе
на множество имен не является инъекцией, так как есть дети,
имеющие одинаковые имена
3) Является ли инъекцией отображение множества людей,
проживающих в Вашем доме на множество номеров квартир?
Почему?
Примеры

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

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

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

Свойства функций. Пример.
Пусть А и В - множества действительных чисел и f : A → B определена таким образом: f(х) = 3x + 5.
Функция f инъективна, так как если f(a) = f(a' ), тогда 3а + 5 = 3а' + 5 ⇒ а = а' .
Функция f является также сюръективной:
Для любого действительного числа b требуется найти такое а, что f(a) = b = 3a + 5. ⇒ а = (1/3)(b – 5), тогда f(a) = b.
Поэтому f представляет собой взаимно однозначное соответствие.

Свойства функций. Пример.
Пусть А и В – множество действительных чисел, и функция f : A → B определена как f(x) = x2. Функция f не является инъективной,
так как f(2) = f(-2), но 2 ≠ -2.
Функция f не является также и сюръективной, так как не существует такого действительного числа а, для которого f(a) = -1.
Если А и В - множество неотрицательных действительных чисел, тогда f является как инъективной, так и сюрьективной.

Обратная функция.
Пусть f – функция из множества А во множество В, то есть f : A → B .
f ⊆ A × B, так как f является отношением на A × B.
Обратное отношение f -1⊆ B × A определяется как
f -1= {(b, a): (a, b) ∈f }.
При этом отношение f -1 может не быть функцией из В в А, даже если f является функцией из А в В.
Если f -1 действительно является функцией, то ее называют обращением функции f, или ее обратной функцией.
Пример. Функции f(х) = 3x + 6 и f(x) = x2 имеют обратные функции?

Обратная функция. Пример.
Требуется найти обратную функцию для y = 3x + 6.
Обращая функцию, получается
{(y, x): y = 3x + 6}.
Это тоже самое, что
{(x, y): х = 3у + 6}.
Решение этого уравнения относительно у:
{(x, y): у = (х - 6) / 3}.

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

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

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

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

Рассмотрим примеры отображений.
2) Англо-русский словарь устанавливает соответствие между множествами слов английского и русского языков. Такое соответствие не является однозначным, так как каждому английскому понятию соответствуют различные варианты перевода на русский язык, и наоборот.

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

Отображение е: А ? А называется тождественным (единичным), если каждому аргументу оно ставит в соответствие себя.
Очевидно, такое отображение можно задать на любом непустом множестве.
Если е(х) = х, то Е(е) = D(e) = А.
Очевидно, что отображение, обратное единичному, также единичное.

Обратная функция. Теорема 1.
1) Если f : A → B является биекцией. То обратное отношение f -1 является функцией из В в А, причем биекцией.
2) Обратно, для f : A → B, если f -1 – функция из В в А, то f является биекцией.

Обратная функция. Теорема 2.
Если f : A → B является биекцией, то
a) f (f -1(b)) = b для любого b из B;
б) f -1 (f (a)) = a для любого a из A.
Доказательство:
Пусть b ∈ B и а = f -1(b). Тогда f(a) = b.
Поскольку a = f -1(b)), то f (f -1(b)) = f(a) = b.
Аналогично доказывается
f -1 (f (a)) = a для любого a из A.

Обратная функция. Теорема 3.
Если f : A → A и I - тождественная функция на А,
то I ° f = f ° I = f .
Если для f существует обратная функция,
то f ° f -1 = f -1 ° f = I.
Прим. Тождественная функция – это функция, переводящая элемент сам в себя. Например, f(x) = x.

Композиция функций.
Пусть заданы отображения f1: А?В и f2: B?C. Отображение f: А?C, при котором каждому элементу х∈А соответствует определенный элемент z∈С, такой, что
z = f2(y), где y=f1(x), называется произведением, композицией, или суперпозицией отображений
f1 и f2.

Композиция функций.
Теорема:
Пусть g : A → B и f: B → C.
Тогда
а) композиция f °g есть отображение из А в С. Обозначение f ° g : A → C;
б) если а ∈ А, то (f °g)(a) = f (g(a)).

Композиция функций. Примеры.

Композиция функций. Теорема.
Пусть g : A → B f : B → C . Тогда
а) если g и f - сюръекции А на В и В на С соответственно, то f °g есть сюръекция А на С. Иначе: композиция двух сюръекций – сюръекция.
б) если g и f - инъекции, то f °g - также инъекция.
Иначе: Композиция двух инъекций – инъекция.
в) если g и f - биекции, то f °g - также биекция.
Иначе: Композиция двух биекций – биекция.
г) (f ° g) -1 = g -1 ° f -1.

Повторение

Примеры
Функциональное бо
Не отображение
Не функциональное бо
Не отображение

Классификация отображений по мощности
На множество
«сюръекция»;
На множество
«биекция»;
Во множество
«инъекция».

На множество - «сюръекция»
Соответствие. при котором каждому элементу множества А указан единственный элемент множества В, а каждому элементу множества В можно указать хотя бы один элемент множества А, называется отображением множества А на множество В
А
В

На множество - «биекция»
Отображение множества А на множество В, при котором каждому элементу множества В соответствует единственный элемент множества А, называется взаимно-однозначным соответствием между двумя множествами, или биекцией.
А
В

Во множество - «инъекция»
Соответствие. при котором каждому элементу множества А указан единственный элемент множества В, а каждому элементу В соответствует не более одного прообраза из А, называется отображением множества А во множество В.
А
В

Примеры
Инъективное, не сюръективное
отображение
Не инъективное, сюръективное
отображение

Примеры
Не инъективное, не сюръективное
отображение
Инъективное, сюръективное
отображение – биекция

Примеры
7) Список студентов – биекция между номером и фамилией.
8) , где - множество экзаменов в сессии, - множество оценок.
- не инъекция, не сюръекция.
9) Определить множества, на которых отображение является биекцией.
не сюръекция, не инъекция,
сюръекция, не инъекция,
сюръекция, инъекция – биекция.