Relations

From Ordered Pairs to Relations

The previous tutorial, “Ordered Pairs,” established that \((x,y)=(u,v)\) exactly when \(x=u\) and \(y=v\). This coordinatewise equality makes ordered pairs useful for recording associations: the first coordinate can have one role and the second coordinate another. A relation collects selected pairs, specifying which first-coordinate objects are related to which second-coordinate objects.

For example, a set of pairs might record which students are enrolled in which courses. A pair \((s,c)\) belongs to the relation when student \(s\) is enrolled in course \(c\). The relation does not have to associate every student with a course, and one student may be associated with more than one course. Relations are therefore more general than functions, which will be studied later.

Definition (Relation from One Set to Another). Let \(A\) and \(B\) be sets. A relation from \(A\) to \(B\) is a subset \(R\) of the Cartesian product \(A\times B\): $$ R\subseteq A\times B. $$ Thus every element of \(R\) is an ordered pair \((x,y)\) with \(x\in A\) and \(y\in B\). A relation on \(A\) is a relation from \(A\) to itself, so it is a subset of \(A\times A\).

Because a relation is a set, the membership notation is already available. If \((x,y)\in R\), we say that \(x\) is related to \(y\) by \(R\), and may write \(xRy\). This is a notation for the statement \((x,y)\in R\); the symbol between \(x\) and \(y\) is chosen to name the relation.

Reading and Describing a Relation

There are two equivalent ways to describe a relation. We can list its ordered pairs, or we can give a condition that determines which pairs belong to it. For instance, on a set of numbers, the condition \(x<y\) defines a relation by selecting every pair for which the inequality holds. In either description, coordinate positions matter: membership of \((x,y)\) says something about \(x\) in the first position and \(y\) in the second.

When the relation is defined by a condition \(P(x,y)\), its set-builder description can be written $$ R=\{(x,y)\in A\times B:P(x,y)\}. $$ The domain \(A\) and codomain \(B\) specify where the coordinates are drawn from. The relation itself selects which of those possible pairs are included.

Domain and Range

The domain of a relation consists of the objects that actually appear as first coordinates. The range consists of the objects that actually appear as second coordinates. These are sets determined by the relation; they need not equal the sets \(A\) and \(B\) from which the pairs were drawn.

Definition (Domain and Range of a Relation). If \(R\) is a relation from \(A\) to \(B\), define $$ \operatorname{dom}(R)=\{x\in A:\text{there exists }y\in B\text{ such that }(x,y)\in R\} $$ and $$ \operatorname{ran}(R)=\{y\in B:\text{there exists }x\in A\text{ such that }(x,y)\in R\}. $$ The word “exists” matters: an element belongs to the domain if it occurs in at least one pair as a first coordinate, and belongs to the range if it occurs in at least one pair as a second coordinate.

For an empty relation \(R=\varnothing\), there are no first or second coordinates appearing in its pairs. Accordingly, \(\operatorname{dom}(R)=\varnothing\) and \(\operatorname{ran}(R)=\varnothing\), regardless of the sets \(A\) and \(B\) from which its possible pairs would have been drawn.

Inverting a Relation

The inverse relation reverses every pair. If \(R\) relates \(x\) to \(y\), its inverse relates \(y\) to \(x\). Reversal changes the positions of the coordinates, so the ordered-pair equality result from “Ordered Pairs” helps keep the definition precise.

Definition (Inverse Relation). If \(R\) is a relation from \(A\) to \(B\), its inverse is the relation from \(B\) to \(A\) defined by $$ R^{-1}=\{(y,x)\in B\times A:(x,y)\in R\}. $$ Equivalently, \(yR^{-1}x\) if and only if \(xRy\). The inverse reverses each pair; it does not replace a relation with a numerical reciprocal.

The operation of taking an inverse has two immediate structural consequences: it swaps domain and range, and taking the inverse twice returns to the original relation. We prove both from the definitions.

Theorem (Domain and Range of the Inverse). If \(R\) is a relation from \(A\) to \(B\), then $$ \operatorname{dom}(R^{-1})=\operatorname{ran}(R) \qquad\text{and}\qquad \operatorname{ran}(R^{-1})=\operatorname{dom}(R). $$

Proof. Let \(y\) be any object. By the definition of domain, $$ y\in\operatorname{dom}(R^{-1}) \quad\Longleftrightarrow\quad \text{there exists }x\in A\text{ such that }(y,x)\in R^{-1}. $$ By the definition of the inverse, \((y,x)\in R^{-1}\) exactly when \((x,y)\in R\). Therefore $$ y\in\operatorname{dom}(R^{-1}) \quad\Longleftrightarrow\quad \text{there exists }x\in A\text{ such that }(x,y)\in R, $$ which is the definition of \(y\in\operatorname{ran}(R)\). This proves equality of the domains in the first assertion, by equality of condition-defined sets. For the other assertion, for any \(x\in A\), $$ x\in\operatorname{ran}(R^{-1}) \quad\Longleftrightarrow\quad \text{there exists }y\in B\text{ such that }(y,x)\in R^{-1} \quad\Longleftrightarrow\quad \text{there exists }y\in B\text{ such that }(x,y)\in R. $$ The last condition is exactly \(x\in\operatorname{dom}(R)\). Thus the range of \(R^{-1}\) is the domain of \(R\). \(\square\)

Proposition (Taking the Inverse Twice). For every relation \(R\), $$ (R^{-1})^{-1}=R. $$ Proof. Let \(x\) and \(y\) be arbitrary objects. From the definition of inverse, $$ (x,y)\in (R^{-1})^{-1} \quad\Longleftrightarrow\quad (y,x)\in R^{-1} \quad\Longleftrightarrow\quad (x,y)\in R. $$ Thus the two sets contain exactly the same ordered pairs. By the characterization of equality of condition-defined sets, \((R^{-1})^{-1}=R\). \(\square\)

Comparing Relations and Recognizing Common Properties

Relations are sets, so the definitions of subset and set equality apply directly. In particular, \(R\subseteq S\) means that every ordered pair in \(R\) is also in \(S\). In the notation for related objects, this says that whenever \(xRy\), we also have \(xSy\). Equality is stronger: the relations must contain exactly the same ordered pairs.

Theorem (Inclusion of Relations by Pair Membership). Let \(R\) and \(S\) be relations from \(A\) to \(B\). Then $$ R\subseteq S \quad\Longleftrightarrow\quad \text{for all }x\in A\text{ and }y\in B,\ \bigl((x,y)\in R\Longrightarrow(x,y)\in S\bigr). $$ Proof. First suppose \(R\subseteq S\). Let \(x\in A\) and \(y\in B\), and suppose \((x,y)\in R\). By the definition of subset inclusion, every element of \(R\) belongs to \(S\), so \((x,y)\in S\). This proves the stated implication for all such \(x,y\). Conversely, suppose the stated implication holds. To prove \(R\subseteq S\), let \(z\in R\). Since \(R\subseteq A\times B\), there are \(x\in A\) and \(y\in B\) such that \(z=(x,y)\). The assumed implication gives \((x,y)\in S\), so \(z\in S\). Every element of \(R\) therefore belongs to \(S\), and \(R\subseteq S\). \(\square\)

A relation on one set can also be described by properties of the pairs it contains. A relation \(R\) on \(A\) is reflexive if \((x,x)\in R\) for every \(x\in A\); it is symmetric if \((x,y)\in R\) implies \((y,x)\in R\) for all \(x,y\in A\); and it is transitive if \((x,y)\in R\) and \((y,z)\in R\) together imply \((x,z)\in R\), for all \(x,y,z\in A\). Each property is a condition to check against every relevant element or pair, not just the pairs that happen to be listed first in an example.

For the relation \(R=\{(1,2),(1,3),(2,3)\}\) on \(\{1,2,3\}\), reflexivity fails because none of \((1,1),(2,2),(3,3)\) belongs to \(R\). Symmetry fails because \((1,2)\in R\) but \((2,1)\notin R\). Transitivity does hold: the only possible two-step chain in these pairs is \((1,2)\) followed by \((2,3)\), and the required pair \((1,3)\) is present. A property may hold or fail independently of the others.