> **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\\)

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\\)