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

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

Математически это можно выразить следующим образом. Пусть $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$.

Пример. Рассмотрим множество студентов и их курсы в университете. Пусть $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$, так как все студенты сидят за столами, также студенты могут сидеть по двое за одним столом, по трое и т. д., но есть и пустые столы.

Пример. Пусть $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$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Нахождение образа множества $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\}$.