# Question about equivalence relation defining integers in an elementary topos

Hi all,

Let $\mathcal{E}$ be an elementary topos with natural number object $N$, and let $+: N \times N \to N$ be the the addition arrow; I expect that the nature of $N$ and $+$ will turn out to be irrelevant to my question, but if so they should at least make its motivation clear. Let $E$ be the pullback of $+$ along itself, with projections $p, q: E \to N \times N$; for example if $\mathcal{E}$ is the topos of sets then $E$ may simply be taken to be the set of quadruples $(n, m, n', m') \in N^4$ such that $n + m' = n' + m$, with $a(n, m, n', m') = (n, m')$, $b(n, m, n', m') = (n', m)$. Let $f_1, f_2: E \to N \times N$ be given by

$f_1 \equiv \left< p_1 a, p_2 b \right>$

$f_2 \equiv \left< p_1 b, p_2 a \right>$

(here $p_1, p_2: N \times N \to N$ are the projections and $\left< f, g \right>$ denotes the product arrow $X \to N \times N$ of arrows $f, g: X \to N$). For example in the topos of sets again, $f_1 (n, m, n', m') = (n, m)$ etc.. Let $c: N \times N \to Z$ be the coequaliser of $f_1$ and $f_2$, so $Z$ is the integer object in $\mathcal{E}$.

My question is: if $g, h, g', h': X \to N$ are such that $c \left< g, h \right> = c \left< g', h' \right>$, is it always the case that $+ \left< g, h' \right> = + \left< g', h \right>$? Equivalently, is $E$ with the arrows $f_1$, $f_2$ the pullback of $c$ along itself?

I've spent a while trying to prove it is but I just keep going round in circles, so any hints will be much appreciated.

-

I think what you want first is a lemma that $\mathbb{N}$ is a cancellative monoid (which is the case in any topos). Just think about how you would prove your statement in the category of sets using ordinary elements, and I think it will become clear.

The usual construction of the left adjoint to the forgetful functor from abelian groups to abelian monoids involves the observation that, for $m, n, m', n'$ in an abelian monoid $M$, the relation

$$\exists_{j \in M} m' + n + j = m + n' + j$$

defines an equivalence relation $\langle m, n \rangle \sim \langle m', n' \rangle$ on $M \times M$. (Only transitivity need be checked.) Cancellation means that from this we can infer

$$m' + n = m + n'$$

which is what you want.

We thus need to show

$$\forall_{j \in \mathbb{N}} ((x + j = y + j) \Rightarrow (x = y))$$

in the natural numbers object. This is done by induction on $j$ (the subobject of such $j$ contains 0 and ... and therefore is all of $\mathbb{N}$).

-
Thanks for your reply and apologies if I'm missing something, but I don't see how that helps with my question. I need to show that $f_1, f_2$ is the kernel pair of some arrow. Does the fact that $\left< f_1, f_2 \right>$ is an equivalence relation imply that it's also a kernel pair in an arbitrary (not necessarily Grothendieck) topos? Mac Lane and Moerdijk mention that the implication (equivalence relation \Rightarrow kernel pair) does not hold in an arbitrary category. – Phil Wild Oct 2 '10 at 0:34
Phil: yes. This is a famous exactness property of toposes: that every equivalence relation is the kernel pair of the coequalizer (of the two projection maps restricted to the equivalence relation). One says that in a topos, "equivalence relations are effective". I wasn't able to find this fact for general toposes in Mac Lane-Moerdijk, but see for example Categories, Allegories by Freyd and Scedrov, 1.951 (page 173). – Todd Trimble Oct 2 '10 at 1:14
OK, thanks. Is the fact you mention easy to prove, and if so, can you give me a hint? (I don't have access to a university library so checking the reference you give won't be so easy.) One of the reasons for my original question was that Mac Lane and Moerdijk state without proof that the natural map $c \left< 1_N, 0! \right>: N \to Z$ is monic, which would follow easily from the positive answer. Do you know if there's another way to see that it's monic? – Phil Wild Oct 2 '10 at 2:35
If you want that an equivalence relation is the kernel pair of some arrow, take the arrow to be the classifying map $X \to PX$ of the relation $R$ as subobject of $X \times X$. (You can also take the arrow to be the coequalizer, but it's more work.) A detailed proof is in Johnstone's Sketches of an Elephant (p. 97); try googling that +djvu and you should find what you need. It's not very hard. – Todd Trimble Oct 2 '10 at 4:05
Excellent, thanks. – Phil Wild Oct 2 '10 at 5:31