Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
3  
@Sivaram: no, you didn't; you did undo most of my edits, though. (-; –  Arturo Magidin Nov 26 '10 at 5:10
show 7 more comments

4 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
    
+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
add comment

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

share|improve this answer
    
@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
1  
@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
show 1 more comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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