How to Prove a Function Is Injective and Surjective

Some examples on proving/disproving a function is injective/surjective (CSCI 2824, Spring 2015)

This page contains some examples that should help you finish Assignment 6.

(See also Section 4.3 of the textbook)

Proving a function is injective

Recall that a function F:Ato B is injective/one-to-one if

forall, x,uin A, F(x)=F(u) implies x=u .

Example 1: Disproving a function is injective (i.e., showing that a function is not injective)

Consider the function

$f:mathbb{R}^2tomathbb{R} : (x,y)mapsto sqrt{x^2 + y^2}$ .

(This function defines the Euclidean norm of points in $mathbb{R}^2$ .) Recall also that $mathbb{R}^2 triangleq mathbb{R}timesmathbb{R}$ .

Claim: is not injective.

Proof

Note that $(1,2),(2,1)inmathbb{R}^2$ are distinct and f(1,2)=sqrt{5}=f(2,1) . Hence is not injective. QED.

Example 2: Proving a function is injective

Consider the function

$g:mathbb{R}^2to mathbb{R}^2 : (x,y)mapsto (2x-y, -x+2y)$ .

Claim: is injective.

Proof

Fix any $(x,y), (u,v)in mathbb{R}^2$ satisfying .
By definition of , we have .
The equality of the two points in $mathbb{R}^2$ means that their coordinates are the same, i.e.,
Multiplying equation (2) by 2 and adding to equation (1), we get .
Then , or equivalently, .
On the other hand, multiplying equation (1) by 2 and adding to equation (2), we get , or equivalently, .
Therefore .
This proves that is injective. QED.

Proving a function is surjective

Recall that a function F:Ato B is surjectiveonto if

forall, yin B, exists, xin A left(, y= F(x), right) .

To prove that a function is surjective, we proceed as follows:
To prove that a function is not surjective, simply argue that some element of cannot possibly be the output of the function .

Example 3: disproving a function is surjective (i.e., showing that a function is not surjective)

Consider the function

$h:mathbb{Z}tomathbb{Z}: xmapsto x^2$ .

Claim: is not surjective.

Example 4: disproving a function is surjective (i.e., showing that a function is not surjective)

Consider the absolute value function

h:mathbb{R}tomathbb{R}: xmapsto |x| .

Claim: is not surjective.

Proof

Note that for any in the domain , must be nonnegative.
On the other hand, the codomain includes negative numbers.
Hence is not surjective.

Example 5: proving a function is surjective

Consider again the function

$g:mathbb{R}^2to mathbb{R}^2 : (x,y)mapsto (2x-y, -x+2y)$ .

Claim: is injective.

Scrap work

Fix any in the codomain $mathbb{R}^2$ .
We want to find a point in the domain satisfying .
Note that if and only if .
This is equivalent to and .
We are going to express in terms of .
Note that the first equation implies .
Substituting this into the second equation, we get .
Rearranging to get in terms of and , we get $x=frac23 u +frac13 v$ .
Now we work on . The second equation gives .
Substituting into the first equation we get .
Rearranging to get in terms of and , we get $y=frac13 u + frac23 v$ .
Hence the input we want is $(x,y)=(frac23 u+frac13 v, frac13u +frac23 v)$ .

Proof

Fix any in the codomain $mathbb{R}^2$ .
Consider $(x,y)=(frac23 u+frac13 v, frac13u +frac23 v)$ .
Note that lies in the domain $mathbb{R}^2$ and

$begin{array}{rcl} g(x,y)&=&(2x-y, -x+2y) &=& (2(frac23 u+frac13 v) -frac13u +frac23 v, -(frac23 u+frac13 v) + 2(frac13u +frac23 v) ) &=&(u,v). end{array}$

This shows that is surjective.

Finding the inverse

Once we show that a function is injective and surjective, it is easy to figure out the inverse of that function. The inverse is simply given by the relation you discovered between the output and the input when proving surjectiveness.

Only bijective functions have inverses!

Example 6

Consider the function

k:mathbb{R}tomathbb{R}: xmapsto 2x-1 .

We claim (without proof) that this function is bijective. So what is the inverse of ?

Fix any .
Consider the equation and we are going to express in terms of .
Using the definition of , we get , which is equivalent to $x=frac12 (y+1)$ .
Therefore the inverse of is given by

$k^{-1} : mathbb{R}tomathbb{R} : ymapsto frac12 (y+1)$ .

Example 7

The function

$g:mathbb{R}^2to mathbb{R}^2 : (x,y)mapsto (2x-y, -x+2y)$

that we consider in Examples 2 and 5 is bijective (injective and surjective). The inverse is given by

$g^{-1} : mathbb{R}^2tomathbb{R}^2 : (u,v) mapsto (frac23 u+frac13 v, frac13u +frac23 v)$ .

Note that this expression is what we found and used when showing is surjective.

How to Prove a Function Is Injective and Surjective

Source: https://home.cs.colorado.edu/~yuvo9296/courses/csci2824/sect19-functions-examples.html

How to Prove a Function Is Injective and Surjective

Some examples on proving/disproving a function is injective/surjective (CSCI 2824, Spring 2015)

Proving a function is injective

Example 1: Disproving a function is injective (i.e., showing that a function is not injective)

Example 2: Proving a function is injective

Proving a function is surjective

Example 3: disproving a function is surjective (i.e., showing that a function is not surjective)

Example 4: disproving a function is surjective (i.e., showing that a function is not surjective)

Example 5: proving a function is surjective

Finding the inverse

Example 6

Example 7

0 Response to "How to Prove a Function Is Injective and Surjective"

Post a Comment

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel