Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
1  
You don't need a hint; that is a correct proof. –  MJD Mar 27 '12 at 17:15
    
That is correct. –  Isaac Solomon Mar 27 '12 at 17:16
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$. –  Arturo Magidin Mar 27 '12 at 17:22
    
Correct proof. Try formalizing it more though. –  ThisIsNotAnId Mar 27 '12 at 17:24
2  
$Y$ can be the empty set if $X$ is also. –  MJD Mar 27 '12 at 18:06

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
1  
Hard to beat that for concision. –  Brian M. Scott Mar 27 '12 at 21:59
    
But comments must be at least 15 characters long... –  dtldarek Mar 28 '12 at 1:13
    
And answers have to be at least $40$. But those excess characters don't have to actually end up displaying anything. –  Chris Eagle Mar 28 '12 at 10:11

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}

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.