Fact-checked by Grok 2 weeks ago

Equivalence class

In mathematics, an equivalence class is a subset of a given set consisting of all elements that are equivalent to a particular element under an equivalence relation, which is a binary relation on the set that satisfies the properties of reflexivity, symmetry, and transitivity.^[1] For an equivalence relation \sim on a set X and an element x \in X, the equivalence class of x, denoted _\sim, is defined as _\sim = \{ y \in X \mid y \sim x \}.^[2] Equivalence classes possess key properties that make them fundamental in abstract algebra and set theory: two equivalence classes are either identical or disjoint, and the collection of all distinct equivalence classes forms a partition of the original set X, meaning every element of X belongs to exactly one class.^[1] This partitioning arises directly from the reflexive, symmetric, and transitive nature of the relation, ensuring no overlaps and complete coverage.^[2] A bijection exists between the set of all equivalence relations on X and the set of all pairwise disjoint partitions of X, highlighting their structural equivalence.^[2] Common examples include congruence modulo an integer n on the integers \mathbb{Z}, where _n = \{ m \in \mathbb{Z} \mid m \equiv k \pmod{n} \} for $0 \leq k < n, partitioning \mathbb{Z} into n classes based on remainders.^[1] Another is parity on \mathbb{Z}, dividing integers into even and odd classes.^[2] These classes underpin concepts like modular arithmetic and quotient sets, enabling constructions such as the integers modulo n, denoted \mathbb{Z}/n\mathbb{Z}.^[1]

Definition and Basic Concepts

Formal Definition

In mathematics, given a set X and an equivalence relation \sim on X, the equivalence class of an element x \in X, denoted $$, is defined as the subset = \{ y \in X \mid y \sim x \}, comprising all elements of X that are related to x under \sim.^[3] The equivalence classes of all elements in X form a partition of X: these subsets are pairwise disjoint, and their union equals X, ensuring every element belongs to exactly one such class.^[3] This concept was formalized in the late 19th century amid the development of set theory, with early contributions including Richard Dedekind's use of equivalence in algebraic number theory (1871).^[4]

Equivalence Relation

An equivalence relation is a fundamental concept in mathematics that generalizes the intuitive notions of equality and congruence between objects, allowing for the identification of elements that share certain properties while distinguishing others.^[5] This generalization enables the study of structures where "sameness" is defined relative to specific criteria, such as congruence modulo an integer, rather than strict identity.^[6] Typically denoted by the symbol \sim or \equiv, an equivalence relation on a set A is a binary relation \sim \subseteq A \times A that satisfies three key axioms: reflexivity, symmetry, and transitivity.^[1] These axioms mirror the properties of equality but apply to broader contexts.

Reflexivity: For every element a \in A, a \sim a. This ensures that every element is related to itself.^[1]
Symmetry: For all a, b \in A, if a \sim b, then b \sim a. This guarantees that the relation is bidirectional.^[1]
Transitivity: For all a, b, c \in A, if a \sim b and b \sim c, then a \sim c. This allows the relation to chain across multiple elements.^[1]

These properties collectively ensure that the relation behaves like an extended form of equality on the set.^[7]

Properties

Fundamental Properties

Equivalence classes possess several intrinsic properties that stem directly from the definition of an equivalence relation. For any set X equipped with an equivalence relation \sim, the equivalence class of an element x \in X, denoted = \{ y \in X \mid y \sim x \}, satisfies the property that every element belongs to its own class, ensuring x \in . This reflexivity guarantees that no equivalence class is empty.^[8] Furthermore, distinct equivalence classes are disjoint: if \neq, then \cap = \emptyset. This disjointness arises because if there exists some z \in \cap , then z \sim x and z \sim y, implying x \sim y by transitivity and symmetry, so =.^[1] A key characterizing feature is the equality of classes: = if and only if x \sim y. This equivalence means that two elements share the same class precisely when they are related under \sim, which directly ties the structure of the classes to the relation itself. Consequently, every element of X belongs to exactly one equivalence class, as the classes cover X without overlap.^[8] This exhaustiveness ensures a complete partitioning of the set into these classes.^[2] Regarding cardinality, equivalence classes may be finite or infinite, and distinct classes within the same partition can have different sizes depending on the relation and the set. No universal bound exists on class sizes, allowing for significant variation across the collection of classes.

Connection to Partitions

Equivalence relations on a set X and partitions of X are in one-to-one correspondence, meaning every equivalence relation induces a unique partition of X into its equivalence classes, and conversely, every partition of X determines a unique equivalence relation by relating elements within the same partition block.^[9]^[10] Formally, if \sim is an equivalence relation on a nonempty set X, then the set of equivalence classes X / \sim = \{ \mid x \in X \} forms a partition of X, where the equivalence classes are pairwise disjoint and their union equals X.^[9]^[11] To see this, the union of all equivalence classes covers X because reflexivity ensures every x \in X belongs to its own class . For disjointness, suppose two classes and $$ have nonempty intersection, so there exists c \in \cap ; then transitivity and symmetry imply =, establishing that distinct classes are disjoint.^[9]^[10] Conversely, given a partition \Pi = \{ P_i \mid i \in I \} of X, define x \sim y if x and y belong to the same P_i; this relation is reflexive, symmetric, and transitive, yielding an equivalence relation whose classes are precisely the blocks of \Pi.^[9]^[10]

Examples

Everyday Examples

Equivalence classes appear in everyday scenarios where objects or entities are grouped based on shared properties that satisfy reflexive, symmetric, and transitive relations. One common example is the parity of integers, where numbers are classified as even or odd. All even numbers—such as 2, 4, 6, and so on—form one equivalence class because they leave a remainder of 0 when divided by 2, while all odd numbers—such as 1, 3, 5—form another class with a remainder of 1. This grouping is intuitive in daily tasks like checking divisibility or balancing accounts, where the specific value within the class is less important than the shared parity property.^[12] Another relatable instance involves color perception for people with color blindness, where certain shades that differ to those with typical vision appear identical, creating equivalence classes of indistinguishable colors. For example, in red-green color blindness (deuteranopia or protanopia), hues like certain reds and greens blend together, forming a class that might confuse viewers when interpreting visual aids such as traffic lights, subway maps, or product labels. Designers account for these classes by selecting palettes where no two colors fall into the same equivalence group for affected individuals, ensuring clarity in navigation or data visualization.^[13] In postal systems, ZIP codes provide a practical equivalence relation by grouping addresses that share the same code for delivery efficiency. Each ZIP code defines an equivalence class encompassing all locations—from individual homes to businesses—within its geographic area, such as all addresses under 90210 in Beverly Hills, California. This partitioning simplifies mail routing, as items destined for the same class are handled equivalently regardless of exact street details, illustrating how equivalence classes streamline real-world logistics.^[14]

Mathematical Examples

One prominent example of equivalence classes arises in the study of congruence modulo n on the set of integers \mathbb{Z}, where n is a positive integer. The relation defined by a \sim b if n divides a - b (denoted a \equiv b \pmod{n}) is an equivalence relation, partitioning \mathbb{Z} into n distinct equivalence classes. Each class _n = \{ k \in \mathbb{Z} \mid k \equiv a \pmod{n} \} consists of all integers congruent to a modulo n, forming the residue system modulo n. For instance, with n=3, the classes are

{{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}}_3 = \{\ldots, -6, -3, 0, 3, 6, \ldots\}

{{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}}_3 = \{\ldots, -5, -2, 1, 4, 7, \ldots\}

, and

{{grok:render&&&type=render_inline_citation&&&citation_id=2&&&citation_type=wikipedia}}_3 = \{\ldots, -4, -1, 2, 5, 8, \ldots\}

.^[12]^[15] Another fundamental construction uses equivalence classes to define the rational numbers \mathbb{Q} from pairs of integers. Consider the set \mathbb{Z} \times (\mathbb{Z} \setminus \{0\}) of ordered pairs (a, b) with b \neq 0, equipped with the relation (a, b) \sim (c, d) if ad = bc. This relation is an equivalence relation, and each equivalence class [(a, b)] = \{ (c, d) \in \mathbb{Z} \times (\mathbb{Z} \setminus \{0\}) \mid ad = bc \} represents a rational number, intuitively a/b in lowest terms. For example, the class [(1, 2)] includes pairs like (2, 4), (3, 6), and (-1, -2), all denoting $1/2. The set of all such classes, with operations defined componentwise and verified to be well-defined, forms the field \mathbb{Q}.^[16]^[17] In graph theory, equivalence classes emerge from the connectivity relation on the vertices of an undirected graph G = (V, E). The relation u \sim v if there exists a path between u and v in G is an equivalence relation on V, with each equivalence class $$ comprising all vertices reachable from u, known as a connected component. For a graph with three components—a single vertex, a path of two edges, and an isolated edge—the classes are \{[v_1]\}, \{[v_2, v_3, v_4]\}, and \{[v_5, v_6]\}, respectively, partitioning V into disjoint subsets where intra-class connectivity holds but inter-class paths do not. These classes exhibit the disjointness property inherent to equivalence relations.^[18]^[19]

Representations

Graphical Representations

Equivalence classes, as disjoint subsets forming a partition of the underlying set, are commonly visualized using diagrams that emphasize their mutual exclusivity and complete coverage. For finite sets, a standard graphical method employs Venn-like diagrams consisting of disjoint circles or bounded regions, each enclosing the elements of a single equivalence class. This representation highlights the partition property by showing non-overlapping areas whose union is the entire set, aiding in intuitive understanding of how the relation groups elements without overlap. In illustrations for specific examples, such as congruence modulo n on the integers, partition bars or color-coded regions on a number line effectively depict the repeating structure of classes. For instance, the equivalence classes modulo 3 can be visualized on a number line with periodic groupings based on remainders 0, 1, and 2. However, graphical representations face significant limitations when dealing with infinite equivalence classes, as it is impossible to exhaustively draw or color unbounded sets in a finite diagram. In such cases, set-builder notation, such as = \{ x \mid x \sim a \}, serves as a complementary tool to denote the classes abstractly, preserving precision where visuals fall short.

Invariants

In mathematics, an invariant for an equivalence relation \sim on a set S is a function f: S \to W, where W is another set, such that f(a) = f(b) whenever a \sim b; that is, f takes the same value on every element of an equivalence class.^[20] This property ensures that f remains unchanged under the equivalence, providing a way to assign a single representative value to each class. Invariants are particularly useful for distinguishing between different equivalence classes without examining every element individually. A classic example arises in the equivalence relation of congruence modulo n on the integers \mathbb{Z}, where two integers a and b satisfy a \sim b if n divides a - b. The function f(a) = a \mod n, which returns the remainder when a is divided by n (in the range $0 to n-1), serves as an invariant, as all elements in the class $$ share the remainder k. Similarly, in linear algebra, similarity of square matrices over a field defines an equivalence relation, and the trace—the sum of the diagonal elements—is an invariant: if B = P^{-1}AP for an invertible matrix P, then \operatorname{trace}(A) = \operatorname{trace}(B).^[21] This follows from the cyclic property of the trace, \operatorname{trace}(XY) = \operatorname{trace}(YX), applied iteratively to the similarity transformation.^[21] Invariants play a key role in classifying objects up to equivalence by providing measurable properties that define class membership. In Euclidean geometry, congruence—defined as the existence of an isometry mapping one figure to another—forms an equivalence relation, and quantities like side lengths of triangles act as invariants: two triangles are congruent if and only if their corresponding side lengths match. These invariants enable efficient determination of equivalence without physical manipulation, as seen in criteria such as SSS (side-side-side), where equal side lengths guarantee congruence. Such applications extend to broader classification problems, where a complete set of invariants fully separates the classes.

Applications

Quotient Sets

In set theory, given a set X and an equivalence relation \sim on X, the quotient set, denoted X / \sim, is defined as the set of all equivalence classes of \sim, that is, X / \sim = \{ \mid x \in X \}, where $$ denotes the equivalence class of x under \sim.^[22] This construction partitions X into disjoint subsets, each corresponding to an element of X / \sim. The canonical projection map \pi: X \to X / \sim is the surjective function defined by \pi(x) = for all x \in X, which identifies each element of X with its equivalence class.^[23]^[24] This map establishes a bijection between X / \sim and the partition of X induced by \sim. The cardinality of the quotient set |X / \sim| equals the number of distinct equivalence classes, which is generally smaller than or equal to |X|, with equality holding if and only if \sim is the equality relation on X.^[22]^[25] If \sim is a congruence relation—meaning it is compatible with any algebraic operations on X—then these operations induce well-defined operations on X / \sim. For instance, an n-ary operation f: X^n \to X induces an operation on X / \sim by [x_1], \dots, [x_n] \mapsto [f(x_1, \dots, x_n)], preserving the structure of the original set.^[24] An example occurs with addition on the integers \mathbb{Z}, where the equivalence relation of congruence modulo n induces addition on the quotient \mathbb{Z}/n\mathbb{Z}, forming the cyclic group of order n.^[26]

Topological Quotient Spaces

In topology, equivalence classes extend the discrete notion of partitioning sets to continuous spaces, allowing the construction of quotient spaces that identify equivalent points while preserving topological structure. Given a topological space (X, \tau) and an equivalence relation \sim on X, the quotient space X / \sim consists of the set of equivalence classes endowed with the quotient topology. The quotient map \pi: X \to X / \sim, which sends each point to its equivalence class, induces this topology: a subset U \subseteq X / \sim is open if and only if \pi^{-1}(U) is open in X.^[27] This definition ensures that the quotient topology is the finest topology on X / \sim making \pi continuous, thereby capturing the "gluing" of equivalent points in a manner compatible with the original topology on X. For the quotient space to exhibit well-behaved properties, such as the quotient map being open or closed under certain conditions, open sets in X are often required to be saturated with respect to \sim. A set C \subseteq X is saturated if it is a union of equivalence classes, meaning that if C intersects an equivalence class, it contains the entire class; this condition aligns open sets in the quotient with unions of classes, facilitating continuity and other topological invariants.^[27] A classic example is the circle S^1, obtained as the quotient of the closed interval [0, 1] under the equivalence relation identifying the endpoints $0 \sim 1, with all other points forming singleton classes. The projection \pi: [0, 1] \to S^1 given by \pi(t) = e^{2\pi i t} equips the quotient with the standard topology on the circle, where open sets correspond to preimages that are open intervals or unions thereof in [0, 1].^[28]^[29] Another prominent example is the real projective plane \mathbb{RP}^2, formed as the quotient of the 2-sphere S^2 by identifying antipodal points via x \sim -x for x \in S^2. This identification yields a nonorientable surface, with the quotient topology ensuring that the projection \pi: S^2 \to \mathbb{RP}^2 is a covering map of degree 2, and open sets in \mathbb{RP}^2 arise as images of saturated open sets on the sphere.^[29]

Algebraic Applications

In abstract algebra, equivalence classes play a central role in the construction of quotient structures, particularly in the study of groups and rings. For groups, a normal subgroup N of a group G defines an equivalence relation on G where two elements g_1, g_2 \in G are equivalent if g_1^{-1}g_2 \in N. The equivalence classes under this relation are the left (or right, since N is normal) cosets of N in G, denoted gN for g \in G. These cosets form the quotient group G/N, where the group operation is induced by the operation in G: (g_1 N)(g_2 N) = (g_1 g_2) N. This structure preserves the algebraic properties of G modulo N, allowing the analysis of G through its "factor" group.^[30] Similarly, in ring theory, an ideal I of a ring R induces an equivalence relation where a \sim b if a - b \in I. The equivalence classes are the cosets a + I, and they form the quotient ring R/I with addition and multiplication defined componentwise: (a + I) + (b + I) = (a + b) + I and (a + I)(b + I) = (ab) + I. For R/I to be a well-defined ring, I must absorb multiplication from R, ensuring the operations are independent of coset representatives. This construction is fundamental for studying ring homomorphisms and modular arithmetic in algebraic contexts.^[31] The first isomorphism theorem for groups connects these equivalence classes to homomorphisms: if \phi: G \to H is a group homomorphism, the kernel \ker(\phi) = \{g \in G \mid \phi(g) = e_H\} is a normal subgroup of G, and the equivalence classes are the cosets g \ker(\phi). The theorem states that G / \ker(\phi) is isomorphic to the image \phi(G), providing a way to identify quotient groups with subgroups of the codomain via the induced map \overline{\phi}: G / \ker(\phi) \to \phi(G) given by \overline{\phi}(g \ker(\phi)) = \phi(g). This result generalizes to rings, linking kernels as ideals to quotient rings and images.^[32] These concepts emerged in the early 20th century as part of the development of modern abstract algebra, with Emmy Noether's work on ideals, modules, and chain conditions in the 1920s providing a unified framework for quotient constructions in associative structures.^[33]

References

[1]
5.1 Equivalence Relations
Definition and Examples ... If ∼ is an equivalence relation defined on the set A and a∈A, let [a]={x∈A:a∼x},. called the equivalence class corresponding to a.
[2]
[PDF] Math 127: Equivalence Relations
Let ∼ be an equivalence relation on X. The set [x]∼ as defined in the proof of Theorem 1 is called the equivalence class, or simply class of x under ∼.
[3]
[PDF] Equivalence Relations, Well-Definedness, Modular Arithmetic, and ...
Equivalence Classes. We shall slightly adapt our notation for relations in this document. Let ∼ be a relation on a set X. Formally, ∼ is a subset of X × X.
[4]
Equivalence: an attempt at a history of the idea | Synthese
Jan 19, 2018 · This paper proposes a reading of the history of equivalence in mathematics. The paper has two main parts. The first part focuses on a ...
[5]
Equivalence Relations - Mathematics
Equivalence relation can be viewed a generalization of equality. We only care whether two objects are "equivalent" (or are equal up to some "equivalence").
[6]
[PDF] Some notes on equivalence relations - Ernie Croot
Jan 23, 2012 · The notion of an 'equivalence relation' is one such construct, as it unifies the notion of the equality of numbers, congruent and similar ...
[7]
[PDF] Math 4310 Handout - Equivalence Relations - Cornell Mathematics
An equivalence relation is a binary relation where elements are related if (a, b) ∈ R. The quotient set A/∼ is the set of equivalence classes.
[8]
https://math.libretexts.org/Courses/SUNY_Schenectady_County_Community_College/Discrete_Structures/07%3A_Equivalence_Relations/7.03%3A_Equivalence_Classes
[9]
[PDF] Equivalence Relations, Order and Cardinality - John McCuan
Jan 14, 2020 · Consequently, there is no such thing as an empty equivalence class. In the case of cardinality Rcard, the equivalence class for a set A is ...
[10]
6.3: Equivalence Relations and Partitions - Mathematics LibreTexts
May 5, 2020 · The overall idea in this section is that given an equivalence relation on set A, the collection of equivalence classes forms a partition of set A.Definition: Equivalence Class · Equivalence Classes form a...
[11]
[PDF] 2.9. Set Decomposition: Partitions and Relations
Feb 23, 2024 · We will show that an equivalence relation on a set determines a partition and, conversely, a partition of a set determines an equivalence ...
[12]
8.3 Equivalence Relations
If A is a set and R is an equivalence relation on A, then the distinct equivalence classes of R form a partition of A; that is, the union of the equivalence ...
[13]
7.3: Equivalence Classes - Mathematics LibreTexts
Sep 29, 2021 · An equivalence relation on a set is a relation with a certain combination of properties (reflexive, symmetric, and transitive) that allow us ...PREVIEW ACTIVITY 7 . 3 . 1... · The Definition of an...
[14]
Designing for Color blindness - Martin Krzywinski
To people with color blindness, some colors appear the same. This equivalence can be used to identify colors that are distinct to those with normal as well as ...
[15]
2.2. Relations — Discrete Structures for Computing
We can represent the equivalence class of people with N6A 3K6 as their postal code using a representative of that group. Because of the symmetry and ...
[16]
[PDF] Congruence and Congruence Classes
You should think of an equivalence relation as a generalization of the notion of equality. Indeed, the usual notion of equality among the set of integers is an ...
[17]
[PDF] The Rational Numbers
According to the definition, a rational number is an equivalence class containing certain pairs of integers. What do some of the equivalence classes look like?Missing: authoritative source
[18]
[PDF] 7. The Rationals (10/19/10)
In this section, we build the rationals as equivalence classes of an equivalence relations on ordered pairs of integers; the equivalence relation we will use ...
[19]
[PDF] Lecture 2: Connected components 1 Equivalence relations
In the case of our relation ∼, the equivalence classes will give us the connected components of a graph. Proof of Proposition 1.1. Let's check all three ...Missing: authoritative source
[20]
[PDF] Connected Components - Stanford University
Theorem: Let G = (V, E) be a graph. Then the connectivity relation over V is an equivalence relation. Proof: Consider an arbitrary graph G = (V, E).Missing: authoritative source
[21]
Equivalence Classes (CS 2800, Spring 2017)
If R is an equivalence relation on A and x∈A, then the equivalence class of x, denoted [x]R, is the set of all elements of A that are related to x.Missing: authoritative | Show results with:authoritative
[22]
[PDF] Scissors Congruence - Penn Math
More generally, let ∼ be an equivalence relation on some set X. An invariant for ∼ is a function ι : X → Y such that if x ∼ x0, then ι(x) = ι(x0).<|control11|><|separator|>
[23]
Equivalence relations | Peter Cameron's Blog - WordPress.com
Mar 31, 2010 · An invariant is a function which can be calculated for each object in the set X and which takes the same values for equivalent objects. A set of ...
[24]
https://math.berkeley.edu/~wodzicki/H113.S18/H113.pdf
[25]
[PDF] Similarity Invariants Math 422
Some of important properties shared by similar matrices are the determinant, trace, rank, nullity, and eigenvalues. Proof. Suppose B = PL1AP.
[26]
[PDF] Equivalence Relations - Cornell: Computer Science
The set of all equivalence classes of ∼ on A, denoted A/∼, is called the quotient (or quotient set) of the relation. It is by definition a subset of the power ...
[27]
[PDF] equivalence relations, quotients, and
1 Equivalence relations. Definition 1. Let X be a set. An equivalence relation ∼ on X is a relationa which is: (i) reflexive, that is, x ∼ x for all x ∈ X.
[28]
[PDF] Introduction to Algebra - UC Berkeley Mathematics
Mar 7, 2019 · ∈ X. Exercise 41 Prove that, for any congruence relation, the product of the equiv- ... The n-ary operation induces on the quotient set X/∼ the ...
[29]
[PDF] Math 100A Week 3: Equivalence relations, Lagrange's theorem
Oct 18, 2024 · The quotient set. Suppose S is a set with an equivalence relation ∼. Quotient set. Define a new set S whose elements are the equivalence classes ...
[30]
[PDF] Math 222A W03 D. Congruence relations 1 . The concept Let's start ...
(1) In Z, a congruence relation is the same as congruence mod n for some n. The case n = 0 is allowed, giving the equality relation. (2) In a group, a ...
[31]
[PDF] Section 22. The Quotient Topology
Jan 5, 2015 · In the quotient topology on X∗ induced by p, the space S∗ under this topology is the quotient space of X. Note. Recall that we have a partition ...
[32]
3.01 Quotient topology
The quotient space should be the circle, where we have identified the endpoints of the interval. Indeed, we can map X to the unit circle S1⊂C via the map q ...
[33]
None
Below is a merged summary of the quotient topology from Hatcher’s *Algebraic Topology* (AT.pdf), consolidating all the information from the provided segments into a comprehensive response. To maximize detail and clarity, I will use a structured format with tables where appropriate, followed by a narrative summary that integrates key points, examples, and citations. Given the constraint of no thinking tokens, I’ll focus on directly synthesizing the content without additional analysis or inference beyond what’s provided.
[34]
10.1: Factor Groups and Normal Subgroups - Mathematics LibreTexts
Sep 7, 2021 · That is, a normal subgroup of a group G is one in which the right and left cosets are precisely the same. Example ...
[35]
8.3: Ideals and Quotient Rings - Mathematics LibreTexts
Apr 16, 2022 · Definition: Ideal. Let R be a ring and let I be a subset of R . I is a left ideal (respectively, right ideal) of R if I is a subring and r ...Definition: Ideal · Theorem 8 . 3 . 4 : First... · Example 8 . 3 . 1 : Principal...
[36]
9.1: The First Isomorphism Theorem - Mathematics LibreTexts
Oct 23, 2021 · A very powerful theorem, called the First Isomorphism Theorem, lets us in many cases identify factor groups (up to isomorphism) in a very slick way.
[37]
Emmy Noether (1882 - 1935) - Biography - MacTutor
Emmy Noether is best known for her contributions to abstract algebra, in particular, her study of chain conditions on ideals of rings. Thumbnail of Emmy Noether