# Knaster-Tarski Theorem

Knaster-Tarski theorem is a simple but powerful fixpoint theorem in order theory. It could give a very elegant proof of Cantor–Bernstein–Schroeder theorem which states that if there are injections $f : A \rightarrow B$ and $g : B \rightarrow A$, there exists a bijection between A and B.

Theorem. Let L be a complete lattice and f be a order-preserving morphism from L to L. The sup (join) of the set $\{ x \in L : x \leq f(x) \}$ is the greast fixpoint of f.

Proof. Let $X = \{ x \in L : x \leq f(x) \}$. Consider $s = \bigvee X$, we have $x \leq s$ for all $x \in X$, and thus $x \leq f(x) \leq f(s)$ which means that $f(s)$ is an upper bound of $X$, i.e. $s \leq f(s)$. However, since $s \leq f(s)$, we also have $f(s) \leq f(f(s))$ which satisfies the predicate of $X$. Hence, $f(s) \in X$ and $f(s) \leq s$ by definition. Finally, we thus have $s \leq f(s)$ and $s \geq f(s)$, so $s = f(s)$.

The part of greatestness is obvious. $\Box$

Now, we could simplify the proof of Cantor–Bernstein–Schroeder between sets $X, Y$ by explicitly defining the construction of sequence of sets as a function from $\mathcal{P}(X) \rightarrow \mathcal{P}(Y)$. However, we also generalise the process than we need.

Theorem. Given two functions $f : A \rightarrow B$ and $g : B \rightarrow A$. There are disjoint sets $X_1, X_2$ and $Y_1, Y_2$ with $X = X_1 \cup X_2$ and $Y = Y_1 \cup Y_2$ and $f(X_1) = Y_1$, $g(Y_2) = X_2$.

Proof. Consider $X = X_1 \cup X_2 = X_1 \cup (g(Y_2)) \Leftrightarrow X_1 = X \backslash g(Y_2) = X \backslash g(Y \backslash f(X_1))$ which may give a hint that $F(S) = X \backslash g(Y \backslash f(S))$ works if it is order-preserving. However, it is obvious that as $S_1 \subseteq S_2$, $F(S_1) \subseteq F(S_2)$. By applying Knaster-Tarski theorem, we have a fixpoint $X_1$ with the desired properties. $\Box$

Finally, with the help of the above fact we could decompose the domain and codomains of injections $f : A \rightarrow B$ and $g : B \rightarrow A$, and thus we have two bijections $f |_{A_1} : A_1 \rightarrow B_1$ and $g |_{B_2} : B_2 \rightarrow A_2$ where $A = A_1 \cup A_2$, $\emptyset = A_1 \cap A_2$, $B_1 \cap B_2 = \emptyset$, and $B = B_1 \cup B_2$. Then, define $h = (f|_{A_1}) \cup (g|_{B_2})^{-1} : A \rightarrow B$ which is obviously bijective. Done.

# Cantor–Bernstein–Schroeder theorem

## 3 thoughts on “Knaster-Tarski Theorem”

1. I have seen a tutorial from Roland Backhouse on fixed-points entirely in a calculational style. I like it because I don’t trust my proof unless I can do it this way.

Backhouse abused the notation a bit by writing ∀ x ∈ X . x ≤ y as X ≤ y.

The definition of lub is that s = ⋁ X iff.

1. s is an upperbound of X. That is, for all y,
y ∈ X ⇒ y ≤ s.

2. s is the least among upper bounds of X. That is forall y,
X ≤ y ⇒ s ≤ y.

Let X = {x ∈ L ∣ x ≤ f x} and s = ⋁ X. The proof of s ≤ f s goes:

s ≤ f s
⇐ { 2. }
X ≤ f s
⇐ { since X ≤ f X }
f X ≤ f s
⇐ { f monotonic }
X ≤ s

And the proof of f s ≤ s goes:

f s ≤ s
⇐ { 1. }
f s ∈ X
≡ { definition of X }
f s ≤ f (f s)
⇐ { f monotonic }
s ≤ f s

2. I don’t understand the proof of Cantor–Bernstein–Schroeder, however.

“There are disjoint sets X₁, X₂ … with X = X₁ ∪ X₂..” I think this is only possible if X is non-empty?

So is the rest of the proof trying to construct X₁ by picking some F and let X₁ be the greatest fixed point of F?

What are A₁, B₁, etc, then?

3. I slightly elaborate the layout and the detail. Hope it is helpful.

“I think this is only possible if X is non-empty?”
Why?