Question

Consider the following functions that map N into N:

1N(n) = n

f(n) = 3n

g(n) = n + (-1)^n

h(n) = min{n, 100}

k(n) = max{0, n-5}

(a) Which of these functions are one-to-one?

(b) Which of these functions map N onto N?

Answer 1

Hmm, what's the first function supposed to be? I haven't come across that notation before. Do you have a definition for it?

Answer 2

No, that is all that is given. =\

Answer 3

I'm afraid I wouldn't be able to help with that one then...

For \(f(n)=3n\) (and the others, for that matter), use the definition of one-to-one:
\[f(x_1)=f(x_2)~~\Rightarrow~~x_1=x_2\\
\text{(contrapositive of what you may have been shown: }x_1\not=x_2~~\Rightarrow~~f(x_1)\not=f(x_2).)\]
So assume \(f(n_1)=f(n_2)\) for some \(n_1,n_2\in\mathbb{N}\):
\[\begin{align*}f(n_1)&=f(n_2)\\
3n_1&=3n_2\\
n_1&=n_2\end{align*}\]
So the first function is one-to-one.

To check if it is onto requires some simple reasoning. For any given \(n\), \(f(n)\) will always result with a multiple of 3. So this one isn't onto, since the multiples of 3 are only a subset of \(\mathbb{N}\).

Answer 4

By the way, were you told that \(\mathbb{N}=\left\{0,1,2,...\right\}\) or \(\mathbb{N}=\left\{1,2,...\right\}\) ? I only ask because if it's the latter, then the last function \(k(n)\) doesn't map from \(\mathbb{N}\) to \(\mathbb{N}\).

Answer 5

N = the set of positive integers: 1,2,3 ...

Answer 6

without the 0, right.

Answer 7

Okay.

By the way, now that I think about it, it could be that \(1_\mathbb{N}(n)\) is just an arbitrary way of saying something like \(f(n)\). If that's the case, then you can apply the same exact reasoning for \(3n\).

Assume \(f(n_1)=f(n_2)\) for some \(n_1,n_2\in\mathbb{N}\):
\[\begin{align*}f(n_1)&=f(n_2)\\
n_1&=n_2\end{align*}\]
So \(1_\mathbb{N}(n)\) is one-to-one.

This function is onto, though, since for any \(n\in\mathbb{N}\) you plug in you get the same \(n\). The range of the function will be \(\mathbb{N}\), same as the target set.

Answer 8

so using that reasoning, I don't understand why all of the functions would not be one-to-one

Answer 9

Oh, disregard that thing I mentioned about \(k(n)\). I thought it said min, not max.

And not all are one-to-one.

Anyway, going down the list:
\[g(n)=n+(-1)^n=\begin{cases}n-1&\text{for odd }n\\
n+1&\text{for even }n\end{cases}\]

Answer 10

If \(n_1\) is odd and \(n_2\) is even, then obviously \(g(n_1)\not=g(n_2)\), so you have to assume both are odd or both are even.
\[\begin{align*}g(n_{1})&=g(n_2)\\
n_1\pm1&=n_2\pm1\\
n_1&=n_2\end{align*}\]
So \(g(n) \) is indeed one-to-one.

It's not onto, though. What happens when \(n=1\)?

Answer 11

You get 0?

Answer 12

Right. Not in the natural numbers, so the function isn't even well defined.

Answer 13

The next one's pretty easy.
\[h(n)=\min\left\{n,100\right\}=\begin{cases}n&\text{for }n<100\\100&\text{for }n\ge100\end{cases}\]
What do you think?

Answer 14

h(n1) = h(n2)

Answer 15

That's about as far as I get =\

I don't really understand the concept of one-to-one

Answer 16

Consider the values of \(n\) one case at a time.

Let say \(n_1<100\) and \(n_2<100\). Then you have \(h(n_1)=n_1\) and \(h(n_2)=n_2\), right? So for this case, \(h(n)\) is one-to-one, provided that \(h(n_1)\not=h(n_2)\), as per the definition.

For \(n_1,n_2\ge100\), you have \(h(n_1)=h(n_2)=100\). So it's not one-to-one, since there are two values of \(n\) that give the same output. ("two-to-one" as opposed to "one-to-one")

It's not onto either, since for \(n\ge100\), the output doesn't get higher than 100, thus leaving out all the other natural numbers. Make sense?

Answer 17

Kind of makes sense.

Answer 18

What specifically are you having trouble with?

Answer 19

so for an earlier problem you say g(n1)n1±1n1=g(n2)=n2±1=n2

but in this problem h(n1)=n1 and h(n2)=n2 and n1<100 and n2<100 so wouldn't that mean n1 = n2? so I don't get why h(n1)≠h(n2)

Answer 20

in the first problem n1 = n2

Answer 21

For \(g(n)\), I assume \(g(n_1)=g(n_2)\) and showed that \(n_1=n_2\), meaning that for two equal outputs, you have that the inputs are the same.

If \(n_1,n_2\) are odd, then \(g(n_1)=n_1-1\), likwise for \(n_2\).

Similarly, if they're even, then \(g(n_1)=n_1+1\), and likewise for \(n_2\).

So if \(g(n_1)=g(n_2)\), then \(n_1-1=n_2-1\) or \(n_1+1=n_2+1\), or more succintly, \(n_1\pm1=n_2\pm1\), which gives you \(n_1=n_2\). So \(g\) is one-to-one.

Answer 22

Note that \(g\) was dealt with case-wise. I did the same for \(h\).

\(\min\{n,100\}\) is the smallest number between \(n\) and 100, which is either \(n\) or 100.

Take the first case: If \(n<100\), then \(\min\{n,100\}\) must be \(n\), right?

So we then assume \(h(n_1)=h(n_2)\) \(\color{red}{\text{for some }n_1,n_2<100}\). Then \(h(n_1)=n_1\) and \(h(n_2)=n_2\). This means that \(n_1=n_2\), so the function is one-to -one *for this case only*.

Answer 23

so for the same inputs, the outputs must be the same on both sides of the equation for the function to be one to one?

I don't get what the difference is between n1 and n2 in h(n)

Answer 24

Yes. Given that two outputs are the same, you have to show that the two inputs used to get that output are the same as well.

In other words \(f(a)=f(b)\) is only true if \(a=b\). \(f(a),f(b)\) are the outputs, \(a,b\) are the inputs.

Answer 25

In \(h(n)\), whether there is a difference between \(n_1\) and \(n_2\) depends entirely on what \(h(n_1)\) and \(h(n_2)\) are.

Like I said earlier, if both \(n_1\) and \(n_2\) are less than 100, then their associated outputs are \(h(n_1)=n_1\) and \(h(n_2)=n_2\).

If \(h(n_1)=h(n_2)\), then you necessarily have \(n_1=n_2\), and so \(h\) is one-to-one ONLY if \(n_1\) and \(n_2\) are less than 100.

Answer 26

For the second case, a simple counter-example suffices to show that \(h\) isn't one-to-one.

Take \(n_1=100\) and \(n_2=101\). Then \(h(100)=h(101)=100\). You have two inputs that give the same output. \(h\) is thus not one-to-one.

Answer 27

so if different inputs give the same output the function is not one-to-one. But if the same inputs give the same output the function is one-to-one?

Answer 28

If *only* the same inputs give the same output, the function is one-to-one.

Answer 29

ah ok that makes sense.

Answer 30

So for k(n) = max{0, n-5} would we need to do same thing for each of the cases?

Answer 31

The problem with this function is that it's not well-defined. It doesn't map from \(\mathbb{N}\) to \(\mathbb{N}\). For \(n\le5\), you have \(\max\{0,n-5\}\le0\).
\[k(n)=\max\{0,n-5\}=\begin{cases}0&\text{for }n\le5&&\text{(this is the poorly-defined part)}\\
n-5&\text{for }n>5\end{cases}\]
But yes, you would need to check case-by-case.

Answer 32

so we say n1 <= 5 and n2 <= 5. Then we have k(n1) = n1 and k(n2) = n2?

Answer 33

which means that it is one-to-one for the first case?

Answer 34

No, not quite. \(k(n_1)=k(n_2)=0\), by the definition of \(k\).

Answer 35

oh right

Answer 36

Now supposing we have \(n_1\not=n_2\), we still have that \(k(n_1)=k(n_2)\). Same output for different inputs. So not one-to-one.

Answer 37

so would it map N onto N?

Answer 38

Why do you think so? I want to see your reasoning.

Answer 39

I don't think it would be.

Answer 40

I don't really know how to show it isn't

Answer 41

I don't know, I don't understand how to know if a function maps N onto N either :(

Answer 42

I would say it is. \(n-5\) gives you all natural numbers, provided that \(n>5\), of course.

It's the same reason for why \(1_\mathbb{N}(n)\) was onto.

Answer 43

hmm, ok, so was h(n) onto then?

Answer 44

Alright, well I think I'm starting to understand one-to-one a little better now. I will look over it some more and see if I can understand everything that is happening.

Sorry to take so much time, and thank you so much for all the help and for putting up with my stupidity! :)

Answer 45

Yeah, it's onto.

Not a problem, happy to help!