Question

.Let\(R\)be the relation that contains the pair\(\left( {a,b} \right)\)if\(a\)and\(b\)are cities such that there is a direct non-stop airline flight from\(a\)to\(b\). When is\(\left( {a,b} \right)\)in

a)\({R^2}\)?

b)\({R^3}\)?

c)\({R^*}\)?

Short answer

(a) There is an airline flight from\(a\)to\(b\)with exactly 1 stop in some intermediate city

(b) There is an airline flight from\(a\)to\(b\)with exactly 2 stops in some intermediate cities

(c) It is possible to fly from \(a\) to \(b\)

Step-by-step solution

Given

\(R = \{ (a,b)\mid \)There is a direct non-stop airline flight from\(a\)to\(b\} \)

\(A = {\rm{ Set of all cities }}\)

Concept of Relation

A relation\(R\)can be represented by the matrix\({{\bf{M}}_R} = \left( {{m_{ij}}} \right)\)

\({m_{ij}} = \left\{ {\begin{array}{*{20}{l}}1&{{\rm{ if }}\left( {{a_i},{b_j}} \right) \in R}\\0&{{\rm{ if }}\left( {{a_i},{b_j}} \right) \notin R}\end{array}} \right.\)

The composite\(S^\circ R\)consists of all ordered pairs\((a,c)\)for which there exists an element\(b\)such that\((a,b) \in R\)and\((b,c) \in S\).

Use Definition of composite for part (a)

\(R = \{ (a,b)\mid \)There is a direct non-stop airline flight from\(a\)to\(b\} \)

\(A = {\rm{ Set of all cities }}\)

(a) Use the definition of composite:

\(\begin{array}{c}{R^2} = R^\circ R\\ = \{ (a,b)\mid {\rm{ There cxists a city csuch that there is a direct non - stop airline flight from }}a{\rm{ to }}c\\{\rm{and there is a direct non - stop airline flight from }}c{\rm{ to }}b\} \\ = \{ (a,b){\rm{ It is possible to fly from }}a{\rm{ to }}b{\rm{ with exactly }}1{\rm{ stop in some intermediate city }}\} \end{array}\)

 Step 4: Use Definition of composite for part (b)

(b) Use the definition of composite:

\(\begin{array}{c}{R^3} = {R^2}^\circ R\\ = \{ (a,b)\mid {\rm{ There exists a city csuch that there is a direct non - stop airline flight from }}a{\rm{ to }}c\\{\rm{ and there is an airline flight from }}c{\rm{ to }}b{\rm{ with cxactly }}1{\rm{ stop in some intermediate city }}\} \\ = \{ (a,b){\rm{ It is possible to fly from }}a{\rm{ to }}b{\rm{ with cxactly }}2{\rm{ stops in some intermediate cities }}\} \end{array}\)

Step 5: Use Definition of composite for part (c)

(c)

Property\({R^*}\):\({R^*} = R \cup {R^2} \cup {R^3} \cup \ldots . \cup {R^n}\)

Generalizing part (a) and (b):

\({R^j} = \{ (a,b)\)It is possible to fly from\(a\)to\(b\)with exactly\(j - 1\)stops in some intermediate cities\(\} \)

\(j \in \{ 1,2, \ldots ,n\} \)

Using\({R^*} = R \cup {R^2} \cup {R^3} \cup \ldots \cup {R^n}\)

\({R^*} = \{ (a,b)\mid \) It is possible to fly from \(a\) to \(b\} \)