Suppose that \(S\) and \(T\) are sets. A relation from \(S\) to \(T\) is a subset of the product set \(S \times T\). As the name suggests, a relation \(R\) from \(S\) into \(T\) is supposed to define a relationship between the elements of \(S\) and the elements of \(T\), and so we usually use the more suggestive notation \(x\,R\,y\) when \((x, y) \in R\). The domain of \(R\) is the set of first coordinates and the range of \(R\) is the set of second coordinates.
\[ \begin{align} \text{domain}(R) & = \{x \in S: (x, y) \in R \text{ for some } y \in T\} \\ \text{range}(R) & = \{y \in T: (x, y) \in R \text{ for some } x \in S\} \end{align} \]A relation from a set \(S\) to itself is said to be a relation on \(S\).
Suppose that \(S\) is a set and recall that \(\mathscr{P}(S)\) denotes the power set of \(S\), the collection of all subsets of \(S\). The membership relation \(\in\) from \(S\) to \(\mathscr{P}(S)\) is perhaps the most important and basic relationship in mathematics. Indeed, for us, it's a primitive (undefined) relationship--given \(x\) and \(A\), we assume that we understand the meaning of the statement \(x \in A\).
Another basic primitive relation is the equality relation \(=\) on a given set of objects \(S\). That is, given two objects \(x\) and \(y\), we assume that we understand the meaning of the statement \(x = y\).
Other basic relations that you have seen are
Note that a function \(f\) from \(S\) into \(T\) is a special type of relation. To compare the two types of notation (relation and function), note that \(x\,f\,y\) means that \(y = f(x)\).
Since a relation is just a set of ordered pairs, the set operations can be used to build new relations from existing ones. Specifically, if \(Q\) and \(R\) are relations from \(S\) to \(T\), then so are \(Q \cup R\), \(Q \cap R\), \(Q \setminus R\). If \(R\) is a relation from \(S\) to \(T\) and \(Q \subseteq R\), then \(Q\) is a relation from \(S\) to \(T\).
Suppose that \(Q\) and \(R\) are relations from \(S\) to \(T\).
If \(R\) is a relation on \(S\) and \(A \subseteq S\) then \(R_A = R \cap (A \times A)\) is a relation on \(A\), called the restriction of \(R\) to \(A\).
If \(R\) is a relation from \(S\) to \(T\), the inverse of \(R\) is the relation from \(T\) to \(S\) defined by
\[ y\,R^{-1}\,x \text{ if and only if } x\,R\,y \]Equivalently, \(R^{-1} = \{(y, x): (x, y) \in R\}\). Note that any function \(f\) from \(S\) into \(T\) has an inverse relation, but only when the \(f\) is one-to-one is the inverse relation also a function (the inverse function).
Suppose that \(Q\) is a relation from \(S\) to \(T\) and that \(R\) is a relation from \(T\) to \(U\). The composition \(Q \circ R\) is the relation from \(S\) to \(U\) defined as follows: for \(x \in S\) and \(z \in U\), \(x(Q \circ R)z\) if and only if there exists \(y \in T\) such that \(x\,Q\,y\) and \(y\,R\,z\). Note that the notation is inconsistent with the notation used for composition of functions, essentially because relations are read from left to right, while functions are read from right to left. Hopefully, the inconsistency will not cause confusion, since we will always use function notation for functions.
The important classes of relations that we will study in the next couple of sections are characterized by certain basic properties. Suppose that \(R\) is a relation on \(S\).
A relation \(R\) on \(S\) is reflexive if and only if the equality relation \(=\) on \(S\) is a subset of \(R\).
A relation \(R\) on \(S\) is symmetric if and only if \(R^{-1} = R\).
A relation \(R\) on \(S\) is transitive if and only if \(R \circ R \subseteq R\).
A relation \(R\) on \(S\) is antisymmetric if and only if \(R \cap R^{-1}\) is a subset of the equality relation \(=\) on \(S\).
Suppose that \(Q\) and \(R\) are relations on \(S\). For each property below, if both \(Q\) and \(R\) have the property, then so does \(Q \cap R\).
Suppose that \(R\) is a relation on a set \(S\).
Suppose that \(R\) is a relation on a set \(S\).
Let \(R\) be the relation defined on \(\R\) by \(x\,R\,y\) if and only if \(\sin(x) = \sin(y)\). Determine if \(R\) has each of the following properties:
The relation \(R\) in the previous exercise is a member of an important class of equivalence relations.
Let \(R\) be the relation defined on \(\R\) by \(x\,R\,y\) if and only if \(x^2 + y^2 \le 1\). Determine if \(R\) has each of the following properties: