Relations

Relations between elements of sets are very common. For example:

More formally: let $A$ and $B$ be sets. A binary relation from $A$ to $B$ is a subset of $A \times B$.

Therefore, a binary relation $R$ is just a set of ordered pairs. We write $aRb$ to mean $(a,b) \in R$ and $a \cancel{R} b$ to mean $(a,b) \notin R$. When $(a,b) \in R$, we say that "$a$ is related to $b$ by $R$".

Such relations are binary relations because $A \times B$ consists of pairs. In general, we can have relations that are subsets of $A \times B \times C \times \cdots$ to give us an $n$-ary relation. We concentrate on the binary case.

For example, let $A$ be the set of students at Carleton and $B$ be the set of courses at Carleton. Let $R$ be the "enrolled in" relation, so that $(a,b) \in R$ (that is, $aRb$) if student $a$ is enrolled in course $b$.

Note that you can think of all functions as relations (where the input is related to the output), but not vice versa (since a single element can be related to many others).

Sometimes, relations are between a set $A$ and itself: a subset of $A \times A$. In this case, we say the relation is on the set $A$.

Here are some more examples of relations:

Properties of Relations

Relations can have several properties which help to classify them.

Combining Relations

Relations are sets, so they can be combined the same way sets can be combined.

Remember the relations are like functions, so it makes sense to talk about their composition, too.

Let $R$ be a relation from set $A$ to set $B$. Let $S$ be a relation from set $B$ to set $C$. The composition of $R$ and $S$ is the relation consisting of ordered pairs $(a,c)$ where $a \in A$, $c \in C$ and there exists an element $b \in B$ such that $(a,b) \in R$ and $(b,c) \in S$. We write $S \circ R$ to denote this relation.

For example, if we have a relation $R$ from the set $\{1,2,3\}$ to the set $\{1,2,3,4\}$ and a relation $S$ from the set $\{1,2,3,4\}$ to the set $\{0,1,2\}$ defined as follows:

then $S \circ R = \{ (1,0),(1,1),(2,1),(2,2),(3,0),(3,1) \}$.

One special case of composition occurs when you compose a relation with itself. For example, let $R = \{ (a,b) \;|\; a \text{ is a parent of } b \}$ be defined on the set of all people. Then $R \circ R$ is the set of ordered pairs $(a,c)$ such that there exists a person $b$ so that $a$ is a parent of $b$ and $b$ is a parent of $c$, \ie, $a$ is a grandparent of $c$.

Of course, this produces a new relation which can be composed with $R$ again to produce the "is a great-grandparent of" relation.

As a shortcut, we write $R^2 = R \circ R$, $R^3 = (R \circ R) \circ R)$, and so on.

Let $R = \{ (1,1),(2,1),(3,2),(4,3) \}$. Then:

Interestingly, we can understand transitivity in terms of composition: a relation $R$ on a set $A$ is transitive if and only if $R^n \subseteq R$ for $n \ge 1$.

Reflexive Closure

Sometimes a relation does not have some property that we would like it to have: for example, reflexivity, symmetry, or transitivity.

How do we add elements to our relation to guarantee the property? Ideally, we'd like to add as few new elements as possible to preserve the "meaning" of the original relation.

We first consider making a relation reflexive. This is called the reflexive closure. Suppose we have a relation $R$ on a set $A$ and want to make it reflexive. We need to ensure that $(a,a)$ is in the relation for all $a \in A$. We also do not wish to add anything extra.

Define $\Delta = \{ (a,a) \;|\; a \in A \}$. The reflexive closure of $R$ is $R \cup \Delta$.

For example, the reflexive closure of $R = \{ (a,b) \;|\; a \lt b \}$ on the set of integers is the relation

$$R \cup \Delta = \{ (a,b) \;|\; a \lt b \} \cup \{ (a,a) \;|\; a \in \mathbb{Z} \} = \{ (a,b) \;|\; a \le b \}$$

Symmetric Closure

For the symmetric closure, we want to ensure that $(b,a)$ is in the closure relation whenever $(a,b)$ is in the original relation.

Define $R^{-1} = \{ (b,a) \;|\; (a,b) \in R \}$. The symmetric closure of $R$ is $R \cup R^{-1}$.

For example, the symmetric closure of $R = \{ (a,b) \;|\; a \lt b \}$ on the set of integers is the relation

$$R \cup R^{-1} = \{ (a,b) \;|\; a \lt b \} \cup \{ (b,a) \;|\; a \gt b \} = \{ (a,b) \;|\; a \neq b \}$$

Transitive Closure

Consider $R = \{ (1,3),(1,4),(2,1),(3,2) \}$ on $A = \{1,2,3,4\}$. This is not a transitive relation: it is missing $\{(1,2),(2,3),(2,4),(3,1) \}$. Let's try adding them and calling the new relation $R'$:

$$R' = \{ (1,3),(1,4),(2,1),(3,2),(1,2),(2,3),(2,4),(3,1) \}$$

Unfortunately, this relation is still not transitive: $(3,1) \in R'$ and $(1,4) \in R'$, but $(3,4) \notin R'$. It seems we will need to do a bit more work.

Recall that if we compose $R$ with itself, then we get the elements $(a,c)$ where $(a,b) \in R$ and $(b,c) \in R$ for some $b$. We need these elements for transitivity, so add them to $R$. As we saw above, this might not be enough, so we repeat this.

How any times do we repeat? This is the same as asking how many intermediate elements we could find. Since there are $|A|$ possible intermediate elements, we might need to do as many as $|A|$ compositions.

Therefore, the transitive closure of $R$ over a set $A$ is

$$R \cup R^2 \cup R^3 \cup \cdots \cup R^{|A|}$$

Here is an example of computing the transitive closure:

It turns out we can view this another way if we look at the matrix representation. Given a matrix representations $M_R$ and $M_S$ for the relations $R$ and $S$, the matrix representation of $S \circ R$ is $M_R \odot M_S$, where $\odot$ denotes the join operation. This operation is identical to matrix multiplication, but any non-zero entries are simply written as ones.

The matrix representation of $R$ in the previous example is $$ M_R = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \\ \end{bmatrix} $$

Therefore, we have: $$ M_{R^2} = M_R \odot M_R = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \\ \end{bmatrix} $$ and $$ M_{R^3} = M_{R^2} \odot M_R = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \\ \end{bmatrix} $$

We now take the union of these matrices by taking the logical-or of each entry: $$ \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \\ \end{bmatrix} \vee \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \\ \end{bmatrix} \vee \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \\ \end{bmatrix} $$

As we would expect, this is the matrix representation of $\{ (1,1),(1,2),(1,3),(2,2),(3,1),(3,2),(3,3) \}$; the same answer we computed previously.