Relation

Topics: Discrete Mathematics - Algebra

---

A (binary) relation associates elements of one set with elements of another (or the same) set.

There are three types of relations:

• Functions
• Equivalence relations
• Order relations

Relations can also be seen as a set. They have a domain and a range. Relations can have several properties and they can also have inverses. Relations can be represented graphically with a digraph, and they can also be represented with a matrix.

Examples §

Trivial Examples

Examples of trivial binary relations are “greater than” ($\ge$), “equal to” ($=$) or “less than” ($\le$). Notice how these relations establish an association between two (and only two) elements of two sets.

Example 1

Let $A=B=\{a,b\}$. We have that:

$$A\times B=\{(a,a),(a,b),(b,a),(b,b)\}$$

There are $2^4=16$ possible relations in $A\times B$:

• $R_1=\varnothing$
• $R_2=\{(a,a)\}$
• $R_3=\{(a,b)\}$
• $R_4=\{(b,a)\}$
• $R_5=\{(b,b)\}$
• $R_6=\{(a,a),(a,b)\}$
• $R_7=\{(a,a),(b,a)\}$
• $R_8=\{(a,a),(b,b)\}$
• $R_9=\{(a,b),(b,a)\}$
• $R_{10}=\{(a,b),(b,b)\}$
• $R_{11}=\{(b,a),(b,b)\}$
• $R_{12}=\{(a,a),(a,b),(b,a)\}$
• $R_{13}=\{(a,a),(a,b),(b,b)\}$
• $R_{14}=\{(a,a),(b,a),(b,b)\}$
• $R_{15}=\{(a,b),(b,a),(b,b)\}$
• $R_{16}=A\times B$

We can say the following about some of these relations:

$$\text{dom}(R_6)=\{a\}$$

$$\text{ran}(R_6)=\{a,b\}$$

$$R_{12}^{-1}=\{(a,a),(b,a),(a,b)\}=R_{12}$$

$$R_{13}^{-1}=\{(a,a),(b,a),(b,b)\}\ne R_{13}$$

Example 2

Let $X=\{2,3,4\}$, $Y=\{3,4,5,6,7\}$. We define the relation $R$ as:

$$(x,y)\in R\text{ if }x\text{ divides }y$$

The relation seen as a set is:

$$R=\{(2,4),(2,6),(3,3),(3,6),(4,4)\}$$

…and we can also see that:

$$\text{dom}(R)=\{2,3,4\}$$

$$\text{ran}(R)=\{3,4,6\}$$