Релације

Бинарна релација у скупу $A \times B$ је сваки његов подскуп.
Ако је $\rho \subset {A^2}$ онда је $\rho $ бинарна релација на скупу $A$.

Нека је $\rho $ бинарна релација у скупу $A \times B$. Ако је $\left( {a,b} \right) \in \rho $ каже се да је $a$ у релацији $\rho $ са $b$. То се записује $a\rho b$, тј.

$\left( {a,b} \right) \in \rho \Leftrightarrow a\rho b$

Аналогно, $\left( {a,b} \right) \notin \Leftrightarrow \neg \left( {a\rho b} \right)$

Бинарна релација $\rho $ у скупу А је:

$R$ (рефлексивна) $ \Leftrightarrow $ $(\forall a \in А)(a \rho a)$
$AR$ (анитрефлексивна) $ \Leftrightarrow $ $(\forall a \in А) \neg (a \rho a)$
$S$ (симетрична) $ \Leftrightarrow $ ${\text{(}}\forall a,b \in A){\text{ }}a\rho a \Rightarrow b\rho a$
$AS$ (асиметрична) $ \Leftrightarrow $ ${\text{(}}\forall a,b \in A){\text{ (}}a\rho b \wedge b\rho a) \Rightarrow a = b$
$Т$ (транзитивна) $ \Leftrightarrow $ ${\text{(}}\forall a,b,c \in A){\text{ }}(a\rho b \wedge b\rho c) \Rightarrow {\text{ }}a\rho c$

Релација еквиваленције

Релација еквиваленције је бинарна релација која је истовремено $R$, $S$ и $T$.

Релација поретка

Релација поретка је бинарна релација која је истовремено $R$, $АS$ и $T$.

Релација строгог поретка

Релација строгог поретка је бинарна релација која је истовремено $АR$, $АS$ и $T$.

Класе еквиваленције

Ако је $p$ релација у скупу $A$, онда је скуп:

$\left\{ {x\backslash x \in A \wedge x\rho a} \right\}$

где је $a \in A$ назива класа еквиваленције скупа $A$, индукована елементом $a$, у односу на релацију $\rho $.

Скуп свих класа еквиваленције скупа $А$ у односу на релацију еквиваленције тог скупа назива се фрактор скуп (или количински скуп) скупа $А$.

Елементи $a$ и $b \in A$ су упоредиви, с обзиром на релацију поретка $p$ скупа $А$, ако и само ако је $a\rho b \vee a = b \vee b\rho a$.

Уређење скупа

Уређени пар $(A,\rho )$, где је релација $ \rho $ поретка у скупу $А$, назива се уређен скуп.

Ако су свака два елемента у скупу $А$ упоредива, онда се каже да је $А$ потпуно (линеарно) уређен скуп. Иначе $А$ је парцијално уређен скуп.

Релација поретка се означава са $ \leqslant $ а релација строгог поретка са $ < $.

У уређеном скупу $(A, \leqslant)$

$a \in A$	је минимални елемент	$ \Leftrightarrow \neg {\text{(}}\exists x \in A)(x \ne a \wedge x \leqslant a)$
$a \in A$	је најмањи елемент	$ \Leftrightarrow {\text{(}}\forall x \in A)(a \leqslant x)$
$a \in A$	је максимални елемент	$\neg (\exists x \in A)(x \ne a \wedge a \leqslant x)$
$a \in A$	је највећи елемент	$\left( {\forall x \in A} \right)\left( {x \leqslant a} \right)$

Инверзна релација

Инверзна релација релације $\rho $ је релација

${\rho ^{ - 1}} = \left\{ {\left( {b,a} \right)\backslash \left( {a,b} \right) \in \rho } \right\}$

Композиција

Композиција (производ) релација ${\rho _1} \subset A \times B$ и ${\rho _2} \subset B \times C$ је релација:

${\rho _1}^\circ {\rho _2} = \left\{ {\left( {x,y} \right)\backslash \left( {\exists z} \right)\left( {x{\rho _1}z \wedge z{\rho _2}y} \right)} \right\}$