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

Отношение – это подмножество декартова произведения множеств. Обозначается как $R \subseteq A \times B$.

Пример отношения: $R = \{ (x,y) | x^2 + y^2 \leq 9 \}$, где $A$ и $B$ – множества действительных чисел.

Функция – отображение одного множества в другое, при котором каждому элементу из области определения соответствует единственный элемент из области значений.

Обозначение функции: $f : X \rightarrow Y$.

Отношение $R$ называется рефлексивным, если $(a,a) \in R$ для любого элемента $a$ из множества $A$.

Пример: отношение равенства $=$ является рефлексивным.

Отношение $R$ симметрично, если $(a,b) \in R$ тогда и только тогда, когда $(b,a) \in R$.

Пример: отношение "быть братом" симметрично.

Отношение $R$ транзитивно, если $(a,b) \in R$ и $(b,c) \in R$ влечет за собой $(a,c) \in R$.

Пример: отношение порядка $\leq$ транзитивно.

Упорядоченная пара – это множество $\{ a, b \}$ с указанием порядка элементов. Записывается как $(a, b)$.

Декартово произведение множеств $A$ и $B$ обозначается $A \times B$ и состоит из всех упорядоченных пар $(a, b)$, где $a \in A$ и $b \in B$.

$$A \times B = \{(a, b) | a \in A, b \in B\}$$

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

Формально: $f(x_1) = f(x_2)$ тогда и только тогда, когда $x_1 = x_2$.

Сюръективная функция отображает область определения на всю область значений.

Формально: для каждого $y \in Y$ существует хотя бы один $x \in X$ такой, что $f(x) = y$.

Биективная функция одновременно инъективна и сюръективна.

Композиция двух функций $f : X \rightarrow Y$ и $g : Y \rightarrow Z$ определяется как $g \circ f : X \rightarrow Z$ и записывается как $g(f(x))$.