Lemma 8.5.14. Let X be a partially ordered set with ordering relation $\leq$, and let $x_0$ be an element of $X$. Then there is a well-ordered subset $Y$ of $X$ which has $x_0$ as its minimal element, and which has no strict upper bound.
Proof. The intuition behind this lemma is that one is trying to perform the following algorithm: we initalize $Y:=\{x_0\}$. If $Y$ has no strict upper bound, then we are done; otherwise, we choose a strict upper bound and add it to $Y$ . Then we look again to see if $Y$ has a strict upper bound or not. If not, we are done; otherwise we choose another strict upper bound and add it to $Y$ . We continue this algorithm “infinitely often” until we exhaust all the strict upper bounds; the axiom of choice comes in because infinitely many choices are involved. This is however not a rigorous proof because it is quite difficult to precisely pin down what it means to perform an algorithm “infinitely often”. Instead, what we will do is that we will isolate a collection of “partially completed” sets $Y$, which we shall call good sets, and then take the union of all these good sets to obtain a “completed” object $Y_{\infty}$ which will indeed have no strict upper bound.
We now begin the rigorous proof. Suppose for sake of contradiction that every well-ordered subset $Y$ of $X$ which has $x_0$ as its minimal element has at least one strict upper bound. Using the axiom of choice (in the form of Proposition 8.4.7), we can thus assign a strict upper bound $s(Y)\in X $ to each well-ordered subset $Y$ of $X$ which has $x_0$ as its minimal element.
Let us define a special class of subsets $Y$ of $X$. We say that a subset $Y$ of $X$ is good iff it is well-ordered, contains $x_0$ as its minimal element, and obeys the property that
$x=s\left(\{y\in Y:y<x\}\right)$ for all $x \in Y\backslash \{x_0\}$.
Note that if $x \in Y\backslash \{x_0\}$ then the set $\{y \in Y :y<x\}$ is a subset of $X$ which is well-ordered and contains $x_0$ as its minimal element. Let $\Omega:=\{Y \subseteq X: Y\, \text{is good}\}$ be the collection of all good subsets of $X$. This collection is not empty, since the subset $\{x_0\}$ of $X$ is clearly good (why?).
We make the following important observation: if $Y$ and $Y^\prime$ are two good subsets of $X$, then every element of $Y^{\prime}\backslash Y$ is a strict upper bound for $Y$ , and every element of $Y\backslash Y^{\prime}$ is a strict upper bound for $Y^{\prime}$. In particular, given any two good sets $Y$ and $Y^\prime$, at least one of $Y^{\prime}\backslash Y$ and $Y \backslash Y^{\prime}$ must be empty (since they are both strict upper bounds of each other). In other words, $\Omega$ is totally ordered by set inclusion: given any two good sets $Y$ and $Y^\prime$, either $Y \subseteq Y^\prime$ or $Y^\prime \subseteq Y$.
Let $Y_{\infty}:= \cup \Omega$, i.e., $Y_{\infty}$ is the set of all elements of X which
belong to at least one good subset of X. Clearly $x_0 \in Y_{\infty}$· Also,
since each good subset of X has $x_0$ as its minimal element, the
set $Y_{\infty}$ also has $x_0$ as its minimal element (why?).
Next, we show that $Y_{\infty}$ is totally ordered. Let x, x' be two
elements of $Y_{\infty}$. By definition of $Y_{\infty}$, we know that x lies in some
good set Y and x' lies in some good set Y'. But since $\Omega$ is totally
ordered, one of these good sets contains the other. Thus x, x' are
contained in a single good set (either Y or Y'); since good sets
are totally ordered, we thus see that either x $\leq$ x' or x' $\leq$ x as
desired.
Next, we show that $Y_{\infty}$ is well-ordered. Let A be any nonempty subset of $Y_{\infty}$. Then we can pick an element a $\in$ A, which
then lies in $Y_{\infty}$. Therefore there is a good set Y such that a $\in$ Y.
Then A$\cap$Y is a non-empty subset of Y; since Y is well-ordered,
the set A$\cap$Y thus has a minimal element, call it b. Now recall
that for any other good set Y', every element of Y'\ Y is a strict
upper bound for Y, and in particular is larger than b. Since b is
a minimal element of A$\cap$Y, this implies that b is also a minimal
element of A$\cap$Y' for any good set Y' (why?). Since every element
of A belongs to $Y_{\infty}$ and hence belongs to at least one good set
y', we thus see that b is a minimal element of A. Thus $Y_{\infty}$ is
well-ordered as claimed.
Since $Y_{\infty}$ is well-ordered with $x_0$ as its minimal element, it
has a strict upper bound s($Y_{\infty}$)· But then $Y_{\infty}$ U {s($Y_{\infty}$ )} is wellordered (why? see Exercise 8.5.11) and has $x_0$ as its minimal
element (why?). Thus this set is good, and must therefore be
contained in $Y_{\infty}$. But this is a contradiction since s($Y_{\infty}$) is a
strict upper bound for $Y_{\infty}$. Thus we have constructed a set with
no strict upper bound, as desired.
I think I understand about 90% of this proof. I've highlighted the remaining 10% that I don't quite grasp.
Firstly, Professor Tao mentioned that before starting the rigorous proof, he would show that $Y_{\infty}$ does not have a strict upper bound. However, I couldn't see that part in the actual proof.
Secondly, Professor Tao mentioned at the end of the proof that we have constructed a set. Does that refer to $Y_{\infty}$?
Due to these two points, I was confused. This proof seems like a proof by contradiction which is a non-constructive argument, but why did Professor Tao mention that he would create a set without a strict upper bound at the beginning and end of the proof? And is that $Y_{\infty}$?
Actually, before posting my question here, I reached out to Professor Tao on his blog. He kindly responded, but I must admit that I didn't fully grasp his explanations. I would greatly appreciate it if someone could help me with this.
Best Answer
It’s important to note that Tao’s proof is not remotely constructive and cannot be made constructive. In particular, Tao’s theorem implies Zorn’s Lemma. For suppose we have a POSET $(X, \leq)$ such that all chains (chain = totally ordered subset) have an upper bound. Then let $x_0$ be an upper bound of $\emptyset$. Let $Y \subseteq P$ be a well-ordered subset containing $x_0$ with no strict upper bound. Then $Y$ is a chain. Let $m$ be an upper bound of $Y$. Then $m$ is a maximal element of $X$, since any element strictly exceeding $m$ is a strict upper bound of $Y$.
Tao was presumably using the term “construct” in a different sense than “constructive proof”.