How to categorically represent natural numbers and connection between them only if their difference is 1?

Question

How can one categorically represent natural numbers (as objects) with connection between each two of them only if their difference is 1? Obviously the above mentioned connection(relationship) can not be a morphism because it wouldn't compose (or maybe I'm wrong). So is there a way to represent it in category theory and if not, does that mean there are simple mathematical structures that can not be defined using category theory?

Answer 1

Let's go to a bit more general setting first: take $(P, \leq)$ a poset. That is , $P$ is a set with a (partial) order relation $\leq$. Then, we can associate $P$ a category (which I will also name $P$). We define $\operatorname{ob}(P) = P$. Then, $\operatorname{mor}(x,y)$ will have a unique arrow $x \to y$ iff $x \leq y$ and none otherwise.

In the case of $\mathbb{N}$, the objects are the natural numbers, and we have an arrow $n \to m$ iff $n \leq m$. Of course this gives more arrows than just $n \to n+1$ for each $n$. This is, in a way, inevitable: if you desire to have an arrow $n \to n+1$ and another one $n+1 \to n+2$, the category axioms force you to define a composition from $n$ to $n+2$ in some way. However, any arrow $n \to m$ can be written as a composition

$$ n \to n + 1 \to n+2 \to \cdots \to m-1 \to m, $$

so for most things it suffices to consider only these 'elementary' arrows.

For example, suppose I have abelian groups $G_1,G_2, \dots$ and functions $f_{i,i+1} : G_i \to G_{i+1}$. This is like assigning each natural $i$ a group $G_i$ and each arrow $i \to i+1$ a function $G_i \to G_{i+1}$. If we now define

$$ \begin{align} G : \mathbb{N}& \to \mathsf{Ab}\\ &n \mapsto G_n\\ &\downarrow \quad \downarrow{g_{n,m}}\\ &m \mapsto G_m \end{align} $$

with $g_{n,m} = g_{n,n+1}\circ g_{n+1,n+2} \circ \cdots \circ g_{m-1,m}$, this yields a functor.

Answer 2

The successor function $\mathsf{inc}:\mathbb{N}\rightarrow\mathbb{N}$ sends each number to the one after it $(n\mapsto n+1)$. It is a morphism which captures the relationship you describe.

And you can define $\mathsf{inc}$ in a categorical way:

• There is a functor $F:\mathbf{Set}\rightarrow \mathbf{Set}$ which appends a new element to each set: $X\mapsto X+1$. (On morphisms, it maps the new element of the domain onto the new element of the codomain.)

• As with any functor from a category to itself, you can form a new category consisting of all morphisms of the form $f:F(A)\rightarrow A$, where composition of morphisms makes the relevant square commute properly. This category is called an F-algebra.

• This particular F-algebra has an initial element. You can prove that the inital element is $[\mathsf{zero}, \mathsf{inc}]: 1+\mathbb{N} \rightarrow \mathbb{N}$. The function $\mathsf{zero}:1\rightarrow \mathbb{N}$ picks out the first element $0\in \mathbb{N}$. The function $\mathsf{inc}:\mathbb{N}\rightarrow \mathbb{N}$ maps each number onto its successor.

• And so we have a categorical definition of this relation. It neatly introduces the natural numbers, and zero, and the successor function, as universal constructs.