Why does Finset not have a natural numbers object?

Question

Let $C$ be an elementary topos with final object $1$. A natural numbers object is an object $\mathbb{N}$ equipped with morphisms $q:1\longrightarrow \mathbb{N}$ and $s:\mathbb{N}\longrightarrow\mathbb{N}$ such that for any object $A$ and morphisms $z:A\longrightarrow A$ and $f:A\longrightarrow A$ there exists an unique morphism $\phi:\mathbb{N}\longrightarrow A$ such that the obvious diagram is commutative.

For proving that the category Finset doesn't have a NNO I was thinking to use an especific object $A=\{a_{0},...,a_{n}\}$ and morphisms $q:1\longrightarrow A$ such that $q(0):=a_{0}$ and $f:A\longrightarrow A$ such that $f(a_{i})=a_{i+1}$ for all $0\leq i\leq n-1$ and $f(a_{n})= a_{0}$. Then there exists the object $\mathbb{N}$ with $|\mathbb{N}|=m$ with the morphisms $s$ and $z$.

Then I was thinking that we will conclude that $\mathbb{N}\cong \mathbb{Z}_{n}$, because we will have $\phi(z(0)))=a_{0}$, $\phi(s(z(0)))=f(a_{0})=a_{1}$ and $\phi(s^{n}(z(0)))=a_{n}$, but from here I don't know how to get a contradiction.

Thank you very much.

Answer 1

Keep in mind that the morphism $\phi$ you get does not have to be injective. Suppose $\mathbb N$ is a natural numbers object in FinSet, and let $A_n:=\{a_0,\dots,a_n\}$ be the finite set you called $A$. Your choice of $q_n:1\to A_n$ and $f_n:A_n\to A_n$ give rise to a morphism $\phi_n:\mathbb N\to A_n$. So far this is just recapping what you had said.

Now, $\phi_n$ is a priori just some map of sets. It is not necessarily a bijection, so we can not conclude that $|\mathbb N|=|A_n|=n+1$ and similarly cannot conclude that $\mathbb N\cong\mathbb Z_{n+1}$ (note I have $(n+1)$'s where you wrote $n$ since we started indexing the $a_i$'s at $0$ instead of $1$). For example, if $n=1$, it is a priori possible that $\mathbb N=\{0,1,2,3\}$ with $\phi(n)=a_{(n\mod2)}\in A_2$.

So we do not get a contradiction from considering one $A_n$, but we will get one from considering all $A_n$'s. The point is that the $\phi_n$ you constructed is always surjectivie, so we do know that $|\mathbb N|\ge|A_n|=n+1$. In fact, we know this for all values of $n$. Thus, $\mathbb N$ cannot be a finite set, and this is the contradiction.

Answer 2

In a topos, $\mathbb{N} \simeq 1 \coprod \mathbb{N}$.

Now suppose we have a finite set $S$ with cardinality $n$. Then $1 \coprod S$ has cardinality $n + 1$, hence is not isomorphic to $S$.

Therefore, there is no natural numbers object in the category of finite sets.

Answer 3

Your solution basically works aside from the last paragraph. As Niven pointed out in their answer the trick to make this work is to consider a family of sets like the one you constructed and show that this forces the cardinality of the hypothetical natural numbers object to be infinite.

Alternatively, and this is the main reason I'm writing this answer, you could follow the route suggested by Mark Saving and prove that in general $\mathbb{N}\cong 1 \amalg \mathbb{N}\newcommand\NN{\mathbb{N}}$, which would immediately give a contradiction.

Proof:

Note on terminology. I'm going to call triples $(A,z:1\to A, s:A\to A)$ counting systems. I don't know that this is standard terminology, but I need a name for these things, and this is what I settled on.

Suppose $(\NN,z:1\to \NN, s:\NN\to\NN)$ is a natural numbers object. To show $\NN\cong 1\amalg \NN$, it suffices to show that $1\amalg \mathbb{N}$ is also a natural numbers object. We define $z' : 1\to 1\amalg \NN$ to be the inclusion $\iota_1$ in the coproduct. We define $s' : 1\amalg \NN\to 1\amalg \NN$ to be $\iota_\NN\circ z + \iota_\NN \circ s$.

Now if $(A,z_A, s_A)$ is another counting system, suppose $f'=f_0+f : 1\amalg \NN\to A$ is a map compatible with the counting systems, i.e., $f'\circ z' = z_A$, $f'\circ s' = s_A\circ f'$. The first equality says $f_0 = z_A$, so $f_0$ is uniquely determined by these equations, and the second equality says that $$f'(\iota_\NN z+\iota_\NN s) = fz + fs = s_A f' = s_Af_0 + s_Af.$$ This gives us that $fz=s_Af_0=s_Az_A$ and $fs=s_Af$. So $f$ is a map of counting systems from $(\NN,z,s)$ to $(A,s_Az_A,s_A)$, and is therefore unique.

Therefore $f'$, if it exists, is unique. On the other hand, we can also use these equations to construct $f_0$ and $f$ to produce a valid map $f'$.