Problem 3. (32 points)

a) (8 points) Write a function in python that takes a set A and a relation R on A (as a python function such that R(x,y) returns true if and only if the relation xRy holds), and returns True if and only if the relation R is relfexive. Here is the function signature you need to use. def is_reflexive(A, R): You can test your code as follows. 1 s = {1,2,3} def y(x, y): return x == y def n(x, y): return x == y and x != 3 is_reflexive(s, y) # returns True is_reflexive(s, n) # returns False

b) (12 points) Write a function in python that takes a domain domain (as a python set) and a function f (with domain domain) and returns True if and only if f is injective. Here is the function signature you need to use. def is_injective(domain, f): You can test your code as follows. s = {1,2,3} def double(x): return x * 2 def halve(x): return x // 2 # integer division rounds down is_injective(s,double) # returns True is_injective(s,halve) # returns False

c) (12 points) Write a function in python that takes a set A and a relation R on A (as a python function such that R(x,y) returns true if and only if the relation xRy holds), and returns True if and only if the relation R is transitive. Here is the function signature you need to use. def is_transitive(A, R):

Problem 4. (35 points) Write python code that checks if a set of sets p (a list of sets in python because python does not allow sets of sets) is a partition of a set s. p is a partition of s if and only if the union of the elements of p is equal to s and the intersection of any two elements of p is empty set. In each subproblem, you can invoke functions from previous subproblems if that helps.

a) (7 points) Implement a function with signature def are_parts_nonoverlapping(p): that returns True if and only if the intersection of any two elements of p is the empty set. You can test your code as follows. are_parts_nonoverlapping([{0, 1}, {3, 5}]) # returns True are_parts_nonoverlapping([{0, 1}, {3, 5, 1}]) # returns False

b) (7 points) Implement a function with signature def do_parts_contain_element(x, p): 2 that returns True if and only if the element x is an element of some element of p.

c) (7 points) Implement a function with signature def do_parts_cover_set(s, p): that returns True if and only if every element of s is in some element of p.

d) (7 points) Implement a function with signature def do_parts_have_nothing_extra(s, p): that returns True if and only if every element of every element of p is in s.

e) (7 points) Implement a function with signature def is_partition(s, p): that returns True if and only if p is a partition of s.