Editing Equivalence relation (section)

=== 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).