1
$\begingroup$

i have a question about injective and surjective functions, i don't seem to understand it right i tried multiple sources including my books of course and i seem to get stuck mostly in the surjective proving questions. my question is - f:N→N prove that f is injective if and only if for every 2 different and infinite sets A,B⊆N,f[A]≠f[B]

i started from the side of proving that f is an injective , i did it by contradiction saying that f[A]=f[B] and if the function is an injective then A=B and for every element in the range there is only one element that gets in from the domain and since i stated that A=B it means there is more than one so it cant be right therefore f[A]≠f[B] and they are not equal. now i don't know if what i did is even right .. and i couldn't prove it the other way around (other side)

and the second question is- f:N→N prove that f is surjective if and only if for every 2 different and infinite sets A,B⊆N,f^-1[A]≠f^-1[B] for this i had no clue how to even start..can someone help explain about surjective and injective functions please ?

thank you all for the big help!

$\endgroup$

1 Answer 1

2
$\begingroup$

Statements about injectivity are often easier to prove by contrapositive. So I'll prove

  1. if there are two different infinite sets $A$ and $B$ such that $f[A]=f[B]$, then $f$ is not injective;

  2. if $f$ is not injective, then there are two different infinite sets $A$ and $B$ such that $f[A]=f[B]$.

Suppose there exists two different infinite sets $A$ and $B$ such that $f[A]=f[B]$. Then, without loss of generality, we can assume there is $a\in A$ such that $a\notin B$. From $f[A]=f[B]$, we conclude there is $b\in B$ with $f(b)=f(a)$. Since $b\ne a$, we conclude that $f$ is not injective.

Now let's tackle the converse. Suppose $f$ not injective. Then there are $a$ and $b$ with $a\ne b$ and $f(a)=f(b)$. Take $C=\mathbb{N}\setminus\{a,b\}$. This is infinite and so are $A=C\cup\{a\}$ and $B=C\cup\{b\}$. Conclude.

For surjectivity, you might want to use the fact that $f$ is surjective if and only if, for every $A\subseteq\mathbb{N}$, $f[f^{-1}[A]]=A$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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