5
$\begingroup$

In the category of sets, I want to prove that a morphism is an epimorphism if and only if it is surjective.

In both directions, I'm having a hard time approaching this problem.

This is how far I got.

$$\text{Morphism is epimorphism} \implies \text{Morphism is surjective}:$$ Let $\phi: A \to B$ be an epimorphism.

For any morphisms $\beta,\beta': B \to Y$, we have $$ \beta \ \circ \ \phi = \beta' \ \circ \phi \implies \beta = \beta'. $$

$$\vdots$$

$$\text{Morphism is surjective}\implies \text{Morphism is epimorphism} :$$ Pick an arbitrary $b \in B$.

Since $\phi$ is surjective there exists an $a\in A$ such that $b = \phi(a)$.

Set $y = \beta(\phi(a)) = \beta'(\phi(a))$. $$\vdots$$

$\endgroup$
  • $\begingroup$ For the first direction, prove the contrapositive - if $f$ is not surjective, find a counter-example to prove it is not an epimorphism. $\endgroup$ – Thomas Andrews Mar 10 '16 at 15:18
9
$\begingroup$

I will give a constructive (or, more precisely, intuitionistic) proof.

First, the easy direction: surjective maps are epimorphisms. Indeed, if $f : X \to Y$ is surjective and $g_0 \circ f = g_1 \circ f$, then $g_0 = g_1$, i.e. for every $y \in Y$, $g_0 (y) = g_1 (y)$, because there is $x \in X$ such that $y = f(x)$ and therefore $g_0 (y) = g_0 (f (x)) = g_1 (f (x)) = g_1 (y)$.

Now, the harder direction: epimorphisms are surjective. Suppose $f : X \to Y$ is an epimorphism. Let $\Omega$ be the set of subsets of $\{ 0 \}$, let $g_0 : Y \to \Omega$ be the constant map with value $\{ 0 \}$, and let $g_1 : Y \to \Omega$ be defined as follows: $$0 \in g_1 (y) \iff \exists x \in X . f (x) = y$$ By construction, $g_0 \circ f = g_1 \circ f$; but then $g_0 = g_1$, so for every $y \in Y$, there is $x \in X$ such that $f (x) = y$, i.e. $f : X \to Y$ is surjective.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you pinpoint where surjectivity is actually used. Here's my take; in order to show the implication of $g_0 = g_1$, we need to show that when $g_0 \circ f, g_1\circ f$ act on an arbitrary $x \ in X$ the same result occurs. Now, by surjectivity, we get the equalities $g_0(y) = g_0(f(x))$ and $g_1(y) = g_1(f(x))$. The crucial step is made when we now point out that $g_0(y) = g_0(f(x)) = g_1(f(x)) = g_1(y)$. Hence $g_0(y) = g_1(y)$. So, $g_0 = g_1$. Voila! Unlike your narrative which prematurely states $g_0 = g_1$, and then goes on to say: "Therefore $g_0(y) = \ldots = g_1(y)$". _ $\endgroup$ – Mussé Redi Mar 10 '16 at 20:32
  • $\begingroup$ It's the other way around. $\endgroup$ – Mussé Redi Mar 10 '16 at 20:34
  • 1
    $\begingroup$ Interesting - the use of impredicativity seems essential here! $\endgroup$ – Thorsten Altenkirch Apr 14 '19 at 13:59
  • $\begingroup$ This is an exceptional solution, and very conducive to formalization using a theorem verifier like Lean/Coq. $\endgroup$ – Enrico Borba Jan 11 at 21:13
10
$\begingroup$

If $f:X\to Y$ is an epimorphism, define $g_1:Y\to\{0,1\}$ with $g_1(y)=0$ for all $y\in Y$, and $$g_2(y)=\begin{cases}0&y\in\mathrm{im}(f)\\1&\text{otherwise}\end{cases}$$

Then for $x\in X$ we see that $g_1\circ f (x)=0= g_2\circ f(x)$. From the property of epimorphism, this means that $g_1=g_2$, which is only possible if $\mathrm{im}(f)$ is all of $Y$.

Now, if $f$ is surjective, then take $g_1,g_2:Y\to Z$ with $g_1\circ f = g_2\circ f$. Then for any $y\in Y$, we can find $x\in X$ such that $f(x)=y$. Then $$g_1(y)=g_1\circ f (x)=g_2\circ f(x)=g_2(y)$$

So $g_1=g_2$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I find the choice of $g_1$ and $g_2$ a bit "magic". How would this follow naturally? $\endgroup$ – Mussé Redi Mar 10 '16 at 18:35
  • 1
    $\begingroup$ These are actually the most trivial maps to distinguish the two cases - I suppose if I had switched $1$ and $0$ it would be obvious that $g_1$ is the characteristic function of $Y$ and $g_2$ is the characteristic function of $\mathrm{im}(f)$. If those sets aren't the same, the functions are different, but they agree on $\mathrm{im}(f)$. $\endgroup$ – Thomas Andrews Mar 10 '16 at 18:38
  • $\begingroup$ Does it suffice, when showing that an epimorphism is surjective, to show it for particular $g_1,g_2$? Shouldn't this choice be aribtrary, or is it? $\endgroup$ – Mussé Redi Mar 10 '16 at 20:52
  • $\begingroup$ @MusséRedi This is a very late reply (and by someone else!), but while one should prove the above for general $g_1,g_2$, it is possible to adapt the above proof into a working one. For instance, to show that ($f$ epi $\implies$ $f$ surjective), one can proceed by contrapositive and show that if $f$ is not surjective, then for any $y\in Y\setminus\mathrm{im}(f)$ we have $g_1(y)=0\neq1=g_2(y)$, and hence $g_1\neq g_2$, while $g\circ f=g\circ f$. Therefore $f$ is not an epi. $\endgroup$ – Théo Oct 3 '19 at 18:07
2
$\begingroup$

Some hints:

  • For epic $\Rightarrow$ surjective, let $Y=B \cup \{ \star \}$ (where $\star \not \in B$), let $\beta$ be the identity on $B$, and let $\beta'$ be the map which sends everything in the image of $\phi$ to itself, and everything not in the image of $\phi$ to $\star$. See what happens.

  • For surjective $\Rightarrow$ epic, just show that if $\beta,\beta' : B \to Y$ and $\beta \circ \phi = \beta' \circ \phi$, then $\beta(b)=\beta'(b)$ for all $b \in B$. Use the fact that $\phi$ is surjective to write a given $b \in B$ in a more useful way.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Wait, you are given and $f:X\to Y$, so you mean pick an $y\in Y$. Not clear what you mean here by "ley $Y=\dots$ $\endgroup$ – Thomas Andrews Mar 10 '16 at 16:52
  • $\begingroup$ How would you come about considering the union $B \cup \{ \star \}$? How would you find this naturally? $\endgroup$ – Mussé Redi Mar 10 '16 at 19:23
  • $\begingroup$ @ThomasAndrews In the notation of the OP, we're given $\phi : A \to B$. I'm then choosing $Y$ and $\beta,\beta' : B \to Y$, and then using the definition of $\phi$ being epic, to demonstrate that $\phi$ is a surjection. $\endgroup$ – Clive Newstead Mar 11 '16 at 22:23
  • $\begingroup$ @MusséRedi: The idea is to show that the image of $\phi$ is $B$. My strategy is to compose with two maps which in some sense separate the elements of the image of $\phi$ from the elements not in the image of $\phi$. If these maps are equal, it shows that the image of $\phi$ is in fact all of $B$, so that $\phi$ is surjective. We could have taken $Y = \{ 0,1 \}$, let $\beta : B \to Y$ be the constant function with value $1$, and $\beta' : B \to Y$ be the indicator function of $\mathrm{im}(\phi)$... this would have worked just as well. $\endgroup$ – Clive Newstead Mar 11 '16 at 22:26
  • $\begingroup$ (The alternative tactic in my second comment above is exactly what Zhen Lin did.) $\endgroup$ – Clive Newstead Mar 11 '16 at 22:28
1
$\begingroup$

To show that a surjective function is epic, just check the equality pointwise. If $X \overset{f}{\to} Y$ is your surjection, and $g_1, g_2 : Y \to Z$ are two functions you want to test with $f$, see that $$g_1 \circ f = g_2 \circ f \iff \forall x \in X, g_1(f(x)) = g_2(f(x)) \overset{\text{surj.}}{\implies} g_1 = g_2,$$ since surjectivity tells us that $g_1$ and $g_2$ now agree everywhere on $Y$.

To show that an epimorphism is a surjection, show the contrapositive. If $X \overset{f}{\to} Y$ is not a surjection, i.e. the image $\operatorname{im}(f)$ is a proper subset of $Y$, then choose a surjection $\pi : Y \twoheadrightarrow \operatorname{im}(f)$. Consider the map $Y \overset{\pi}{\twoheadrightarrow} \operatorname{im}(f) \hookrightarrow Y.$ This is clearly not the identity on $Y$. Yet, if you precompose $\operatorname{id}_Y$ with $f$, you get the same thing as precomposing $Y \overset{\pi}{\twoheadrightarrow} \operatorname{im}(f) \hookrightarrow Y$ with $f$. So $f$ fails to be right-cancellative, which is the contrapositive.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You need $\pi(y)=y$ for $y\in\mathrm{im}(f)$ for this to work. And $\pi$ does not exist if $X=\emptyset$, so you'll have to cover that case seperately. Easier to just define $g_1,g_2:Y\to\{0,1\}$ with $g_1(y)=0$ for all $y\in Y$ and $$g_2(y)=\begin{cases}0&y\in\mathrm{im}(f)\\1&\text{otherwise}\end{cases}$$ $\endgroup$ – Thomas Andrews Mar 10 '16 at 15:51
  • $\begingroup$ Ah, yes, $\pi$ has to extend the embedding of $\operatorname{im}(f)$. $\endgroup$ – mad_algebraist Mar 10 '16 at 15:54
  • $\begingroup$ How does surjectivity tell us that $g_1$ and $g_2$ agree everywhere on Y? Doesn't it only say that $\forall y \in Y\ \exists \ x \in X \ : y = f(x)$? $\endgroup$ – Mussé Redi Mar 10 '16 at 18:32
  • $\begingroup$ In combination with the assumption that $g_1 \circ f = g_2 \circ f$, it does (which is what we were trying to show). The logic is the same as Zhen's answer. $\endgroup$ – mad_algebraist Mar 10 '16 at 22:01
0
$\begingroup$

Suppose $f\colon A\to B$ is any map, with $A\ne\emptyset$. Consider the relation $\sim$ on $B$ defined by $x\sim y$ if and only if $x\in f(A)$ and $y\in f(A)$ or $x\notin f(A)$ and $y\notin f(A)$.

It is clear that $\sim$ is an equivalence relation on $B$, so we can consider the canonical projection $p\colon B\to B/{\sim}$ and also the map $q\colon B\to B/{\sim}$ defined by $q(b)=[f(a)]_{\sim}$, where $a\in A$ and, for $b\in B$, $[b]_{\sim}$ is the equivalence class of $b$.

It is clear that $p\circ f=q\circ f$. However, if $b\notin f(A)$, we clearly have $p\ne q$, because $p(b)=[b]_{\sim}\ne[f(a)]_{\sim}=q(b)$. Therefore $f$ is not epic.

If $A=\emptyset$, then $f$ epic implies that, for each set $C$, there exists a unique map $B\to C$. Therefore $B$ is an initial object and so $B=\emptyset$. Therefore $f$ is surjective.

The converse, that is “surjective implies epic”, is easy to prove.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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