Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
How to prove that $f(\emptyset)=\emptyset$ for $f: X \rightarrow Y$?
I already have these:
Two things to prove: $f(\emptyset) \subseteq \emptyset$ and $\emptyset \subseteq f(\emptyset)$.
First prove that $\emptyset \subseteq f(\emptyset)$: Suppose $x \in \emptyset$, than $x \in f(\emptyset)$ so $\emptyset \subseteq f(\emptyset)$.
But how can I prove that the subset of the function applied to the empty set is a subset of the empty set?
Regards, Kevin
The empty set is a subset of every set, since $x\in\emptyset \Rightarrow x\in A$ holds trivially because no $x$ satisfies $x\in\emptyset$.
It's the other direction you should worry about, and your proof is wrong. If $x\in\emptyset$ it does not imply that $x\in f(\emptyset)$ - why should it? Moreover, even if it were, you show here that $\emptyset \subseteq f(\emptyset)$ and not vice versa.
In the other direction, assume that $y\in f(\emptyset)$. So by definition there is $x\in\emptyset$ such that $f(x)=y$. However, this is a contradiction, so there is no $y\in f(\emptyset)$ (and hence $f(\emptyset)=\emptyset$). Note that this direction is really all you need.
Let $f:X\ \to\ Y$ be a function. Recall that $f$ induces a function $f:P(X)\ \to\ P(Y)$. To prove that $f[\emptyset]\ =\ \emptyset$. We usually prove the two inclusions: $\ \ \emptyset\ \subseteq\ f[\emptyset]\ \hbox{and}\ f[\emptyset]\ \subseteq\ \emptyset$.
The first inclusion $\emptyset\ \subseteq\ f[\emptyset]$ is always true. Then it suffices only to prove the inclusion $f[\emptyset]\ \subseteq\ \emptyset$. To do this, we must show that the implication $\ \ z\ \in\ f[\emptyset]\ \longrightarrow\ z\ \in\ \emptyset$ is not false for an arbitrary $z$.
The above implication is false if and only if its antecedent $\ z\ \in\ f[\emptyset]\ $ is true and its consequent $z\ \in\ \emptyset$ is false.
But the consequent $\ z\ \in\ \emptyset\ $ is clearly false and so the implication $z\ \in\ f[\emptyset]\ \longrightarrow\ z\ \in\ \emptyset$ can only be true if its antecedent $z\ \in\ f[\emptyset] $ is false.
But $z\ \in\ f[\emptyset]$ is false only if there are no elements in $f[\emptyset]$; consequently, this means that the set $f[\emptyset]$ must be empty; and so $f[\emptyset]\ =\ \emptyset$.
\Longrightarrow instead of \longrightarrow, you produce $\Longrightarrow$. Otherwise, nice proof.
$\endgroup$
Oct 23, 2012 at 18:28
Try the contrapositive: if $A\subseteq X$ and $f(A)\ne \emptyset$ then $A\ne \emptyset$. Indeed, let $b\in f(A)$. Then there is $a\in A$ such that $b=f(a)$. In particular, $A\ne \emptyset$.
The trouble with this question is that $f(\emptyset)$ is ambiguous. Is it the unique $y$ such that $(\emptyset,y)\in f$ (when we treat $\emptyset$ as an element of $X$)? Or is it $\{y:\exists x \in \emptyset | (x,y)\in f\}$ (when we treat $\emptyset$ as a subset of $X$)?
To a human mathematician, it's clear which meaning is intended here. But there might be contexts where the meaning is ambiguous, and I don't know of any notation that would dispel the ambiguity. Anyone?
$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \text{"#2"} \\ \quad & } \newcommand{\endcalc}{\end{align}} $Here is a proof where both directions are proved at the same time. Note that for clarity I'll write $\;f[X]\;$ instead of $\;f(X)\;$ for subsets $\;X\;$.
Let's compute which $\;y\;$ are elements of $\;f[\emptyset]\;$. So we calculate for any $\;y\;$:
$$\calc y \in f[\emptyset] \calcop{\equiv}{definition of $\;\cdot[\cdot]\;$} \langle \exists x :: x \in \emptyset \;\land\; f(x) = y \rangle \calcop{\equiv}{definition of $\;\emptyset\;$} \langle \exists x :: \text{false} \;\land\; f(x) = y \rangle \calcop{\equiv}{logic: simplify} \langle \exists x :: \text{false} \rangle \calcop{\equiv}{logic: simplify} \text{false} \endcalc$$
In other words (by the definition of $\;\emptyset\;$), $\;f[\emptyset] = \emptyset\;$.
Of course I spelled out the logic part for clarity's sake, but in practice I would take the last three steps together, leading to a short and clear proof of both directions at the same time.
Thanks, I now have this, is this legal?
Suppose $y \in f(\emptyset)$, than $\exists x \in \emptyset : f(x) = y$ But such an $x$ does not exists. So by contradiction, there is no $y \in f(\emptyset)$, so $f(\emptyset)$ must be empty and therefor $f(\emptyset)=\emptyset$.
