I need to grasp these concepts of injective, surjective, and bijective. I have grasped the idea behind it, but when it comes to determining it with functions, I get confused and lost. For example this question:

Let $\mathbb{Z}$ be the set of integers and $\mathbb{N}$ the set of positive integers. Use it to solve the following:

1.)The function $f: \mathbb{Z} \to \mathbb{Z}$ given by $f(x)=\lceil x \rceil$ is___

A.) injective, but not surjective, B.) surjective, but not injective, C.) bijective , D.) Neither

2.)The function $f: \mathbb{N} \to \mathbb{N}$ given by $f(x) = x+3$ is ___

A.) injective, but not surjective, B.) surjective, but not injective, C.) bijective , D.) Neither

For the first attempt, I plugged in $f(1) = \lceil 1 \rceil = 1$, $f(-1) = \lceil -1 \rceil = -1$...so far it's one-to-one, how do I determine the surjective, because the answer was bijective, which is both one-to-one and onto.

For second attempt, to check on injective I plugged in $f(2) = 5$, $f(3) = 6$, $f(0) = 3$. This checks for one-to-one, but surjective is where it gets me, how do I find out? I read something like this works...$y=x+3 \to y-3 = x$...then what? It's confusing me.

Please help me understand this better, or provide me with a good explanation, I need to grasp this before my Finals :(

Thanks in advance.

  • 1
    $\begingroup$ For the first problem, we have $f(x)=x$ for all $x\in \mathbb{Z}$. $\endgroup$ May 7 '16 at 1:47
  • $\begingroup$ Can you elaborate on it? $\endgroup$ May 7 '16 at 17:25
  • $\begingroup$ If $x$ is an integer, then $\lceil x\rceil$, the smallest integer $\ge x$, is $x$. The function $f(x)=x$ is a bijection from $\mathbb{Z}$ to $\mathbb{Z}$. Verification of the properties is straightforward. $\endgroup$ May 7 '16 at 17:29
  • $\begingroup$ How can I apply it to surjection? Would it be something like this f(x) = y? and go from there. $\endgroup$ May 7 '16 at 17:44
  • $\begingroup$ We want to prove that for every $b$ there is an $a$ such that $f(a)=b$. Let $a=b$. Then indeed $f(a)=b$. $\endgroup$ May 7 '16 at 17:46

1) The function $\lceil~\rceil\colon \mathbb{Z}\rightarrow\mathbb{Z}$ is the identity (why?), and is thus bijective.

2) It's not enough to check a few points to see if $f$ is injective. To be rigorous, you might make an argument as follows: if $n,m\in\mathbb{Z}$ are such that $f(n)=f(m)$, then $n+3=m+3$, so that $n=m$, whence $f$ is injective.

For surjectivity, you're on the right track. An element $y$ in the image of $f$ is of the form $y=x+3$ for some $x\in\mathbb{N}$. In this case, $x=y-3$. Is there some $x\in\mathbb{N}$ making this possible if $y=1\in\mathbb{N}$? What does this imply about $f$?

  • $\begingroup$ What do you mean in 1.)? and for 2.) if I plug in 1 in for y, then x = -2, what does that tell me? Sorry, I still have trouble understanding it. $\endgroup$ May 7 '16 at 2:26
  • $\begingroup$ What do you not understand for 1)? For 2), recall what $\mathbb{N}$ is. $\endgroup$
    – neth
    May 7 '16 at 2:28
  • $\begingroup$ For 1) How do I figure out surjective? I still have trouble getting the "onto" part. And for 2) I see, I totally forgot that it's positive integers only, since we get a negative, does that imply its injective but not surjective? $\endgroup$ May 7 '16 at 2:37

The standard way to show that a function is injective is to act the function on two arbitrary elements of the domain, assume the results are equal, and show that in that case the two elements of the set in fact have to be equal.

For example, let's take $f: \mathbb{Z} \to \mathbb{Z}$ defined by $f(x) = \lceil x \rceil$. First, you should think about the function and try to convince yourself whether you believe it is or is not injective. Examining the ceiling function, I notice that if I feed an integer in I will always get the same integer back out. Since my domain is integers, that just means $f(x)=x$. Given this, there is no way that I can input two different integers to $f$ and get the same integer as a result of both, so I conclude that $f$ must be injective. Now that we know the answer, all that is left is to make a formal proof.

Let $m,n \in \mathbb{Z}$ such that $f(m) = f(n)$ Using the definition of $f$ and our reasoning above, this implies $\lceil m \rceil = \lceil n \rceil$ and since $m$ and $n$ are integers this means $m = n$. We've shown that the only way for $f(n) = f(m)$ is if $m = n$, which means that $f$ is injective, as we expected.

To prove that a function is surjective, you will often take an arbitrary element $y$ in the codomain (the set that $f$ maps into), and show that there is some element in the domain that gets mapped to $y$.

As an example, we'll again use $f$ as defined above. Again, it's a good idea to first convince yourself of what the answer should be. If $f$ is surjective then its range covers all of $\mathbb{Z}$, so we ask ourselves if there is any element of $\mathbb{Z}$ that cannot be "reached" by $f$. Given that we already know $f(x)=x$ for all $x \in \mathbb{Z}$ it is clear that any element of $\mathbb{Z}$ can be reached by $f$, so $f$ should be surjective.

Now with the proof. Let $n \in \mathbb{Z}$ Because $f(x)= \lceil x \rceil=x$ we see that $f(n) = n$. Since there exists an element of $\mathbb{Z}$ which maps to $n$, (namely, $n$ itself gets mapped to $n$) we conclude that $f$ is surjective, as expected.

You can use these same techniques to answer your second problem, as well as most others you will encounter.


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.