Functions and Inverses

Date: 05/29/2002 at 01:42:57
From: Marianne Richa
Subject: Functions (Surjection, Bijection)

Hi Dr. Math,

I was doing the following exercise and I couldn't find when both are 
injective and surjective:

  Let A, B, and C be three sets, and f:A->B, g:B->C are two 
  functions.  

  Define A, B, C, f and g such that (g o f) is both injective and 
  surjective, but f is not surjective and g is not injective.

Thanks for your help.
Best Regards
Marianne

Date: 05/29/2002 at 12:53:52
From: Doctor Peterson
Subject: Re: Functions (Surjection, Bijection)

Hi, Marianne.

Let's try to picture it. Since f is not surjective, the image of A 
(range of f) must be only part of B:

                      +---------------+
                      |       B       |
    +-----+           |    +-----+    |
    |     |      f    |    |     |    |
    |  A  |--------------->|  A' |    |
    |     |           |    |     |    |
    +-----+           |    +-----+    |
                      |               |
                      +---------------+

But when we follow that with g, the composition must be both 
injective and surjective, so C must be "the same size as" A, and must 
be the image of A':

                      +---------------+
                      |       B       |
    +-----+           |    +-----+    |             +-----+
    |     |      f    |    |     |    |     g       |     |
    |  A  |--------------->|  A' |----------------->|  C  |
    |     |           |    |     |    |             |     |
    +-----+           |    +-----+    |             +-----+
                      |               |
                      +---------------+

Now g is defined on all of B, so clearly it must not be injective; it 
must take the rest of B into C as well.

There are many ways to do this. One easy way is to take A, B, and C 
as the integers, and take f as

    f(x) = 2x

This is not surjective, but is injective; its image is the even 
integers. Now can you find a g that will take these to all integers?

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 05/29/2002 at 14:23:51
From: Marianne Richa
Subject: (Continued)

Hi,

I understood all that you wrote, but still I couldn't define 
g(x).  Could it be 3x?

Thank you.

Date: 05/29/2002 at 14:41:59
From: Doctor Peterson
Subject: Re: (Continued)

Hi, Marianne.

You don't sound very sure ... so you probably aren't right! Did 
you try finding the composite (f o g) and seeing if it fits the 
requirements; or check whether your g is surjective?

You want a function g that is sort of an inverse of f; for every 
integer, there should be some even number that g will take there. 
Since we made f double each integer, what if g divides by 2? The 
problem is, the odd integers won't go to integers then, so you'll 
need a different definition for the function in that case. If you 
think about it, you'll realize that it really doesn't matter what 
you choose to do with the odd numbers (which are B-A' in my picture).

You might like to try a different solution. Suppose we just made 
A = {1,2,3} and B = {4,5,6,7} and C = {8,9,10}. Can you follow my 
picture to define f and g by just naming where each function takes 
each element of its domain?

The concepts of injective and surjective functions become almost 
trivial if you learn to picture them right. This page may help a 
little:

    http://mathforum.org/library/drmath/view/52454.html

You can find more help by searching our site for those words.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/