| Equivalence Relation |
Article Index for Equivalence |
Website Links For Relation |
Information AboutEquivalence Relation |
| CATEGORIES ABOUT EQUIVALENCE RELATION | |
| mathematical relations | |
|
# ( Reflexivity ) ''a'' ~ ''a'' # ( Symmetry ) if ''a'' ~ ''b'' then ''b'' ~ ''a'' # ( Transitivity ) if ''a'' ~ ''b'' and ''b'' ~ ''c'' then ''a'' ~ ''c'' A set together with an equivalence relation is called a setoid. Equivalence relations are often used to group together objects that are similar in some sense. EXAMPLES OF EQUIVALENCE RELATIONS
EXAMPLES OF RELATIONS THAT ARE NOT EQUIVALENCES
PARTITIONING INTO EQUIVALENCE CLASSES Every equivalence relation on ''X'' defines a Partition of ''X'' into subsets called Equivalence Class es: all elements equivalent to each other are put into one class. Conversely, if the set ''X'' can be partitioned into subsets, then we can define an equivalence relation ~ on ''X'' by the rule "''a'' ~ ''b'' if and only if ''a'' and ''b'' lie in the same subset". For example, if ''G'' is a Group and ''H'' is a Subgroup of ''G'', then we can define an equivalence relation ~ on ''G'' by writing ''a'' ~ ''b'' if and only if ''ab''-1 lies in ''H''. The equivalence classes of this relation are the right Coset s of ''H'' in ''G''. Since every equivalence relation can be identified with a partition and vice versa, the number of equivalence relations on a set ''X'' of ''n'' elements is given by the ''n''th Bell Number , ''Bn''. If an equivalence relation ~ on ''X'' is given, then the set of all its equivalence classes is the Quotient Set of ''X'' by ~ and is denoted by ''X''/~. For every equivalence relation, there is a Surjective canonical projection map π from ''X'' to ''X''/~ defined by π(''x'') = {Link without Title} . Conversely, any surjection between sets determines a partition on its domain, the set of preimages of singletons in the codomain. Thus there are three equivalent ways of formally "modding out by" some property: specifying an equivalence relation, specifying a partition, or specifying a projection map. GENERATING EQUIVALENCE RELATIONS If two equivalence relations over the set ''X'' are given, then their intersection (viewed as subsets of ''X''×''X'') is also an equivalence relation. This allows for a convenient way of defining equivalence relations: given any binary relation ''R'' on ''X'', the equivalence relation ''generated by R'' is the smallest equivalence relation containing ''R''. Concretely, the equivalence relation ~ generated by ''R'' can be described as follows: ''a'' ~ ''b'' if and only if there exist elements ''x''1, ''x''2,...,''x''''n'' in ''X'' such that ''x''1 = ''a'', ''x''''n'' = ''b'' and such that (''x''''i'' , ''x''''i'' +1) or (''x''''i'' +1, ''x''''i'') is in ''R'' for every ''i'' = 1,...,''n'' -1. Note that the resulting equivalence relation can often be trivial! For instance, the equivalence relation ~ generated by the binary relation ''≤'' has exactly one equivalence class: ''x''~''y'' for all ''x'' and ''y''. More generally, the equivalence relation will always be trivial when generated on a relation R having the "antisymmetric" property that, given any ''x'' and ''y'', either ''x'' R ''y'' or ''y'' R ''x'' must be true. In Topology , if ''X'' is a Topological Space and ~ is an equivalence relation on ''X'', then we can turn the quotient set ''X''/~ into a topological space in a natural manner. See Quotient Space for the details. One often generates equivalence relations to quickly construct new spaces by "gluing things together". Consider for instance the square ''X'' = and the equivalence relation on ''X'' generated by the requirements (''a'',0) ~ (''a'',1) for all ''a'' in [0,1 and (0,''b'') ~ (1,''b'') for all ''b'' in [0,1]. Then the quotient space ''X''/~ can be naturally identified with a Torus : take a square piece of paper, bend it to glue together the upper and lower edge, then bend the resulting cylinder to glue together the two mouths. COMMON NOTIONS IN EUCLID'S ''ELEMENTS'' The first person who introduced the idea of equivalence relations was Euclid in his book '' The Elements '', under the heading of "Common Notions". Common Notion 1. Things which equal the same thing also equal one another. Nowadays, a Binary Relation is called Euclidean if it satisfies this property. Unfortunately, he did not mention symmetry or reflexivity. But this suggests an alternative formulation: An equivalence relation is a relation which is Euclidean, symmetric and reflexive. SEE ALSO Equivalent concepts Related concepts EXTERNAL LINKS |
|
|