The reverse can be done easily and the proof is well known I am wondering if the exact same argument can be used to prove reverse as well.

  • 1
    $\begingroup$ I understand the SB theorem as saying that in the category of sets, if there exists monos from X to Y and from Y to X, there there exists an isomorphism between them. I understand the KT theorem as saying that if $f: X \to X$ is a monotone function on a sup-lattice, then $f$ has a fixed point. Is that what you mean as well? $\endgroup$
    – Todd Trimble
    Oct 17, 2010 at 13:26
  • $\begingroup$ Forgive my ignorance, but why does this have a rings-and-algebras tag? $\endgroup$
    – Yemon Choi
    Oct 19, 2010 at 23:42
  • $\begingroup$ @Yemon Choi: "Lattice theory and universal algebra" is considered part of "rings and algebras" by the arXiv. $\endgroup$ Oct 20, 2010 at 0:46
  • $\begingroup$ @Bjørn: I asked because I seem to recall you tagging a question about $H^\infty$ (or some kind of AP question) with the rings-and-algebras tag, which bumped it back to the front page to no apparent purpose. $\endgroup$
    – Yemon Choi
    Oct 20, 2010 at 3:17
  • $\begingroup$ That said, your explanation about lattice theory being R&A by arXiv classification does make sense to me $\endgroup$
    – Yemon Choi
    Oct 20, 2010 at 3:18

1 Answer 1


The Cantor-Schroeder-Bernstein theorem admits many proofs of various natures, which have been extended in diverse mathematical contexts to show that the phenomenon holds in many other parts of mathematics. So the question of whether the CSB property holds is an interesting mathematical question in many mathematical contexts (and it is particularly interesting in contexts where it fails).

And the proof of CSB from the Knaster-Tarski theorem that you have in mind proceeds as follows: suppose that $f:A\to B$ and $g:B\to A$ are both injective. Define $\varphi:P(A)\to P(A)$ on the power set of $A$ by $\varphi(X)=A-g[B-f[X]]$. It is easy to see by applying the functions and taking complements (twice) that $X\subset Y\to \varphi(X)\subseteq \varphi(Y)$, and so $\varphi$ is a monotone (order-preserving) operation on the power set of $A$, a complete lattice. Thus, by KT there is a fixed point $\varphi(X)=X$. From this, it follows that the function $h=(f|X)\cup(g^{-1}|(A-X))$ is a bijection between $A$ and $B$, and I leave all the details as a fun exercise.

Meanwhile, the proof of KT itself has a very short direct proof, which it would seem difficult to improve upon by using CSB. Namely, if $\varphi:L\to L$ is a order-preserving function on a complete lattice $L$, then let $d=\wedge\{e \mathrel{|} \varphi(e)\leq e\}$. Note that $\varphi(e)\leq e$ implies $d\leq e$ which implies $\varphi(d)\leq \varphi(e)\leq e$ and so $\varphi(d)\leq d$ and consequently $\varphi(\varphi(d))\leq \varphi(d)$, and so $\varphi(d)$ is one of the $e$'s, and so $d\leq \varphi(d)$ and hence $d=\varphi(d)$, as desired.

Note that the function $\varphi$ arising in the proof of CSB from KT is not merely monotone, but also continuous, since if $X=\bigcup_i X_i$, then $f[X]=\bigcup_i f[X_i]$ and so $B-f[X]=\bigcap_i B-f[X_i]$ and thus $g[B-f[X]]=\bigcap_i g[B-f[X_i]]$, because $g$ is injective, and hence $\varphi(X)=A-g[B-f[X]]=A-\bigcap_i g[B-f[X_i]]=\bigcup_i (A-g[B-f[X_i]])=\bigcup_i \varphi(X_i)$. In short, $\varphi(\bigcup_i X_i)=\bigcup_i\varphi(X_i)$, which means that $\varphi$ is continuous.

Thus, the standard argument shows that CSB follows not only from KT, but from the special case of continuous-KT, that is, KT restricted to continuous monotone functions. But the full KT is true for arbitrary monotone $\varphi$, even when they are not continuous, by the simple argument above. I take this as suggesting that the ``exact same argument,'' as you asked in your question, does not establish KT from CSB. Not every monotone $\varphi$ arises as the $\varphi$ used in the proof, since not every monotone map is continuous.

Meanwhile, I also observe that the direct proof of KT is so simple, it would seem difficult to find a substantially simpler proof of it by using any other principle, including CSB.

  • $\begingroup$ I've been interpreting the question in the context of reverse mathematics. I figure is the only way of making sense of it and hoping for some kind of answer. $\endgroup$ Oct 20, 2010 at 1:09
  • $\begingroup$ The proof that Joel Hamkins gives above for KST works in RCAo assuming that we use the naive formalizations of "countable complete lattice" and "monotone function". I don't know enough about complete lattices to know whether KST for countable complete lattices is of much interest, though. Similarly, CSB is provable in RCAo, but not by the proof that is sketched (which uses powersets). The proof of CSB breaks into cases depending whether the sets are finite or infinite. The finite case uses a pigeonhole principle. The infinite case is trivial: every two infinite sets are in bijection in RCAo. $\endgroup$ Oct 20, 2010 at 2:49
  • $\begingroup$ Thank you @Joel David Hamkins for sharing this lovely proof of CSB via KT, and (to my mind) beautiful proof of KT itself. Regarding your proof that $\varphi$ is continuous, I am probably being very dense here, but don't all functions commute with union, and aren't all functions on the power set of a given set, partially ordered with respect to set inclusion, therefore continuous, with respect to that partial order ? $\endgroup$
    – Simon
    Dec 14, 2018 at 11:43
  • $\begingroup$ @Simon I'm glad you like the proof. Regarding your latter comment, however, I agree that all functions on the power set that arise by application of a function on the underlying set will be continuous in the way you describe. But there are other functions on the power set that do not arise by application of a function on the underlying space, and indeed, the function $\varphi$ does not arise that way. So the assertion that it is continuous has content. $\endgroup$ Dec 14, 2018 at 14:30
  • 1
    $\begingroup$ @AnduinWilde When I looked on my phone, I saw that error you mentioned, but now that I am on my computer, on Chrome, I see no error with "in short". So this seems to be some kind of display bug with the very long line of math, rather than anything wrong with the answer text. $\endgroup$ Nov 30, 2023 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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