# Relation

Keywords: relations, reflexivity, symmetry, transitivity, anti-symmetry, equivalence, partial order:, dichotomy, order

## Definition

${A}^{2}=A×A=\left\{\left(a,b\right):a\in A,b\in A\right\}$
$\rho \subseteq {A}^{2}$

The relation ρ is a set of ordered pairs, a subset of an Cartesian squere AxA.

Example:

$A=\left\{1,3,6\right\}$
$AxA=\left\{\left(1,1\right),\left(1,3\right),\left(1,6\right),\left(3,1\right),\left(3,3\right),\left(3,6\right),\left(6,1\right),\left(6,3\right),\left(6,6\right)\right\}$
$\rho =\left\{\left(1,1\right),\left(1,3\right),\left(1,6\right),\left(3,3\right),\left(3,6\right),\left(6,6\right)\right\}|\rho \subseteq {A}^{2},$

The relation ρ in this case means (less or equal): (1≤1), (1≤3), (1≤6), (3≤3), (3≤6), (6≤6).

## Properties of Relations

Reflexivity

$\left(a\in A\right):a\rho a$

IN CASE OF ORDERED GRAPH: every vertex of graph hase loop.

Example:ρ is reflexiv, because for every element of  A is true: $\left(1\le 1\right),\left(3\le 3\right),\left(6\le 6\right)$

Symmetry

$\left(a,b\in A\right):a\rho b⇒b\rho a$

IN CASE OF ORDERED GRAPH: every edge of the graph is two sided.

Example:ρ is not symmetric, because if 3 ≤ 6 [or (3, 6) ∈ ρ], does not follow that 6 ≤ 3 [or (6, 3) ∈ ρ].

Transitivity

$\left(a,b,c\in A\right):a\rho b\wedge b\rho c⇒a\rho c$

IN CASE OF ORDERED GRAPH: if there is a path between two vertices, there is a longer path too between them.

Example:ρ is transitiv, because if 1 ≤ 3 and 3 ≤ 6 means 1 ≤ 6.

Anti-symmetry

$\left(a,b\in A\right):a\rho b⇒b\rho a$

IN CASE OF ORDERED GRAPH: there is 0 or 1 edge between any of two different vertecies.

Example:ρ is ant-symmetric, because each number is less than or equal to itself.

## Types of Relations

• Equivalence Relations: reflexive, symmetric and transitivev
• Partial order: reflexive, anti-symmetric and transitivevv
• Dichotomy: for every a, b ∈ A,  (a, b) ∈ ρ or (b, a) ∈ ρ
IN CASE OF ORDERED GRAPH: there is a path between any two points of the graph.
• Order:, partial order and dichotomy