"Информатика", Горячев А.В., Волкова Т.О.
Отображение связывает элементы двух множеств по правилу: каждому элементу первого множества соответствует ровно один элемент второго. Оно помогает описывать связи между объектами, а также числовые функции и преобразования данных. Чтобы разобраться в отображении, нужно отличать область определения от множества прибытия и множества значений, уметь находить образы и прообразы. По стрелочной схеме можно проверить, является ли отображение инъективным, сюръективным или взаимно-однозначным.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Отображение множества A в множество B — правило, которое каждому элементу A ставит в соответствие ровно один элемент B. Множества и правило нужны вместе: без них нельзя установить, откуда берутся элементы и куда они переходят. Условие «ровно один» отличает отображение от других способов связывать объекты. Например, правило может отправлять несколько разных элементов A в один и тот же элемент B.
Область определения отображения — множество A, элементы которого получают образы. Именно с его элементами начинают работу: если элемент не входит в A, данное отображение не обязано задавать для него результат. Это понятие помогает понять, для каких объектов действует правило. Например, у правила f на множестве A проверяют только элементы A.
Образ элемента — элемент множества B, поставленный в соответствие данному элементу A. Если элемент a переходит в b, записывают f(a) = b: f обозначает правило, а f(a) — полученный результат. Такая запись позволяет быстро находить результат для заданного элемента. Например, если f(2) = 5, то образ числа 2 равен 5.
Множество значений отображения — все элементы B, которые являются образами хотя бы одного элемента A. Оно может совпадать с B, но может быть и его частью. Это понятие нужно, чтобы отличать реально полученные результаты от всех возможных элементов множества прибытия. В записи f: A → B множество значений не обязательно равно B.
Отображение задают двумя множествами и правилом, потому что правило само по себе не сообщает, к каким исходным и конечным объектам его применяют. Обозначение f: A → B показывает область, откуда берутся элементы, и множество, в котором находятся результаты. Для каждого элемента A результат должен существовать: иначе правило не определено на всей области. Он должен быть ровно один, иначе нельзя однозначно сказать, чему равно f(a).
В записи f: A → B множество A называют областью определения, а B — множеством прибытия. Это разные роли: A содержит входные элементы, B задаёт множество возможных выходов. Множество значений — только те элементы B, которые получились на деле. Например, если B = {a, b, c}, а стрелки ведут лишь к a и b, то множество значений равно {a, b}, а c остаётся элементом множества прибытия.
Чтобы найти образ, берут элемент из A и применяют к нему правило: для формулы подставляют вместо переменной этот элемент. Чтобы найти прообразы заданного элемента B, действуют в обратном направлении и выясняют, какие элементы A дают такой образ. Прообразов может быть несколько или не быть совсем. Например, при f(x) = x² на множестве целых чисел число 4 имеет прообразы 2 и −2, а число −4 прообраза не имеет.
Произвольное соответствие становится отображением только тогда, когда каждому элементу A сопоставлен ровно один элемент B. Нельзя оставить элемент A без образа или направить от него две стрелки к разным элементам. При этом один элемент B может получать стрелки от нескольких элементов A — это не нарушает определения. Также элемент B может не получить ни одной стрелки: тогда он просто не входит в множество значений.
По стрелочной схеме можно проверить дополнительные свойства. Отображение инъективно, если разные элементы A не переходят в один и тот же элемент B: у каждого занятого элемента B не больше одного прообраза. Оно сюръективно, если стрелки достигают всех элементов множества прибытия, то есть у каждого есть хотя бы один прообраз. Взаимно-однозначное отображение одновременно инъективно и сюръективно: каждому элементу B соответствует ровно один элемент A. Поэтому при проверке схемы сначала смотрят, не совпали ли образы, а затем — не осталось ли элементов B без стрелок.
| Вид отображения | Условие для образов | Условие для множества прибытия | Пример применения |
|---|---|---|---|
| Произвольное отображение | Каждый элемент A имеет ровно один образ; разные элементы могут иметь одинаковые образы. | Некоторые элементы B могут не иметь прообразов. | Сопоставление каждому ученику его класса. |
| Инъективное отображение | Разные элементы A имеют разные образы. | У каждого элемента B не больше одного прообраза; элементы без прообраза возможны. | Назначение каждому человеку его уникального номера. |
| Сюръективное отображение | У каждого элемента A ровно один образ; образы разных элементов могут совпадать. | Каждый элемент B имеет хотя бы один прообраз. | Распределение заданий между группами так, чтобы каждая группа получила задание. |
| Взаимно-однозначное отображение | Разные элементы A имеют разные образы. | Каждый элемент B имеет ровно один прообраз. | Связь между местами в зале и билетами на эти места. |
Сначала проверьте, что у каждого элемента A ровно один образ: без этого схема вообще не задаёт отображение. Затем для инъективности сравните образы разных элементов, а для сюръективности просмотрите всё множество B. Если выполнены оба условия, отображение взаимно-однозначное.
Задача 1. Даны A = {1, 2, 3} и B = {a, b}. Соответствие задано стрелками 1 → a, 2 → b, 3 → a. Нужно определить, является ли оно отображением A в B, и указать множество значений. Проверим, что у каждого элемента A ровно одна стрелка, а затем соберём все элементы B, к которым ведут стрелки.
Ответ: соответствие является отображением A в B; множество значений — {a, b}. Элемент множества прибытия не остался без стрелки. Повторяющийся образ допустим, поэтому стрелки от 1 и 3 к a не мешают.
Задача 2. Отображение задано формулой f(x) = 2x − 1 на множестве A = {0, 1, 2, 3}. Найдём образы всех элементов, множество значений и прообраз числа 3. Сначала подставим каждый элемент A в формулу, а затем решим уравнение для поиска прообраза.
Ответ: образы элементов A равны соответственно −1, 1, 3 и 5; множество значений — {−1, 1, 3, 5}. Прообраз числа 3 — элемент 2. Проверка подстановкой даёт f(2) = 3.
Задача 3. Задано f: {1, 2, 3, 4} → {a, b, c}, где 1 → a, 2 → b, 3 → b, 4 → c. Нужно проверить инъективность и сюръективность, а затем решить, является ли отображение взаимно-однозначным. Для этого сравним образы и проверим, получила ли стрелку каждая буква множества прибытия.
Ответ: отображение сюръективно, но не инъективно и не является взаимно-однозначным. Совпадение образов у 2 и 3 нарушает инъективность. При этом оно не мешает сюръективности, так как все элементы множества прибытия получили стрелки.
Первую ошибку допускают, когда называют отображением соответствие, в котором у одного элемента A два образа или нет ни одного. Так бывает, если смотрят только на наличие стрелок и забывают условие «ровно одна». Проверьте отдельно каждый элемент области определения: от него должна выходить ровно одна стрелка. Если это не так, заданное соответствие не является отображением A в B.
Вторая ошибка — считать все элементы множества прибытия множеством значений. Их путают, потому что оба множества связаны с возможными результатами. Но значением является только элемент, к которому ведёт хотя бы одна стрелка. Чтобы проверить себя, просмотрите схему и выпишите именно использованные элементы B; элементы без стрелок оставьте за пределами множества значений.
Третья ошибка — менять местами образ и прообраз. Образ получают, начиная с элемента области определения, а прообраз ищут среди элементов, которые приводят к заданному результату. Путаница часто возникает, когда направление стрелок не учитывают. Проследите стрелку слева направо: её конец — образ, а начало при поиске заданного конца — прообраз.
Четвёртая ошибка — объявлять отображение сюръективным только потому, что оно задано для всех элементов A. Полнота области определения гарантирует лишь, что у каждого входа есть результат, но ничего не говорит о том, использованы ли все элементы B. Для проверки сюръективности нужно пройтись по множеству прибытия и найти хотя бы одну стрелку к каждому его элементу. Если хотя бы один элемент B остался без стрелок, отображение не сюръективно.
Для изучения отображений нужны понятия множества, его элемента, подмножества и способов задания множеств. Они позволяют точно назвать исходные и конечные объекты, а также перечислить их. Отображение подготавливает к изучению функций: функцию рассматривают как отображение числовых множеств, заданное правилом или формулой. Похожие связи используют и в информатике — при описании соответствий между объектами, алгоритмов, отношений и преобразований данных.
Может ли у одного элемента области определения быть несколько образов?
Нет. По определению отображения каждому элементу области определения соответствует ровно один образ. Если для одного элемента указаны два образа или ни одного, это не отображение данной области.
Может ли один элемент множества прибытия иметь несколько прообразов?
Да. Разные элементы области определения могут иметь один и тот же образ. В таком случае у элемента множества прибытия несколько прообразов.
Чем множество значений отличается от множества прибытия?
Множество прибытия — это всё множество B, куда направлено отображение. Множество значений включает только те элементы B, к которым ведёт хотя бы одна стрелка.
Как по стрелочной схеме быстро определить, является ли отображение сюръективным?
Проверьте каждый элемент множества прибытия: к каждому должна вести хотя бы одна стрелка. Если остался элемент без стрелок, отображение не сюръективно.
Почему функция является частным случаем отображения?
Функция сопоставляет каждому допустимому аргументу ровно одно значение, то есть удовлетворяет определению отображения. Обычно говорят о функциях числовых множеств и задают их формулой.
§ 17. Отображение множеств
