Lemmas for Functions on Sets

We discuss some lemmas for functions on sets, which I wrote up some time ago to clarify and better understand the nature of $f^{- 1}(S)$ .

For any function (not just invertible) and for any sets $S,T$ , is $f(S) = T$ equivalent to $S = f^{- 1}(T)$ ?

Left-to-right: assume $f(S) = T$ , so $T = \left\{ f(s):s \in S \right\}$ , and put $U = f^{- 1}(T) = \left\{ u:f(u) \in T \right\}$ . We WTS $S = U$ . If $x \in S$ , then by definition of $T$ , $f(x) \in T$ , so then $x \in U$ . If $x \in U$ , then $f(x) \in T$ , so $f(x) = f(s)$ for some $s \in S$ . Is it possible that $x$ can be chosen outside of $S$ ? It seems like it can be for a non-injective $f$ . Let’s make this concrete: $f(x) = x^{2}$ , $S = \lbrack 0,1\rbrack$ , then $T = f(S) = \lbrack 0,1\rbrack = S$ , but $f^{- 1}(T) = \lbrack - 1,1\rbrack \neq S$ . Thus, this isn’t necessarily true if $f$ is non-injective. If $f$ is injective, then the LTR works. Thus, it is not generally the case that $S = f^{- 1}\left( f(S) \right)$ (a restatement of LTR.) We do however always have $S \subseteq f^{- 1}\left( f(S) \right)$ , with equality if $f$ is injective. In fact, we can say $\forall S\left( S \subseteq f^{- 1}\left( f(S) \right) \right)$ with equality if and only if $f$ is injective, since if $f$ is not injective we can always find $a \neq b$ with $f(a) = f(b)$ , and then just pick $S$ so that $a \in S$ and $b \notin S$ .

I suspect that $f$ must be surjective for RTL to work, with a similar inequality and an equality condition of surjectivity. Indeed, I suspect a reverse inequality: $f\left( f^{- 1}(S) \right) \subseteq S$ . Let us prove this. Let $x \in f\left( f^{- 1}(S) \right)$ , so that there exists $y \in f^{- 1}(S)$ with $x = f(y)$ . Then, by definition of $y \in f^{- 1}(S)$ , $f(y) \in S$ , and $x = f(y) \in S$ . But in the other direction, let $x \in S$ , and assume $f$ is surjective. Then, by surjectivity of $f$ , exists $y$ with $f(y) = x$ , so $y \in f^{- 1}(S)$ . Thus, $x = f(y) \in f\left( f^{- 1}(S) \right)$ . But if $f$ is not surjective, then we can choose $S$ that has an $x$ such that $x$ is not the image of any $y$ by $f$ , or $x \notin f(U)$ for any $U$ . Then there is no way that $x \in f\left( f^{- 1}(S) \right)$ , and thus we have inequality.

Written April 28, 2022.

Share and like (need WordPress account to like):

Leave a comment Cancel reply