I am trying to prove the Bourbaki–Witt theorem, which states:
Let $\left(X,\leq\right)$ be a partially ordered set and let $f:X\rightarrow X$ be a function. Suppose that $f\left(x\right)\geq x$ for all $x\in X$ and that every chain in $X$ has a supremum. Then for all $x\in X$, there exists an element $y\in Y$ such that $y\geq x$ and $f\left(y\right)=y$.
There is more than one way to prove this theorem. The method I want to use involves Hartogs Lemma (there exists an ordinal which does not inject to a given set) and transfinite recursion. The proofs I have seen start by recursively defining a function as follows:
This is from the following proofwiki article: Bourbaki–Witt theorem .
First of all, I am uncomfortable with how they defined $g$. It's not rigorous enough for me. My goal is to define $g$ more rigorously/precisely using the recursion theorem. This is the version of the recursion theorem that I will use:
Let $\alpha$ be an ordinal, let $Y$ be a non-empty set, and let $a\in Y$. Let $g:Y\rightarrow Y$ be a function and let $h:\wp\left(Y\right)\rightarrow Y$ be a function. Then there exists a unique function $\varphi:\alpha\rightarrow Y$ such that
• $\varphi\left(\emptyset\right)=a$,
• $\varphi\left(\beta^{+}\right)=g\left(\varphi\left(\beta\right)\right)$ for all $\beta\in\alpha$ with $\beta^{+}\in\alpha$, and
• $\varphi\left(\gamma\right)=h\left(\varphi\left[\gamma\right]\right)$ for every limit ordinal $\gamma\in\alpha$.
By $\beta^{+}$, I mean the immediate successor of the ordinal $\beta$ and by $\wp\left(Y\right)$, I mean the power set of $Y$. Also, $\varphi\left[\gamma\right]$ is the set $\left\{ \varphi\left(\beta\right):\beta\in\gamma\right\} $.
Is this version of the Recursion Theorem sufficient to define $g$? I know that there are many different versions of the recursion theorem that may be more appropriate than this one. Now using this recursive definition, I will try to define the function $g$ used in the proofwiki article, which I will just label $\varphi$:
Let $x\in X$ and let $\alpha$ be an ordinal such that there does not exist an injection from $\alpha$ to $X$. Let $h:\wp\left(X\right)\rightarrow X$ be any function such that for all $A\in\wp\left(X\right)$, if $A$ is a chain in $X$, then $h\left(A\right)=\sup A$ . By the Recursion Theorem above, there exists a unique function $\varphi:\alpha\rightarrow X$ such that
• $\varphi\left(\emptyset\right)=x$,
• $\varphi\left(\beta^{+}\right)=f\left(\varphi\left(\beta\right)\right)$ for all $\beta\in\alpha$ with $\beta^{+}\in\alpha$, and
• $\varphi\left(\gamma\right)=h\left(\varphi\left[\gamma\right]\right)$ for every limit ordinal $\gamma\in\alpha$.
This is how I started the proof. Now evidently, the function $\varphi$ is apparently not the function required. I need to show that if $\gamma\in\alpha$ is a limit ordinal, then $\varphi\left[\gamma\right]$ is a chain in $X$. That will guarantee that $\varphi\left[\gamma\right]$ will have a supremum. I will then have obtained the function in the proofwiki article. This is the part that I am having trouble with. The proofwiki article stated that indeed this is the case and follows from the fact that $f\left(x\right)\geq x$ for all $x\in X$. However, this is not at all obvious to me. How can I show that $\varphi\left[\gamma\right]$ is a chain in $X$ for every limit ordinal $\gamma$?
$f$ is known as inflationary iff for any $x, f(x)\geqslant x$. So it is obvious that $f$ inflationary implies $\varphi(\beta)$ increasing (as mentioned in proofwiki ) for $$ \varphi(\beta^+)=f(\varphi(\beta))\geqslant \varphi(\beta) $$ Also $\varphi\left[\gamma\right]$ is clearly a chain for $\gamma_1<\gamma_2$ $$ \varphi[\gamma_1]=\{\varphi(\beta):\beta<\gamma_1\} \subset \{\varphi(\beta):\beta<\gamma_2\}=\varphi[\gamma_2] $$ If $\alpha$ is limit ordinal, then for $\gamma_1<\gamma_2<\cdots<\alpha$ $$ \varphi[\gamma_1]\subset\varphi[\gamma_2]\subset\cdots\subset\bigcup_{\gamma<\alpha}\varphi[\gamma]=\sup_{\gamma<\alpha}\varphi[\gamma] $$ So we can define $\quad h(\varphi[\gamma])=\sup_{\gamma<\alpha}\varphi[\gamma]$.