RELATIONS AND DIGRAPHS

4 : RELATIONS  AND DIGRAPHS  

 4.1  Product sets 

             An ordered pair ( a , b ) is a listing of the objects a and b in a prescribed order, with  a  appearing first and b appearing second.  Thus an ordered pair is merely a sequence of length 2. The ordered pairs  ( a₁ , b₁ )  and  ( a₂ , b₂ )  are equal if and only if  a₁ = a₂  and  b₁ = b₂ . 

             If  A  and  B  are two nonempty sets,  then the product set  or Cartesian product  A x B  as the set  of all ordered pairs ( a , b ) with  a Î A  and  b Π B.  Thus,

A  x  B  = {  ( a , b ) |  a Î A  and  b Π B } .

Example 1:

          Let  A = { 1 , 2 ,  3 , 4 }            and    B  =  {  w , x }   then

                        A  x  B  =  { ( 1, w) , ( 1, x ) ,  ( 2, w ) , ( 2, x ) ,  ( 3, w ) ,  ( 3, x ) , ( 4, w ) ,  ( 4, x ) }

    Observe that the elements of  A x B can be arranged in convenient tabular array as shown :

                                 

B  A	w	x
1	( 1 , w )	( 1 , x )
2	( 2 , w )	( 2 , x )
3	( 3 , w )	( 3 , x )
4	( 4 , w )	( 4 , x )

 

Example  2 :

            If  A and B are  as in Example 1, then

                   B  x  A =  { ( w, 1) , ( x, 1 ) ,  ( w, 2 ) , ( x, 2 ) ,  ( w, 3 ) ,  ( x, 3 ) , ( w, 4 ) ,  ( x, 4 ) }

  Theorem  1 : For any two finite, nonempty sets A and B,  | A x B |  =  | A | | B |     

        Proof :

            Suppose that | A | = m  and | B |  =  n. To form an ordered pair ( a, b ), a Î A  and  b Î B, perform two successive tasks.  Task 1 is to choose a first element from A, and task 2 is to choose a second element from B. There are m ways to perform task 1 and n ways to perform task 2; so by the multiplication principle, there are m x n ways to form an ordered pair ( a, b ).

            In other words, | A x B | = m × n  = | A | | B |.

Example 3.

          If  A = B = R, the set of all real numbers, then  R x R, also denoted by R ², is the set of all points in the plane. The ordered pair ( a , b ) gives the coordinates of a point in the plane.     

Example 4 :

 A marketing research firm classifies a person according to the following two criteria :

    Gender : male ( m ) ; female ( f )

    Highest level of education completed : elementary ( e ) ; high school ( h ) ; college ( c ) ; graduate ( g )

 Let  S = { m , f } and L { e , h , c , g } .  The product set  S x L  contains all the categories into which the population is classified.  Thus, the classification ( f, g ) represents a female who has completed graduate school. There are eight categories in this classification scheme.

      We now define the Cartesian product of three or more nonempty sets by generalizing the earlier definition of the Cartesian product of two sets. That is, the Cartesian product  A₁ x  A₂ x . . . x  A_m of the nonempty sets  A ₁,  A ₂, . . . , A _m  is the set of all ordered m – tuples  ( a ₁, a ₂, . . ., a _m ),  where a _i Î A _i for    i = 1, 2, . . . , m. Thus   A ₁ x  A ₂ x . . . x  A _m  = { ( a ₁, a ₂, . . . , a _m ) | a _i Î A  _i  ,  i = 1, 2, . . . , m } .  

Example 5 :

      A software firm provides the following three characteristics for each program that it sells :

            Language : FORTRAN ( f ) ;  PROLOG ( p ) ; LISP ( l )

            Memory :  2 meg ( 2 ) ;  4 meg ( 4 ) ;  8 meg ( 8 )

            Operating system : UNIX ( u ) ; DOS ( d )

     Let  L = { f , p , l } ,  M = { 2 , 4 , 8 }  and  O = { u , d } . Then the Cartesian product  L x M x O contains all the categories that describe a program. There are 3 × 3 × 2 or 18 categories in this classification scheme.

            Proceeding in a manner similar to that used to prove Theorem 1, using the extended multiplication principle, we can show that if A₁ has n₁ elements, A₂ has  n₂ elements, . . . , A _m has  n_m elements then  A₁ x  A₂  x . . . x  A_m  has  n₁ , n₂ , . . . ,  n_m  elements.

PARTITIONS

    A partition or quotient set of a nonempty set A is a collection  P  of nonempty subsets of A such that

            1.  Each element of A belongs to one of the sets in P.    

            2.  If  A₁  and  A₂ are distinct elements of P, then     

                                                                 A ₁ ∩ A ₂ = Ø

          The  sets in  P  are called the blocks or cells of the partition. 

The figure shows a partition  P = { A₁,  A₂,  A₃,  A₄,  A₅,  A₆,  A₇ } into seven blocks.  

Example 6 :

      Let  A = { s,  t,  u,  v,  w,  x,  y,  z } .  Consider the following subsets of A :

            A ₁ = { s,  t,  u,  v } ;  A ₂  =  { s,  u,  w,  x,  y,  z } ;  A ₃ = { s,  u, w,  y } ;  
             A ₄ = { t,  v } ; A ₅ = { x, z } 

Then  { A ₁ , A ₂ } is not a partition since

                                                        A ₁ ∩ A ₂ is not = Ø.

Also,  { A ₁ , A ₅ } is not a partition since w Ï A ₁ and  w Ï A ₅. 
 The collection  P = { A ₃ , A ₄ , A ₅ } is a partition of A.

Example 7.

            Let         Z   = set of all integers.

                        A ₁  = set of all even integers, and

                        A ₂  = set of all odd integers.

            Then  {  A ₁ ,  A ₂ }  is a partition of Z. 

Since the members of a partition of a set are subsets of A, we see that the partition is a subset of P ( A ), the power set of A. That is, partitions can be considered as particular kinds of subsets of P ( A ).

Exercises : 4.1 p 105

In # 1 – 4, find x or y so that the statement is true.

     1.  a)  ( x , 3 ) = ( 4 , 3 )                            b)  ( a , 3y ) = ( a , 9 )

     2.  a)  ( 3x + 1 , 2 ) = ( 7 ,  2 )                  b)  ( C ^{+ +} , LISP ) =  ( y , x ) 

     3.  a)  ( ( 4x , 6 ) = ( 16 , y )                     b)  ( 2x – 3 , 3y – 1 ) = ( 5 , 5 )

     4.  a)  ( x ² , 27 )  =  (  49 , y ³ )                b)  ( x , y ) = ( x ² , y ² )

          Let  A = {  a,  b }   and    B = {  3 ,  5 ,  7 }

     5.  List the elements in  a)  A  x  B    and   b )  B  x  A

     6.  List the elements in  a)  A  x  A    and   b)  B  x  B    

      In the next exercises, let  A = { 1,  2,  3,  4,  5,  6, 7,  8,  9, 10 }  and

             A ₁ =  { 1, 2, 3, 4 }                 A ₃  =  { 4, 5, 7, 9 }                   A ₅  =  {  8,  9,  10 }       

             A ₂ =  { 5, 6, 7 }                     A ₄  =  { 4, 8, 10 }                     A ₆  =  { 1, 2, 3, 6, 8, 10 }

 7.  Which of the following are partitions of A ?

          a)  {  A₁, A₂ ,  A ₅ }        b)  {  A₁, A₃ ,  A₅ }     c) {  A₃, A₆ }       d) {  A₂, A₃ ,  A₄ }

RELATIONS AND DIGRAPHS

          Let A and B be nonempty sets. A relation  R  from  A  to  B is a subset of  A x  B. If  R Í A  x  B and  ( a,  b )  Î R, we say that  a  is related to b by R, and we also write  a R b.  If a is not related to b by R, we write a R b.    ( R/ )

 Example 1.     

        Let  A = { 1, 2, 3 } and B = { w, x }. Then  R = { ( 1 , w ), ( 2 , x ),  ( 3, w ) }  is a relation from A to B.

 Example  2 :

          Let A and B be sets of real numbers . We define the following relation R ( equals )  from A to B.:

                                              a R b   if and only if  a = b.

 Example 3 :

        Let  A = { 1,  2,  3,  4,  5 }. Define the following relation R ( less than ) on A :

                                              a R b  if and only if  a < b.

  Then,  R = { ( 1, 2 ), ( 1, 3 ), ( 1, 4 ), ( 1, 5 ), ( 2, 3 ), ( 2, 4 ), ( 2, 5 ), ( 3, 4 ), ( 3, 5 ), ( 4, 5 ) }

 Example 4 :

        Let  A = Z ⁺ ,  the set of all positive integers. Define the following relation R on A :

                                                a R b   if and only if  a  divides  b

   Then,  4 R 12 ,  but  5 is not R 7       ( R/ )

 Example 5 :  

       Let A be the set of all people in the world. We define the relation  R on A,  a R b  if and only if there is a sequence  a ₀,  a ₁, . . . , a _n  of people such that a ₀ =  a,  a _n =  b  and  a _{i – 1} knows  i =  1, 2, . . ., n     ( n will depend on a and b )

 Example  6 :

       Let  A = , the set of real numbers. We define the following relation  R on A :

                          x R y   if and only if  x  and  y  satisfy the equation 

                                            

.                             

The set R consists of all points on the ellipse shown in the figure.

Example 7 :

    Let A be the set of all possible inputs to a given computer program. Define the following relation R from A to B :  a R b  if and only if b is the output produced by the program when input a is used.

Example  8 :

    Let A = the set of all lines in the plane. Define the following relation

R on A :

                                                     L₁ R  L₂   if and only if  L₁ is parallel to L₂.

    

     Example 9 :

         An airline services the five cities c ₁, c ₂, c ₃, c ₄, and c ₅. The cost ( in dollars ) of going from c_i to c_j is shown in the following table.  Thus, the cost of going from c ₁ to c ₃  is  $ 100, while that of  c ₄  to  c ₂  is $ 200.    

                                         

To From	C1	C2	C3	C4	C5
C1		150	110	160	210
C2	200		210	170	230
C3	120	190		200	260
C4	200	210	130		160
C5	210	110	210	160

 

We now define the following relation R on the set of cities 

       A =  { C ₁ , C ₂ , C ₃, C ₄ , C ₅ } : c_i R c_j if and only if the cost of going from  c_i   to c_j is defined and less than or equal to  $190.  Find R.

Solution :

            The relation R is the subset of A x A consisting of all cities ( c_{i ,} c_j),  where the cost of going from c_i to c_j is less than or equal to  $ 190. Hence ; 

   R = { (c ₁, c ₂ ), (c ₁, c ₃ ), (c ₁, c ₄) , (c ₂ , c ₄), (c ₃, c ₁), (c ₃, c ₂ ), (c ₄ , c ₃), (c ₄, c ₅),  (c ₅, c ₂), ( c ₅ , c ₄ ) }

Sets Arising from Relations

        1.  Domain of R.  Dom ( R ), is the set of all elements in A that are related to some element in B. It is a subset of A, it is the set of all first elements in the pairs that make up R.

        2.  Range of R. Ran ( R ), is the set of elements in B that are second elements of pairs in R, that is, all elements in B that are related to some elements in A.

            Elements in A that are not in Dom ( R ) are not involved in the relation R in any way. This also true for elements of B That are not in Ran ( R ).

Example :

        Let  A = { 1,  2,  3,  4,  5 }.  a R b  if and only if  a < b.

  Then, R = { (1, 2 ), ( 1, 3 ) , ( 1, 4 ) , ( 1, 5 ), ( 2, 3) , ( 2, 4 ) , ( 2, 5 ), ( 3, 4 ), ( 3, 5 ), ( 4, 5 ) }

            Also Dom ( R ) = { 1, 2, 3, 4 } and  Ran ( R ) = { 2, 3,  4, 5 }

In example 6 ( ellipse ) :

     DOM ( R )  = [ –2, 2 ] and  Ran ( R ) = [ –3, 3 ]. Note that this is given in interval notation.

If R is a relation from A to B and  x  Π A , we define R ( x ), the R–relative set of x, to be the set of all y in B with the property that x is R–related to y. Thus, in symbols,

                                                R ( x ) = { y  Î  B  |  x R y  }

Similarly, if  A₁  Í  A, then R ( A₁ ), the  R – relative set of A₁, is the set of all y in B with the property that x is  R – related to y for some x in A₁, that is,

                                                R ( A₁ ) ={ y  Î  B  |  x R y  for some x in A₁ }  

From the preceding definitions, we see that R ( A₁ )  is the union of the sets  R ( x ),  where  x  Î  A₁. The sets   R ( x )  play an important role in the study of many types of relations.

Let  A = { w,  x,  y,  z } and  let  R = { ( w, w ), ( w,  x ), ( x,  y ),  ( y,  w ),  ( z,  y ),  ( y,  x ) }

Then R ( w ) = { w , x } ,  R ( x ) = { y } ,  and if  A ₁ = { y , z } , then  R ( A ₁ ) = { w , x ,  y }  

Let R be the relation in example 6 ( ellipse ), and let  x  Π  .  If  x R y for some y, then  

            If  x is not in the interval (– 2, 2 ) then no y can satisfy the equation, since

                                            

Thus, in this case R ( x ) = { 0 } .  If  x = – 2 , then x ² / 4  = 1, so x can only be related to 0. Thus, R (– 2 ) = { 0 } .  Similarly, R ( 2 ) = { 0 }.