Cantor's theorem states that we cannot construct an surjective map from $X \to \mathcal{P}(X)$ which can be rephrased as there is no $X$ such that $X \to \{0, 1\} \cong X$.

I was wondering if this is still true if we change from arbitrary $X$s and arbitrary maps to partially ordered sets $P$ and monotone maps? Eg is there a partially ordered set $P$ such that the set of monotone maps $P \to \{0, 1\}$ (ordered pointwise) is isomorphic to $P$?

  • 1
    $\begingroup$ I had thought of Cantor's theorem as saying there is no surjection from $X$ to $\mathcal P(X)$. ${}\qquad{}$ $\endgroup$ Aug 25 '15 at 23:43
  • $\begingroup$ How do you order $\{0,1\}$? $\endgroup$
    – Asaf Karagila
    Aug 25 '15 at 23:44
  • $\begingroup$ @AsafKaragila $0 \le 1$. The idea being that you can uniquely describe a subset with a function which is $1$ for all members of the subset and $0$ for everything else. $\endgroup$ Aug 25 '15 at 23:46
  • $\begingroup$ @MichaelHardy Quite right, long day :) $\endgroup$ Aug 25 '15 at 23:46
  • $\begingroup$ So I assume you mean partial order in the reflexive, anti-symmetric and transitive; rather than irreflexive and transitive. $\endgroup$
    – Asaf Karagila
    Aug 25 '15 at 23:47

The strengthened version is true.

Let $\langle P,\le\rangle$ be a partial order, let $2=\{0,1\}$, and let $M$ be the set of monotone maps from $P$ to $2$ with the natural pointwise partial order $\preceq$. Suppose that $\varphi:\langle P,\le\rangle\cong\langle M,\preceq\rangle$. Clearly the constant functions $\mathbf{0}$ and $\mathbf{1}$ are the minimum and maximum elements of $M$ respectively, so $P$ has a minimum element $b$ and a maximum element $t$. Let

$$f_0:P\to 2:x\mapsto\begin{cases} 1,&\text{if }x=t_0\\ 0,&\text{otherwise}\;; \end{cases}$$

then $f_0\in M$, and $f_0$ is the immediate successor of $\mathbf{0}$. Similarly,

$$g_0:P\to 2:x\mapsto\begin{cases} 0,&\text{if }x=b_0\\ 1,&\text{otherwise}\;; \end{cases}$$

is the immediate predecessor of $\mathbf{1}$ in $M$. Then $b_0=\varphi^{-1}(f_0)$ and $t_0=\varphi^{-1}(g_0)$ are the minimum and maximum elements, respectively, of $M\setminus\{\mathbf{0},\mathbf{1}\}$.

Suppose that for some ordinal $\eta$ we’ve defined $b_\xi,t_\xi\in P$ and $f_\xi,g_\xi\in M$ for $\xi<\eta$ so that for each $\xi<\eta$ we have

$$\begin{align*} b_\xi&=\min(P\setminus\{b_\zeta:\zeta<\xi\})\;,\\ t_\xi&=\max(P\setminus\{t_\zeta:\zeta<\xi\})\;,\\ \varphi(b_\xi)=f_\xi&=\min(M\setminus\{f_\zeta:\zeta<\xi\})\;,\text{ and}\\ \varphi(t_\xi)=g_\xi&=\max(M\setminus\{g_\zeta:\zeta<\xi\})\;. \end{align*}$$

Let $B_\eta=\{b_\xi:\xi<\eta\}$ and $T_\eta=\{t_\xi:\xi<\eta\}$; if $x\in P\setminus(B_\eta\cup T_\eta)$, then $b_\zeta<x<b_\xi$ for all $\zeta,\xi<\eta$. Define

$$f_\eta:P\to 2:x\mapsto\begin{cases} 1,&\text{if }x\in T_\eta\\ 0,&\text{otherwise}\;; \end{cases}$$


$$g_\eta:P\to 2:x\mapsto\begin{cases} 0,&\text{if }x\in B_\eta\\ 1,&\text{otherwise}\;. \end{cases}$$

Clearly $f_\xi\prec f_\eta$ and $g_\eta\prec g_\xi$ for each $\xi<\eta$. Moreover, if $h\in M\setminus\varphi[B_\eta]$, then $h(t_\xi)=1$ for each $\xi<\eta$, so $f_\eta\preceq h$, and hence $f_\eta=\min\big(M\setminus\varphi[B_\eta]\big)$. Similarly, $g_\eta=\max\big(M\setminus\varphi[T_\eta]\big)$, and we can continue to extend the recursive construction.

Suppose that at some point $P=B_\eta\cup T_\eta$. Then the function

$$h:P\to 2:x\mapsto\begin{cases} 0,&\text{if }x\in B_\eta\\ 1,&\text{if }x\in T_\eta \end{cases}$$

is monotone and not in the range of $\varphi$. Thus, the recursion defines two injections of the ordinals into $P$, which is impossible.

  • $\begingroup$ Ah this is wonderful, thank you :) I feel slightly better about not being able to come up with a construction now.. $\endgroup$ Aug 26 '15 at 1:14
  • $\begingroup$ @jozefg: You’re welcome. It was a neat problem; I’m glad that you asked it. $\endgroup$ Aug 26 '15 at 1:16
  • $\begingroup$ Nit pick: the numeration looks a little off in the second paragraph. Since $b_0$ and $t_0$ are the bottom and top elements, we have $\phi(b_0) = \mathbf{0}$ and $\phi(t_0) =\mathbf{1}$; I think what you want at the end of the second paragraph is $b_1 = \phi^{-1}(f_0)$ and $t_1 =\phi^{-1}(g_0)$, or in other words $\phi(b_1) = f_0$ and $\phi(t_1) = g_0$. $\endgroup$
    – user43208
    Mar 9 '16 at 13:03
  • $\begingroup$ @user43208: That was indeed an oversight, though I prefer to fix it a little differently; thanks! $\endgroup$ Mar 9 '16 at 19:31

Brian Scott's proof is perfectly clear, but somewhat removed from the type of diagonalization argument one naturally associates with Cantor's theorem, Russell's paradox, and so on (see this paper by Yanofsky for a comprehensive overview of diagonalization arguments). I'd like to offer an approach that at its core emphasizes diagonalization.

It's easiest to explain the proof using some (easy) category theory, leaving some steps to the reader. I can give more details if desired. For the cognoscenti, the proof can be internalized to any topos, with $2$ below replaced by the subobject classifier $\Omega$. .

Let $2^X$ denote the poset of order-preserving maps (aka poset maps) $X \to 2 = \{0 \leq 1\}$, with the pointwise order, and let $X^{op}$ denote the opposite or dual poset of $X$. I'll prove a stronger result.

Theorem: There exists no surjective poset map $f: X \to 2^X$, and no surjective poset map $f: X \to 2^{X^{op}}$.

$2^X$ is canonically identified with the poset of upward closed subsets $A \subseteq X$ ordered by inclusion; here upward closed means that if $a \in A$ and $a \leq b$, then $b \in A$. (For, each $f: X \to 2$ determines and is determined by the upward closed subset $f^{-1}(1)$.) Similarly, $2^{X^{op}}$ is canonically identified with the poset of downward closed subsets of $X$, ordered by inclusion (each $f: X^{op} \to 2$ determines and is determined by a downward closed subset $f^{-1}(1)$ of $X$).

A poset map $f: X \to Y$ induces a map $2^f: 2^Y \to 2^X$, sending a poset map $g: Y \to 2$ to $g \circ f: X \to 2$. It can also be viewed as taking an upward closed $B \subseteq Y$ to the inverse image $f^{-1}(B)$ which is also upward closed. The map $2^f$ has a left adjoint, denoted as $\exists_f: 2^X \to 2^Y$. This is a poset map such that for any upward closed $A \subseteq X$ and $B \subseteq Y$ we have

$$\exists_f(A) \subseteq B \qquad iff \qquad A \subseteq f^{-1}(B).$$

The subset $\exists_f(A)$ may be succinctly described as the smallest upward closed subset of $Y$ containing the image $f(A)$.

Generally speaking, an adjunction between posets, say $f: X \to Y$ and $g: Y \to X$ with $f \dashv g$, is equivalently described as a pair of maps such that $1_X \leq g f$ and $f g \leq 1_Y$. A left adjoint $f$ such that the inequality $f g \leq 1_Y$ is an equality will be called a reflector. It should be considered a strong notion of surjective map.

Lemma 1: If $f: X \to Y$ is surjective, then $\exists_f: 2^X \to 2^Y$ is a reflector.

The proof is easy. Since $f^{op}: X^{op} \to Y^{op}$ is also surjective, we have that $\exists_{f^{op}}$ is also a reflector.

Here is the core diagonalization argument:

Proposition 1: For any poset $L$, there exists no reflector map $\phi: L \to 2^{L^{op}}$.

Notice that this would prove the half of the theorem that says there are no surjective poset maps $f: X \to 2^{X^{op}}$, otherwise put $L = 2^{X^{op}}$ and $\phi = \exists_{f^{op}}$ to derive a contradiction.

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

(This proof is actually intuitionistically valid. If anyone has doubts, I suggest reading this article by Andrej Bauer on the distinction between "proof of negation" and "proof by contradiction".)

Now we'll wrap things up. A poset map $f: X \to Y$ is called full if for any elements $x, y \in X$, we have $x \leq y$ whenever $f(x) \leq f(y)$. It is easy to see that full maps are injective.

Lemma 2: If $i: X \to Y$ is a full map, then $2^i$ is a reflector.

I'll sketch the proof. $2^i: 2^Y \to 2^X$ has a right adjoint (which category theorists often denote by $\forall_i: 2^X \to 2^Y$) because it preserves colimits (joins). So we have $1_{2^Y} \leq \forall_i 2^i$ and $2^i \forall_i \leq 1_{2^X}$, so all that is left is to show $1_{2^X} \leq 2^i \forall_i$, equivalent to $\exists_i \leq \forall_i$, equivalent to $2^i \exists_i \leq 1_{2^X}$. But for any upward closed $A \subseteq X$, if $a' \in i^{-1} \exists_i A$, then $i(a')$ belongs to the upward closure of $i(A)$, i.e., $i(a) \leq i(a')$ for some $a \in A$. Since $i$ is full, $a \leq a'$, and since $A$ is upward closed, $a' \in A$. Thus we have shown $i^{-1} \exists_i A \subseteq A$, as desired.

Proposition 2: There is no reflector map $\phi: L \to 2^L$.

Proof: Let $i: L^{op} \to 2^L$ be the poset map taking $x \in L$ to the upward closed set $\{y \in L: x \leq y\}$. It is simple to check that $i$ is full (it is an analogue of the Yoneda embedding). Thus $2^i$ is a reflector by Lemma 2, and so if we suppose there exists a reflector $\phi: L \to 2^L$, we get a composite of reflector maps

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

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

This gives the other half of the theorem, using the same reasoning as in the sentence just after the statement of Proposition 1.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.