# Equivalence relation/Quotient set/Section
## Definition

Let $R\subseteq M\times M$ denote an equivalence relation. The set
    $M/R:={\left\{[x]\mid x\in M\right\}}\,$
$R$

## Definition

Let $R\subseteq M\times M$ denote an equivalence relation, and let $M/R$ be the quotient set. The mapping
    $q_{R}\colon M\longrightarrow M/R,x\longmapsto [x],$
$R$
With the quotient set, the equivalence classes become elements of a new set. Under the canonical projection, equivalent elements are mapped to the same element and so they are identified. We also say that the theory of equivalence relations is the art of identifying. In working with quotient sets, the proper definition is not so important any more; instead, we work rather with the intrinsic properties of these sets. The following statement says, in particular, that every equivalence relation can be obtained as in example. Therefore, equivalent always means equal under a suitable mapping.

## Lemma

Let $M$ be a set, and let $\sim$ denote an equivalence relation on $M$, together with the equivalence classes $[x]$ and the quotienten set
$M/\sim$
* $x\sim y$ if and only if $[x]=[y]$, and this holds if and only if $[x]\cap [y]\neq \emptyset$.
* $M=\bigcup _{[x]\in M/\sim }[x]$ is a disjoint union.
* The canonical projection is surjective.
    $q\colon M\longrightarrow M/\sim ,x\longmapsto [x],$
* We have $q^{-1}([x])=[x]$.

### Proof

* Let $x$ and $y$ be equivalent, and $u\in [x]$. Then $x\sim u$, and, by transitivity, also $y\sim u$, thus $u\in [y]$. Therefore, the equivalence classes coincide. The implication from the middle to the right is clear, because, due to $x\sim x$, the equivalence classes are not empty. Suppose now that $[x]\cap [y]\neq \emptyset$, and let $z$ denote an element in the intersection. Then $x\sim z$ and $y\sim z$, and, by transitivity, $x\sim y$.
* Because of the reflexivity, we have $x\in [x]$; therefore, $M=\bigcup _{[x]\in M/\sim }[x]$. This union is disjoint by part (1).
* The surjectivity is clear because of the definition of the quotient set, and since $x$ is sent to the class $[x]$.
* We have
    $q^{-1}([x])={\left\{y\in M\mid q(y)=[x]\right\}}={\left\{y\in M\mid [y]=[x]\right\}}={\left\{y\in M\mid y\sim x\right\}}=[x]\,.$
$\Box$
Important mathematical constructions can be described as a quotient set to a certain equivalence relation on a simpler set. This is illustrated by the following examples.

## Example

Let $n\in \mathbb {N}$, and set $M=\mathbb {R} ^{n+1}\setminus \{0\}$. $\mathbb {R} ^{n+1}$ is a real vector space, the scalar multiplication of $\lambda \in \mathbb {R}$ and $x\in \mathbb {R} ^{n+1}$ is denoted by $\lambda \cdot x$ Moreover, set
    $R={\left\{(x,y)\in M\times M\mid {\text{ there exists some }}\lambda \in \mathbb {R} \setminus \{0\}{\text{ such that }}\lambda \cdot x=y\right\}}\,.$
Therefore, two points are defined to be equivalent if they can be transformed to each other by scalar multiplication with a scalar $\lambda \neq 0$. We can also say that two points are equivalent if they define the same line through the origin.
This is indeed an equivalence relation. The reflexivity follows from $x=1x$ for every $x\in M$. To prove symmetry, suppose $xRy$, that is, there exists some $\lambda \neq 0$ such that $\lambda x=y$. Then also $y=\lambda ^{-1}x$ holds, as $\lambda$ has an inverse element. To prove transitivity, suppose that $xRy$ and $yRz$ holds; this means that there exist $\lambda ,\delta \neq 0$ such that $\lambda x=y$ and $\delta y=z$. Then $z=\delta y=(\delta \lambda )x$ with $\delta \lambda \neq 0$. The equivalence classes of this equivalence relation are the lines through the origin (but without the origin). The quotient set is called the real-projective space (of real dimension $n$), and is denoted by $[[:Template:Op:Projectivespace]]$.

## Example

Let $\mathbb {N}$ be the set of the natural numbers, and let $M=\mathbb {N} \times \mathbb {N}$ denote the product set with the componentwise addition. We define on $M$ a relation by
    $(a,b)\sim (c,d),{\text{ if }}a+d=b+c.$
This holds, in case $a\leq c$, if and only if there exists an $e\in \mathbb {N}$ (namely $e=c-a$) such that
    $(c,d)=(a,b)+(e,e)\,.$
This means that the pairs differ by an diagonal element, that is, a pair, where both components coincide. This relation is an equivalence relation on $M$, see exercise. If we consider $\mathbb {N} \times \mathbb {N}$ as a square lattice (a "discrete coordinate system“), then the equivalence classes are given by the points on a "discrete line“ parallel to the diagonal. The points $(a,b)$ with $a\geq b$ are equivalent with $(a-b,0)$; they have a representative where the second component is $0$. The points $(a,b)$ with $a\leq b$ are equivalent to $(0,b-a)$; they have a representative where the first component is $0$. The points $(a,a)$ are equivalent to $(0,0)$. We call the representative of an equivalence class where at least one component is $0$, the standard representative of this equivalence class. The standard representatives are the discrete points of the confining lines of the quadrant; for a point, we find its standard representative by going, parallel to the diagonal, in direction of these lines. Two points are equivalent if and only if they have the same standard representative.
We call now the quotient set, that is, the set of the equivalence classes under this equivalence relation, the set of the integer numbers, and denote it with $\mathbb {Z}$. Every integer number has exactly one standard representative of the form $n:=(n,0)$ with $n\in \mathbb {N} _{+}$, or of the form $0:=(0,0)$, or of the form $-n:=(0,n)$ with $n\in \mathbb {N} _{+}$. We consider a natural number $n$ as the integer number $(n,0)$.
We want to "add“ two integer numbers, that is, two such equivalence classes $[(a,b)]$ and $[(c,d)]$, in order to get a binary operation $\oplus$ on $\mathbb {Z}$. The first idea that comes to mind is to define this via
    $[(a,b)]\oplus [(c,d)]:=[(a+c,b+d)]\,.$
However, here we encounter the problem whether this is well-defined, since this operation is defined using certain representatives; it is not clear at all whether different representatives give the same result. Therefore, if $(a,b)\sim (a',b')$ and $(c,d)\sim (c',d')$ holds, then we have to check that also
    $(a+c,b+d)\sim (a'+c',b'+d')\,$
holds, which means $[(a+c,b+d)]=[(a'+c',b'+d')]$. This is the case, see exercise. Moreover, one can show that this operation on $\mathbb {Z}$ is associative and commutative, that $[(0,0)]$ is the neutral element of this operation, and that for every element $[(a,b)]$ there exists an inverse element, namely $[(b,a)]$.
We define now a multiplication on $\mathbb {Z}$ via
    $[(a,b)]\cdot [(c,d)]:=[(ac+bd,ad+bc)]\,.$
Again, this is well-defined, and one can show that the multiplication is associative and commutative, that $1=[(1,0)]$ is the neutral element, and that the distributive law holds.
The following proposition describes the universal property of the quotient set.

## Lemma
### Proof

$\Box$
* ↑ For example, suitable interpretations for the pairs in this context are: the pair $(a,b)$ represents the result of a football game, where $a$ gives the number of goals scored by the home team, and $b$ gives the number of goals scored by the away team; or: the pair $(a,b)$ represents the ages of a human couple, where $a$ represents the age of the woman, and $b$ represents the age of the husband. Going to the equivalence classes means that we are only interested in goal difference of in the age difference, not for the exact result of the ages of the individual persons. Man kann also the Paar als a step folge aus $a$ stepen nach rechts and $b$ stepen nach links ansehen.