Как найти образ соответствия

Рассмотрим
два непустых множества А
и В.
Элементы этих множеств могут каким-либо
образом сопоставляться друг другу,
образуя пары (а,
b).
Если задан способ такого сопоставления,
то говорят, что между множествами
установлено соответствие. При этом
совершенно необязательно, чтобы в
сопоставлении участвовали все элементы
множеств А и В.

Соответствием
между множествами А и В называется любое
подмножество G

АВ
– декартово произведения этих множеств.

Множество
А иногда называют областью
отправления соответствия
G,
а множество В – областью
прибытия.

График
этого соответствия – множество
упорядоченных
пар (а,
b)
соответствия G.

Обозначается
соответствие так:

G:
AB
или G

АВ
= {(a,
b)aA,
bB,
(a,
b)G}.

Первой
проекцией
или областью
определения
соответствия G
называется множество всех первых
компонентов пар (а,
b)G.
Обозначается

пр₁
G или
Dom(G)
= {a
aA,
(а,
b)G}.

Второй
проекцией
или областью
значений
соответствия G
называется множество всех вторых
компонентов пар (а,
b)G.
Обозначается

пр₂
G
или
Im(G)
= {bbB,
(а,
b)G}.

Каждый
элемент bB,
соответствующий элементу aA,
называется образом
этого элемента
a
. Множество всех образов элемента aA
будем обозначать δ(a,
G)
= {bbB,
(а,
b)G}.

Каждый
элемент aA,
соответствующий элементу bB,
называется прообразом
элемента b.
Множество всех прообразов элемента bB
будем обозначать δ^─1(b,
G)
= {aaA,
(а,
b)G}.

Очевидно,
что множество всех образов всех элементов
aA
есть ни
что иное, как множество значений
соответствия G (его вторая проекция), а
множество всех прообразов всех элементов
bB

множество определения соответствия G
(его первая проекция).

Пусть
ХА,
а YB.
Образом
множества Х
при данном соответствии G
называется
такое множество

Г(X,G)
= {b
b=δ(x,G),
x

X,
b

B}.

Прообразом
множества Y
называется множество Г^─1(Y,G)
= {x
x

A,
y

Y,
(x,
y)

G}.

Рассмотренное
выше соответствие относится к двум
множествам и поэтому носит название
бинарного
соответствия.
Однако этот понятие распространяется
на любое конечное число множеств.
Рассмотрим, например, декартово
произведение n
непустых
множеств: А₁
А₂
…А_п.
Рассмотрим какое-либо подмножество G
этого произведения, то есть отберём
элементы произведения, удовлетворяющие
некоторому условию

G

А₁
А₂
…А_п
=

=
{(a₁,
a₂,
…a_n)

a₁A₁,
a₂A₂,…,
a_nA_n,
(a₁,
a₂,
…a_n)G}.

Это
подмножество называют п-местным
соответствием
на множестве А₁
А₂
…А_п.
Подобные многоместные соответствия
используются в теории баз данных.
Предметом же нашего рассмотрения будут
бинарные соответствия.

Задача
4.4.1.
Рассмотрим
экзаменационную ведомость студенческой
группы и установим соответствия между
студентами и полученными ими оценками.

Табл.4.1

Решение.
Обозначим множество студентов через А
= {Б, В, М, Я},
множество оценок через B
= {2, 3, 4, 5}. Тогда соответствие G

AB
= {(Б,5), (Б,4), (Б,2), (В,2), (В,3), (В,5), (М,3), (М,5),
(Я,4), (Я,5)}. Некоторые упорядоченные пары
встречаются несколько раз, но мы их
записываем только один раз.

Первая
проекция (или область определения)
соответствия:

пр₁G
= Dom(G)
= {Б,В,М,Я}, вторая проекция (область
значений):

пр₂
= Im(G)
= {2,3,4,5}.

Образ
Б: δ(Б,G)
= {2,4,5}; образ В: δ(B,G)
= {2,3,5};

образ
M:
δ(M,G)
= {3,5}; образ Я:
δ(Я,G)
= {4}.

Прообраз
2: δ^─1(2,G)
= {Б,В};
прообраз 3: δ^─1(3,G)
= {В,М};
прообраз 4: δ^─1(4,G)
= {Б,Я};
прообраз 5: δ^─1(5,G)
= {Б,В,М}.

Задача
4.4.2. Дано
соответствие G
= {(a,2),
(b,1),
(b,5),
(d,4)}
для множеств А= {a,
b,
c,
d}
и B
= {1, 2, 3, 4, 5}. Найти образ множества X
= {a,
b}
и прообраз множества Y
= {3, 4}.

Решение.
Найдём образы элементов множества Х:
δ(а,G)=2;
δ(b,G)={1,5}.
Объединяя эти элементы в одно множество,
получим образ множества Х: Г(Х,G)
= {1,2,5}.

Найдём
прообразы элементов множества Y:
δ^─1(3,G)
= ;
δ^─1(4,G)
= d
. Поэтому
прообразом множества
Y
будет множество, состоящее из одного
элемента: Г^─1(Y,G)
= {d}.
Пустое множество 
является частью любого множества,
поэтому записи {,
d}
и { d
} выражают одну и ту же мысль.

Задача
4.4.3. Найти
образ отрезка [1, 10] при соответствии y
= lg
x.

Решение.
Функция
y
= lg
x
является
непрерывной и монотонной на множестве
(0, ∞) – множество А, область её изменения
(-∞, ∞) – множество В. G
= {(x,
y)|
xA,
yB,
y
= lg
x}.
Значению х=1
соответствует у
= lg1
= 0, значению х=10
соответствует у
= lg10
= 1. Следовательно, образом отрезка [1,
10] будет отрезок [0, 1].

Задачи для
самостоятельного решения.

1.
Дано соответствие G = {(a,4), (b,3), (b,2), (с,3),
(d,4)} для множеств А= {a, b, c, d} и B = {1, 2, 3, 4}.
Найти образы и прообразы элементов
множеств А и В, а также и прообраз множеств
X = {b, d} и Y = {2, 4}.

2.
Найти прообраз отрезка [-1, 1] при
соответствии y = sin x. (ответ – вся числовая
ось).

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Соответствия и бинарные отношения на множествах

Отображение из множества в множество считается заданным, если каждому элементу сопоставлен единственный элемент . Отображение из множества в множество обозначают записью или . Элемент , который отображением сопоставляется элементу , называют образом элемента при отображении и обозначают .

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

Наоборот, пусть в декартовом произведении задано такое подмножество , что:

1) для любого существует , для которого ;
2) для любых двух пар и множества из равенства следует равенство .

Тогда множество единственным образом определяет некоторое отображение из в . Это отображение, обозначаемое также , элементу сопоставляет элемент , удовлетворяющий условию . Таким образом, мы можем отождествить отображения с их графиками и считать, что отображение есть подмножество декартова произведения.

Отображение множества в себя называют тождественным, если при всех из .

В общем случае для отображения может существовать несколько различных элементов множества , образы которых совпадают. Множество всех элементов , для которых , называют прообразом элемента при отображении .

Так, прообраз числа при отображении есть множество всех решений уравнения , т.е. множество

Прообраз элемента может быть пустым множеством. Это имеет место, например, для числа при отображении .

Множество всех , таких, что найдется , для которого , называют областью значений отображения . Область значений отображения будем обозначать .

Отображение называют инъективным (инъекцией), если каждый элемент из области его значений имеет единственный прообраз, т.е. из следует .

Отображение называют сюръективным (сюръекцией), если его область значений совпадает со всем множеством . Сюръективное отображение из в называют также отображением множества на множество .

Отображение называют биективным (биекцией), если оно одновременно инъективно и сюръективно.

Таким образом, если отображение биективно, то каждому элементу множества отвечает единственный элемент множества и наоборот. Тогда говорят, что множества и находятся между собой во взаимно однозначном соответствии.

Биекцию множества на себя называют автоморфизмом множества . Используют также термин «подстановка множества».

Пример 1.2. а. Отображение, заданное равенством , есть, как нетрудно показать, биекция множества натуральных чисел на его подмножество .

б. Отображение есть биекция множества всех натуральных чисел на множество всех четных натуральных чисел.

в. Любая показательная функция , есть биекция множества всех действительных чисел на множество всех положительных действительных чисел.

г. Функция есть биекция множества на интервал .

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

Образ и прообраз множества

Пусть задано отображение и — некоторое множество. Множество элементов , таких, что , называют образом множества при отображении . Например, при отображении отрезок является образом множества (отрезка) , равно как и любого объединения отрезков вида (для произвольного целого ). При это можно записать следующим образом: .

Заметим, что для любого отображения образ всего множества есть область значений данного отображения.

Для произвольного множества множество всех элементов , таких, что , называют прообразом множества при отображении .

Например, для любого действительного числа множество, которое является объединением всех отрезков вида

есть прообраз отрезка при отображении .

Прообраз области значений произвольного отображения совпадает со всем множеством .

Множество всех отображений из в будем обозначать как .

Частичное отображение и его область определения

Понятие отображения можно обобщить. Обобщение может проходить по двум позициям. Во-первых, можно отказаться от полной определенности отображения, полагая, что образ определен не для каждого элемента множества , а для некоторых элементов этого множества. Тогда придем к понятию частичного отображения. При этом подмножество всех элементов , для которых определен образ, называют областью определения данного частичного отображения.

Многие элементарные функции являются частичными отображениями множества всех действительных чисел в себя. Например, функция есть частичное отображение с областью определения

Во-вторых, можно отказаться от однозначности отображения, полагая, что данному сопоставлен не один, а несколько образов (множество образов) в множестве . В этом случае говорят, что задано соответствие из множества в множество .

Примером могут служить обратные тригонометрические функции: скажем, «большой» арксинус, сопоставляющий каждому множество всех таких чисел , что , т.е. множество, являющееся прообразом элемента при отображении, определяемом графиком функции .

Если задано соответствие из в , будем использовать обозначение по аналогии с обозначением для отображений, понимая при этом, что есть уже не элемент множества , а его подмножество.

Аналогично графику отображения можно определить график соответствия из множества в множество как множество упорядоченных пар , таких, что и элементы связаны соответствием , то есть . Указанное множество упорядоченных пар есть подмножество декартова произведения .

Обратно, фиксируя на декартовом произведении какое-либо подмножество , мы тем самым однозначно определяем некоторое соответствие из в , а именно

Нетрудно заметить, что графиком соответствия будет как раз множество , а соответствием, отвечающим графику , будет . Поэтому можно отождествить соответствие с его графиком и считать, что соответствие из множества в множество есть некоторое подмножество декартова произведения , то есть . В частности, при получаем пустое соответствие, а при , совпадающем со всем указанным декартовым произведением, — универсальное соответствие.

При этом будем писать для упорядоченных пар, связанных соответствием .

Используют также термины «частичное мультиотображение» и «частичная многозначная функция».

Пример 1.3. Рассмотрим множество программистов и множество программ . Зададим соответствие из в , связывающее программистов и разрабатываемые ими программы:

Область определения соответствия из множества в множество — это множество всех первых компонент упорядоченных пар из

Область значения соответствия — это множество всех вторых компонент упорядоченных пар из

Из определения вытекает, что . Соответствие из в называют всюду определенным, если его область определения совпадает с множеством .

Сечением соответствия для фиксированного элемента будем называть множество . Можно сказать, что сечение соответствия есть множество всех «образов» элемента при данном соответствии.

Сечением соответствия по множеству будем называть множество

Пример 1.4. Область определения соответствия т из примера 1.3 есть все множество , а область значения — все множество . Сечением соответствия по элементу будет множество .

Бинарные отношения на множествах

Соответствие из множества в себя, т.е. подмножество множества , называют бинарным отношением на множестве .

Пример 1.5. Простейшим примером бинарного отношения является отношение нестрогого неравенства на множестве действительных чисел . Здесь каждому поставлены в соответствие такие , для которых справедливо .

Для произвольного бинарного отношения на некотором множестве часто используют запись вместо , говоря при этом об элементах, связанных бинарным отношением . Это согласуется с традиционной формой записи некоторых часто используемых бинарных отношений. Так, пишут , а не . Для таких бинарных отношений употребляют устоявшиеся словосочетания. Например, запись читается так: « не больше «.

Бинарное отношение на множестве , состоящее из всех пар , т.е. пар с совпадающими компонентами, называют диагональю множества и обозначают . Нетрудно понять, что диагональ есть тождественное отображение на себя.

Иногда говорят о диагонали в множестве , хотя правильнее было бы называть это отношение диагональю декартова квадрата множества .

Для наглядного изображения соответствий из в (бинарных отношений, в частности) будем использовать два способа. Первый из этих способов состоит в интерпретации соответствия как подмножества декартова произведения, которое можно изображать примерно так же, как на плоскости можно изображать подмножества декартова квадрата числовых множеств. Второй способ, применяемый для конечных множеств в , — построение так называемого графа соответствия. В этом случае элементы множеств в изображаются на плоскости кружочками. Если и только если пара принадлежит соответствию , то в графе соответствия из кружочка, обозначающего элемент , проводим стрелку к кружочку, обозначающему элемент . Для бинарного отношения на конечном множестве часто удобнее использовать граф другого вида. Элементы множества изображаются кружочками только один раз, а стрелки проводятся по тем же правилам, что и в графе соответствия. Заметим, что при таком построении возможно соединение кружочка стрелкой с самим собой (петля).

Пример 1.6. а. На рис. 1.1, а изображены график и граф бинарного соответствия из примера 1.3.

б. Пусть . Бинарное отношение на определим как множество всех упорядоченных пар , таких, что . Тогда

Область определения отношения , область значений . График и два варианта графа отношения изображены на рис. 1.1, б.

в. Множество точек окружности есть график бинарного отношения на множестве действительных чисел, состоящего из всех таких упорядоченных пар , что , или, что равносильно, компоненты пары удовлетворяют уравнению . Область определения бинарного отношения есть отрезок , область значения — также отрезок .

Функциональное соответствие

Соответствие называют функциональным по второй (первой) компоненте, если для любых двух упорядоченных пар и из равенства следует (и из следует ). Функциональность соответствия по второй компоненте означает, что, фиксируя в любой упорядоченной паре, принадлежащей данному соответствию, первую компоненту, мы однозначно определяем и вторую компоненту. Таким образом, мы можем сказать, что соответствие, функциональное по второй компоненте, есть отображение (возможно, частичное).

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

Отношения произвольной арности

В заключение обобщим понятие соответствия, определив отношения произвольной арности.

Определение 1.4. Произвольное подмножество декартова произведения называют (п-арным или п-местным) отношением на множествах .

В случае если все множества совпадают, т.е. , говорят об n-арном отношении на множестве .

Если — n-арное отношение на множествах и , то говорят об элементах , связанных отношением .

Замечание 1.3. При получаем бинарное отношение на множествах . Это не что иное, как соответствие из в , где множества и , вообще говоря, различны.

При получаем введенное ранее бинарное отношение на множестве, т.е. подмножество декартова квадрата .

Таким образом, в общем случае (при произвольном ) следует, строго говоря, различать термины «n-арное отношение» и «n-арное отношение на множестве».

Связь между введенными понятиями отношения, соответствия и отображения проиллюстрирована на рис. 1.2.

Пусть n-арное отношение удовлетворяет условию: для любых двух кортежей

и

из выполнения равенств для любого следует, что и . Тогда отношение называют функциональным по i-й компоненте .

Другими словами, функциональность n-местного отношения по i-й компоненте равносильна условию, что, фиксируя все компоненты, кроме i-й, мы однозначно определяем и i-ю компоненту.

Пример 1.7. а. Представим строку учебного расписания как кортеж вида

(преподаватель, группа, дисциплина, аудитория, день, час).

Тогда расписание можно рассматривать как секстарное (шестиместное) отношение на соответствующих множествах. Оно будет функционально по первой компоненте, если, конечно, предположить, что два преподавателя или более не проводят одно и то же занятие одновременно в одном и том же месте (хотя, например, на лабораторных работах это возможно). Оно также функционально по третьей компоненте (один преподаватель не может вести одновременно занятия по разным дисциплинам), по четвертой (преподаватель со своей группой не могут находиться в разных аудиториях) и не будет, вообще говоря, функционально по второй, пятой и шестой компонентам.

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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

ЛЕКЦИЯ 12 Образ и прообраз множества при данном соответствии 21. 11. 2012 г.

• Пусть дано соответствие Г = (X, Y, F). • Образом элемента х Х при соответствии Г называется и через Г(х) обозначается множество элементов y Y, для которых пара F. Иначе, Г(х)={y Y| F}. Т. е. , образ элемента х Х – это множество тех элементов y Y, которые соответствуют элементу x. • На графе образ элемента x можно представить как множество тех вершин y, в которые входят дуги, выходящие из вершины x.

ПРИМЕР • x 1 x 2 x 3 x 4 • y 1 y 2 y 3 y 4 y 5 • Образ элемента x 2 Г(x 2)={y 3}; • Образ элемента x 3 Г(x 3)={y 1, y 3}; • Образ любого множества A X при соответствии Г = (X, Y, F) представляет собой объединение образов всех элементов x A и обозначается Г(А).

• В общем случае справедливо: • Г(А) = Г(х) • х А • Для рассмотренного примера если А={x 2, x 3}, то Г(А)=Г(х2) Г(х3)={y 3} {y 1, y 3}={y 1, y 3}. • Пусть дано соответствие Г = (X, Y, F). • Прообразом элемента y Y при соответствии Г называется и через Г-1(y) обозначается множество элементов x X, для которых пара F.

5 • Таким образом, Г-1(y)={x X| F } – это множество тех элементов из Х, которым соответствует элемент y. • На графе прообраз элемента y можно представить множеством тех вершин х, из которых выходят дуги, заходящие в вершину y. Для рассмотренного примера • Г-1(y 3)={x 1, x 2, x 3}, Г(y 4)= .

6 • Прообразом произвольного множества B Y при соответствии Г = (X, Y, F) называется объединение прообразов всех элементов y B и обозначается Г-1(В), т. е. • Г-1(В) = Г-1(y) • y B • Если В={y 3, y 4, y 5}, то при соответствии Г для рассмотренного примера прообраз запишется • Г-1(В)={x 1, x 2, x 3, x 4}.

7 • Пусть Г = (X, Y, F) – произвольное соответствие и А – произвольное подмножество множества Х. • Сужением соответствия Г на множество А называется и через ГА обозначается соответствие, график которого FA определяется выражением: • FA = (A Y) F, т. е. ГА = (X, Y, FA). • Соответствие ГА Г. Соответствие Г в этом случае называют продолжением соответствия ГА на множество Х.

Основные свойства соответствий • 1. ФУНКЦИОНАЛЬНОСТЬ: • Соответствие Г = (X, Y, F) называется функциональным, если для любого х Х образ Г(х) содержит не более одного элемента y Y, в противном случае соответствие называется нефункциональным.

ПРИМЕР: x 1 x 2 x 3 • y 1 y 2 y 3 • Соответствия • Функциональное Нефункциональное

10 • 2. ИНЪЕКТИВНОСТЬ: • Соответствие Г = (X, Y, F) называется инъективным, если для любого y Y прообраз Г-1(y) содержит не более одного элемента х Х, в противном случае соответствие называется неинъективным.

ПРИМЕР: • • X 1 Y 1 X 2 Y 2 X 3 X 1 X 2 X 3 Y 1 Y 2 Y 3 Соответствия инъективное неинъективное

12 • 3. ОПРЕДЕЛЕННОСТЬ: • Соответствие Г = (X, Y, F) называется всюду определенным, если для каждого х Х образ Г(х) , в противном случае соответствие не всюду определено. • В графе всюду определенного соответствия из каждой вершины х Х выходит хотя бы одна дуга.

13 • 4. СЮРЪЕКТИВНОСТЬ: • Соответствие Г = (X, Y, F) называется сюръективным, если для любого элемента y Y прообраз Г-1(y) , в противном случае соответствие несюръективно. • В графе сюръективного соответствия в каждую вершину, соответствующую y Y, входит хотя бы одно ребро (дуга, стрелка). • Если соответствие одновременно функциональное, инъективное, всюду определенное и сюръективное, то оно называется взаимно-однозначным или биективным.

ПРИМЕР: • • X 1 X 2 X 3 X 4 Y 1 Y 2 Y 3 Y 4 • Взаимно-однозначное • (биективное) соответствие Г = (X, Y, F)

14 • Биекция — это отображение, которое является одновременно и сюръективным, и инъективным. При биективном отображении каждому элементу одного множества соответствует ровно один элемент другого множества, при этом, определено обратное отображение, которое обладает тем же свойством. Поэтому биективное отображение называют ещё взаимно-однозначным отображением (соответствием), одно-однозначным отображением. • Если между двумя множествами можно установить взаимно-однозначное соответствие (биекция), то такие множества называются равномощными. С точки зрения теории множеств, равномощные множества неразличимы. • Взаимно-однозначное отображение конечного множества в себя называется перестановкой (элементов этого множества). (википедия)

Общее понятие функции • Пусть Х – некоторое числовое множество. • Говорят, что на Х задана функция, если любому элементу из множества Х поставлено в соответствие определенное число y Y. • Если теперь перейти от числовых множеств к множествам произвольной природы, то приходим к самому общему понятию ФУНКЦИИ.

17 • Пусть X и Y – множества произвольной природы, и пусть между ними задано соответствие. • Если соответствие функционально, то оно называется функцией и обозначается • f = (X, Y, F). • Из определения следует, что функция может быть определена не на всех элементах множества Х.

18 • Если же функция определена на всех элементах множества Х, т. е. введенное соответствие не только функциональное, но и всюду определенное, то такая функция называется ОТОБРАЖЕНИЕМ. • Различают отображение X на Y и отображение X в Y. • X на Y, если f(X) = Y, • X в Y, если f(X) Y. • ФУНКЦИЯ – частный вид СООТВЕТСТВИЯ.

Скачать материал

Скачать материал