6
$\begingroup$

Can someone give me hint how to prove that for a function $f:X\rightarrow Y$ and $B\subseteq X$ we have $$f(B)=\emptyset \Rightarrow B=\emptyset \ ?$$

Is my idea that, supposing $x\in B\neq \emptyset$, we would have to have, since $f$ is a function, a $y$ such that $f(x)=y$ and therefore $y\in f(B)=\emptyset$, which is a contradiction, correct ?

  • 1
    You don't need a hint; that is a correct proof.2012-03-27
  • 0
    That is correct.2012-03-27
  • 1
    You can cast it as a proof by contrapositive (which it is) instead of a proof by contradiction: $B\neq\varnothing\implies f(B)\neq\varnothing$.2012-03-27
  • 0
    Correct proof. Try formalizing it more though.2012-03-27
  • 0
    Thanks. Although, now I'm observing that I actually wasn't precise enough: $Y$ is not allowed to be the empty set. Otherwise we wouldn't even have a function $f$ to talk about, right ?2012-03-27
  • 2
    $Y$ can be the empty set if $X$ is also.2012-03-27

2 Answers 2

3

Yes.${}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}$

  • 1
    Hard to beat that for concision.2012-03-27
  • 0
    But comments must be at least 15 characters long...2012-03-28
  • 1
    And answers have to be at least $40$. But those excess characters don't have to actually end up displaying anything.2012-03-28
4

Here is a slightly longer answer. :-)

A straightforward calculation shows that both parts are actually equivalent: we start with the left hand side, expand the definition of $\;\cdot[\cdot]\;$, and then simplify. \begin{align} & f[B] = \varnothing \\ \equiv & \;\;\;\;\;\text{"basic property of empty set"} \\ & \langle \forall y :: y \not\in f[B] \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\;\cdot[\cdot]\;$"} \\ & \langle \forall y :: \lnot \langle \exists x : x \in B : f(x) = y \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"simplify: apply DeMorgan to $\;\exists x\;$"} \\ & \langle \forall y :: \langle \forall x : x \in B : f(x) \not= y \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"rearrange quantifications -- to prepare for one-point rule"} \\ & \langle \forall x,y : y = f(x) : x \not\in B \rangle \\ \equiv & \;\;\;\;\;\text{"one-point rule"} \\ & \langle \forall x :: x \not\in B \rangle \\ \equiv & \;\;\;\;\;\text{"basic property of empty set"} \\ & B = \varnothing \\ \end{align}