The asymmetry in pushing and pulling sets

I’m going to begin by proving that $f$ and $f^{-1}$ both commute with unions, and then I’ll show that $f^{-1}$ commutes with intersections but $f$ doesn’t in general. It’ll turn out that it comes down to well-definedness (abbreviated WD) and how it interacts with unions and intersections, so I’ll be emphasizing the role of those things in the proofs.

Before going further, I’ll dispense with some trivial cases involving the empty set. If $\cup X_\alpha = \emptyset$ then each $X_\alpha = \emptyset$ so

$$
f(\cup X_\alpha) = f(\emptyset) = \emptyset = \cup_\alpha \emptyset = \cup_\alpha f(\emptyset) = \cup f(X_\alpha),
$$

and similarly if $\cup Y_\beta = \emptyset$ then

$$
f^{-1}(\cup Y_\beta) = f^{-1}(\emptyset) = \emptyset = \cup f^{-1}(\emptyset) = \cup f^{-1}(Y_\beta).
$$

For intersections, if $\cap X_\alpha = \emptyset$ then $f(\cap X_\alpha) = \emptyset$ so $f(\cap X_\alpha) \subseteq \cap f(X_\alpha)$. If instead $\cap Y_\beta = \emptyset$ then $f^{-1}(\cap Y_\beta) = \emptyset$ but also $\cap f^{-1}(Y_\beta) = \emptyset$ since if not then there’s some $x \in \cap f^{-1}(Y_\beta)$ which means $f(x) \in Y_\beta$ for all $\beta \in B$, and therefore $f(x) \in \cap Y_\beta$ which contradicts $\cap Y_\beta$ being empty. This means $\cap f^{-1}(Y_\beta) = \emptyset = f^{-1}(\cap Y_\beta)$. So without losing any generality I’ll assume $\cup X_\alpha$, $\cup Y_\beta$, $\cap X_\alpha$, and $\cap Y_\beta$ are all non-empty.

Unions

Result 1: $f$ commutes with unions

$f$ commuting with unions means $f(\cup X_\alpha) = \cup f(X_\alpha)$. Before I prove this, I want to think about what it means. I’ve got this big set $\cup X_\alpha$ in $\X$. An element $y \in \Y$ is hit by something in $\cup X_\alpha$ if and only if it is hit by something in some particular $X_\alpha$. Effectively the definition of the set-theoretic union is that $x \in \cup X_\alpha$ iff $x$ is in some particular $X_\alpha$. This will be very helpful as it lets me move back and forth between statements like “$\exists x \in X_\alpha : P(x)$” and “$\exists x \in \cup X_\alpha : P(x)$” for some property $P$.

I’ll now formally prove

$$
f\left(\bigcup_{\alpha \in A} X_\alpha \right) = \bigcup_{\alpha \in A}f(X_\alpha).
$$

Pf:
$$y \in f(\cup X_\alpha)$$

$$\iff \exists x \in \cup X_\alpha : f(x) = y$$

$$\iff \exists \alpha \in A\; \exists x \in \X : x \in X_\alpha \wedge f(x)=y$$

$$\iff \exists \alpha \in A : y \in f(X_\alpha)$$

$$\iff y \in \cup f(X_\alpha)$$

$\square$

In both directions that defining property of unions is what gave me the ability to move from there being an element mapped to $y$ in all of $\cup X_\alpha$ versus in some particular $X_\alpha$ and vice versa. The story is similar with $f^{-1}$ and unions.

Result 2: $f^{-1}$ commutes with unions

The intuition is similar to that of $f$: I’ve got some big set $\cup Y_\beta\subseteq \Y$ and I want to think of the $x \in \X$ that map to this set. A given $x$ is mapped to $\cup Y_\beta$ if and only if it’s mapped to some particular $Y_\beta$ so again it comes down to the cooperation between “$\exists$” and unions.

Claim: for the collection $\{Y_\beta : \beta \in B\}$,
$$
f^{-1}\left(\bigcup_{\beta \in B} Y_\beta \right) = \bigcup_{\beta \in B}f^{-1}(Y_\beta).
$$

Pf:
$$x \in f^{-1}(\cup Y_\beta)$$

$$\iff \exists y \in \cup Y_\beta : f(x) = y$$

$$\iff \exists \beta \in B \; \exists y \in \Y : y \in Y_\beta \wedge f(x) = y$$

$$\iff \exists \beta \in B : x \in f^{-1}(Y_\beta)$$

$$\iff x \in \cup f^{-1}(Y_\beta)$$

$\square$

I deliberately wrote this proof to show how every bit of logic is the same as in the proof for $f$, and well-definedness has not yet appeared. The only difference WD has made so far is that in Result 1 there may be many $x$ in any particular $X_\alpha$ (and also $\cup X_\alpha$) such that $f(x) = y$, while for Result 2 I start with an $x \in \X$ so there is actually just one $y \in \Y : f(x) = y$ by WD. But this distinction didn’t matter for the proof because in every case I just needed there to be at least one such element.

Intersections

Result 3: $f^{-1}$ commutes with intersections

Now think about some $x \in \X$ that maps into $\cap Y_\beta$. Then necessarily $x$ maps into $Y_\beta$ for all $\beta \in B$ (and now intersections have changed things from “$\exists \beta \in B$” to “$\forall \beta \in B$”). If $x$ maps into each $Y_\beta$ then $x$ hits some $y$ in each $Y_\beta$, but by WD $x$ only hits a single element of $\Y$ so in fact $x$ hits something in $\cap Y_\beta$.

The claim:
$$
f^{-1}\left(\bigcap_{\beta \in B} Y_\beta \right) = \bigcap_{\beta \in B}f^{-1}(Y_\beta).
$$

Pf:
$$x \in f^{-1}(\cap Y_\beta)$$

$$\iff f(x) \in \cap Y_\beta$$

$$\iff \forall \beta \in B \; f(x) \in Y_\beta$$

$$\iff \forall \beta \in B \; x \in f^{-1}(Y_\beta)$$

$$\iff x \in \cap f^{-1}(Y_\beta)$$

$\square$

WD appears when starting with $x\in\cap f^{-1}(Y_\beta)$ and is what lets me go from every $Y_\beta$ having some element hit by $x$ to concluding that it’s the same element in every case so $\cap Y_\beta$ in fact has such an element (namely $f(x)$). This will fail for $f$.

Result 4: $f$ does not necessarily commute with intersections

Claim:
$$
f\left(\bigcap_{\alpha \in A} X_\alpha\right) \subseteq \bigcap_{\alpha \in A} f(X_\alpha) \tag{2.2}
$$
but equality does not necessarily hold.

This is saying that I can always push $\cap X_\alpha$ to being within every $f(X_\alpha)$ but I can’t guarantee that it’s equal. Very intuitively, WD means that $f$ can’t “enlarge” a set because I can have at most as many unique image points as domain points, so if I start with a “small” set like $\cap X_\alpha$ it’s easy to end up with an even smaller set, while first getting all of the images $f(X_\alpha)$ can possibly lead to a larger overlap. This also suggests that the injectivity of $f$ is something to consider as this determines $f$’s ability to “shrink” a set.

Pf of result:

$$y \in f(\cap X_\alpha)$$

$$\iff \exists x \in \cap X_\alpha : f(x) = y$$

$$\iff \exists x \in \X : \forall \alpha \in A \; x \in X_\alpha \wedge f(x) = y$$

$$\implies \forall \alpha \in A \; y \in f(X_\alpha)$$

$$\iff y \in \cap f(X_\alpha)$$

$\square$

The most important thing to note is the 4th line where the “iff” changes to just an implication, and this is because with intersections I can go from $\exists x \in \cap X_\alpha : P(x)$ to $\forall \alpha \in A \exists x \in X_\alpha : P(x)$, but I can’t count on being able to go the other way. I can definitely have a collection of sets where every $X_\alpha$ has an $x_\alpha : P(x_\alpha)$, but $\cap X_\alpha$ has no such $x$. Just as an example of this kind of thing, I could take $\X = \mathbb N$ and $P(x) = 2|x$. Then let $\mathcal O=\{1,3,5,\dots\}$ denote the odd natural numbers, and set $X_\alpha = \mathcal O \cup \{2 \alpha\}$ for $A = \mathbb N$. Then it is true that $\forall \alpha \in A \exists x \in X_\alpha : P(x)$ yet $\cap X_\alpha = \mathcal O$ and that set has no element that satisfies $P$.

So just to re-emphasize, when I started in $f(\cap X_\alpha)$ I could conclude that there is a common $x$ in every $X_\alpha$ that satisfies the property $f(x)=y$, but when I started with $y \in \cap f(X_\alpha)$ there can be many $x \in \X$ that map to one $y$, so there’s no guarantee that a single one of these $x_\alpha$ appears in $\cap X_\alpha$. With unions this didn’t come up because existence in a union is equivalent to existence in a set that the union is over.

The thing that would save this is if $f$ is injective, which would force all of these $x_\alpha$ to actually just be one element, and then I’d have a single element in every $X_\alpha$ and therefore in $\cap X_\alpha$.

This leads me to my final result:

Result 5: Guaranteeing that $f$ commutes with intersections

Claim:
$$
\forall \{X_\alpha\} \;f(\cap X_\alpha) = \cap f(X_\alpha) \iff f \text{ is an injection}.
$$

Pf:

First, note that $f(\cap X_\alpha) \subseteq \cap f(X_\alpha)$ regardless of the injectivity of $f$ so really I only need to show $f(\cap X_\alpha) \supseteq \cap f(X_\alpha)$ in each direction.

$(\implies)$ by contrapositive: if $f$ is not an injection then the result will not hold. So suppose $\exists x \neq z \in \X$ with $y := f(x)=f(z)$. Consider $X_1 = \{x\}$ and $X_2=\X \backslash \{x\}$. Then
$$
f(X_1 \cap X_2) = f(\emptyset) =\emptyset \neq \{y\} = f(X_1) \cap f(X_2).
$$

$(\impliedby)$ Suppose $f$ is an injection and let $y \in \cap f(X_\alpha)$. Then

$$\forall \alpha \in A \; y \in f(X_\alpha)$$

$$\implies \forall \alpha \in A \; \exists x_{\alpha} \in X_\alpha : f(x_\alpha) =y.$$

But now by injectivity all these $x_\alpha$ are actually the same element, say $x$, so I have

$$\exists x \in \X : \forall \alpha \in A \; x \in X_\alpha \wedge f(x) = y$$

$$\implies \exists x \in \cap X_\alpha : f(x) = y$$

$$\implies y \in f(\cap X_\alpha)$$

$\square$

Conclusion