Provide examples of functions from the natural numbers to the natural numbers that are one-to-one but not onto, onto but not one-to-one, and both one-to-one and onto (but not the identity function).

Assumption: The set of natural numbers $\mathbb{N}$ is defined as the set of positive integers, $\mathbb{N} = \{1, 2, 3, \dots\}$.

a) one-to-one but not onto.
Consider the function $f: \mathbb{N} \to \mathbb{N}$ defined by $f(n) = n+1$.

• One-to-one: If $f(n_1) = f(n_2)$, then $n_1+1 = n_2+1$, which implies $n_1 = n_2$. Thus, $f$ is one-to-one.
• Not onto: The range of $f$ is $\{2, 3, 4, \dots\}$. The number $1 \in \mathbb{N}$ (codomain) is not in the range of $f$, as there is no $n \in \mathbb{N}$ such that $n+1=1$. Thus, $f$ is not onto. Example: $\boxed{f(n) = n+1}$

b) onto but not one-to-one.
Consider the function $f: \mathbb{N} \to \mathbb{N}$ defined by $f(n) = \lceil \frac{n}{2} \rceil$.

• Not one-to-one: $f(1) = \lceil \frac{1}{2} \rceil = 1$ and $f(2) = \lceil \frac{2}{2} \rceil = 1$. Since $f(1) = f(2)$ but $1 \neq 2$, $f$ is not one-to-one.
• Onto: For any $k \in \mathbb{N}$ (codomain), we can choose $n = 2k-1$. Since $k \ge 1$, $n = 2k-1 \ge 1$, so $n \in \mathbb{N}$. Then $f(2k-1) = \lceil \frac{2k-1}{2} \rceil = \lceil k - \frac{1}{2} \rceil = k$. Thus, $f$ is onto. Example: $\boxed{f(n) = \lceil \frac{n}{2} \rceil}$

c) both onto and one-to-one (but different from the identity function).
Consider the function $f: \mathbb{N} \to \mathbb{N}$ defined by:

$$f(n) = \begin{cases} n+1 & \text{if } n \text{ is odd} \\ n-1 & \text{if } n \text{ is even} \end{cases}$$

• One-to-one: If $f(n_1) = f(n_2)$, then $n_1$ and $n_2$ must have the same parity (an odd number maps to an even number, and an even number maps to an odd number). If $n_1, n_2$ are both odd, $n_1+1 = n_2+1 \implies n_1=n_2$. If $n_1, n_2$ are both even, $n_1-1 = n_2-1 \implies n_1=n_2$. Thus, $f$ is one-to-one.
• Onto: For any $k \in \mathbb{N}$ (codomain): if $k$ is even, choose $n=k-1$ (which is odd and in $\mathbb{N}$ since $k \ge 2$). Then $f(k-1) = (k-1)+1 = k$. If $k$ is odd, choose $n=k+1$ (which is even and in $\mathbb{N}$). Then $f(k+1) = (k+1)-1 = k$. Thus, $f$ is onto.
• Different from identity: For example, $f(1) = 1+1 = 2 \neq 1$. Example: $\boxed{f(n) = \begin{cases} n+1 & \text{if } n \text{ is odd} \\ n-1 & \text{if } n \text{ is even} \end{cases}}$

d) neither one-to-one nor onto.
Consider the function $f: \mathbb{N} \to \mathbb{N}$ defined by $f(n) = 1$.

• Not one-to-one: $f(1) = 1$ and $f(2) = 1$. Since $f(1) = f(2)$ but $1 \neq 2$, $f$ is not one-to-one.
• Not onto: The range of $f$ is $\{1\}$. The number $2 \in \mathbb{N}$ (codomain) is not in the range of $f$. Thus, $f$ is not onto. Example: $\boxed{f(n) = 1}$