12
$\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$
1
  • 1
    $\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$ Commented Mar 10, 2016 at 15:18

5 Answers 5

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

$\endgroup$
3
  • $\begingroup$ I find the choice of $g_1$ and $g_2$ a bit "magic". How would this follow naturally? $\endgroup$ Commented Mar 10, 2016 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$ Commented Mar 10, 2016 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$ Commented Mar 10, 2016 at 20:52
18
$\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.

$\endgroup$
4
  • $\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$ Commented Mar 10, 2016 at 20:32
  • $\begingroup$ It's the other way around. $\endgroup$ Commented Mar 10, 2016 at 20:34
  • 1
    $\begingroup$ Interesting - the use of impredicativity seems essential here! $\endgroup$ Commented Apr 14, 2019 at 13:59
  • $\begingroup$ This is an exceptional solution, and very conducive to formalization using a theorem verifier like Lean/Coq. $\endgroup$ Commented Jan 11, 2020 at 21:13
3
$\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.

$\endgroup$
5
  • $\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$ Commented Mar 10, 2016 at 16:52
  • $\begingroup$ How would you come about considering the union $B \cup \{ \star \}$? How would you find this naturally? $\endgroup$ Commented Mar 10, 2016 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$ Commented Mar 11, 2016 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$ Commented Mar 11, 2016 at 22:26
  • $\begingroup$ (The alternative tactic in my second comment above is exactly what Zhen Lin did.) $\endgroup$ Commented Mar 11, 2016 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.

$\endgroup$
4
  • $\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$ Commented Mar 10, 2016 at 15:51
  • $\begingroup$ Ah, yes, $\pi$ has to extend the embedding of $\operatorname{im}(f)$. $\endgroup$ Commented Mar 10, 2016 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$ Commented Mar 10, 2016 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$ Commented Mar 10, 2016 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .