Give examples of functions from $\mathbb{N}$ to $\mathbb{N}$ with the following properties: i. one-to-one but not onto
ii. onto but not one-to-one
iii. both onto and one-to-one
iv. neither one-to-one nor onto
Here's my solution:
i. $y = x^2$ from the set of non-negative real numbers to the set of all real numbers
ii. $y = x^2$ from the set of all real numbers to the set of non-negative real numbers
iii. $y = x^2$ from the set of non-negative real numbers to the set of non-negative real numbers iv. $y = x^2$ from the set of all real numbers to the set of all real numbers
Do you think my answers are correct?
$\endgroup$ 14 Answers
$\begingroup$i. This is certainly injective because $(-x)^2$ will be unique for unique $x \in \mathbb{R}^+$. However, it cannot be surjective since you aren't mapping onto any negative reals.
ii. That is certainly correct. $(-x)^2$ and $x^2$ will map to the same element, so the function is not injective. However, every element in $\mathbb{R}^+$ has a square root, so it must be a surjective mapping to the non-negative reals.
iii. Is also correct. The problem with ii not being injective has been resolved by restricting the function's domain to the non-negative real numbers.
iv. Is correct. Certainly, it cannot be surjective since you aren't mapping onto the negative reals. It cannot be injective because $(-x)^2$ = $x^2$.
In short, you are partiallly correct. The only thing is that it looks like your problem statement requires your functions be defined as $f:\mathbb{N} \rightarrow \mathbb{N}$?
$\endgroup$ $\begingroup$You must give functions with domain and codomain equals to $\mathbb{N}$.
One possible solution is:
i. $f(x)=2x$
$f(x)=f(y) \Rightarrow 2x=2y \Rightarrow x=y$
So $f$ is one-to-one.
There is no $x\in\mathbb{N}$ such that $2x=1$, so $f$ is not onto.
ii. $f(1)=1$ and $f(x)=x-1$ if $x>1$
$f(1)=f(2)=1$, so $f$ is not one-to-one.
$\forall x\in\mathbb{N}, f(x+1)=x$, so $f$ is onto.
iii. $f(x)=x$
iv. $f(x)=1$
$f(1)=1=f(2)$, so $f$ is not one-to-one.
There is no $x\in\mathbb{N}$ such that $f(x)=2$, so $f$ is not onto.
Hint: for (i) $x \rightarrow x+1$ (ii) $1 \rightarrow 1$, and for $x \neq 1, x \rightarrow x-1$, can you do (iii) and (iv) now?
$\endgroup$ $\begingroup$Hint: $\mathbb{N}$ does not include any negative numbers, so i, ii and iv are partially incorrect. $\mathbb{N} = \{1, 2, 3, ...\}$ (or even sometimes $\mathbb{N} = \{0, 1, 2, 3, ...\}$).
$\endgroup$
