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

  • 0
    Sorry, I wrote it down the wrong way. I have already proven that, but now the other way remains ($f(\emptyset) \subseteq \emptyset$)2011-09-15
  • 1
    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."2011-09-15
  • 6
    @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.2011-09-15
  • 0
    @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.2011-09-15
  • 0
    @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)$.2011-09-15
  • 0
    What do you know about $f$? There are certainly functions where $f(\emptyset) \ne \emptyset$2011-09-15
  • 0
    @Ross Though not very clear from the question, I guess it is used in this sense: $f(A) = \{ f(x) \,:\, x \in A \}$ for $A \subseteq X$. (I don't know what this function $g:2^{X} \to 2^{Y}$ is called.)2011-09-15
  • 0
    @Srivatsan Narayanan: Thanks.2011-09-15
  • 0
    @Srivatsan: I was taught to write $f[A]$, reserving $f(A)$ for the case in which $f:\wp(X)\to\wp(Y)$.2011-09-15

6 Answers 6

7

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.

  • 0
    Thanks, I wrote it down the wrong way. So I still need to prove that $f(\emptyset) \subseteq \emptyset$2011-09-15
  • 0
    Ok, added the solution.2011-09-15
  • 1
    @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$.2011-09-15
  • 0
    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$.2011-09-15
4

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

  • 1
    If you use `\Longrightarrow` instead of `\longrightarrow`, you produce $\Longrightarrow$. Otherwise, nice proof.2012-10-23
3

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

1

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?

  • 0
    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 http://math.stackexchange.com/questions/63374.2011-09-15
  • 5
    @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.2011-09-15
0

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

  • 0
    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$"2011-09-15
  • 0
    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.2011-09-15
  • 0
    @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 empty2011-09-15
  • 0
    @Deven Okay, that makes sense. Thanks2011-09-15
  • 0
    See my answer on how to avoid a contradiction.2011-09-15
0

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