Finitary relation ($R\subseteq X_1\times \cdots \times X_n$)

A subset of a finite Cartesian product specifies which tuples of elements satisfy a relation. A first-order structure interprets a relation symbol with $n$ argument places as such a subset of the $n$-fold Cartesian product of its domain of a first-order structure. For two argument places this is a binary relation; for three, the set of triples satisfying $x+y=z$ is an example involving addition.

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

A binary relation is right Euclidean when any two successors of the same element are related in the indicated order. A reflexive relation with this property is an equivalence relation: reflexivity gives symmetry, and symmetry followed by the Euclidean property gives transitivity. Without reflexivity, even the empty binary relation is Euclidean.

Reversing every ordered pair of a binary relation. Swapping the two components is its own inverse and therefore preserves distinctness of a representation by a list of distinct pairs.

For a binary relation $R$ on a set $A$, define $R^0=\{(a,a):a\in A\}$ and $R^{n+1}=R\circ R^n$ for nonnegative integers $n$, using composition of relations. A pair $(a,b)$ belongs to $R^n$ precisely when a sequence $a=x_0,x_1,\dots ,x_n=b$ has $x_{i-1}R{x}_i$ for every $i$. This follows by mathematical induction, splitting off one step in the recurrence. Thus $R^n$ records paths with exactly $n$ steps, rather than at most $n$ steps. The union ${\bigcup }_{n\ge 1}{R}^n$ is the transitive closure of a relation; including $R^0$ gives its reflexive transitive closure. The powers of a single relation agree under the two common composition-order conventions.

Two expressions are equal when they denote the same mathematical object. An equality test in a program implements a specified comparison of represented values; for example, approximate floating-point arithmetic comparison is not identical to exact equality of real numbers.

A binary relation is serial when every domain element has at least one outgoing related element. A serial relation may have cycles; combining seriality with an irreflexive relation and a transitive relation instead forces a nonempty domain to be infinite, by the infinite-model property of a serial strict partial order.

A binary relation is irreflexive when no element is related to itself. An irreflexive relation that is also a transitive relation is a strict partial order. Transitivity then excludes every finite directed cycle, since a cycle would imply $R(x,x)$ at its starting element.

A binary relation is irreflexive exactly when it contains no diagonal pair $(x,x)$. Its negation requires at least one diagonal pair, whereas a reflexive relation requires every diagonal pair.

Represent a binary relation on an $n$-element finite set by its zero-one incidence matrix. If no column may be empty, each column has $2^n-1$ choices. Apply the inclusion-exclusion principle to empty rows: fixing $k$ empty rows leaves $(2^{n-k}-1{)}^n$ allowed matrices. Summing over those row sets with alternating signs yields the displayed count.

A weak preference relation records that one alternative is at least as desirable as another. Rational preferences are complete and transitive. Their strict preference and indifference relation are the asymmetric and symmetric parts. On a consumption space, continuity is expressed by a closed set of weakly ranked pairs.

A preference relation on lotteries is complete when every pair is comparable, allowing an indifference relation. Completeness does not require strict ranking of distinct lotteries. Together with a transitive relation, it gives the ordering assumption in the Von Neumann-Morgenstern utility theorem.

This is the Fell topology restricted to closed graphs of complete, transitive, continuous preference relations. Both the upper limit condition and approximation of every limiting weak comparison are needed. A large limiting indifference class can make the second requirement stronger than convergence of numerical utility differences.

On $[0,\infty )$ the utility functions $u_n(x)=x/n$ converge uniformly on every bounded set to $u(x)=0$. Their preference relations remain the usual order, while the limiting utility function makes all pairs indifferent. The weak comparison $0⪰1$ in the limit cannot be approximated by comparisons from the varying graphs. Uniform convergence does guarantee the upper graph-limit condition, because convergent pairs remain in a fixed bounded set.

For a preorder, the indifference relation is an equivalence relation. Passing to its equivalence classes removes ties and produces a partial order.

The strict preference associated with a weak preference relation retains comparisons that do not hold in the reverse direction.

This convention composes paths in their written order; some sources instead reverse that convention. Composition of relations is associative. Taking inverse relations reverses the order: $(R\circ S{)}^{-1}=S^{-1}\circ R^{-1}$.

// Target: foundations-of-mathematics.bigb

If $R\subseteq R^{\prime }$ and $S\subseteq S^{\prime }$, then $R\circ S\subseteq R^{\prime }\circ S^{\prime }$. A witness joining a pair through $S$ and then $R$ also joins it through the larger relations. If both $R$ and $S$ are reflexive relations on the same set, inserting an identity step gives $R\cup S\subseteq R\circ S$, so monotonicity also gives $(R\cup S{)}^2\subseteq (R\circ S{)}^2$.

If $R:X\times Y\to \{false,true\}$ and $S:Y\times Z\to \{false,true\}$ expose only membership predicates, composition requires finding whether some middle value satisfies both. A complete finite enumeration of $Y$ makes the query decidable by scanning until a witness is found or all values fail. Without an enumeration or equivalent access operation, generic membership oracles do not supply enough information: a finite query transcript can agree with an all-false case yet omit a fresh middle witness that makes composition true. Known finiteness is not the same as an available traversal. A separate carrier argument preserves the variance of the base predicate interfaces.

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

The reflexive closure of a binary relation $R\subseteq A\times A$ is $R\cup {\Delta }_A$, where ${\Delta }_A=\{(a,a):a\in A\}$. Every reflexive relation containing $R$ must contain the diagonal, so this is the least such extension.

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

The symmetric closure of a binary relation $R$ is $R\cup R^{-1}$, where $(x,y)\in R^{-1}$ means $(y,x)\in R$. Every symmetric relation containing $R$ contains all these reversed pairs, proving minimality.

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

The property of a binary relation that opposite directed relationships between two elements can hold only when those elements are equal. It does not require every pair to be comparable and does not prohibit a longer directed cycle whose reverse edges are initially absent. Taking reflexive transitive closure can therefore destroy this property.

The union of two antisymmetric relations need not be an antisymmetric relation. On $\{0,1\}$, take $R=\{(0,1)\}$ and $S=\{(1,0)\}$. Each is an antisymmetric relation, but $R\cup S$ contains both directions between distinct elements. This counterexample shows why testing each binary relation separately does not control cross-pairs in their union.

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

The transitive closure of a relation connects $x$ to $y$ when a finite nonempty chain of $R$-steps leads from $x$ to $y$. Concatenation proves transitivity, and induction along a chain shows that any transitive relation containing $R$ contains $R^{+}$. This concerns closure of a relation, rather than the transitive closure of a set under membership.

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