Соответствия, отображения и их применение в дискретной математике: основные концепции и примеры

Соответствие между двумя множествами — это концепция, которая описывает отношение между элементами этих множеств. Одному элементу из первого множества может соответствовать несколько элементов второго множества и наоборот. Также возможна ситуация, когда некоторым элементам одного множества не находится соответствия в другом.

Математически это можно выразить следующим образом. Пусть $A$ и $B$ — два множества. Соответствие между множествами $A$ и $B$ — это подмножество декартова произведения $A \times B$ , то есть набор пар $(a,b)$ , где $a \in A$ и $b \in B$ . Другими словами, соответствие задаётся как множество $R \subseteq A \times B$ .

Для элемента $a \in A$ может существовать несколько пар $(a,b_{i})$ в соответствии, где $b_{i} \in B$ . Это означает, что одному элементу могут соответствовать несколько элементов в другом множестве.

Не каждому элементу множества $A$ обязательно найдется соответствующий элемент во множестве $B$ , и наоборот.

Пример. Пусть $A = \{1, 2, 3\}$ и $B = \{a, b, c\}$ . Соответствие между $A$ и $B$ может быть задано следующим множеством пар: $R = \{(1,a), (1,b), (2,b)\}$ . Здесь элементу 1 из множества $A$ соответствуют элементы $a$ и $b$ из множества $B$ , элементу 2 соответствует элемент $b$ , а элементу 3 не соответствует ни один элемент из множества $B$ , как и элементу $c$ не соответствует ни один элемент из множества $A$ .

Рис. 1.4.1 – Соответствие между множествами

Пример. Рассмотрим множество студентов и их курсы в университете. Пусть $S$ — множество студентов, а $C$ — множество курсов. Соответствие между студентами и курсами может быть установлено на основе того, какие курсы каждый студент выбирает.

— Студент А может быть записан на курсы по математике, физике и литературе.

— Студент Б может выбрать курсы по математике, экономике и истории.

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

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

Таблица 1.4.1 — Соответствие между студентами и курсами

Студент	Математика	Физика	Литература	Экономика	История	Биология
А	Да	Да	Да	Нет	Нет	Нет
Б	Нет	Нет	Нет	Да	Да	Нет
В	Нет	Нет	Нет	Нет	Нет	Нет
Г	Да	Нет	Нет	Нет	Нет	Нет
Д	Нет	Нет	Да	Нет	Да	Нет

В данной таблице студент «В» не выбрал ни одного курса, и никто из студентов не выбрал курс «Биология».

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

Пусть $A$ и $B$ — два множества. Отображением из множества $A$ во множество $B$ , обозначаемым как $f: A \rightarrow B$ , называется правило, согласно которому каждому элементу $a$ из множества $A$ ставится в соответствие ровно один элемент $b$ из множества $B$ . Элемент $b$ называется образом элемента $a$ и обозначается как $f(a)$ .

Математически определение отображения формулируется следующим образом: $f: A \rightarrow B$ , где $f(a) = b$ .

При таком отображении множества $A$ во множество $B$ , элемент $b \in B$ называется образом элемента $a \in A$ , а элемент $a \in A$ называется прообразом элемента $b \in B$ .

Пример. Пусть $A$ — множество студентов в аудитории, $B$ — множество столов в этой аудитории. Соответствие "студент $a$ сидит за столом $b$ " задает отображение множества $A$ во множество $B$ , так как все студенты сидят за столами, также студенты могут сидеть по двое за одним столом, по трое и т. д., но есть и пустые столы.

Соответствия, отображения и их применение в дискретной математике: основные концепции и примеры — Рис. 1.4.2 – Отображение из множества A во множество B

Пример. Пусть $f: \mathbb{R} \rightarrow \mathbb{R}$ задана формулой $f(x) = 3x + 7$ . Здесь каждому действительному числу $x$ сопоставляется значение $3x + 7$ .

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

Математически определение сюръективного отображения формулируется следующим образом: пусть есть отображение $f: A \rightarrow B$ между множествами $A$ и $B$ ; отображение $f$ считается сюръективным (сюръекцией), если для каждого элемента $b$ из множества $B$ существует элемент $a$ из множества $A$ такой, что $f(a) = b$ .

Пример. Рассмотрим отображение $f: \mathbb{R} \rightarrow \mathbb{R}$ , где $f(x) = x^{2}$ .

Отображение $f$ является сюръективным, потому что для каждого вещественного числа $y$ существует такое вещественное число $x$ , что $f(x) = x^{2} = y$ . Например, если $y = 4$ , то $x = 2$ или $x = -2$ . Таким образом, каждый элемент второго множества $(\mathbb{R})$ имеет по крайней мере один прообраз в первом множестве $(\mathbb{R})$ .

Это свойство сюръективности означает, что отображение «покрывает» всю область значений, достигает каждое возможное значение во втором множестве.

Пример. Пусть $A$ — множество книг, $B$ — множество студентов. Соотношение «книга $a$ принадлежит студенту $b$ » задает сюръективное отображение множества $A$ на множество $B$ .

Рис. 1.4.3 – Сюръективное отображение - Теория множеств ischanow.com — Рис. 1.4.3 – Сюръективное отображение

Пример. Представим себе ситуацию с заказом еды через доставку. Пусть у нас есть два множества:

A = {Варианты блюд для заказа};

B = {Клиенты, которые могут сделать заказ}.

Теперь предположим, что есть сюръективное отображение $f: A \rightarrow B$ , где каждому клиенту сопоставлен хотя бы один вариант блюда.

A = {Пицца, Суши, Бургеры, Мороженое, Салат, Суп};

B = {Джон, Мария, Арслан}.

Джон заказал пиццу и салат; Мария — суп, суши и мороженое; Арслан — бургеры. Каждому клиенту сопоставлен хотя бы один вариант блюда, и, таким образом, отображение является сюръективным.

Рис. 1.4.4 – Сюръективное отображение - Теория множеств ischanow.com — Рис. 1.4.4 – Сюръективное отображение

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

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

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

Математически определение инъективного отображения формулируется следующим образом: пусть есть отображение $f: A \rightarrow B$ между множествами $A$ и $B$ ; отображение $f$ считается инъективным (или инъекцией), если для любых различных элементов $a_{1}$ и $a_{2}$ из множества $A$ выполняется условие $f(a_{1}) \neq f(a_{2})$ .

Пример. Пусть $A$ — множество студентов, $B$ — множество стульев. Соответствие «студент $a$ сидит на стуле $b$ » задает инъективное отображение между множествами $A$ и $B$ . Это очевидно, так как все студенты сидят на стульях, причем каждый на своем, но в аудитории есть и пустые стулья.

Пример. Рассмотрим отображение $f: \mathbb{R} \rightarrow \mathbb{R}$ , где $f(x) = 2x$ . Это отображение инъективно, потому что разные значения $x_{1}$ и $x_{2}$ вещественных чисел приводят к разным значениям $f(x_{1}) = 2x_{1}$ и $f(x_{2}) = 2x_{2}$ . Например, если $x_{1} = 3$ и $x_{2} = -2$ , то $f(x_{1}) = 2 \cdot 3 = 6$ и $f(x_{2}) = 2 \cdot (-2) = -4$ , и эти значения не равны. Таким образом, отображение $f$ является инъективным.

Биективное отображение (биекция, взаимно-однозначное соответствие).

Если при отображении $f$ каждому элементу $x \in X$ поставлен в соответствие один элемент $y \in Y$ , и при этом соответствии каждому элементу $y \in Y$ соответствует единственный элемент $x \in X$ , то такое отображение называется биективным (взаимно-однозначным). Иными словами, каждому элементу первого множества сопоставляется единственный и уникальный элемент второго множества, и наоборот.

Математически определение биективного отображения формулируется следующим образом: пусть есть два множества $A$ и $B$ , и отображение $f: A \rightarrow B$ ; если для каждого элемента $a$ из множества $A$ существует единственный элемент $b$ из множества $B$ такой, что $f(a) = b$ , и для каждого элемента $b$ из множества $B$ существует единственный элемент $a$ из множества $A$ такой, что $f^{-1}(b) = a$ , то отображение $f$ является биекцией (взаимно-однозначным соответствием) между $A$ и $B$ .

Пример. Рассмотрим два множества: $A = \{1, 2, 3\}$ и $B = \{a, b, c\}$ . Пусть у нас есть отображение $f: A \rightarrow B$ такое, что: $f(1) = a$ , $f(2) = b$ , $f(3) = c$ .

Это отображение устанавливает взаимно-однозначное соответствие между элементами множеств $A$ и $B$ , так как каждому элементу из $A$ сопоставлен уникальный элемент из $B$ , и наоборот. Таким образом, отображение $f$ является взаимно-однозначным соответствием.

Пример. Взаимно-однозначное соответствие «студенты и номера студенческих билетов». Пусть $A$ — множество студентов, $B$ — множество студенческих билетов. В университете каждому студенту может быть выдан уникальный номер студенческого билета. Соответствие «студенту $a$ принадлежит студенческий билет $b$ » задает взаимно-однозначное отображение между множествами $A$ и $B$ . Это очевидно, так как все студенты имеют студенческие билеты, причем каждый только один и каждый студенческий билет принадлежит своему студенту.

1.4.1. Изобразите соответствие $F = (X, Y, G)$ . Проверьте соответствие на сюръективность, инъективность и биективность. Найдите образ множества $A$ и прообраз множества $B$ при данном соответствии, $X = \{r, p, h, v\}$ ; $Y = \{1, 2, 3, 4\}$ ; $G = \{(r, 2), (p, 4), (h, 3), (v, 4)\}$ ; $A = \{h, v\}$ ; $B = \{2, 3\}$ .

Решение.

Изобразим соответствие с помощью диаграммы (рис. 1.4.7). Мы имеем множество $X = \{r, p, h, v\}$ и множество $Y = \{1, 2, 3, 4\}$ . Стрелки проводятся от каждого элемента $X$ к соответствующему элементу $Y$ в соответствии с $G$ : стрелка от $r$ к $2$ , от $p$ к $4$ , от $h$ к $3$ , и от $v$ к $4$ .

Анализ свойств соответствия $F$ .

Сюръективность. Нет, так как в $Y$ присутствует 1, для которого нет пары в $X$ .

Инъективность. Нет, поскольку элемент $4$ в $Y$ соответствует двум различным элементам в $X$ ( $p$ и $v$ ).

Биективность. Нет, поскольку при данном виде отображения каждому элементу первого множества должен сопоставляться единственный и уникальный элемент второго множества, и наоборот. В данном случае это условие нарушается: в $Y$ присутствует 1, для которого нет пары в $X$ ; элемент $4$ в $Y$ соответствует двум различным элементам в $X$ ( $p$ и $v$ ).

Нахождение образа множества $A$ и прообраза множества $B$ . Образом $F(A)$ будет множество элементов $Y$ , которым соответствуют элементы $A$ . Таким образом, $F(A) = \{3, 4\}$ .

Прообразом $F^{-1}(B)$ будет множество элементов $X$ , которые соответствуют элементам $B$ . Следовательно, $F^{-1}(B) = \{r, h\}$ .

Задания для самостоятельной работы

1.4.2. Изобразите соответствие $F = (X, Y, G)$ . Проверьте соответствие на сюръективность, инъективность и биективность. Найдите образ множества $A$ и прообраз множества $B$ при данном соответствии, $X = \{k, t, y\}$ ; $Y = \{1, 2, 3, 4\}$ ; $G = \{(k, 2), (t, 2), (y, 3)\}$ ; $A = \{y, t\}$ ; $B = \{4, 1\}$ .

1.4.3. Изобразите соответствие $F = (X, Y, G)$ . Проверьте соответствие на сюръективность, инъективность и биективность. Найдите образ множества $A$ и прообраз множества $B$ при данном соответствии, $X = \{c, e, h, y\}$ ; $Y = \{1, 2, 3, 4, 5\}$ ; $G = \{(c, 5), (e, 4), (h, 3), (y, 5)\}$ ; $A = \{y, e\}$ ; $B = \{1, 3\}$ .

1.4.4. Изобразите соответствие $F = (X, Y, G)$ . Проверьте соответствие на сюръективность, инъективность и биективность. Найдите образ множества $A$ и прообраз множества $B$ при данном соответствии, $X = \{z, g, d, x, n\}$ ; $Y = \{1, 2, 3\}$ ; $G = \{(z, 1), (g, 3), (d, 2), (x, 1), (n, 2)\}$ ; $A = \{d, n\}$ ; $B = \{1, 2\}$ .

1.6.34. Изобразите соответствие $F = (X, Y, G)$ . Проверьте соответствие на сюръективность, инъективность и биективность. Найдите образ множества $A$ и прообраз множества $B$ при данном соответствии, $X = \{w, f, x, a, j\}$ ; $Y = \{1, 2, 3, 4, 5\}$ ; $G = \{(w, 3), (f, 5), (x, 1), (a, 5), (j, 4)\}$ ; $A = \{a, w\}$ ; $B = \{4, 3\}$ .

1.6.35. Изобразите соответствие $F = (X, Y, G)$ . Проверьте соответствие на сюръективность, инъективность и биективность. Найдите образ множества $A$ и прообраз множества $B$ при данном соответствии, $X = \{y, t, n, v\}$ ; $Y = \{1, 2, 3\}$ ; $G = \{(y, 3), (t, 3), (n, 2), (v, 2)\}$ ; $A = \{v, y\}$ ; $B = \{3, 1\}$ .

1.6.36. Изобразите соответствие $F = (X, Y, G)$ . Проверьте соответствие на сюръективность, инъективность и биективность. Найдите образ множества $A$ и прообраз множества $B$ при данном соответствии, $X = \{f, h, z, t\}$ ; $Y = \{1, 2, 3\}$ ; $G = \{(f, 2), (h, 1), (z, 2), (t, 1)\}$ ; $A = \{z, f\}$ ; $B = \{3, 1\}$ .