3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do you include $0$ in the natural numbers? $\endgroup$ – graydad Oct 1 '14 at 19:57
  • 1
    $\begingroup$ For onto but not one to one, an idea close to yours will work. Let $f(1)=f(2)=1$, and let $f(n)=n-1$ for $n\ge 3$. (I am assuming your $\mathbb{N}$ does not include $0$.) $\endgroup$ – André Nicolas Oct 1 '14 at 20:01
  • $\begingroup$ @graydad No, I don't consider 0 to be natural. Good question. :) $\endgroup$ – Ethan Oct 1 '14 at 20:14
  • $\begingroup$ @AndréNicolas So once I specify that f(1) = 1 that allows me to get a repeat answer/y (as you said f(1) = f(2)) to make it unto. That's helpful, thanks. :D $\endgroup$ – Ethan Oct 1 '14 at 20:14
  • $\begingroup$ If you want a fancier example, let $f(2n)=n$ and let $f(2n-1)=n$. So the values of the function are $1,1,2,2,3,3,\dots$, seriously not one to one. $\endgroup$ – André Nicolas Oct 1 '14 at 20:18
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very well explained. What is and isn't "reached" is helpful vocabulary and you certainly put this all into perspective. Thank you. $\endgroup$ – Ethan Oct 1 '14 at 20:18
  • $\begingroup$ By the way, when you are learning elementary maths it may be helpful to draw simple diagrams to visualize things. Like those in en.wikipedia.org/wiki/Injective_function. I found them extremely helpful at the beginning, also for more complex situations. $\endgroup$ – Giovanni Mascellani Oct 1 '14 at 20:27
1
$\begingroup$

One and four look good to me. For two you haven't quite defined a function because you didn't define $f(1)$. You could make that a piecewise function with $$f(1)=1 \quad \text{and} \quad f(n) = (n-1) \space \text{if} \space n>1$$ This will make $f$ onto but not one-to-one as $f(1)=f(2).$

Three also doesn't make sense to me, as have $g: \mathbb{N} \to \Bbb{N}$ where $g(n)=0$. The way you defined $g$ is by making it map outside of $\Bbb{N}$? That doesn't work, but you could fix that by just having $g(n)=1$. Then it is true that $g$ is not one-to-one and not onto.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ f(1) = f(2) ... that blew my mind a little, and it explains a lot about how this works. xD And I see what you mean by g(n)=1. At first I didn't want to put that because that means every n maps to 1, but I see now that because every other natural number is not mapped at all, it is therefore not unto. :) Thanks! $\endgroup$ – Ethan Oct 1 '14 at 20:11

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.