Please send typos/corrections to david.hodge at
gcu.ac.uk
Topic: Functions / mappings
Objectives
Investigate the property known as one-to-one, or 1-1, or injective for functions
Investigate the property known as onto or surjective for functions
Introduction
These notes will assume you are a little comfortable with the idea of
a function1 Also called a map or a mapping.
The key fact about a function is that every
permitted input has exactly one output.
Understanding this key fact is vital for moving onto the difficult
properties known as injectivity and
surjectivity.
Here’s a sample diagram showing a function which takes \(a\), \(b\), \(c\)
or \(d\) as inputs and gives out
integer values between \(1\) and \(5\). Notice every point on the left (from
the domain) has exactly one line coming out of
it, going into exactly one point on the right.
A basic mapping diagram
If we call this function \(f\)
then
\[f(a)=5,\; f(b)=4,\; f(c)=1,\;
f(d)=3\]
The first term: injective or one-to-one
Firstly we must discuss the ridiculous number of names for the same
adjectives describing a function.
The following three statements all mean exactly the same
thing
A function f is injective2 a very technical term
A function f is one-to-one3 a confusing less technical sounding term
A function f is 1-14 a lazy shorthand for one-to-one
The term one-to-one is particularly
misleading, as you are about to discover.
Definition
A function is injective (or one-to-one) if
Whenever you pick one value achieved by the function
on right-hand side, investigation shows that it’s achieved from
only one input.
This is very difficult to grasp when you first learn it because it
sounds very similar to our Key Fact above about functions5 which is the reason many people dislike the term
one-to-one and prefer injective. Note the difference
in these two statements:
Every individual input to a function results in a single output
value.
Every output value from a function came from only one input
value.
The first box is a statement of fact about every
function6 it’s what it means to be a function!.
The second box is not always a fact. If it happens to be true for a
function then we say that function is one-to-one or injective.
Some examples of injectivity for you to try
Which of the following four diagrams, each representing a different
function, has the injective property7 property is used here like the word characteristic, we
say metals have certain properties to describe what they are like. The
same is true here, but with a function.?
Function 1
Function 2
Function 3
Function 4
For a discussion of the answers, see the bottom of these notes.
This property is actually easier to understand as it is less easily
confused with the definition of what it means to be a function.8 it’s still a little weird!
This property only has two standard names. The following two
statements both mean exactly the same thing
A function f is surjective9 a very technical term
A function is onto10 a less technical sounding term
The slightly weird thing about being surjective is that whether a function is
surjective or not depends upon the
set of values you think it can take!11 You might be screaming now that this sounds
subjective! In the diagrams above the set drawn on
the right-hand side is the set we care about, this is often called the
co-domain12 with the left hand set of inputs called the
domain. However, some authors call it the
range which can be confusing13 let’s not open that can of worms here!.
Definition
A function is surjective (or
onto) if
Every value in your identified set of possible output values is
achieved by at least one of your inputs.
In terms of the picture diagrams above, this one is very easy… does
every point in the set on the right-hand side have at least one arrow
coming into it? Are they any points in the right hand set with no arrows
coming in?
If all right-hand side points have an arrow coming in… then it’s
surjective.
The quite strange thing here is that suppose you have a function
which is not surjective because there are some points with no arrows
coming in. You might complain and ask… ‘Then why bother to draw them in
the first place?’ or ‘Why not pretend this points aren’t possible
outputs?’
These are both great questions, and the answer is that if you are
allowed to go back and change you co-domain after seeing all
the function output values, so that there are no lonely points then you
have turned your function into a surjective one!14 You’re just not normally allowed to do this, especially
when comparing multiple functions with similar output sets
Now for some examples for you to try…
Some examples of surjectivity for you to try
Which of the following four diagrams, each representing a different
function, has the surjective
property?
Function 5
Function 6
Function 7
Function 8
Bonus question: do any of the eight function
diagrams above show a function which is both injective and surjective?
Definition
A function which is both injective
and surjective is called bijective15 notice ‘bi’ meaning two, because it’s both the
‘jectives’?!. Such functions are
generally very nice.
The property bijective functions
have is that you can move left to right then back to left again; or
right to left and back to right again on the mapping diagram and always
get back to where you started. This means that the procedure of un-doing
the function and re-doing it, or doing the function and un-doing it
always end up back where you started. This is the idea of invertibility discussed in many areas of
maths. It’s vital for being able to reverse engineer the answer to a
question, for example in decoding.
Answers to injective questions
Our plan is to identify injectivity
when it occurs. This means making sure no elements in the right-hand set
of all the diagrams have more than one arrow coming into them. It’s that
easy, once you know how!
Function 1
Function 1: Clearly not injective as both \(1\) and \(4\) have more than one input that result in
them. e.g. \(f(b)=f(d)=1\) an example
of two inputs both giving the same input. Not injective.
Function 2
Function 2: There’s only one problem value here but it’s still not
injective. You need every output to have only one
source input. Here the output of \(3\)
comes from both \(b\) and \(d\). Not injective.
Function 3
Function 3: This is definitely not injective! There are four
different inputs all leading the same output of \(4\)!
Function 4
Function 4: This is injective.
Every input is mapped to a different output, so every output
only has one arrow coming in. Injective.
In the Function 4 discussion there is another sentence which can be
useful to remember:
Every input is mapped to a different output
This is another way to check if a function is injective (but veers
closer to the earlier confusion, so I’ve not mentioned it until now).
It’s not a shortcut to showing a function is injective, because you
don’t just need to find two inputs that go to different places. You need
to show every pair of inputs go to different outputs.16 It does provide an easy way to show a function is not
injective. Just find two input values that go to the same place.
e.g. the \(f(x)=x^2\) function for all
integers. We know that \(f(-3)=f(3)=9\)
so it is not injective.
Answers to surjective questions
Our plan is to identify surjectivity when it occurs. It’s as easy
as looking at the sets on the right-hand side and seeking out any
examples of elements which have zero incoming arrows.
Function 5
Function 5: Not surjective. The value \(1\) is not the output of any of the
inputs.
Function 6
Function 6: (Very!) Not surjective. The value \(1\) is not the output of any of the
inputs17 Values \(2\) and \(4\) are also not outputs, but any one of
them having this property was enough to be not surjective.
Function 7
Function 7: This is surjective.
You’ll notice that \(1\), \(2\), \(3\)
and \(4\) all have exactly one arrow
coming in. For every possible output you can find (at least one18 more than one is okay, we’re talking surjectivity not
injectivity here!) input
that reaches it.
Function 8
Function 8: This example is also surjective. Notice that I removed \(1\) from the output set, every element in
the output set19 called the co-domain that we’re considering, is reached by at
least one of the inputs20\(2\) is reached from
two different inputs, but we don’t care.
Bijectivity of the functions given
Were there any functions that were both surjective and injective. You’ll need to go back and answer
the questions for the other sets of functions to find the answer. None
of the first four functions was surjective, but Function 7 was surjective and a quick inspection shows
every output reached from only one input, so it’s also injective. So Function 7 is bijective!
As a test, pick any point on the left of Function 7, follow any
arrow21 there’ll only be 1 because it’s a function!
to the right and pick any arrows back22 there’ll only be one because it’s injective and you’ll be back
where you started.
Function 7
Now also try the same with the right-hand side, pick any starting
element from the right, follow any arrow23 exactly 1, because the function is surjective and injective back to the input
set, and then following the only function line out of that input gets
you back to where you began. Well done!
