What is an equivalence class example

You are given a set $A = \{1,3,5,9,11,18\}$ and a relation $R$ on $A$ given by $$R = \{(a,b) \mid a - b \text{ is divisible by } 4\}.$$ For example, $(1,9) \in R$ because $1 - 9 =

What is an equivalence class example

You are given a set $A = \{1,3,5,9,11,18\}$ and a relation $R$ on $A$ given by $$R = \{(a,b) \mid a - b \text{ is divisible by } 4\}.$$ For example, $(1,9) \in R$ because $1 - 9 = 8$ is divisible by $4$.

Now, any time we have an equivalence relation on a set, this relation partitions the set into disjoint sets called equivalence classes, where each equivalence class is given by those elements that are equivalent to each other with respect to the equivalence relation. In order for this to make sense, however, we first need to check that $R$ is indeed an equivalence relation, otherwise we can not speak of its equivalence classes.

Clearly $R$ is reflexive because $a - a = 0$, and $0$ is always divisible by $4$. $R$ is also symmetric because if $a$ is divisible by $4$, then $-a$ is divisible by $4$. If $a - b$ is divisible by $4$ and $b - c$ is divisible by $4$, then $a - c = (a - b) + (b - c)$ is also divisible by $4$, so $R$ is also transitive, and hence an equivalence relation.

The equivalence classes for $R$ on $A$ turn out to be $$C_1 = \{1,5,9\}$$ $$C_2 = \{3,11\}$$ $$C_3 = \{18\}$$ Note that these sets are disjoint, and together they contain all elements of $A$, just like we expected. To see why for example $C_1$ is an equivalence class, notice that $1 - 5 = 4$ and $1 - 9 = 8$ are divisible by $4$, so $1$ is equivalent to $5$ and $9$ with respect to $R$. However, $1$ is not equivalent to for example $3$, because $1 - 3 = 2$ is not divisible by $4$. Hence $1$ and $3$ must be in different equivalence classes.

Video liên quan