5. Equivalence relations

Definition

A relation \sim on a set A will be called an equivalence relation, it it has the following three properties:

  • reflexive: for all a\in A, a\sim a,
  • symmetric: for all a,b\in A, if a\sim b, then b\sim a,
  • transitive: for all a,b,c\in A, ifa\sim b and b\sim c, then a\sim c.

E.g., a relation \mod on natural numbers such that n\mod m if and only if 2016|m-n is an equivalence relation. Indeed, for all n\in\mathbb{N}, we get 2016|n-n=0, so it is reflexive. It is also symmetric, because if 2016|n-m, then 2016|m-n. Finally, it is transitive, since if m\mod n and n\mod k, so 2016|m-n and 2016|n-k, then 2016|(m-n)+(n-k)=m-k, so m\mod k.

Meanwhile the relation \leq on natural numbers is not an equivalence relation, because it is not symmetric, e.g. 0\leq 1, but not 1\leq 0.

Equivalence relations often appear in the real world. E.g. the following relation is an equivalence relation. Two cars are in the relation if and only if they are of the same colour. Another example is the relation of siblings.

Fundamental theorem of equivalence relations

Given an equivalence relation \sim on a set A, the set of all elements which are in relation with a given a\in A is called the equivalence class of a and denoted by [a]_\sim. So [a]_\sim=\{b\in A\colon a\sim b\}. The family of all equivalence classes is denoted by A/\sim and called the quotient set.

It is easy to notice that if a\sim b, then [a]_\sim=[b]_\sim (the key role in this fact is played by transitivity). On the other hand, if a and b are not in relation \sim, then [a]_\sim\cap[b]_\sim=\varnothing. This observation implies the fundamental theorem of equivalence relations, which states that an equivalence relation on a set is actually the same as a partition of this set.

A family \mathcal{A}\subseteq \mathcal{P}(A) will be called a partition of A, if for any X,Y\in\mathcal{A}, X\cap Y=\varnothing, if only X\neq Y, and \bigcup\mathcal{A}=A.

The fundamental theorem states that every equivalence relation on a set generates a partition of the set, precisely the partition into its equivalence classes. On the other hand every partition of a set generates an equivalence relation on this set. It is the relation such that two elements are in it, if they are in the same element of the partition.

E.g. the relation on the set of cars in which two cars are in the relation if and only if they are of the same colour, generates a partition of the set of cars into classes of equivalence related to each colour of cars.

E.g. relation on \mathbb{R} such that x\sim y, if and only if x-y\in\mathbb{Z} generates the partition of \mathbb{R} into equivalence classes of this relation, e.g. [1/2]_\sim=\{z+1/2\colon z \in\mathbb{Z}\}, which are related to each number from the interval [0,1).

The partition of\{0,1,2,3\} into \{\{0\},\{1,2,3\}\} generates the following equivalence relation: \{\left<0,0\right>,\left<1,1\right>,\left<1,2\right>,\left<1,3\right>,\left<2,1\right>,\left<2,2\right>,\left<2,3\right>,\left<3,1\right>,\left<3,2\right>,\left<3,3\right>\}.

Cardinality of equivalence classes and of quotient set

Often we have to calculate the cardinality of each of the equivalence class of a given relation and the cardinality of its quotient set. E.g, in the relation \mathbb{R} such that x\sim y if and only if x-y\in\mathbb{Z}), no two distinct numbers in [0,1) are in relation, so function f\colon [0,1)\to \mathbb{R}/\sim given as f(x)=[x]_{\sim} is one-to-one, and therefore |\mathbb{R}/\sim|\geq \mathfrak{c}. On the other hand, any partition of the reals is of cardinality \leq \mathfrac{c}, so |\mathbb{R}/\sim|= \mathfrak{c}. Finally, if x\in \mathbb{R}, then [x]_{\sim}=\{y\in\mathbb{R}\colon x-y\in\mathbb{Z}\}=\{z+x\colon z\in\mathbb{Z}\}, and therefore |[x]_\sim|=|\mathbb{Z}|=\aleph_0, for any x\in\mathbb{R}.