Equivalence Relations

    In working with mappings that are not one-to-one, it is very useful to introduce the notion of an equivalence relation. The basic idea of an equivalence relation is to collect together elements that are in some way related, and then treat them as a single entity. The main goals of this topic are to show that every equivalence relation on a set can be realized as a partition of the set, and conversely; and that every equivalence relation can be defined in a natural way by a mapping.

Definition (Equivalence Relation) A relation on a nonempty set is an equivalence relation on if it satisfies the following three properties:

    (i) (Reflexive) If then
    
    (ii) (Symmetric) If and then
    
    (iii) (Transitive) If and and then
    

Definition (Equivalence Class) Let be an equivalence relation on a set and Then the equivalence class of is   The set of all equivalence classes of under is denoted by and the set consisting of exactly one element from each equivalence class from is called a complete set of equivalence class representatives.

Example (Equivalence Relation)

    (i) Let be a permutation group on and define a relation on by if and only if for some Then is an equivalence relation on
    
    (ii) Let be a positive integer. For integers we define if and only if Then is an equivalence relation on and is denoted instead by The set of equivalence classes is denoted
    
    (iii) Let be the set of all integers and let be the set of all nonzero integers. On the set of ordered pairs, define if and only if Then is an equivalence relation and the set of equivalence classes is
    
    (iv) Let two complex numbers be equivalent if their real parts are equal. Then this is an equivalence relation and the set of equivalence classes is
    
    (v) Let be a group and define if and only if or Then is an equivalence relation on
    
    (vi) Let be a group and define if and only if for some Then is an equivalence relation on and and are called conjugates.
    
    (vii) Let be a set and let For subsets and of define if and only if Then is an equivalence relation on

▪

Definition (Partition) A collection of nonempty subsets of a nonempty set forms a partition of provided

    (i) and
    
    (ii)
    

Proposition (Equivalence Relations and Partitions)    

    (i) Any partition of a set determines an equivalence relation.
    
    (ii) Any equivalence relation on a set determines a partition.
    
    (iii) There is a one-to-one correspondence between the equivalence relations on a set and the partitions of the set.
    
    
    Proof. (i): Assume that we are given a partition of the set Then the given partition yields an equivalence relation on by defining if there is some element in the partition to which both and belong. To prove that this is an equivalence relation first let then because belongs to one of the elements of the partition To show symmetric law: let and Then there is a element of the partition in which both and b both belong; and hence To show transitivity, let and Then and belong to the same subset say and and belong to the same subset say where Since is a partition Whence, and so is an equivalence relation on
    (ii): Let be the set of all equivalence classes of on a nonempty set   We will show that is a set of mutually disjoint subsets of whose union is Suppose Then and for some Since no member of is empty, and the union of the members of is Suppose that Then and Thus, and in fact To see this, let then and hence Thus, so that Similiarily, and so Therefore, the sets in are mutually disjoint, and is a partition of as desired.
    (iii): Beginning with an equivalence relation on a set (ii) shows that the equivalence class defines a partition on the set and (i) shows that this partition determines the original equivalence relation On the other hand, if a partition on a set is given, then the equivalence classes of the corresponding equivalence relation are the subsets in the original partition. Thus, there is a natural one-to-one correspondence between the equivalence relations on a set and the partitions of the set.

Definition (Natural Projection) Let be any set and let be an equivalence relation on Then the mapping defined by for all is called the natural projection from to

    For any we have if and only if Thus these are the same equivalence relations, that is; and are the same. Therefore, every equivalence relation can be realized as the equivalence relation defined in a natural way by a mapping. Notice that the natural projection is an onto mapping.

Proposition (Mapping Factorization) If is any mapping, and is the equivalence relation on by letting if and only if for then the mapping defined by for all is bijective; and hence we have a factorization   where is the inclusion mapping.  



    Proof. The mapping is well-defined since if and belong to the same equivalence class in then by definition of the equivalence relation we must have In addition, is onto since if then for some and thus we have Finally, is one-to-one since if then and so by definition which implies that Thus we have a one-to-one correspondence as desired; and we have a factorization of into a composition of better-behaved mappings since where is the inclusion mapping, as shown.

• print this page
• pages linking here
• related pages

Cite this as:
Equivalence Relations
Published by Library of Math -- Online math organized by subject into topics.
Written by Smith, David A.
http://www.libraryofmath.com/equivalence-relations.html