I'm working through Bird and DeMoor's Algebra of Programming and I have some basic gaps in my understanding. Problem 2.28 asks if projection outl is epic in Set, if inl is monic, and why the differing answers is not a violation of duality. The answer key says "Projections need not be epic: consider for instance $outl: 1 \leftarrow 0$ (note: they write morphisms in reverse order of most). Injections are monic. This does not contradict duality as it is about one particular category."

My first question is, is the answer right? How can $outl: 1 \leftarrow 0$ be a valid projection since the empty function does not seem to satisfy the definition of product using the universal condition: $h=< k, l > \iff outl \cdot h = k$ ?

Secondly, I've seen many explanations of what I think is the same issue here and elsewhere online -- the notion that a morphism is epic iff it is surjective. Most explanations offer as a unsatisfactory epimorphism $f: X \times \emptyset \to X$. I don't know if this is the empty function or if this is describing something that is satisfied by no function (looks to be the later) but either way I don't see how it could be a projection (for the same reason as the last paragraph). I did understand this answer, but I'd like to understand its the relation to the others.

Finally, I'm looking for a proof that inl is monic. I thought I had come up with one but its pretty basic and the same argument also proves outl is epic, so it must be wrong. I'd really like to know both what I've got wrong and how to make it right. My incorrect proof is:

To prove inl monic, prove $inl \cdot f = inl \cdot g \iff f = g$.

The right-to-left case is trivial -- $f=g \to inl \cdot f = inl \cdot g$

For the left-to-right case, recall the universal property of inl: $h=[k,l] \iff h \cdot inl = k$

Take $h=[id,l]$. Then $h \cdot inl = id$.

So: $$inl \cdot f = inl \cdot g$$ $$\to h \cdot inl \cdot f = h \cdot inl \cdot g$$ $$\to id \cdot f = id \cdot g$$ $$\to f = g$$

  • $\begingroup$ Could you explain what "inl" and "outl" are? $\endgroup$ – Captain Lama Dec 16 '19 at 4:29
  • $\begingroup$ I'm still learning what's Bird and DeMoor notation and what is more universal. outl and outr are the product projection functions, inl and inr are the coproduct injection functions. $\endgroup$ – Dave Dec 16 '19 at 4:56
  • $\begingroup$ What does 1<-0 mean? I am not familiar with that notation. As far as the empty function, be careful with the universal property: it is often the case that when that is a valid function, it satisfies the universal property vacuously (will there actually exist a function $h$?) $\endgroup$ – Arturo Magidin Dec 16 '19 at 4:59
  • $\begingroup$ They use 0 for the initial object (so, here, the empty set) and 1 for the terminal object (so, a singleton set). $\endgroup$ – Dave Dec 16 '19 at 5:04
  • $\begingroup$ But then what does “outl: 1<-0” mean? You said “outl” was one of the functions from the product. What product? The product of the empty set with a terminal object? The product is empty; if your $h$ is supposed to represent a function $l$ to the terminal object and a function $k$ to the initial one, then $k$ must be the empty function, meaning that $h$ is in fact the empty function itself. $\endgroup$ – Arturo Magidin Dec 16 '19 at 5:12

First: let $X$ be a nonempty set. I claim that the empty set, together with two empty functions, $\pi_1\colon \varnothing\to\varnothing$ and $\pi_2\colon\varnothing\to X$ give a product of $X$ and $\varnothing$ in the category of sets.

To verify this, we need to show that if $Y$ is any set, and $f\colon Y\to \varnothing$ and $g\colon Y\to X$ is a pair of functions, then there exists a unique function $F\colon Y\to\varnothing$ such that $f=\pi_1\circ F$ and $g=\pi_2\circ F$.

The reason this holds is by vacuity! For the pair of functions to exist, we must have that $Y$ is empty: for the only set with a function into $\varnothing$ is $\varnothing$. Thus, if the premise is met, then $Y=\varnothing$, $f$ and $g$ are both the empty function, and we can let $F\colon\varnothing\to\varnothing$ be the empty functions. All functions in sight are the empty function, and so they satisfy the required properties. Thus, $(\varnothing,\pi_1,\pi_2)$ is a product of $\varnothing$ and $X$.

Now, since $X$ is not empty, then $\pi_2$ is not onto, so $\pi_2$ is not epic in $\mathbf{Set}$. Explicitly, we can take a two element set $Z=\{a,b\}$, let $f,g\colon X\to Z$ be the maps that send everything to $a$ and everything to $b$, respectively; as $X\neq\varnothing$, $f\neq g$. However, as $\pi_2$ is the empty function, we have that $f\circ \pi_2=\varnothing=g\circ\pi_2$; thus, $\pi_2$ is not right-cancellable, and hence not an epimorphism.

Second: a proof that the inclusions into the coproduct are monics. Let $X$ and $Y$ be sets, let $X\amalg Y$ be their coproduct, and let $i_X$ and $i_Y$ be the corresponding inclusions. To prove that, for example, $i_X$ is monic, we must show that if $A$ is any set and $f,g\colon A\to X$ are functions such that $i_X\circ f = i_X\circ g$, then $f=g$.

If $X$ is empty, then $A$ is empty and $f$ and $g$ are both the empty functions and there is nothing to do. Otherwise, let $h\colon Y\to X$ be an arbitrary function. Then the maps $\mathrm{id}_X\colon X\to X$ and $h\colon Y\to X$ yield a unique function $F\colon X\amalg Y\to X$ such that $F\circ i_X=\mathrm{id}_X$ and $f\circ i_Y=h$. Then $$f = \mathrm{id}_X \circ f = F\circ i_X\circ f = F\circ i_X\circ g = \mathrm{id}_X\circ g = g.$$ Thus, $f=g$, so $i_X$ is monic.

  • $\begingroup$ Thanks! I can see the reasoning now. LSS, the critical observation was "a function with empty domain may have non-empty codomain but a function with empty codomain must have empty domain". Your injection proof is the same as mine -- you just use $i_X$ == inl, $F == h$ and $h == l$, but you helpfully explain the "X is empty" case as 'empty codomain -> empty function'. From there, I can see that the same proof doesn't apply for projections (you use $\pi_1 == outl$) because $\pi_1$ has empty domain but that doesn't imply empty codomain, so $f \cdot \pi_1$ doesn't mean f is empty. $\endgroup$ – Dave Dec 16 '19 at 6:36
  • $\begingroup$ @Dave: In other words, in the category of sets, monomorphisms are none other than injections and epimorphisms none other than surjections. In the case of a direct product of the type $A \times \varnothing=\varnothing$ the projection to the factor $\varnothing$ will be surjective hence epic, but the one to the factor $A$ no longer is surjective in general, for $A \neq \varnothing$. $\endgroup$ – ΑΘΩ Dec 16 '19 at 6:55
  • $\begingroup$ @Dave: The other issue is that while the empty function is injective/monic, it is not surjective/epic unless the codomain is also empty. That’s why the embeddings into the coproduct are always monic (always being injective, even in the degenerate case of an empty cofactor) but the projections are not always epic (because they may not be surjective in the degenerate case of an empty factor). $\endgroup$ – Arturo Magidin Dec 16 '19 at 7:15

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.