Does there exist an endofunctor of the category of countable sets that lacks an initial algebra?

Question

There exist endofunctors of $\mathbf{Set}$ that are deficient inasmuch as they lack an initial algebra. The canonical example is the covariant powerset functor (the initial algebra of $\mathcal{P}$, if it existed, would include the whole cumulative hierarchy).

Now let $\mathbf{Set}_{< \aleph_1}$ denote the category of countable sets. I'm curious to know if there exist endofunctors of $\mathbf{Set}_{< \aleph_1}$ that also lack an initial algebra. Since we can't take powersets while remaining in the countable realm, it will be interesting to see if anyone can find an example of such a thing.

Answer 1

Every endofunctor on $\mathbf{Set}_{< \aleph_1}$ has an initial algebra. To prove this, here's the key set-theoretical lemma:

Lemma: Let $T$ be an endofunctor on $\mathbf{Set}_{< \aleph_1}$ and let $A_0\subset A_1\subset A_2\subset\dots$ be a sequence of countably infinite sets with union $A$, such that $A_{n+1}\setminus A_n$ is infinite for each $n$. Then the natural map $\operatorname{colim}T(A_n)\to T(A)$ is surjective.

Proof: Suppose $\operatorname{colim}T(A_n)\to T(A)$ is not surjective. That is, there is some element of $T(A)$ that is not in the image of $T(A_n)\to T(A)$ for any $n$. For each $r\in\mathbb{R}$, let $C(r)=\{q\in\mathbb{Q}:q<r\}$, and pick an increasing sequence of rational numbers $(q_n)$ with limit $r$. We can then find a bijection $f:A\to C(r)$ such that $f(A_n)=C(q_n)$ for each $n$ (here we use the assumption that $A_{n+1}\setminus A_n$ is infinite for each $n$). So, there is some element $x_r\in T(C(r))$ which is not in the image of $T(C(q_n))$ for any $n$. It follows that $x_r$ is not in the image of $T(C(s))$ for any $s<r$.

Now let $y_r$ be the image of $x_r$ in $T(\mathbb{Q})$. By construction, $y_r$ is in the image of $T(C(r))\to T(\mathbb{Q})$ but is not in the image of $T(C(s))\to T(\mathbb{Q})$ for any $s<r$. Thus the elements $y_r\in T(\mathbb{Q})$ are all distinct. This is a contradiction, since $T(\mathbb{Q})$ must be countable.

From this lemma, we can deduce the following remarkable fact:

Theorem: Every endofunctor on $\mathbf{Set}_{< \aleph_1}$ preserves sequential colimits.

Proof: Let $T$ be an endofunctor on $\mathbf{Set}_{< \aleph_1}$. We first prove that $A_0\to A_1\to A_2\to\dots$ be a sequential diagram in $\mathbf{Set}_{< \aleph_1}$ with colimit $A$, then the natural map $\operatorname{colim} T(A_n)\to T(A)$ is surjective.

Note first that every surjection in $\mathbf{Set}_{< \aleph_1}$ splits and so $T$ preserves surjections. If the map $A_n\to A$ is surjective for some $n$, the conclusion is thus trivial. So we assume $A_n\to A$ is not surjective for any $n$. In particular, this means $A_n$ is nonempty for sufficiently large $n$, so we may assume $A_n$ is always nonempty. Passing to a subsequence, we may also assume that for each $n$, the image of $A_n$ in $A$ is strictly contained in the image of $A_{n+1}$ in $A$.

Now let $B=A\times\mathbb{N}$ and $B_n=A_n\times\mathbb{N}$. Note that our diagram $(A_n)$ is then a retract of the diagram $(B_n)$, and so the map $\operatorname{colim} T(A_n)\to T(A)$ is a retract of the map $\operatorname{colim} T(B_n)\to T(B)$. Since a retract of a surjection is surjective, it suffices to show $\operatorname{colim} T(B_n)\to T(B)$ is a surjection.

Now let $C_n$ be the image of $B_n$ in $B$. By our previous reductions, we know that each $C_n$ is infinite and that $C_{n+1}\setminus C_n$ is infinite for each $n$. By the Lemma, we conclude that the natural map $\operatorname{colim} T(C_n)\to T(B)$ is surjective. But we have surjections $B_n\to C_n$ compatible with the maps to $B$ for each $n$, and thus surjections $T(B_n)\to T(C_n)$ compatible with the maps to $T(B)$. It follows that $\operatorname{colim} T(B_n)\to T(B)$ is also surjective and thus so is $\operatorname{colim} T(A_n)\to T(A)$.

Note in particular that writing any countable set as a sequential colimit of finite subsets, we see that for any $A$ and any $x\in T(A)$, there is some finite $F\subseteq A$ such that $x$ is in the image of $T(F)\to T(A)$. We now use this to prove that for any sequential diagram $A_0\to A_1\to A_2\to\dots$ with colimit $A$, the natural map $\operatorname{colim} T(A_n)\to T(A)$ is also injective (and thus bijective, so $T$ preserves the colimit).

If $A$ is empty then so is every $A_n$ and the conclusion is trivial, so we assume $A$ is nonempty and then may also assume each $A_n$ is nonempty (if not just drop the finitely many empty terms from the sequence). Now suppose $x,y\in \operatorname{colim} T(A_n)$ have the same image in $T(A)$. There is $n$ such that $x$ and $y$ both lift to $T(A_n)$, and then a finite nonempty subset $F\subseteq A_n$ such that $x$ and $y$ both lift to $T(F)$. Since $F$ is finite, its image in $A_m$ for $m\geq n$ eventually stabilizes. That is, we can choose $m\geq n$ such that the natural map $F'\to A$ is injective, where $F'$ is the image of $F$ in $A_m$. Since $F'$ is nonempty, this injection splits, and so $T(F')\to T(A)$ is injective too. Since $x$ and $y$ have the same image in $T(A)$, their lifts to $T(F')$ must thus be equal. That means their lifts to $T(A_m)$ are equal, so $x$ and $y$ are equal in $\operatorname{colim} T(A_n)$.

It then follows that any endofunctor on $\mathbf{Set}_{< \aleph_1}$ has an initial algebra by Adámek's theorem. Explicitly, we define $A_n=T^n(\emptyset)$ for each $n\in\mathbb{N}$. There are canonical maps $A_n\to A_{n+1}$ given by applying $T^n$ to the unique map $\emptyset\to T(\emptyset)$. Letting $A=\operatorname{colim} A_n$, we also have $A\cong\operatorname{colim} T(A_n)$ since $T(A_n)=A_{n+1}$ and this is compatible with the maps in the system. Since $T$ preserves sequential colimits, the canonical map $A\cong\operatorname{colim} T(A_n)\to T(A)$ is an isomorphism, and its inverse gives a $T$-algebra structure $T(A)\to A$ on $A$, which can be shown to be initial.