Skip to main content
1 of 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 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 the 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) \;\;\;\;\;\;(*)$$ for all $y \in \Omega^A$, so particularly for $y = P$, we can derive contradiction $\bot$. Therefore, $p \in P \rightarrow \bot$.

On the other hand formula $(*)$ holds for every $y$ --- substituting $p$ by $j(P)$ we have to show: $$p \in y \rightarrow j(P) \not= j(y)$$ or equivalently: $$p \in y \wedge j(P) = j(y) \rightarrow \bot$$ since $j$ is injective we have $j(P) = j(y) \rightarrow P = y$ and by composing it with the proof of $p \in P \rightarrow \bot$ we get the above formula.


This means that there are 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$ --- there is an obvious injection $A \rightarrow \Omega^A$ and composing injections gives injection. Thus, 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^{(-)}}$.