Last edited 7/15/2009 7:50:00 PM
Properties of
functions
Injectivity
Definition: injective
A function 
is injective if for any
elements in the domain A,
if then .
Useful rewordings of the definition:
¨ is injective if and only if for all ,
if then .
This is the contrapositive of the definition, and so is
equivalent
to it. In many cases it is the best version of the
definition to use in a proof.
¨ is injective if and only if different inputs
give different outputs.
¨ is injective if and only if its kernel is the diagonal.
¨ is injective if and only if “different
elements of A go to different
elements of B.”
Usage
¨
An injective function is called an injection or is said to be one to one.
¨
It is the whole function that is or is not
injective.
Warning Do
not try to reword this definition using the word “unique”. It is too easy to get it mixed up with the definition of functional property.
Examples
¨
The articles about most of the example
functions state whether they are injective or not. Checking each of these functions to see why
it is or is not injective is an excellent way to get a feel for the concept of
injectivity.
¨
The doubling function is injective on the real numbers and in fact
on the complex numbers. Doubling
different numbers gives different numbers.
¨
The squaring function is not injective, because for example . Squaring different numbers might give you the
same number.
¨
The cubing function on the reals is
injective. It is not injective on the
complex numbers, because for example
¨
See Wikipedia for more examples and more discussion.
Understanding injectivity
No information loss
An injective function loses no information. If you have an output from the function, you
know it came from exactly one input.
¨
If you
got 8 when you cubed a real number, the real number had to be 2. The cubing function is injective on the reals.
But if you got 8 when you cubed a complex number, the complex number could be
any of three numbers (see above); the cubing function is not injective on the
complex numbers.
¨
If you got 4 when you squared something, the
something could have been either 2 or 2: You lost some information about the input,
namely its sign in this case. The squaring
function is not injective.
¨
If you get as an output from the sine
blur function, it could have come from any one of an infinite number of inputs. The sin blur function is ridiculously
noninjective.
Embeds as a substructure
Some functions preserve some structure. For example, multiplying integers by 2
preserves addition. In other words, if
you let be defined by ,
then (write it out, don’t just believe me!). This makes it a group homomorphism. Because multiplying by 2 is injective, this
says that the substructure of the group of integers with addition as operation
that consists of the even integers is a copy of
the group of integers itself.
Horizontal line crosses the graph only once
at most
Let be a real continuous function. Then F is
injective if no horizontal line cuts it twice.
This is a useful way of thinking about injective continuous functions,
but it doesn’t work with arbitrary functions.
a) This
is a plot of part of (which is injective) with some horizontal
lines
b) On
the other hand, is not injective. Note that some horizontal
lines cut it more than once, but others cut it only once.
c) Horizontal lines don’t have to cut a function at
all. This is part of . Horizontal
lines below zero don’t cut its graph because 0 is its minimum. There are horizontal
lines that cut it twice, so it is not injective.
Surjectivity
Definition: surjective
A function is surjective if and only if
for every element b in the codomain B there is an element in the domain
A for which .
Useful rewordings of the definition:
¨ is surjective if and only if the image of F is
the same as the codomain B.
¨ is surjective if and only if “every element of
B comes from an element of A.”
Examples
¨ Let be the squaring function, so for every real number x. Then F is not
surjective, since for any negative number b, there is no real number a such that F(a) = b. (You can’t solve ,
for example).
¨ But if you define (where denotes the set of nonnegative reals) by ,
then G is surjective. As you
can see, whether a function is surjective
or not depends on the codomain you specify for it. Note that “G is surjective” says exactly that every nonnegative real number has a square root.
Usage
Another way of saying that is surjective is to say, “F is surjective onto B”, or simply, “F is onto B”. Saying it this way does not depend on whether you use the loose
or strict
definition for functions.
Example
A function is surjective if every horizontal line
crosses its graph (one or more times). Check out the graphs (a) through (c) above:
and are surjective onto ,
but is not surjective onto . H is surjective onto the set of nonnegative real numbers.
Exercise
How do you prove
that a function F:A→B is not surjective?
Exercise
Let α be a relation
on A.
Exercise
Show that if α is reflexive,
then the coordinate functions p1 α :α→A and p2 α :α→A are surjective.
Exercise
Show that the converse
of (a) need not be true.
Exercise
hard[ label:
cantorex] Show that there for any set S, no function from S to PS is
surjective. Do not assume S is finite.
Extended hint: If F:S→PS
is a function, consider the subset
|
{x‖x is
not an element of F(x)}
|
No argument that
says anything like "the powerset of a set has more elements than the
set" can possibly work for this problem, and therefore such arguments will
not be given even part credit. The reason is that we have developed none of the
theory of what it means to talk about the number of elements of an infinite
set, and in any case this problem is a basic theorem of that theory.
Let's be more
specific: One such invalid argument is that the function that takes
x to {x} is an injective function from S to PS, and it clearly leaves
out the empty set (and many others) so PS has "more elements" than S.
This is an invalid argument. Consider the function from N to N that takes
n to 42n. This is injective and leaves out lots of integers, so does N have
more elements than itself?? (In any case you can come up with other functions
from N to N that don't leave out elements.)
Bijectivity
Definition:bijective
[ label:
bijdef] A function which is both injective and surjective
is bijective.
Remark
A bijection F:A→B
matches up the elements of A and B - each element of A corresponds to
exactly one element of B and each element of B corresponds to exactly one
element of A.
Usage
A bijective function
is called a bijection
and is said to be a one to one correspondence.
Example
For any set A, \idA
:A→A is bijective. Another example is the function
F:{1,2,3}→{2,3,4} defined by F(1)=3, F(2)=2, F(3)=4.
Exercise
[ label:
mypbij] Show that the function G:N→Z defined by
$$G(n)=
\begin{cases}-\frac{n}{2} & \text{n even}\\\frac{n+1}{2} & \text{n odd}\end{cases}$$
is a bijection.
Exercise
Show how to
construct bijections β as follows for any sets A, B and C.
Exercise
β:A×B→B×A.
Exercise
β:(A×B)×C→A×(B×C).
Exercise
β:{1}×A→A.
Answer: (a)
β=<x,y>‖→<y,x>:A×B→B×A (or you can write
β(x,y)=<y,x> or β=λ<x,y>.<y,x>).
(b) β=
<< x,y>,z>‖→<x,<y,z>>.
(c) β= p2 (the
second projection).
Exercise
Let α be a relation
from A to B.
Exercise
Prove that α is
functional if and only if the first coordinate function p1 α is injective.
(See Section [projfromrel] .)
Exercise
Prove that α is the
graph of a function from A to B if and only if the first coordinate function is bijective.
Exercise
Give an example of a
function F:R→ R++ for which F is bijective. ( R++ is the set of positive real numbers.) Answer: One possible answer is x‖→ ex .
Exercise
hard[ label:
isexlast] Give an example of a function F:R→ R+ for which F is bijective.
( R+ is the set of nonnegative real numbers.) Answer: Here is one possible answer:
$$f(x)=\begin{cases} 0 & \text{if $x=0$}\\ e^{x-1} &\text{if $x\in \N$ and $x\neq 0$}\\ e^x & \text{if $x\notin\N$}\end{cases}$$
Note that the image
of x‖→ ex itself does not include 0.
Exercise
hard Let F:A→B be a function.
Prove that the restriction to Γ(F) of the first coordinate function
from A×B is a bijection. Answer:
A typical element of Γ(F) is <x,F(x)> for some element x
of A. Suppose p1 (x,F(x))= p1 (x',F(x')). We must show that
<x,F(x)>=<x',F(x')>. By Specification [opspec] , page ,
this requires us to show that x=x' and F(x)=F(x'). By definition of coordinate function ( [coordfunc] , page ), p1
(x,F(x))=x for any x. It follows that x=x'. But then by the singlevalued
property ( [singlevalued] ), page , F(x)=F(x').
To see that p1 is surjective,
suppose x∈A. By GS. [svvv] ,
page , there is y∈B such that
<x,y>∈Γ(F). (In fact,
y=F(x).) Then p1 (x,y)=x, so p1 is surjective.
Exercise
hard Prove that a subset
C of A×B is the graph of a function from A to B if and only if the restriction
to C of the first coordinate function is a bijection.
Exercise
hard[ label:
alphastar] Let β: Rel (A,B)→\fsA(PB) be the function which takes
a relation
α to the function α* :A→PB defined by α* (a)={b∈B‖aαb} (see Definition [reltopow] ). Show that β is a bijection.
(This function is studied further in Problem [betanat]
, page , and in Problem [betainvp] , page .)
Exercise
hard[ label:
prdprop] Let A, B and C be sets. In this exercise we define a particular
function β from the set \fsAB×\fsAC to the set \fsA(B×C), so that β
as input a pair of functions
<f,g>, with f:A→B and g:A→C, and outputs a function β(f,g) from A to B×C.
Here is the definition of β: for all a∈A,
Prove that β is a bijection.
Definition:permutation
[ label:
permdef] A permutation of a
set A is a bijection β:A→A.
Example
The fact just noted
that \idA is a bijection says that \idA is a (not very interesting) permutation
of A for any set A.
Example
[ label:
permex] The function F:{1,2,3}→{1,2,3} that takes 1 to 2, 2 to 1 and 3 to 3 is
a permutation of {1,2,3}.
Usage
[ label:
permexex] Many books define a permutation to be a list exhibiting a
rearrangement of the set {1,2,…,n} for some n. If the ith entry in the list is
ai that indicates that the permutation takes i to ai .
Example
The permutation of
Example [permex] would be given in the list notation as <2,1,3>.
Worked Exercise
List all the
permutations of {1,2,3,4} that take 1 to 3 and 2 to 4. Answer: <3,4,1,2> and
<3,4,2,1>,
Exercise
List all six
permutations of {1,2,3}.