5
$\begingroup$

Let C be a category satisfying the following axioms:

  1. C contains an initial element, designated $0$;
  2. C contains a terminal element, designated $1$;
  3. $0$ and $1$ are not isomorphic;
  4. $1$ is a separator in C; i.e. $((f_0, f_1:X \rightarrow Y) \wedge (\forall x:1\rightarrow X \; [f_0 \circ x = f_1 \circ x])) \Rightarrow (f_0 = f_1)$;
  5. for any objects $A_0$, $A_1$ in C, their co-product $A_0 \oplus A_1$ is an object of C.

I'm looking for a proof of (or counterexample for) the following assertion:

All the canonical insertions of any binary co-product in C are monic.

Thanks!

PS: This question is derived from an exercise (2.12, p. 33) in Lawvere and Rosebrugh's Sets for Mathematics (2003). The original wording of the exercise is:

Prove on the basis of the axioms for $\cal{S}$ [i.e. Set] so far introduced that if $i_0:A_0 \rightarrow A, i_1:A_1 \rightarrow A$ is a sum in $\cal{S}$, then $i_0$ is a monomapping.

The five axioms I listed are those "so far introduced", as I understand them (except for the first one, which simply states that $\cal{S}$ is a category), and the definition given for "sums" is exactly the definition for co-products. The reason for leaving open the possibility that the assertion is false is that I may have misunderstood some aspect of the question, or of the axioms. In this case, a counterexample would help me see where I'm going wrong.

  • 0
    What are your thoughts on this question? And by the way: what is an ISO proof?2011-07-26
  • 0
    @Theo: ISO="in search of" (fixed title to make it clearer); I think the assertion is true, but I have no idea of how one proves it; I've worked on it for a few hours, and have not gotten any traction at all.2011-07-26
  • 0
    @kjo: Does it help if I tell you the claim is false?2011-07-26
  • 2
    @Zhen Lin: I'm not playing a riddles game here. I'm working very hard to teach myself CT, from books in my spare time. No class, no teacher, no time. It's hard enough as it is. If you don't want to help me, that's fine, but please don't treat me like a child.2011-07-26
  • 0
    @kjo: That was merely a hint to look for a counterexample. I don't know what your background is, so I can't judge whether you would be well-placed to find one or not. If you're not I can give details. All I know is that you are reading _Sets for Mathematics_ —that was also *my* first introduction to category theory, because I didn't have enough background to appreciate the textbooks aimed at students with more mathematical background. But for all I know you've completed several abstract algebra classes and have for some reason decided to pick up this book rather than, say, Mac Lane's classic.2011-07-26
  • 0
    [...] For what it's worth, it's been two and half years or so since I picked up _Sets for Mathematics_ and it's only now—after finishing a full 3 years of undergraduate mathematics—that I feel well-placed to begin really understanding category theory. Many interesting examples simply aren't available if you don't know enough algebra or topology or geometry.2011-07-26
  • 2
    Let $\iota_A \colon A \sqcup B$ be a coproduct injection. We have to show that for every distinct $f \neq g \colon X \rightarrow A$ the condition $\iota_A \circ f \neq \iota_B \circ g$ is satisfied. Let us assume $f \neq g$. $1$ is a generator, so if $f \neq g$ then there exists $x \colon 1 \rightarrow A$. Thus we have morphisms $id_A \colon A \rightarrow A$ and $f \circ x \circ ! \colon B \rightarrow A$, where $!$ is the unique morphism to the reminal object...2011-07-26
  • 2
    ...By universality of the coproduct, there is a morphism $h \colon A \sqcup B \rightarrow A$ such that $h \circ \iota_A = id_A$. Thus, $\iota_A$ is split mono, so mono.2011-07-26
  • 0
    @Mockup: Nice! I was having trouble seeing how to get an arrow $B \to A$ and I was thinking about splitting it between the case that there is some arrow $1 \to A$ and the case that there aren't but then I got stuck there.2011-07-26
  • 0
    @Zhen Lin: sorry for my testy reply. Too many times I have received responses that accuse me of trying to get a solution to some school homework problem on the cheap, or insinuated as much. When one is 52, long out of school, and studying independently in the little spare time one has, such responses get particularly irritating. Also, thanks for the counterexample you posted. Even though, as Theo Buehler noted, it did not fully satisfy all the axioms I posted, thinking about the way in which it failed to do so led me to a lot of illuminating results. I wish now I had copied it down!2011-07-30

3 Answers 3

4

I must say I do not understand Beroal's completion/simplification of the comment. Let me allow to restate the argument.

Let $\iota_A \colon A \rightarrow A \sqcup B$ be a coproduct injection.


Observation: If we had any morphism $r \colon B \rightarrow A$, then we could apply the universal property of the coproduct to the morphisms $id_A \colon A \rightarrow A$ and $r \colon B \rightarrow A$ to obtain a morphism $h \colon A \sqcup B \rightarrow A$ that commutes with the identity $id_A$, and thus makes the injection $\iota_A$ a split monomorphism.


We have to show that for every pair of distinct morphisms $f \neq g \colon X \rightarrow A$ they precomposition with $\iota_A$ gives different morphisms --- that is: $\iota_A \circ f \neq \iota_A \circ g$. So, let us take such $f$ and $g$. Because the terminal object $1$ is a separator of the category and $f \neq g$, there exists $x \colon 1 \rightarrow A$. Therefore we have a morphism $r = f \circ x \circ ! \colon B \rightarrow A$, where $!$ is the unique morphism to the terminal object, what by the above observation completes the proof.


Zhen, my comment to your former answer about extensive categories, was just like a shoot to a fly with a cannon. Here is a simpler and more accurate argument, which consists of three relatively easy to prove facts:

  • it suffices for a category to be distributive to have monic coproduct injections
  • every cartesian closed category with coproducts is distributive
  • every topos is cartesian closed and has coproducts
  • 0
    $h$ does not commute with the identity $id_A$ because $h\circ id_A$ is not allowed.2011-10-27
1

This is Mockup's proof, completed/simplified.

Definition. An object $A$ is inhabited if there exists an element of $A$.

Lemma 0. For every inhabited $A$ and every object $B$ there exists a constant morphism of type $B\to A$. Proof. It is $e\circ u$, where $e$ is that element of $A$, $u:B\to 1$. Qed.

Lemma 1. Suppose that an object $A$ is not inhabited. Every morphism $f$ from $A$ is a monomorphism. Proof. Suppose $e_0, e_1$ are elements of $A$. This contradicts that $A$ is not inhabited, then $e_0=e_1$. Then $f$ is an injective morphism. Then by Exercise 2.7 $f$ is a monomorphism. Qed.

Your question. Proof. Using the axiom of excluding middle, $A$ is inhabited or $A$ is not inhabited. If $A$ is not inhabited, then $\iota_0:A\to A+B$ is a monomorphism by Lemma 1. Suppose $A$ is inhabited, then there exists $c:B\to A$ by Lemma 0. $[id(A),c]\circ\iota_0 = id(A)$ by algebraic properties of the coproduct, then $\iota_0$ is a split monomorphism, then it is a monomorphism. Qed.

Square brackets denote sum of morphisms. Sum of morphisms is extracted from universal property of a coproduct, as well as the algebraic properties which I referred to. Moreover, a coproduct may be defined algebraically. Unfortunately, this seems to be omitted in your textbook.

1

I hope it's OK to post yet another proof.


Let $i_0:A_0 \rightarrow A, i_1:A_1 \rightarrow A$ be a sum in $\cal{S}$. To prove that $i_0$ is monic, the following simple lemma is useful. It follows directly from the definition of separator in the trivial case where there are no morphisms from the separator to some other object:

Lemma: Let $G$ be a separator in some category $\cal{C}$, and suppose for some object $X$ in $\cal{C}$ there are no morphisms $G \to X$. Then, for any object $Y\;$ in $\cal{C}$ there can be at most one morphism $X \to Y.\;\;$

Now, to prove that $i_0$ is monic, we consider two cases.

Case $0$: there are no morphisms $1 \to A_0$. In this case, if $\; \exists f:X \to A_0$, then there can be no morphisms $1 \to X$ either (otherwise, a morphism $1 \to A_0$ could be constructed by composing a morphism $1 \to X$ with $f\;$). Since $1$ is a separator in $\cal{S}$, by the lemma above, $f\;$ is the only morphism $X \to A$. Therefore, $i_0$ is (vacuously) monic.

Case $1$: there is a morphism $a:1\to A_0$. Then we also have the morphism $a \; \circ \; !_{A_1}:A_1 \to A_0$ (where $!_{A_1}$ is the unique morphism $A_1 \to 1$), which, together with $1_{A_0}:A_0 \to A_0$, entails the existence of a unique morphism $u:A_0 \oplus A_1 \to A_0$ with $u \circ i_0 = 1_{A_0}$ and $u \circ i_1 = {a} \; \circ \; !_{A_1}$. This means that $u$ is a left inverse of $i_0$, which implies that $i_0$ is left-cancellable, or, equivalently, that $i_0$ is monic. $_\blacksquare$


While thinking about this problem, I realized that a very simple category (which Goldblatt calls $\mathbf{2}$), consisting of two objects, an initial $0$ and a terminal $1$, and three mandatory morphisms (the two identities, and $0 \to 1$) satisfies all the five axioms in the original problem statement (although vacuously so for axiom 4 and "most" of axiom 5). This explains to me why my intuitions based on my prior knowledge of standard set theory led me astray so often: there's a lot more to $\cal{S}$ than those axioms allow for.

This also relates to what I see as the only merit in my proof (and the reason I decided to post it even though other fine proofs had already been posted), namely that it reflects the bipartite structure that the five axioms impose on the category (and epitomized by the category $\mathbf{2}$ described above), in which objects are partitioned into two non-empty equivalence classes according to whether they are codomains to some morphism with domain $1$ or not.


Thanks to all who responded. This was an unexpectedly instructive exercise.

  • 1
    This looks good. Just a very small typo: at the very end of case 1 you want to say that $i_0$ is monic, not $1_{A_0}$.2011-07-30
  • 0
    Thanks for looking over the proof. Typo fixed!2011-07-30