§9. Соответствие, обратное данному. Взаимно однозначные соответствия

Пусть G соответствие между элементами множеств X и Y.

Соответствие G называется всюду определенным, если множество D(G) = Х. Если E(G) = Y. Если же E(G) = Y, то соответствие называют сюръективным, или накрывающим.

Рис. 14

Соответствие G Ì Х ´ Y называется функциональным, если образом любого элемента из D(G) является единственный элемент из E(G). Например, соответствие, представленное на рис. 14 б не функционально.

Соответствие называется инъективным, если любому элементу из E(G) соответствует единственный элемент из D(G). На рис. 14 а изображено инъективное соответствие.

Пусть R — соответствие «Число х в пять раз меньше числа у» между элементами множеств Х = {1, 2, 4, 5, 6} и Y = {10, 5, 20, 13, 25}.

Граф этого соответствия будет таким, как на рис. 15.

Если изменить направление стрелок этого графа на обратное, то получим граф (рис. 16) нового соответствия «Число у в пять раз больше числа х», рассматриваемого между множествами Y и Х.

Это соответствие называется соответствием, обратным соответствию R, и обозначается R–1.

Рис. 15 Рис. 16

Определение 1. Пусть R — соответствие между элементами множеств Х и Y. Соответствие R–1 между элементами множеств Y и Х называется обратным данному R, когда пара (у, х) Î R–1 тогда и только тогда, когда пара (х, у) Î R.

Соответствия R и R–1 называют взаимно обратными.

Если множества Х и Y числовые, то график соответствия R–1, обратного соответствию R, состоит из точек, симметричных точкам графика соответствия R относительно биссектрисы первого и третьего координатных углов.

Действительно, условимся первую компоненту пары любого соответствия R, в том числе и обратного ему соответствия R–1, считать абсциссой, а вторую — ординатой. Пусть (а, b) Î R, тогда (b, а) Î R–1. Но точки с координатами (а, b) и (b, а) симметричны относительно биссектрисы первого и третьего координатных углов (рис. 17).

Рис. 17

Определение 2. Если графики соответствий Р Ì Х ´ Y и S Ì Х ´ Y дополнительные множества в Х ´ Y (т.е. они не пересекаются, а их объединение является Х ´ Y), то такие соответствия называются противоположными.

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

Пусть после звонка, когда расселись все зрители, оказалось, что все места в зале заняты и никто не сидит на подставном кресле, т.е. на каждом месте сидит зритель и для каждого зрителя нашлось место. В этом случае говорят, что между множеством мест в зрительном зале и множеством зрителей установлено взаимно однозначное соответствие.

Определение 3. Пусть даны два множества Х и Y. Соответствие между элементами множеств Х и Y, при котором каждому элементу множества Х соответствует единственный элемент множества Y, и каждый элемент множества Y соответствует только одному элементу из множества Х, называется взаимно однозначным (или биективным).

Таким образом, соответствие между X и Y называется взаимно однозначным, если оно всюду определено, сюръективно, функционально и инъективно.

Рассмотрим примеры взаимно однозначных соответствий.

Пример 1. В каждой школе каждому классу соответствует классный журнал.

Пример 2. Дан треугольник АВС (рис. 18). А1С1 — средняя линия треугольника. Пусть Х — множество точек на отрезке А1С1, Y — множество точек на АС.

Рис. 18

Произвольную точку х отрезка А1С1 соединим с вершиной В треугольника отрезком прямой линии и продолжим его до пересечения с АС в точке y. Поставим в соответствие точке х точку у, построенную таким образом. При этом между множествами Х и Y будет установлено взаимно однозначное соответствие.

Действительно, нетрудно убедиться в том, что каждой точке отрезка А1С1 соответствует одна и только одна точка отрезка АС и, наоборот, каждая точка отрезка АС поставлена в соответствие одной и только одной точке отрезка А1С1.

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

Эквивалентность двух множеств обозначается так: X ~ Y.

Пример, приведенный выше, показывает, что множество классов школы и множество классных журналов являются равномощными.

Если Х и Y — равномощные множества, то говорят также, что множества Х и Y имеют одинаковую мощность. Понятие мощности является обобщением понятия количества. Мощностью любого множества считают количество его элементов.

Распространим понятие количества элементов на бесконечные множества.

Определение 5. Множество, имеющее ту же мощность, что и множество N натуральных чисел, называется счетным. Его элементы можно пронумеровать, поставить во взаимно однозначное соответствие с числами натурального ряда.

Пример 1. Множество натуральных чётных чисел счетно. Установить взаимно однозначное соответствие между этим множеством и множеством N всех натуральных чисел можно следующим образом:

Вообще, любое бесконечное подмножество множества N счетно.

Примеры счетных множеств: Z, Q и любые их бесконечные подмножества.

Пример 2. Множество точек отрезка эквивалентно множеству точек полупрямой. Грубо говоря, в отрезке столько же точек, сколько их в луче.

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

У последнего множества есть особо название: континуум.

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

Примеры множеств мощности континуума: отрезок, полуинтервал, интервал, луч, числовая прямая

Возникет вопрос: как соотносятся между собой множество всех действительных чисел между нулем и единицей включительно и множество N всех натуральных чисел?

Оказывается, хотя оба множества и бесконечны, но эти бесконечности разные. Эти множества неэквивалентны.

Рассмотрим, как из множества всех действительных чисел между нулем и единицей включительно [0;1] можно выделить подмножество, эквивалентное множеству N натуральных чисел: пусть единице соответствует единица, двойке — одна вторая, тройке — одна третья и т.д. После этого останутся точки [0;1], которые не занумеровали

Рис. 19

? Мощность счетного множества меньше мощности континуального.