Отношения и функции

TL;DR

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

1. The Mental Model

Думайте об отношениях как о стрелках, соединяющих элементы из одного "облака" в другое. Функции — это более строгий вид таких стрелок: от каждого элемента первого облака выходит ровно одна стрелка к элементам второго облака.

2. The Core Material

Отношения

Отношение $R$ между двумя множествами $A$ и $B$ (обозначается как $A \times B$) – это просто подмножество декартова произведения $A \times B$. Это означает, что $R$ состоит из пар $(a, b)$, где $a \in A$ и $b \in B$, и $a$ связано с $b$ каким-то правилом.

Пример:
Пусть $A = \{1, 2, 3\}$ и $B = \{'x', 'y'\}$.
Отношение $R = \{(1, 'x'), (2, 'y'), (3, 'x')\}$ – это отношение из $A$ в $B$.
Отношение на одном множестве $A$ (т.е. из $A$ в $A$) может быть, например, $S = \{(1, 2), (2, 3)\}$ на множестве $A = \{1, 2, 3\}$.

Свойства отношений

На одном множестве $A$, отношения могут обладать следующими свойствами:

• Рефлексивность: Каждый элемент связан сам с собой. Для всех $a \in A$, $(a, a) \in R$.
• Иррефлексивность: Ни один элемент не связан сам с собой. Для всех $a \in A$, $(a, a) \notin R$.
• Симметричность: Если $a$ связано с $b$, то $b$ связано с $a$. Если $(a, b) \in R$, то $(b, a) \in R$.
• Асимметричность: Если $a$ связано с $b$, то $b$ не может быть связано с $a$. Если $(a, b) \in R$, то $(b, a) \notin R$.
• Антисимметричность: Если $a$ связано с $b$ и $b$ связано с $a$, то $a$ и $b$ должны быть одним и тем же элементом. Если $(a, b) \in R$ и $(b, a) \in R$, то $a = b$.
• Транзитивность: Если $a$ связано с $b$ и $b$ связано с $c$, то $a$ связано с $c$. Если $(a, b) \in R$ и $(b, c) \in R$, то $(a, c) \in R$.

Функции (Отображения)

Функция $f$ из множества $A$ (область определения) в множество $B$ (область значений) – это специальный вид отношения, где каждому элементу из $A$ соответствует ровно один элемент из $B$.

Важные термины:
* Область определения (Domain): Множество $A$.
* Область значений (Codomain): Множество $B$.
* Образ (Image): Множество всех элементов в $B$, которые фактически являются значениями функции. Это подмножество области значений.
* Прообраз (Preimage): Элементы из области определения, которые отображаются в конкретный элемент или подмножество области значений.

Типы функций:

graph TD
    A["Функции"] --> B{"Свойства отображения"}
    B --> C["Инъективная (одно-однозначная)"];
    B --> D["Сюръективная (на)"];
    B --> E["Биективная (взаимно-однозначная)"];

    C -- "Каждый b в Image(f) имеет\nне более одного a в Domain(f)" --> C1["f(a₁) = f(a₂) => a₁ = a₂"];
    D -- "Каждый b в Codomain(f) имеет\nхотя бы один a в Domain(f)" --> D1["Image(f) = Codomain(f)"];
    E -- "Инъективная И Сюръективная" --> E1["Соответствие 1:1 между Domain(f) и Codomain(f)"];

• Инъективная (одно-однозначная): Разным элементам области определения соответствуют разные элементы области значений. Если $f(a_1) = f(a_2)$, то $a_1 = a_2$.
• Сюръективная (на): Каждый элемент области значений является образом хотя бы одного элемента области определения. То есть, образ функции совпадает с областью значений.
• Биективная (взаимно-однозначная): Функция одновременно инъективна и сюръективна. Такая функция имеет обратную.

3. Worked Example

Пусть у нас есть множество $A = \{1, 2, 3, 4\}$ и множество $B = \{'a', 'b', 'c'\}$.

Пример отношения:
Рассмотрим отношение $R_1 = \{(1, 'a'), (2, 'b'), (3, 'a'), (4, 'c')\}$ из $A$ в $B$.
Это отношение является функцией?
Да, это функция, потому что от каждого элемента из $A$ (1, 2, 3, 4) выходит ровно одна "стрелка" к элементам $B$.

Пример, который не является функцией:
Рассмотрим отношение $R_2 = \{(1, 'a'), (1, 'b'), (2, 'c'), (3, 'a')\}$.
Это отношение не является функцией, потому что элемент $1 \in A$ связан с двумя разными элементами из $B$ ('a' и 'b'). Также, элемент $4 \in A$ вообще не связан ни с одним элементом из $B$.

Свойства функции $f(x) = x^2$ для $f: \mathbb{Z} \to \mathbb{Z}$ (целые числа в целые числа):
* Инъективная? Нет. Например, $f(-2) = 4$ и $f(2) = 4$. Разные элементы области определения (-2 и 2) отображаются в один и тот же элемент области значений (4).
* Сюръективная? Нет. Например, нет целого числа $x$, такого чтобы $x^2 = 2$ или $x^2 = -1$. Область значений $\mathbb{Z}$ содержит отрицательные числа, которые не могут быть результатом возведения в квадрат целого числа. Образ этой функции — это множество неотрицательных квадратов целых чисел: $\{0, 1, 4, 9, \ldots\}$.

4. Key Takeaways

• Отношение — это набор упорядоченных пар, связывающих элементы из двух множеств.
• Функции — это особый вид отношений, где каждый элемент первого множества связан ровно с одним элементом второго.
• Область определения - это все возможные входы функции, область значений - все возможные выходы.
• Инъективность означает, что разные входы дают разные выходы.
• Сюръективность означает, что каждый возможный выход достигается хотя бы одним входом.
• Биективные функции - это те, которые одновременно инъективны и сюръективны, и они обратимы.
• Понимание свойств отношений (рефлексивность, симметричность, транзитивность) важно для классификации отношений эквивалентности и порядка.

5. Now Try It

Подумайте о множестве людей $P$ и множестве городов $C$. Создайте отношение $R$, где $(p, c) \in R$, если человек $p$ родился в городе $c$. Определите, является ли это отношение функцией из $P$ в $C$. Если нет, объясните почему. Если да, то является ли она инъективной, сюръективной или биективной? Обоснуйте свой ответ.

Успех выглядит так: Вы четко объясняете, является ли отношение функцией, и если да, то какие свойства она имеет (или не имеет) по отношению к инъективности, сюръективности и биективности, используя определения из текста.