Fact-checked by Grok 2 weeks ago

Equivalence relation

In mathematics, an equivalence relation is a binary relation on a set that is reflexive, symmetric, and transitive, generalizing the notion of equality to partition the set into disjoint subsets known as equivalence classes.^[1]^[2] The reflexive property requires that every element is related to itself; the symmetric property ensures that if one element is related to another, the relation holds in both directions; and the transitive property means that if one element is related to a second and the second to a third, then the first is related to the third.^[1]^[3] These properties together allow the relation to behave like an intuitive form of "sameness" within the set, often denoted by symbols such as \sim or \equiv.^[2] Given an equivalence relation \sim on a set X, the equivalence class of an element a \in X is the subset = \{ x \in X \mid x \sim a \}, which contains all elements equivalent to a.^[4] These classes form a partition of X, meaning they are pairwise disjoint (any two classes are either equal or have empty intersection) and their union covers the entire set.^[2]^[3] Conversely, any partition of a set induces an equivalence relation by defining elements to be equivalent if they belong to the same part.^[3] Common examples include the equality relation on any set, where elements are equivalent only to themselves; congruence modulo n on the integers, partitioning \mathbb{Z} into n classes represented by residues $0, 1, \dots, n-1; and the relation of having the same length on vectors in \mathbb{R}^2, yielding concentric circles centered at the origin.^[4]^[2] Equivalence relations originated conceptually in ancient Greek geometry with Euclid's ideas of proportionality around 300 BCE but were formalized in the 19th century by mathematicians like Dedekind through work on congruence classes, with the modern terminology "equivalence relation" emerging in the early 20th century via Hasse and Birkhoff.^[5] They are fundamental in fields such as abstract algebra, where they underpin quotient structures, and set theory, enabling the construction of new mathematical objects from existing ones.^[2]

Fundamentals

Definition

In mathematics, an equivalence relation on a set X is a binary relation R \subseteq X \times X that satisfies three axioms: reflexivity, symmetry, and transitivity.^[2]^[6] Reflexivity requires that for every element x \in X, xRx, ensuring that each element is related to itself; this property is necessary because it establishes self-consistency, mirroring the fundamental truth that any object is identical to itself under equality, without which the relation could exclude elements from being comparable even to themselves.^[2]^[6] Symmetry stipulates that if xRy for x, y \in X, then yRx; this bidirectional implication is essential as it guarantees mutual relatedness, reflecting equality's reversibility (if x = y, then y = x) and preventing one-sided connections that would undermine balanced equivalence.^[2]^[6] Transitivity demands that if xRy and yRz for x, y, z \in X, then xRz; this chaining effect is crucial for logical closure, akin to equality's property (if x = y and y = z, then x = z), allowing relations to propagate consistently across elements without gaps.^[2]^[6] These axioms collectively generalize the concept of equality by defining when elements of a set are indistinguishable under the relation, thereby partitioning the set into subsets of equivalent elements.^[2]^[6]

Properties

An equivalence relation on a set S is characterized by three fundamental axiomatic properties: reflexivity, symmetry, and transitivity.^[7] These properties collectively ensure that the relation behaves analogously to equality within the set, enabling consistent groupings of elements.^[8] Reflexivity requires that every element in the set is related to itself, formally expressed as \forall x \in S, x \sim x.^[9] This property guarantees self-consistency, preventing scenarios where an element stands isolated from itself in the relation.^[6] Without reflexivity, the relation cannot serve as a basis for partitioning, as elements would lack a foundational relation point.^[7] Symmetry ensures bidirectionality, meaning that if one element is related to another, the relation holds in reverse: \forall x, y \in S, (x \sim y \implies y \sim x).^[9] This property enforces mutuality, akin to the undirected nature of equality, and its absence would render the relation asymmetric, akin to a directed graph where connections are one-way.^[6] Symmetry, combined with the other properties, is essential for maintaining relational balance across the set.^[8] Transitivity provides chain-like consistency, stipulating that if x relates to y and y to z, then x relates to z: \forall x, y, z \in S, (x \sim y \land y \sim z \implies x \sim z).^[9] This ensures that relations propagate reliably, preventing fragmented connections that could undermine grouping.^[6] A lack of transitivity results in incomplete chains, where indirect relations fail to hold, disrupting the overall coherence.^[7] The interconnections among these properties are such that all three must hold simultaneously for the relation to qualify as an equivalence; the definition itself posits that reflexivity, symmetry, and transitivity together define an equivalence relation.^[8] Violating any one property invalidates the entire structure: for instance, non-transitivity breaks chain consistency even if reflexivity and symmetry are present, while non-reflexivity undermines self-relation regardless of the others.^[6] Proofs verifying an equivalence relation typically demonstrate each property separately using direct implication arguments, confirming their joint satisfaction.^[7] As consequences, these properties render the relation compatible with set-theoretic operations, such as unions and intersections of related elements, ultimately leading to a division of the set into disjoint subsets where intra-subset relations hold fully and inter-subset relations do not.^[9] This compatibility underpins the relation's role in structuring sets hierarchically without overlaps or gaps.^[8]

Notation

Equivalence relations are typically denoted using infix notation to express that two elements are related, such as x \sim y, where the tilde symbol \sim indicates equivalence between x and y. This notation treats the relation as a binary operator, similar to equality, and is widely used in set theory and discrete mathematics texts. Alternatively, the triple bar \equiv or the approximation symbol \approx may be employed in specific contexts, though \sim remains the most common for general equivalence./07:_Relations/7.03:_Equivalence_Relations)^[10] In more formal or relational settings, equivalence relations are represented in prefix form as R(x, y), where R is the name of the relation, emphasizing its function-like structure on elements from a set. The relation itself is often defined as a subset of the Cartesian product of the set with itself using set-builder notation:

R = \{ (x, y) \in X \times X \mid x \, R \, y \},

where X is the underlying set. This representation underscores the binary relation's membership in X \times X.^[11] The tilde \sim originates from its historical use in geometry to denote similarity between figures, such as similar triangles, where it symbolized proportional equivalence; this convention evolved to encompass broader equivalence relations in modern mathematics. In algebraic contexts, notations like a \sim b or a \equiv b \pmod{n} are standard for congruences, which are equivalence relations. Conversely, in logic, equivalence is frequently denoted by \equiv for material equivalence or \leftrightarrow for biconditional statements.^[12]^[13]^[14]

Examples and Illustrations

Equivalence Relations

An equivalence relation on a set is a binary relation that is reflexive, symmetric, and transitive.^[15] A fundamental example is the equality relation on any set A, defined by x \sim y if and only if x = y for all x, y \in A. This relation is reflexive because every element equals itself (x = x). It is symmetric since if x = y, then y = x. It is transitive because if x = y and y = z, then x = z. Thus, the equality relation partitions A into singleton sets.^[6] In number theory, congruence modulo n (where n is a positive integer) defines an equivalence relation on the integers \mathbb{Z}, denoted x \equiv y \pmod{n} if n divides x - y. To verify the properties: reflexivity holds because n divides x - x = 0 for any x \in \mathbb{Z}. Symmetry follows since if n divides x - y, then n divides y - x = -(x - y). For transitivity, if x \equiv y \pmod{n} and y \equiv z \pmod{n}, then x - y = kn and y - z = mn for integers k, m, so x - z = (k + m)n, which is divisible by n. This relation groups integers into n equivalence classes, each corresponding to remainders $0, 1, \dots, n-1 when divided by n.^[15] In geometry, congruence of triangles provides another example, where two triangles are related if they have the same size and shape, often verified by criteria like side-angle-side (SAS). This relation on the set of all triangles is reflexive, as any triangle is congruent to itself via the identity mapping. It is symmetric because if triangle ABC is congruent to DEF, then DEF is congruent to ABC by reversing the correspondence. Transitivity holds: if ABC \cong DEF and DEF \cong GHI, then ABC \cong GHI by composing the congruences, preserving side lengths and angles. The side-angle-side criterion states that two triangles are congruent if two sides and the included angle of one equal those of the other.^[16] Consider the relation on the set of all people where two people are related if they share the same birthday (ignoring the year). This is reflexive, as every person has the same birthday as themselves. It is symmetric: if person P shares a birthday with Q, then Q shares it with P. It is transitive because if P and Q share a birthday, and Q and R share one, then P, Q, and R all share the same birthday. The equivalence classes are the sets of people born on each specific date (e.g., January 1).^[17]

Non-Equivalence Relations

A common example of a relation that fails to be an equivalence relation is the "greater than" relation on the set of real numbers, defined by x > y. This relation is irreflexive, as no real number satisfies x > x for any x, violating reflexivity; for instance, $3 \not> 3.^[18] It is also asymmetric, since if x > y, then it cannot be that y > x, but asymmetry is not a requirement for equivalence relations—instead, the lack of reflexivity and symmetry already disqualifies it. It is transitive: if x > y and y > z, then x > z, as illustrated by $1 > 0 and $0 > -1 implying $1 > -1.^[18] Another example is the "divides" relation on the set of positive integers, where x divides y (denoted x \mid y) if there exists a positive integer k such that y = kx. This relation is reflexive, since x \mid x for every positive integer x (with k=1), and transitive, as if x \mid y and y \mid z, then x \mid z (composing the multiples).^[19] However, it fails symmetry: for example, $2 \mid 4 (since $4 = 2 \cdot 2), but $4 \nmid 2 (no integer k satisfies $2 = k \cdot 4).^[19] Thus, the absence of symmetry prevents it from being an equivalence relation. A relation that is reflexive and symmetric but not transitive is the "at most distance 1" relation on the real numbers, defined by x \sim y if |x - y| \leq 1. Reflexivity holds because |x - x| = 0 \leq 1 for all real x, and symmetry follows since |x - y| = |y - x|.^[20] Transitivity fails, however: consider $0 \sim 1 (as |0 - 1| = 1 \leq 1) and $1 \sim 2 (as |1 - 2| = 1 \leq 1), but |0 - 2| = 2 > 1, so $0 \not\sim 2.^[20] This illustrates a partial failure where two properties hold, but the lack of transitivity disqualifies equivalence.

Equivalence Classes

Given an equivalence relation R on a set X, the relation partitions X into subsets known as equivalence classes.^[21] The equivalence class of an element x \in X, denoted $$, is the set of all elements in X that are related to x under R:

= \{ y \in X \mid y \, R \, x \}.

This set consists of precisely those elements equivalent to x.^[22]^[2] Equivalence classes exhibit key properties arising from the reflexive, symmetric, and transitive nature of R. Each class is non-empty, as reflexivity ensures x \in for every x \in X.^[22] The classes are pairwise disjoint: for any a, b \in X, either = or \cap = \emptyset.^[3] Moreover, the classes cover the entire set X, meaning every element of X belongs to exactly one equivalence class.^[23] To specify the relation when multiple are under consideration, the notation _R is used for the equivalence class of x under R. The size of an equivalence class $$ can vary depending on the relation and set; some classes may be finite, while others are infinite, and their internal structure reflects the symmetries imposed by R.^[22] A classic example occurs with congruence modulo n on the integers \mathbb{Z}, where a \, R \, b if n divides a - b. The equivalence class $$ is the residue class consisting of all integers congruent to k modulo n:

= \{ \dots, k - 2n, k - n, k, k + n, k + 2n, \dots \}.

Each such class is infinite and equally structured, capturing numbers that share the same remainder when divided by n.^[22]

Partitions

A partition of a set X is a collection of nonempty subsets of X that are pairwise disjoint and whose union is X.^[24] Every equivalence relation on X induces a unique partition of X, consisting of the equivalence classes as its blocks, while conversely, every partition of X defines a unique equivalence relation on X by declaring two elements equivalent if they belong to the same block.^[24] This establishes a bijection between the set of all equivalence relations on X and the set of all partitions of X.^[24] To see that an equivalence relation R on X yields a partition, consider the collection \Pi_R = \{_R \mid x \in X\} of equivalence classes. Each _R is nonempty by reflexivity, as x \in _R; the union of all such classes is X since every element belongs to its own class; and distinct classes are disjoint, because if _R \cap _R \neq \emptyset, then symmetry and transitivity imply _R = _R.^[24] Conversely, given a partition \Pi = \{A_i \mid i \in I\} of X, define the relation R_\Pi by x R_\Pi y if and only if x and y are in the same A_i. This R_\Pi is reflexive (each x is in some A_i), symmetric (membership is symmetric), and transitive (if x, y \in A_i and y, z \in A_i, then x, z \in A_i), hence an equivalence relation whose classes are precisely the blocks A_i.^[24] These constructions are inverses, confirming the bijection.^[24] The number of partitions of a finite set with n elements is given by the nth Bell number B_n.^[25] The Bell numbers satisfy the recurrence B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_{n-k} with B_0 = 1, yielding values such as B_1 = 1, B_2 = 2, B_3 = 5, B_4 = 15, and B_5 = 52.^[25] More granularly, the number of partitions into exactly k blocks is the Stirling number of the second kind S(n,k), and B_n = \sum_{k=1}^n S(n,k).^[25] These numbers thus also count the equivalence relations on an n-element set.^[25]

Quotient Sets

Given an equivalence relation R on a set X, the quotient set X/R is defined as the set of all equivalence classes of R, that is, X/R = \{ \mid x \in X \}, where = \{ y \in X \mid y \, R \, x \} denotes the equivalence class of x.^[26]^[22] This construction formalizes the partition of X induced by R into a new set whose elements are the distinct equivalence classes.^[27] The canonical projection map \pi: X \to X/R is defined by \pi(x) = for all x \in X.^[26] This map is surjective, as every equivalence class

is the [image](/page/Image) of its representative $x$, and the fibers of $\pi$—that is, the preimages $\pi^{-1}()$—precisely coincide with the equivalence classes

.^[26]^[27] Equivalence relations on X naturally induce structures on the quotient set X/R. Specifically, if f: X \to Y is a function such that x \, R \, y implies f(x) = f(y) (meaning f is constant on equivalence classes), then there exists a unique induced function \bar{f}: X/R \to Y satisfying \bar{f} \circ \pi = f, defined by \bar{f}() = f(x).^[28] This induced map preserves the essential behavior of f while operating directly on the quotient. Similarly, binary relations on X compatible with R can induce relations on X/R. A classic example arises with the integers \mathbb{Z} under the equivalence relation a \sim b if n divides a - b for some fixed positive integer n. The quotient set \mathbb{Z}/\sim consists of the equivalence classes

{{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}}, {{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}}, \dots, [n-1]

, which is in natural bijection with the cyclic group \mathbb{Z}/n\mathbb{Z}.^[26] The projection \pi: \mathbb{Z} \to \mathbb{Z}/n\mathbb{Z} given by \pi(k) = [k \mod n] is surjective, with fibers being the arithmetic progressions differing by multiples of n.^[26]

Structural Connections

Fundamental Theorem of Equivalence Relations

The fundamental theorem of equivalence relations establishes a bijective correspondence between the set of all equivalence relations on a given set X and the set of all partitions of X. Specifically, for any set X, there is a one-to-one correspondence where each equivalence relation \sim on X corresponds uniquely to the partition consisting of its equivalence classes, and conversely, each partition of X defines a unique equivalence relation on X.^[29] To prove this bijection, first consider the forward direction: given an equivalence relation R on a nonempty set A, the distinct equivalence classes of R form a partition of A. The union of all equivalence classes $$ for a \in A equals A, since every element belongs to its own class by reflexivity. Moreover, the classes are pairwise disjoint: if \cap \neq \emptyset, then there exists some c such that a R c and b R c, implying a R b by symmetry and transitivity, so =. Thus, the map from equivalence relations to partitions is well-defined and injective.^[29] For the inverse direction, given a partition P = \{B_i \mid i \in I\} of A, define the relation R_P by x R_P y if and only if x and y belong to the same block B_i \in P. This R_P is reflexive, as each x \in B_i satisfies x R_P x; symmetric, since membership in the same block is bidirectional; and transitive, because if x, y \in B_i and y, z \in B_i, then x, z \in B_i. Hence, R_P is an equivalence relation, and the equivalence classes of R_P are precisely the blocks of P, confirming surjectivity. The two maps are inverses, establishing the bijection.^[29] This theorem unifies the perspectives of equivalence relations and partitions, showing that every partition of X arises from a unique equivalence relation via block membership, and every equivalence relation induces a unique partition via its classes. As a corollary, for a finite set X with |X| = n, the number of equivalence relations on X equals the number of partitions of an n-element set, which is the nth Bell number B_n. For instance, B_3 = 5 for a set with three elements.^[30]

Generating Equivalence Relations

Equivalence relations can be generated from arbitrary binary relations by taking their reflexive, symmetric, and transitive closure, which produces the smallest equivalence relation containing the original relation.^[31] For a given relation R on a set A, the reflexive closure adds all pairs (a, a) for a \in A, the symmetric closure further includes (b, a) whenever (a, b) \in R, and the transitive closure incorporates (a, c) whenever there exists b such that (a, b) \in R and (b, c) \in R.^[31] This process can be applied iteratively until the resulting relation satisfies reflexivity, symmetry, and transitivity, ensuring it is the minimal such extension.^[31] Another standard method constructs an equivalence relation directly from a partition of the underlying set. Given a partition P = \{B_i \mid i \in I\} of a set A, where the B_i are nonempty disjoint subsets whose union is A, define the relation R by x R y if and only if x and y belong to the same block B_i for some i.^[32] Formally, R = \bigcup_{i \in I} (B_i \times B_i), which is reflexive because each x \in A pairs with itself in its block, symmetric by the equality of pairs within blocks, and transitive since elements in the same block remain connected through any intermediate element in that block.^[32] In algebraic structures, equivalence relations known as congruences are often generated as the kernels of homomorphisms. For a homomorphism \phi: A \to B between algebraic structures, the kernel \ker \phi = \{(a, a') \in A \times A \mid \phi(a) = \phi(a') \} forms a congruence relation on A, meaning it is an equivalence relation compatible with the operations of A.^[33] This kernel respects the structure, ensuring that if a \sim a' and b \sim b', then the operations applied to them yield equivalent results.^[33] A concrete example arises in the integers \mathbb{Z} with addition, where the congruence modulo n (for n > 0) is generated as the kernel of the canonical projection homomorphism \pi: \mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}, defined by \pi(k) = k + n\mathbb{Z}.^[9] Thus, a \equiv b \pmod{n} if and only if \pi(a) = \pi(b), or equivalently, n divides a - b, partitioning \mathbb{Z} into n equivalence classes represented by \{0, 1, \dots, n-1\}.^[9] This relation is reflexive (n divides $0), symmetric (if n divides a - b, then it divides b - a), and transitive (if n divides a - b and b - c, then it divides a - c).^[9]

Comparing Equivalence Relations

Equivalence relations on a fixed set can be compared using the notion of refinement, which provides a partial order on the collection of all such relations. Specifically, for two equivalence relations R and S on a set X, R is said to be finer than S (or S coarser than R) if R \subseteq S as subsets of X \times X. This inclusion implies that every equivalence class of R is contained within some equivalence class of S, meaning the partition induced by R refines the partition induced by S. This correspondence between refinement of relations and refinement of their associated partitions is a fundamental duality in set theory.^[18] The set of all equivalence relations on X, denoted \mathcal{E}(X), forms a complete lattice under the refinement order, where the order is defined by inclusion (R \leq S if R \subseteq S). In this lattice, the meet (greatest lower bound) of two equivalence relations R and S is their intersection R \cap S, which is itself an equivalence relation as it inherits reflexivity, symmetry, and transitivity from both. The join (least upper bound) is the transitive closure of their union R \cup S, ensuring the result is transitive while containing both relations. This lattice structure captures how equivalence relations can be combined or compared systematically, with \mathcal{E}(X) being distributive and semimodular for finite |X| \geq 4.^[34] In this lattice, the coarsest equivalence relation is the universal relation \Delta_X = X \times X, where all elements of X are equivalent, corresponding to the single-block partition \{\{X\}\}. Conversely, the finest equivalence relation is the equality relation \{(x,x) \mid x \in X\}, where each element forms its own singleton class, yielding the discrete partition consisting of all singletons. These extremal elements bound the lattice: every equivalence relation refines the universal relation and is refined by the equality relation.^[18] A concrete example illustrates refinement on the integers \mathbb{Z}. The congruence relation modulo 4, defined by a \equiv b \pmod{4} if $4 \mid (a - b), partitions \mathbb{Z} into four classes: \{ \dots, -8, -4, 0, 4, 8, \dots \}, \{ \dots, -7, -3, 1, 5, \dots \}, and similarly for residues 2 and 3. This refines the coarser congruence modulo 2, which partitions into evens and odds, as each modulo-4 class (e.g., multiples of 4 and 4-plus-1) is a subset of either the evens or odds modulo 2.^[35]

Applications in Mathematics

Algebraic Structures

In group theory, normal subgroups play a central role in defining equivalence relations via cosets. For a subgroup H of a group G, the relation x \sim y if xy^{-1} \in H is an equivalence relation on G, with equivalence classes being the left cosets of H.^[36] However, this relation respects the group operation—allowing a well-defined quotient group structure—only when H is normal, meaning left and right cosets coincide.^[37] In this case, the quotient group G/N consists of cosets as elements, with multiplication [g_1][g_2] = [g_1 g_2], providing a fundamental way to construct new groups from existing ones.^[36] In ring theory, ideals serve an analogous role to normal subgroups, acting as kernels of ring homomorphisms and inducing equivalence relations. For an ideal I in a ring R, the relation a \equiv b \pmod{I} if a - b \in I is an equivalence relation, partitioning R into cosets a + I.^[38] The quotient ring R/I is then formed by these cosets, with addition and multiplication defined componentwise: (a + I) + (b + I) = (a + b) + I and (a + I)(b + I) = (ab) + I, provided I absorbs multiplication from R.^[39] This construction extends to modules, where submodules play the role of ideals, yielding quotient modules that preserve the module structure.^[39] In category theory, equivalence relations generalize to equivalences between categories, defined via functors that are inverses up to natural isomorphism. An equivalence between categories \mathcal{C} and \mathcal{D} consists of functors F: \mathcal{C} \to \mathcal{D} and G: \mathcal{D} \to \mathcal{C} such that G \circ F \cong \mathrm{id}_{\mathcal{C}} and F \circ G \cong \mathrm{id}_{\mathcal{D}}, where \cong denotes natural isomorphism.^[40] A natural isomorphism between functors F and G is a natural transformation whose components are isomorphisms in the codomain category.^[41] Groupoids, as categories where every morphism is invertible, exemplify structures where all equivalences arise naturally from these functorial inverses.^[40] In lattice theory, equivalence relations that preserve the order structure are known as congruences, which are compatible with the lattice operations of meet and join. A congruence \theta on a lattice L is an equivalence relation such that if a \theta b and c \theta d, then (a \wedge c) \theta (b \wedge d) and (a \vee c) \theta (b \vee d), ensuring the quotient L/\theta inherits a lattice structure.^[42] Such relations maintain the partial order on equivalence classes via the induced order \leq if there exist representatives satisfying the original order.^[43] The quotient lattice preserves key properties like distributivity when the original does.^[42]

Well-Definedness

In the context of an equivalence relation ~ on a set X, a function f: X \to Y is said to be well-defined on the quotient set X/~ if it is constant on each equivalence class, meaning that whenever x \sim y, it holds that f(x) = f(y).^[11] This condition ensures that f does not depend on the choice of representative from an equivalence class, allowing it to descend to a genuine function \bar{f}: X/~ \to Y defined by \bar{f}() = f(x), where $$ denotes the equivalence class of x.^[28] The compatibility of f with ~ can be characterized by the inclusion of the kernel of f in the relation: f respects ~ if and only if \ker(f) \subseteq ~, where \ker(f) = \{(x, y) \in X \times X \mid f(x) = f(y)\}.^[28] Under this condition, the induced map \bar{f} is well-defined and satisfies \bar{f} \circ \pi = f, with \pi: X \to X/~ the canonical projection sending x to $$.^[11] This framework guarantees that operations or mappings on quotient sets are unambiguous and independent of representatives. A concrete example arises in modular arithmetic, where congruence modulo n (for n \in \mathbb{N}) defines an equivalence relation on the integers \mathbb{Z}, partitioning them into residue classes = \{m \in \mathbb{Z} \mid m \equiv k \pmod{n}\}. The addition and multiplication operations on \mathbb{Z}/n\mathbb{Z} are well-defined: if a \equiv c \pmod{n} and b \equiv d \pmod{n}, then a + b \equiv c + d \pmod{n} and ab \equiv cd \pmod{n}, so + = [a + b] and \cdot = [ab].^[11] For instance, in \mathbb{Z}/5\mathbb{Z},

{{grok:render&&&type=render_inline_citation&&&citation_id=2&&&citation_type=wikipedia}} + {{grok:render&&&type=render_inline_citation&&&citation_id=3&&&citation_type=wikipedia}} = {{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}}

and

{{grok:render&&&type=render_inline_citation&&&citation_id=2&&&citation_type=wikipedia}} \cdot {{grok:render&&&type=render_inline_citation&&&citation_id=3&&&citation_type=wikipedia}} = {{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}}

, preserving the structure regardless of representatives like $7 for

{{grok:render&&&type=render_inline_citation&&&citation_id=2&&&citation_type=wikipedia}}

.^[11] For binary operations on quotient sets, well-definedness requires compatibility with the equivalence relation: an operation \star: X \times X \to X induces a well-defined \bar{\star}: (X/~) \times (X/~) \to X/~ if [x_1] \star [x_2] = [x_1 \star x_2] whenever [x_1'] = [x_1] and [x_2'] = [x_2], meaning the result is independent of choices within classes.^[28] This criterion verifies that the operation respects the partition induced by ~, enabling consistent algebraic structures on the quotient.^[11]

Mathematical Logic

In mathematical logic, congruence relations on terms and formulas arise as equivalence relations that preserve the structure of logical expressions under substitution and operations. A congruence \theta on an algebra A of type L is an equivalence relation on A's carrier that satisfies compatibility: for all n-ary connectives * \in L, if a_i \theta b_i for i = 1, \ldots, n, then *^A(a_1, \ldots, a_n) \theta *^A(b_1, \ldots, b_n).^[44] Such relations enable the formation of quotient algebras A / \theta, where the carrier consists of equivalence classes $$ and operations are defined as *^{A/\theta}([a_1], \ldots, [a_n]) = [*^{A}(a_1, \ldots, a_n)].^[44] In the context of terms, congruences on the term algebra T—where elements are terms built from variables and function symbols, and operations compose terms—are fully invariant under endomorphisms, forming the basis for equational theories.^[45] Quotient models in equational logic extend this framework by constructing models from congruences on algebras, preserving the satisfaction of equations. For an algebra A and congruence \theta, the quotient model A / \theta has universe consisting of classes a / \theta, with operations Q_{A / \theta}(a_0 / \theta, \ldots, a_{r-1} / \theta) = Q_A(a_0, \ldots, a_{r-1}) / \theta, ensuring that equations true in A remain true in the quotient.^[45] This construction is linked to homomorphisms via the Homomorphism Theorem, which identifies quotient models as homomorphic images, and plays a role in undecidability results, such as the Base Undecidability Theorem, where non-trivial quotients are built using \omega-universal terms derivable from finite axiom sets.^[45] In model theory, elementary equivalence captures structural similarity between models through first-order logic. Two structures A and B in the same language are elementarily equivalent, denoted A \equiv B, if they satisfy exactly the same first-order sentences, meaning \mathrm{Th}(A) = \mathrm{Th}(B), where \mathrm{Th} denotes the theory.^[46] This relation is coarser than isomorphism and can be characterized using Ehrenfeucht–Fraïssé games: A \equiv B if and only if the Duplicator has a winning strategy in all finite rounds of the game on A and B.^[46] Types in model theory further refine equivalences by describing possible behaviors of elements; a complete type p(x) over a set of parameters C is a maximal consistent set of formulas in variables x with parameters from C, realizing the "possible worlds" consistent with the theory.^[46] Definable equivalences emerge when an equivalence relation on a structure's domain is defined by a first-order formula, such as (a, b) \sim (c, d) if a + d = b + c in an interpretation of integers in naturals, allowing quotients that link theories via parameter expansions.^[46] Proof theory employs equivalence under provable equality to analyze derivability in formal systems, particularly in theories like Peano arithmetic (PA). In PA, equality = is a binary predicate provably satisfying reflexivity, symmetry, and transitivity as an equivalence relation, with substitution axioms ensuring that if u = v, then replacing u with v in any term t yields an equal term, and in any formula A yields an equivalent formula.^[47] This provable equality underpins equality reasoning in PA, where axioms like induction and successor properties allow derivation of equalities such as \forall y ((0 + y) = (y + 0)), supporting the consistency and completeness of arithmetic proofs.^[47] A concrete example is logical equivalence in propositional logic, where two formulas \phi and \psi are equivalent, denoted \phi \equiv \psi or \models \phi \leftrightarrow \psi, if they have the same truth value under every assignment of truth values to atomic propositions.^[48] This equivalence forms a congruence relation on the set of formulas, as it is compatible with connectives: if \phi_1 \equiv \phi_2 and \psi_1 \equiv \psi_2, then (\phi_1 \land \psi_1) \equiv (\phi_2 \land \psi_2), and similarly for other operations like \lor and \lnot, preserving validity and enabling substitution while maintaining logical properties.^[48]

References

[1]
Equivalence Relation -- from Wolfram MathWorld
An equivalence relation on a set X is a subset of X×X, i.e., a collection R of ordered pairs of elements of X, satisfying certain properties.
[2]
5.1 Equivalence Relations
We say ∼ is an equivalence relation on a set A if it satisfies the following three properties: a) reflexivity: for all a∈A, a∼a. b) symmetry: for all a,b∈A, if
[3]
Equivalence Relation
A binary relation R on a set A is an equivalence relation if and only if (1) R is reflexive (2) R is symmetric, and (3) R is transitive.
[4]
Equivalence Class -- from Wolfram MathWorld
An equivalence class is defined as a subset of the form {x in X:xRa}, where a is an element of X and the notation "xRy" is used to mean that there is an ...
[5]
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 ...
[6]
[PDF] equivalence-relations.pdf
An equivalence relation is a relation which “looks like” ordinary equality of numbers, but which may hold between other kinds of objects. Here are three ...
[7]
[PDF] [Ch 8] Relations 1. Basics 2. Reflexivity, Symmetry, Transitivity
A relation on a set that satisfies the three properties of reflexivity, symmetry, and transitivity is called an equivalence relation. • Example: ✓ Consider the ...
[8]
None
### Summary of Equivalence Relations and Related Properties from CS103 Handout 16
[9]
[PDF] Math 127: Equivalence Relations
An equivalence relation is a relation that is reflexive, symmetric, and transitive. For example, x ∼ y if x and y have the same parity.
[10]
Tilde -- from Wolfram MathWorld
The tilde is the mark "~" placed on top of a symbol to indicate some special property. x^~ is voiced "x-tilde." The tilde symbol is commonly used to denote ...
[11]
[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.<|control11|><|separator|>
[12]
Earliest Uses of Symbols from Geometry - Department of Mathematics
Nov 4, 2006 · The symbol was an S for similis, written sideways. The original manuscripts do not survive and it is uncertain whether the symbol Leibniz first ...
[13]
Equivalence relations (article) - Khan Academy
A ≡ B ( mod C ) ‍ · A mod C = B mod C ‍ · C | ( A − B ) ‍ (The | symbol means divides, or is a factor of) · A = B + K ⋅ C ‍ (where K ‍ is some integer).
[14]
[PDF] Propositional Logic, Equivalences - Washington
- Definition: Two propositions are logically equivalent if they have identical truth values. - The notation for and being logically equivalent is . - Examples:.
[15]
7.2: Equivalence Relations
### Summary: Congruence Modulo n as an Equivalence Relation
[16]
[PDF] Some notes on equivalence relations - Ernie Croot
Jan 23, 2012 · We say that x ∼ y (more properly we should perhaps use the notation x ∼d y to indicate that we are going to produce infinitely many equivalence ...
[17]
[PDF] Contents 1 Relations, Orderings, and Functions - Evan Dummit
◦ Example: The relation of having the same birthday (on the set of people) is an equivalence relation: everyone has the same birthday as themselves, if P has ...Missing: source | Show results with:source
[18]
[PDF] Equivalence and Order - UCSD Math
For example xRy if and only if x<y defines a binary relation on Z, but it is not an equivalence relation because we never have x<x, but an ... size greater than ...<|control11|><|separator|>
[19]
[PDF] Section 9.5
Hence, “divides” is not an equivalence relation. Reflexivity: a divides a for all a. Not Symmetric: For example, 2 divides 4, but 4 divides 2 does not hold.
[20]
[PDF] Homework 8
R is reflexive and symmetric, but not transitive. One example that works here is xRy iff |x − y| ≤ 1. Reflexivity and symmetry are easy to check, and so is ...
[21]
Equivalence Classes - Foundations of Mathematics
Nov 2, 2018 · Definition. Let be an equivalence relation on the set , and let . The equivalence class of under the equivalence is the set. of all elements of ...
[22]
[PDF] Equivalence Classes - Trinity University
Definition. Let R be an equivalence relation on A and let a ∈ A. The equivalence class of a is the set. [a] = {b ∈ A|bRa}, the set of all elements of A that ...
[23]
[PDF] Math 1365 (Intensive Mathematical Reasoning)
Oct 25, 2023 · From the results in the proposition, we can see that the equivalence classes are nonempty, pairwise disjoint subsets of A whose union is A.
[24]
[PDF] 5 Equivalence Relations
R is transitive if xRy, yRz =⇒ xRz for all x, y, z ∈ A. • R is an equivalence relation if R is reflexive, symmetric, and transitive. Example The following ...
[25]
1.4 Bell numbers
... n,k),. where S(n,k) is the number of partitions of {1,2,…,n} into exactly k parts, 1≤k≤n. The S(n,k) are the Stirling numbers of the second kind.
[26]
None
### Summary of Quotient Sets, Projection, and Examples from the Handout
[27]
[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 ...
[28]
[PDF] equivalence relations, quotients, and
Proof: (a) Take x, y ∈ X and consider [x]∼, [y]∼ ∈ X/∼. If [x] ... Hence, there is a 1-1 correspondence between equivalence relations and partitions.
[29]
6.3: Equivalence Relations and Partitions
### Summary of Fundamental Theorem on Equivalence Relations
[30]
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_and_Graph_Theory_(Guichard)/01%3A_Fundamentals/1.05%3A_Bell_Numbers
[31]
[PDF] 8 Relations - Computer Science
Apr 5, 2021 · The reflexive symmetric transitive closure of R is the smallest relation R≡ ⊇ R such that R≡ is reflexive, symmetric, and transitive.
[32]
[PDF] Basic Modern Algebra with Applications - ResearchGate
... (equivalence relation induced by partition Pρ). Proof Let x ∈ X. Since P is a partition, there exists A ∈ P, such that x ∈ A. So,. (x,x) ∈ ρ. This implies ...<|control11|><|separator|>
[33]
[PDF] Math 222A W03 D. Congruence relations 1 . The concept Let's start ...
(6) For a homomorphism. : A , the kernel of is a congruence relation. ere the kernel of a homomorphism means the equivalence relation that induces on its ...
[34]
[PDF] arXiv:1604.08401v2 [math.RT] 21 Oct 2016
Oct 21, 2016 · of two relations is given by the intersection of relations and the join of two relations is given by the transitive closure of union of ...
[35]
[PDF] Chapter 1: Abstract Group Theory - Rutgers Physics
We can define an equivalence relation by saying that a ∼ b iff a − b is ... modulo 4 refines equivalence modulo 2. 3. Groups: Basic Definitions And ...
[36]
[PDF] 6 Normal Subgroups and Quotient Groups - MIT OpenCourseWare
... equivalence relation; in this case, the equivalence relation is defined by the partition of G into cosets. bThe product can be verified to be independent of ...
[37]
[PDF] MAT 312/AMS 351 Notes and exercises on normal subgroups and ...
MAT 312/AMS 351. Notes and exercises on normal subgroups and quotient groups. If H is a subgroup of G, the equivalence relation ∼H is defined be- tween elements ...
[38]
[PDF] Chapter 6, Ideals and quotient rings
The equivalence classes for this relation, are commonly called cosets. What ... We can generalize this idea of ideals and kernels to any ring homomorphism.
[39]
[PDF] Math 533 Winter 2021, Lecture 3: Rings and ideals
Thus, ideals of rings are somewhat like normal subgroups of groups: You can “quotient them out” (this is slang for “take a quotient by them”) and get a ring ...
[40]
equivalence of categories in nLab
Oct 27, 2025 · An equivalence between two categories is a pair of functors between them which are inverse to each other up to natural isomorphism of functors.Isomorphism · Strong equivalence · Weak equivalence · Anaequivalence
[41]
[PDF] Equivalence of Categories - OU Math
Sep 24, 2015 · An equivalence of categories consists of functors F: CD, G D C together with a natural isomorphism 7: 1c Go F and e: FoG 1p. Definition: ...
[42]
[PDF] Orders, lattices and Boolean algebras - Tommaso Moraschini
equivalence relations on A that preserve the operations of A. The next proposition states that these are precisely the congruences of the lattice reduct hA ...
[43]
[PDF] Lattice congruences of the weak order: Algebra, combinatorics, and ...
Mar 30, 2019 · equivalence class is order-preserving. (iii) The map π↑ taking each element to the top element of its equivalence class is order-preserving.
[44]
Propositional Consequence Relations and Algebraic Logic
Dec 19, 2006 · An L-equation is a formula φ ≈ ψ where φ and ψ are terms of the L-algebraic language (that is, L-formulas if we take the propositional logics ...
[45]
[PDF] Equational Logic - University of South Carolina
The concepts that can be expressed by means of equations and the kinds of proofs that may be devised using equations are central concerns of equational logic.
[46]
Model Theory - Stanford Encyclopedia of Philosophy
Nov 10, 2001 · Model theory is the study of the interpretation of any language, formal or natural, by means of set-theoretic structures, with Alfred Tarski's truth definition ...
[47]
[PDF] 19. Peano Arithmetic
19 Peano Arithmetic. 19.1 Equality Theories. An equality theory is one with a binary predicate, usually denoted '=,' which is provably an equivalence relation ...
[48]
Propositional Logic - Stanford Encyclopedia of Philosophy
May 18, 2023 · Any formula of propositional logic under the classical interpretation is equivalent to a disjunction of conjunctions of propositional variables ...