1fa a b C and B 1 3 1 0 1 3 then the number of injections that can be defined from A to B is

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\)

(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.\]

\(\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.

(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.

(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

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

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.\) 

(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: