Discrete Math: Functions

Question

1. Prove or disprove the following: If f is 1-1 and g is onto, then gof is onto
2. Prove or disprove the following: If gof exists and f inverse, g inverse exist, then (gof)^-1 = f^-1 o g^-1

Answer 1

1. Suppose we have a function f which maps from its domain D into a co-domain C

f: D -> C

To be 1:1 means that every element in D maps to a unique element in C. We can't have a many to 1 mapping, where multiple elements in D map to the same element in C. The way mathematicians say that formally is

if d_1, d_2 in D and f(d_1) = f(d_2), then d_1 = d_2

Note that this is primarily a statement about the domain D. Everything in it maps to something unique in the co-domain C. BUT, we don't know whether the range of f covers C or not. It could be that there are elements in C that aren't mapped to by f. That's where the concept of "onto" comes in. A mapping onto a codomain C means the range R of f completely fills C. So being onto is a primarily a statement about the codomain C.

More formally, the way mathematicians express this is

Let g: D_g -> C_g

for every c in C_g, there exists a d in D_g such that g(d) = c

Observe that being 1:1 and onto are separate criteria. To illustrate, nothing in the definition of onto prevents multiple d in D from mapping to the same c in C. It merely says that each c has some d, not that it is unique.

Now, when we compose functions, the output of the inner function becomes the input to the outer function. In math speak, that means the codomain of one function is in the domain of another function. In our example, if

(g o f) : D -> C_g

then C must be a subset of D_g. But since f is only 1:1, we have no guarantee that its range is onto D_g.

Thus, this proposition is false. To show something is false, we only need to provide a counterexample. So we can choose any 1:1 function that isn't onto. For simplicity, let's choose the integers:

f(n), g(n) : Z -> Z

f(n) = 2n

g(n) = n

g(f(n)) = 2n

which we can see is always even. It isn't onto because the odd integers aren't mapped to.

2. An inverse f^-1 of a function f has the property

(f o f^-1) (x) = (f^-1 o f) (x) = x

or more simply in function notation

f o f^-1 = f^-1 o f = id = the identity function

The property of the identity is that for any function it returns that function

f o id = id o f = f

Suppose also that g has an inverse

g o g^-1 = g^-1 o g = id

If (g o f) has an inverse, then we must show

(g o f) o (g o f)^-1 = (g o f)^-1 o (g o f) = id

The proposition is (g o f)^-1 = f^-1 o g^-1. Would this work? Let's plug it in and see. First test the right hand inverse

g o f o f^-1 o g^-1 = g o id o g^-1

because f has an inverse, the property of the identity gives us

= g o g^-1 = id

and lastly because g has an inverse. Similarly for the left hand inverse

f^-1 o g^-1 o g o f o = f o id o f^-1 = f o f^-1 = id

Thus, this proposition is true. Note that the mark of a tight proof is that we must use all of our givens. We required the f and g both had inverses in order to complete our proof, which is usually a sign we are on the right track.

Feel free to contact me for tutoring if you'd like more help with discrete math. Cheers.