# Understanding Injective and Surjective functions

• Apr 12th 2012, 09:38 AM
ConfusedGuy19
Understanding Injective and Surjective functions
Hey Guys, I am new here and I hope that I have posted this in the right place.

I'm in a serious dilemma regarding understanding how to do Injective and Surjective functions. To be more precise, how to do them formally the formal definition). I am given this as an example from my lecturer

Quote:

Let f : A → B be a function.

We call f an INJECTIVE (or ONE-TO-ONE) function if f(a1) = f(a2) ⇒ a1 = a2 for all a1,a2 ∈A.
Since this is logically equivalent to the statement a1 ≠ a2 ⇒ f(a1) ≠ f(a2), an injective function never repeats values. In other words, different inputs give different outputs.

We call f a SURJECTIVE (or ONTO) function if the range of f coincides with the codomain of f.
This means that for every b∈B there exists an a∈A with b = f(a). In other words, each element in the codomain is a value of the function.
What I am failing to understand is
Quote:

f(a1) = f(a2) ⇒ a1 = a2 for all a1,a2 ∈A
.

Does this mean that f(a1) and f(a2) have the be the same value like f(2) = f(2)???

I would a appreciate a few examples of both Injective and Surjective functions in order to help me understand this better because I am really stressed out.

Thanks
• Apr 12th 2012, 10:53 AM
HallsofIvy
Re: Understanding Injective and Surjective functions
It means that two different values of x cannot give the same value of f. For example, $f(x)= x^2$ is NOT "injective" because $f(2)= f(-2)$ while, of course, $\displaystyle 2\ne -2$. On the other hand, f(x)= 3x- 4 because if $\displaystyle f(x_1)= f(x_2)$ then [tex]3x_1- 4= 3x_2- 4[/itex], adding 4 to both sides, $\displaystyle 3x_1= 3x_2$ so, dividing both sides by 3, $\displaystyle x_1= x_2$. f(x)= 3x- 4 is "injective".

A function from set A to set B is "surjective" if something in A is mapped to every member of B. Again, f(x)= 3x- 4 is a example of a surjective function from R to R: if y is any real number (in R) then we can solve 3x- 4= y for x: 3x= y+ 4, x= (y+4)/3. No matter what y is (y+4)/3 is a real number so x= (y+4)/3 is "mapped" to y. However,$\displaystyle f(x)= x^2$ is NOT a surjective function from R to R because there is not x such that $\displaystyle x^2= -4$
• Apr 12th 2012, 11:19 AM
jfk
Re: Understanding Injective and Surjective functions
Quote:

Originally Posted by ConfusedGuy19
Let f : A → B be a function.

We call f an INJECTIVE (or ONE-TO-ONE) function if f(a1) = f(a2) ⇒ a1 = a2 for all a1,a2 ∈A.
Since this is logically equivalent to the statement a1 ≠ a2 ⇒ f(a1) ≠ f(a2), an injective function never repeats values. In other words, different inputs give different outputs.

We call f a SURJECTIVE (or ONTO) function if the range of f coincides with the codomain of f.
This means that for every b∈B there exists an a∈A with b = f(a). In other words, each element in the codomain is a value of the function.

The above definition gives all the explanation you need (although it might be a little tricky to understand sometimes).
Consider a function $\displaystyle f:{A}\rightarrow{B}$ where $\displaystyle A=\{x,y,z\}$ and $\displaystyle b=\{1,2,3\}$ then let's say $\displaystyle x\mapsto{1}, y\mapsto{2},z\mapsto{3}$ then you can see that f is injective since $\displaystyle x\ne{y}\ne{z}$ therefore $\displaystyle f(x)\ne{f(y)}\ne{f(z)$ and you can convince yourself by replacing $\displaystyle f(x)=1,f(y)=2,f(z)=3$ also remember that the elements on a set are not allowed to repeat, that's why the contrapositive makes sense (if f(x)=f(y) then x must be equals to y since you must map each value of the domain to a different value in the codomain)
You may also want to take a look at this article: Injective function - Wikipedia, the free encyclopedia
• Apr 12th 2012, 11:23 AM
emakarov
Re: Understanding Injective and Surjective functions
Quote:

Originally Posted by ConfusedGuy19
What I am failing to understand is

f(a1) = f(a2) ⇒ a1 = a2 for all a1,a2 ∈A

The function "father" on the set of people is injective, by definition, if

for all people x and y, if father(x) = father(y), then x = y.

Is "father" injective?

The function "social security number (SSN)" from people to natural numbers is injective, by definition, if

for all people x and y, if SSN(x) = SSN(y), then x = y.

Is "SSN" injective?
• Apr 12th 2012, 11:58 AM
ConfusedGuy19
Re: Understanding Injective and Surjective functions
OK,

So just to make sure I understand:

q: R→R given by h(a) = 2a + |a|.

for this one I came up with it being [B/NOT[/B]"Injective" because if h(a_1)= h(a_2) then $2a_1 + |a_1| = 2a_2 + |a_2|$, dividing both sides by 2, a_1 + |a_1|= a_2 +|a_2|. h(a)= 2a + |a| is NOT "injective".

I don't how to test whether it is surjective. Can anyone please help with this and thank you for the previous replies?

Note: |a| means abs value of real number (e.g. |a| = a if a => 0 and |a| = -a if a < 0.

Sorry for being such a nuisance. :(
• Apr 12th 2012, 12:17 PM
emakarov
Re: Understanding Injective and Surjective functions
Quote:

Originally Posted by ConfusedGuy19
for this one I came up with it being [B/NOT[/B]"Injective" because if h(a_1)= h(a_2) then $\displaystyle 2a_1 + |a_1| = 2a_2 + |a_2|$, dividing both sides by 2, a_1 + |a_1|= a_2 +|a_2|.

Really?

Quote:

Originally Posted by ConfusedGuy19
h(a)= 2a + |a| is NOT "injective".

But the definition of injectivity says that h(a_1) = h(a_2) must imply a_1 = a_2. You, on the other hand, showed that h(a_1) = h(a_2) implies a_1 + |a_1|/2 = a_2 + |a_2|/2. Does the latter equality imply a_1 = a_2 or is there a counterexample?

Quote:

Originally Posted by ConfusedGuy19
I don't how to test whether it is surjective.

I recommend first sketching a graph of h and use it to find the answer before doing algebraic manipulations.
• Apr 12th 2012, 12:40 PM
ConfusedGuy19
Re: Understanding Injective and Surjective functions
Quote:

Originally Posted by emakarov
Really?

But the definition of injectivity says that h(a_1) = h(a_2) must imply a_1 = a_2. You, on the other hand, showed that h(a_1) = h(a_2) implies a_1 + |a_1|/2 = a_2 + |a_2|/2. Does the latter equality imply a_1 = a_2 or is there a counterexample?

I recommend first sketching a graph of h and use it to find the answer before doing algebraic manipulations.

I think it is the h(a)= 2a + |a| that is confusing me because I think I am left with |a| + |a| afterwards. No counter example

Do you know the simplest way Injective and Surjective can be explained formally? I spent hours trying to understand it to no avail. :'(
• Apr 12th 2012, 12:49 PM
emakarov
Re: Understanding Injective and Surjective functions
By saying "Really?" I meant that dividing both sides of 2a_1 + |a_1| = 2a_2 + |a_2| by 2 gives a_1 + |a_1|/2 = a_2 + |a_2|/2, not a_1 + |a_1| = a_2 + |a_2|.

Quote:

Originally Posted by ConfusedGuy19
Do you know the simplest way Injective and Surjective can be explained formally?

Do you mean the formal definition or formal proof for this particular function h? You have the formal definition, and a formal proof of h(a_1) = h(a_2) => a_1 = a_2 can be arbitrary as long as it is a valid proof.

Or do you mean explain injection intuitively? A function is injective if it maps distinct objects into distinct results. For example, "father" is not injective because two brothers are mapped into the same person, but "SSN" is injective because no two people have the same SSN.
• Apr 12th 2012, 01:16 PM
ConfusedGuy19
Re: Understanding Injective and Surjective functions
Quote:

Originally Posted by emakarov
By saying "Really?" I meant that dividing both sides of 2a_1 + |a_1| = 2a_2 + |a_2| by 2 gives a_1 + |a_1|/2 = a_2 + |a_2|/2, not a_1 + |a_1| = a_2 + |a_2|.

Do you mean the formal definition or formal proof for this particular function h? You have the formal definition, and a formal proof of h(a_1) = h(a_2) => a_1 = a_2 can be arbitrary as long as it is a valid proof.

Or do you mean explain injection intuitively? A function is injective if it maps distinct objects into distinct results. For example, "father" is not injective because two brothers are mapped into the same person, but "SSN" is injective because no two people have the same SSN.

I mean through the formal definition. I understand how to it works when you are using lines to connect points but when writing it like the examples given above, that is when I get confused. Like answering a formal definition whether it is injrctive or surjective. :'(
• Apr 12th 2012, 02:27 PM
emakarov
Re: Understanding Injective and Surjective functions
First you need to have an intuitive idea why some function is injective. If often helps to look at the graph. Then you figure out a way to convert this intuitive idea into a formal proof.

From the graph of 2x + |x| we see that different x's are mapped into different y's.

Now we need to prove "For all x1, x2, if h(x1) = h(x2), then x1 = x2." Fix arbitrary x1 and x2 and assume that h(x1) = h(x2). This part was automatic; now we need some ingenuity. Note that since |x| = x for x >= 0 and |x| = -x for x < 0,

$\displaystyle h(x)=\begin{cases}3x&x\ge 0\\x&x<0\end{cases}$

In particular, the sign of h(x) coincides with the sign of x. Suppose that h(x1) = h(x2) >= 0. Then x1 >= 0 and x2 >= 0, so h(x1) = h(x2) means 3x1 = 3x2, which implies x1 = x2. Suppose that h(x1) = h(x2) < 0. Then x1 < 0 and x2 < 0, so h(x1) = h(x2) means x1 = x2. In both cases, we proved x1 = x2 from the assumption h(x1) = h(x2).