Question

Give example of a function f: N-> N which is
(a) injective but not surjective
(b) surjective but not injective
(c) bijective but not identity function.
....... Urgent help.

Answer 1

a. \(n \longrightarrow 2n\)

Answer 2

b. if \(n\) is even, let \(n=2k\). Then \(2k \longrightarrow k\)

Otherwise, \(n = 2k+1\). Then \(2k+1 \longrightarrow k\).


Can someone assure me that this is in fact surjective but not injective? I think it is, but I'm not positive.

Answer 3

c. If \(n\) is even, \(n \longrightarrow n-1\)
If \(n\) is odd, \(n \longrightarrow n+1\)

Answer 4

That last one is assuming \(\mathbb{N} = \{1, 2, 3, 4, ...\}\)

If \(\mathbb{N} = \{0, 1, 2, 3, ...\}\), then switch the statements.

Answer 5

For (b) you can always pick the \(f:\mathbb{N}\to\mathbb{N}\) function \(f(n)=\lceil n/2 \rceil\).

Answer 6

My example is basically the same thing except \(f(n) = \lfloor n/2\rfloor\) correct?

Answer 7

The problem with \(f(n) = \lfloor n/2\rfloor\) is that \(0\in f(\mathbb{N})\).

Answer 8

Right.

In that case, for my answer to part b, it should say "otherwise \(n=2k-1\)" instead of \(n=2k+1\).

Answer 9

@Desi_Spark, if you need an explanation for why these functions work, just say so.

Answer 10

@k - yes,mate if u have time then plz explain these function.You guys hav already helped me a lot. thanks a lot.

Answer 11

First up, a. An injective function that isn't surjective. This means that you want a function that has a unique output for each input, that doesn't cover the natural numbers.

In formal terms a function \(f\) is injective if \(f(x)=f(y)\) implies \(x=y\). Thus, if we take \(f(n) = 2n\), and \(f(x)=f(y)\), then \(2x=2y\) so \(x=y\). Thus it's injective.

We also know that it's not surjective because no value maps to \(1\) (or any odd number) since if \(f(x)=1\), then \(1=2x \Longrightarrow x=1/2\). However, since \(1/2 \notin \mathbb{N}\), the function isn't surjective.

Make sense?

Answer 12

@kingGeorge - yes now i got it.thanks a lot.u saved me.

Answer 13

You're very welcome.

Answer 14

As for b. our function is as follows:

If \(n=2k\), then \(f(n)=k\).
Otherwise, \(n=2k-1\) and \(f(n)=k\).

This is not injective since if you have \(f(x)=f(y) = 1\), then \(x=2\) and \(y=1\) are valid possibilities for \(x, y\). It is however surjective because every \(k\in\mathbb{N}\) was mapped to by either \(2k\) or \(2k-1\).

Answer 15

For c. Think of the function like this. Suppose you have an odd number \(x\). Then \((x, x+1)\) is mapped to \((x+1, x)\). Basically, the function swaps every consecutive pair of numbers. This can be checked to be injective and surjective in a similar manner to above.