Binary Relation · aiwiki.page

A binary relation in mathematics specifies a connection between two elements at a time. In set theory, a relation from a set $A$ to a set $B$ is a subset $R\subseteq A\times B$ of their Cartesian product. The notation $aRb$ means that $(a,b)\in R$ . Equality, numerical inequalities, and functions can all be described within this framework. “Binary” refers to the number of positions in each related tuple, not to binary numerals. (ocw.mit.edu)

Definition and notation

The constituents of a relation are ordered pairs: the first and second positions have distinct roles. A relation on $A$ is a subset of $A\times A$ , whereas a relation between different sets need not connect objects of the same kind. For example, a relation between students and courses can record enrollment, allowing one student to be related to several courses. This illustrates that a relation need not assign a unique output. (ocw.mit.edu)

A function $f:A\to B$ is a special relation in which every element of $A$ is paired with exactly one element of $B$ . A general relation may pair an element with no elements, one element, or several elements. The set-theoretic graph of a function is

\{(a,f(a)):a\in A\}.

Thus the definition of a relation is less restrictive than that of a function. (cs.cornell.edu)

For specified sets $A,B$ , all relations between them constitute the power set $\mathcal P(A\times B)$ . Consequently, if $A$ and $B$ have $m$ and $n$ elements, there are $2^{mn}$ possible relations: each possible pair is either included or excluded. (ocw.mit.edu)

Properties of relations on a set

Several properties classify a relation $R\subseteq A\times A$ :

Reflexive: $aRa$ for every $a\in A$ .
Irreflexive: $aRa$ holds for no $a\in A$ .
Symmetric: $aRb$ implies $bRa$ .
Antisymmetric: $aRb$ and $bRa$ together imply $a=b$ .
Asymmetric: $aRb$ implies that $bRa$ does not hold.
Transitive: $aRb$ and $bRc$ imply $aRc$ . (cs.cornell.edu)

Antisymmetry is not the negation of symmetry: it forbids reciprocal connections only between distinct elements. Asymmetry additionally forbids self-connections. For example, $\leq$ is reflexive, antisymmetric, and transitive, while $<$ is irreflexive, asymmetric, and transitive. Equality is both symmetric and antisymmetric. (cs.cornell.edu)

These conditions are universally quantified, so missing pairs do not necessarily violate them. The empty relation is symmetric and transitive because their premises never occur. On a nonempty underlying set it is not reflexive; on the empty set, reflexivity also holds vacuously. (cs.cornell.edu)

Equivalence and order

An equivalence relation is reflexive, symmetric, and transitive. It expresses sameness with respect to a selected criterion rather than necessarily literal identity. Each element $a$ determines an equivalence class

[a]_R=\{b\in A:aRb\}.

The distinct classes form a partition of $A$ : each element belongs to exactly one class. Their collection is the quotient set $A/R$ . (cs.cornell.edu)

For example, on the integers, having the same remainder upon division by a fixed positive integer is an equivalence relation. This provides the classes used in modular arithmetic. (cs.cornell.edu)

A preorder is reflexive and transitive. A partial order additionally satisfies antisymmetry. It is a total order if every two elements are comparable: $aRb$ or $bRa$ . Partial orders permit incomparable elements, as illustrated by set inclusion. A strict partial order is irreflexive and transitive. (cs.cornell.edu)

Operations on relations

Because relations are sets, relations with the same underlying product admit union, intersection, difference, and complement relative to that product. Union records pairs belonging to either relation; intersection records pairs belonging to both. The converse reverses every pair:

R^{-1}=\{(b,a):(a,b)\in R\}.

This notation does not imply that $R$ is an invertible function. (cs.cornell.edu)

For $R\subseteq A\times B$ and $S\subseteq B\times C$ , relational composition connects elements through an intermediate element:

S\circ R=\{(a,c):\exists b\in B,\ aRb\text{ and }bSc\}.

Here $R$ is applied first, following the convention for function composition; some texts use the opposite ordering. Composition is associative but generally not commutative. The identity relation $I_A=\{(a,a):a\in A\}$ supplies the appropriate identity for composition. (cs.cornell.edu)

Graphs, closure, and computation

A relation on $A$ can be represented by a directed graph, with vertices for elements and an arrow $a\to b$ for each pair $(a,b)$ . Reflexivity requires a loop at every vertex; symmetry requires a reverse arrow for every arrow; transitivity requires a direct connection whenever two consecutive arrows connect the same endpoints. (cs.cornell.edu)

The transitive closure $R^+$ adds precisely the pairs connected by one or more relational steps. The reflexive-transitive closure $R^*$ also permits zero steps:

R^+=\bigcup_{n\geq1}R^n,\qquad R^*=\bigcup_{n\geq0}R^n,\qquad R^0=I_A.

These are the smallest transitive, and reflexive-transitive, relations containing $R$ , respectively. (cs.cornell.edu)

In formal verification, a program can be interpreted as a relation between initial and final states. Composition models sequential execution, while reflexive-transitive closure models arbitrarily many repetitions, including none. This interpretation accommodates computations with multiple possible outcomes rather than only deterministic functions. (cs.cornell.edu)