Relations and Equivalence Relations

---

Relations and Equivalence Relations

---

1. What is a Relation?

A relation on a set $A$ is a collection of ordered pairs of elements from $A$. Formally, a relation $R$ on a set $A$ is a subset of the Cartesian product $A \times A$.

For example, if $A = \{1, 2, 3\}$, a relation $R$ on $A$ could be:

$$R = \{(1, 2), (2, 3)\}$$

This means that 1 is related to 2, and 2 is related to 3.

---

2. Types of Relations

A relation $R$ on a set $A$ can have different properties. Some important ones are:

a) Reflexive Relation

A relation $R$ on a set $A$ is reflexive if for every element $a \in A$, the pair $(a, a)$ is in the relation $R$.

$$\forall a \in A, (a, a) \in R$$

Example:
If $A = \{1, 2, 3\}$, the relation $R = \{(1, 1), (2, 2), (3, 3)\}$ is reflexive.

---

b) Symmetric Relation

A relation $R$ on a set $A$ is symmetric if whenever $(a, b) \in R$, then $(b, a) \in R$.

$$\forall a, b \in A, \, (a, b) \in R \Rightarrow (b, a) \in R$$

Example:
If $A = \{1, 2, 3\}$, and $R = \{(1, 2), (2, 1)\}$, this relation is symmetric because if 1 is related to 2, then 2 is also related to 1.

---

c) Transitive Relation

A relation $R$ on a set $A$ is transitive if whenever $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$.

$$\forall a, b, c \in A, \, (a, b) \in R \, \text{and} \, (b, c) \in R \Rightarrow (a, c) \in R$$

Example:
If $A = \{1, 2, 3\}$, and $R = \{(1, 2), (2, 3), (1, 3)\}$, the relation is transitive because if 1 is related to 2, and 2 is related to 3, then 1 is also related to 3.

---

3. Equivalence Relations

An equivalence relation is a relation on a set $A$ that satisfies three specific properties:

1. Reflexive: For all $a \in A$, $(a, a) \in R$.
2. Symmetric: For all $a, b \in A$, if $(a, b) \in R$, then $(b, a) \in R$.
3. Transitive: For all $a, b, c \in A$, if $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$.

If a relation $R$ satisfies all three properties, it is called an equivalence relation.

---

4. Example of Equivalence Relation

Let $A = \{1, 2, 3, 4\}$ and define a relation $R$ by:

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

This relation $R$ is:

• Reflexive: Each element is related to itself.
• Symmetric: If $(1, 2) \in R$, then $(2, 1) \in R$; similarly for $(3, 4)$ and $(4, 3)$.
• Transitive: For example, $(1, 2)$ and $(2, 1)$ imply $(1, 1)$, and so on.

Thus, $R$ is an equivalence relation.

---

5. Equivalence Classes

Given an equivalence relation $R$ on a set $A$, the equivalence class of an element $a \in A$, denoted by $[a]$, is the set of all elements that are related to $a$ under $R$.

$$[a] = \{ b \in A \mid (a, b) \in R \}$$

Example:
For the relation $R$ defined on $A = \{1, 2, 3, 4\}$, the equivalence classes are:

• $[1] = \{1, 2\}$
• $[3] = \{3, 4\}$

Each equivalence class groups elements that are "equivalent" to each other.

---

6. Partition of a Set

An equivalence relation on a set $A$ partitions $A$ into disjoint equivalence classes. This means that the equivalence classes form a partition of $A$, meaning that:

• Every element of $A$ belongs to exactly one equivalence class.
• The equivalence classes are disjoint (no overlap).

Example:
Given $A = \{1, 2, 3, 4\}$ and the relation $R$ from earlier, the equivalence classes $[1] = \{1, 2\}$ and $[3] = \{3, 4\}$ form a partition of $A$, because each element of $A$ is in exactly one equivalence class.

---

7. Equivalence Relation Properties

• Reflexivity: Every element is related to itself.
• Symmetry: If $a$ is related to $b$, then $b$ is related to $a$.
• Transitivity: If $a$ is related to $b$ and $b$ is related to $c$, then $a$ is related to $c$.

These properties ensure that equivalence relations allow us to group elements of a set into classes that share some common property.

---