0.7 The Extended Real Number System

We briefly talk about materials in elementary real analysis. We will not prove those properties (see elementary real analysis textbook such as Principles of Mathematical Analysis for reference).

We form the extended real number system by adding two elements $-\infty$ and $\infty$ on $\mathbb{R}$; $$ \bar{\mathbb{R}} = \mathbb{R} \cup \left\{ -\infty, \infty \right\} $$ Also we extend the usual ordering $\leq$ on $\mathbb{R}$ by defining $$ -\infty < x < \infty, (\forall x \in \mathbb{R}) $$

0.6 More about Well Ordered Sets

We discuss more about Well Ordered sets.

If $X$ is well ordered and $A \subset X$, then $\cup_{x \in A} I_{x}$ is either initial segment or $X$ itself.

Let $ J = \cup_{x \in A} I_{x}$. If $J = X$, nothing more to prove. If $J \neq X$, let $b = \inf(X \setminus J)$. If $y < b$ for $y \in X$, by construction, $y \in J$. This means $I_{b} \subset J$. Now pick $y \in J$. Then $y \in I_{x}$ for some $x \in A$. If $y \not\in I_{b}$, then $y \geq b$ gives $b \leq y < x$, in turn $b \in I_{x} \implies b \in J$; contradiction. So $ y \in I_{b}$. Thus, $J = I_{b}$.

This proposition states that any union of initial segments are also an initial segment (including whole set) when the whole set is well ordered.

If $X$ and $Y$ are nonempty and well ordered, then either

1. $X$ is order isomorphic to $Y$
2. $X$ is order isomorphic to an initial segment of $Y$
3. $Y$ is order isomorphic to an initial segment of $X$

Consider the collection $\mathcal{F}$ of order isomorphisms whose domains are initial segments of $X$ or $X$ itself and whose ranges are initial segments of $Y$ or $Y$ itself. $\mathcal{F}$ is nonempty since $f: \left\{ \inf X \right\} \rightarrow \left\{ \inf Y \right\}$ is a memeber of $\mathcal{F}$. Also $\mathcal{F}$ is partially ordered by set inclusion if functions are viewed as subsets of $X \times Y$. By similar reasoning used in Section 0.4, Proposition 1-2, if $S$ is nonempty linearly ordered subset of $\mathcal{F}$, then $$ f^{\ast} = \bigcup_{f \in S} f $$ is well defined function and upper bound of $S$. By Zorn's Lemma, $\mathcal{F}$ has a maximal element; say $g$ with domain $A$ and range $B$. If $A = I_{x}$ and $B = I_{y}$ for some $x \in X$ and $y \in Y$, then we can extend $g$ by $$ \bar{g}: A \cup \left\{ x \right\} \rightarrow Y,\ \bar{g}(a) = \begin{cases} g(a) & (a \in A) \\ y & (a = x) \end{cases} $$ because $I_{x} \cup \left\{ x \right\}$, $ I_{y} \cup \left\{ y \right\}$ are again initial segments (including whole set $X$ or $Y$). This contradicts to maximality of $g$. Hence either $A = X$ or $B = Y$, and the result follows.

Well Ordering principle gives us the way to construct weird uncountable sets.

There is an uncountable well ordered set $\Omega$ such that $I_{x}$ is countable for every $x \in \Omega$. If $\Omega'$ is another set with the same properties, then $\Omega$ and $\Omega'$ are order isomorphic.

First by well ordering principle, uncountable well ordered set $\Omega_{0}$ exists. Then define $$ A = \left\{ t \in \Omega_{0}: I_{t} \text{ is uncountable } \right\} $$ If $\Omega_{0}$ satisfies the desired property, then nothing more to prove. If not, $A$ has minimal element $a$ by well ordering principle. Then the set $\Omega = I_{a}$ would be the desired set, because for any $x \in \Omega$, $x \not\in A$, so that $I_{x}$ is countable. Any other $\Omega'$ satisfying this property is order isomorphic to $\Omega$ itself, because any initial segments of $\Omega$ and $\Omega'$ are countable. (See Proposition 2).

Every nonempty countable subset of $\Omega$ has an upper bound.

Let $A \subset \Omega$ be countable and nonempty. $\cup_{x \in A} I_{x}$ is countable union of countable sets, so it is countable. By Proposition 1, it should be equal to $I_{y}$ for some $y \in \Omega$. Then for any $a \in A$, $$ I_{a} \subset I_{y} \implies a \leq y $$ which is equivalent to saying $y$ is an upper bound of $A$.

The set $\Omega$ is called a set of countable ordinals. We usually define $\Omega^{\ast} = \Omega \cup \left\{ \omega_{1} \right\}$ and extend the well ordering by declaring $$ x < \omega_{1},\ (\forall x \in \Omega) $$ $\omega_{1}$ is called the first uncountable ordinal. We won't get further deep into theory of ordinals.

0.5 Countable Sets and Set of Real Numbers

We begin by defining countable sets.

A set $X$ is countable if $|X| \leq |\mathbb{N}|$. For finite sets, we denote $$ |X| = n \iff |X| = |\left\{ 1, 2, ..., n \right\}|$$

Since $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|$ by this theorem, power set of natural numbers is uncountable.

1. Finite product of countable sets are countable.
2. Countable union of countable sets is countable.
3. If $X$ is countably infinite, then $|X| = |\mathbb{N}|$.

1. It is sufficient to show that $\mathbb{N} \times \mathbb{N}$ is countable. Define a function $$ h: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N},\ h(n, m) = \frac{(n+m)(n+m-1)}{2} + 1- n $$ This is clearly injection (check it!). So $\mathbb{N} \times \mathbb{N}$ is countable. Using induction, we can deduce that finite product of countable sets are countable.
2. Let $\left\{ X_{\alpha} \right\}_{\alpha \in A}$ be countable collection of countable sets. First for each $X_{\alpha}$, there exist surjection $$ g_{\alpha}: \mathbb{N} \rightarrow X_{\alpha}$$ Also there exist surjection $$ f: \mathbb{N} \rightarrow A$$ Define $$ h: \mathbb{N} \times \mathbb{N} \rightarrow \bigcup_{\alpha \in A} X_{\alpha},\ h(n, m) = g_{f(n)}(m) $$ then $h$ is surjection. This implies that $\cup_{\alpha} X_{\alpha}$ is countable.
3. It is sufficient to show that there exist injection from $\mathbb{N}$ to $X$. First, well order $X$ by some relation $\leq$. Then define $$ f: \mathbb{N} \rightarrow X,\ f(n) =\begin{cases} \leq\text{-smallest element on }X & (n = 1) \\ \leq\text{-smallest element on }X\setminus \left\{ f(1), f(2), ..., f(n-1) \right\} & (n > 1) \end{cases} $$ Clearly $f$ is injection. By Schröoder-Bernstein theorem, $|X| = |\mathbb{N}|$.

$\mathbb{Z}$ and $\mathbb{Q}$ are countable.

Since $\mathbb{Z}$ is union of countable sets; namely $\mathbb{N} \cup \left\{ -n: n \in \mathbb{N} \right\} \cup \left\{ 0 \right\}$, it is countable. The function $$ f: \mathbb{Z} \times \mathbb{Z}\setminus \left\{ 0 \right\} \rightarrow \mathbb{Q},\ f(p,q) = \frac{p}{q} $$ is surjection; so $\mathbb{Q}$ is countable.

Now we come to set of real numbers, $\mathbb{R}$.

A set $X$ is said to have the cardinality of the continuum if $|X| = |\mathbb{R}|$. We denote $|\mathbb{R}| = \mathfrak{c} $.

A nice proposition shows that power set of natural numbers has cardinality of continuum.

$|\mathcal{P}(\mathbb{N})| = \mathfrak{c}$.

Define a function $$ f: \mathcal{P}(\mathbb{N}) \rightarrow \mathbb{R},\ f(A) = \begin{cases} 2 & (\text{if } A = \emptyset) \\ 1 + \sum_{n \in A} 2^{-n} & (\text{if }A\text{ is finite})\\ \sum_{n = 1}^{\infty} \chi_{A}(n) 2^{-n} & (\text{if }A\text{ is infinite}) \end{cases}$$ where $\chi_{A}(x) = 1$ if $x \in A$ and $0$ otherwise. Now suppose $f(A) = f(B)$. Since finite sets have function value strictly larger than infinite sets, both are finite or both are infinite. Define $\alpha$ and $\beta$ be least elements on infinite sets $A$ and $B$ respectively. Then, $$ f(A) = 2^{-\alpha} + \Sigma^{A} = 2^{-\beta} + \Sigma^{B} = f(B) $$ for some $\Sigma^{A}$, $\Sigma^{B} > 0$. Then $$ 2^{-\alpha} < f(A) = 2^{-\beta} + \Sigma^{B} \leq 2^{-\beta} + 2^{-\beta} = 2^{-\beta + 1} $$ and $$ 2^{-\beta} < f(B) = 2^{-\alpha} + \Sigma^{A} \leq 2^{-\alpha + 1}$$ Combining both equations give $\alpha > \beta - 1$ and $\beta > \alpha - 1$, which in turn $ \beta - 1 < \alpha < \beta + 1 \implies \alpha = \beta$. Now using transfinite induction, $A = B$. For finite sets, exactly same reasoning (as in the case of infinite sets) can be applied. So $f$ is injection.

Every real number $x \in (0, 1)$ has a unique base-2 decimal expansion $x = \sum_{n = 1}^{\infty} x_{n}2^{-n}$ (not including the repeated 1's on the end). Define a function $$ g: \mathcal{P}(\mathbb{N}) \rightarrow \mathbb{R}^{\leq 0},\ g(A)= \begin{cases} \ln \left( \sum_{n=1}^{\infty} \chi_{A}(n) 2^{-n} \right) & (A \neq \emptyset) \\ -1 & (A = \emptyset) \end{cases} $$ This is clearly surjection. Composition with surjective function $$h:\mathbb{R}^{\leq 0} \rightarrow \mathbb{R},\ h(x) = \begin{cases} \ln(-x) &( x \neq 0) \\ 1 & (x = 0) \end{cases}$$ $h \circ g$ is surjection. By the Schröder-Bernstein theorem, $|\mathcal{P}(\mathbb{N})| = \mathfrak{c}$.

There is a proposition for $\mathfrak{c}$ analogous to countable sets.

1. If $|X| \leq \mathfrak{c}$ and $|Y| \leq \mathfrak{c}$, then $|X \times Y| \leq \mathfrak{c}$.
2. If $|A| \leq \mathfrak{c}$ and $|X_{a}| \leq \mathfrak{c}$ for all $a \in A$, then $|\cup_{a \in A} X_{a}| \leq \mathfrak{c}$.

1. It is sufficient to check for $X = Y = \mathcal{P}(\mathbb{N})$. First define $\phi, \psi: \mathbb{N} \rightarrow \mathbb{N}$ by $\phi(n) = 2n$ and $\psi(n) =2n-1$ (both are bijections). Now define a map $$ f: \mathcal{P}(\mathbb{N}) \times \mathcal{P}(\mathbb{N}) \rightarrow \mathcal{P}(\mathbb{N}),\ f(A, B) = \phi(A) \cup \psi(B) $$ This is clearly bijection because every nonempty subset of natural numbers can be partitioned into set of even numbers and set of odd numbers. So $|\mathcal{P}(\mathbb{N}) \times \mathcal{P}(\mathbb{N})| \leq \mathfrak{c}$.
2. Let $f: A \rightarrow \mathbb{R}$, $g_{\alpha}: X_{\alpha} \rightarrow \mathbb{R}$ ($\alpha \in A$) injections. Then $$ h: \mathbb{R} \times \mathbb{R} \rightarrow \bigcup_{\alpha \in A} X_{\alpha},\ h(x, y) = g_{f(x)}(y) $$ is surjection. Since $|\mathbb{R} \times \mathbb{R}| \leq \mathfrak{c}$, so does $\cup_{a \in A} X_{a}$.

0.4 Cardinality of Sets, Schröder-Bernstein's Theorem

Now we move on to cardinality of sets.

If $X$ and $Y$ are nonempty sets, we define the expressions

1. $\left| X \right| \leq \left| Y \right|$ if there exist injection from $X$ to $Y$.
2. $\left| X \right| = \left| Y \right|$ if there exist bijection from $X$ to $Y$.
3. $\left| X \right| \geq \left| Y \right|$ if there exist surjection from $X$ to $Y$.

Note that cardinality is defined in relative sense.

Let $X$ and $Y$ be sets.

1. $\left| X \right| \leq \left| Y \right| \iff \left| Y \right| \geq \left| X \right|$
2. Either $\left| X \right| \leq \left| Y \right|$ or $\left| Y \right| \leq \left| X \right|$.

1. Suppose $|X| \leq |Y|$. Then there exist an injection $f: X \rightarrow Y$. Pick any $x_{0} \in X$. Define $g: Y \rightarrow X$ as follows. $$ g(y) = \begin{cases} f^{-1}(y) & (\text{if } y \in f(X)) \\ x_{0} & (\text{otherwise}) \end{cases} $$ $g$ is well defined for $y \in f(X)$ since $f$ is injective. It is evident that $g$ is surjective. So $|Y| \geq |X|$.
   Conversely, suppose $|Y| \geq |X|$. Then there exist a surjection $g: Y \rightarrow X$. For any $x \in X$, $g^{-1}(x)$ is nonempty subset of $X$. So using axiom of choice, $$ \prod_{x \in X} g^{-1}(x) $$ is nonempty. Any function $f: X \rightarrow Y$ in $\prod_{x \in X} g^{-1}(x)$ would be injection. This gives $|X| \leq |Y|$.
2. Let $\mathcal{J}$ be a collection of injections from subsets of $X$ to $Y$. Memebers of $\mathcal{J}$ can be considered as subsets of $X \times Y$, so $\mathcal{J}$ is partially ordered by set inclusion $\subset$. Let $S$ be a linearly ordered subset of $\mathcal{J}$. Then consider $$ f^{\ast} = \bigcup_{f \in S} f $$ By linear ordering of $S$, if a function $f \in S$ has element $(x, y) \in f$, then so does any function in $S$ which has $x$ in its domain. So $f^{\ast}$ is well defined function. Also for if $f^{\ast}(s) = f^{\ast}(t)$, then $f^{\ast}(s) = f_{1}(s)$ for some $f_{1} \in S$ such that $s \in dom(f_{1})$, $f^{\ast}(t) = f_{2}(t)$ for some $f_{2} \in S$ such that $t \in dom(f_{2})$. Either $f_{1} \subset f_{2}$ or $f_{2} \subset f_{1}$, it is clear that $s = t$; $f^{\ast}$ is indeed injection.
   
   It is clear that $f^{\ast}$ is an upper bound of $S$. By Zorn's Lemma, there exist a maximal element of $\mathcal{J}$; namely $\bar{f}$ with domain $A$ and range $B$. If $x_{0} \in X \setminus A$ and $y_{0} \in Y \setminus B$, we can extend $\bar{f}$ by setting $\bar{f}(x_{0}) = y_{0}$, contradicting maximality. Hence either $A = X$, in which case $|X| \leq |Y|$, or $B = Y$, in which case $|Y| \leq |X|$.

Now comes the most important theorem.

(Schröder-Bernstein's Theorem). If $|X| \leq |Y|$ and $|Y| \leq |X|$, then $|X| = |Y|$.

Let $f: X \rightarrow Y$ and $g:Y \rightarrow X$ be injections. Given $x \in X$, we construct a sequence $$ x \rightarrow g^{-1}(x) \rightarrow (f^{-1} \circ g^{-1})(x) \rightarrow (g^{-1} \circ f^{-1} \circ g^{-1})(x) \rightarrow ... $$ until each terms exist. Then we can distinguish such $x$, by four types.

1. The sequence repeats (or has a loop).
2. The sequence goes indefinitely without repeating.
3. The sequence stops in finite number of steps, in set $X$.
4. The sequence stops in finite number of steps, in set $Y$.

We define a new function $h: X \rightarrow Y$ as follows. $$ h(x) = \begin{cases} f(x) & (\text{if }x\text{ is type 1, 2, and 3}) \\ g^{-1}(x) & (\text{if }x\text{ is type 4}) \end{cases}$$ For all $x \in X$, $x$ and $h(x)$ are always in same sequence regardless of the type of $x$. For if $h(a) = h(b)$ and $a$ is in type 1, 2, or 3, then $h(a) = f(a) = h(b) = f(b)$, so that $a = b$ because $f$ is injection. For if $h(a) = h(b)$ and $a$ is in type 4, then $h(a) = g^{-1}(a) = h(b) = g^{-1}(b)$, which implies $a = b$. So $h$ is injective.

Now pick $y \in Y$. Every $y$ is in some sequence of $x$, because there should exist $x \in X$ such that $g(y) = x$. If $y$ is in type 1, 2, or 3, then there exist some $x \in X$ such that $h(x) = f(x) = y$. If $y$ is in type 4, there exist $x \in X$ such that $x = g(y)$. Now $x$ and $y$ are in same sequence, so $h(x) = g^{-1}(x) = y$. This means $h$ is surjective. Combining the facts, $h$ is bijection; $|X| = |Y|$.

Together with Proposition 1, Schröder-Bernsten's Theorem makes $\leq$ on cardinality of sets to behave like a linear ordering. (Transitivity is almost trivial, since composition of two injections are still injection)

Lastly we introduce famous theorem, which states that every set has strictly smaller cardinality than its power set. This arise concept of countability (which we will discuss next).

For any set $X$, $|X| < |\mathcal{P}(X)|$.

It is clear that $|X| \leq |\mathcal{P}(X)|$, since $x \longmapsto \left\{ x \right\}$ is injection. Define $$ A = \left\{ x \in X: x \not\in g(x) \right\}$$ If $g: X \rightarrow \mathcal{P}(X)$ is surjection, then there exist $x_{0} \in X$ such that $g(x_{0}) = A$. But \begin{align} x_{0} \in A &\iff x_{0} \not\in g(x_{0}) \\ &\iff x_{0} \not\in A \end{align} which is contradiction. So there is no surjection from a set to its power set. This gives $|X| < |\mathcal{P}(X)|$.

0.3 Axiom of Choice and Equivalents (Zorn's lemma, Hausdorff's maximal principle, Well ordering and Tukey's Lemma)

Now we discuss fundamental axiom of set theory - Axiom of Choice.

The following are equivalent.

1. (The Hausdorff Maximal Principle). Every partially ordered set has a maximal linearly ordered subset.
2. (Zorn's Lemma). If $X$ is partially ordered set and every linearly ordered subset of $X$ has an upper bound, then $X$ has a maximal element.
3. (Well Ordering Principle). Every nonempty set $X$ can be well ordered.
4. (Axiom of Choice). If $\left\{ X_{a} \right\}_{a \in A}$ is nonempty collection of nonempty sets, then $\prod_{a \in A} X_{a}$ is nonempty.
5. (Tukey's Lemma). Every nonempty collection of finite character partially ordered by set inclusion has a maximal element.

We will prove the equivalence by showing $$ (1) \implies (2) \implies (3) \implies (4) \implies (2) \implies (5) \implies (1) $$ $(\textbf{1} \implies \textbf{2})$ Let $(X, \leq)$ be partially ordered set with the following property. $$ \text{"every linearly ordered subset of }X\text{ has an upper bound"} $$ Then by $1$, there exist maximal linearly ordered subset; namely $S$. Let $m$ be an upper bound of $S$. If there exists an element $x \in X$ such that $m < x$, then $S \cup \left\{ x \right\}$ is also linearly ordered subset of $X$, contradicting to the maximality of $S$. So $m$ is the maximal element of $X$.

$(\textbf{2} \implies \textbf{3})$ Let $\mathcal{W}$ be the collection of well orderings of subsets of $X$. We define a partial ordering $\lesssim$ on $\mathcal{W}$ as follows. If $\leq_{1}$ and $\leq_{2}$ are well orderings on the subsets $E_{1}$, $E_{2}$ of $X$, then $$ (\leq_{1})\ \lesssim\ (\leq_{2}) \iff \begin{cases} E_{1} \subset E_{2},\ \leq_{1}\text{ and }\leq_{2}\text{ agrees on }E_{1} \\ \text{for all } x \in E_{2} \setminus E_{1}, y \leq x\text{ for all } y \in E_{1} \end{cases} $$ Let $S = \left\{ \leq_{\alpha} \right\}_{\alpha \in \Lambda}$ be linearly ordered subset of $\mathcal{W}$, with well ordering $\leq_{\alpha}$ defined on $E_{\alpha} \subset X$.

$\leq^{\ast} = \cup_{\alpha} \leq_{\alpha}$ is a well ordering on $\cup_{\alpha} E_{\alpha}$.

Pick $x, y \in \cup_{\alpha} E_{\alpha}$. Define $$ I = \left\{ E_{\alpha}: \alpha \in \Lambda,\ \left\{ x, y\right\}\subset E_{\alpha} \right\} $$ and $E = \cap I$.

• If $E$ is nonempty, pick $E_{\alpha}, E_{\beta} \in I$. By linear ordering of $S$, either $(\leq_{\alpha})\ \lesssim\ (\leq_{\beta})$ or vice versa. Either case, $$ x \leq_{\alpha} y \iff x \leq_{\beta} y $$ or $$ y \leq_{\alpha} x \iff y \leq_{\beta} x $$ so $\leq^{\ast}$ is well defined.
• If $E$ is empty, $x \in E_{\alpha}$, $y \in E_{\beta}$ for $\alpha \neq \beta$. But then by linear ordering of $S$, either $(\leq_{\alpha})\ \lesssim\ (\leq_{\beta})$ or vice versa, which induces inclusion relation between $E_{\alpha}$ and $E_{\beta}$. This implies either one of them includes both elements $x$ and $y$; contradiction.

Now suppose $M$ is nonempty subset of $\cup_{\alpha} E_{\alpha}$ such that has no least element. Then there exist a sequence $\left\{ x_{n} \right\} \subset X$ such that $$ x_{1} {}^{\ast}> x_{2} {}^{\ast}> ... {}^{\ast}> x_{n} {}^{\ast}> x_{n+1}... $$ Now suppose $x_{1} \in E_{\alpha_{1}}$. Then we can deduce that all elements are in $E_{\alpha_{1}}$, which then ${}^{\ast}>$ reduces to $>_{\alpha_{1}}$. Since $>_{\alpha_{1}}$, it has least element, which is contradiction. So $\leq^{\ast}$ is a well ordering on $\cup_{\alpha} E_{\alpha}$.

Now back to the original proof, pick any $E_{\beta}$ and $\leq_{\beta}$ where $\beta \in \Lambda$. Clearly by definition $E_{\beta} \subset \cup_{\alpha}E_{\alpha}$ and $\leq^{\ast}$ agrees with $\leq_{\beta}$ on $E_{\beta}$. Next for $x \in \cup_{\alpha}E_{\alpha} \setminus E_{\beta}$, there exist $\gamma$ such that $x \in E_{\gamma} \setminus E_{\beta}$. By linear ordering of $S$, the only possibility is $E_{\beta} \subset E_{\gamma}$, so that $y \leq_{\gamma} x $; which in turn $y \leq^{\ast} x$ for all $y \in E_{\beta}$. This asserts that $S$ is bounded above by $\leq^{\ast}$. By Zorn's Lemma, $\mathcal{W}$ has maximal element $\leq$. If $\leq$ is well ordering on some proper subset $T$ of $X$, we can add single element $x_{0} \in X \setminus T$ and define $\leq'$ on $T \cup \left\{ x_{0} \right\}$ by $\leq'$ agrees with $\leq$ on $T$ and $t \leq' x_{0}$ for all $t \in T$. This shows the only possibility of $\leq$ is well ordering on $X$ (whole set).

$(\textbf{3} \implies \textbf{4})$ Let $X = \cup_{\alpha \in A} X_{\alpha}$, and pick a well ordering on $X$. For each $\alpha$, define $f(\alpha)$ to be a minimal element of $X_{\alpha}$. Then $f \in \prod_{\alpha \in A} X_{\alpha}$.

$(\textbf{4} \implies \textbf{2})$ Let $(X, \leq)$ be a nonempty partially ordered set with property that every linearly ordered subset has an upper bound. For each $x \in X$, define $$ S_{x} = \begin{cases} \left\{ y \in X: y > x \right\} & (\text{if } x \text{ is not maximal element of } X) \\ \left\{ x \right\} & (\text{if } x \text{ is maximal element of }X) \end{cases} $$ Then by axiom of choice, $\prod_{x \in X} S_{x}$ is not empty. So we've constructed a function $f \in \prod_{x \in X} S_{x}$ such that $$ f: X \rightarrow X,\ x \leq f(x)\ (\forall x \in X) $$ Now by Bourbaki's Fixed Point Theorem, there exist $x^{\ast} \in X$ such that $f(x^{\ast}) = x^{\ast}$. By definition of $S_{x^{\ast}}$, automatically $x^{\ast}$ is the maximal element of $X$ and Zorn's Lemma follows.

$(\textbf{2} \implies \textbf{5})$ Let $\mathcal{F}$ be collection of sets that is of finite character. $\subseteq$ is a natural partial ordering on $\mathcal{F}$. Let $\mathcal{C}$ be nonempty linearly ordered subset of $\mathcal{F}$.

$\bigcup \mathcal{C} \in \mathcal{F} $.

Let $M = \left\{ m_{1}, ..., m_{n} \right\} $ be a finite subset of $\cup \mathcal{C}$. Then there exist $C_{i} \in \mathcal{C}$ for each $i = 1, 2, ..., n$ such that $m_{i} \in C_{i}$. Since $\mathcal{C}$ is linearly ordered, there is a set $C_{j}$ among $C_{i}$s' such that $C_{j} \supset C_{i}$ for all $i$, so that $$ M \subset C_{j} $$ Thus $M \in \mathcal{F}$ as $C_{j} \in \mathcal{F}$ and $\mathcal{F}$ is finite character. It follows that $\cup \mathcal{C} \in \mathcal{F}$.

Back to original proof, it is clear that $\cup \mathcal{C}$ is an upper bound for $\mathcal{C}$. By Zorn's Lemma, there is a maximal element of $\mathcal{F}$; which is exactly what Tukey's Lemma states.

$(\textbf{5} \implies \textbf{1})$ Let $(X, \leq)$ be a partially ordered set. Define $\mathcal{L}$ to be collection of all linearly ordered subsets of $X$.
$(\implies)$ Pick $L \in \mathcal{L}$. Any finite subset of $L$ is also linearly ordered (trivial). So any finite subset of $L$ is in $\mathcal{L}$.
$(\impliedby)$ Suppose all finite subsets of $A \subset X$ are members of $\mathcal{L}$. Then for any finite subsets of $A$ of the form $\left\{ x,y \right\}$ satisfy either $x \leq y$ or $y \leq x$. The union over all such two elements subsets, form $A$; which then makes $A$ linearly ordered. So $A \in \mathcal{L}$.
This shows $\mathcal{L}$ is of finite character, and by Tukey's Lemma there exist maximal element (which is maximal linearly ordered subset of $X$). Hausdorff's Maximal Principle directly follows.

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}$.

0.1 The Language of Set Theory

It is assumed that the reader is familiar with the basic concepts of set theory; the following discussion is meant mainly to fix our terminology.
Our notation for the fundamental number systems is as follows.

\begin{align} \mathbb{N} &= \text{the set of positive integers not including zero} \\ \mathbb{Z} &= \text{the set of integers} \\ \mathbb{Q} &= \text{the set of rational numbers} \\ \mathbb{R} &= \text{the set of real numbers} \\ \mathbb{C} &= \text{the set of complex numbers} \end{align}

Our notation for set logic is as follows.

\begin{align} \emptyset &= \text{the empty set} \\ \mathcal{P}(X) &= \text{the power set of set } X \end{align} Given collection of sets $\mathcal{E}$, we have \begin{align} \bigcup_{E \in \mathcal{E}} E &= \left\{ x: x \in E \text{ for some } E \in \mathcal{E} \right\} \\ \bigcap_{E \in \mathcal{E}} E &= \left\{ x: x \in E \text{ for all } E \in \mathcal{E} \right\} \end{align} Given indexed family of sets $\left\{ X_{a} \right\}_{a \in A}$, we have \begin{align} \bigcup_{a \in A} X_{a} &= \left\{ x: x \in X_{a} \text{ for some } a \in A \right\} \\ \bigcap_{a \in A} X_{a} &= \left\{ x: x \in X_{a} \text{ for all } a \in A \right\} \end{align} A family of sets $\mathcal{E} = \left\{ E_{a} \right\}_{a \in A}$ is called disjoint if $E_{a} \cap E_{b} = \emptyset$ whenever $a \neq b$.

When the index set is $\mathbb{N}$, then we just denote $\left\{ E_{n} \right\}_{n \in \mathbb{N}}$ as $\left\{ E_{n} \right\}_{1}^{\infty}$. In this situation, we define \begin{align} \limsup E_{n} &= \cap_{n=1}^{\infty} \cup_{i=n}^{\infty} E_{n} \\ \liminf E_{n} &= \cup_{n=1}^{\infty} \cap_{i=n}^{\infty} E_{n} \end{align} If $E$ and $F$ are sets, we denote their difference by $E \setminus F$: $$ E \setminus F = \left\{ x: x \in E \text{ and } x \not\in F \right\} $$ and their symmetric difference $$ E \triangle F = (E \setminus F) \cup (F \setminus E) $$ When $E$ is subset of some universal set $X$, we denote $$ E^{c} = X \setminus E $$ In this situation we have deMorgan's Laws: \begin{align} \left( \bigcup_{a \in A} E_{a} \right)^{c} &= \bigcap_{a \in A} E_{a}^{c} \\ \left( \bigcap_{a \in A} E_{a} \right)^{c} &= \bigcup_{a \in A} E_{a}^{c} \end{align}

Our notation for relations and functions is as follows.

If $X$ and $Y$ are sets, we denote their Cartesian product $$ X \times Y = \left\{ (x, y): x \in X \text{ and } y \in Y \right\} $$ A relation from $X$ to $Y$ is a subset $R$ of $X \times Y$. If $X = Y$, then we just call it relation on $X$. Important relations are follows.

An equivalence relation on $X$ is a relation $R$ on $X$ having following properties. \begin{align} \text{Reflexive} &: (x, x) \in R \text{ for all } x \in X \\ \text{Symmetric} &: \text{if } (x,y) \in R, \text{ then } (y, x) \in R \\ \text{Transitive} &: \text{if } (x,y) \in R \text{ and } (y, z) \in R, \text{ then } (x, z) \in R \end{align}

A function $f: X \rightarrow Y$ is a relation $R$ from $X$ to $Y$ with the property that for every $x \in X$, there is a unique $y \in Y$ such that $(x, y) \in R$, in which case we write $f(x) = y$.

If $f: X \rightarrow Y$ and $g: Y \rightarrow Z$ are mappings, we define function composition $$ g \circ f: X \rightarrow Z,\ (g \circ f)(x) = g(f(x)) $$

For $f: X \rightarrow Y$, $D \subset X$ and $E \subset Y$, we denote \begin{align} f(D) &= \left\{ y \in Y: f(x) = y \text{ for some } x \in D \right\} \text{ (image of } D)\\ f^{-1}(E) &= \left\{ x \in X: f(x) \in E \right\} \text{ (inverse image of } E) \end{align} Now, for the inverse image, following holds. For $\left\{ E_{a} \right\}_{a \in A} $ where $E_{a} \subset Y$, \begin{align} f^{-1} \left( \bigcup_{a \in A} E_{a} \right) &= \bigcup_{a \in A} f^{-1}(E_{a}) \\ f^{-1} \left( \bigcap_{a \in A} E_{a} \right) &= \bigcap_{a \in A} f^{-1}(E_{a}) \\ \end{align}

For types of functions,

$f: X \rightarrow Y$ is said to be \begin{align} \text{injective} &: f(x_{1}) = f(x_{2}) \text{ only when } x_{1} = x_{2} \\ \text{surjective} &: f(X) = Y \\ \text{bijective} &: \text{ injective and surjective } \end{align}

Lastly cartesian product for infinite index set.

For indexed family of set $\left\{ E_{a} \right\}_{a \in A}$ $$ \prod_{a \in A} E_{a} $$ is the set of functions $f: A \rightarrow \cup_{a \in A} E_{a}$ which satisfies $f(a) \in E_{a}$. If $A = \mathbb{N}$, then we call these functions as sequences.