I was given a function $f:A\rightarrow B$, and was asked to find the statements in answer choices that are equivalent to saying $f$ is onto. I am wondering, is there a way I can mechanically simplify the answer choices and see if they are equivalent to the definition of an onto function? How should I approach this kind of questions? Thanks.
The definition of onto function on the textbook is: $$\forall y\in B, \exists x\in A, f(x) = y$$
And here are the answer choices:
- $$\neg \exists x\in A, \forall y\in B \; f(x) \not= y$$
- $$\forall y\in B, \exists x\in A, \exists w \in B \; f(x)=w \land y=w$$
- $$\neg \exists y\in B, \forall x\in A\; f(x) \not= y$$
- $$\forall y\in B, \exists x\in A \; f(x)=y$$
- $$\forall x\in A, \exists y\in B \; f(x)=y$$
Note that $\neg\exists u\in U\colon P(u)$ is equivalent to $\forall u\in U\colon \neg P(u)$. Similarly $\neg \forall u\in U\colon P(u)$ is equivalent to $\exists u \in U\colon \neg P(u)$. In other words you can "slide" a negation through a quantifier as long as you also "invert" the quantifier (from $\exists$ to $\forall$ and vice-versa). Using this rule you can transform the third statement into the fourth (which happens to be your original definition) and the first into the fifth.
The second statement is like the fourth, except $f(x)=y$ is replaced by $\exists w\in B\colon f(x)=w\wedge y=w$. Clearly the second of these implies the first (since $f(x)=w=y$ implies $f(x)=y$). As long as $f(x)$ and $y$ are elements of $B$ (which they are in this context), the converse also holds (since you can take $w$ to be $y$).
So we see that $1.\leftrightarrow 5.$ and $2.\leftrightarrow 3.\leftrightarrow 4$
Now you just need to convince yourself that 5. (and hence 1.) is true for any function, no matter if onto or not; hence it is not equivalent to the others.