# Can the Knaster-Tarski theorem be proved using the Schroeder-Bernstein theorem?

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.

• 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.

• 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
• 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 ? – Simon Dec 14 '18 at 11:43
• @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. – Joel David Hamkins Dec 14 '18 at 14:30
• @JoelDavidHamkins, thank you very much for your nice reply. I was indeed being dense ! Only a tiny proportion of the functions from $P(A)$ to $P(B)$ arise from functions from $A$ to $B$ in this way. – Simon Dec 15 '18 at 8:56