1) f(n) = 2n + 1 from set of integers to set of integers
2) f(n) = 2[n/2] from set of integers to set of integers [] is floor
Could someone demonstrate how I would prove whether these are one-to-one and/or onto?
For example, on the first one:
f(n) = 2n+1
I can look at it and try some numbers: (0,1), (1,3), (2,5)…
every A has a unique B it looks like, so it is one-to-one (injective)
it does not look like every B has at least one A because we skip 2, 4, etc. so it is not onto (surjective)
but how would i write a proof for this?
Best Answer
Tidus,
To show that a function is injective, you need to show that if two points $x$ and $y$ get mapped to the same point, i.e. $f(x)=f(y)$, then we must have $x=y$. For the first function $f(n)=2n+1$, this is quite straight forward since if we have two integers $n,m$ such that $f(n)=f(m)$, this means that $2n+1=2m+1\Rightarrow n=m$.
To show that it is surjective, we must show that for every $n$, we can find another integer $m$ such that $f(m)=n$. However, note that the set $Im(f)=\{f(n)\mid n\in \mathbb{N}\}=\{2n+1\mid n\in \mathbb{N}\}$ is precisely equal to the set of odd integers. Therefore, $f$ is not onto (nothing maps to even integers).
I will leave the second function to you as an easy exercise!