CMPU-145, Spring 2013
Answers to Practice Problems


1.  A.  Let A = {1,2}, B = {10,20}, and C = {100,200}.
    	Let f = {(1,10),(2,20)} (i.e., f(1)=10 and f(2)=20).
        Let g = {(10,100),(20,100)} (i.e., g(10)=g(20)=100).
	Then gof = {(1,100),(2,100)}.
	Note that f is injective, but g is not.
	In this case, gof is not injective either.

    B.  If f and g are functions such that g(f(a))=a for each a 
    	in A, then f must be injective; and g must be surjective.
        However, f might not be surjective; and g might not be
	injective.

    C.  Here's a counter-example where f is NOT surjective
        and g is NOT injective:

            A = {1}, B = {10,20}, f = {(1,10)}, g = {(10,1),(20,1)}

        Note that f is not surjective because 20 is not in the
        range of f.  And g is not injective because g(10)=g(20).

2.  A.  The relation R = {(1,1),(2,1),(3,1)} is serial over {1,2,3}
        but is not reflexive.  (For example, (2,2) is not in R.)

    B.  TRUE.  If f:A -> A is a function, then it must be serial.
    	(It's part of the definition of a function that each a in A
	has a corresponding "output" value f(a).)

    C.  If R is a reflexive binary relation over a set A, 
    	then R must also be serial.

        PROOF.  Let R be a reflexive binary relation of some set A.
                Let a in A be arbitrary.  Since R is reflexive,
		(a,a) is in R.  Thus, if we let y=a it follows
		that there is a pair (a,y) in R for some y in A.

    D.  If R is a serial, symmetric and transitive relation over
    	some set A, then R must also be reflexive.

        PROOF.  Let R be a serial, symmetric and transitive
                relation over some set A.

                Goal:  Show that R is reflexive (i.e., that
                       for every a in A, the pair (a,a) is in R.

                  Let a be any element in A.
                  Since R is serial, there is some y in A such
                    that (a,y) is in R.
                  Since R is symmetric, (y,a) must also be in R.
                  Since (a,y) and (y,a) are in R, the transitivity
                    of R ensures that (a,a) is in R.


3.  An example of a relation over the set {1,2,3,4,5} that
    is Euclidean but not transitive:

        Let R = {(1,2), (2,3), (2,2), (3,3), (3,2)}.

    R is not transitive since (1,2) and (2,3) are in R, but (1,3) is
    not.

    RE: Being Euclidean.  It is important to realize that the values
        of a, b and c in the definition of Euclidean need not be
        distinct.

        We can demonstrate that R is Euclidean by checking
        every pair of entries in R having the same first elements:
  
           (1,2) and (1,2) in R require that (2,2) be in R.

           (2,2) and (2,2) in R require that (2,2) be in R.
           (2,2) and (2,3) in R require that (2,3) be in R.
           (2,3) and (2,2) in R require that (3,2) be in R.
           (2,3) and (2,3) in R require that (3,3) be in R.

           (3,3) and (3,3) in R require that (3,3) be in R.
           (3,3) and (3,2) in R require that (3,2) be in R.
           (3,2) and (3,3) in R require that (2,3) be in R.
           (3,2) and (3,2) in R require that (2,2) be in R.


4.  The LISTERINO function!

    ;;;  LISTORINO
    ;;; ---------------------------------------
    ;;;  INPUTS:  N, TOTAL -- natural numbers
    ;;;  OUTPUT:  A list containing the fractions 1/N, 2/(N-1), ... , N/1.
    ;;;  Example:  (listorino 4 5) ==> (1/4 2/3 3/2 4/1)
    ;;;            (listorino 8 9) ==> (1/8 2/7 3/6 4/5 5/4 6/3 7/2 8/1)

    (define listorino
      (lambda (n total)
        (if (= n 0)
            ()
            (cons (/ (- total n) n)
                  (listorino (- n 1) total)))))

    Here's what happens when LISTORINO is called in the Interactions
    Window:

    > (listorino 4 5)
    (1/4 2/3 3/2 4)
    > (listorino 6 7)
    (1/6 2/5 3/4 4/3 5/2 6)
    > (listorino 20 21)
    (1/20 2/19 1/6 4/17 5/16 2/5 1/2 8/13 3/4 10/11 11/10 4/3 13/8 2 
     5/2 16/5 17/4 6 19/2 20)

    Notice that some of the fractions are shown in reduced form, but
    that's okay.