2
$\begingroup$

Let $f:A \rightarrow B$.

The complements indicated below are taken within $A$ or $B$.

I need to prove that $f(S)^c \subseteq f(S^c)$, $\forall S \subseteq A$, if and only if $f$ is surjective.

So I need to prove $f(A) = B$ right?

How can I prove this?

  • 0
    @Sivaram: You had no way of knowing. It is clear we were editing at the same time; you just saved your edits a bit after mine. The obliteration occurred automatically. Unless you got the banner on top saying the post had been edited (which you likely didn't given the time window) there was nothing you could have done to figure it out.2010-11-27

4 Answers 4

3

You want to prove two things:

  1. If the complement of the image is always contained in the image of the complement, then $f(A)=B$; and

  2. If $f(A)=B$, then for every subset $S$ of $A$ you have that the complement of the image is contained in the image of the complement.

So, "I have to prove that $f(A)=B$" is only true for half of the problem at issue.

As to how you prove 1 above, well, since the containment holds for all subsets $S$ of $A$, perhaps you can pick a particular subset $S$ of $A$ in some clever way that will tell you that $f(A)$ must be equal to $B$. (HINT: $f(A)=B$ if and only if $f(A)^c$ is... )

For 2, you have to assume that $f(A)=B$ (that $f$ is surjective). Then you need to take an arbitrary subset $S$ of $A$. Then to test whether $f(S)^c\subseteq f(S^c)$ holds, you need to take an arbitrary $b\in f(S)^c$, and show that it must lie in $f(S^c)$; that is, that there exists some $a\notin S$ such that $b=f(a)$. Now go to it.

2

HINT $\rm\ (\Rightarrow)\ $ Put $\rm S\ =\ \ldots\ \ (\Leftarrow)\ $ Consider $\rm\ {\overline {f(S)}} \cap (f(S) \cup f(\overline S))$

  • 0
    @Zaricuse: Do you mean that you think this hint does not go far enough?2010-11-26
2

You need to prove more than that $f(A) = B$. You need to show that if $f$ is surjective, then $(f(S))^c \subset f(S^c)$ for every possible subset $S$ of $A$, and that if $f$ is not surjective, then there is some $S$ for which $(f(S))^c$ is not a subset of $f(S^c)$.

Largish hint for the first part: If $f$ is surjective then $f(S) \cup f(S^c)$ is all of $B$, regardless of what $S$ is. Use this to prove the contrapositive of the first part.

Hint for the second part: Pick a special subset $S$ of $A$ and show it works for that $S$.

  • 0
    @Zaricuse: Yes, there is nothing wrong in what you stated; I guess my point is that you first start by saying he needs to "prove more than that $f(A)=B$", but then the hints you give are such that he *never* proves $f(A)=B$ at all (let alone, proving *more* than that fact). I feared it might engender some confusion.2010-11-27
0

(I assume it is OK to post a full solution to what was long ago probably a homework question.)

Let me provide a complete (but perhaps overly long-winded) proof which does not use separate $\Rightarrow$ and $\Leftarrow$ parts, but only equivalences.

The most complex part seems to be $f[S]^c \subseteq f[S^c]$, so let's try to simplify that: for any $S \subseteq A$, $ \begin{align} & f[S]^c \subseteq f[S^c] \\ \equiv & \;\;\;\;\;\text{"definition of $\subseteq$"} \\ & \langle \forall y :: y \in f[S]^c \Rightarrow y \in f[S^c] \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $^c$, which means $B$-complement here"} \\ & \langle \forall y :: y \in B \land y \not\in f[S] \Rightarrow y \in f[S^c] \rangle \\ \equiv & \;\;\;\;\;\text{"logic: rearrange to bring both occurrences of $f[\cdot]$ together"} \\ & \langle \forall y :: y \in B \Rightarrow y \in f[S] \lor y \in f[S^c] \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\cup$ -- since we know distribution properties of $\cdot[\cdot]$"} \\ & \langle \forall y :: y \in B \Rightarrow y \in f[S] \cup f[S^c] \rangle \\ (*) \; \equiv & \;\;\;\;\;\text{"$f[\cdot]$ distributes over $\cup$"} \\ & \langle \forall y :: y \in B \Rightarrow y \in f[S \cup S^c] \rangle \\ \equiv & \;\;\;\;\;\text{"set theory: basic property of $^c$, which here means $A$-complement"} \\ & \langle \forall y :: y \in B \Rightarrow y \in f[A] \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\subseteq$"} \\ & B \subseteq f[A] \\ \equiv & \;\;\;\;\;\text{"using $f[S] \subseteq B$ for any $S$, since the range of $f$ is $B$"} \\ & B = f[A] \\ \equiv & \;\;\;\;\;\text{"one of the definitions of surjectivity, using $f : A \to B$"} \\ & f \textrm{ is surjective} \\ \end{align} $

Now formally wrapping up, we have $ \begin{align} & \langle \forall S :: f[S]^c \subseteq f[S^c] \rangle \\ \equiv & \;\;\;\;\;\text{"by the above calculation"} \\ & \langle \forall S :: f \textrm{ is surjective} \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify: $S$ does not occur inside $\forall S$"} \\ & f \textrm{ is surjective} \\ \end{align} $ which proves the statement in question.

The key step was $(*)$, and this is the most 'creative' part in an otherwise fairly mechanical proof, provided one is familiar with logic and the definitions and basic properties of set theory and functions.