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 and , 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 is the greast fixpoint of f.

**Proof.** Let . Consider , we have for all , and thus which means that is an upper bound of , i.e. . However, since , we also have which satisfies the predicate of . Hence, and by definition. Finally, we thus have and , so .

The part of greatestness is obvious.

Now, we could simplify the proof of Cantor–Bernstein–Schroeder between sets by explicitly defining the construction of sequence of sets as a function from . However, we also generalise the process than we need.

**Theorem.** Given two functions and . There are disjoint sets and with and and , .

**Proof.** Consider which may give a hint that works if it is order-preserving. However, it is obvious that as , . By applying Knaster-Tarski theorem, we have a fixpoint with the desired properties.

Finally, with the help of the above fact we could decompose the domain and codomains of injections and , and thus we have two bijections and where , , , and . Then, define which is obviously bijective. Done.

# Cantor–Bernstein–Schroeder theorem

### Like this:

Like Loading...

*Related*

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

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?

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

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

Why?