8.3 Relations

Now we have more examples to play with, we return to thinking about “sameness" more formally. But in order to conclude whether two objects are the same, we need a criteria against which they are being compared.

Definition 8.16 (Relation).

A relation $R$ on the set $X$ is a subset of the product set $X\times X$ . If $a,b\in X$ such that $(a,b)\in R$ then we write $aRb$ and we say “ $a$ is related to $b$ under $R$ ”.

Even though the relation itself is a set, for some common relations, we may use a particular symbol in place of the set name to indicate when one element is related to another. One example of this is the strict inequality.

Example 8.17.

The strict inequality $<$ is an example of a relation on $\mathbb{R}$ , defined by the set

S=\{(a,b)\in\mathbb{R}\times\mathbb{R}:b=a+\varepsilon\text{ for some positive% real number $\varepsilon$}\}.

For example, $(1,2)\in S$ (so $1<2$ ) but $(-2,-2)\notin S$ (so $-2<-2$ ). In particular, we say that $-2$ is incomparable to itself under the relation $<$ .

The relation “ $=$ ” on $\mathbb{R}$ is another example: two real numbers are related via “ $=$ ” if they are equal. Another example is the relationship that one real number is at most another, and we write $a\leq b$ when we want to say $a$ and $b$ are related in this way. A less mathematical example is the relation “daughter of”, so for example “ $a$ is the daughter of $b$ ”.

Exercise 8.18.

Express the relations $\leq$ and “daughter of” as sets.

Solution (please try for yourself before looking)

For $\leq$ , we can consider

R=\left\{(a,b)\in\mathbb{R}\times\mathbb{R}:b=a+\varepsilon\text{ for some non% -negative real number }\varepsilon\right\}.

For “daughter of”, let $A$ be the set of all people. Then:

T=\left\{(a,b)\in A\times A:a\text{ is the daughter of }b\right\}.

Exercise 8.19.

Can you think of a relation $R$ on a set $X$ such that every pair of elements in $X$ are related under $R$ ?

Solution (please try for yourself before looking)

There are many possible relations here but one of the simplest is

R=\left\{(a,b)\in X\times X:a\in X\text{ and }b\in X\right\}.

8.3.1 Graphically representing relations

Any function can be used to define a relation. Let $f:A\to B$ be a function and consider the set $X=A\cup B$ . Then we consider the following relation on $X$ :

\left\{(a,b)\in X\times X:b=f(a)\right\}.

Limiting ourselves to real functions for a moment, the graph of the function $f:\mathbb{R}\to\mathbb{R}$ is a subset of $\mathbb{R}\times\mathbb{R}$ which graphically represents the associated function.

Figure 8.4: The graph of a function shows the relation defined by the function.

We can extend this: you may be familiar with graphically representing inequalities to show subsets of the Cartesian plane. For example, the inequality $y>x$ can be represented by the blue region below:

Figure 8.5: We can also graphically represent inequalities such as

y>x

Exercise 8.20.

Represent another relation on $\mathbb{R}$ graphically on the Cartesian plane.

Solution (please try for yourself before looking)

By shading the area below the line $y=x$ in the above graph instead, we obtain a graphical representation of the inequality $y<x$ on $\mathbb{R}$ .

Exercise 8.21.

The two images in Figure 8.6 represent familiar relations on $\mathbb{Z}$ as a shaded region of $\mathbb{Z}^{2}$ . What are the relations?

Figure 8.6: Two shaded regions of

\mathbb{Z}^{2}

represented two relations for 8.21.

Solution (please try for yourself before looking)

For $a,b\in\mathbb{Z}$ , the first figure in Figure 8.6 demonstrates the relation $a\neq b$ while the second represents $a|b$ .

We can also use directed graphs (with nodes and edges²² 2 Don’t worry if you haven’t seen graphs like this before.) to represent a relation on a finite set. The nodes of the graph are the elements in the set while the (directed) edges are placed between nodes whose elements are related to each other. So if $a\sim b$ , where $\sim$ is the relation we want to represent, then we would draw an arrow from the node $a$ to the node $b$ .

For example, consider the set $X=\{1,2,3,4,5,6\}$ and the relation $a|b$ on $X$ . We can represent this as in Figure 8.7.

Figure 8.7: Graphical representation of

a|b

on the set

\{1,2,3,4,5,6\}

8.3.2 Properties of Relations

Given a relation, there are several properties which we are interested in:

Definition 8.22 (Properties of Relations).

Let $X$ be a set and $\sim$ be a relation on $X$ . We say $\sim$ is:

•

reflexive if for each $a\in X$ , $a\sim a$ ;
•

symmetric if for every $a,b\in X$ such that $a\sim b$ , then $b\sim a$ ;
•

transitive if for all $a,b,c\in X$ such that $a\sim b$ and $b\sim c$ , then $a\sim c$ .

Example 8.23.

The relation “ $=$ ” on $\mathbb{R}$ is a reflexive relation as for all $a\in\mathbb{R}$ , $a=a$ . It is also symmetric as if $a=b$ , then $b=a$ . Finally, it is transitive as if $a=b$ and $b=c$ , then we have $a=c$ .

(a) Reflexivity

(b) Symmetry

Figure 8.8: Graphical representative of reflexivity, symmetry and transitivity

Proving a relation has (or does not have) one of these properties usually involves using both the definition of the property and relation carefully.

Lemma 8.24.

The relation $<$ on $\mathbb{R}$ is transitive.

Proof.

To show $<$ is transitive, we need to show that if $a<b$ and $b<c$ , then $a<c$ for some $a,b,c\in\mathbb{R}$ . Therefore, we assume $a<b$ and $b<c$ .

By definition of $<$ (see Example 8.17), we have $b=a+\varepsilon_{1}$ and $c=b+\varepsilon_{2}$ where $\varepsilon_{i}$ are positive real numbers. Then, substituting for $b$ , we obtain

c=a+\varepsilon_{1}+\varepsilon_{2}=a+\varepsilon_{3},

where $\varepsilon_{3}=\varepsilon_{1}+\varepsilon_{2}$ . As the sum of two positive real numbers is also a positive real number, $\varepsilon_{3}$ is a positive real number so, by definition of $<$ , we also have $a<c$ .

Therefore, $<$ is transitive.

Exercise 8.25.

Find counterexamples to show that $<$ is neither reflexive nor symmetric on $\mathbb{R}$ .

Solution (please try for yourself before looking)

For example, $1\not<1$ so $<$ is not reflexive. Also, even though $1<2$ , we have $2\not<1$ , and thus $<$ is not symmetric.

Lemma 8.26.

The relation $\subseteq$ on the set $\Omega$ consisting of all sets is transitive and reflexive.

Proof.

To show $\subseteq$ is transitive, we need to show that if $A\subseteq B$ and $B\subseteq C$ , then $A\subseteq C$ for some $A,B,C\in\Omega$ . Therefore, we assume $A\subseteq B$ and $B\subseteq C$ .

By definition of $\subseteq$ (Definition 4.7), if $A\subseteq B$ , then every element in $A$ also belongs to $B$ . Similarly, if $B\subseteq C$ , then every element in $B$ belongs to the set $C$ . Therefore, all the elements in the set $A$ , are also in the set $B$ so must also be in set $C$ meaning, by Definition 4.7, $A\subseteq C$ and thus $\subseteq$ is a transitive relation.

For reflexivity, we need to show that for all sets $A\in\Omega$ , $A\subseteq A$ . Every element of the set $A$ is an element of the set $A$ so, by Definition 4.7, $A\subseteq A$ . Therefore $\subseteq$ is reflexive.

Note that this proof only uses the definition of the $\subseteq$ and the definition of the relation property we are trying to show.

Exercise 8.27.

Prove that $\subseteq$ is not symmetric.

Solution (please try for yourself before looking)

As a counterexample, consider the sets $\emptyset,\{1\}$ . Then $\emptyset\subseteq\{1\}$ but $\{1\}\not\subseteq\emptyset$ because $1\notin\emptyset$ . So $\subseteq$ is not symmetric.

Lemma 8.28.

The relation $\neq$ on $\mathbb{R}$ is symmetric.

Proof.

To show $\neq$ is symmetric, we need to show that for all $a,b\in\mathbb{R}$ , then if $a\neq b$ , we have $b\neq a$ .

Assume $a\neq b$ , then there exists a non-zero number $\varepsilon$ such that $a=b+\varepsilon$ . Rearranging this, we have $b=a-\varepsilon$ . As $\varepsilon$ is a non-zero number, then $-\varepsilon$ is also a non-zero number so $b\neq a$ . This means $\neq$ is symmetric.

Exercise 8.29.

Find counterexamples to show that $\neq$ is neither reflexive nor transitive on $\mathbb{R}$ .

Solution (please try for yourself before looking)

Since $1=1$ , we do not have $1\neq 1$ and thus $\neq$ is not reflexive on $\mathbb{R}$ . Also, even though we have $1\neq 2$ and $2\neq 1$ , we don’t have $1\neq 1$ . Thus, $\neq$ is not transitive on $\mathbb{R}$ .