# Bourbaki-Witt to Tarski-Knaster Fixed Point Theorem

I was looking at the Bourbaki-Witt Fixed Point Theorem which states that

If $X$ is a non-empty, chain complete poset and $f: X \to X$ s.t. $f(x) \geq x$ for all $x$, then $f$ has a fixed point.

I was wondering if one could modify the proof of this theorem to prove a version of the Tarski-Knaster Fixed point theorem. Suppose also that $X$ has a minimum element $a$ and every subset of $X$ has a supremum. Let $f: X \to X$ be a monotone function i.e. $x \leq y \implies f(x) \leq f(y)$. Then $f$ must have a fixed point.

Proof: Define the functional:

\begin{align} g(0) &= a \\ g(\alpha^+) &= f(g(\alpha)) \\ g(\lambda) &= \text{sup}\{g(\alpha) : \alpha < \lambda\} \end{align}

where $\lambda$ is a limit ordinal. If there is no ordinal $\alpha$ s.t. $g(\alpha) = g(\alpha^+)$ (which would be a fixed point), then $g$ must be a monotonically increasing function and is thus an injection from the ordinals into $X$ which is a contradiction.

The reasoning seems a little dubious to me so I would appreciate any thoughts!

Edit:

We can see $g$ is weakly increasing by noting that, since $g(0)$ is the minimum element, we have $g(0) \leq g(1)$. Then by monotonicity of $f$, we have $g(1) = f(g(0)) \leq f(g(1)) = g(2)$ and so on. This notion could be formalized via induction.

• It may be because it's early in the morning, but is it obvious (or even true) that $g(\alpha^+) \geq g(\alpha)$? – Patrick Stevens Sep 5 '17 at 8:46
• @PatrickStevens You ask a good question. My reasoning might be flawed but I added a hand wavy explanation to the end of the question. – gowrath Sep 5 '17 at 8:54
• Applications: (1). (ZF). For every $y\in On$ there exists an infinite cardinal ordinal $x>y$ such that $x$ is the $x$th cardinal.(I.e. $x$ is a fixed point of the Aleph function.)... (2). (ZFC). For every $y\in On$ there exists an infinite cardinal ordinal $x>y$ where $x$ is the $x$th strong limit cardinal ( A strong limit means $\forall z<x\;(2^z<x)$....) – DanielWainfleet Sep 5 '17 at 16:34
• Using $\alpha^+$ to denote anything other than the successor cardinal... is just bad. – Asaf Karagila Sep 5 '17 at 20:35
• Yes, this is common in very basic set theory books, but it is completely against the standard notation of advanced books, and research level set theory. – Asaf Karagila Sep 6 '17 at 4:56

Yes, this proof works. When $\lambda$ is a limit ordinal, you can prove $g(\lambda)\leq g(\lambda^+)$ as follows. For any $\alpha<\lambda$, $g(\alpha)\leq g(\lambda)$ and hence $g(\alpha)\leq g(\alpha^+)=f(g(\alpha))\leq f(g(\lambda))=g(\lambda^+)$. Since $g(\lambda)$ is the least upper bound of all these $g(\alpha)$, we must have $g(\alpha)\leq g(\lambda^+)$.