Your final submission must be hand-written, either on paper or on a tablet. If you write on paper, scan your work into a PDF file using your camera or a native app. If you write on a tablet, you should be able to save your work as a PDF file directly. In both cases, make sure that the file consists of pages with size 8.5 x 11.

Problem 1 [20 pts]

Consider a function f:X→Yf:X→ Y defined as follows:

f(x)={−2x,x≤02x−1,x>0f(x)={−2x,2x−1,x≤0x>0

1. Suppose that X=Y=RX=Y=R. Show that f is neither injective nor surjective.

2. Suppose that X=ZX=Z andY=Z0+Y=Z0+. Sketch this function on the 2D coordinate plane. Be sure to accurately reflect the domain and function range.

3. Prove that f, as defined in 2 above, is bijective.

4. For f as defined above, give complete descriptions (domain, codomain, and formulas) for the functions f−1f−1 and f。f。f. Show that f。f。f is not surjective.

Problem 2 [16 pts]

Suppose we have two functions f:X→Yf:X→ Y and g:Y→Zg:Y→Z.

1. Suppose that f is not injective. Prove that g。fg。f cannot be injective.

2. Suppose that gg is not surjective. Prove that g。fg。f cannot be surjective.

3. Suppose that f is injective and gg is not. Come up with two simple examples of sets X,Y,ZX,Y,Z and functions f,gf,g, one where g。fg。f is injective, and one where it is not.

4. Suppose that gg is surjective and f is not. Come up with two simple examples of sets X,Y,ZX,Y,Z and functions f,gf,g, one where g。fg。f is surjective, and one where it is not.

Problem 3 (python coding)

Implement the three Boolean functions in Python below. Each takes Python set arguments f and Y,   and isFunction() also takes in a set X. In particular, f is a set containing tuples. See the examples in the code cells below containing print statements. A further description of each function is as follows:

•    isFunction() should return True if f is a valid mathematical function with domain equal to X and codomain equal to Y, and False otherwise.

•    isInjective() should return True if f is injective and False otherwise. You may assume that f is indeed a function with codomain equal to Y.

•    isSurjective() should return True if f is surjective and False otherwise. You may assume that f is indeed a function with codomain equal to Y.

Each function should take no more than five or so lines of code. You may write solutions that use either loops or list comprehension.

Once you have finished writing all functions below, run all code cells and show the outputs. Export this notebook as a PDF file and append it to your PDF file for submission.

Problem 4 [24 pts]

For each of the relations defined below, briefly explain whether it satisfies each of the six relation properties. Write no more than two or three sentences per property justification.

1. Let XX be the set of all logical propositions. Let RR be a relation on XXwhere p R qp R q iff p→q is truep→q is true.

2. Let XX be the set of all Columbia computer science courses. Let RR be a relation on XXwhere x R yx Ry iff x is a prerequisite for y.x is a prerequisite for y.

Problem 5 [24 pts]

Suppose we have two relations R1R1 andR2R2 on a set XX, with matrix representations M1M1 and M2M2, respectively. From these, we can construct three new relations using set operations. We say that a property is not preserved ifR1R1 andR2R2 both have that property, but the newly constructed relation does not.

1. Let R3=R1UR2R3=R1UR2. Concisely explain how we can construct its matrix representation M3M3 from the matrices M1M1 and M2M2. Which of the six relation properties are not preserved by R3R3? Briefly justify each one that you identify, e.g. by giving a simple example. (You do not have to explain the properties that are preserved.)

2. Repeat 1 for the relation R3=R1∩R2R3=R1∩R2.

3. Repeat 1 for the relation R3=R1−R2R3=R1−R2.