Difference between revisions of "Equivalence relation"
(Importing text file) |
(Unite comment with text) |
||
| (6 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| − | + | {{TEX|done}} | |
| + | {{MSC|03E}} | ||
| − | + | 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 (of a relation)|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|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}} | ||
Revision as of 20:37, 30 December 2014
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
Equivalence relation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Equivalence_relation&oldid=17622