1 Equivalence relations
1.1 Definition
An equivalence relation on a set \(S\) is a relation \(\sim\) that is reflexive, symmetric, and transitive. When such a relation is fixed, it defines a notion of “sameness” among elements of \(S\): elements related by \(\sim\) are treated as indistinguishable under the intended perspective.
1.2 Properties
1.2.1 Reflexivity
A relation \(\sim\) is reflexive if every element is related to itself: for all \(x \in S\), \(x \sim x\). Reflexivity guarantees that each element belongs to the class determined by its own behavior.
1.2.2 Symmetry
A relation \(\sim\) is symmetric if the relationship goes both ways: for all \(x,y \in S\), if \(x \sim y\) then \(y \sim x\). Symmetry ensures that equivalence is not directional.
1.2.3 Transitivity
A relation \(\sim\) is transitive if it composes consistently: for all \(x,y,z \in S\), if \(x \sim y\) and \(y \sim z\) then \(x \sim z\). Transitivity lets “equivalent to the same thing” propagate across chains of identifications.
1.3 Examples of equivalence relations
Common examples include:
- Equality itself on any set: \(x \sim y\) iff \(x=y\).
- Congruence modulo \(n\) on integers: \(a \sim b\) iff \(n\mid(a-b)\).
- Equality of rational numbers represented by fractions: \(\frac{a}{b} \sim \frac{c}{d}\) iff \(ad=bc\) (on an appropriate domain).
- Indistinguishability of strings under a specified rewriting rule sequence, when the rule system is chosen to yield an equivalence relation.
2 Equivalence classes
2.1 Definition of an equivalence class
Given an equivalence relation \(\sim\) on \(S\) and an element \(x \in S\), the equivalence class of \(x\) is \[ [x]=\{y\in S : y\sim x\}. \] The class collects exactly those elements that are related to \(x\) and therefore considered equivalent under \(\sim\).
2.2 Class membership
An element \(y\) is a member of \([x]\) precisely when \(y\sim x\). This membership criterion is often used to translate between relational statements and set-theoretic statements about classes.
2.3 Partition induced by an equivalence relation
The set of all equivalence classes determined by \(\sim\) partitions \(S\). That is, each element lies in exactly one equivalence class, and classes form the “blocks” of the partition.
2.3.1 Disjointness of classes
If two equivalence classes share an element, then they are identical. Concretely, if \([x]\cap [y]\neq\varnothing\), then \([x]=[y]\). Hence distinct classes cannot overlap.
2.3.2 Covering the underlying set
Every element \(x\in S\) belongs to its own class \([x]\). Thus the union of all equivalence classes is the entire set \(S\).
3 Quotient set
3.1 Definition of the quotient set
The quotient set associated with \(\sim\) is the collection of equivalence classes: \[ S/{\sim}=\{[x] : x\in S\}. \] This construction “forgets” the specific representatives inside a class and keeps only the class itself.
3.2 Notation and terminology
The quotient set is commonly written as \(S/\!\sim\) or \(S/{\sim}\). Elements of the quotient are equivalence classes, often denoted by \([x]\), while the individual \(x\) remain members of the original set.
3.3 Relationship to equivalence classes
By definition, the quotient set is precisely the set of equivalence classes. Consequently, all information about \(\sim\) that is expressible in terms of class membership is captured at the quotient level.
4 Construction of the quotient
4.1 Forming the quotient from a set and relation
To form a quotient set, one starts with:
- a set \(S\),
- an equivalence relation \(\sim\) on \(S\),
and then collects all equivalence classes of elements of \(S\). The resulting quotient set is well-defined because the equivalence relation determines a partition of \(S\).
4.2 Canonical projection map
4.2.1 Definition of the projection
There is a natural function, the canonical projection (or quotient map), \[ \pi:S\to S/{\sim},\qquad \pi(x)=[x]. \] It sends each element to its equivalence class.
4.2.2 Surjectivity of the projection
The projection map is surjective because every equivalence class \([x]\) is hit by the element \(x\). Thus, for every element of the quotient set, there exists a representative in \(S\) mapping to it.
4.3 Well-definedness considerations
Many quotient-based constructions require checking that a definition does not depend on the chosen representative. For instance, if a function on classes is defined by using representatives, one must verify that equivalent representatives produce the same output. This requirement is typically phrased as “well-definedness”: the value depends only on the equivalence class, not on the particular element used to describe it.
5 Examples of quotient constructions
5.1 Integers modulo n
Let \(S=\mathbb{Z}\) and define \(a\sim b\) iff \(a\equiv b\pmod n\). The quotient \(\mathbb{Z}/n\mathbb{Z}\) consists of classes \([a]\), which can be represented by residues \(0,1,\dots,n-1\). Two integers share a class exactly when they differ by a multiple of \(n\).
5.2 Rational numbers as quotient structures
One way to view rationals is to start with integer pairs \(S=\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})\) and impose the relation \[ (a,b)\sim(c,d)\quad\text{iff}\quad ad=bc. \] The quotient identifies different fractional representations of the same rational number. Each equivalence class corresponds to a single rational value.
5.3 String or symbol identifications
Given a set of symbols or strings and a chosen equivalence criterion—such as “having the same result after applying a set of rewrite rules until no rule applies,” when that criterion is actually an equivalence relation—one obtains a quotient set of normalized forms or equivalence blocks. Elements that are indistinguishable under the chosen rule system fall into the same class.
6 Properties of quotient sets
6.1 Cardinality of quotient sets
The size of \(S/{\sim}\) depends on how many distinct equivalence classes occur. If \(S\) is finite, one can compute the quotient cardinality by counting the blocks in the partition. More generally, the quotient cardinality reflects how strongly the relation identifies elements: a finer relation yields more, smaller classes, while a coarser relation yields fewer, larger classes.
6.2 Refinement and coarsening of partitions
Given two equivalence relations \(\sim_1\) and \(\sim_2\) on the same set, one can compare their induced partitions. If \(\sim_1\) identifies at least as many elements as \(\sim_2\), then \(\sim_1\) is considered coarser (classes are larger) and \(\sim_2\) is finer (classes are smaller). This yields the corresponding monotonic behavior for the quotient sizes.
6.3 Universal properties
6.3.1 Factorization through quotient maps
A quotient set often satisfies a factorization property: maps from \(S\) that are constant on equivalence classes correspond uniquely to maps from \(S/{\sim}\). More precisely, if \(f:S\to T\) satisfies \(x\sim y\Rightarrow f(x)=f(y)\), then there exists a unique \( \overline{f}:S/{\sim}\to T\) such that \(f=\overline{f}\circ \pi\). This captures the idea that the quotient is the most economical way to enforce the identifications prescribed by \(\sim\).
6.3.2 Compatibility with functions
Functional compatibility with the quotient relies on the same constraint: the rule used to define an output must respect the equivalence relation. When it does, the function descends to the quotient, meaning it can be described entirely in terms of equivalence classes rather than individual representatives.
7 Quotients in algebra and discrete mathematics
7.1 Congruence relations
In algebraic settings, congruence relations are equivalence relations that respect the operations of the structure. They allow the quotient to inherit an algebraic structure (e.g., addition or multiplication on classes) in a way that remains consistent with representatives.
7.2 Quotient structures in groups and rings
For groups, quotienting by a normal subgroup produces a quotient group: the equivalence relation is based on cosets, and the quotient operation is defined by selecting representatives and verifying that the result is independent of choices. For rings, quotienting by an ideal similarly yields a ring structure on equivalence classes.
7.3 Automata and state minimization
In theoretical computer science, an automaton can be viewed as having states that may be indistinguishable with respect to accepted language behavior. When a relation between states captures exactly this behavioral equivalence, it can be used to form a quotient automaton with fewer states. The resulting minimized automaton preserves the same observable behavior while collapsing redundant distinctions.
8 Common applications
8.1 Simplifying combinatorial objects
Quotients streamline combinatorial problems by merging configurations that are equivalent under a chosen rule. This can reduce complexity by replacing many similar objects with a single representative class, focusing attention on invariants that survive the identification.
8.2 Identifying equivalent states or configurations
In models of computation, optimization, and reasoning about transitions, two configurations may differ only in irrelevant details. Equivalence relations formalize this irrelevance so that the quotient captures the “essential” state. The outcome is a smaller state space that often leads to clearer analysis.
8.3 Classifying objects up to isomorphism
In many areas of mathematics, objects are considered the same up to structural renaming. While isomorphism is not merely an arbitrary relation—it is an equivalence relation—taking the quotient by isomorphism groups objects into equivalence classes representing each isomorphism type. This supports classification by reducing the problem to enumerating distinct structures rather than listing all presentations.