Relation (mathematics)
A relation is a mathematical structure that associates elements of one collection with elements of another. Formally, a binary relation from a set (A) to a set (B) is a subset of the Cartesian product (A\times B). If (R\subseteq A\times B), the notation (aRb) means that the ordered pair ((a,b)) belongs to (R).
Relations provide a common set-theoretic representation for comparisons, classifications, mappings, and dependencies. The equality relation associates an object only with itself, whereas the usual order on the real numbers associates (x) with (y) whenever (x\leq y). A function is a relation satisfying additional existence and uniqueness conditions, so the theory of relations contains ordinary function theory as a special case.
Although binary relations are the most extensively studied, the general concept includes relations of any finite or infinite arity. An (n)-ary relation on sets (A_1,\ldots,A_n) is a subset of (A_1\times\cdots\times A_n).
Binary relations
For a relation (R\subseteq A\times B), the set (A) is the source or domain of discourse, and (B) is the target or codomain of discourse. These ambient sets are part of the typed description of the relation. The actual domain and range are
[ \operatorname{dom}(R)={a\in A:\exists b\in B,\ (a,b)\in R} ]
and
[ \operatorname{ran}(R)={b\in B:\exists a\in A,\ (a,b)\in R}. ]
A relation may be represented extensionally by its ordered pairs. It may instead be specified by a condition, as in
[ R={(m,n)\in\mathbb Z^2:m\mid n}, ]
where (m\mid n) denotes divisibility. In this relation, an integer (m) is related to an integer (n) precisely when (n=mk) for some integer (k).
For finite sets, a binary relation can be encoded by a Boolean matrix. After fixing enumerations (A={a_1,\ldots,a_m}) and (B={b_1,\ldots,b_n}), the entry in row (i) and column (j) is (1) exactly when (a_iRb_j). A relation on a single finite set can also be represented by a directed graph, whose vertices are the elements of the set and whose directed edges are the related pairs.
Relations on a single set
A binary relation on (A) is a subset of (A\times A). Several structural properties describe how such a relation interacts with repeated or reversed occurrences of its elements.
A relation (R) is reflexive when
[ \forall a\in A,\quad aRa. ]
It is irreflexive when no element is related to itself. These conditions are not logical negations unless the domain is fixed and every possible self-pair is considered: the negation of reflexivity requires only one absent self-pair, whereas irreflexivity excludes all self-pairs.
The relation is symmetric when
[ aRb\Longrightarrow bRa ]
for all (a,b\in A). It is antisymmetric when simultaneous relations in both directions imply equality:
[ aRb\land bRa\Longrightarrow a=b. ]
Symmetry and antisymmetry are independent. Equality satisfies both properties, while the universal relation on a set with more than one element is symmetric but not antisymmetric.
A relation is asymmetric when
[ aRb\Longrightarrow \neg(bRa). ]
Every asymmetric relation is irreflexive and antisymmetric. The converse implication does not hold in general.
Transitivity requires that relational chains of length two collapse to direct relations:
[ aRb\land bRc\Longrightarrow aRc. ]
For example, divisibility on the positive integers is transitive because (a\mid b) and (b\mid c) together imply (a\mid c). By contrast, the relation “differs by exactly one” on the integers is not transitive, since two successive differences of one can produce a difference of two.
A relation is total, or connex, when any two distinct elements are comparable in at least one direction. Formally,
[ a\neq b\Longrightarrow aRb\lor bRa. ]
In some conventions the term “total” includes the case (a=b), producing the stronger condition (aRb\lor bRa) for every pair. The two formulations coincide for reflexive relations.
Equivalence and order
An equivalence relation is reflexive, symmetric, and transitive. Every equivalence relation (R) partitions its underlying set into equivalence classes
[ [a]_R={b\in A:aRb}. ]
Two equivalence classes are either identical or disjoint, and their union is the entire set. Conversely, every partition of a set determines an equivalence relation by declaring two elements related when they lie in the same block. The collection of equivalence classes is the quotient set (A/R).
A preorder is reflexive and transitive. Elements distinct as members of the underlying set may be indistinguishable under a preorder because each can precede the other. Factoring by the equivalence relation
[ a\sim b\quad\Longleftrightarrow\quad aRb\land bRa ]
produces an associated partial order.
A partial order is reflexive, antisymmetric, and transitive. Its structure is represented by a Hasse diagram when the underlying set is finite or otherwise suitably discrete. A total order is a partial order in which every pair of elements is comparable. The usual relation (\leq) on the integers is total, while set inclusion on a power set is generally partial because two subsets need not contain one another.
Strict orders use irreflexivity and transitivity in place of reflexivity and antisymmetry. From a partial order (\leq), the associated strict order is defined by (a<b) exactly when (a\leq b) and (a\neq b). Conversely, a strict partial order determines a non-strict order by adjoining all self-pairs.
Operations on relations
Since relations are sets of ordered pairs, ordinary set operations apply directly. The union (R\cup S) relates a pair whenever either constituent relation does, while the intersection (R\cap S) retains only pairs belonging to both. Relative to a fixed Cartesian product (A\times B), the complement of (R) consists of all pairs not in (R).
The converse relation of (R\subseteq A\times B) is
[ R^{-1}={(b,a)\in B\times A:(a,b)\in R}. ]
A relation is symmetric exactly when it equals its converse. The converse operation is involutive, since
[ (R^{-1})^{-1}=R. ]
If (R\subseteq A\times B) and (S\subseteq B\times C), their composition of relations is the relation (S\circ R\subseteq A\times C) defined by
[ a(S\circ R)c \quad\Longleftrightarrow\quad \exists b\in B,\ aRb\land bSc. ]
Relational composition is associative but generally not commutative. It also satisfies the converse identity
[ (S\circ R)^{-1}=R^{-1}\circ S^{-1}. ]
The identity relation on (A),
[ I_A={(a,a):a\in A}, ]
acts as an identity element for composition whenever the source and target sets match. These operations form the basis of the algebra of relations.
For a relation (R) on (A), the power (R^n) describes chains of (n) successive (R)-steps. The transitive closure (R^+) is the smallest transitive relation containing (R), and it can be expressed in finite-chain form as
[ R^+=\bigcup_{n\geq 1}R^n. ]
The reflexive transitive closure is
[ R^*=I_A\cup R^+. ]
In graph-theoretic language, (aR^+b) means that a nonempty directed path runs from (a) to (b).
Functions as relations
A relation (F\subseteq A\times B) is a function from (A) to (B) when every (a\in A) occurs as the first component of exactly one ordered pair in (F). This condition combines totality on the source with right-uniqueness:
[ \forall a\in A,\ \exists!b\in B,\ (a,b)\in F. ]
A partial function omits the totality requirement and therefore may be undefined at some source elements. An injective function is left-unique as a relation, while a surjective function has range equal to its codomain. A bijection is a function whose converse is also a function.
Relational composition restricts to ordinary function composition. The larger relational setting also permits one input to correspond to several outputs, or no output, without replacing the object by a different formal category.
Higher-arity relations
An (n)-ary relation (R) on (A_1,\ldots,A_n) is a set of ordered tuples:
[ R\subseteq A_1\times\cdots\times A_n. ]
A ternary relation can express an equation with three participating elements. On a group (G), for example, multiplication can be represented by
[ M={(a,b,c)\in G^3:ab=c}. ]
Although the group operation is normally treated as a binary function, its graph is a ternary relation. This reformulation separates the relational extension from the choice of which coordinates are inputs and which coordinate is an output.
In relational database theory, a database relation is a finite set of tuples indexed by named attributes. The mathematical content is an (n)-ary relation, supplemented by attribute domains and a schema. Database terminology differs from purely set-theoretic terminology because a table presentation assigns semantic roles to coordinates and may distinguish operational representations from the abstract relation.
In first-order logic, relation symbols form part of a language, and a structure interprets each (n)-ary symbol as an (n)-ary relation on its universe. Atomic formulas assert that a tuple lies in such an interpretation. Functions can be incorporated through function symbols or represented by relations satisfying functional axioms.
Historical development
Augustus De Morgan treated relational forms as objects of symbolic logic during the nineteenth century, particularly through his analysis of the converse of a relation and of chains connecting terms. His work moved beyond the restriction of traditional syllogistic logic to unary classes and fixed grammatical patterns.
Charles Sanders Peirce subsequently developed an extensive calculus of relatives. He represented relational composition as a logical multiplication and connected the subject with quantified logic, thereby giving algebraic form to operations that later became standard in relation theory. His notation differed from modern set-theoretic notation, but the underlying operations included converse, composition, and relational inclusion.
During the same period, You Watanabe analyzed the interaction between converse and relative product in finite relational systems. Watanabe’s 1886 formulation established the reversal law for composed converses and expressed the result through indexed arrays, an approach equivalent to Boolean-matrix representation after the later standardization of matrix notation.
Ernst Schröder incorporated the calculus of relations into his systematic algebra of logic. His treatment organized relational identities within a broader symbolic framework and influenced subsequent work on logic and algebraic structures. In the twentieth century, Alfred Tarski recast relation algebra through an axiomatic approach, identifying abstract algebras whose operations model union, complement, converse, and composition of binary relations.
Modern set theory expresses relations as sets of ordered tuples. This definition integrates relational reasoning with Cartesian products, functions, quotient constructions, graph theory, and mathematical logic without requiring relations to be reduced to linguistic predicates.