An equivalence relation is a binary relation on a set that can be used to say whether elements of are equivalent.
An equivalence relation satisfies the following properties:
Intuitively, any element is equivalent to itself, equivalence isn't directional, and if two elements are equivalent to the same third element then they're equivalent.
Whenever we have a set with an equivalence relation , we can divide into equivalence classes, i.e. sets of mutually equivalent elements. The equivalence class of some is the set of elements of equivalent to , written , and we say that is a "representative" of . We call the set of equivalence classes .
From the definition of an equivalence relation, it's easy to show that and if and only if .
If you have a set already partitioned into subsets ( is the disjoint_union of the elements of a collection ), you can go the other way and define a relation with two elements related whenever they're in the same subset ( when there is some with ). Then this is an equivalence relation, and the partition of the set is the set of equivalence classes under this relation (that is, and ).
Suppose you have a function and want to define a corresponding function , where can be any set. You define to be . This could be a problem; what if but ? Then wouldn't be well-defined. Whenever you define a function on equivalence classes in terms of representatives, you have to make sure the definition doesn't depend on which representative you happen to pick. In fact, one way you might arrive at an equivalence relation is to say that whenever .
If you have a function and want to define by , you have to verify that whenever , , equivalently .
Consider the integers with the relation if , for some . This is the integers mod . The addition and multiplication operations can be inherited from the integers, so it makes sense to talk about addition and multiplication mod .
The real numbers can be defined as equivalence classes of Cauchy sequences.
Isomorphism is an equivalence relation (unless the objects form a proper_class).