Let $X$ and $Y$ be sets and let $f : P(X) \rightarrow P(Y)$. Prove the following: $$\forall A,B \subseteq X[f(A \cup B)=f(A) \cup f(B)] \text{ } \Rightarrow \text{ } \forall A,B \subseteq X[f(A \cap B) \subseteq f(A) \cap f(B)]$$

I wasn't sure how to start this problem so I went about proving (at least, I think I proved) the left and right sides.

Left side:

$x \in f(A \cup B)$

$\leftarrow \rightarrow x = f(c) \text{ for some } c \in A \text{ or } c \in B$

$\leftarrow \rightarrow x \in f(A) \text{ or } x \in f(B) \leftarrow \rightarrow x \in f(A) \cup f(B) \leftarrow \rightarrow f(A) \cup f(B)$

Right side:

$x \in f(A \cap B)$

$\rightarrow x = f(c) \text{ for some } c \in A \text{ and } c \in B$

$\rightarrow x \in f(A) \text{ and } x \in f(B) \rightarrow x \in f(A) \cap f(B) \rightarrow f(A) \cap f(B)$

After doing this I figured I would prove the left side implies the right side, but I can't seem to get it to click which way to do that or how to start. Am I on the right track? How would I continue if I am?

  • 1
    $\begingroup$ $f(A \cup B)=f(A) \cup f(B)$ and $f(A \cap B) \subseteq f(A) \cap f(B)$ are always true. They are not related. $\endgroup$ – Math Wizard Sep 29 '16 at 23:01
  • $\begingroup$ I'm not sure what you are getting at. I proved them just to get my brain warmed-up, and the question implies that the left implies the right. $\endgroup$ – Qwurticus Sep 30 '16 at 2:58
  • 1
    $\begingroup$ No, they are both well known theorems and are right independently $\endgroup$ – Math Wizard Sep 30 '16 at 4:05
  • $\begingroup$ @Qwurticus: Where did you get you propostion? $\endgroup$ – Moritz Oct 1 '16 at 15:02
  • $\begingroup$ @Moritz It was my a problem from my teacher's lecture notes, which we also use as our "book". I already turned the assignment in yesterday with an answer that I believe will get partial credit. When I get the assignment back I will answer my own question here if no one else can figure it out. $\endgroup$ – Qwurticus Oct 1 '16 at 17:25

Your Answer

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

Browse other questions tagged or ask your own question.