- отношение на множестве
- Отношением на множестве $A$ называется подмножество декартова квадрата этого множества, то есть множество упорядоченных пар элементов из $A$: $R \subseteq A \times A$
- функция
- Функцией называется соответствие, при котором каждому элементу из одного множества ставится в соответствие ровно один элемент из другого множества: $f: A \rightarrow B$
- инъективная функция
- Функция называется инъективной (взаимно-однозначной), если разным элементам множества $A$ соответствуют разные элементы множества $B$: $\forall a_1, a_2 \in A, a_1 \neq a_2 \Rightarrow f(a_1) \neq f(a_2)$
- сюръективная функция
- Функция называется сюръективной (на), если каждый элемент множества $B$ является образом хотя бы одного элемента множества $A$: $\forall b \in B \exists a \in A, f(a) = b$
- биективная функция
- Функция называется биективной (взаимно-однозначным соответствием), если она одновременно инъективна и сюръективна: $\forall a_1, a_2 \in A, a_1 \neq a_2 \Rightarrow f(a_1) \neq f(a_2)$ и $\forall b \in B \exists a \in A, f(a) = b$
- отношение эквивалентности
- Отношение эквивалентности на множестве $A$ — это отношение, которое рефлексивно, симметрично и транзитивно: $\forall a \in A, aRa$, $\forall a, b \in A, aRb \Rightarrow bRa$, $\forall a, b, c \in A, aRb \land bRc \Rightarrow aRc$
- частичный порядок на множестве
- Отношение частичного порядка на множестве $A$ — это отношение, которое антисимметрично, транзитивно и рефлексивно: $\forall a, b \in A, aRb \land bRa \Rightarrow a = b$, $\forall a, b, c \in A, aRb \land bRc \Rightarrow aRc$, $\forall a \in A, aRa$
- возрастающая функция
- Функция называется возрастающей (нестрого), если для любых $x_1, x_2 \in A, x_1 \leq x_2 \Rightarrow f(x_1) \leq f(x_2)$
- строго возрастающая функция
- Функция называется строго возрастающей, если для любых $x_1, x_2 \in A, x_1 < x_2 \Rightarrow f(x_1) < f(x_2)$