Difference between revisions of "Equivalence relation"

From Maths
Jump to: navigation, search
m (See Also: Linking out to new pages)
m (See Also)
Line 37: Line 37:
 
* {{link|Passing to the quotient|function}} - things are often factored through the [[canonical projection of an equivalence relation]]
 
* {{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
 
* [[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]]
+
** [[Factoring a function through the projection of an equivalence relation induced by that function yields an injection]]
 +
*** [[If a surjective function is factored through the canonical projection of the equivalence relation induced by that function then the yielded function is a bijection]]
  
 
==Notes==
 
==Notes==

Revision as of 22:26, 8 October 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.
This page is waiting for a final review, then this notice will be removed.

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]
    • Defined as [ilmath][a]:=\{b\in X\ \vert\ b\sim 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

  1. This terminology means [ilmath]\sim \subseteq X\times X[/ilmath], as described on the relation page.

References

  1. Set Theory - Thomas Jech - Third millennium edition, revised and expanded


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