Some guidelines:

• Please write clear and detailed solutions in the boxes following each question or part of question. The boxes should typically provide sufficient space for your solution, but if you find you need extra space please take an empty sheet of paper and continue your solution there, clearly indicating which question this refers to. Also indicate in the corresponding box that the solution continues at the end.

• There is no need to include your preparatory scratch work (do this on separate paper) but make sure that the solution you write in the box is a complete explanation.

The quality of the exposition will be assessed alongside the correctness of the approach.

• For technical reasons (since you will be scanning your solutions to upload to GradeScope), please write legibly with a very readable writing implement.

• Results stated in the lectures can be used (without having to re-prove them); make sure you say clearly what result you are using, though.

• It is acceptable for students to discuss the questions on the assignments and strategies for solving them. However, each student must write down their solutions in their own words and notation (and make sure that they understand what they are writing).

• Assignments are a valuable learning tool in this subject, so strive to maximise their impact on your understanding of the material.

• No Chegg or anything similar. At all. Please. 

1. Use the principle of mathematical induction to prove that, for any n ≥ 1 and any list of n differentiable1  functions f1 ,f2 , . . . ,fn , we have

(f1 (x)f2 (x) . . . fn (x))\  = f(x) + f(x) + ··· + f(x)

2.  Sets can be dark, scary places, so we want to institute a buddy system2 to make things nicer for the elements.  Given a set A and x,y ∈ A, we will write x ∼ y to signify that “x is the buddy of y”, and we want this to satisfy three properties:

• x ∼ x for all x ∈ A (“everyone is buddies with themselves”);

• if x ∼ y then y ∼ x (“if you are my buddy then I am your buddy”);

• if x ∼ y and y ∼ z then x ∼ z (“the buddy of my buddy is also my buddy”).

(a) Let A, B be sets and f : A → B a function. For x,y ∈ A, define x ∼ y if f(x) = f(y).

Show that this satisfies the properties of a buddy system on A.

(b) Fix a natural number n.  For k,m ∈ Z, define k ∼ m if m − k is divisible by n.  Show

that this satisfies the properties of a buddy system on Z.

(c) Fix a set Ω and let A denote the set of all subsets of Ω .  For X,Y ∈ A define X ∼ Y if there exists a bijective function X → Y .  Show that this satisfies the properties of a buddy system on A.

(d)  Suppose we are given a buddy system on a set A. For any element x ∈ A, we define the

buddy group of x as:

♡(x) = {y ∈ A | x ∼ y}.

Show that, for any elements x,z ∈ A, their buddy groups are either identical or disjoint, in other words:

either ♡(x) = ♡(z)   or ♡(x) ∩ ♡(z) = ∅ .

(e) How many distinct buddy groups are there for the buddy system on Z defined in part

(b)? Make sure to prove that the number you give (and which will probably depend on n) is the exact number of groups (not just an upper bound, for instance).

(f)  Suppose we are given a buddy system on a set A, and consider the set B of buddy

groups:

B = {♡(x) | x ∈ A}.

There is an obvious surjective function π : A → B defined by π(x) = ♡(x). Under what circumstances (if any) is π a bijection?

(g) Let A = N × N and define (a,b) ∼ (c,d) if a + d = b + c.

i.  Show that this satisfies the conditions of a buddy system on A.

ii.  Construct a bijective function B → Z, where B is the set of buddy groups.  (Don’t forget to prove that your function is well-defined, and that it is bijective.)

3. For a given set X, its power set P(X) is the set of all its subsets: P(X) = {S | S ⊆ X}.

For example:

P ({1, 2, 3}) ={∅ , {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Suppose now that X and Y are sets and f : X → Y is a function.  Given a subset S ⊆ X , its image under f is the subset

f(S) ={y ∈ Y | there exists x ∈ S such that f(x) = y } ⊆ Y.

(A special case of this construction is f(X), the range of f .)

With this setup we have a function between power sets:

If : P(X) → P(Y)       given by If (S) = f(S).

(a) Let S and T be subsets of X . Prove that

f(S n T) = f(S) n f(T).