Namespaces
Variants
Actions

Difference between revisions of "Equivalence relation"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(tex, partial rewrite)
Line 1: Line 1:
A [[Binary relation|binary relation]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e0360301.png" /> on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e0360302.png" /> with the following properties:
+
{{TEX|done}}
 +
{{MSC|03E}}
  
1) for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e0360303.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e0360304.png" /> (reflexivity);
+
Let $X$ be a set. An equivalence relation on $X$ is a subset $R\subseteq X\times X$ that satisfies the following three properties:
  
2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e0360305.png" /> (symmetry);
+
1) Reflexivity: for all $x\in X$, $(x,x)\in R$;
  
3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e0360306.png" /> (transitivity).
+
2) Symmetry: for all $x,y\in X$, if $(x,y)\in R$ then $(y,x)\in R$;
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e0360307.png" /> maps the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e0360308.png" /> into a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e0360309.png" />, then the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e03603010.png" /> is an equivalence.
+
3) Transitivity: for all $x,y,z \in X$, if $(x,y)\in R$ and  $(y,z)\in R$ then $(x,z)\in R$.
  
For any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e03603011.png" /> the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e03603012.png" /> consisting of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e03603013.png" /> equivalent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e03603014.png" /> is called the equivalence class of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e03603015.png" />. Any two equivalence classes either are disjoint or coincide, that is, any equivalence defines a partition (decomposition) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036030/e03603016.png" />, and vice versa.
+
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|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.
 +
 
 +
 
 +
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$. 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.

Revision as of 16:07, 1 June 2012

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.


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$. 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.

How to Cite This Entry:
Equivalence relation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Equivalence_relation&oldid=26964
This article was adapted from an original article by V.N. Grishin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article