# A Question about Proof of Lemma 8.5.14 in Terence Tao Analysis I

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 for all $$x \in Y\backslash \{x_0\}$$.

Note that if $$x \in Y\backslash \{x_0\}$$ then the set $$\{y \in Y :y 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.

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”.

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.)

• Wow... It looks simpler now. Following your suggestion, it really feels like I've created a set with no strict upper bound. I'm a bit less familiar with partial functions, though. Do we also need the axiom of choice to construct partial functions? Commented Sep 11, 2023 at 16:13
• Yes, you still need to use the axiom of choice. Commented Sep 11, 2023 at 17:21

The answer to both of your points is in a sentence near the beginning of 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." So the goal in the rest of the proof will be to produce a contradiction from this supposition. The supposition is used in (among other places) the first of your two bolded sentences; it provides $$s(Y_\infty)$$. The rest of that paragraph produces the desired contradiction, in the sentence before your second bolded one.

Technically, the second bolded sentence could be omitted, because the previous sentence already produces a contradiction and thus proves that the supposition at the beginning was false. The second bolded sentence just emphasizes and summarizes this by explicitly asserting the negation of the original supposition.

• Thank you for your response! However, I have three sentences highlighted in bold, and the first one reads as follows: 'Instead, what we will do is isolate a collection of "partially completed" sets, which we will refer to as 'good sets,' and then take the union of all these good sets to obtain a 'completed' object Y∞ that indeed has no strict upper bound.' I am still unable to locate this part in the actual proof. Commented Sep 11, 2023 at 2:39

Here is slightly different definition for the function $$s$$:

Consider the collection $$\mathcal S$$ of all well-ordered subsets $$Y$$ of $$X$$ which has $$x_0$$ as its minimal element and for which there exist strict upper bounds. Using the axiom of choice select a mapping

$$Y \mapsto s(Y) \quad \forall Y \in \mathcal S$$

Claim: If $$Y$$ is good set with a strict upper bound, then

$$Y^{} = Y \cup \{s(Y)\}$$

is also a good set.

Discussion: The element $$x_0 \in Y^{}$$ is minimal - you just have to check that $$x_0 \le s(Y)$$, but that is obviously true since $$s(Y)$$ is greater than all the elements in $$Y$$.

Similarly, since $$x \le s(Y)$$ for all $$x \in Y$$, and $$Y^{}$$ extends the totally ordered set $$Y$$ by this one element, the set $$Y^{}$$ is also totally ordered.

Given a nonempty subset of $$Y^{}$$, if it is equal to the singleton $$\{s(Y)\}$$ then the minimum would be $$s(Y)$$. Otherwise, we can just intersect the set with $$Y$$ (which is well-ordered) and find the minimum there to get the minimum in $$Y^{}$$ ($$s(Y)$$ plays no role).

Finally, the relation

$$x=s\left(\{y\in Y^{}:y for all $$x \in Y^{}\backslash \{x_0\}$$.

can be handled in like manner as the arguments given above.

Another claim with a similar discussion (or proof if desired) is that any union of good sets is a good set.

If you take the union of all the good sets, call it $$Y_{\infty}$$, then you would be looking at the 'biggest' good set containing all the others, and which, moreover, can't have a strict upper bound. For if it did we can create a still bigger set.

Rather than using the definition good sets, Tao might have called them

$$\quad$$ good sets built from $$s$$