Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have learned that an injective function is one such that no two elements of the domain map to the same value in the codomain.

Example: The function $x \mapsto x^2$ is injective when the domain is positive numbers but is not injective when the domain is all numbers because both $(-2)^2$ and $2^2$ map to the same value, $4$.

Is there an advantage of an injective function over a non-injective function? What is the practical benefit of injective functions? Or perhaps there is an advantage to a function not being injective?

I have also learned about surjective functions: a surjective function is one such that for each element in the codomain there is at least one element in the domain that maps to it.

What is the benefit of a function being surjective? Is there a danger to using functions that are not surjective?

I'd like to have a deeper understanding of injective and surjective than simply be able to parrot back their definitions. Please help.

share|improve this question
2  
An advantage? In what context? A lot of the time you don't use functions, you are given functions and you have to deal with them. Understanding the properties that a function has (such as injectivity or surjectivity) means that you can better understand what it does. For example, if a function is injective and surjective, it is invertible. This breaks testing for invertibility into two easier tests. –  Aaron Aug 4 '12 at 14:36
    
It's not about benefits or dangers. The words "injective" and "surjective" are useful words for describing a mathematical situation. –  Qiaochu Yuan Aug 4 '12 at 14:44

3 Answers 3

Careless use of non-surjective functions can lead to your presence on certain government watch lists... ;)

There is no "danger" to a function that is or isn't injective or surjective. However, in certain cases, you need to be certain that the function (morphism) has these properties, otherwise the property you are trying to prove would not be proven.

For example, one type of function is a homomorphism from one group to another. A special type of homomorphism is an isomorphism; existence of isomorphisms between groups are extremely strong, and indicate that one group is essentially the same as another, which is a very powerful statement indeed. For a homomorphism to be an isomorphism, it must be both injective and surjective -- called bijective.

Another example is the invertibility of a function. A function $f$ has an inverse function $f^{-1}$ if and only if it is bijective. This is why $x^2$ has no inverse (this is really an incomplete statement about which a lot more can be said; I am trying to paint a broad picture here).

So the advantages of a function having these properties depends a lot on your context; but as soon as you require these properties, the ability to demonstrate them for your function becomes critically important, and can be very powerful.

share|improve this answer
up vote 1 down vote accepted

Ed and Aaron, thank you very much for explaining the practical benefits of injectivity and surjectivity.

I have taken what I learned from you and cast it into my own thoughts and experiences. Please let me know of any errors.


Motivation

When I go hiking, I want to be able to retrace my steps and get back to my starting point.

When I go to a store, I want to be able to return home.

When I swim out from the shore, I want to be able to get back to the shore.

Going somewhere and then coming back to where one started is important in life.

And it is important in mathematics.

And it is important in functional programming.

Domain, Codomain, and Inverse

If a function maps a set of elements (the domain) to a set of values (the codomain) then it is often useful to have another function that can take the elements in the codomain and send them back to their original domain values. The latter is called the inverse function.

In order for a function to have an inverse function, it must possess two important properties, which I explain now.

The Injective Property

Let the domain be the set of days of the week. In Haskell one can create the set using a data type definition such as this:

data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday

Let the codomain be the set of breakfasts. One can create this set using a data type definition such as this:

data Breakfast = Eggs | Cereal | Toast | Oatmeal | Pastry | Ham | Grits | Sausage

Now I create a function that maps each element of the domain to a value in the codomain.

Here is one such function. The first line is the function signature and the following lines is the function definition:

f  ::  Day  ->  Breakfast
f  Monday       =  Eggs
f  Tuesday      =  Cereal
f  Wednesday    =  Toast
f  Thursday     =  Oatmeal
f  Friday       =  Pastry
f  Saturday     =  Ham
f  Sunday       =  Grits

An important thing to observe about the function is that no two elements in the domain map to the same codomain value. This function is called an injective function.

[Definition] An injective function is one such that no two elements in the domain map to the same value in the codomain.

Contrast with the following function, where two elements from the domain -- Monday and Tuesday -- both map to the same codomain value -- Eggs.

g  ::  Day  ->  Breakfast
g  Monday       =  Eggs
g  Tuesday      =  Eggs
g  Wednesday    =  Toast
g  Thursday     =  Oatmeal
g  Friday       =  Pastry
g  Saturday     =  Ham
g Sunday        =  Grits

The function is not injective.

Can you see a problem with creating an inverse function for g :: Day -> Breakfast?

Specifically, what would an inverse function do with Eggs? Map it to Monday? Or map it to Tuesday? That is a problem.

[Important] If a function does not have the injective property then it cannot have an inverse function.

In other words, I can't find my way back home.

The Surjective Property

There is a second property that a function must possess in order for it to have an inverse function. I explain that next.

Did you notice in the codomain that there are 8 values:

data Breakfast = Eggs | Cereal | Toast | Oatmeal | Pastry | Ham | Grits | Sausage

So there are more values in the codomain than in the domain.

In function f :: Day -> Breakfast there is no domain element that mapped to the codomain value Sausage.

So what would an inverse function do with Sausage? Map it to Monday? Tuesday? What?

The function is not surjective.

[Definition] A surjective function is one such that for each element in the codomain there is at least one element in the domain that maps to it.

[Important] If a function does not have the surjective property, then it does not have an inverse function.

[Important] In order for a function to have an inverse function, it must be both injective and surjective.

Injective + Surjective = Bijective

One final piece of terminology: a function that is both injective and surjective is said to be bijective. So, in order for a function to have an inverse function, it must be bijective.

Recap

If you want to be able to come back home after your function has taken you somewhere, then design your function to possess the properties of injectivity and surjectivity.

share|improve this answer
    
Yes, this is a nice summary overview of the properties. Another example I have seen used: say you have a function mapping archers' arrows onto foot soldiers of an enemy's army. You surely want this function to be injective! –  Arkamis Aug 4 '12 at 22:49
    
Actually, you only need the function to be injective in order to "take you back home" (that is, to allow a pseudoinverse). –  F M Aug 5 '12 at 17:37

If you are studying algebraic structures (let's say rings) an injective homomorphism $\phi: R \longrightarrow S$ provides you with a way to interpret one ring as a subring of the other. After all, this just means that $R$ will be isomorphic to $\mathrm{Im}(\phi)$. For example, let $\phi: \mathbb{Q} \longrightarrow \mathbb{Q}[X]$ be defined by $\phi(a) = a + 0x + 0x^{2} + \cdots$. One can then check (you check!) that $\phi$ is injective and a homomorphism.

And indeed, $\mathbb{Q}$ can be interpreted as a subsystem of the ring of polynomials with coefficients in $\mathbb{Q}$, just by viewing each rational as a constant polynomial.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.