$f(S)^c \subseteq f(S^c)$, $\forall S\subseteq A$, if and only if $f\colon A\to B$ is surjective

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?

-
Can someone fix this text? –  AD. Nov 26 '10 at 4:54
How did you come across this? What did you try? –  AD. Nov 26 '10 at 4:54
@AD. Done. Also fixed the tags. –  Arturo Magidin Nov 26 '10 at 5:01
@AD.: This is my first edit of a question. Hope I did not change the meaning of the question. –  user17762 Nov 26 '10 at 5:02
@Sivaram: no, you didn't; you did undo most of my edits, though. (-; –  Arturo Magidin Nov 26 '10 at 5:10

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.

-

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

-
+1 Well said, I skip my text. :) –  AD. Nov 26 '10 at 5:22
I think if he can figure out this hint he'd have solved it on his own by now ;) –  Zarrax Nov 26 '10 at 6:29
@Zaricuse: Do you mean that you think this hint does not go far enough? –  Bill Dubuque Nov 26 '10 at 17:01

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$.

-
@Zaricuse: $S$ cannot equal $B$, as $S$ is a subset of $A$. You may also want to mention that "if $f$ is not surjective..." is the contrapositive of a statement in which he would have to prove that $f(A)=B$. –  Arturo Magidin Nov 26 '10 at 5:42
thanks, I corrected the typo.. I think I stated the "if $f$ is not surjective" part satisfactorily. –  Zarrax Nov 26 '10 at 5:44
@Zaricuse: For a hint one shouldn't reveal so much, esp. for questions which look like homework - where students are supposed to learn from the problem solving experience. –  Bill Dubuque Nov 26 '10 at 5:48
It's Thanksgiving, I'm feeling generous ;) (Normally I do give smaller hints than this.) –  Zarrax Nov 26 '10 at 5:52
alright, I shrunk the hint. –  Zarrax Nov 26 '10 at 6:00

(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.

-