relation

relation (defined on sets S₁, S₂,… S_n) A subset R of the Cartesian product S₁ × S₂ × … × S_n

of the n sets S₁, …, S_n. This is called an n-ary relation. When a relation R is defined on a single set S the implication is that R is a subset of S × S × … × S (n terms)

The most common situation occurs when n = 2, i.e. R is a subset of S₁ × S₂. Then R is called a binary relation on S₁ to S₂ or between S₁ and S₂. S₁ is the domain of R and S₂ the codomain of R. If the ordered pair (s₁,s₂) belongs to the subset R, a notation such as s₁ R s₂ or s₁ ρ s₂

is usually adopted and it is then possible to talk about the relation R or ρ and to say that s₁ and s₂ are related.

An example of a binary relation is the usual “is less than” relation defined on integers, where the subset R consists of ordered pairs such as (4,5); it is however more natural to write 4 < 5. Other examples include: “is equal to” defined on strings, say; “is the square root of” defined on the nonnegative reals; “is defined in terms of” defined on the set of subroutines within a particular program; “is before in the queue” defined on the set of jobs awaiting execution at a particular time.

The function is a special kind of relation. Graphs are often used to provide a convenient pictorial representation of a relation.

Relations play an important part in theoretical aspects of many areas of computing, including the mathematical foundations of the subject, databases, compiling techniques, and operating systems. See also equivalence relation, partial ordering.