5
$\begingroup$

I haven't been able to do this exercise:

Let $f: A \rightarrow B$ be any function. $f^{-1}(X)$ is the inverse image of $X$. Demonstrate that if $f$ is surjective then $X = f(f^{-1}(X))$ where $X \subseteq B$.

Since $X \subseteq B$, all the elements in $X$ belong to the codomain of $f$.

Since $f$ is surjective, it means that all elements in the codomain $B$ have some preimage in $A$. Given that $X \subseteq B$, all elements in $X$ must also have a preimage in $A$.

Have $\triangle = f^{-1}(X)$, $\triangle$ is now a set containing the preimages of the elements in $X$. Because of this, $\triangle \subseteq A$.

If we evaluate $f(\triangle)$, we...... nope, I don't know what I'm doing now.


What do you think?

$\endgroup$
4
$\begingroup$

In this cases double inclusion is the way: let $x \in f(f^{-1}(X))$, then there is $a \in f^{-1}(X)$ such that $f(a) = x$. By definition of the pre image, $x \in X$. This gives $$f(f^{-1}(X)) \subset X.$$ Note that we didn't use that the function is surjective to prove this inclusion, meaning that it holds in general.

Now let $x \in X$. Being $f$ surjective, we can find $a \in A$ such that $f(a) = x$. This gives $a \in f^{-1}(X)$ and hence $x = f(a) \in f(f^{-1}(X))$. This shows $$X \subset f(f^{-1}(X)).$$

$\endgroup$
  • 1
    $\begingroup$ One easy way to remember this is to notice that $f(f^{-1}(X))=X \cap f(A) \subseteq X$, with equality if $f$ is surjective. $\endgroup$ – Watson Feb 14 '16 at 15:13
  • $\begingroup$ Leap in logic. More steps to prove you know what youre talking about would be great. $\endgroup$ – CogitoErgoCogitoSum Jan 9 '18 at 22:14
2
$\begingroup$

Here is how I would do this: go to the element level, expand the definitions and basic properties, and use logic to simplify. Start with the most complex expression, which is here $\;f[f^{-1}[X]]\;$.

So for any $\;b\;$, \begin{align} & b \in f[f^{-1}[X]] \\ \equiv & \;\;\;\;\;\text{"basic property of $\;\cdot[\cdot]\;$"} \\ & \langle \exists a : a \in f^{-1}[X] \;\land\; f(a) = b \rangle \\ \equiv & \;\;\;\;\;\text{"basic property of $\;\cdot^{-1}[\cdot]\;$"} \\ & \langle \exists a :: f(a) \in X \;\land\; f(a) = b \rangle \\ \equiv & \;\;\;\;\;\text{"logic: use right conjunct in left to substitute"} \\ & \langle \exists a :: b \in X \;\land\; f(a) = b \rangle \\ \equiv & \;\;\;\;\;\text{"logic: extract conjunct which does not use $\;a\;$ out of $\;\exists a\;$"} \\ & b \in X \;\land\; \langle \exists a :: f(a) = b \rangle \\ \equiv & \;\;\;\;\;\text{"assumption: $\;f\;$ is surjective, i.e., $\;\langle \forall b :: \langle \exists a :: f(a) = b \rangle \rangle\;$"} \\ & b \in X \\ \end{align} By set extensionality this proves the statement in question.

Strongly related: the proof of (4) in an answer of mine to another question (https://math.stackexchange.com/a/434230/11994).

$\endgroup$
0
$\begingroup$

I thought to provide some intuition by virtue of a picture. As drawn, $f$ is NOT surjective, because:

$a \in$ set X. $b, c \in$ set $Y.$ Your $X$ is my $S$ and $S \subsetneq Y$ here.

The pink bespeaks both $f^{-1}(S)$ and $f: X \to Y$ defined by $f(a) = b$. The green point is $c \in Y$.

Then $f(f^{-1}(\{c\}))=f(\varnothing)=\varnothing\neq\{c\}\quad\text{and}\quad f(f^{-1}(Y))=f(\{a\})=\{b\}\neq Y$.

Yet, espy that if I extend/stretch $f(X)$ (in pink inside $S$) to "cover" all of $Y$, then $f(X) = Y$.
By virtue of the definition of surjectivity, this mans $f$ is surjective.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.