Difference between revisions of "Equivalence relation"
m (→Definition: - write instead of written) |
m |
||
| Line 1: | Line 1: | ||
| − | {{Refactor notice}} | + | {{Refactor notice|review=yes}} |
__TOC__ | __TOC__ | ||
Revision as of 01:54, 12 April 2016
This page is waiting for a final review, then this notice will be removed.
Contents
Definition
A relation, [ilmath]\sim[/ilmath], in [ilmath]X[/ilmath][Note 1] is an equivalence relation if it has the following properties[1]:
| Name | Definition | |
|---|---|---|
| 1 | Reflexive | [ilmath]\forall x\in X[(x,x) \in \sim][/ilmath]. Which we write [ilmath]\forall x\in X[x\sim x][/ilmath]. |
| 2 | Symmetric | [ilmath]\forall x,y\in X[M[/ilmath]. Which we write [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]. Which we write [ilmath]\forall x,y,z \in X [(x\sim y \wedge y\sim z) \implies x\sim z][/ilmath]. |
Terminology
- An equivalence class is the name given to the set of all things which are equivalent under a given equivalence relation.
- Often denoted [ilmath][a][/ilmath] for all the things equivalent to [ilmath]a[/ilmath]
- This is not unique, if [ilmath]b\sim a[/ilmath] then we could write [ilmath][b][/ilmath] instead. (Equivalence classes are either equal or disjoint)
- Defined as [ilmath][a]:=\{b\in X\ \vert\ b\sim a\}[/ilmath]
- Often denoted [ilmath][a][/ilmath] for all the things equivalent to [ilmath]a[/ilmath]
- If there are multiple equivalence relations at play, we often use different letters to distinguish them, eg [ilmath]\sim_\alpha[/ilmath] and [ilmath][\cdot]_\alpha[/ilmath]
- Sometimes different symbols are employed, for example [ilmath]\cong[/ilmath] denotes a topological homeomorphism (which is an equivalence relation on topological spaces)
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
