Equivalence relation/Equivalence classes/Section

An equivalence relation ${}R\subseteq M\times M$ on a set ${}M$ may also be considered as a partition of the set ${}M$. In order to see this, the concept of an equivalence class is helpful.

Definition

Let ${}R\subseteq M\times M$ be an equivalence relation, and let ${}x\in M$. Then

${}[x]:={\left\{y\in M\mid (x,y)\in R\right\}}\,$

is called the equivalence class of ${}x$ with respect to ${}R$.

Hence, ${}[x]$ is the subset of all elements of ${}M$ that are equivalent with ${}x$. Every element ${}y\in [x]$ is called a representative of the equivalence class ${}[x]$.

Definition

Let ${}\sim$ be an equivalence relation on a set ${}M$. A subset ${}T\subseteq M$ is called a system of representatives for the equivalence relation, if for every equivalence class

there exists exactly one element in ${}T$ of this class.

Three equivalence classes for the equivalence relation given by being parallel.

Example

On the set of all lines in the plane, we can consider the property of being parallel as an equivalence relation. A line is parallel to itself, the relation is obviously symmetric, and if ${}G_{1}$ and ${}G_{2}$ are parallel, and ${}G_{2}$ and ${}G_{3}$ are parallel, then also ${}G_{1}$ and ${}G_{3}$ are parallel. The equivalence class of a line ${}G$ consists of all lines that are parallel to ${}G$; these lines form a parallel linenschar. We fix a point ${}M$ in the plane. Then there exists, for every line ${}G$, a parallel line ${}G'$ running through ${}M$. Therefore, every equivalence class can be uniquely represented by a line through the point ${}M$. The set of lines through ${}M$ form a system of representatives for this equivalence relation.

Under the equivalence relation "accessible overland“, the islands and the continents are the equivalence classes.

Example

Suppose that we are in a situation, where certain places (or Objects) can be reached from certain other places or not. This accessibility can be determined by the choice of means of transport, or by a more abstract kind of movement. Such an accessibility relation yields often an equivalence relation. A place can be reached by starting at this place, this gives reflexivity. The symmetry of accessibility means that if it is possible to reach ${}A$ starting from ${}B$, then it is also possible to reach ${}B$ starting from ${}A$. This is a natural condition for accessibility, though it is probably not fulfilled for every kind of accessibility. The transitivity does hold whenever we can do the movements after each other, like going from ${}A$ to ${}B$, and then from ${}B$ to ${}C$.

If, for example, accessible is given by walking overland, then two places are equivalent if and only if they lie on the same island (or continent). Islands and continents are the equivalence classes. In topology, the concept of path-connectedness plays an important role: two points are path-connected if they can be connected by a continuous path. Or: On the set of integer number, there is a colony of fleas, and every jump of a flea has the length of five unites (in both directions). How many flea populations are there, which fleas can meet each other?

Example

In chess, a bishop can move diagonally and arbitrarily far in every direction. Two squares (positions) on a chess board are called bishop-equivalent if it is possible to reach, starting from one square, by finitely many bishop moves, the other square. This is an equivalence relation on the chess board. Moving diagonally, the color of the position does not change; therefore, a bishop standing on a white square will always stay on a white square. Moreover, a bishop, standing on a white square, can reach every white square. Hence, there are only two equivalence classes: the white squares and the black squares; accordingly, we talk about the light-squared and the dark-squared bishop (this is not the color of the piece).

Example

Visualization of the example. The equivalence classes are colored differently.

We consider the lattice product set ${}M=\mathbb {N} \times \mathbb {N}$. We fix the jumps (think about a Meadow jumping mouse that can perform these jumps and no other jumps)

$\pm (2,0)\,\,{\text{ and }}\,\,\pm (3,3).$

We say that two points ${}P=(a,b),\,Q=(c,d)\in M$ are equivalent if it is possible, starting in ${}P$, to reach the point ${}Q$ with a sequence of such jumps. This defines an equivalence relation (the main reason is that for every jump also its negative jump is allowed). Typical questions are: How can we characterize equivalent points, how can we decide whether two points are equivalent or not?