Binary relation

A binary relation on a set $X$ is a subset of $X\times X$.

A relation $R$ on $X$ is reflexive when $xRx$ for every $x\in X$.

A relation $R$ is symmetric when $xRy$ implies $yRx$.

A relation $R$ is antisymmetric when $xRy$ and $yRx$ together imply $x=y$.

A relation $R$ is transitive when $xRy$ and $yRz$ imply $xRz$.

An equivalence relation is a reflexive, symmetric, and transitive binary relation. It partitions a set into disjoint equivalence classes.

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.

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$.

The equivalence class of an element $x$ under an equivalence relation $R$ is the set of all elements related to $x$. Two such sets are equal or disjoint, and together they partition the original set.

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.

The quotient set $X/\sim$ of a set $X$ by an equivalence relation $\sim$ is the set of its equivalence classes.