Equivalence relation ($x\sim y$)

An equivalence relation says which set elements should count as the same for a particular purpose. In modular arithmetic, for example, distinct integers with the same remainder are equivalent. The relation gathers interchangeable set elements into equivalence classes; the quotient set then treats each whole equivalence class as one object.

Formally, an equivalence relation on a set $X$ is a binary relation $R\subseteq X\times X$, written $x\sim y$, satisfying three conditions for all $x,y,z\in X$:These conditions make the equivalence classes a partition of a set: each set element belongs to exactly one class. ^[ref]

For a worked example, take the finite set $X=\{0,1,\dots ,8\}$ and restrict integer congruence modulo three to $X$:Reflexivity follows because $x-x=0$. The symmetric relation property follows by changing the sign of a difference, and transitivity follows by adding $x-y$ and $y-z$: divisibility by three is preserved in both steps. Thus $0\sim 3$ and $3\sim 6$ force $0\sim 6$. The three equivalence classes are $\{0,3,6\}$, $\{1,4,7\}$ and $\{2,5,8\}$. Their members alternate along the number line; membership in an equivalence class need not mean being close together.

The transitivity requirement rules out a tempting alternative. On $\{0,1,2\}$, define nearness by the absolute value condition $|x-y|\le 1$. This binary relation is reflexive and symmetric, but $0$ is near $1$ and $1$ is near $2$ while $0$ is not near $2$. Its neighborhoods $\{0,1\}$, $\{0,1,2\}$ and $\{1,2\}$ overlap without being equal. They are not equivalence classes or a partition of a set.

A congruence relation on a first-order structure is an equivalence relation compatible with each interpreted function and relation. Equivalent input tuples give equivalent function outputs, and an atomic relation has the same truth value on equivalent input tuples. This compatibility makes the functions and relations well-defined on the quotient set. In a Henkin term model with equality, membership of a formal equality in the maximal consistent theory gives precisely the equivalence relation used for this quotient.

Using the left-to-right convention for composition of relations, two equivalence relations $R,S$ have an equivalence-relation composite exactly when $R\circ S=S\circ R$. Its inverse is $S\circ R$. Commutation gives $(R\circ S{)}^2=R^2\circ S^2=R\circ S$, proving transitivity. Every equivalence relation containing $R,S$ contains their two-step composite, so this is their least common extension.

// Destination: combinatorics.bigb

For two equivalence relations on the same set, their composite contains each and is reflexive. It is symmetric exactly when the relations commute. It is transitive exactly when $S\circ R\subseteq R\circ S$, which by inversion is also equivalent to commutation. Under these conditions the composite is the smallest equivalence relation containing both. For congruences modulo $m,n$ on the integers, their composite is congruence modulo $\gcd (m,n)$.

// Target: combinatorics.bigb

The equivalence closure of a binary relation $R$ is the least equivalence relation containing it. Add diagonal and reversed pairs, then connect points by finite chains. Constant chains prove reflexivity, reversed chains prove symmetry, and concatenated chains prove transitivity. Any equivalence relation extending $R$ contains every such chain endpoint by induction.

A union of equivalence relations on the same set is reflexive and symmetric, but can fail transitivity. On a three-point set, partitions into blocks $\{1,2\},\{3\}$ and $\{1\},\{2,3\}$ make the union relate $1$ to $2$ and $2$ to $3$ without relating $1$ to $3$. An equivalence relation containing both requires transitive closure as well.

The intersection of any family of equivalence relations on one set is an equivalence relation. Reflexivity and symmetry hold in every component. A pair of consecutive related points belongs to every component, so each component's transitivity supplies the required final pair. Its equivalence classes refine the component partitions. The empty intersection is the universal relation.

For positive integers $a,b$, partition the nonnegative integers by equality of $\lfloor n/a\rfloor$ and separately by equality of $\lfloor n/b\rfloor$. The intersection of equivalence relations gives nonempty intersections of these consecutive blocks. Its boundaries occur at multiples of either $a$ or $b$.

Let $\ell =\mathrm{lcm}(a,b)$. Translating by $\ell$ increases the two floor quotients by the fixed integers $\ell /a$ and $\ell /b$, so it preserves all within-block equalities and all block boundaries. Thus the refinement repeats in intervals of length $\ell$. If $0=c_0<c_1<\cdots <c_r=\ell$ lists the multiples of $a$ or $b$ within one period, its blocks are exactly $\{j\ell +c_i,\dots ,j\ell +c_{i+1}-1\}$ for $j\ge 0$ and $0\le i<r$. The pattern repeats, but blocks in different periods remain distinct equivalence classes.

An equivalence relation on the natural numbers is co-computably enumerable when its complement as a set of pairs is computably enumerable. Inequivalence can then be positively recognized, even when equivalence cannot be decided. This is sufficient for a semidecidable least-representative transversal.

For a co-computably enumerable equivalence relation, the least element of each equivalence class forms a complete transversal of a set family. Membership is semidecidable: run the finitely many inequivalence tests against smaller numbers in parallel and accept when all succeed. Infinitely many classes are needed only to make the resulting transversal infinite.

Two functions $f:A\to X$ and $g:B\to X$, whose domains lie in one ambient set, are equivalent modulo finite changes when $A△B$ is a finite set and the functions disagree at only finitely many points of $A\cap B$. The symmetric difference inclusion $A△C\subseteq (A△B)\cup (B△C)$ handles domains in a transitive chain. An exceptional set for values must also include points of $A\cap C$ absent from the middle domain $B$; these lie in the finite difference $A\setminus B$.

An equivalence class collects all the set elements indistinguishable from a specified set element under an equivalence relation. For an equivalence relation $R$ on a set $X$, the precise definition isThe ambient set matters: a finite class for integer congruence restricted to $\{0,\dots ,8\}$ differs from the infinite residue class for the same integer congruence on all integers. We write $[x]$ when the equivalence relation and ambient set are clear.

In the finite modulo-three example,There are nine names $[x]$ but only three distinct equivalence classes. In particular, $3\in [0]$, whereas $[3]=[0]$: the first statement is membership of a set element; the second is equality of two sets.

For any equivalence relation on $X$, the essential rule isReflexivity puts $x$ in $[x{]}_R$, so the equivalence classes are nonempty and cover $X$. If two equivalence classes share $z$, the symmetric relation property and transitivity relate their defining elements through $z$; transitivity then makes their members coincide. Thus distinct equivalence classes are disjoint, giving a partition of a set. Conversely, declare two set elements equivalent when they belong to the same block of a partition of a set. The three relation properties follow immediately and its equivalence classes recover the blocks. ^[ref]

An equivalence class representative is any set element belonging to that equivalence class. In the finite modulo-three example, either $0$, $3$ or $6$ represents $\{0,3,6\}$. Changing the equivalence class representative changes its name but preserves the equivalence class itself. Choosing $0,1,2$ gives one representative of an equivalence class from each class; the quotient set consists of the three whole sets.

Every function $f:X\to Y$ induces an equivalence relation on $X$ by $x\sim y$ exactly when $f(x)=f(y)$. Reflexivity, symmetry, and transitivity follow from the corresponding properties of equality in $Y$; the equivalence classes are the nonempty fibers of $f$.

Positive integers are equivalent when they have the same finite set of prime factors. Equivalently, each divides a positive power of the other. This equivalence relation is induced by the radical of an integer; its equivalence classes correspond to finite prime supports. The empty support gives the singleton $\{1\}$, and every nonempty support gives an infinite class by varying exponents.

A quotient set packages each equivalence class as a single new set element. It remembers which class an original set element belongs to and forgets which member of that class it was. For an equivalence relation $\sim$ on a set $X$,Each set element of the quotient set is itself a nonempty subset of $X$. The canonical projection of a quotient set sends an original set element to this entire equivalence class. ^[ref]

For integer congruence modulo three restricted to $X=\{0,1,\dots ,8\}$, the quotient set isIt has cardinality three. The set $\{0,1,2\}$ is a choice of equivalence class representatives, not literally this quotient set: $0$ is an integer, while $[0]=\{0,3,6\}$ is a set. The function sending each chosen equivalence class representative to its equivalence class is a bijection between these two different sets.

A quotient set alone specifies no arithmetic. To obtain the familiar modular arithmetic example with addition, use integer congruence on the whole set of integers. Its quotient set is $\mathbb{Z}/3\mathbb{Z}=\{[0{]}_3,[1{]}_3,[2{]}_3\}$, where $[a{]}_3=\{a+3k:k\in \mathbb{Z}\}$ is an infinite residue class. Define addition byThe answer must be independent of the equivalence class representatives. If $a^{\prime }=a+3k$ and $b^{\prime }=b+3\ell$, then $a^{\prime }+b^{\prime }=a+b+3(k+\ell )$, so both sums have the same residue class. This is what it means for the group operation to be well-defined. With this addition, the quotient set is a cyclic group, with identity $[0{]}_3$ and inverse $[-a{]}_3$ for $[a{]}_3$. ^[ref]

For example, $[2{]}_3+[2{]}_3=[4{]}_3=[1{]}_3$. Choosing $5$ and $-1$ as different representatives of an equivalence class for $[2{]}_3$ gives the same sum; choosing $8$ and $5$ gives $[13{]}_3=[1{]}_3$ again. These calculations use residue classes of all integers. Raw addition on the finite $X=\{0,\dots ,8\}$ does not stay in $X$: $8+8=16\notin X$. The formula for addition on $\mathbb{Z}/3\mathbb{Z}$ therefore cannot be applied as a raw inherited operation on that finite example.

The canonical projection of a quotient set is the function $q(x)=[x]$. It is surjective: every set element of $X/\sim$ is $[x]$ for some $x\in X$. Two set elements have the same image exactly when they are related by the equivalence relation. Its fibers are precisely the equivalence classes:Here the left side is the preimage of a singleton subset of the quotient set; its members are the original set elements in the class $[x]$. In the diagram, the three arrows arriving at $[1]$ start at $1$, $4$ and $7$.