Answers to HW #2

Let f:X->Y and g:Y->Z be functions.

1. Give an example where g o f is onto, but f is not onto.

Let X = {a}, Y = {3,green}. Let f = {(a,green)}, and g = {(3,a),(green,a)} (the only possibility for g).

2. Assume g o f is 1:1, and f is onto. Show that g is 1:1.

Let y1,y2 in Y have g(y1)=g(y2). We want to show y1=y2.
Since f is onto, there exist x1,x2 such that f(x1)=y1, f(x2)=y2.
So (g o f)(x1) = g(f(x1)) = g(y1) = g(y2) = g(f(x2)) = (g o f)(x2).
Since g o f is 1:1, x1 = x2.
Hence f(x1) = f(x2), i.e. y1=y2.
So g is 1:1.

3. Let X have 2 elements and Y have n elements. Show, by induction on n, that the number of 1:1 functions from X to Y is n²-n.

[Actually it was silly to do this by induction, I realized later -- one can count all function, n², and subtract the noninjective ones, in which both elements of X go the same place. There are obviously n of those, depending on the choice of place.]

If Y is empty, there are no functions, and 0 = 0² - 0.
Otherwise, we may pick an element y in Y.
The functions f from X to Y that don't hit y (i.e. such that there doesn't exist any x s.t. f(x)=y) are exactly the same as the functions from X to Y \ {y}.
By induction, the number of those is (n-1)² - (n-1) = n² - n - 2(n-1).
So how many more 1:1 functions are there from X to Y, that do hit y?
Call the elements of X be {a,b}.
Then either f(a) = y, and f(b) is not y (since f is 1:1); there are n-1 choices for f(b).
Or f(a) is not y, in which case f(b) must be y (since f hits y); there are n-1 choices for f(a).
So there are 2(n-1) more functions,
for a total of (n² - n - 2(n-1)) + 2(n-1) = n² - n.

4. Assume that X=Z, so g:Y->X.
The function I:X->X such that I(x)=x for all x in X is called the identity function.
(Every set's got one!)
Call g a left inverse of f if g o f is the identity function on X.

a. If g is a left inverse of f, show that f is 1:1.

Let x1,x2 be in X, and assume f(x1)=f(x2). Apply g to both sides. Then x1 = I(x1) = (g o f)(x1) = (g o f)(x2) = I(x2) = x2.

b. If f is 1:1 and X is nonempty, show that f has a left inverse.

Since X is nonempty, we may pick some element x₀ in X.
Define g:Y->X as follows.
For each y in Y such that there exists an x in X with f(x)=y, let g(y)=x.
For the remaining y in Y, let g(y) = x₀.

First we have to argue that this g really is a function, i.e. that it assigns a unique value to every y. Certainly it assigns a value, since we caught any stragglers with "for the remaining y...". If in the first line, g(y) was pointed toward x1 and x2, then f(x1)=y=f(x2). But since f is 1:1, this forces x1=x2.

Second, we have to show that this g is a left inverse.
For all x in X, g(f(x)) = x by the first line of the definition of g.

[One could also define g as a set of ordered pairs; it is the union of {(y,x) : (x,y) in f} and {(y,x₀) : there doesn't exist x in X with f(x)=y}. Then one again has to use injectivity of f to show that this is indeed a function.]

c. If X is empty, show that f is 1:1, and determine when it has a left inverse.

One definition of f 1:1 started with "given two elements x1,x2 of X, unequal, ..." but there are no two such elements. So the condition is vacuously true.

For g to be a function from Y to an empty set X, Y has to itself be empty. In this case f has a left inverse: the empty function.