0.2 Orderings, Transfinite Induction and Bourbaki's Fixed Point Theorem

Here, we define orderings (which are types of relations also) and fundamental theorems (Transfinite Induction and Bourbaki's Fixed Point Theorem).

A partial ordering on a nonempty set $X$ is a relation $R$ on $X$ with the following properties. $$\begin{align} \text{Reflexive} &: (x, x) \in R \text{ for all } x\in X \\ \text{Anti-Symmetric} &: \text{if } (x,y) \in R \text{ and } (y, x) \in R, \text{ then } x= y \\ \text{Transitive} &: \text{if } (x,y) \in R \text{ and } (y, z) \in R, \text{ then } (x, z) \in R \end{align}$$ We denote partial orderings by $\leq$, and write $x < y$ to mean that $x \leq y$ but $x \neq y$.

Partial ordering does not guarantee any two elements in set $X$ to be comparable, but linear (or total) ordering does.

A linear (or total) ordering on $X$ is a partial ordering on $X$ such that for any $x, y \in X$, either $(x, y) \in R$ or $(y, x) \in R$.

Two partially ordered sets $X$ and $Y$ are said to be order isomorphic if there is a bijection $f: X \rightarrow Y$ such that $$x_{1} \leq x_{2} \iff f(x_{1}) \leq f(x_{2})$$

If $X$ is partially ordered by $\leq$,

1. A maximal (resp. minimal) element of $X$ is an element $x \in X$ such that the only $y\in X$ satisfying $x \leq y$ (resp. $y \leq x$) is $x$ itself.
2. If $E \subset X$, an upper (resp. lower) bound for $E$ is an element $x \in X$ such that $y \leq x$ (resp. $x \leq y$) for all $y \in E$.

Also,

• If $A \subset X$ is nonempty, then the greatest lower bound of $A$ (if exists) is called infimum; and denoted by $\inf A$
• If $B \subset X$ is nonempty, then the least upper bound of $B$ (if exists) is called supremum; and denoted by $\sup B$

A well ordering $\leq$ on $X$ is a linear ordering on $X$ such that every nonempty subset of $X$ has a $\leq$-minimal element. $X$ is said to be well ordered by $\leq$.

Note that when $X$ is linearly ordered, minimal (or maximal) element of $A \subset X$ is unique if exists and is equal to $\inf A$. We shall discuss about properties of well ordered sets and transfinite induction.

For each $x \in X$, we define the initial segment of $x$ to be $$I_{x} = \left\{ y \in X: y < x \right\}$$ The elements of $I_{x}$ are called predecessors of $x$.

(The principle of Transfinite Induction). Let $X$ be a well ordered set. If $A$ is a subset of $X$ such that $x \in A$ whenever $I_{x} \subset A$, then $A = X$.

Suppose $A \neq X$. $X \setminus A$ is nonempty, we can define $x = \inf (X \setminus A)$. Then $I_{x} \subset A$ but $x \not\in A$; contradiction. Thus $A = X$.

(Bourbaki's Fixed Point Theorem). Let $(X, \leq)$ be a partially ordered set. Assume that every nonempty linearly ordered subset of $X$ has a supremum (least upper bound). Suppose $f: X \rightarrow X$ and $f(x) \geq x$ for all $x \in X$. Then there is some $x^{\ast} \in X$ such that $f(x^{\ast}) = x^{\ast}$.

Fix $a \in X$. A subset $A \subset X$ is admissible if

• $a \in A$
• $x \in A \implies f(x) \in A$
• if $F$ is linearly ordered subset of $X$ and $F \subset A$, then $\sup F \in A$.

Clearly $X$ is admissible. Let $\mathcal{F}$ be collection of all admissible subsets of $X$. Then it is easy to check that $$M = \bigcap \mathcal{F}$$ is also admissible. Thus $M$ is the smallest admissible subset of $X$. Now define $$M' = \left\{ x \in M : a \leq x \right\}$$ It is also easy to check that $M'$ is admissible, so that $M \subset M' \implies M = M'$. Thus $a$ is the minimum element of $M$. Pick $x \in M$ and define $$B_{x} = \left\{ y \in M : y \leq x \text{ or } f(x) \leq y \right\}$$ If $y < x \implies f(y) \leq x$ holds for all $y \in M$, then

• $a \in B_{x}$ since $a \leq x$ for all $x \in M$
• If $y \in B_{x}$, then $y \leq x$ or $f(x) \leq y$. If $f(x) \leq y$, then $f(x) \leq y \leq f(y)$, so $f(y) \in B_{x}$. Or if $y < x$, then by assumption $f(y) \leq x$; $f(y) \in B_{x}$.
• Suppose $F \subset B_{x}$ is linearly ordered. Since $B_{x} \subset M$, $F \subset M$. Above we proved that $M$ is admissible, so $\sup F \in M$. Since $y \leq x$ or $f(x) \leq y$ for all $y \in F$, the "least" upper bound $\sup F$ should satisfy either $\sup F \leq x$ or $f(x) \leq \sup F$. This gives $\sup F \in B_{x}$.

This shows that $B_{x}$ is admissible; which implies $M \subset B_{x} \implies B_{x} = M$. We also define a set $$C = \left\{ t \in M : y < t \implies f(y) \leq t \text{ holds for all } y \in M \right\}$$

• $a \in C$ because the statement $y < a$ for $y \in M$ is false (vacuously true)
• Suppose $t \in C$. If $y < f(t)$ for $y \in M$, then since $B_{t} = M$, we get $y \leq t$. If $y < t$, by assumption $f(y) \leq t$; so that $f(y) \leq t \leq f(t)$. If $y = t$, automatically $f(y) \leq f(t)$. So $f(t) \in C$.
• Suppose $F \subset C$ is linearly ordered. Since $C \subset M$, $F \subset M$. Above we proved that $M$ is admissible, so $b = \sup F \in M$. Suppose $y < b$ for some $y \in M$. If all $t \in F$ satisfy $f(t) \leq y$, then $t \leq y$ for all $t\in F$ so that $y$ is an upper bound of $F$, $y \geq b$ (which is contradiction). So there is $t_{0} \in F$ such that $f(t_{0}) > y$. Since $t_{0} \in C$, $B_{t_{0}} = M$. Now $$y \leq t_{0} \text{ or } f(t_{0}) \leq y$$ The only possibility is $y \leq t_{0}$. Here we divide into two cases. (1) If $y < t_{0}$, then by condition of set $C$, $f(y) \leq t_{0} \leq b$, so that $f(y) \leq b$. (2) If $y = t_{0}$, $b \in B_{y} = M$, which again gives $$b \leq y \text{ or } f(y) \leq b$$ The only possibility is $f(y) \leq b$ (because we already assumed $y < b$). In both cases, $b \in C$.

This means $C \subset M$ is admissible, $C = M$. Combining two facts, we get the following fact. $$\forall x \in M,\ B_{x} = M$$ This implies that for any $x, y \in M$, either $y \leq x$ or $f(x) \leq y$. Since $x \leq f(x)$, the condition simplifies into $y \leq x$ or $x \leq y$; a linear ordering on $M$. Assumption guarantees existence of unique least upper bound $x^{\ast}$ of $M$ in $M$. Admissibility of $M$ implies $f(x^{\ast}) \in M$. Then $x^{\ast} \leq f(x^{\ast}) \leq x^{\ast}$, so that $f(x^{\ast}) = x^{\ast}$.