6.1: Relations on Sets

Definition: Relation

A relation from a set \(A\) to a set \(B\) is a subset of \(A \times B\). Hence, a relation \(R\) consists of ordered pairs \((a,b)\), where \(a\in A\) and \(b\in B\). If \((a,b)\in R\), we say that is related to , and we also write \(a\,R\,b\).

Remark

We can also replace \(R\) by a symbol, especially when one is readily available. This is exactly what we do in, for example, \(a<b\). To say it is not true that \(a<b\), we can write \(a\nless b\). Likewise, if \((a,b)\notin R\), then \(a\) is not related to \(b\), and we could write \(a\!\not\!R\,b\). But the slash may not be easy to recognize when it is written over an uppercase letter. In this regard, it may be a good practice to avoid using the slash notation over a letter. Alternatively, one may use the “bar” notation \(\overline{a\,R\,b}\) to indicate that \(a\) and \(b\) are not related.

Example \(\PageIndex{1}\label{eg:defnrelat-04}\)

Define \(R=\{(a,b)\in\mathbb{R}^2 \mid a<b \}\), hence \((a,b)\in R\) if and only if \(a<b\). Obviously, saying “\(a<b\)” is much clearer than “\(a\,R\,b\).” If \(a\) and \(b\) are not related, we could say \((a,b)\notin R\), or \(a\nless b\).

Since a relation is a set, we can describe a relation by listing its elements (that is, using the roster method).

Example \(\PageIndex{2}\label{eg:parity}\)

Let \(A=\{1,2,3,4,5,6\}\) and \(B=\{1,2,3,4\}\). Define \((a,b)\in R\) if and only if \((a-b)\bmod 2 = 0\). Then \[R=\{(1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4), (5,1), (5,3), (6,2), (6,4)\}.\] We note that \(R\) consists of ordered pairs \((a,b)\) where \(a\) and \(b\) have the same parity. Be cautious, that \(1\leq a\leq 6\) and \(1\leq b\leq 4\). Hence, it is meaningless to talk about whether \((1,5)\in R\) or \((1,5)\notin R\).

hands-on Exercise \(\PageIndex{1}\label{he:relat-div}\)

Let \(A=\{2,3,4,7\}\) and \(B=\{1,2,3,\ldots,12\}\). Define \(a\,S\,b\) if and only if \(a\mid b\). Use the roster method to describe \(S\).

In the last example, 7 never appears as the first element (in the first coordinate) of any ordered pair. Likewise, 1, 5, 7, and 11 never appear as the second element (in the second coordinate) of any ordered pair.

Definition

The domain of a relation \(R\subseteq A\times B\) is defined as \[\mbox{domain of}\,R = \{ a\in A \mid (a,b)\in R \mbox{ for some $b\in B$} \},\] and the range is defined as \[\mbox{range of}\,R= \{ b\in B \mid (a,b)\in R \mbox{ for some $a\in A$} \}.\]

hands-on Exercise \(\PageIndex{5}\label{he:defnrelat-05}\)

Find \(\mbox{domain of}\,S\) and \(\mbox{range of}\,S\), where \(S\) in Hands-On Exercise 1.

A relation \(R\subseteq A\times B\) can be displayed graphically on an arrow graph, also called digraph (for directed graph). Represent the elements from \(A\) and \(B\) by vertices or dots, and use arrows (also called directed edges or arcs) to connect two vertices if the corresponding elements are related. The figure below displays a graphical representation of the relation in Example 2.

 

hands-on Exercise \(\PageIndex{7}\label{he:defnrelat-07}\)

The courses taken by John, Mary, Paul, and Sally are listed below.

John:	MATH 211, CSIT 121, MATH 220
Mary:	MATH 230, CSIT 121, MATH 212
Paul:	CSIT 120, MATH 230, MATH 220
Sally:	MATH 211, CSIT 120

Represent, using an arrow graph, the relation \(R\) defined as \(a\,R\,b\) if student \(a\) is taking course \(b\).

Summary and Review

• Relations are generalizations of functions. A relation merely states that the elements from two sets \(A\) and \(B\) are related in a certain way.
• More formally, a relation is defined as a subset of \(A\times B\).
• The domain of a relation is the set of elements in \(A\) that appear in the first coordinates of some ordered pairs, and the image or range is the set of elements in \(B\) that appear in the second coordinates of some ordered pairs.
• For brevity and for clarity, we often write \(x\,R\,y\) if \((x,y)\in R\).
• Under this convention, the mathematical notations \(\leq\), \(\geq\), \(=\), \(\subseteq\), and their like, can be regarded as relational operators.

Exercises 

Exercise \(\PageIndex{1}\label{ex:defnrelat-01}\)

Let \(A=\{A_1,A_2,A_3,A_4,A_5\}\) where \(A_1=\{1\}\qquad A_2=\{5,6,7\} \qquad A_3=\{1,2,3\} \qquad A_4=\{4\} \qquad A_5=\{10,11\}.\)

Define the relation \(R\) on the set \(A\) as \(A_i \, R \, A_j \mbox{ iff } |A_i| \geq |A_j|.\)

True or False?

(a)  \(A_2 \, R \, A_3\)

(b)  \(A_1 \, R \, A_5\)

(c)  \(A_3 \, R \, A_5\)

(d)  \(A_2 \, R \, A_1\)

(e)  \(A_5 \, R \, A_2\)

(f) \((A_1,A_3) \in R\)

(g) \((A_1,A_4) \in R\)

Solution

(a) True \(\qquad\) (b) False \(\qquad\) (c) True \(\qquad\)(d) True \(\qquad\)(e) False \(\qquad\) (f) False \(\qquad\) (g) True

Exercise \(\PageIndex{2}\)

Let \(A=\{A_1,A_2,A_3,A_4,A_5\}\) where \(A_1=\{1\}\qquad A_2=\{5,6,7\} \qquad A_3=\{1,2,3\} \qquad A_4=\{4\} \qquad A_5=\{10,11\}.\)

Define the relation \(R\) on the set \(A\) as \(A_i \, R \, A_j \mbox{ iff } |A_i| \geq |A_j|.\)

(a) List all the elements of \(A\) that are related to \(A_5.\)

(b) List all the elements of \(A\) that  \(A_5\) is related to

Exercise \(\PageIndex{3}\)

Write out the relation \(R\) as a set of ordered pairs. \(R :\mathscr{P} (\{1,2\}) \to \mathscr{P}(\{1,2\})\), where \[(S,T)\in R \Leftrightarrow S\cap T = \emptyset.\]

 

Solution

\(\big \{ (\emptyset , \emptyset), (\emptyset , \{1\}), (\{1\}, \emptyset ), (\emptyset , \{2\}), (\{2\}, \emptyset ),(\emptyset , \{1,2\}),(\{1,2\}, \emptyset ),(\{1\} , \{2\}), (\{2\},\{1\})\big \}\)

 

Exercise \(\PageIndex{4}\)

Represent each of the following relations from \(\{1,2,3,6\}\) to \(\{1,2,3,6\}\) using an arrow graph.

(a) \(\{(x,y)\mid x = y\}\)

(b) \(\{(x,y)\mid x\neq y\}\)

(c) \(\{(x,y)\mid x < y\}\)

Exercise \(\PageIndex{5}\)

Find the domain and image of each relation in Problem Exercise 4.

Solution

(a) \(\mbox{domain}=\mbox{range}=\{1,2,3,6\}\).

(b) \(\mbox{domain}=\mbox{range}=\{1,2,3,6\}\).

(c) \(\mbox{domain}=\{1,2,3\}\), \(\mbox{range}=\{2,3,6\}\).

 

Exercise \(\PageIndex{6}\)

Represent each of the following relations from \(\{1,2,3,6\}\) to \(\{1,2,3,6\}\) using an arrow graph.

(a) \(\{(x,y)\mid x^2\leq y\}\)

(b) \(\{(x,y)\mid x \mbox{ divides }y\}\)

(c)  \(\{(x,y)\mid x+y\mbox{ is even }\}\)

Exercise \(\PageIndex{7}\)

Find the domain and image of each relation in Problem 6.

Solution

(a) \(\mbox{domain}=\{1,2\}\), \(\mbox{range}=\{1,2,3,6\}\).

(b) \(\mbox{domain}=\mbox{range}=\{1,2,3,6\}\).

(c) \(\mbox{domain}=\mbox{range}=\{1,2,3,6\}\).

 

 

Exercise \(\PageIndex{8}\)

Create the arrow graph that represents the relation \(S\) defined on \(\{1,2,4,5,10,20\}\) by \[x\,S\,y \Leftrightarrow \mbox{($x<y$ and $x$ divides $y$)}.\]

Exercise \(\PageIndex{9}\label{ex:defnrelat-09}\)

Answer these questions about the relation \(S\) defined on \(\{1,2,4,5,10,20\}\) by \[x\,S\,y \Leftrightarrow \mbox{($x<y$ and $x$ divides $y$)}.\]

True or False?

(a) If \((x,y) \in S,\) then \((y,x) \notin S,\) for all \(x,y \in S.\) 

(b) \((x,x) \in S,\) for all \(x \in S.\)

(c) If \((x,y) \in S,\)  and \((y,z) \in S,\) then \((x,z) \in S,\)  for all \(x,y,z \in S.\) 

Solution

(a) True \(\qquad\) (b) False \(\qquad\) (c) True

 

Exercise \(\PageIndex{10}\label{ex:defnrelat-10}\)

For a relation \(R\subseteq A\times A\), instead of using two rows of vertices in a digraph, we can use a digraph on the vertices that represent the elements of \(A\). Hence, it is possible to have two directed arcs between a pair of vertices, and a loop may appear around a vertex \(x\) if \((x,x)\in R\). Write the set of ordered pairs for the relation represented by the following arrow diagram: