Релације

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

Бинарна релација $\rho$ у скупу $A$ је сваки подскуп скупа $A^2 = A \times A$ ; пишемо $a \rho b$ кад $(a, b) \in \rho$ . Релација је рефлексивна ако је $a \rho a$ за свако $a \in A$ , симетрична ако из $a \rho b$ следи $b \rho a$ , антисиметрична ако из $a \rho b$ и $b \rho a$ следи $a = b$ , а транзитивна ако из $a \rho b$ и $b \rho c$ следи $a \rho c$ .

Релација еквиваленције је рефлексивна, симетрична и транзитивна и дели скуп на дисјунктне класе еквиваленције. Релација поретка је рефлексивна, антисиметрична и транзитивна, као $\leq$ или дељивост у $\mathbb{N}$ . Пазите: антисиметрична не значи „није симетрична“ (једнакост је и једно и друго), а да релација није транзитивна, довољно је наћи један контрапример.

Таблица релације ρ: Исти остатак при дељењу са 3
ρ	1	2	3	4	5	6	7	8
1
2
3
4
5
6
7
8

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

Класе: {1, 4, 7}, {2, 5, 8}, {3, 6}

Рефлексивна: да
Симетрична: да
Антисиметрична: не1 ρ 4 и 4 ρ 1, а 1 ≠ 4
Транзитивна: да

Исти остатак при дељењу са 3 дели бројеве на класе, као што дан у недељи дели датуме у примеру: цела дијагонала је означена, а таблица је симетрична у односу на њу. Дељивост је релација поретка, а код суседних бројева један контрапример,

1 \rho 2

2 \rho 3

, али не

1 \rho 3

, показује да релација није транзитивна.

Кад библиотека сврстава књиге по жанру, а календар датуме по дану у недељи, то је подела на класе еквиваленције. Релација поретка одређује редослед радова на градилишту, где неки посао мора да се заврши пре другог.

Дани у недељи

На скупу датума у октобру 2026, $A = \{1, 2, \ldots, 31\}$ , посматрајте релацију $a \rho b$ ако је $a - b$ дељиво са 7. Покажите да је то релација еквиваленције, одредите класе и наведите датуме који падају истог дана у недељи као 1. октобар, који је четвртак.

Решење

Рефлексивност: $a - a = 0$ је дељиво са 7. Симетричност: ако $7 \mid a - b$ , онда $7 \mid b - a$ , јер је $b - a = -(a - b)$ .
Транзитивност: ако $7 \mid a - b$ и $7 \mid b - c$ , онда 7 дели и збир $(a - b) + (b - c) = a - c$ .
Класа датума 1 је $[1] = \{1, 8, 15, 22, 29\}$ , а остале су $[2], [3], \ldots, [7]$ , на пример $[7] = \{7, 14, 21, 28\}$ . Има их 7, по једна за сваки дан у недељи.
Класе $[1]$ , $[2]$ и $[3]$ имају по 5 датума, а остале по 4. Оне су дисјунктне и заједно дају цео скуп: $3 \cdot 5 + 4 \cdot 4 = 31$ .

Одговор: Релација је релација еквиваленције са 7 класа, а четвртак је 1., 8., 15., 22. и 29. октобра 2026.

Задатак за вежбу

Да ли је у скупу $\{1, 2, \ldots, 10\}$ релација „ $a$ и $b$ имају исти остатак при дељењу са 3“ релација еквиваленције? Ако јесте, наведите класе.

Прикажи решење

Јесте: сваки број има исти остатак као сам себе; ако $a$ и $b$ имају исти остатак, имају га и $b$ и $a$ ; ако исти остатак имају $a$ и $b$ , као и $b$ и $c$ , имају га и $a$ и $c$ . Класе су $\{3, 6, 9\}$ , $\{1, 4, 7, 10\}$ и $\{2, 5, 8\}$ .

Релације

Укратко

Изаберите релацију

Пример из живота

Дани у недељи

Решење

Задатак за вежбу