Problem 110 pts If functions f and f g are onetoone does it

Problem 1[10 pts]: If functions f and f g are one-to-one does it follow that g is one-to-one? If your answer is “Yes” give a proof, otherwise give a counterexample.

Problem 2[10 pts]: If functions f and f g are onto, does it follow that g is onto? If your answer is “Yes” give a proof, otherwise give a counterexample.

Problem 3[15 pts]: Suppose f : A A is a bijective function where A is a nite set and |A| = n. Prove that there is an integer m n and a a A such that fm(a) = a where fm denotes the m fold composition of f, for example f2(x) = f f(x),f3(x) = f (f f(x)), and so on.

Solution

1 Yes. If f and f o g are one-one functions, g is also one-one. Proof is by contradiction. Suppose g is not one-one then we prove that either f is not one-one or f o g is not one-one.

Let g: A B and f: B C. By assumption, since g is not one-one, there exists 2 distinct elements x1 and x2 such that g(x1) = g(x2) = y where y belongs to B. Let f(y) = z for some z belonging to C. Thus, f o g (x1) = f o g (x2) = z. Hence f o g cannot be one-one. This means that if f and f o g are one-one, g has to be one-one using the fact that p q ¬q ¬p

2 No. A counter example as our proof

Let f = ln(x) and g(x) = e^x . Clearly, f is onto and fog = ln(e^x) = x is also onto.

However, g is not onto since g(x)=e^x is >0 for all x.