Give an example of a one-to-one function that is not onto

[maggiemagnet]

a) Give an example of a one-to-one function f:N->N (the function f, from the natural numbers to the natural numbers) that does not map N onto N.

Can I use f(n) = 2n, because that uses all of the n's in N, and each f(n) has only one n going to it, but it doesn't "cover" all of N?

b) Given an example of a function f mapping N onto N that is not a one-to-one function.

I'm drawing a blank here.

c) Give an example of a function f:N->N that is not one-to-one and does not map onto N.

Can I use f(n) = 1? This doesn't cover N, and isn't one-to-one because all the n's go to 1.

Thanks in advance!

[stapel_eliz]

a) Yes, f(n) = 2n should do fine.

b) Think about doing something similar to (a), but in reverse: If n is odd, so n = 2m + 1, let f(n) = m; if n is even, so n = 2m, let f(n) = m. Because the set of naturals is infinite, you can always get to a given value in N, eventually, by taking a large-enough value 2m or 2m + 1. But obviously having two values (namely, 2m and 2m + 1) go to one value (namely, m) makes this not one-to-one.

(I'm sure there are many, many other ways to answer this part. The above is just what happened to occur to me first.)

c) A constant function is a great choice for this!

Eliz.

[maggiemagnet]

How would I write out a formula for the function in b?

[stapel_eliz]

How would I write out a formula for the function in b?

Use the "piecewise" format that allows for different rules for different parts:

. . . . .

The different parts don't have to be "connected", like "for all x > 3"; all you need is enough rules to "cover" for every possible input.

[maggiemagnet]

Thank you!