Union If R and S are binary relations over sets X and Y then R \cup S = \{ (x, y) \mid xRy \text{ or } xSy \} is the of R and S over X and Y. The identity element is the empty relation, in which no x is related to any y. For example, \leq is the union of and =, and \geq is the union of > and =.
Intersection If R and S are binary relations over sets X and Y then R \cap S = \{ (x, y) \mid xRy \text{ and } xSy \} is the of R and S over X and Y. The identity element is the universal relation, in which every x is related to every y. For example, the relation "is divisible by 6" is the intersection of the relations "is divisible by 3" and "is divisible by 2".
Composition If R is a binary relation over sets X and Y, and S is a binary relation over sets Y and Z then S \circ R = \{ (x, z) \mid \text{ there exists } y \in Y \text{ such that } xRy \text{ and } ySz \} (also denoted by R; S) is the of R and S over X and Z. If X=Y=Z, the identity element w.r.t. composition is the identity relation on X, in which x \in X is related only to itself. The order of R and S in the notation S \circ R used here agrees with the standard notational order for
composition of functions. For example, the composition (is parent of)\circ(is mother of) yields (is grandmother of), while the composition (is mother of)\circ(is parent of) yields (is maternal grandparent of). For the latter case, if x is the parent of y and y is the mother of z, then x is the maternal grandparent of z.
Converse If R is a binary relation over sets X and Y then R^\textsf{T} = \{ (y, x) \mid xRy \} is the , also called , of R over Y and X. For example, = is the converse of itself, as is \neq, and and > are each other's converse, as are \leq and \geq. A binary relation is equal to its converse if and only if it is
symmetric.
Complement If R is a binary relation over sets X and Y then \bar{R} = \{ (x, y) \mid \neg xRy \} (also denoted by \neg R) is the of R over X and Y. For example, = and \neq are each other's complement, as are \subseteq and \not \subseteq, \supseteq and \not \supseteq, \in and \not \in, and for
total orders also and \geq, and > and \leq. The complement of the
converse relation R^\textsf{T} is the converse of the complement: \overline{R^\mathsf{T}} = \bar{R}^\mathsf{T}. If X = Y, the complement has the following properties: • If a relation is symmetric, then so is the complement. • The complement of a reflexive relation is irreflexive—and vice versa. • The complement of a
strict weak order is a total preorder—and vice versa.
Restriction If R is a binary
homogeneous relation over a set X and S is a subset of X then R_{\vert S} = \{ (x, y) \mid xRy \text{ and } x \in S \text{ and } y \in S \} is the of R to S over X. If R is a binary relation over sets X and Y and if S is a subset of X then R_{\vert S} = \{ (x, y) \mid xRy \text{ and } x \in S \} is the of R to S over X and Y. If a relation is
reflexive, irreflexive,
symmetric,
antisymmetric,
asymmetric,
transitive,
total,
trichotomous, a
partial order,
total order,
strict weak order,
total preorder (weak order), or an
equivalence relation, then so too are its restrictions. However, the transitive closure of a restriction is a subset of the restriction of the transitive closure, i.e., in general not equal. For example, restricting the relation "x is parent of y" to females yields the relation "x is mother of the woman y"; its transitive closure does not relate a woman with her paternal grandmother. On the other hand, the transitive closure of "is parent of" is "is ancestor of"; its restriction to females does relate a woman with her paternal grandmother. Also, the various concepts of
completeness (not to be confused with being "total") do not carry over to restrictions. For example, over the
real numbers a property of the relation \leq is that every
non-empty subset S \subseteq \R with an
upper bound in \R has a
least upper bound (also called supremum) in \R. However, for the rational numbers this supremum is not necessarily rational, so the same property does not hold on the restriction of the relation \leq to the rational numbers. A binary relation R over sets X and Y is said to be a relation S over X and Y, written R \subseteq S, if R is a subset of S, that is, for all x \in X and y \in Y, if xRy, then xSy. If R is contained in S and S is contained in R, then R and S are called written R = S. If R is contained in S but S is not contained in R, then R is said to be than S, written R \subsetneq S. For example, on the
rational numbers, the relation > is smaller than \geq, and equal to the composition > \circ >.
Matrix representation Binary relations over sets X and Y can be represented algebraically by
logical matrices indexed by X and Y with entries in the
Boolean semiring (addition corresponds to OR and multiplication to AND) where
matrix addition corresponds to union of relations,
matrix multiplication corresponds to composition of relations (of a relation over X and Y and a relation over Y and Z), the
Hadamard product corresponds to intersection of relations, the
zero matrix corresponds to the empty relation, and the
matrix of ones corresponds to the universal relation. Homogeneous relations (when X = Y) form a
matrix semiring (indeed, a
matrix semialgebra over the Boolean semiring) where the
identity matrix corresponds to the identity relation. == Examples ==