Cantor's theorem for posets

In his nice paper on Lawvere’s fixed-point theorem and self-referentiality, Noson Yanofsky wonders whether it might be possible to see the assertion of the Knaster-Tarski fixed-point theorem (every monotone map $X \to X$ on a sup-lattice has a fixed point) as a corollary of Lawvere’s fixed-point theorem.

One crazy idea is to attempt to show that in the cartesian closed category of posets, there is for each sup-lattice $X$ a fixed point $Y$ of $X^-$, i.e., a poset $Y$ such that $X^Y \cong Y$. (To make this more structural, you could for example construe $X^-$ as a covariant functor on $Pos$, by considering left Kan extensions for example, and then ask whether such an endofunctor $X^-: Pos \to Pos$ has an initial algebra.) If that were true, then it would immediately follow from Lawvere’s fixed-point theorem that every map $X \to X$ has a fixed point.

One *raison d’être* for this modest little note is to show this idea can’t possibly work, by showing for example that this is hopeless even for the case $X = 2$ (the poset $\{0 \leq 1\}$).

In other words, the purpose of this note is to prove Cantor’s theorem for the cartesian closed category of posets. More precisely, we will prove the following stronger result, internally valid in any topos (with $2$ replaced by $\Omega$):

There can be no surjective poset map $f: Y \to 2^Y$. Similarly, there can be no surjective poset map $Y \to 2^{Y^{op}}$.

This theorem is not entirely obvious, at least not to me. As indicated above, a surjection $Y \to X^Y$ is not ruled out by Lawvere’s fixed-point theorem via the implication that every endomap $X \to X$ has a fixed point: that conclusion is true if $X$ is a sup-lattice. And it’s certainly not something one can deduce on crude cardinality grounds, since for example the case $Y = \omega$, the first infinite ordinal, yields $2^Y \cong \bot \sqcup \omega^{op}$ (freely adjoin a bottom element to $\omega^{op}$), with the same cardinality as $Y$.

There are various ways of proving this. One method which involves a transfinite construction may be found here. As a ZFC proof in classical logic, this is fine, but here we are after something manifestly valid in any topos, and we are also after something that has more the character of a diagonalization argument.

We note that the poset $2^Y$ can be identified with the poset of upward-closed subsets of $Y$, ordered by inclusion.

The following notion, which we may think of as a strong notion of surjectivity, will be useful.

A map $\phi: A \to B$ between posets is a *reflector* if it has a right adjoint $s: B \to A$ whose counit is an equality $\phi \circ s = 1_B$ (the right adjoint of a reflector will be called simply the *adjoint* of $\phi$).

For any poset map $f: X \to Y$, we define $\exists_f: 2^X \to 2^Y$ to be the left adjoint of $2^f: 2^Y \to 2^X$. The map $\exists_f$ takes an upward-closed $A \subseteq X$ to the smallest upward-closed set containing $f(A)$, in other words $\bigcup_{a \in A} f(a)^\uparrow$ where $x^\uparrow \coloneqq \{y: x \leq y\}$ is the upward set generated by $x$ (aka the principal filter generated by $x$, also denoted $prin(x)$).

If $f: X \to Y$ is a surjective poset map, then $\exists_f: 2^X \to 2^Y$ is a reflector. (As $f^{op}$ is also surjective, $\exists_{f^{op}}: 2^{X^{op}} \to 2^{Y^{op}}$ is also a reflector with adjoint $2^{f^{op}}$.)

The adjunction $\exists_f \dashv 2^f$ is well-known and elementary, and obtains for any poset map $f$ (not necessarily surjective). So $1_{2^X} \leq 2^f \exists_f$ and $\exists_f 2^f \leq 1_{2^Y}$, and it remains to check $1_{2^Y} \leq \exists_f 2^f$.

If $f$ is surjective, then for any $b \in B$ there is $a \in A$ such that $f(a) = b$, and so $b \in \bigcup_{a \in f^{-1}B} f(a)^\uparrow$. Thus $B \subseteq \exists_f f^{-1} B$.

As for showing there is no surjective poset map $f: Y \to 2^{Y^{op}}$, Lemma 1 implies that it suffices to show there can be no reflector $\phi: L \to 2^{L^{op}}$ (consider $L = 2^{Y^{op}}$ and $\phi = \exists_{f^{op}}$).

For any poset $L$, there is no reflector $\phi: L \to 2^{L^{op}}$.

The following diagonalization-style proof is intuitionistically valid and can be enacted in any topos.

Suppose $\phi \dashv s: 2^{L^{op}} \to L$ and $\phi \circ s = 1$. Put

$y = s(\bigcup_{x \notin \phi(x)} \phi(x)).$

We prove $y \notin \phi(y)$. Suppose $y \in \phi(y) = \bigcup_{x \notin \phi(x)} \phi(x)$. Then $y \in \phi(x)$ for some $x$ such that $x \notin \phi(x)$. Also $\phi(x) \subseteq \phi(y)$. So

$x \leq s \phi(x) \leq s \phi(y) = y$

where the first inequality is from $\phi \dashv s$. From $x \leq y$ and $y \in \phi(x)$ and downward-closure of $\phi(x)$, we obtain $x \in \phi(x)$, contradiction.

So $y \notin \phi(y)$. Put $t = s(\{x \in L: x \leq y\})$. We show $t \notin \phi(t)$. If $t \in \phi(t) = \{x: x \leq y\}$, then $t \leq y$, whence $\phi(t) \subseteq \phi(y)$, and since $y \in \phi(t)$ we derive $y \in \phi(y)$, contradiction.

So $t \notin \phi(t)$. But this implies $\phi(t) \subseteq \phi(y)$ by how $y$ was defined, and so $y \in \phi(t)$ implies $y \in \phi(y)$, contradiction.

Similarly, to show there is no surjective poset map $f: Y \to 2^Y$, it suffices by Lemma 1 to show that there can be no reflector $\phi: L \to 2^L$ (put $L = 2^Y$ and $\phi = \exists_f$). We will show how to reduce this to Proposition 1. First, we prove a kind of dual of Lemma 1.

If $i: X \to Y$ is a full poset map, then $2^i = i^{-1}: 2^Y \to 2^X$ is a reflector.

We know $2^i$ (being for example cocontinuous) has a right adjoint which we denote $\forall_i: 2^X \to 2^Y$, so it remains to check that the counit $2^i \circ \forall_i \leq 1$ is an equality. Taking left adjoints on both sides, this is equivalent to the statement that the unit $1 \leq 2^i \exists_i$ of $\exists_i \dashv 2^i$ is an equality. So we check $2^i \exists_i \leq 1$.

For all $A \in 2^X$, if $a' \in i^{-1}(\bigcup_{a \in A} i(a)^\uparrow)$, i.e., if $i(a') \in i(a)^\uparrow$ for some $a \in A$, then $i(a) \leq i(a')$ and thus $a \leq a'$ by fullness, and hence $a' \in A$ since $A$ is upward-closed. Thus $i^{-1}(\bigcup_{a \in A} i(a)^\uparrow) \subseteq A$ for all upward-closed $A$.

For any poset $L$, there is no reflector $\phi: L \to 2^L$.

A preliminary remark will help reduce the claim to Proposition 1. For any poset, the map $prin: P^{op} \to 2^P$ (see the paragraph before Lemma 1) is full (Yoneda lemma). Thus $2^{prin}: 2^{2^P} \to 2^{P^{op}}$ is a reflector by Lemma 2.

Now if $\phi: L \to 2^L$ is a reflector, we have a composite of reflectors

$L \stackrel{\phi}{\to} 2^L \stackrel{\exists_\phi}{\to} 2^{2^L} \stackrel{2^{prin}}{\to} 2^{L^{op}}.$

This composite is also a reflector, and this contradicts Proposition 1.

- Noson Yanofsky,
*A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points*, http://arxiv.org/pdf/math/0305282v1.pdf (May 19, 2003).

Revised on October 5, 2016 at 08:29:29
by
Todd Trimble