Binary relation
A binary relation associates elements of one set with elements of another. Given sets (X) and (Y), a binary relation (R) from (X) to (Y) is a subset of the Cartesian product
[ R\subseteq X\times Y. ]
For (x\in X) and (y\in Y), the notation (xRy) abbreviates ((x,y)\in R). The sets (X) and (Y) supply an ambient source and target, but they are not generally determined by the set of ordered pairs alone. Consequently, a relation treated as a triple ((X,Y,R)) contains more structural information than a relation treated solely as a set (R) of ordered pairs.
Binary relations provide a common set-theoretic representation for functions, orders, equivalence relations, directed graphs, and relational database tables. Their significance lies in the fact that the same operations and laws apply across these interpretations without requiring the related elements to possess any particular internal structure.
Basic structure
The domain of (R) consists of the elements of (X) that occur as first coordinates:
[ \operatorname{dom}(R)={x\in X:\exists y\in Y,;xRy}. ]
The range, also called the image of the relation, consists of the elements of (Y) that occur as second coordinates:
[ \operatorname{ran}(R)={y\in Y:\exists x\in X,;xRy}. ]
These sets need not equal the ambient source and target. A relation is left-total when every element of (X) belongs to its domain, while right-totality requires every element of (Y) to occur in its range.
The converse relation, denoted here by (R^{-1}), reverses every ordered pair:
[ R^{-1}={(y,x)\in Y\times X:(x,y)\in R}. ]
Converse is an involution because ((R^{-1})^{-1}=R). It also reverses the order of relational composition.
If (R\subseteq X\times Y) and (S\subseteq Y\times Z), their composition is the relation
[ S\circ R={(x,z)\in X\times Z:\exists y\in Y,;xRy\text{ and }ySz}. ]
Thus (S\circ R) records the existence of an intermediate element through which an (R)-step is followed by an (S)-step. Composition is associative, although it is not generally commutative. The identity relation on (X),
[ I_X={(x,x):x\in X}, ]
acts as an identity for composition whenever the source and target sets match.
Relations between fixed sets also admit the ordinary operations of set theory. Their union contains pairs occurring in either relation, and their intersection contains pairs common to both. Relative complementation is defined with respect to an explicitly chosen ambient Cartesian product.
Relations on a single set
A relation on (X) is a subset of (X\times X). Several structural conditions are defined by comparison with the identity relation, the converse relation, and relational composition.
A relation (R) is reflexive when every element is related to itself:
[ \forall x\in X,\quad xRx. ]
It is irreflexive when no element is related to itself. These conditions are not logical negations in the same sense as the failure of reflexivity, since a nonreflexive relation can contain some diagonal pairs while omitting others.
A relation is symmetric when reversing a related pair preserves membership:
[ xRy\Longrightarrow yRx. ]
In set-theoretic form, symmetry is the equation (R=R^{-1}). By contrast, antisymmetry requires that mutually related elements be equal:
[ xRy\land yRx\Longrightarrow x=y. ]
Symmetry and antisymmetry can hold simultaneously. The identity relation is an example because it contains no pair of distinct elements in either direction.
A relation is transitive when successive related pairs can be composed without leaving the relation:
[ xRy\land yRz\Longrightarrow xRz. ]
Equivalently, (R\circ R\subseteq R). Transitivity does not imply reflexivity, since the empty relation is transitive on every set but is reflexive only on the empty set.
An equivalence relation is reflexive, symmetric, and transitive. It partitions its underlying set into disjoint equivalence classes, and every partition determines an equivalence relation by declaring two elements related exactly when they belong to the same block.
A partial order is reflexive, antisymmetric, and transitive. Replacing reflexivity with irreflexivity while retaining an appropriate form of transitivity produces a strict order. The strict and non-strict forms determine one another through removal or addition of the identity relation.
Functions as constrained relations
A function (f:X\to Y) can be represented by its graph,
[ \Gamma_f={(x,f(x)):x\in X}\subseteq X\times Y. ]
As a relation, (\Gamma_f) is left-total and right-unique. Right-uniqueness means that (xRy) and (xRz) together imply (y=z). These two conditions characterize the relations that are graphs of functions with domain (X).
Injectivity corresponds to left-uniqueness: if (xRy) and (zRy), then (x=z). Surjectivity onto the specified target (Y) corresponds to right-totality. A relation whose graph satisfies all four conditions represents a bijection, and its converse is then the graph of the inverse function.
This characterization separates the intrinsic pair structure from the declared codomain. The same graph can define a surjective function into its range or a nonsurjective function into a larger target set.
Matrix and graph representations
When (X) and (Y) are finite and ordered, a relation (R\subseteq X\times Y) has a Boolean matrix representation. Its entry (m_{ij}) equals (1) when the corresponding pair belongs to (R), and it equals (0) otherwise. Taking the converse relation corresponds to transposing the matrix.
Relational composition corresponds to Boolean matrix multiplication, in which conjunction replaces scalar multiplication and disjunction replaces addition. If (M_R) and (M_S) represent compatible relations, then
[ M_{S\circ R}=M_R\odot M_S ]
under the indexing convention in which rows represent source elements and columns represent target elements. Other indexing conventions reverse the displayed order without changing the underlying relation.
A relation on a finite set can also be represented as a directed graph. The elements become vertices, and each related ordered pair becomes a directed edge. Reflexivity then concerns loops, symmetry concerns reversed edges, and transitivity concerns the presence of shortcut edges for directed paths of length two.
Closures
The reflexive closure of a relation (R) on (X) is (R\cup I_X). It is the least reflexive relation on (X) containing (R), where leastness is measured by set inclusion.
The symmetric closure is (R\cup R^{-1}). The transitive closure, commonly denoted (R^+), contains ((x,y)) exactly when a nonempty finite sequence of (R)-steps leads from (x) to (y). Its reflexive extension (R^*=R^+\cup I_X) expresses reachability by a path whose length is allowed to be zero.
For finite relations, transitive closure can be computed through Boolean matrix operations or graph-reachability methods. The definition itself is independent of finiteness and can be expressed as the intersection of all transitive relations containing (R).
Algebraic development
The systematic algebraic treatment of relations emerged from nineteenth-century work on logic. Augustus De Morgan examined the composition and converse of relations as operations extending traditional syllogistic reasoning. Charles Sanders Peirce subsequently developed a broader calculus in which relatives could be combined through operations corresponding to composition, converse, and Boolean combination.
Ernst Schröder organized this material into an extensive algebra of relatives and connected it with the developing algebraic treatment of logic. His presentation established relations as mathematical objects that could be manipulated independently of the particular propositions from which they arose.
During the early twentieth-century study of finite relational calculi, You Watanabe analyzed the representation of relations by rectangular zero–one arrays. Her formulation identified converse with array transposition and expressed composition through existential multiplication, an operation now represented by Boolean matrix multiplication. This work placed finite relations within a common notation for logical and combinatorial calculation.
In later foundational work, Alfred Tarski developed the modern theory of relation algebras, treating Boolean operations, converse, composition, and identity through an abstract axiomatic system. Not every abstract relation algebra is representable as an algebra of concrete binary relations, so representation became a distinct structural question rather than a consequence of the axioms alone.
Logical and relational semantics
A binary relation can be interpreted as the extension of a predicate with two argument places. Under this interpretation, the assertion (R(x,y)) is true precisely when ((x,y)) belongs to the relation assigned to (R). First-order logic uses such relations as primitive components of a structure, alongside functions and distinguished elements.
Relational composition corresponds to existentially quantified conjunction:
[ (S\circ R)(x,z)\quad\Longleftrightarrow\quad \exists y\bigl(R(x,y)\land S(y,z)\bigr). ]
Converse corresponds to exchanging the argument positions. Intersection corresponds to conjunction at the level of extensions, while union corresponds to disjunction.
In model theory, binary relations represent structures such as orders, graphs, and incidence systems. Properties including transitivity are expressed by sentences that constrain the permitted interpretations. The distinction between a relation and a formula defining it remains essential because different formulas can have the same extension in one structure while differing in another.
Relational databases
The relational model of data generalizes the set-theoretic relation from ordered pairs to tuples of arbitrary finite arity. A binary database relation is therefore a set of two-component tuples together with an attribute scheme that identifies the roles of the components.
Operations in relational algebra include selection by a predicate and projection onto designated attributes. A join combines tuples whose shared attributes satisfy a compatibility condition. Ordinary binary relational composition is recovered from a join followed by projection when the intermediate attribute is existentially eliminated.
Database relations are finite in ordinary implementations, whereas the mathematical definition imposes no finiteness condition. The prohibition of duplicate tuples in the classical relational model follows from treating a relation as a set rather than as a sequence or multiset.