1.10 Соответствия
Рассмотрим два множества А и В. Элементы этих двух множеств могут каким-либо образом сопоставляться друг с другом, образуя пары (x, y). Если способ такого сопоставления определен, т.е. для каждого элемента указан элемент , с которым сопоставляется элемент x, то говорят, что между множествами А и В установлено соответствие. При этом не обязательно, чтобы в сопоставлении участвовали все элементы множества А и В. Для того, чтобы задать соответствие, необходимо указать:
множество А, элементы которого сопоставляются с элементами другого множества;
множество В, с элементами которого сопоставляются элементы первого множества;
множество , определяющее закон, в соответствии с которым осуществляется соответствие, т.е. перечисляющее все пары x и y.
Таким образом, соответствие, обозначаемое q, представляет собой тройку множеств:
q=(A, B, P); P=AB.
В этом выражении 1-ю компоненту А называют областью отправления соответствия, 2-ю компоненту В – областью прибытия соответствия, 3-ю компоненту P – графиком соответствия.
Кроме рассмотренных множеств А, В, Р с каждым соответствием неразрывно связаны еще два множества: множество Пр1Р, называемое областью определения соответствия, и в которое входят элементы множества А, участвующие в сопоставлении, и множество Пр2Р, называемое областью значений соответствия, в которое входят элементы множества В, участвующие в сопоставлении. Если Пр1Р=А, то соответствие называется всюду определенным, в противном случае – частично определенным. Если Пр2Р=В, то соответствие называется сюръективным.
Множество всех уВ, соответствующих элементу хА, называется образом х в В при соответствии Р. Множество всех х, которым соответствует у, называется прообразом у в А при соответствии Р. Короче, образ х есть Р(х)={y | ( x, y) P}, а прообразом элемента уВ (обозначается Р-1(у)) является Р-1(у)={x | (x, y) P}.
Если , то говорят, что элементу y соответствует элемент х при соответствии Р. Геометрически это удобно изображать стрелкой, направленной от х к у.
Пример: A={3, 4}; B={2, 5}. P=AB={(3, 2), (3, 5), (4, 2), (4, 5)}.
Это множество дает возможность получить соответствия:
Р1={(3, 2)}; P2={(3, 2), (3,5)}; P3={(3, 2), (3, 5), (4, 2)}.
Если D Пр1Р, то образом множества D называется объединение образов всех элементов из D. Аналогично определяется прообраз множества S В для любого SПр2Р.
Соответствие Р называется функциональным (или однозначным), если образом любого элемента Пр1Р является единственный элемент из Пр2Р. Заметим, что здесь не говорится о том, что различные элементы из Пр1Р должны иметь различные образы из Пр2Р. Соответствие Р между А и В называется взаимно однозначным, если оно всюду определено, сюръективно, функционально и, кроме того, прообразом любого элемента из Пр2Р является единственный элемент из Пр1Р.
Пример 1. Англо-русский словарь устанавливает соответствие между множествами английских и русских слов. Это соответствие не является функциональным, так как одному английскому слову, как правило, ставится в соответствие несколько русских слов. Кроме того, оно практически никогда не является полностью определенным: всегда можно найти английское слово, не содержащееся в данном словаре. Областью отправления является множество всех английских слов, областью прибытия – множество всех русских слов. Область определения (значений) является подмножеством области отправления (прибытия).
П ример 2. Круг Р радиуса 1 с центром в точке (3, 2) {(x, y) | (x –3)2+(y-2)21} задает соответствие между R и R. Образом числа 4 при этом соответствии является число 2, образом числа 3 – отрезок [1, 3] оси ординат; этот же отрезок [1, 3] является образом отрезка [2, 4] оси абсцисс, который в свою очередь служит прообразом числа 2 (См. Рис.1.8).
Y 3 B A C 2 1 X 2 3 4
Рис. 1.8
Данное соответствие не является функциональным. Примером функционального соответствия является дуга АВС.
Пример 3. Различные виды кодирования – кодирование букв азбукой Морзе, представление чисел в различных системах счисления, секретные шифры и т.п. – являются соответствиями между кодируемыми объектами и присваемыми им кодами. Эти соответствия, как правило, обладают всеми свойствами взаимно однозначного соответствия, кроме, быть может, одного – сюръективности.
Пример 4. В цехе имеется 3 специализированных станка Ст1, Ст2, Ст3. Станок Ст2 не работает. Штат содержит три оператора, обслуживающие эти станки – О1, О2, и О3. Причем, О3 болен (или в отпуске и т.п.) В этом случае распределение операторов по станкам можно выразить соответствием:
Геометрическая интерпретация имеет вид:
О1 О2 О3
Ст1 Ст2 Ст3
Здесь областью определения соответствия является множество {О1, О2}. Областью значений соответствий является множество {Ст1, Ст3}. Вполне очевидно, что соответствие не является функциональным.
- 1. Элементы теории множеств
- 1.1 Понятие множества. Основные определения
- Способы задания множества
- Равенство множеств
- Подмножество
- Операции над множествами
- Предварительные замечания
- Объединение множеств
- 1.5.3 Пересечение множеств
- 1.5.4 Разность множеств
- 1.5.5 Симметрическая разность
- 1.5.6 Универсальное множество
- 1.5.7 Дополнение множества
- Принцип двойственности в алгебре множеств
- Тождества алгебры множеств
- Разбиение множества
- Упорядочение элементов и прямое произведение множеств
- Упорядоченное множество
- Прямое произведение множеств
- 1.9.3 Проекция множества
- 1.10 Соответствия
- 1.10.1 Обратное соответствие
- 1.10.2 Композиция соответствий
- 1.10.3 Отображения и функции
- 1.10.4 Основные свойства отображений
- 1.11 Функция
- 1.11.1 Способы задания функции
- 1.11.2 Сужение функции
- 1.11.3 Обратная функция
- 1.11.4 Функция времени
- 1.11.5 Понятие функционала
- 1.11.6 Понятие оператора
- 1.12 Отношения
- 1.12.1 Задание бинарных отношений
- Свойства отношений
- 1.12.3 Отношение эквивалентности
- 1.12.4 Отношение порядка
- 1.13 Конечные и бесконечные множества
- 1.13.1 Счётные и несчётные множества
- 1.13.2 Свойства счетных множеств
- 1. Всякое подмножество счетного множества конечно или счетно.
- 2. Объединение любого конечного или счетного множества счетных множеств есть снова счетное множество.
- 3. Всякое бесконечное множество содержит счетное подмножество.
- 1.13.3 Эквивалентность множеств
- 1.13.4 Теорема г. Кантора
- 1.13.5 Теорема Кантора – Бернштейна
- 1.13.6 Верхняя и нижняя границы множества
- 1.13.7 Теорема о верхних и нижних границах подмножества
- 1.13.8 Понятие мощности множества
- 2. Основные положения теории графов
- 2.1 Определение графа
- 2.2 Матричные представления графа
- 2.3. Достижимость
- 2.4. Неориентированные графы
- 2.5. Изоморфизм графов
- 2.6. Отношение порядка и отношение эквивалентности на графе
- 2.7. Характеристики графов
- 2.8 Операции над графами
- 2.9. Определение путей экстремальной длины
- 2.9.1. Задача о кратчайшем пути между двумя вершинами (ориентированного графа
- 2.9.2 Задача о нахождении пути максимальной длины между двумя фиксированными вершинами ориентированного графа
- Номера работ обозначены числами в кружке.
- Литература