Problem  1.    [10 points] For each of the following determine whether the relation on the given set is reflexive, symmetric, transitive, and an equivalence relation.  Justify each of your answers using either paragraph proof or counterexamples.  Just like two-column proofs, paragraph- form proofs must justify each statement based on previous statements. Unlike two-column proofs, there’s no rigid format any more, and no need to explicitly number your lines. Instead, use phrases like“because of,”“since,””therefore,” etc.

a) R = {(f,g) ∣ f(1) > 0 AND g(1)  0} on set A ={f  ∣ f ∶ Z → Z}.  Here f and g represent functions.

b) R = {(f,g) ∣ f(1) > 0 XOR g(1)  0} on set A ={f  ∣ f ∶ Z → Z}.  Here f and g represent functions.

Problem 2.    [15 points] We wish to investigate a new property of relations which we will call Stevian (FYI: that’s not really its name). A relation R on the set A is Stevian if:

∀a,b,c e A  aRb ∧ aRc → bRc

a)  Explain, in English, how “transitive”is not the same as “Stevian.”

b)  Relation R = {(a,c), (a,b), (b,b), (b,c), (d,b), (d,d)} is given to you.

1. Draw a directed graph for the above relation.

2. Is it Stevian? If No, redraw the directed graph and add the ordered pairs (arrows) to make it Stevian.

3. Does the updated graph in previous part is a counterexample showing that Stevian relations are not necessarily transitive? Justify your answer.

c)  Is the following statement implied by the fact that a relation is Stevian?

∀a,b,c e A  aRb ∧ aRc → cRb

Explain why or why not.

d)  Prove that if a relation R is reflexive and Stevian then R is an equivalence relation.

Problem 3.    [15 points] You create a general AI (artificial intelligence) and want to teach him “friendship” as a relation on a set of people.  You define some rules for this friendship relation. These are your four laws of robotic friendships:

1.  “Everyone is friend of him or herself”.

2.  “Not everyone is friend with everyone”.

3.  “The enemy of my enemy is my friend” (here “enemy”just means “not friend”).

4.  “The enemy of my friend is my enemy.”

a)  Can the following directed graph represent the above “friendship” relation on a set of 2 people? Justify your answer.

b)  Is the defined “friendship” relation reflexive? Justify your answer (explain, in English).

c)  Is the defined “friendship” relation symmetric? Justify your answer (explain, in English).

d)  Is the defined “friendship” relation transitive? Justify your answer (explain, in English).

e)  Is the defined “friendship” relation equivalence? Justify your answer (explain, in English).

f)  Can the following directed graph represent the defined “friendship”relation on a set of 5 people? Justify your answer (explain, in English).

g)  Draw a directed graph for the defined “friendship” relation on a set of 4 people

{Alice,Bob,Allen,Eve}.  Then, write down the quotient set (partition) that your relation makes on this set of 4 people if it is possible.

Problem 4.   [10 points]

a)  Write a function in python that takes a domain A (as a python set or list) and a function f (with domain A) and returns True if and only if f is injective.

Here is the function signature you need to use.

def  injective(A,f):

You can test your code as follows.

A  =  {1 ,2 ,3}

B  =  {-2 ,0 ,2}

def  powerOfTwo(x):

return  x  **  2

print(injective(A,powerOfTwo))    # prints True

print(injective(B,powerOfTwo))    # prints False

b)  Write a function in python that takes a domain A and a target B (as python sets or lists) and a function f (with domain A) and returns True if and only if f is surjective over the target B.

Here is the function signature you need to use.

def  surjective(A,B,f):

You can test your code as follows.

A  =  {1 ,2 ,3}

B  =  {2 ,4 ,6}

C  =  {3 ,5 ,7}

def  double(x):

return  x  *  2

print(surjective(A,B,double))    # prints True

print(surjective(A,C,double))    # prints False