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
    Can someone fix this text?2010-11-26
  • 0
    How did you come across this? What did you try?2010-11-26
  • 0
    @AD. Done. Also fixed the tags.2010-11-26
  • 0
    @AD.: This is my first edit of a question. Hope I did not change the meaning of the question.2010-11-26
  • 3
    @Sivaram: no, you didn't; you did undo most of *my* edits, though. (-;2010-11-26
  • 0
    @Arturo Magidin: @Sivaram: Maybe we could replace $\bar{X}$ by $X^c$ too?2010-11-26
  • 0
    @Arturo Magidin: @Sivaram: BTW... Thanks. :)2010-11-26
  • 0
    @AD. *I* had used $X^c$; but apparently Sivaram was editing at the same time (his edit was saved one minute after mine) which superseded my edits. I've taken the liberty of going back to it now, and of fixing the misspelling (I'm pretty sure Bradley did not mean he was saying good things about the sets).2010-11-26
  • 0
    @Arturo Magidin: We have been here before, have we not :) It really is a problem that there is no source control. I should add that to meta!2010-11-26
  • 0
    @Arturo Magidin: Please up-vote my post in Meta http://meta.math.stackexchange.com/questions/1223/source-control-of-posts so that they might listen and do something. :)2010-11-26
  • 0
    @Arturo: ok. I shall be careful from hereon.2010-11-27
  • 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
    I think if he can figure out this hint he'd have solved it on his own by now ;)2010-11-26
  • 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: $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$.2010-11-26
  • 0
    thanks, I corrected the typo.. I think I stated the "if $f$ is not surjective" part satisfactorily.2010-11-26
  • 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.2010-11-26
  • 0
    It's Thanksgiving, I'm feeling generous ;) (Normally I do give smaller hints than this.)2010-11-26
  • 0
    alright, I shrunk the hint.2010-11-26
  • 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.