Equivalence relation/Examples/Introduction/Section

Definition

An equivalence relation on a set ${}M$ is a relation ${}R\subseteq M\times M$ fulfilling the following three properties (for arbitrary ${}x,y,z\in M$).

1. ${}x\sim x$ (reflexive).
2. ${}x\sim y$ implies ${}y\sim x$ (symmetric).
3. From ${}x\sim y$ and ${}y\sim z$ we can deduce ${}x\sim z$ (transitive).

Here, ${}x\sim y$

means that the pair ${}(x,y)$ belongs to ${}R$.

Example

A basic example of an equivalence relation is the equality on an arbitrary set ${}M$. Under equality, every element is only equivalent with itself.

In such examples from "daily life“, one has to be cautious, as these properties are usually not defined as precisely as mathematical concepts. In everyday life, similarity is more important that equality with respect to a certain property. However, similarity is not an equivalence relation; it is reflexive and symmetric but not transitive. If ${}A$ and ${}B$ are similar, and ${}B$ and ${}C$ as well, then ${}A$ and ${}C$ might be already not similar any more (in the same way: is a neighbor of, is related to, etc.).

Wildebeest form an equivalence class with respect to the equivalence relation belonging to the same species, zebras as well.

Example

In many situations, we are not interested in objects individually, instead, we are interested in some of their specific properties. Objects that behave equally with respect to a certain property might be considered as equivalent (with respect to this property). Such an equality with respect to a certain property defines an equivalence relation. If, for example, we are only interested in the color of some objects, then objects that have (exactly) the same color are equivalent to each other. If we are interested, among a collection of animals, not for their individual properties but only for the species they belong to, then two animals are equivalent if and only if they belong to the same species. Students might be considered as equivalent if they study the same combination of subjects. Vectors can be considered as equivalent if they have the same distance to the origin, etc. An equivalence relation is typically a certain way to look at certain objects, which considers certain objects as equal.

The equality with respect to a property can be made precise by the following mathematical construction.

Example

Let ${}M$ and ${}N$ be sets, and let ${}f\colon M\rightarrow N$ denote a mapping. In such a situation, we always get an equivalence relation on the domain ${}M$ of the mapping by declaring two elements ${}x,y\in M$ to be equivalent if they map under ${}f$ to the same element, that is, if ${}f(x)=f(y)$ holds. If the mapping ${}f$ is injective, then the equivalence relation defined by ${}f$ on ${}M$ is the equality. If the mapping is constant, then all elements from ${}M$ are equivalent under the corresponding equivalence relation.

For a mapping ${}f\colon M\rightarrow N$, the set of all points ${}x\in M$ mapping to a certain point ${}z\in N$ is called the fiber over ${}z$. In this situation ,the equivalence classes (see below) are just the fibers.

Example

Let ${}d\in \mathbb {N}$ be fixed. We consider on ${}\mathbb {Z}$ the equivalence relation ${}\sim$, where two numbers ${}a,b\in \mathbb {Z}$ are considered to be equivalent if their difference ${}a-b$ is a multiple of ${}d$. Two numbers are equivalent if and only if it is possible to reach from one number the other number by jumps of length ${}d$. Using division with remainder, this means that two numbers are equivalent to each other if, upon division by ${}d$, they leave the same remainder.

Example

We consider the floor of a real number, that is, the mapping

$\lfloor \,\,\rfloor \colon \mathbb {R} \longrightarrow \mathbb {Z} ,t\longmapsto \lfloor t\rfloor .$

A real number ${}t$ is mapped to the largest integer number that is smaller or equal ${}t$. Here, the interval ${}[n,n+1)$ (with integer bound ${}n$, closed on the left, open on the right) is mapped to ${}n\in \mathbb {Z}$. With respect to this mapping, two real numbers are equivalent if and only if they lie in the same interval of this type. In the decimal expansion, this means that their digits before the point are identical.

We can also consider the digits after the point. This corresponds to the mapping

$\mathbb {R} \longrightarrow [0,1),t\longmapsto t-\lfloor t\rfloor .$

Under the equivalence relation defined by this mapping, two real numbers are equivalent if their digits after the point are identical. This is the case if and only if their difference is an integer number.