KMB, 12/12/99

M1F Foundations of Analysis—Problem Sheet 10

1) Let A, B and C be sets, and let f : A → B and g : B → C be functions. Note then that their composite g ∘ f maps A to C.

a) Prove that if f and g are injective then so is g ∘ f.

b) Prove that if f and g are surjective then so is g ∘ f.

c) Prove that if f and g are bijective then so is g ∘ f.

2) If f : A → B is a function, then prove that there is a set X and maps s : A → X and i : X → B such that

• s is surjective,

• i is injective,

• f = i ∘ s.

Hint: Let X be the subset of B consisting of things in the image of f.

3) Let X be a set with three elements, and let Y be a set with five elements. How many functions f : X → Y are there? How many are injective? And how many are surjective?

4) Which of the following relations on the real numbers ℝ are equivalence relations? For each one, either prove reflexivity, symmetry and transitivity, or give an example to show that one of these does not hold.

(a) x ∼ y ⟺ x ≥ y

(b) x ∼ y ⟺ x^{2} = y^{2}

(c) x ∼ y ⟺ x + y ∈ ℤ

(d) x ∼ y ⟺ x − y ∈ ℤ

(e) x ∼ y ⟺ x ≠ y.

5) Let S be a set and let ∼ denote a relation on S. I will now try to prove that if ∼ is symmetric and transitive, then it is reflexive.

Let x ∈ S be any element. Choose y such that x ∼ y. By symmetry of ∼, we deduce that y ∼ x. By transitivity of ∼, we have x ∼ y and y ∼ x, so we can deduce that x ∼ x. But x was arbitrary, so we have proved that ∼ is reflexive.

Actually, no we haven’t, I have made a mistake. Find it, and give an example of a relation on a set S that is symmetric and transitive, but not reflexive.

6) In Theorem 8.2 of the course, we showed that if ∼ is an equivalence relation on a set S, then the equivalence classes for ∼ form a partition of S. There is a converse to this and it’s easier! So prove it yourselves :-) Namely, let S be a set, and let T_{1}, T_{2},… be a partition of S (so the T_{i} are disjoint and their union is S). Now define an equivalence relation on S by

x ∼ y ⟺ there is an i such that x and y both lie in T_{i}.

Check that this is an equivalence relation. Also check that the equivalence classes for ∼ are precisely the sets T_{i}. So in fact, to give an equivalence relation on a set S and to give a partition of S are essentially the same thing.

7) How many relations are there on a set with three elements? And how many equivalence relations? Hint for last part: use Q6.