0
$\begingroup$

For homework, I have to proof that, for $f: M \rightarrow N$, $M_1, M_2 \subseteq M$ and $N_1,N_2 \subseteq N$, $f(M_1 \cup M_2) = f(M_1) \cup f(M_2)$ which seemed easy at first since

$f(M_1) \cup f(M_2)\\ = \{ y \in N | x \in M_1 \land y = f(x) \} \cup \{y\in N | x \in M_2 \land y = f(x)\} = \{y \in N | (x \in M_1 \land y = f(x)) \lor (x \in M_2 \land y = f(x) \} = \{y \in N | (x \in M_1 \lor x \in M_2) \land y=f(x)\}\\ = f(M_1 \cup M_2)$.

However, the next task was to proof or disproof $f(M_1 \cap M_2) = f(M_1) \cap f(M_2)$ which can be done by providing an example: $f: x \rightarrow 0$, $f(\{1\} \cap \{1\}) = f(\emptyset) = \emptyset \neq \{0\} = f(\{1\}) \cap f(\{2\})$. But one could still apply the first proof and replace $\cup$ by $\cap$ and $\lor$ by $\land$:

$f(M_1) \cap f(M_2)\\ = \{ y \in N | x \in M_1 \land y = f(x) \} \cap \{y\in N | x \in M_2 \land y = f(x)\} = \{y \in N | (x \in M_1 \land y = f(x)) \land (x \in M_2 \land y = f(x) \} = \{y \in N | (x \in M_1 \land x \in M_2) \land y=f(x)\}\\ = f(M_1 \cap M_2)$.

Obviously, we know have a right looking "proof" for something which already has been proven wrong. After some hours of thinking with my classmates, we still haven't found our fallacy. If you do not want to do our homework, simply pointing out our error would be enough :)

$\endgroup$
1
  • 1
    $\begingroup$ You simply forgot the existential quantifier: it is not necessarily the same $x$ which belongs to $M_1$ and to $M_2$. $\endgroup$ – Bernard Nov 6 '18 at 12:50
1
$\begingroup$

The very first statement in your first proof is wrong:

$f(M_1) \cup f(M_2)= \{ y \in N | x \in M_1 \land y = f(x) \} \cup \{y\in N | x \in M_2 \land y = f(x)\}$

The right-hand side depends on $x$, so it cant be equal to the left-hand side, which doesn't depend on $x$. You have to say:

$f(M_1) \cup f(M_2)= \{ y \in N\;|\;\exists x \in M_1 \text{ such that } y = f(x) \} \cup \{y\in N\;|\; \exists x \in M_2 \text{ such that } y = f(x)\}$

The two instances of $x$ can be different here; perhaps it is clearer to put

$f(M_1) \cup f(M_2)= \{ y \in N\;|\;\exists x \in M_1 \text{ such that } y = f(x) \} \cup \{y\in N\;|\; \exists z \in M_2 \text{ such that } y = f(z)\}$

But anyway it is more complicated than you thought!

$\endgroup$

Your Answer

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

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