Equivalence class

Last updated
Congruence is an example of an equivalence relation. The leftmost two triangles are congruent, while the third and fourth triangles are not congruent to any other triangle shown here. Thus, the first two triangles are in the same equivalence class, while the third and fourth triangles are each in their own equivalence class. Congruent non-congruent triangles.svg
Congruence is an example of an equivalence relation. The leftmost two triangles are congruent, while the third and fourth triangles are not congruent to any other triangle shown here. Thus, the first two triangles are in the same equivalence class, while the third and fourth triangles are each in their own equivalence class.

In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation) defined on them, then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a and b belong to the same equivalence class if, and only if, they are equivalent.

Contents

Formally, given a set S and an equivalence relation ~ on S, the equivalence class of an element a in S, denoted by , [1] [2] is the set [3]

of elements which are equivalent to a. It may be proven, from the defining properties of equivalence relations, that the equivalence classes form a partition of S. This partition—the set of equivalence classes—is sometimes called the quotient set or the quotient space of S by ~, and is denoted by S / ~.

When the set S has some structure (such as a group operation or a topology) and the equivalence relation ~ is compatible with this structure, the quotient set often inherits a similar structure from its parent set. Examples include quotient spaces in linear algebra, quotient spaces in topology, quotient groups, homogeneous spaces, quotient rings, quotient monoids, and quotient categories.

Examples

Notation and formal definition

An equivalence relation on a set X is a binary relation ~ on X satisfying the three properties: [7] [8]

The equivalence class of an element a is denoted [a] or [a]~, [1] and is defined as the set of elements that are related to a by ~. [3] The word "class" in the term "equivalence class" does not refer to classes as defined in set theory, however equivalence classes do often turn out to be proper classes.

The set of all equivalence classes in X with respect to an equivalence relation R is denoted as X/R, and is called X modulo R (or the quotient set of X by R). [9] The surjective map from X onto X/R, which maps each element to its equivalence class, is called the canonical surjection, or the canonical projection map.

When an element is chosen (often implicitly) in each equivalence class, this defines an injective map called a section . If this section is denoted by s, one has [s(c)] = c for every equivalence class c. The element s(c) is called a representative of c. Any element of a class may be chosen as a representative of the class, by choosing the section appropriately.

Sometimes, there is a section that is more "natural" than the other ones. In this case, the representatives are called canonical representatives. For example, in modular arithmetic, consider the equivalence relation on the integers defined as follows: a ~ b if ab is a multiple of a given positive integern (called the modulus). Each class contains a unique non-negative integer smaller than n, and these integers are the canonical representatives. The class and its representative are more or less identified, as is witnessed by the fact that the notationa mod n may denote either the class, or its canonical representative (which is the remainder of the division ofa by n).

Properties

Every element x of X is a member of the equivalence class [x]. Every two equivalence classes [x] and [y] are either equal or disjoint. Therefore, the set of all equivalence classes of X forms a partition of X: every element of X belongs to one and only one equivalence class. [10] Conversely, every partition of X comes from an equivalence relation in this way, according to which x ~ y if and only if x and y belong to the same set of the partition. [11]

It follows from the properties of an equivalence relation that

x ~ y if and only if [x] = [y].

In other words, if ~ is an equivalence relation on a set X, and x and y are two elements of X, then these statements are equivalent:

Graphical representation

Graph of an example equivalence with 7 classes Equivalentie.svg
Graph of an example equivalence with 7 classes

An undirected graph may be associated to any symmetric relation on a set X, where the vertices are the elements of X, and two vertices s and t are joined if and only if s ~ t. Among these graphs are the graphs of equivalence relations; they are characterized as the graphs such that the connected components are cliques. [5]

Invariants

If ~ is an equivalence relation on X, and P(x) is a property of elements of X such that whenever x ~ y, P(x) is true if P(y) is true, then the property P is said to be an invariant of ~, or well-defined under the relation ~.

A frequent particular case occurs when f is a function from X to another set Y; if f(x1) = f(x2) whenever x1 ~ x2, then f is said to be class invariant under~, or simply invariant under~. This occurs, e.g. in the character theory of finite groups. Some authors use "compatible with ~" or just "respects ~" instead of "invariant under ~".

Any function f : XY itself defines an equivalence relation on X according to which x1 ~ x2 if and only if f(x1) = f(x2). The equivalence class of x is the set of all elements in X which get mapped to f(x), i.e. the class [x] is the inverse image of f(x). This equivalence relation is known as the kernel of f.

More generally, a function may map equivalent arguments (under an equivalence relation ~X on X) to equivalent values (under an equivalence relation ~Y on Y). Such a function is a morphism of sets equipped with an equivalence relation.

Quotient space in topology

In topology, a quotient space is a topological space formed on the set of equivalence classes of an equivalence relation on a topological space, using the original space's topology to create the topology on the set of equivalence classes.

In abstract algebra, congruence relations on the underlying set of an algebra allow the algebra to induce an algebra on the equivalence classes of the relation, called a quotient algebra. In linear algebra, a quotient space is a vector space formed by taking a quotient group, where the quotient homomorphism is a linear map. By extension, in abstract algebra, the term quotient space may be used for quotient modules, quotient rings, quotient groups, or any quotient algebra. However, the use of the term for the more general cases can as often be by analogy with the orbits of a group action.

The orbits of a group action on a set may be called the quotient space of the action on the set, particularly when the orbits of the group action are the right cosets of a subgroup of a group, which arise from the action of the subgroup on the group by left translations, or respectively the left cosets as orbits under right translation.

A normal subgroup of a topological group, acting on the group by translation action, is a quotient space in the senses of topology, abstract algebra, and group actions simultaneously.

Although the term can be used for any equivalence relation's set of equivalence classes, possibly with further structure, the intent of using the term is generally to compare that type of equivalence relation on a set X, either to an equivalence relation that induces some structure on the set of equivalence classes from a structure of the same kind on X, or to the orbits of a group action. Both the sense of a structure preserved by an equivalence relation, and the study of invariants under group actions, lead to the definition of invariants of equivalence relations given above.

See also

Notes

  1. 1 2 "Comprehensive List of Algebra Symbols". Math Vault. 2020-03-25. Retrieved 2020-08-30.
  2. "7.3: Equivalence Classes". Mathematics LibreTexts. 2017-09-20. Retrieved 2020-08-30.
  3. 1 2 Weisstein, Eric W. "Equivalence Class". mathworld.wolfram.com. Retrieved 2020-08-30.
  4. Avelsgaard 1989 , p. 127
  5. 1 2 Devlin 2004 , p. 123
  6. Maddox 2002 , pp. 77–78
  7. Devlin 2004 , p. 122
  8. Weisstein, Eric W. "Equivalence Relation". mathworld.wolfram.com. Retrieved 2020-08-30.
  9. Wolf 1998 , p. 178
  10. Maddox 2002 , p. 74, Thm. 2.5.15
  11. Avelsgaard 1989 , p. 132, Thm. 3.16

Related Research Articles

Equivalence relation Mathematical concept for comparing objects

In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The relation "is equal to" is the canonical example of an equivalence relation.

Quotient group

A quotient group or factor group is a mathematical group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure. For example, the cyclic group of addition modulo n can be obtained from the group of integers under addition by identifying elements that differ by a multiple of n and defining a group structure that operates on each such class as a single entity. It is part of the mathematical field known as group theory.

Group action Operation of the elements of a group as transformations or automorphisms (mathematics)

In mathematics, a group action on a space is a group homomorphism of a given group into the group of transformations of the space. Similarly, a group action on a mathematical structure is a group homomorphism of a group into the automorphism group of the structure. It is said that the group acts on the space or structure. If a group acts on a structure, it will usually also act on objects built from that structure. For example, the group of Euclidean isometries acts on Euclidean space and also on the figures drawn in it. In particular, it acts on the set of all triangles. Similarly, the group of symmetries of a polyhedron acts on the vertices, the edges, and the faces of the polyhedron.

In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special cases of a preorder: an antisymmetric preorder is a partial order, and a symmetric preorder is an equivalence relation.

Semigroup

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation.

Topological group Group that is a topological space with continuous group action

In mathematics, a topological group is a group G together with a topology on G such that both the group's binary operation and the function mapping group elements to their respective inverses are continuous functions with respect to the topology. A topological group is a mathematical object with both an algebraic structure and a topological structure. Thus, one may perform algebraic operations, because of the group structure, and one may talk about continuous functions, because of the topology.

In algebra, the kernel of a homomorphism is generally the inverse image of 0. An important special case is the kernel of a linear map. The kernel of a matrix, also called the null space, is the kernel of the linear map defined by the matrix.

In abstract algebra, a congruence relation is an equivalence relation on an algebraic structure that is compatible with the structure in the sense that algebraic operations done with equivalent elements will yield equivalent elements. Every congruence relation has a corresponding quotient structure, whose elements are the equivalence classes for the relation.

Ring (mathematics) Algebraic structure with addition and multiplication

In mathematics, rings are algebraic structures that generalize fields: multiplication need not be commutative and multiplicative inverses need not exist. In other words, a ring is a set equipped with two binary operations satisfying properties analogous to those of addition and multiplication of integers. Ring elements may be numbers such as integers or complex numbers, but they may also be non-numerical objects such as polynomials, square matrices, functions, and power series.

Coset Concept in mathematical group theory

In mathematics, specifically group theory, a subgroup H of a group G may be used to decompose the underlying set of G into disjoint equal-size subsets called cosets. There are left cosets and right cosets. Cosets have the same number of elements (cardinality) as does H. Furthermore, H itself is both a left coset and a right coset. The number of left cosets of H in G is equal to the number of right cosets of H in G. This common value is called the index of H in G and is usually denoted by [G : H].

Quotient ring

In ring theory, a branch of abstract algebra, a quotient ring, also known as factor ring, difference ring or residue class ring, is a construction quite similar to the quotient groups of group theory and the quotient spaces of linear algebra. It is a specific example of a quotient, as viewed from the general setting of universal algebra. One starts with a ring R and a two-sided ideal I in R, and constructs a new ring, the quotient ring R / I, whose elements are the cosets of I in R subject to special + and operations.

Quotient space (topology)

In topology and related areas of mathematics, the quotient space of a topological space under a given equivalence relation is a new topological space constructed by endowing the quotient set of the original topological space with the quotient topology, that is, with the finest topology that makes continuous the canonical projection map. In other words, a subset of a quotient space is open if and only if its preimage under the canonical projection map is open in the original topological space.

In mathematics, a quotient algebra is the result of partitioning the elements of an algebraic structure using a congruence relation. Quotient algebras are also called factor algebras. Here, the congruence relation must be an equivalence relation that is additionally compatible with all the operations of the algebra, in the formal sense described below. Its equivalence classes partition the elements of the given algebraic structure. The quotient algebra has these classes as its elements, and the compatibility conditions are used to give the classes an algebraic structure.

In set theory, the kernel of a function f may be taken to be either

Partition of a set Mathematical ways to group elements of a set

In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset.

In mathematics, particularly in combinatorics, given a family of sets, here called a collection C, a transversal is a set containing exactly one element from each member of the collection. When the sets of the collection are mutually disjoint, each element of the transversal corresponds to exactly one member of C. If the original sets are not disjoint, there are two possibilities for the definition of a transversal:

In linear algebra, the quotient of a vector space V by a subspace N is a vector space obtained by "collapsing" N to zero. The space obtained is called a quotient space and is denoted V/N.

In mathematics, abuse of notation occurs when an author uses a mathematical notation in a way that is not entirely formally correct, but which might help simplify the exposition or suggest the correct intuition. However, since the concept of formal/syntactical correctness depends on both time and context, certain notations in mathematics that are flagged as abuse in one context could be formally correct in one or more other contexts. Time-dependent abuses of notation may occur when novel notations are introduced to a theory some time before the theory is first formalized; these may be formally corrected by solidifying and/or otherwise improving the theory. Abuse of notation should be contrasted with misuse of notation, which does not have the presentational benefits of the former and should be avoided.

Rational number Quotient of two integers

In mathematics, a rational number is a number such as −3/7 that can be expressed as the quotient or fraction p/q of two integers, a numerator p and a non-zero denominator q. Every integer is a rational number: for example, 5 = 5/1. The set of all rational numbers, often referred to as "the rationals", the field of rationals or the field of rational numbers is usually denoted by a boldface Q ; it was thus denoted in 1895 by Giuseppe Peano after quoziente, Italian for "quotient".

Real projective line

In geometry, a real projective line is an extension of the usual concept of line that has been historically introduced to solve a problem set by visual perspective: two parallel lines do not intersect but seem to intersect "at infinity". For solving this problem, points at infinity have been introduced, in such a way that in a real projective plane, two distinct projective lines meet in exactly one point. The set of these points at infinity, the "horizon" of the visual perspective in the plane, is a real projective line. It is the set of directions emanating from an observer situated at any point, with opposite directions identified.

References

Further reading