Difference between revisions of "Equivalence relation"
From Maths
m |
(Refactoring this page to be more in line with other pages on relations.) |
||
| Line 1: | Line 1: | ||
| − | {{ | + | {{Refactor notice}} |
| + | __TOC__ | ||
| + | |||
| + | ==Definition== | ||
| + | A [[relation]] {{M|\sim}} in {{M|X}}<ref group="Notes">This terminology means {{M|\sim \subseteq X\times X}}, as described on the [[relation]] page.</ref> is an ''equivalence relation'' if it has the following properties{{rSTTJ}}: | ||
| + | * Reflexivity, {{M|x\sim x}} | ||
| + | * Symmetricity, {{M|x\sim y}} implies {{M|y\sim x}} | ||
| + | * Transitivity, {{M|x\sim y}} and {{M|y\sim z}} implies {{M|x\sim z}}. | ||
| + | {| class="wikitable" border="1" | ||
| + | |- | ||
| + | ! | ||
| + | ! Name | ||
| + | ! Definition | ||
| + | |- | ||
| + | ! 1 | ||
| + | | [[Relation#Types_of_relation|Reflexive]] | ||
| + | | {{M|\forall x\in X[(x,x) \in \sim]}}. Often written {{M|\forall x\in X[x\sim x]}}. | ||
| + | |- | ||
| + | ! 2 | ||
| + | | [[Relation#Types_of_relation|Symmetric]] | ||
| + | | {{M|\forall x,y\in X[M|(x,y) \in \sim \implies (y,x) \in \sim]}}. Often written {{M|\forall x,y \in X[x\sim y \implies y\sim x]}}. | ||
| + | |- | ||
| + | ! 3 | ||
| + | | [[Relation#Types_of_relation|Transitive]] | ||
| + | | {{M|\forall x,y,z\in X[((x,y) \in \sim \wedge (y,z) \in \sim) \implies (x,z) \in \sim]}}. Often written {{M|\forall x,y,z \in X [(x\sim y \wedge y\sim z) \implies x\sim z]}}. | ||
| + | |} | ||
| + | ==Terminology== | ||
| + | *Sometimes, letters and other designations are used with symbols to distinguish between different equivalence relations, such as {{M|a \equiv_x b}}. | ||
| + | **For an {{M|x\in X}}, the [[equivalence class]] is written {{M|[x]}} or {{M|x_\sim}}. That is, {{M|\forall a\in X[a\in[x] \implies a\sim x]}}. | ||
| + | ==See Also== | ||
| + | *[[Relation]] | ||
| + | *[[Equivalence class]] | ||
| + | **[[An equivalence class partitions a set]]. | ||
| + | ==Notes== | ||
| + | <references group="Notes"/> | ||
| + | ==References== | ||
| + | <references/> | ||
| + | {{Relations navbox|plain}} | ||
| + | {{Definition|Set Theory|Abstract Algebra}} | ||
| + | |||
| + | |||
| + | |||
| + | =Old Page= | ||
An equivalence relation is a special kind of [[Relation|relation]] | An equivalence relation is a special kind of [[Relation|relation]] | ||
Revision as of 17:01, 18 March 2016
This page is currently being refactored (along with many others)
Please note that this does not mean the content is unreliable. It just means the page doesn't conform to the style of the site (usually due to age) or a better way of presenting the information has been discovered.
Contents
Definition
A relation [ilmath]\sim[/ilmath] in [ilmath]X[/ilmath][Notes 1] is an equivalence relation if it has the following properties[1]:
- Reflexivity, [ilmath]x\sim x[/ilmath]
- Symmetricity, [ilmath]x\sim y[/ilmath] implies [ilmath]y\sim x[/ilmath]
- Transitivity, [ilmath]x\sim y[/ilmath] and [ilmath]y\sim z[/ilmath] implies [ilmath]x\sim z[/ilmath].
| Name | Definition | |
|---|---|---|
| 1 | Reflexive | [ilmath]\forall x\in X[(x,x) \in \sim][/ilmath]. Often written [ilmath]\forall x\in X[x\sim x][/ilmath]. |
| 2 | Symmetric | [ilmath]\forall x,y\in X[M[/ilmath]. Often written [ilmath]\forall x,y \in X[x\sim y \implies y\sim x][/ilmath]. |
| 3 | Transitive | [ilmath]\forall x,y,z\in X[((x,y) \in \sim \wedge (y,z) \in \sim) \implies (x,z) \in \sim][/ilmath]. Often written [ilmath]\forall x,y,z \in X [(x\sim y \wedge y\sim z) \implies x\sim z][/ilmath]. |
Terminology
- Sometimes, letters and other designations are used with symbols to distinguish between different equivalence relations, such as [ilmath]a \equiv_x b[/ilmath].
- For an [ilmath]x\in X[/ilmath], the equivalence class is written [ilmath][x][/ilmath] or [ilmath]x_\sim[/ilmath]. That is, [ilmath]\forall a\in X[a\in[x] \implies a\sim x][/ilmath].
See Also
Notes
- ↑ This terminology means [ilmath]\sim \subseteq X\times X[/ilmath], as described on the relation page.
References
| |||||||||||
Old Page
An equivalence relation is a special kind of relation
Required properties
Given a relation [ilmath]R[/ilmath] in [ilmath]A[/ilmath] we require the following properties to define a relation (these are restated for convenience from the relation page)
Reflexive
A relation [ilmath]R[/ilmath] if for all [ilmath]a\in A[/ilmath] we have [ilmath]aRa[/ilmath]
Symmetric
A relation [ilmath]R[/ilmath] is symmetric if for all [ilmath]a,b\in A[/ilmath] we have [ilmath]aRb\implies bRa[/ilmath]
Transitive
A relation [ilmath]R[/ilmath] is transitive if for all [ilmath]a,b,c\in A[/ilmath] we have [ilmath]aRb\text{ and }bRc\implies aRc[/ilmath]
Definition
A relation [ilmath]R[/ilmath] is an equivalence relation if it is:
- reflexive
- symmetric
- transitive
