I am a undergraduate majoring in CS. In preparation for a discrete mathematics exam coming up next week, I am looking through problems I got wrong on the homework. A concept I don't understand are surjections, injections, and bijection. From lecture, for a function to be a bijection, it has to be both an injection and a surjection. So say I proved a function is not a surjection, why couldn't I say that it has to be injection since we know it can't be a bijection by definition?
So my homework problem is in the link below.
Problem 4.26. Let $A$, $B$, and $C$ be sets and let $f\colon B\to C$ and $g\colon A\to B$ be functions. Let $h\colon A\to C$ be the composition, $f\circ g$, that is, $h(x)::=f(g(x))$ for $x\in A$. Prove or disprove the following claims.
- (a) If $h$ is surjective, then $f$ must be surjective.
- (b) If $h$ is surjective, then $g$ must be surjective.
- (c) If $h$ is injective, then $f$ must be injective.
- (d) If $h$ is injective and $f$ is total, then $g$ must be surjective
I got a) True b) False c) True d) False
When the answer is supposed to be a) True b) false c) false d) true
I think the reason why I got them wrong is because I assumed that if a function is not surjective, then it has to be injective and vice versa. Could someone help me understand this concept? That would be much appreciated!
I think the simplest way to identify things like this as false (in those cases that are false) is to find counterexamples in sets of perhaps two or three members.
One of the statements says "If $h$ is injective, then $f$ must be injective." $$ A=\left\{ \begin{array}{c} 1 \\ 2 \\ 3 \end{array} \right\} \overset{g} \longrightarrow B = \left\{ \begin{array}{c} a \\ b \\ c \\ d \end{array} \right\} \overset{f} \longrightarrow C = \left\{ \begin{array}{c} p \\ q \\ r \end{array} \right\} $$ $$ \begin{array}{rr} f(1) = a, & g(a) = p, \\ f(2) = b, & g(b) = q, \\ f(3) = c, & g(c) = r, \\ & g(d)= r. \end{array} $$ Then $f\circ g$ is injective and $f$ is not injective. And $f\circ g$ is surjective although $g$ is not surjective.
"If $h$ is surjective, then $f$ must be surjective." That one is true. If $f$ didn't map some member of $B$ to $c$, then neither would $f\circ g$.
"If $h$ is injective and $f$ is total, then $g$ must be injective." As most mathematicians define "function", all functions are "total", but in computer science it is necessary to consider total and partial functions. I take "$f$ is total" to mean it is well defined at every member of $B$ rather than only some of them. If $g$ is not injective, then it takes two members of $A$ to the same member of $B$; say $g(1)=g(2)=a$. Since $f$ is total, $f(g(1))$ and $f(g(2))$ both exist, and they must be equal since $g(1)=g(2)$. Therefore $h$ would not be injective.
Epilogue:
I once heard a confused undergraduate say "onto is the opposite of one-to-one." That of course is nonsense, but there is a deeper sense in which something similar is true. Suppose $$ g: A \longrightarrow B $$ (and that means $g$ is a total function) and for subsets $B_1\subseteq B$, let $g^{-1}(B_1) = \{ a\in A: g(a)\in B_1 \}$. There is no need for an inverse function $g^{-1}$ to exist for this to be well defined. Let $k(B_1) = g^{-1}(B_1)$, so $k$ is a function from the set of all subsets of $B$ into the set of all subsets of $A$. Then: \begin{align} g \text{ is injective if and only if } k \text{ is surjective.} \\[6pt] g \text{ is surjective if and only if } k \text{ is injective.} \end{align}