Соответствие между множествами

Пусть даны два множества . Тогда пары задают соответствие между мно­жествами А и В, если указано правило R, по которому для элемента множества А выбирается элемент из множества В.

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

Пусть задано соответствие R между множествами А и В, т. е. R: (a; b), a ϵ A, b ϵ В. Для некоторого элемента а множества А поставлен в соответствие некоторый элемент b из множества B, который называется образом элемента а и записывается b = R(a). Тогда а – R^-1(b) — прообраз элемента b ϵ В.

Образ множества А при соответствии R называется множеством значений этого соответствия и обозначается R(A), если R(A) со­стоит из образов всех элементов множества А.

Прообраз множества В при некотором соответствии R называют областью определения этого соответствия и обозначают R^-1(B).

Так, для соответствия R, заданного точками координатной плоскости, областью определения является множество точек оси абсцисс, а множеством значений — проекции точек на ось ординат.

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

Для задания отображения необходимо указать:

• множество, которое отображается (область определения дан­ного отображения, часто обозначается D(f));

• множество, в (на) которое отображается данная область оп­ределения (множество значений этого отображения, часто обозна­чается E(f)).

• закон или соответствие между этими множествами, по кото­рому для элементов первого множества (прообразов, аргументов) выбраны элементы (образы) из второго множества. Приняты записи или f: А → В.

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

Cпособ задания отображений в виде формул называется аналитическим. Существуют еще табличный и графи­ческий способы.

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

Графическое представление отображения связано со стрелочными схемами (диаграммами или графами).

Табличное задание отображения

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

Графическое задание инъективного отображения множества

Соответствие между элементами двух множеств, при котором каждому элементу первого множества соответствует один определённый элемент второго множества, а каждому элементу второго множества — один определённый элемент первого множества, называется взаимно-однозначным соответствием меж­ду двумя множествами, или биекцией.

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

Рассмотрим примеры отображений.

1. Отображение γ: а → а /2, где а ϵ Z, является биекцией множества Z целых чисел на некоторое множество В. Табличное задание такой биекции можно представить в виде таблицы:

Из таблицы видно, что каждому элементу множества Z ставит­ся в соответствие единственный элемент множества В. И наоборот, каждому элементу множества В можно поставить в соответ­ствие единственный элемент из Z. Обратное отображение можно представить аналитически: γ: а → 2а и таблично, поменяв места­ми строки в таблице.

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

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

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