Todd Trimble Cantor's theorem for posets

Introduction
The proof
- Diagonalization argument
- No surjective map $Y \to 2^Y$
Reference

Introduction

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$ ):

Theorem

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}}$ .

Warning

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.

The proof

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.

Definition

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)$ ).

Lemma

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}}$ .)

Proof

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$ .

Diagonalization argument

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}}$ ).

Proposition

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.

Proof

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.

No surjective map $Y \to 2^Y$

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.

Lemma

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

Proof

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$ .

Proposition

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

Proof

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.

Reference

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 12:29:29 by Todd Trimble

Todd Trimble Cantor's theorem for posets

Contents

Introduction

Theorem

Warning

The proof

Definition

Lemma

Proof

Diagonalization argument

Proposition

Proof

No surjective map Y→2 YY \to 2^Y

Lemma

Proof

Proposition

Proof

Reference

No surjective map $Y \to 2^Y$