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?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s