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

Re: Understanding Injective and Surjective functions

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, $\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$

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

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?

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

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.

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

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.

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

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