Does this kind of endofunctor ever have an initial algebra?

Question

Let $C$ be a topos with subobject classifier $\Omega$. Let $F$ be the endofunctor $x \mapsto \Omega^{\Omega^x}$ on $C$. Does there exist $C$ such that $F$ has an initial algebra? What if $\Omega$ is replaced with the coproduct $2 = 1 \sqcup 1$ of two copies of the terminal object? (What if it is replaced with any object that is not the terminal object?)

The motivation for this question is a somewhat long story, but if someone wants I can edit it in.

Note that if $C = \text{Set}$ then this is impossible by Cantor's theorem (and Lambek's theorem). I'm worried that the Lawvere fixed point theorem can shoot down this question as well.

Answer 1

By Lambek's theorem, any initial algebra for an endofunctor $F$ has the property that its structural morphism $\alpha : F A \to A$ is an isomorphism. So we seek an object $A$ such that $P P A = \Omega^{\Omega^A} \cong A$.

However:

Proposition. If a topos $\mathcal{E}$ contains an object $A$ such that $P A$ is a subquotient of $A$, then $\mathcal{E}$ is a degenerate topos (i.e. $0 \cong 1$).

Proof. This is Proposition D4.1.8 in [Johnstone, Sketches of an elephant]. 　◻

So, suppose that $A \cong P P A$. Clearly, $A$ is a subobject of $P A$ via the singleton operator $\lbrace \cdot \rbrace_A : A \to P A$, so this isomorphism exhibits $P P A$ as a subquotient of $P A$, which by the proposition implies our topos is degenerate.

That said, $\Omega$ is a bit special. The general form of Cantor's theorem for function-sets is known to fail in toposes; for example, in the effective topos, if $N$ is the natural numbers object, then $N^N$ is a subquotient of $N$. There are also cartesian closed categories (hence toposes via Yoneda) containing an object $A$ such that $A \cong A^A$ (and hence $A \cong A^{A^A}$).

Answer 2

I don't know any examples with $\Omega$, but $x\mapsto 2^{2^x}$ has an initial algebra in the effective topos. The object $2^{2^x}$ is a quotient of a subobject of the natural number object for any object $x$. The category of quotients of subobjects of the natural number object is `weakly complete' (see Hyland 1988 'A small complete category'). This is complete enough to get an initial algebra in this subcategory, and I am pretty sure that it is initial in the category of all algebras in the effective topos. My paper (Stekelenburg 2010 'A note on extensional PERs') has a description of these algebras.

Answer 3

This is a supplement to the answers of Lin and Stekelenberg. It describes an observation I made in conversation with Andrej Bauer and Martín Escardó in 2007, which may well be known to others.

In addition to realizability toposes, there are Grothendieck toposes in which the functor $2^{2^{(-)}}$ has an initial algebra. A nice example is given by Johnstone's topological topos, where the carrier object of the initial algebra is the natural numbers object $N$.

This works as follows. The objects $N$, $2^N$ and $2^{2^N}$ all reside in the subcategory of the topological topos corresponding to sequential topological spaces. $N$ is the natural numbers with discrete topology. $2^N$ is a countable power of $2$, which has the product topology; i.e., it is Cantor space. $2^{2^N}$ is the set of clopen sets in Cantor space, with discrete topology. Via Stone duality, the clopen sets of Cantor space form the free boolean algebra on countably many generators, and there are thus countably many of them. Thus $2^{2^N}$ is isomorphic to $N$.

To describe the initial algebra consider any bijection: $$\phi: N \to 2^{2^N}$$ satisfying the property that the modulus of uniform continuity of $\phi(n)$ is always $\leq n$. (Here the modulus of uniform continuity of a continuous $C: 2^N \to N$ is the smallest $m$ such that $C(\alpha)$ is always determined by the values of $\alpha$ on $\{0, \dots, m-1\}$.) Such a $\phi$ is easy to construct. The inverse $$\phi^{-1}: 2^{2^N} \to N$$ then provides an initial algebra.

To verify initiality, given an algebra $f: 2^{2^X} \to X$ one needs to construct the unique homomorphism $h: N \to X$. The homomorphism property gives the following recursive equation for $h$ $$h(n) = f(\lambda p. \phi(n)(\lambda m. p(h(m))))$$ which is then well-defined and uniquely determined by induction on $n$, using the assumed property of $\phi$. (I am treating the sheaf $X$ as a set, which is fine since the formula defines $h$ in the internal logic of the topos.)

Three further remarks: Identical reasoning shows that the natural numbers carry the initial algebra for $2^{2^{(-)}}$ in the usual cartesian closed categories of topological spaces. Also, a purely category-theoretic argument shows that when $\phi$ is an initial algebra then $2^\phi$ is a final coalgebra, hence Cantor space carries the final coalgebra. (This can also be proved directly, using an argument similar to that above for the initiality of $\phi$.) Finally, a natural level of generality for the argument above is: in any elementary topos with natural numbers object in which the "fan theorem" holds, the definition of $\phi^{-1}: 2^{2^N} \to N$ above is an initial algebra for $2^{2^{(-)}}$.

Answer 4

The above answers are great, but I would like to stress on one fundamental aspect here.

Contrary to some common beliefs, Cantor's diagonal argument is purely constructive and as such carries to the internal logic of elementary topos (notice, however, that it relies on impredicativity of the topos). For let us assume, there is an injection $j \colon \Omega^A \rightarrow A$. We may form a paradoxical subset of $\Omega^A$: $$P = \{x \in A \colon \forall_{y \in \Omega^A} x \in y \rightarrow x \not= j(y) \}$$ Let us consider: $$p = j(P)$$ If $p \in P$ then according to the definition of $P$: $$p \in y \rightarrow p \not= j(y) \;\;\;\;\;\;\(F\)$$ for all $y \in \Omega^A$, so particularly for $y = P$, we have: $$p \in P \rightarrow p \not= j(P)$$ and by using (again) the assumption $p \in P$, we can derive $p \not= J(P)$, which by the definition of $p$ produces $\bot$. Therefore we constructed a method of turning a statement $p \in P$ into absurd, that is $p \in P \rightarrow \bot$.

On the other hand, we may show that the formula (F) holds for every $y$. By the definition of $p$, it is equivalent to: $$p \in y \rightarrow j(P) \not= j(y)$$ and by the definition of the implication, to: $$j(P) = j(y) \overset{\psi \circ \phi}\rightarrow (p \in y \rightarrow \bot)$$ Now, we may use our extra assumption saying that $j$ is injective: $$j(P) = j(y) \overset{\phi}\rightarrow P = y$$ and cut it with: $$P = y \overset{\psi}\rightarrow (p \in y \rightarrow \bot)$$ which is equivalent to: $$P = y \wedge p \in y \rightarrow \bot$$ and holds because $p \in P \rightarrow \bot$ as has been shown in the first part of the proof. Therefore, (F) holds as the composition of proofs $\psi$ with the fact $\phi$ saying that $j$ is injective. Finally, by comprehension, $p \in P$. So: $$(p \in P) \wedge (p \in P \rightarrow \bot)$$ thus: $$\bot$$

---

This means that there can be no injection $\Omega^A \rightarrow A$ for any $A$. This also means that there can be no injection $\Omega^{\Omega^A} \rightarrow A$ (because we have an obvious injection $A \rightarrow \Omega^A$ and composition of injections is an injection). Therefore, there are no isomorphisms $\Omega^{\Omega^A} \approx A$ and by Lambek's theorem, there are no initial (nor final) (co)algebras for $\Omega^{\Omega^{\(-\)}}$.

More generally, by a similar argument, one may show that if there exists an injection $\Omega \rightarrow X$ then there could be no initial algebra for $X^{X^{(-)}}$.

Answer 5

I am surprised that you are asking about algebras for this functor, rather than for the monad of which it is naturally a part.

Classically. the algebras are complete atomic Boolean algebras (Lindenbaum and Tarski, 1930s).

In a topos, they are full powersets and indeed the category of algebras is equivalent to the opposite of the topos. This was proved by Bob Paré in 1973. It was an inportant part of the development of elementary toposes at the time because it meant that colimits could be deleted as a requirement (in fact Christian Mikkelsen had done this a bit earlier.)

Another example of such a dual equivalence arising from double exponentiation of an object $\Sigma$ is the category of locally compact locales (or spaces, with Choice.)

There is also an abstract construction that takes a category that has products and powers of a particular object and yields a category with this monadic property.

My programme called Abstract Stone Duality bulds on these ideas to develop a computable theory of general topology.