- Suppose that $f: A \to B$ and $g: B \to C$ are functions. Prove the following:
(a) If $g \circ f$ is injective, then $f$ is injective.
Proof. Assume that $f$ is not injective. Then there exists $a,b \in A$ such that $f(a) = f(b)$ and $ a \ne b$. It follows that there is an $a,b \in A$ such that $g(f(a)) = g(f(b))$ but $a \ne b$, demonstrating that $g$ is not injective. $\Box$
(b) If $g \circ f$ is surjective then $g$ is surjective.
Proof. Assume that $g \circ f$ is surjective. Then for every $c \in C$, there exists an $a \in A$ for which $g(f(a)) = c$. Since $f$ is a function from $A$ to $B$, for each $a \in A$ there is a unique $b \in B$ such that $f(a) = b$. Consequently, there exists an element $b \in B$ such that $g(b) = c$. Thus $g$ is surjective. $\Box$
- Suppose that $g : B \to C$ is a function.
(a) Show that $g$ is injective if and only if for any set $A$ and any two functions $f_1,f_2: A \to B$ one has $g \circ f_1 = g \circ f_2 \Rightarrow f_1 = f_2$.
Proof. Assume that $g$ is injective and $g(f_1(x)) = g(f_2(x))$ for each $x \in A$. Injectivity yields $f_1(x) = f_2(x)$, so $g$ is left cancellable. Now assume that $g \circ f_1 = g \circ f2$ implies $f_1 = f_2$. Thus $g$ must be injective, otherwise we could find $f_1, f_2 : A \to B$
such that $f_1(x) \ne f_2(x).$ This completes the proof in both directions. $ \Box$
(b) Show that $g$ is surjective if and only if for any set $D$ and any two functions $h_1,h_2: C \to D$ one has $h_1 \circ g = h_2 \circ g \Rightarrow h_1 = h_2$.
Proof. Suppose that $g$ is surjective and $h_1(g(b)) = h_2(g(b))$ for some $b \in B$. Then for every $c \in C$ there exists a $b \in B$ such that $g(b) = c.$ Now if $h_1(g(b)) = h_2(g(b))$ then $h_1(c) = h_2(c)$ and $h_1 = h_2$, so $g$ is right cancellable. Now suppose that $g$ is not surjective. Then for all $b \in B$, there exists at least one $c_0 \in C$ such that $g(b) \ne c_0$. Let $D = \{m,n\}$ and define $h_1: C \to \{m,n\}$ by $h_1(c) = m$ and $h_2: C \to \{m,n\}$ by $h_2(c) = \left\{ \begin{array}{lr} m : c \ne c_0\\n : c = c_0 \end{array}\right. $. Then $h_1 \circ g = h_2 \circ g$ but $h_1 \ne h_2$. Thus if $g$ is right cancellable, then $g$ must be surjective. $\Box$
Are my proofs correct? I want to make sure that I'm not missing anything. Thanks
Best Answer
You can aim for direct proofs. Suppose that $f(x)=f(y)$. Then $gf(y)=gf(x)$, and since $gf$ is injective, this implies $x=y$. The second proofs looks good. The third proof is not good: you're talking about subsets of the product $A\times B$? This is not what you're supposed to be doing. Just to add to your vocabulary, one says $f$ is left cancellable if $fh=fg$ implies $h=g$. I will show you how to prove a function $f:A\to B$ is injective iff it is left cancellable, then you can aim try to adapt this idea to show a function $g:A\to B$ is onto iff it is right cancellable.
If $f$ is injective and $fg(x)=fh(x)$ for any $x$; injectivity gives $g(x)=h(x)$ for each $x$, so $f$ is left cancellable. Now suppose $f$ is not injective. Then there exist $a,b$ such that $f(a)=f(b)$ yet $a\neq b$, and say $f:X\to Y$. Let $2=\{0,1\}$, and define $h_1:2\to X$ by $h_1(0)=h_1(1)=a$ and $h_2:2\to X$ by $h_2(0)=a,h_2(1)=b$. Then $fh_1=fh_2$, but $h_1(1)=a\neq b=h_2(1)$.
Can you think of a similar proof to show a function $g:A\to B$ is onto iff it is right cancellable? In fancier language, the concept of injective function and monic (i.e. left cancellable) morphism, and the concept of surjective function and epic (i.e. right cancellable) morphism coincide in the category of sets, where objects are sets and arrows are functions.