> **Puzzle 10.** There are many examples of monotone maps between posets. List a few interesting ones!

Here's one inside a proof:

**The Schröder–Bernstein Theorem**. Let \$$f: X \rightarrowtail Y\$$ and \$$g: Y \rightarrowtail X\$$ be a pair of injections. There exists a bijection \$$h: X \to Y\$$.

**Proof**.

Let \$$f[A] := \\{f(a)\ :\ a \in A\\}\$$ denote the image of \$$f\$$ and similarly let \$$g[\cdot]\$$ denote the image of \$$g\$$.

Define \$$F: \mathcal{P}(X) \to \mathcal{P}(X)\$$ as follows:

$$F(S) := X - g[Y - f[S]]$$

*\$$F\$$ is a **monotone map** on \$$\mathcal{P}(X)\$$ when ordered by set containment.*

Define \$$\mu F\$$ to be:

$$\mu F := \bigcap \\{A \subseteq X\ :\ F(A) \subseteq A\\}$$

Then \$$F(\mu F) = \mu F\$$. This is the [Knaster-Tarski Theorem](https://en.wikipedia.org/wiki/Knaster%E2%80%93Tarski_theorem) and generalizes to any monotone map on any complete lattice to itself.

Finally, define \$$h: X \to Y\$$:

$$h(x) := \begin{cases} f(x) & x \in \mu F \\\\ g^{-1}(x) & x \not\in \mu F \end{cases}$$

Then \$$h\$$ is the desired bijection, and its inverse is given by:

$$h^{-1}(y) := \begin{cases} f^-1(y) & y \in f[\mu F] \\\\ g(y) & y \not\in f[\mu F] \end{cases}$$

It's straight forward to check these are both well defined, injective and indeed inverses.

\$$\Box\$$