M55: Exercise sheet 0 (revision of set theory)

Let X, Y be sets. I hope the following concepts and notations are familiar:

(a) The power set 𝒫(X) of X is the collection of all subsets of X. For example, if X = {a, b} then 𝒫(X) = {∅, {a}, {b}, X}.

(b) If A ⊂ X then X \ A = {x ∈ X : x ∉ A}. This is the complement of A in X.

(c) Let f : X → Y be a map. If B ⊂ Y, then the pre-image or inverse image of B under

f is given by:

f^{−1}(B) = {x ∈ X : f(x) ∈ B} ⊂ X.

(d) Less useful, although easier to think about, is the image of A ⊂ X under f given by: f(A) = {f(x) : x ∈ A} ⊂ Y.

Exercises

1. Let f : X → Y be a map from X to Y. Let U, V ⊂ X and A, B ⊂ Y. Prove or give counterexamples to the following assertions.

(a) f(U ∩ V) = f(U) ∩ f(V);

(b) f(U ∪ V) = f(U) ∪ f(V);

(c) f^{−1}(A ∩ B) = f^{−1}(A) ∩ f^{−1}(B);

(d) f^{−1}(A ∪ B) = f^{−1}(A) ∪ f^{−1}(B);

(e) f(X \ U) = Y \ f(U); (f ) f^{−1}(Y \ B) = X \ f^{−1}(B). In the light of this, which is better behaved: the image or pre-image?

2. Let (A_{i})_{i∈I} be a family of subsets of X. Prove the De Morgan Laws:

X \ ⋃_{i∈I} A_{i} = ⋂_{i∈I}(X \ A_{i})
X \ ⋂_{i∈I} A_{i} = ⋃_{i∈I}(X \ A_{i}).

3. Suppose f : X → Y is a bijection with inverse f^{−1} : Y → X.

(a) Let B ⊂ Y. Show that the pre-image of B under f is equal to the image of B under f^{−1}. (So there is no ambiguity in using f^{−1}(B) for both).

(b) Let A ⊂ X. Show that the pre-image of A under f^{−1} is the same as the image of

f. That is (f^{−1})^{−1}(A) = f(A).

4. Let 𝒜 be a collection of subsets of X. Show that the following are equivalent: (a) U is a union of sets from 𝒜.

(b) For every x ∈ U there exists a set V_{x} ∈ 𝒜 such that x ∈ V_{x} ⊂ U.

5. Contemplate the following assertions about a map f : X → Y.

(a) f^{−1}(f(U)) = U for all U ⊂ X.

(b) f(f^{−1}(V)) = V for all V ⊂ Y. Give counter-examples to show that neither is true in general. Under what conditions on f is one or other of these assertions true?

February 7, 2003

Home page: http://www.maths.bath.ac.uk/~feb/math0055.html

M55: Exercise sheet 0—Solutions

1. When proving that two sets A and B are equal, we usually follow the time-honoured strategy of first showing that A ⊂ B and then showing that B ⊂ A. If, on the other hand, the assertion seems false, we cast around for counter-examples involving small sets.

(a) This is false: suppose that f is not injective and let a ≠ b ∈ X such that f(a) = f(b) = c ∈ Y. Let U = {a} and V = {b}. Then

f(U ∩ V) = f(∅) = ∅ ≠ f(U) ∩ f(V) = {c}.

This is the only thing that can go wrong: if f is injective then the assertion is true.

(b) This is true. First note that f(U), f(V) are both subsets of f(U ∪ V) so that their union is also contained in f(U ∪ V). For the converse, if y ∈ f(U ∪ V) then y = f(x) for some x ∈ U ∪ V. So x ∈ U or x ∈ V. That is f(x) is in f(U) or f(V). In other words y = f(x) ∈ f(U) ∪ f(V).

(c) This is true: if x ∈ f^{−1}(A ∩ B) then f(x) ∈ A ∩ B. Thus f(x) ∈ A and f(x) ∈ B. That is, x ∈ f^{−1}(A) and x ∈ f^{−1}(B). Otherwise said, x ∈ f^{−1}(A) ∩ f^{−1}(B) whence f^{−1}(A ∩ B) ⊂ f^{−1}(A) ∩ f^{−1}(B). Conversely, if x ∈ f^{−1}(A) ∩ f^{−1}(B) then x ∈ f^{−1}(A) and x ∈ f^{−1}(B). That is, f(x) ∈ A and f(x) ∈ B so that f(x) ∈ A∩B. This means x ∈ f^{−1}(A∩B) so that f^{−1}(A)∩f^{−1}(B) ⊂ f^{−1}(A ∩ B).

(d) This is also true: the same argument works replacing all occurrences of ∩ by ∪ and “and” by “or”. To spell it out: if x ∈ f^{−1}(A ∪ B) then f(x) ∈ A ∪ B. Thus f(x) ∈ A or f(x) ∈ B. That is, x ∈ f^{−1}(A) or x ∈ f^{−1}(B). Otherwise said, x ∈ f^{−1}(A) ∪ f^{−1}(B) whence f^{−1}(A ∪ B) ⊂ f^{−1}(A) ∪ f^{−1}(B). Conversely, if x ∈ f^{−1}(A)∪f^{−1}(B) then x ∈ f^{−1}(A) or x ∈ f^{−1}(B). That is, f(x) ∈ A or f(x) ∈ B so that f(x) ∈ A ∪ B. This means x ∈ f^{−1}(A ∪ B) so that f^{−1}(A) ∪ f^{−1}(B) ⊂ f^{−1}(A ∪ B).

(e) This is false: for f not surjective we can take U = ∅ and then f(X \ U) = f(X) ≠ Y = Y \ f(U). Even if f is surjective, things can still go wrong: suppose f is surjective but not injective and suppose a and b are distinct elements that map both to c. Let U = {a}. Then

f(X \ U) = f(X \ {a}) = f(X) ≠ f(X) \ {c} = Y \ {c} = Y \ f(U).

If, however, f is bijective there are no problems. (f ) This is true: x ∈ f^{−1}(Y \ B) if and only if f(x) ∉ B if and only if x ∉ f^{−1}(B) if and only

if x ∈ X \ f^{−1}(B). The punch-line is that the map U ↦ f(U) from 𝒫(X) to 𝒫(Y) does not respect the operations of set theory while the “pre-image map” A ↦ f^{−1}(A) from 𝒫(Y) to 𝒫(X) commutes with everything and so is an altogether nicer operation.

2. For the first law: x ∈ X \ ⋃_{i∈I} A_{i} if and only if x ∉ ⋃_{i∈I} A_{i} if and only if, for every i ∈ I, x ∉ A_{i} if and only if, for every i ∈ I, x ∈ X \ A_{i} if and only if x ∈ ⋂_{i∈I}(X \ A_{i}). For the second, x ∈ X \ ⋂_{i∈I} A_{i} if and only if x ∉ ⋂_{i∈I} A_{i} if and only if, for some i, x ∉ A_{i} if and only if, for some i, x ∈ X \ A_{i} if and only if x ∈ ⋃_{i∈I}(X \ A_{i}).

3. (a) The image of B under f^{−1} is the set {f^{−1}(y) : y ∈ B}. But this is equal to {x ∈ X : y =

f(x) ∈ B} which is the preimage of B under f.

(b) The preimage of A under f^{−1} is the set {y ∈ Y : f^{−1}(y) ∈ A}. But this is equal to {y ∈ Y : y = f(x) for some x ∈ A}. The last set is the image of A under f.

4. First we show (a) implies (b): let x ∈ U. Now U is a union of sets from 𝒜 so that x is contained in some V_{x} from this union.

Now for the converse. For each x ∈ U, choose some V_{x} ∈ 𝒜 such that x ∈ V_{x} and V_{x} ⊂ U. Then

U = ⋃_{x∈U}{x} ⊂ ⋃_{x∈U} V_{x} ⊂ U.

We must therefore have equality here so that U is a union of sets from 𝒜.

5. (a) This is true if and only if f is injective: if a ≠ b ∈ X with f(a) = f(b) = c, then, with U = {a}, we have f(U) = {c} and so {a, b} ⊂ f^{−1}(f(U)). Thus f^{−1}(f(U)) ≠ U. On the other hand, we clearly have U ⊂ f^{−1}(f(U)) and, if f is injective and x ∈ f^{−1}(f(U)) then f(x) ∈ f(U) so that, for some u ∈ U, f(x) = f(u). Now injectivity gives x = u so that x ∈ U and f^{−1}(f(U)) ⊂ U.

(b) This is true if and only if f is surjective: if y ∉ f(X) then, with V = {y}, we have f^{−1}(V) = ∅ so that f(f^{−1}(V)) = ∅ ≠ V. On the other hand, it is clear that f(f^{−1}(V)) ⊂ V and, if f is surjective and y ∈ V, there is some x ∈ X with f(x) = y so that x ∈ f^{−1}(V) giving y ∈ f(f^{−1}(V)).