8
$\begingroup$

How to proof that $f(\emptyset)=\emptyset$ for $f: X \rightarrow Y$? I already have this:

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 to prove that the subset of the function applied to the empty set is a subset of the empty set?

Regards, Kevin

|cite|improve this question
$\endgroup$
  • $\begingroup$ Sorry, I wrote it down the wrong way. I have already proven that, but now the other way remains ($f(\emptyset) \subseteq \emptyset$) $\endgroup$ – www.data-blogger.com Sep 15 '11 at 15:26
  • 1
    $\begingroup$ be careful writing your proof that "$\emptyset\subset f(\emptyset)$" because, I may be wrong here, but to me "suppose $x\in\emptyset$" is assuming a contradiction. For me, a better way would be to say something along the lines of, "Since $\emptyset$ has no elements, the conditions that every element of $\emptyset$ is an element of $f(\emptyset)$ holds vacuously." $\endgroup$ – Deven Ware Sep 15 '11 at 15:49
  • 6
    $\begingroup$ @Deven I find the argument correct. Remember that to prove $\emptyset \subseteq A$, we need to prove the implication "If $x \in \emptyset$, then $x \in A$". One need not worry whether the premise $x \in \emptyset$ itself holds or not. $\endgroup$ – Srivatsan Sep 15 '11 at 16:04
  • $\begingroup$ @Srivatsan would you read my comment on one of the answers and let me know your thoughts? I don't understand why are asserting contradictions. $\endgroup$ – mathmath8128 Sep 15 '11 at 16:07
  • $\begingroup$ @Srivatsan You are correct that we need implication. But suppose that we assume $x\in\emptyset$. Then this means the $\emptyset$ is non-empty, then there I see no implication that $x\in f(\emptyset)$ only that $f(x)\in f(\emptyset)$ for example what if the map is defined by $x\mapsto i$ for all $x$ then clearly $x\in\emptyset$ will map to $i$ and $f(\emptyset) = i$, thus $x\notin f(\emptyset)$. $\endgroup$ – Deven Ware Sep 15 '11 at 16:14
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks, I wrote it down the wrong way. So I still need to prove that $f(\emptyset) \subseteq \emptyset$ $\endgroup$ – www.data-blogger.com Sep 15 '11 at 15:29
  • $\begingroup$ Ok, added the solution. $\endgroup$ – Gadi A Sep 15 '11 at 15:40
  • 2
    $\begingroup$ @Gadi: Good answer, but there are a few lines that have fairly minor typos. For example " If $x\in\emptyset$ it does not imply that $x\in f(\emptyset)$ - why should it?" I am not sure what you mean, this is the same trivial implication which appears in the first line of your response. Also "So by definition there is $x\in\emptyset$ such that $f(x)=y$. However, this is a contradiction, so there is no $y\in\emptyset$." I think you there is no $x\in \emptyset$ rather than $y$. $\endgroup$ – Eric Naslund Sep 15 '11 at 17:02
  • $\begingroup$ What I meant is that in general $x\in A$ does not mean $x\in f(A)$, so additional justification is needed. As to the second part - because of the contradiction (which is, indeed, that no suitable $x$ exists) we come to the conclusion, which is that there is no $y$. $\endgroup$ – Gadi A Sep 15 '11 at 17:15
  • $\begingroup$ (-1) The statement $x\in\emptyset \implies x\in A$ is true, so your assertion "If $x\in\emptyset$ it does not imply that $x\in f(\emptyset)$" is just false $\endgroup$ – Masacroso Jun 17 at 6:43
4
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ If you use \Longrightarrow instead of \longrightarrow, you produce $\Longrightarrow$. Otherwise, nice proof. $\endgroup$ – Pragabhava Oct 23 '12 at 18:28
3
$\begingroup$

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

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ It's a good point, and I'd be interested to know if there is anything standard. Locally, one could just adorn $f$ somehow to indicate that the image map on the power set rather than $f$ itself is being applied, in cases where context does not make it clear that the input is being considered as a subset of the domain rather than an element of the domain (and of course define the notation). E.g., for $A\subseteq X$, define $\tilde{f}(A)\subset Y$ to be $\{y\in Y:\exists x \in A | (x,y)\in f\}$. A related notational question arose at math.stackexchange.com/questions/63374. $\endgroup$ – Jonas Meyer Sep 15 '11 at 17:30
  • 5
    $\begingroup$ @Jonas: I consider the notation $f[A]=\{f(x):x\in A\}$ standard, though it seems not to be universally known. (Perhaps set theorists and point-set topologists use it most?) In some set-theoretic contexts $f"A$ is used. $\endgroup$ – Brian M. Scott Sep 15 '11 at 21:30
0
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Yes, that argument would prove it, but you should try to avoid the use of $\exists$ in a proof. It would make more sense to say something like "Suppose for contradiction that we can take $y\in f(\emptyset)$, it then follows that we can choose some $x\in\emptyset$ such that $f(x) = y$. However, this contradicts the fact that $x\notin\emptyset$ for all $x$. $\Box$" $\endgroup$ – Deven Ware Sep 15 '11 at 15:54
  • $\begingroup$ I don't think it's a contradiction. You have a false hypothesis when you assert $x\in\emptyset$. A false hypothesis leads automatically to a true conclusion vacuously. $\endgroup$ – mathmath8128 Sep 15 '11 at 16:01
  • $\begingroup$ @aengle: We are assuming for contradiction that $f(\emptyset)$ is non-empty. This assumption then implies that there is some $x\in\emptyset$ which is the contradiction. And hence, $f(\emptyset)$ must be empty $\endgroup$ – Deven Ware Sep 15 '11 at 16:10
  • $\begingroup$ @Deven Okay, that makes sense. Thanks $\endgroup$ – mathmath8128 Sep 15 '11 at 16:15
  • $\begingroup$ See my answer on how to avoid a contradiction. $\endgroup$ – lhf Sep 15 '11 at 18:26
0
$\begingroup$

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

|cite|improve this answer
$\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.