Proof of Function Cancellation Laws

Question

I have a question that reads:

Let f: A ---> B and g, g' : B ----> C be functions. Show that if g $\circ$ f = g' $\circ$ f and f is surjective $\implies$ g = g'

Unfortunately, I'm not sure how to crack open and this one and make a start on it - it seems axiomatic that g = g' so I'm not sure how to prove that it's true, just that it is true. What would the proof be on this/what's the best way of looking at it? Or at least, how might I start it?

Edit: I've had a go at it, and this is what I have so far - though it just seems too axiomatic/circular as a proof, I think?

f is surjective, thus the domain of g and g' is all of B. Then, since the compositions are equal, the image of B under these two functions is the same: g(B)=g'(B) for every b $\in$ B. (I'm wondering if the proof could stop here - i.e. because the image of a domain set of two functions is the same, that straight up means the two functions are identical? But I continue as I'm not sure).

Assume then that g' $\ne$ g. Then $\exists$ at least one element b $\in$ B s.t. g'(b) $\ne$ g(b). But g(B)=g'(B) for all b, hence g'(b)=g(b) and we have arrived at a contradiction. Hence g' cannot be different to g, and g = g'.

Now, I'm worried that that proof is either a) too circular/axiomatic etc to prove the theorem, or that b) I could have just stopped at g(B) = g'(B) and so haven't quite understood the concepts?

How did my attempt do?

Many thanks, indeed.

Answer 1

Fix a $b\in B$, since $f$ is surjective, choose some $a\in A$ such that $f(a)=b$. On the other hand, $g\circ f(a)=g'\circ f(a)$, then...

Answer 2

For an example of $g \ne g'$ consider $g(x) = x$ and $g'(x) = |x|$ and $f(x) = x^2$. $g \ne g'$ as, for example, $g(-1) \ne g'(-1)$. But $g\circ f(x) = x^2$ and $g'\circ f(x) = |x^2| = x^2$, so $g\circ f = g' \circ f$.

This is possible as for all the points $y$ where $g(y) \ne g'(y)$, (i.e all $y < 0$) there aren't any $x$ so that $f(x) = y$. (i.e. If $y < 0$ there is no $f(x) = x^2 = y < 0$)

So if $f$ is surjective then.....

Well... For every $x \in B$, Let $y$ be so that $f(y) = x$. Then $g(x) = ...$ and $g'(x) = ......$???

===== critiqueing your proof =====

f is surjective, thus the domain of g and g' is all of B.

I don't understand. The domain of $g$ and $g'$ are all of $B$ regardless of whether any other function exists.

However if $f$ is surjective, then the Image of $f$ is all of $B$. So the Image of $f$ is the entire domain of $g$ and $g'$. (Big Hint: If $f$ were not surjective, the image of $f$ would not but the entire domain of $g$ and $g'$.)

Then, since the compositions are equal, the image of B under these two functions is the same: g(B)=g'(B) for every b ∈B.

Only if $b \in $ Image of $f$; or in other words if $b \in f(A)$. You haven't correctly stated that $f(A) = B$ (although you have tried to)

In other words:

1) Because $g\circ f = g'\circ f$ then $g(b) = g'(b)$ for all $b \in f(A)$.

2) Because $f$ is surjective, $f(A) = B$.

So concl: $g(b) = g'(b)$ for all $b \in f(A) = B$. Which is the definition of $g = g'$.

That is a fine and complete proof.

(I'm wondering if the proof could stop here - i.e. because the image of a domain set of two functions is the same, that straight up means the two functions are identical? But I continue as I'm not sure).

Not the images of the domain but that each point of the domain maps to the same point of the image. After all: Image($f(x) = x^3$) = Image($g(x)= x^5$) but $x^3 \ne x^5$. But for all $n \in \mathbb N$ $f(n) = n^2$ and $g(n) = \sum_{n=1}^n (2n-1)$ and $f(n) = g(n)$ therefore $f = g$.

But, yes, you could stop there--- If you have proven that $g(b) = g'(b)$ for all $b \in B$. Which you would have if you had proven $f(A) = B$. Which it does if $f$ is surjective.

Assume then that g' ≠g. Then ∃ at least one element b ∈ B s.t. g'(b) ≠ g(b). But g(B)=g'(B) for all b,

You need to explain why $f$ being surjective leads to this. We don't know $g(b) = g'(b)$ for all $b\in B$. We only know that $g(f(a)) = g'(f(a))$ for all $a \in A$.

We must prove that for all $b \in B$ that $b = f(a)$ for some $a \in A$. And we know that is true because $f$ is surjective.

.....

So if $f$ *isn't surjective, there are some $B' \subset B$ so that $B'$ is is not in the image of $f$. So we can have many $g(b) \ne g'(b)$ for $b \in B'$ but have all $g(c) = g'(c)$ for all $c \in f(A)$ and then $g\circ f = g'\circ f$.