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.
I think the reason for your confusion is that there are two arguments here: an informal argument and a formal argument. Informally, as Tao states at the beginning, there is an easy way to construct a well-ordered set $Y$ with $x_0$ as minimal element and no strict upper bound, which is just to start with $Y:=\{x_0\}$ and to keep adding strict upper bounds for $Y$ to $Y$. Formally, though, Tao makes a proof by contradiction involving the set $Y_\infty$. But the idea of the informal argument has leaked into the formal proof, which is based on it. This is why Tao says "Thus we have constructed a set with no strict upper bound, as desired." Formally, we have not; we have only arrived at a contradiction involving $Y_\infty$ ($s(Y_\infty)$ is in a good set which is contained in $Y_\infty$, but also exceeds all elements of $Y_\infty$.) However, the formal proof could easily be made more constructive, as I will explain in the next paragraph, in such a way that $Y_\infty$ does become the set we want.
Without any assumptions, we can still define a partial function $s$ which will take any well-ordered subset $Y$ of $X$ with $x_0$ as minimal element to a strict upper bound of $Y$, if such a bound exists; otherwise $s(Y)$ will not exist. Then, we can go through most of Tao's proof just as before, defining good sets and constructing $Y_\infty$ in the same way. If $s(Y_\infty)$ exists, we arrive at a contradiction, again just as before. But the conclusion is now that $s(Y_\infty)$ cannot exist, and so $Y_\infty$ is a well-ordered subset of $X$ with $x_0$ as minimal element and no strict upper bound.
There is a slight omission in the version of the proof you give, which has been corrected (see Tao's blog, erratum for p. 205 in the corrected third edition.)