I.2 · Foundations — Problem 2 #

← Back to I. Foundations, Problem 2

Problem. For a function \(f:X \to Y\), prove parts (b) and (c) of the image/inverse-image theorem — that \(f(A \cap B) \subseteq f(A) \cap f(B)\) and \(f(A \setminus B) \supseteq f(A) \setminus f(B)\) — and give a counterexample showing equality can fail in each case.

Hint #

For the inclusions, just chase an element through the definitions of image and of \(\cap\)/\(\setminus\). For the counterexamples, the inclusions that fail are exactly the ones where injectivity would be needed — so try a non-injective function such as \(f(x) = x^2\).

Solution #

Consider (b). To prove the inclusion \(f(A\cap B) \subseteq f(A)\cap f(B)\), take \(y \in f(A \cap B)\). By the definition of the image of a set under \(f\), there is an element \(x \in A \cap B\) with \(f(x)=y\). This \(x\) lies in \(A\), so \(y \in f(A)\); and it lies in \(B\), so \(y \in f(B)\). Hence \(y \in f(A) \cap f(B)\).

The other inclusion can fail. Take a function that is not injective, such as \(f(x)=x^2\), with \(A=[0,1]\) and \(B=[-1,0]\). Then \(A \cap B = \{0\}\) so \(f(A\cap B)=\{0\}\), whereas \(f(A)=f(B)=[0,1]\), giving \(f(A)\cap f(B)=[0,1]\neq\{0\}\). So equality does not hold in general.

Part (c) is handled in a very similar way.

Long solution #

Strategy. Both parts follow the same two-step plan. Each claimed inclusion is proved by element chasing: take an arbitrary element of the smaller set, translate what its membership means using the definition of the image, and reassemble the pieces into membership in the larger set. Then we must show that the reverse inclusions can fail. The proofs themselves reveal the obstruction: the reverse directions would require a single point of \(X\) to do two jobs at once, which only injectivity can guarantee. So for the counterexamples we take the simplest non-injective function, \(f(x) = x^2\), and place the sets \(A\) and \(B\) on opposite sides of \(0\), where \(f\) glues distinct points together.

Definitions used. For \(f : X \to Y\) and \(A \subseteq X\), the image of \(A\) is

$$ f(A) = \{\, y \in Y : y = f(x) \ \text{for some } x \in A \,\}. $$

So the statement “\(y \in f(A)\)” means exactly: there exists \(x \in A\) with \(f(x) = y\). It asserts that \(y\) has at least one preimage inside \(A\) — and different membership statements may be witnessed by different preimages. Recall also that \(x \in A \cap B\) means (\(x \in A\) and \(x \in B\)), that \(x \in A \setminus B\) means (\(x \in A\) and \(x \notin B\)), and that to prove an inclusion \(S \subseteq T\) we take an arbitrary \(y \in S\) and show \(y \in T\).

(b) The inclusion \(f(A \cap B) \subseteq f(A) \cap f(B)\).

Let \(y \in f(A \cap B)\) be arbitrary. By the definition of the image, there exists \(x \in A \cap B\) with \(f(x) = y\). Unpacking the intersection: \(x \in A\) and \(x \in B\).

• Since \(x \in A\) and \(f(x) = y\), this very \(x\) witnesses the existence statement “\(y = f(x)\) for some \(x \in A\)”; hence \(y \in f(A)\).
• Since \(x \in B\) and \(f(x) = y\), the same \(x\) witnesses “\(y = f(x)\) for some \(x \in B\)”; hence \(y \in f(B)\).

Both memberships hold, so \(y \in f(A) \cap f(B)\). As \(y \in f(A\cap B)\) was arbitrary, \(f(A \cap B) \subseteq f(A) \cap f(B)\). Note the logical shape of the argument: one point \(x\), lying in both sets, supplies a witness for each of the two image memberships separately. \(\blacksquare\)

The reverse inclusion can fail. Let \(f : \mathbb{R} \to \mathbb{R}\), \(f(x) = x^2\), and take \(A = [0,1]\), \(B = [-1,0]\).

The value \(y\) has a preimage \(a\) in \(B\) and a different preimage \(b\) in \(A\), but none in \(A \cap B = \{0\}\).

Here \(A \cap B = \{0\}\), so \(f(A \cap B) = \{0\}\). But \(f(A) = f(B) = [0,1]\), so \(f(A) \cap f(B) = [0,1]\), which is much larger than \(\{0\}\).

(c) The inclusion \(f(A \setminus B) \supseteq f(A) \setminus f(B)\).

Note carefully which way this one goes: the big set is \(f(A \setminus B)\). Let \(y \in f(A) \setminus f(B)\) be arbitrary. Unpacking the set difference, this means two things:

1. \(y \in f(A)\): there exists \(x \in A\) with \(f(x) = y\); and
2. \(y \notin f(B)\): the negation of an existence statement, i.e. no element of \(B\) is mapped to \(y\) — for every \(b \in B\) we have \(f(b) \neq y\).

We claim that the point \(x\) from item 1 satisfies \(x \notin B\). Suppose to the contrary that \(x \in B\); then \(x\) would be an element of \(B\) with \(f(x) = y\), directly contradicting item 2. So \(x \notin B\). Combining: \(x \in A\) and \(x \notin B\), i.e. \(x \in A \setminus B\), and \(f(x) = y\); therefore \(y \in f(A \setminus B)\). As \(y\) was arbitrary, \(f(A) \setminus f(B) \subseteq f(A \setminus B)\). \(\blacksquare\)

The reverse inclusion can fail. Again let \(f(x) = x^2\), now with \(A = [-1, 1]\) and \(B = [0, 1]\).

Every value attained on \(A \setminus B\) is also attained on \(B\).

Here \(A \setminus B = [-1, 0)\), so \(f(A \setminus B) = (0, 1]\). But \(f(A) = f(B) = [0,1]\), so \(f(A) \setminus f(B) = \varnothing\), which is strictly smaller than \((0,1]\).