Thread: 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

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

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

It means that two different values of x cannot give the same value of f. For example, [itex]f(x)= x^2[/itex] is NOT "injective" because [itex]f(2)= f(-2)[/itex] while, of course, . On the other hand, f(x)= 3x- 4 because if then [tex]3x_1- 4= 3x_2- 4[/itex], adding 4 to both sides, so, dividing both sides by 3, . 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, is NOT a surjective function from R to R because there is not x such that

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 where and then let's say then you can see that f is injective since therefore and you can convince yourself by replacing 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

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?

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 [itex]2a_1 + |a_1| = 2a_2 + |a_2|[/itex], 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.

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 , dividing both sides by 2, a_1 + |a_1|= a_2 +|a_2|.

Really?

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?

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.

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. :'(

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|.

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.

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. :'(

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,



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).