Математичка логика, скупови, релације и функције

Релације

Бинарна релација у скупу $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 $ у скупу А је:

  1. $R$ (рефлексивна) $ \Leftrightarrow $ $(\forall a \in А)(a \rho a)$
  2. $AR$ (анитрефлексивна) $ \Leftrightarrow $ $(\forall a \in А) \neg (a \rho a)$
  3. $S$ (симетрична) $ \Leftrightarrow $ ${\text{(}}\forall a,b \in A){\text{ }}a\rho a \Rightarrow b\rho a$
  4. $AS$ (асиметрична) $ \Leftrightarrow $ ${\text{(}}\forall a,b \in A){\text{ (}}a\rho b \wedge b\rho a) \Rightarrow a = b$
  5. $Т$ (транзитивна) $ \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\}$