Editing Equivalence relation (section)

== Generating equivalence relations ==

* Given any set <math>X,</math> an equivalence relation over the set <math>[X \to X]</math> of all functions <math>X \to X</math> can be obtained as follows. Two functions are deemed equivalent when their respective sets of [[fixpoint]]s have the same [[cardinality]], corresponding to cycles of length one in a [[permutation]].
* An equivalence relation <math>\,\sim\,</math> on <math>X</math> is the [[Equivalence relation#Equivalence kernel|equivalence kernel]] of its [[surjective]] [[Equivalence relation#Projection|projection]] <math>\pi : X \to X / \sim.</math><ref>[[Garrett Birkhoff]] and [[Saunders Mac Lane]], 1999 (1967). ''Algebra'', 3rd ed. p.&nbsp;33, Th. 18. Chelsea.</ref> Conversely, any [[surjection]] between sets determines a partition on its domain, the set of [[preimage]]s of [[Singleton (mathematics)|singleton]]s in the [[codomain]]. Thus an equivalence relation over <math>X,</math> a partition of <math>X,</math> and a projection whose domain is <math>X,</math> are three equivalent ways of specifying the same thing.
* The intersection of any collection of equivalence relations over ''X'' (binary relations viewed as a [[subset]] of <math>X \times X</math>) is also an equivalence relation. This yields a convenient way of generating an equivalence relation: given any binary relation ''R'' on ''X'', the equivalence relation {{em|generated by R}} is the intersection of all equivalence relations containing ''R'' (also known as the smallest equivalence relation containing ''R''). Concretely, ''R'' generates the equivalence relation 
::<math>a \sim b</math> if there exists a [[natural number]] <math>n</math> and elements <math>x_0, \ldots, x_n \in X</math> such that <math>a = x_0</math>, <math>b = x_n</math>, and <math>x_{i-1} \mathrel{R} x_i</math> or <math>x_i \mathrel{R} x_{i-1}</math>, for <math>i = 1, \ldots, n.</math>
:The equivalence relation generated in this manner can be trivial. For instance, the equivalence relation generated by any [[total order]] on ''X'' has exactly one equivalence class, ''X'' itself.
* Equivalence relations can construct new spaces by "gluing things together." Let ''X'' be the unit [[Cartesian square]] <math>[0, 1] \times [0, 1],</math> and let ~ be the equivalence relation on ''X'' defined by <math>(a, 0) \sim (a, 1)</math> for all <math>a \in [0, 1]</math> and <math>(0, b) \sim (1, b)</math> for all <math>b \in [0, 1],</math> Then the [[Quotient space (topology)|quotient space]] <math>X / \sim</math> can be naturally identified ([[homeomorphism]]) with a [[torus]]: take a square piece of paper, bend and glue together the upper and lower edge to form a cylinder, then bend the resulting cylinder so as to glue together its two open ends, resulting in a torus.