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
    @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

6

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
    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?

  • 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
1

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

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
    See my answer on how to avoid a contradiction.2011-09-15