# Surjective Maps and right cancellation

I'm working through Jacobson's Basic Algebra I, and I have a question about Exercise 3 in Section 0.2. The first part asks the reader to "Show that $S \xrightarrow{\rm \alpha}T$ is surjective if and only if there exist no maps $\beta_1, \beta_2$ of $T$ into a set $U$ such that $\beta_1 \ne \beta_2$ but $\beta_1\alpha = \beta_2\alpha$."

I'm not sure that this is correct if $U$ has only one element. For example, let $S = \{0, 1\}$, $T = \{0,1,2\}$, and $U = \{0\}$. Let $\alpha$ be defined by the graph $\{(0,0), (1,1)\}$. Then $T \xrightarrow{\rm \beta}U$ given by the graph $\{(0,0), (1,0), (2,0)\}$ is the only map from from $T$ to $U$. Thus there are no distinct maps $\beta_1, \beta_2$ from $T$ to $U$ such that $\beta_1\alpha = \beta_2\alpha$, and yet $\alpha$ is clearly not surjective.

I am open to the possibility that I am missing something.

Thanks!

-
What is actually meant is that there is no set $U$ and no maps $\beta_1,\beta_2$ of $T$ into $U$ such that $\beta_1\ne\beta_2$ but $\beta_1\alpha=\beta_2\alpha$. –  Brian M. Scott May 1 '12 at 3:23
Maybe it would help to write an equivalent form for the $Q$ in this $P \Leftrightarrow Q$ statement: for every set $U$ and maps $\beta_1, \beta_2\colon T \to U$, $\beta_1 \circ \alpha = \beta_2 \circ \alpha$ implies $\beta_1 = \beta_2$. –  Dylan Moreland May 1 '12 at 3:24
I'm not sure "uniqueness of left inverses" is accurate here. What Jacobson is actually talking about is right cancellation for surjective functions. That is, $\alpha$ is surjective if and only if it can be cancelled on the right: whenever $\beta_1\alpha=\beta_2\alpha$, we have $\beta_1=\beta_2$. But a surjective function has a left inverse if and only if it is bijective. –  Arturo Magidin May 1 '12 at 4:38
Thanks for fixing the subject, Arturo. You're correct. –  David May 1 '12 at 22:03

In order to show that the characterization is false, since your $\alpha$ is not surjective, you would need to show that even though $\alpha$ is not surjective, the condition is satisfied.
So you would need to show that there does not exist a set $U$ and a pair of maps $\beta_1,\beta_2\colon T\to U$ such that $\beta_1\circ\alpha=\beta_2\circ\alpha$ and $\beta_1\neq\beta_2$. Equivalently, that for all sets $U$ and all $\beta_1,\beta_2\colon T\to U$, if $\beta_1\circ\alpha = \beta_2\circ\alpha$, then $\beta_1=\beta_2$. Your $U$ is an example of a set that does this, but it does not establish that $\alpha$ has the desired property: you've just come up with one example that works, but the condition requires you to prove that for every choice of $U$ and every choice of $\beta_1$ and $\beta_2$, you have $\beta_1\circ\alpha=\beta_2\circ\alpha$ implies $\beta_1=\beta_2$. (That would show that $\alpha$ satisfies the condition, even though it is not surjective).
(In short, the condition negates the existence of a set $U$ with a given property $P$, which means that the condition is actually a universal statement about all possible choices of sets $U$, since $\neg(\exists U (P(U))$ is equivalent to $\forall U (\neg P(U))$. You've come up with one example of set $U$ for which $\neg P(U)$ holds, but an example does not prove a universal statement.)
And in fact, for your choice of $\alpha$, you will not be able to do this: pick $U=\{a,b\}$. Let $\beta_1\colon T\to U$ be given by $\beta_1(0)=\beta_1(1)=\beta_1(2)=a$, and let $\beta_2\colon T\to U$ be given by $\beta_1(0)=\beta_2(1)=a$, $\beta_2(2)=b$. Then $\beta_1\circ\alpha = \beta_2\circ\alpha$, but $\beta_1\neq\beta_2$.