CMPU-145, Spring 2013
Asmt. 2 Solutions to Written Part (Problems 1-3)


1.  Recall the definitions of reflexive, symmetric and transitive relations.
    Let A = {1,2,3}.

    (a) Give an example of a binary relation R1 over A that is
        reflexive and symmetric, but not transitive.

        R1  =  { (1,1), (2,2), (3,3), (1,2), (2,1) (2,3), (3,2) }


    (b) Give an example of a binary relation R2 over A that is
        reflexive and transitive, but not symmetric.

        R2  =  { (1,1), (2,2), (3,3), (1,2), (2,3), (1,3) }

    (c) Give an example of a binary relation R3 over A that is
        symmetric and transitive, but not reflexive.

        R3  =  { }
     

2.  Prove that the intersection of two transitive relations must be transitive.

      PROOF.  Let R and S be two transitive relations.
              Let T be the intersection of R and S.

              Goal: Show that T is transitive (i.e., that for any
                        pairs (x,y) and (y,z) in T, the pair (x,z) is
                        also in T).

              Proof of Goal:  Let (x,y) and (y,z) be any pairs in T.
                    Since T = R INTERSECT S, it follows that
		                 (x,y) and (y,z) both belong to R.
                    Since R is transitive, it follows that (x,z) is in R.
                    Since T = R INTERSECT S, it follows that
                                 (x,y) and (y,z) both belong to S.
                    Since S is transitive, it follows that (x,z) is in S.
                    Since (x,z) is in both R and S, it follows that
                                 (x,z) is in T = R INTERSECT S.


3.  Give an example of two relations, R and S, over the set A = {1,2,3}
    such that R and S are transitive, but the UNION of R and S is not 
    transitive.

              R = { (1,2) },   S = { (2,3) }  are both transitive.

         But their union is  { (1,2), (2,3) },  which is not transitive.