Equivalence Relation

    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.

Group Theory Books

Theory and Practice of Group Psychotherapy, Fifth Edition List Price: $55.00 Buy New: $31.90 You Save: $23.10 (42%) New (55) Used (44) from $29.90In this completely revised and updated fifth edition of group psychotherapy?s standard text, Dr. Yalom and his collaborator present the most recent developments in the field, drawing on nearly a decade (more)

Student Manual for Corey's Theory and Practice of Group Counseling, 7th List Price: $49.95 Buy New: $39.75 You Save: $10.20 (20%) New (18) Used (9) from $39.75The Student Manual helps you experience group process techniques and gain maximum benefit from Corey's textbook. The manual includes many activities, ideas for supervised training groups, summary charts, (more)

Joining Together: Group Theory and Group Skills (10th Edition) List Price: $92.00 Buy New: $68.88 You Save: $23.12 (25%) New (27) Used (18) from $68.88Joining Together: Group Theory and Group Skills (10th Edition) (more)

Group Theory in the Bedroom, and Other Mathematical Diversions List Price: $25.00 Buy New: $16.08 You Save: $8.92 (36%) New (10) Used (2) from $12.50An Award-Winning Essayist Plies His Craft Brian Hayes is one of the most accomplished essayists active today?a claim supported not only by his prolific and continuing high-quality output but also by such (more)

Schaum's Outline of Group Theory List Price: $18.95 Buy Used: $4.29 You Save: $14.66 (77%) New (25) Used (18) Collectible (1) from $4.29Confusing Textbooks? Missed Lectures? Not Enough Time? Fortunately for you, there's Schaum's Outlines. More than 40 million students have trusted Schaum's to help them succeed in the classroom and on (more)

Group Theory: Application to the Physics of Condensed Matter List Price: $89.95 Buy New: $66.67 You Save: $23.28 (26%) New (20) Used (5) from $66.67Every process in physics is governed by selection rules that are the consequence of symmetry requirements. The beauty and strength of group theory resides in the transformation of many complex symmetry (more)

Group Theory and Quantum Mechanics List Price: $24.95 Buy New: $15.44 You Save: $9.51 (38%) New (12) Used (8) Collectible (1) from $12.96This graduate-level text develops aspects of group theory most relevant to physics and chemistry and illustrates their applications to quantum mechanics: abstract group theory, theory of group representations, (more)

Topological Methods in Group Theory (Graduate Texts in Mathematics) List Price: $59.95 Buy New: $45.13 You Save: $14.82 (25%) New (26) Used (7) from $45.13Topological Methods in Group Theory is about the interplay between algebraic topology and the theory of infinite discrete groups. The author has kept three kinds of readers in mind: graduate students who (more)

Symmetry: An Introduction to Group Theory and Its Applications List Price: $14.95 Buy New: $9.11 You Save: $5.84 (39%) New (17) Used (9) from $8.10This well-organized volume develops the elementary ideas of both group theory and representation theory in a progressive and thorough fashion. Designed to allow students to focus on any of the main fields (more)

Character Theory of Finite Groups (AMS Chelsea Publishing) Buy New: $45.00 New (6) Used (3) from $29.95Character theory is a powerful tool for understanding finite groups. In particular, the theory has been a key ingredient in the classification of finite simple groups. Characters are also of interest in (more)

• print this page
• pages linking here
• related pages