[Math] How to come up with One-To-One and Onto Examples

discrete mathematicsfunctions

I'm trying to come up with example functions that are $N \rightarrow N$ for each category:

  1. One-to-one but not onto.
  2. Onto but not one-to-one.
  3. Nether one-to-one nor onto.
  4. Both one-to-one and onto.

Here's what I've got:

  1. $f(n) = 2n$, because it's a linear function.
  2. $f(n) = n-1$, This only works when n is $\geq$ 2, but I'm thinking that's good enough?
  3. $f(n) = 0$, maybe this is a stretch but because y is always outside of $N$ I'm sure this is neither one-to-one or onto.
  4. $f(n) = n$, here x=y which matches both definitions.

So, I'm posting because I'm unsure of what I've got. Especially with 1 and 2. Here are the definitions I've got:

Onto: For every $y \in Y$ at least one $x \in X$ such that $f(x) = y$

One-to-one: For any $y \in Y$ there is at MOST one $x$ such that $f(x) = y$

This means that in order for a function to be onto there can be an x with two y's but it's not required. If it doesn't, doesn't that automatically make it also one-to-one?

Best Answer

It seems that you are having some misconceptions here.

Foreword: I will assume that $0 \in \mathbb{N}$, although nothing really changes if do differently.

  1. This is one-to-one and not onto, but this has nothing to do with it being linear. Linear functions can be one-to-one or not and onto or no. Moreover it is delicate to speak about linear functions when you are working with $\mathbb{N}$ usually linear functions require an underlying field, such as $\mathbb{R}$. Your function is one-to-one simply because different natural number have different doubles and is not onto because $1$ is never reached as the double of another natural number.

  2. This is technically not a function, because $0$ does not go anywhere ($-1$ is not a natural number). This can easily fixed, for example, sending $0$ to $0$ (or, by the way, to any natural number). Then your function is defined as $$ f(n) = \begin{cases} 0 & \text{if $n=0$} , \\ n-1 & \text{otherwise} . \end{cases} $$ This function is onto (each natural number is reached), but not one-to-one (there are two numbers that are sent to $0$: both $0$ itself and $1$).

  3. If you, as I do, consider $0 \in \mathbb{N}$, then this is a perfectly valid function and, as you see, is neither one-to-one nor onto. If you do not take $0 \in \mathbb{N}$ it is enough to define $f(n) = 1 \quad \forall n \in \mathbb{N}$ and you are done anyway.

  4. The identity function is, of course, both onto and one-to-one. This is a perfectly valid example.

Now, as you can see a function can independently be one-to-one or not and onto or not. It is not true that, in general, onto implies one-to-one and neither it is, on the contrary, that one-to-one implies onto.

Related Question