Properties of Relations

Topics: Discrete Mathematics - Relation

---

(definition)

A given relation $R$ in a set $A$ is:

• Reflexive if and only if $aRa\forall a\in A$
• Symmetric if and only if $aRb⟺bRa\forall a,b\in A$
• Antisymmetric if and only if $aRb\wedge bRa⟹a=b$
• Transitive if and only if $aRb\wedge bRc⟹aRc\forall a,b,c\in A$

The properties of a given relation can be easily determined with the help of its digraph and matrix.

Example 1

Let $A=\{a,b,c,d\}$ and:

$R=\{(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(b,d),(d,d)\}$

Notice that:

• $R$ isn’t reflexive since $c/Rc$
• $R$ isn’t symmetric since $aRc$ but $c/Ra$
• $R$ isn’t antisymmetric since $aRb$ and $bRa$ but $a\ne b$
• $R$ isn’t transitive since $aRb$ and $bRd$ but $a/Rd$

Example 2

Let $A=\mathbb{R}$. Let $R$ be the relation defined by $x\le y$ if $x,y\in \mathbb{R}$.

Notice that:

• $R$ is reflexive since $x\le x$ $\forall x\in \mathbb{R}$
• $R$ isn’t symmetric since $1\le 2/⟹2\le 1$
• $R$ is antisymmetric since $x\le y\wedge y\le x⟹x=y$.
• $R$ is transitive since $x\le y\wedge y\le z⟹x\le z$