Namespaces
Variants
Actions

Equivalence relation

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

2020 Mathematics Subject Classification: Primary: 03E [MSN][ZBL]

Let $X$ be a set. An equivalence relation on $X$ is a subset $R\subseteq X\times X$ that satisfies the following three properties:

1) Reflexivity: for all $x\in X$, $(x,x)\in R$;

2) Symmetry: for all $x,y\in X$, if $(x,y)\in R$ then $(y,x)\in R$;

3) Transitivity: for all $x,y,z \in X$, if $(x,y)\in R$ and $(y,z)\in R$ then $(x,z)\in R$.

When $(x,y)\in R$ we say that $x$ is equivalent to $y$.

Instead of $(x,y)\in R$, the notation $xRy$, or even $x\sim y$, is also used.

An equivalence relation is a binary relation.

Example: If $f$ maps the set $X$ into a set $Y$, then $R=\{(x_1,x_2)\in X\times X\,:\, f(x_1)=f(x_2)\}$ is an equivalence relation (cf. Kernel of a function).

For any $y\in X$ the subset of $X$ that consists of all $x$ that are equivalent to $y$ is called the equivalence class of $y$, denoted $[y]_R$. Any two equivalence classes either are disjoint or coincide, that is, any equivalence relation on $X$ defines a partition (decomposition) of $X$, and vice versa.

A subset $A$ of $X$ is saturated with respect to $R$ if $a \in A,\, b \in X,\,a R b \Rightarrow b \in A$: so $A$ is saturated if and only if it is a union of equivalence classes of $R$. For any subset $A$ of $X$, the saturation $A^R$ is the set $\{ b \in X : \exists a \in A,\,a R b \} = \cup_{a \in A} [a]_R$, the union of the equivalence classes that meet $A$.

References

  • N. Bourbaki, Theory of Sets, Eléments de mathématiques 1, reprint ed. Springer (2004) ISBN 3-540-22525-0 Zbl 1061.03001
How to Cite This Entry:
Equivalence relation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Equivalence_relation&oldid=54153
This article was adapted from an original article by V.N. Grishin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article