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 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 a fixed point of , i.e., a poset such that . (To make this more structural, you could for example construe as a covariant functor on , by considering left Kan extensions for example, and then ask whether such an endofunctor has an initial algebra.) If that were true, then it would immediately follow from Lawvere’s fixed-point theorem that every map 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 (the poset ).
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 replaced by ):
There can be no surjective poset map . Similarly, there can be no surjective poset map .
This theorem is not entirely obvious, at least not to me. As indicated above, a surjection is not ruled out by Lawvere’s fixed-point theorem via the implication that every endomap has a fixed point: that conclusion is true if is a sup-lattice. And it’s certainly not something one can deduce on crude cardinality grounds, since for example the case , the first infinite ordinal, yields (freely adjoin a bottom element to ), with the same cardinality as .
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 can be identified with the poset of upward-closed subsets of , ordered by inclusion.
The following notion, which we may think of as a strong notion of surjectivity, will be useful.
A map between posets is a reflector if it has a right adjoint whose counit is an equality (the right adjoint of a reflector will be called simply the adjoint of ).
For any poset map , we define to be the left adjoint of . The map takes an upward-closed to the smallest upward-closed set containing , in other words where is the upward set generated by (aka the principal filter generated by , also denoted ).
If is a surjective poset map, then is a reflector. (As is also surjective, is also a reflector with adjoint .)
The adjunction is well-known and elementary, and obtains for any poset map (not necessarily surjective). So and , and it remains to check .
If is surjective, then for any there is such that , and so . Thus .
As for showing there is no surjective poset map , Lemma 1 implies that it suffices to show there can be no reflector (consider and ).
For any poset , there is no reflector .
The following diagonalization-style proof is intuitionistically valid and can be enacted in any topos.
Suppose and . Put
We prove . Suppose . Then for some such that . Also . So
where the first inequality is from . From and and downward-closure of , we obtain , contradiction.
So . Put . We show . If , then , whence , and since we derive , contradiction.
So . But this implies by how was defined, and so implies , contradiction.
Similarly, to show there is no surjective poset map , it suffices by Lemma 1 to show that there can be no reflector (put and ). We will show how to reduce this to Proposition 1. First, we prove a kind of dual of Lemma 1.
If is a full poset map, then is a reflector.
We know (being for example cocontinuous) has a right adjoint which we denote , so it remains to check that the counit is an equality. Taking left adjoints on both sides, this is equivalent to the statement that the unit of is an equality. So we check .
For all , if , i.e., if for some , then and thus by fullness, and hence since is upward-closed. Thus for all upward-closed .
For any poset , there is no reflector .
A preliminary remark will help reduce the claim to Proposition 1. For any poset, the map (see the paragraph before Lemma 1) is full (Yoneda lemma). Thus is a reflector by Lemma 2.
Now if is a reflector, we have a composite of reflectors
This composite is also a reflector, and this contradicts Proposition 1.