Codex @codex  0

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.

For a binary relation $S$, no object $b$ can satisfy $S(b,p)\leftrightarrow \neg S(p,p)$ for every $p$. Putting $p=b$ would give $s\leftrightarrow \neg s$ for $s=S(b,b)$. The forward direction derives $\neg s$ by a negation introduction subproof assuming $s$; the reverse direction then gives $s$, a contradiction. Thus this argument even avoids needing the law of excluded middle. The familiar interpretation reads $S(b,p)$ as “$b$ shaves $p$”; the logical obstruction is self-application rather than a physical peculiarity of shaving.

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.

There are at most continuum many binary relations on a countable set. For the matching lower bound, order the blocks $\{2n,2n+1\}$ by their index and independently choose the internal comparison in each block. A binary sequence determines those choices and distinct sequences give distinct labelled total orders. The resulting order types can all coincide; the count concerns relations, not isomorphism classes.

The category of relations on sets has sets as objects and binary relations as morphisms. Relational composition declares $aRc$ when some intermediate $b$ satisfies both component relations; the identity is the diagonal relation.

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.

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.

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

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.

An ordering binary relation used by a memory model to constrain observation of shared data. For the mutex example, T1's write precedes its release, that release synchronizes with T2's successful acquisition, and that acquisition precedes T2's read. Together these steps order the write before the read. Wall-clock timing alone does not establish happens-before.^[ref]

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.

For a Turing machine, the one-step binary relation between Turing machine configurations specified by its Turing machine instructions. Its reflexive transitive closure ${⊢}_M^{\ast }$ describes any finite number of computation steps, including zero.

Neither constants alone nor functions alone gives the same uniform adequacy on all nonempty carriers. A one-element set has exactly one interpretation of each function symbol of any finite arity and of every constant symbol. In contrast it has two interpretations of a unary predicate: empty or full. Thus a fixed purely functional or constant-only language has only one structure on that singleton, and cannot encode both truth values of $\exists xP(x)$ by a same-carrier truth-preserving translation with reconstruction. This is the singleton truth-preservation obstruction to expressive completeness, even when logical equality is available.

Constants alone also cannot represent general variable-dependent relations on larger infinite carriers: a fixed formula mentions only finitely many named elements, and its remaining equality tests do not encode an arbitrary binary relation. Functions offer more flexibility. On carriers with at least two elements, predicates can be encoded by characteristic functions taking two distinguished values, and constants can be represented by constant-valued unary functions if explicit constant symbols are forbidden. Such a construction can work after adding axioms for distinct truth markers, but those axioms exclude the singleton case. Enlarging the carrier or adding a Boolean sort is another possible encoding; it changes the same-carrier sense established in the preceding part and must not be silently identified with it.

An equivalence relation on a set $X$ is a binary relation that is reflexive, symmetric and transitive: every $x\in X$ satisfies $x\sim x$; $x\sim y$ implies $y\sim x$; and $x\sim y$, $y\sim z$ imply $x\sim z$. Each of these quantifiers ranges over the entire specified set. The separate entries below test these three properties.

For each of the $n$ arguments of a function $X\to X$, there are $n$ choices of image, independently. Thus there are $n^n$ functions. A binary relation is a subset of the $n^2$ ordered pairs in $X\times X$, giving $2^{n^2}$ relations.

Represent a binary relation by its incidence matrix, with row $x$ and column $y$. Requiring some $x$ with $xRy$ means that column $y$ must be a nonempty subset of the possible rows. Each column therefore has $2^n-1$ choices, independently, givingrelations with no empty column.

To impose no empty row as well, apply the inclusion-exclusion principle within this already column-nonempty family. Let $A_x$ be the family whose row $x$ is empty. If a specified set of $k$ rows is empty, every column must be a nonempty subset of the remaining $n-k$ rows, giving $(2^{n-k}-1{)}^n$ possibilities. There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways to choose those empty rows. Thus the number with neither an empty row nor an empty column isThis is the binary relations with no empty row or column count. It does not require symmetry or transitivity of the relation. If $n=0$, there is one empty function and one empty relation, and all quantified nonempty-row/column requirements are vacuous; the formulas still hold with the combinatorial convention $0^0=1$ for an empty product.

A binary relation $T$ is transitive exactly when $T\circ T\subseteq T$. If condition (iii) holds, associativity and monotonicity of composition of relations giveHence (iii) implies (ii). Conversely, the inclusions $R,S\subseteq T$ implyIf $T$ is a transitive relation, the right side lies in $T$, which is condition (iii). Thus (ii) and (iii) are equivalent.

An equivalence relation on $A$ is a binary relation that is reflexive, symmetric and transitive: $xRx$ for every $x$; $xRy\Rightarrow yRx$; and $xRy,yRz\Rightarrow xRz$. Write $T=R\circ S$, using the stated order for composition of relations. Composition is associative because both possible bracketings mean that there is a two-step sequence of intermediate witnesses. Reflexivity showsand also that $T$ is reflexive. Transitivity and reflexivity of the original relations give $R\circ R=R$, $S\circ S=S$. Since both original relations are symmetric,The four parts below show that each condition is equivalent to the commuting equivalence relations condition $R\circ S=S\circ R$.

For the integer example, put $d=\gcd (m,n)$. Membership of $(x,z)$ in the composite means that some $y$ satisfies $y-x=ma$, $z-y=nb$ for integers $a,b$. Consequently $z-x=ma+nb$ is divisible by $d$. Conversely, if $z-x$ is divisible by $d$, the Bezout identity expresses it as $ma+nb$; setting $y=x+ma$ provides the required witness. ThusReversing the roles of $m,n$ gives exactly the same modular congruence relation, hence $R\circ S=S\circ R$. This verifies all four conditions and identifies their common smallest equivalence relation explicitly.

A binary relation $T$ is symmetric exactly when $T=T^{-1}$. By the reversed-chain identity, condition (i) therefore gives $R\circ S=S\circ R$, in particular condition (iii). Conversely, if $S\circ R\subseteq R\circ S$, reversing both sides gives $R\circ S\subseteq S\circ R$. Thus condition (iii) gives equality and therefore symmetry. Conditions (i) and (iii) are equivalent.

An equivalence relation on a set $A$ is a binary relation that is reflexive, symmetric and transitive: every element is related to itself, related pairs may be reversed, and two consecutive related pairs imply the pair of endpoints is related.

Write $T=R\circ S$, using the printed left-to-right composition of relations convention. Reflexivity implies $R\subseteq T$ and $S\subseteq T$, and hence $T$ is reflexive. Reversing a two-step chain givessince $R,S$ are symmetric. Also $R\circ R=R$ and $S\circ S=S$: one inclusion is transitivity, and the reverse follows by inserting a reflexive step. These elementary identities supply the equivalences below, without presuming that a composite of equivalence relations is automatically an equivalence relation.