Editing Equivalence relation (section)

== Algebraic structure ==

Much of mathematics is grounded in the study of equivalences, and [[order relation]]s. [[Lattice (order)|Lattice theory]] captures the mathematical structure of order relations. Even though equivalence relations are as ubiquitous in mathematics as order relations, the algebraic structure of equivalences is not as well known as that of orders. The former structure draws primarily on [[group theory]] and, to a lesser extent, on the theory of lattices, [[Category theory|categories]], and [[groupoid]]s.

=== Group theory ===

Just as [[order relation]]s are grounded in [[Partially ordered set|ordered sets]], sets closed under pairwise [[supremum]] and [[infimum]], equivalence relations are grounded in [[Partition of a set|partitioned sets]], which are sets closed under [[bijection]]s that preserve partition structure. Since all such bijections map an equivalence class onto itself, such bijections are also known as [[permutation]]s. Hence [[permutation group]]s (also known as [[Group action (mathematics)|transformation groups]]) and the related notion of [[Orbit (group theory)|orbit]] shed light on the mathematical structure of equivalence relations.

Let '~' denote an equivalence relation over some nonempty set ''A'', called the [[Universe (mathematics)|universe]] or underlying set. Let ''G'' denote the set of bijective functions over ''A'' that preserve the partition structure of ''A'', meaning that for all <math>x \in A</math> and <math>g \in G, g(x) \in [x].</math> Then the following three connected theorems hold:<ref>Rosen (2008), pp.&nbsp;243–45. Less clear is §10.3 of [[Bas van Fraassen]], 1989. ''Laws and Symmetry''. Oxford Univ. Press.</ref>
* ~ partitions ''A'' into equivalence classes. (This is the {{em|Fundamental Theorem of Equivalence Relations}}, mentioned above);
* Given a partition of ''A'', ''G'' is a transformation group under composition, whose orbits are the [[Partitions of a set|cells]] of the partition;{{#tag:ref|
''Proof''.<ref>Bas van Fraassen, 1989. ''Laws and Symmetry''. Oxford Univ. Press: 246.</ref> Let [[function composition]] interpret group multiplication, and function inverse interpret group inverse. Then ''G'' is a group under composition, meaning that <math>x \in A</math> and <math>g \in G, [g(x)] = [x],</math> because ''G'' satisfies the following four conditions:
* ''G is closed under composition''. The composition of any two elements of ''G'' exists, because the [[Domain of a function|domain]] and [[codomain]] of any element of ''G'' is ''A''. Moreover, the composition of bijections is [[bijective]];<ref>Wallace, D. A. R., 1998. ''Groups, Rings and Fields''. Springer-Verlag: 22, Th. 6.</ref>
* ''Existence of [[identity function]]''. The [[identity function]], ''I''(''x'') = ''x'', is an obvious element of ''G'';
* ''Existence of [[inverse function]]''. Every [[bijective function]] ''g'' has an inverse ''g''<sup>&minus;1</sup>, such that ''gg''<sup>−1</sup> = ''I'';
* ''Composition [[Associativity|associates]]''. ''f''(''gh'') = (''fg'')''h''. This holds for all functions over all domains.<ref>Wallace, D. A. R., 1998. ''Groups, Rings and Fields''.  Springer-Verlag: 24, Th. 7.</ref>
Let ''f'' and ''g'' be any two elements of ''G''. By virtue of the definition of ''G'', [''g''(''f''(''x''))] = [''f''(''x'')] and [''f''(''x'')] = [''x''], so that [''g''(''f''(''x''))] = [''x'']. Hence ''G'' is also a transformation group (and an [[automorphism group]]) because function composition preserves the partitioning of <math>A. \blacksquare</math>}}
* Given a transformation group ''G'' over ''A'', there exists an equivalence relation ~ over ''A'', whose equivalence classes are the orbits of ''G''.<ref>Wallace, D. A. R., 1998. ''Groups, Rings and Fields''. Springer-Verlag: 202, Th. 6.</ref><ref>Dummit, D. S., and Foote, R. M., 2004. ''Abstract Algebra'', 3rd ed. John Wiley & Sons: 114, Prop. 2.</ref>

In sum, given an equivalence relation ~ over ''A'', there exists a [[transformation group]] ''G'' over ''A'' whose orbits are the equivalence classes of ''A'' under ~.

This transformation group characterisation of equivalence relations differs fundamentally from the way [[Lattice (order)|lattices]] characterize order relations. The arguments of the lattice theory operations [[Meet (mathematics)|meet]] and [[Join (mathematics)|join]] are elements of some universe ''A''. Meanwhile, the arguments of the transformation group operations [[Function composition|composition]] and [[Inverse function|inverse]] are elements of a set of [[bijections]], ''A'' → ''A''.

Moving to groups in general, let ''H'' be a [[subgroup]] of some [[Group (mathematics)|group]] ''G''. Let ~ be an equivalence relation on ''G'', such that <math>a \sim b \text{ if and only if } a b^{-1} \in H.</math> The equivalence classes of ~&mdash;also called the orbits of the [[Group action (mathematics)|action]] of ''H'' on ''G''&mdash;are the right '''[[coset]]s''' of ''H'' in ''G''. Interchanging ''a'' and ''b'' yields the left cosets.

Related thinking can be found in Rosen (2008: chpt. 10).

=== Categories and groupoids ===

Let ''G'' be a set and let "~" denote an equivalence relation over ''G''. Then we can form a [[groupoid]] representing this equivalence relation as follows. The objects are the elements of ''G'', and for any two elements ''x'' and ''y'' of ''G'', there exists a unique morphism from ''x'' to ''y'' [[if and only if]] <math>x \sim y.</math>

The advantages of regarding an equivalence relation as a special case of a groupoid include:
*Whereas the notion of "free equivalence relation" does not exist, that of a [[Free object|free groupoid]] on a [[directed graph]] does. Thus it is meaningful to speak of a "presentation of an equivalence relation," i.e., a presentation of the corresponding groupoid;
* Bundles of groups, [[Group action (mathematics)|group action]]s, sets, and equivalence relations can be regarded as special cases of the notion of groupoid, a point of view that suggests a number of analogies;
*In many contexts "quotienting," and hence the appropriate equivalence relations often called [[Congruence relation|congruences]], are important. This leads to the notion of an internal groupoid in a [[Category (mathematics)|category]].<ref>Borceux, F. and Janelidze, G., 2001. ''Galois theories'', Cambridge University Press, {{ISBN|0-521-80309-8}}</ref>

=== Lattices ===

The equivalence relations on any set ''X'', when ordered by [[set inclusion]], form a [[complete lattice]], called '''Con''' ''X'' by convention. The canonical [[Map (mathematics)|map]] '''ker''' : ''X''^''X'' → '''Con''' ''X'', relates the [[monoid]] ''X''^''X'' of all [[Function (mathematics)|function]]s on ''X'' and '''Con''' ''X''. '''ker''' is [[surjective]] but not [[injective]]. Less formally, the equivalence relation '''ker''' on ''X'', takes each function ''f'' : ''X'' → ''X'' to its [[Kernel (algebra)|kernel]] '''ker''' ''f''. Likewise, '''ker(ker)''' is an equivalence relation on ''X''^''X''.