Least Fixed-Points of Monotone Functions are Monotone

This post presents a simple lemma related to the Knaster-Tarski fixed-point theorem. I used to think it's obvious, but today I set out to write down the full proof and I was somewhat surprised that I got stuck for awhile. As often is the case, I got unstuck with some help from Rasmus, and his slides in this case.

Definitions. Feel free to skip and refer back only if necessary.

A partial order $\le$ is a binary relation that is reflexive, transitive, and antisymmetric. $$ \begin{align} &(1) &&x \le x\\ &(2) &&x \le y \land y \le z \to x \le z\\ &(3) &&x \le y \land y \le x \to x = y \end{align} $$ A greatest lower bound $\inf Y$ of a set $Y$ is a lower bound (smaller than all elements of $Y$) and as big as possible: $$ \begin{align} &(4) &&y:Y\to \inf Y \le y\\ &(5) &&(\forall y\; y:Y\to x\le y) \to x\le\inf Y \end{align} $$ Lowest upper bounds are defined symmetrically. A set equipped with a preorder is a complete lattice when all its subsets $Y$ have a greatest lower bound $\inf Y$ and a lowest upper bound $\sup Y$. A function $f$ is monotone when it preserves the order: $$ \begin{align} &(6) && x \le y \to f(x) \le f(y) \end{align} $$ A pre-fixed-point of $f$ is an element $x$ that may only decrease by going thru $f$: $$ \begin{align} &(7) && f(x) \le x \end{align} $$ Post-fixed-points are defined symmetrically. A fixed-point is an element that is both pre- and post-fixed-point. A least fixed point ${\rm lfp}\,f$ of $f$ is the minimum of fixed points: $$ \begin{align} &(8) &&f({\rm lfp}\,f)={\rm lfp}\,f\\ &(9) &&f(x)=x \to {\rm lfp}\,f \le x \end{align} $$ Note that there is no a-priori reason to believe that least fixed-points (or even fixed-points) exist. Let ${\rm pre}\,f=\{x:f(x)\le x\}$ denote the set of $f$'s pre-fixed points.

Lemmas. Suppose from now on that $f$ is a fixed but arbitrary monotone function, on some complete lattice. Here's the first lemma: $$ \begin{align} &(10) &&f(y)\le y \to f(\inf{\rm pre}\,f) \le y \end{align} $$ Proof. $$ \begin{align} & &&f(y) \le y\\ &\Rightarrow &&\{\text{$(4)$ with $Y:={\rm pre}\,f$}\}\\ & &&\inf{\rm pre}\,f \le y\\ &\Rightarrow &&\{(6)\}\\ & &&f(\inf{\rm pre}\,f)\le f(y)\\ &\Rightarrow &&\text{assumption $f(y)\le y$}\\ & &&f(\inf{\rm pre}\,f)\le y \end{align} $$

Here's the second lemma: $$ \begin{align} &(11) &&f(\inf{\rm pre}\,f) \le \inf{\rm pre}\,f \end{align} $$ Proof. Instantiate (5) with $x:=f(\inf{\rm pre}\,f)$, and use (10) to discharge the assumption.

Here's the third lemma: $$ \begin{align} &(12) &&\inf{\rm pre}\,f \le f(\inf{\rm pre}\,f) \end{align} $$ Proof. Be careful here. It's a tricky argument that avoids talking about descending chains and such. $$ \begin{align} & &&\{(11)\} \\ & &&f(\inf{\rm pre}\,f) \le \inf{\rm pre}\,f \\ &\Rightarrow &&\{(6)\}\\ & &&f(f(\inf{\rm pre}\,f)) \le f(\inf{\rm pre}\,f) \\ &\Rightarrow &&\{\text{$(4)$ with $y:=f(\inf{\rm pre}\,f)$ and $Y:={\rm pre}\,f$}\} \\ & &&\inf{\rm pre}\,f \le f(\inf{\rm pre}\,f) \end{align} $$

Here's the fourth lemma: $$ \begin{align} &(13) &&{\rm lfp}\,f \le \inf{\rm pre}\,f \end{align} $$ Proof. $$ \begin{align} & &&\{\text{$(3)$ with $x:=\inf{\rm pre}\,f$ and $y:=f(\inf{\rm pre}\,f)$}\}\\ & &&(\inf{\rm pre}\,f \le f(\inf{\rm pre}\,f))\land(f(\inf{\rm pre}\,f) \le \inf{\rm pre}\,f) \to \inf{\rm pre}\,f=f(\inf{\rm pre}\,f)\\ &\Rightarrow &&\{\text{$(11)$ and $(12)$}\}\\ & &&\inf{\rm pre}\,f=f(\inf{\rm pre}\,f) \\ &\Rightarrow &&\{\text{$(9)$ with $x:=\inf{\rm pre}\,f$}\} \\ & &&{\rm lfp}\,f \le \inf{\rm pre}\,f \end{align} $$

You guessed: Here's the fifth lemma: $$ \begin{align} &(14) &&f(y)\le y \to {\rm lfp}\,f \le y \end{align} $$ Proof. $$ \begin{align} & &&f(y) \le y \\ &\Rightarrow &&\{(10)\} \\ & &&f(\inf{\rm pre}\,f) \le y \\ &\Rightarrow &&\{\text{$(13)$ and $(2)$}\} \\ & &&{\rm lfp}\,f \le y \end{align} $$

Proposition. Least-fixed points of monotone functions are monotone. Given that both $f$ and $g$ are monotone functions on some complete lattice, we have that $$ \begin{align} \bigl(\forall x\; f(x) \le g(x)\bigr) \to {\rm lfp}\,f \le {\rm lfp}\, g \end{align} $$ Proof. $$ \begin{align} & &&f(x) \le g(x) \\ &\Rightarrow &&\{\text{instantiate with $x:={\rm lfp}\,g$}\} \\ & &&f({\rm lfp}\,g) \le g({\rm lfp}\,g) \\ &= &&\{\text{$(8)$ with $f:=g$}\} \\ & &&f({\rm lfp}\,g) \le {\rm lfp}\,g \\ &\Rightarrow &&\{\text{$(14)$ with $y:={\rm lfp}\,g$}\} \\ & &&{\rm lfp}\,f \le {\rm lfp}\, g \end{align} $$