Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
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
up vote 1 down vote accepted

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$.

share|cite|improve this answer
Thanks Brian, Dylan, and Arturo. I believe you're all saying the same thing, which is that my understanding of the quantification of U in the problem is incorrect. I'm now convinced that you are correct. – David May 1 '12 at 22:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.