Equivalence Relations

One of the most important relations in modern mathematics are equivalence relations. By the way, they appear in a large part of mathematics studies.

Equivalence Relation

In the previous post, we showed some properties such as:

• reflective;
• symmetrical;
• transitive;
• anti-symmetric.

Some of them are necessary to be an equivalence relation.

Definition (Equivalence Relations): A relation $\mathcal{R}$ on a set $A$ is said to be an equivalence relation on $A$ if $\mathcal{R}$ is reflexive, symmetric and transitive.

Examples

To illustrate, look at the following example:

Example 1: The diagonal relation defined as $\Delta = \\{(x,x); x\in A\\}$, is an equivalence relation over $A.$ This is the “smallest” equivalence relation over $A$

Example 2: The relation $A\times A$ over $A$ is the “largest” equivalence relation over $A.$

Example 3: Let $A=\mathbb{Z}$. The relationship:

is an equivalence relation over the set of integers.

Equivalence Class module R

Definition Let $\mathcal{R}$ be an equivalence relation over a non-empty set $A.$ For each $a \in A,$ the subset of $A$ defined by

$$\overline{a} = \\{x \in A;\quad x \mathcal{R} a\\},$$

is said to be the equivalence class determined by the element a module $\mathcal{R}$.

Note that if $\mathcal{R}$ is an equivalence relation over a non-empty set $A,$ then for all $a \in A,$ we have $a \in a,$ that is, each equivalence class is a non-empty subset of $A.$

Example 3: Let $A=\mathbb{Z}$. The relationship:

• For $0\in \mathbb{Z}$

• For $1 \in \mathbb{Z},$ we have

• For $2 \in \mathbb{Z},$ we have

• For $3 \in \mathbb{Z},$ we have

Result for equivalence relation

Next we will see an important result for the equivalence relationship for $\mathbb{Z}/\mathcal{R} = \\{\overline{0}, \overline{1}, \overline{2}\\}.$

Theorem Let $\mathcal{R}$ be an equivalence relation on a non-empty set $A$ and $a, b \in A.$ The following propositions are equivalent:

• (a) $a\mathcal{R} b$
• (b) $a \in b$
• (c) $b \in a$
• (d) $a = b.$

Demo:

• (a) $\Longleftrightarrow$ (b)

It follows immediately from the definition of equivalence class.

• (b) $\Longrightarrow$ (c)

  • $a \in b$ implies $a\mathcal{R} b$ by class definition.
  • Just as $a\mathcal{R} b$ implies $b\mathcal{R} a$ due to the symmetry of $\mathcal{R}$.
  • Consequently, $b\mathcal{R} a$ implies $b\mathcal{R} \overline{a}$ by the class definition.

• (c) $\Longrightarrow$ (d)

Note that $\overline{a}$ and $\overline{b}$ are two sets. In this way, showing that $\overline{a} = \overline{b}$ is equivalent to showing that:

• (1) $\overline{a} \subseteq \overline{b}$
• (2) $\overline{b} \subseteq \overline{a}$

1. Let us show that $\overline{a} \subseteq \overline{b}$.

For $x \in \overline{a},$ we have $x\mathcal{R} a$ and, as per hypothesis, $b \in \overline{a},$ we also have $b\mathcal{R} a.$

Since $\mathcal{R}$ is symmetric, we obtain $x\mathcal{R} a$ and $a\mathcal{R} b$. This fact implies the transitivity of $\mathcal{R}$ than $x\mathcal{R} b$. Consequently,$x \in b$.

2. Analogous.

• (d) $\Longrightarrow$ (a)

Let $x \in \overline{a} = \overline{b}.$ Then, by class definition, we have $x\mathcal{R} a$ and $x\mathcal{R} b$.

Now, from the symmetric and transitive property of $\mathcal{R}$, we obtain $a\mathcal{R} b$.

$\square$

Application of the result

Let us now show the statement $\mathbb{Z}/\mathcal{R} = \\{\overline{0}, \overline{1}, \overline{2}\\}.$

For $A = \mathbb{Z}$ and $\mathcal{R} = \\{(x, y) \in Z × Z; ~ x − y \text{ é múltiplo de } 3\\}$

Note that $\mathbb{Z}/\mathcal{R} \supseteq \\{\overline{0}, \overline{1}, \overline{2}\\}.$

If $a \in \mathbb{Z}/\mathcal{R},$ then when we divide $a$ by $3,$ we obtain than $a = 3q + r,$ with $r = 0, 1$ or $2.$

In this case, we have $r \in a$. By the previous theorem, we have $a = r$

Therefore $\mathbb{Z}/\mathcal{R} \subseteq \\{\overline{0}, \overline{1}, \overline{2}\\}$.

This is the summary of Equivalence Relations. Wait for the next posts.