Todd Trimble
Cantor's theorem for posets

Contents

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 XXX \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 XX a fixed point YY of X X^-, i.e., a poset YY such that X YYX^Y \cong Y. (To make this more structural, you could for example construe X X^- as a covariant functor on PosPos, by considering left Kan extensions for example, and then ask whether such an endofunctor X :PosPosX^-: 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 XXX \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=2X = 2 (the poset {01}\{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 22 replaced by Ω\Omega):

Theorem

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

Warning

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

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 Y2^Y can be identified with the poset of upward-closed subsets of YY, ordered by inclusion.

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

Definition

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

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

Lemma

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

Proof

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

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

Diagonalization argument

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

Proposition

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

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

Proof

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

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

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

xsϕ(x)sϕ(y)=yx \leq s \phi(x) \leq s \phi(y) = y

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

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

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

No surjective map Y2 YY \to 2^Y

Similarly, to show there is no surjective poset map f:Y2 Yf: Y \to 2^Y, it suffices by Lemma 1 to show that there can be no reflector ϕ:L2 L\phi: L \to 2^L (put L=2 YL = 2^Y and ϕ= f\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:XYi: X \to Y is a full poset map, then 2 i=i 1:2 Y2 X2^i = i^{-1}: 2^Y \to 2^X is a reflector.

Proof

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

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

Proposition

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

Proof

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

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

Lϕ2 L ϕ2 2 L2 prin2 L op.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

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