Equivalence relations

Let’s suppose you have cities A, B and C that are connected by two – way roads. Of course, city A is trivially connected to itself. Furthermore, if A is connected to B, then B is connected to A. Also, if A is connected to B and B connected to C, it means that A is connected to C.

Definition: Let $R$ be homogeneous relation on set $A$. We say that $R$ is

a) reflexive if $(\forall x \in A) (x, x) \in \mathbf{R}$

b) irreflexive if $(\forall x \in A) (x, x) \notin \mathbf{R}$

c) symmetric if $(\forall x, y \in A) ((x, y) \in \mathbf{R} \rightarrow (y, x) \in \mathbf{R})$

d) anti – symmetric if $(\forall x, y \in A) ((x, y) \in \mathbf{R}  \land (y, x) \in \mathbf{R}\rightarrow x = y)$

e) transitive if $(\forall x, y, z \in A) ((x, y) \in \mathbf{R} \land (y, z) \in \mathbf{R}\rightarrow (x, z) \in \mathbf{R})$.

Definition: Homogeneous binary relation which is reflexive, symmetric and transitive is called equivalence relation and it is denoted by $\sim$.

Note: Some of the notations that express the fact that two elements $a$ and $b$ of a set are equivalent with respect to an equivalence relation $R$ are: $a \sim b$, $aRb$ and $a \sim _{R}b$.

Example 1: Relation ‘is equal to’ on the set of numbers is an equivalence relation:

reflexivity: $a = a$

symmetry: $a = b \rightarrow b = a$

transitivity: $a = b \land b = c \rightarrow a = c$.

Example 2: Let $\tau$ be a set f all triangles in a plane. Relations $\sim$ ‘is similar’, $\cong$ ‘is congruent’  and $\rho$ ‘has the same area’ are equivalence relations on $\tau$.

Definition: Let $a, b \in \mathbf{Z}$ and $n \in \mathbf{N}$. We say that $a$ is congruent to $b$ modulo $n$, and write $a \equiv b (mod n)$, if $n \mid a – b$.

Example 3:

a) $23 \equiv (3 mod 5)$ because $5 \mid 23 – 3$

b) $14\not \equiv(3 mod 2)$ because $2 \nmid 14 – 3$

Example 4: Relation $\equiv (mod n)$ is an equivalence relation on set $\mathbf{Z}$:

reflexivity: $(\forall a \in \mathbf{Z}) a \equiv a (mod n)$

symmetry: $(\forall a, b \in \mathbf{Z}) a \equiv b (mod n) \rightarrow b  \equiv a (mod n)$

transitivity: $(\forall a, b, c \in \mathbf{Z}) a \equiv b (mod n)  \land b \equiv c (mod n) \rightarrow a \equiv c (mod n)$.

Example 5: Is the relation $\geq$ on $\mathbf{R}$ an equivalence relation?

Solution: Relation $\geq$ is reflexive and transitive, but it is not symmetric. For example, take a look at numbers $4$ and $1$; $4 \geq 1$ does not imply that $1 \geq 4$.

Equivalence classes

Definition: Let $A$ be a non – empty set and $\sim$ equivalence relation on $A$. For every $a \in A$ we define the equivalence class as $$[a] = \{x \in A: x \sim a\} \subseteq A.$$

Equivalence relations 2023

Note: Every equivalence class is a non – empty set, since $\sim$ is reflexive ($a \sim a$ for every $a \in A$) so $a \in [a]$.

For every $x \in A$ there exists an unique equivalence class $[a] \subseteq A$ to which it belongs, i.e.

$$(\forall x \in A)(\exists! [a] \subseteq A) (x \in [a]).$$

If we put in one set all that equivalence classes which are defined by equivalence relation $\sim \subseteq A^{2}$, we”ll get a set whose elements are non – empty, disjunctive and whose union is equal to set $A$. Therefore, we”ll get a partition of set $A$.

Definition: Let $A$ be a non – empty set and $\sim$ equivalence relation on set $A$. Partition of set $A$ which consist of equivalence classes of relation $\sim$ is called the quotient set of set $A$ and it is denoted by $A/_{\sim}$.

$$A/_{\sim} = \{[a]: a \in A\}$$

Example 6: Let $E^{3}$ be the set of all points in a space. An ordered pair of points $(A, B) \in E^{3} \times E^{3}$ defines an oriented segment, which is often denoted by $\overset {\longrightarrow}{AB}$. Let

$$O = \left \{\overset {\longrightarrow}{AB}: A, B \in E^{3}\right\} = E^{3}\times E^{3}$$

be a set of all oriented segments in $E^{3}$. We define relation $\equiv$ ‘to be equivalent’ on O:

$$\overset {\longrightarrow}{AB} \equiv \overset {\longrightarrow}{CD}$$ if and only if segments $\overset {——}{AD}$ and $\overset {——}{BC}$ have the same midpoint. $\equiv$ is an equivalence relation on O.

The quotient set $V^{3} = O/_{\equiv}$ is called vector space, and its elements (equivalence classes) are vectors.

Vector $\overset {\rightarrow}{v}$ is a class of oriented segments, $\overset {\longrightarrow}{AB}$ etc., defined up to parallel translation.

Equivalence relations 2023