NUMBERS AND SETS EXAMPLES SHEET 1. W. T. G.

1. Let A, B and C be three sets. Give a proof that A \ (B ∪ C) = (A \ B) ∩ (A \ C) using the criterion for equality of sets.

2. The symmetric difference A △ B of A and B is defined to be (A \ B) ∪ (B \ A). (That is, it is the set of elements that belong to one of A and B but not both.) Write out a truth table to show that the operation △ is associative. Show that x belongs to A △ (B △ C) if and only if x belongs to an odd number of the sets A, B and C and use this observation to give a second proof that △ is associative.

3. Let A, B, C and D be sets. Prove that A×(B ∪C) = (A×B)∪(A×C). Is it necessarily true that (A × B) ∪ (C × D) = (A ∪ C) × (B ∪ D)?

4. Write down the negations of the following statements.

(i) n is even or m is a multiple of 3.

(ii) Every x ∈ A is also an element of B ∩ C. (iii) If it is not raining today then no pigs can fly.

5. Let f and g be functions and let h = g ∘ f. If f and g are injections/surjections, prove that h is an injection/surjection.

6. Let f be a function from a set X to a set Y and let C and D be subsets of Y. Prove that f^{−1}(C ∩ D) = f^{−1}(C) ∩ f^{−1}(D). Now let A and B be subsets of X. Is it necessarily true that f(A ∩ B) = f(A) ∩ f(B)?

7. How many functions are there from the set {1, 2, 3, 4, 5} to the set {1, 2, 3}? How many of them are surjections?

8. Let n be odd. Prove that exactly half of the 2^{n} subsets of {1, 2, …, n} have even size. Now show that the same is true when n is even (and non-zero). [Hint: divide the sets into those that contain the element 1 and those that do not.]

9. Use the inclusion-exclusion principle to determine how many numbers in the set {1, 2, 3, …, 500} are divisible by none of 2, 3, 5 or 7. (If we have not yet covered the inclusion-exclusion principle, then see if you can work out the answer anyway.)

10. Give an example of a relation that is symmetric and transitive but not reflexive, or else prove that no such relation exists.

11. Define a binary operation ∗ on ℤ^{2} by the formula (a, b) ∗ (c, d) = (ac, ad + bc). Prove that the operation ∗ is commutative and associative. Write down an expression for

(a_{1}, b_{1}) ∗ (a_{2}, b_{2}) ∗ … ∗ (a_{k}, b_{k}) .

12. Let A_{1}, A_{2}, … be sets such that for every positive integer n we have A_{1} ∩…∩A_{n} ≠ ∅. Is it possible that A_{1} ∩ A_{2} ∩ … = ∅?

13. Let f be a function from the real numbers to the real numbers. Say that f is strictly increasing if f(x) < f(y) whenever x < y. Show that if f is strictly increasing, then it is an injection. Must it also be a surjection? Suppose that f is a bijection and that f(0) = 0 and f(1) = 1. Does it follow that f is strictly increasing?

14. Find a bijection from the set of all rational numbers to the set of all non-zero rational numbers. Is there such a bijection that is strictly increasing?