Difference between revisions of "Equivalence relation"
m |
m (→See Also: Linking out to new pages) |
||
| Line 35: | Line 35: | ||
*[[Equivalence class]] | *[[Equivalence class]] | ||
**[[An equivalence class partitions a set]]. | **[[An equivalence class partitions a set]]. | ||
| + | * {{link|Passing to the quotient|function}} - things are often factored through the [[canonical projection of an equivalence relation]] | ||
| + | * [[Equivalence relation induced by a map]] - while many things induce equivalence relations, the "purity" of any [[function]] doing so means this ought to be here | ||
| + | ** [[Factoring a function through the canonical projection of the equivalence relation induced by the map yields an injection and furthermore if the map is surjective the yielded map is a bijection]] | ||
| + | |||
==Notes== | ==Notes== | ||
<references group="Note"/> | <references group="Note"/> | ||
Revision as of 22:20, 8 October 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
- Relation
- Equivalence class
- Passing to the quotient - things are often factored through the canonical projection of an equivalence relation
- Equivalence relation induced by a map - while many things induce equivalence relations, the "purity" of any function doing so means this ought to be here
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
