MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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? – Todd Trimble Oct 17 '10 at 13:26
Forgive my ignorance, but why does this have a rings-and-algebras tag? – Yemon Choi Oct 19 '10 at 23:42
@Yemon Choi: "Lattice theory and universal algebra" is considered part of "rings and algebras" by the arXiv. – Bjørn Kjos-Hanssen Oct 20 '10 at 0:46
@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. – Yemon Choi Oct 20 '10 at 3:17
That said, your explanation about lattice theory being R&A by arXiv classification does make sense to me – Yemon Choi Oct 20 '10 at 3:18

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.

share|cite|improve this answer
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. – Andrés E. Caicedo Oct 20 '10 at 1:09
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. – Carl Mummert Oct 20 '10 at 2:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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