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

Can anyone help me to understand "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}$. "

• Also, have you tried looking at the solution to Exercise 8.5.13, which is quoted as being related? If so, what about that did you not understand? – lioness99a Jul 17 '17 at 11:50
• Thanks for your comments @lioness99a, when I found the image is not displayed correctly I retyped my question. – bin Jul 17 '17 at 12:01
• @lioness99a Yes, I tried to understand the Exercise 8.5.13, my understanding was that it proves that claim by proof either $Y\subseteq Y^\prime$ or $Y^\prime \subseteq Y$ is true. But e.g. if $Y\subseteq Y^\prime$, then $Y\backslash Y^\prime$ is empty, thus each element of $Y\backslash Y^\prime$ is not a strict upper bound for $Y^\prime$ – bin Jul 17 '17 at 12:09
• But the statement is still true: Every element in $Y\setminus Y'$ is an upper bound of $Y'$. This is now an empty assertion and therefore trivially holds. – math635 Jul 17 '17 at 12:14
• Thank @math635 for your answer! Another question: my understanding is that the good subset property of $Y$, $x=s\left(\{y\in Y : y<x\}\right)$ for all $x \in Y \backslash \{x_0\}$ is to recursively construct the set from $Y=\{x_0\}$ by given $Y$ and the next element $s \left(Y\right)$ is ｕniquely determined, am I right ? – bin Jul 17 '17 at 13:18

Here I provide a solution to Exercise 8.5.13, i.e, prove that at least one of $$Y\backslash Y^\prime$$ and $$Y^\prime \backslash Y$$ is empty, which I hope would help you to understand your question.

Proof. Let $$P(m)$$ is true iff we have $$\{y \in Y: y \leq m\}=\{y \in Y^\prime: y \leq m\ \}=\{y \in Y \cap Y^\prime: y \leq m\ \}$$ Now we prove that $$P(m)$$ is true for all $$m \in Y \cap Y^\prime$$ using strong induction. Suppose for induction that, for some $$n \in Y \cap Y^\prime$$, $$P(m)$$ is true for all $$m \in \{y \in Y \cap Y^\prime: y < n \}$$. Now we prove that $$P(n)$$ is true, which is equivalent to $$\{y \in Y: y < n\}=\{y \in Y^\prime: y < n \}$$
Supoose for contradiction that there exists at least one element in $$\{y \in Y: y < n\}$$ which is not contained in $$\{y \in Y^\prime: y < n \}$$. Write $$Y_n := \{y \in Y: y, and $$Y^\prime_n := \{y \in Y^\prime: y. Then the set $$\{y \in Y_n:y \notin Y^\prime_n \}$$ is non-empty and well-ordered, so write $$y_0:= \min(\{y \in Y_n:y \notin Y^\prime_n \})$$. Then we have $$\{y \in Y: y < y_0\}=\{y \in Y \cap Y^\prime: y < y_0 \}$$which implies that $$s(\{y \in Y \cap Y^\prime: y < y_0 \}) = s(\{y \in Y: y < y_0\}) = y_0$$
Then we prove that $$m < y_0$$ for all $$m \in \{ y \in Y \cap Y^\prime : y < n\}$$, which would imply that $$\{y \in Y \cap Y^\prime: y < y_0 \}=\{y \in Y \cap Y^\prime: y < n \}$$. For sake of contradiction, supoose that there exists a $$m_0 \in \{ y \in Y \cap Y^\prime : y < n\}$$ such that $$y_0 < m_0$$. Since $$m_0 < n$$, by our inductive hypothesis we have $$P(m_0)$$ is true, i.e., $$\{y \in Y: y < m_0\}=\{y \in Y \cap Y^\prime: y < m_0 \}$$but obviously, $$y_0 \in \{y \in Y: y < m_0\}$$, $$y_0 \notin \{y \in Y \cap Y^\prime: y < m_0 \}$$, a contradiction. Hence we have $$m < y_0$$ for all $$m \in \{ y \in Y \cap Y^\prime : y < n\}$$. So for every $$m \in \{y \in Y \cap Y^\prime: y < n \}$$, we have $$m \in \{y \in Y \cap Y^\prime: y < y_0 \}$$, thus $$\{y \in Y \cap Y^\prime: y < n \} \subseteq \{y \in Y \cap Y^\prime: y < y_0 \}$$ Since $$y_0 < n$$, we have $$\{y \in Y \cap Y^\prime: y < y_0 \} \subseteq \{y \in Y \cap Y^\prime: y < n \}$$Hence, $$\{y \in Y \cap Y^\prime: y < y_0 \} = \{y \in Y \cap Y^\prime: y < n \}$$Then we have $$s(\{y \in Y \cap Y^\prime: y < n \}) = s(\{y \in Y \cap Y^\prime: y < y_0 \}) = y_0$$ Similarly, $$y_{0}'=\min\{y\in Y^\prime_n:y\notin Y_n\}$$ and $$s(\{y \in Y \cap Y^\prime: y < n \})=y_0'$$ Hence $$y_0=y_0'$$, a contradiction. Thus $$Y_n \subseteq Y^\prime_n$$ and $$Y^\prime_n \subseteq Y_n$$. Hence, we have $$Y^\prime_n = Y_n$$. This closes induction.

Finally we prove that at least one of $$Y\backslash Y^\prime$$ and $$Y^\prime \backslash Y$$ is empty. Suppose for contradiction that these two sets are both non-empty, write $$y_1 = \min(Y\backslash Y^\prime)$$ and $$y_2 = \min(Y^\prime\backslash Y )$$.

we have $$\{y \in Y: y < y_1 \} = Y \cap Y^\prime$$: If $$w\in Y\cap Y'$$ and $$y_1\le w$$, then $$P(w)$$ is true, which implies that $$y_1\in Y\cap Y'$$, a contradiction. If $$y\in Y$$ and $$y, then $$y\in Y\cap Y'$$.

Thus $$s(Y \cap Y^\prime)=s(\{y \in Y: y < y_1 \}) = y_1$$ Similarly, we can show that $$s(Y \cap Y^\prime)=s(\{y \in Y^\prime: y < y_2 \}) = y_2$$So we have $$y_1 = y_2$$. But since $$Y\backslash Y^\prime$$ and $$Y\backslash Y^\prime$$ are disjoint, we have $$y_1 \neq y_2$$, a contradiction. Hence at least one of $$Y\backslash Y^\prime$$ and $$Y^\prime \backslash Y$$ is empty.

• Could someone explain why both $\{y\in Y_{n}:y\notin Y'_{n}\}$ and $\{y\in Y'_{n}:y\notin Y_{n}\}$ must be non-empty? – Karthik Kannan Aug 7 '19 at 19:57
• @KarthikKannan I think the section about $y'_0$ is in the case of the viceversa, i.e. there is an element in the initial segment of Y' that is not in Y. – It'sNotALie. Aug 11 '19 at 3:44
• Now we prove that P(n) is true, which is equivalent to $\lbrace y\in Y:y<n\rbrace =\lbrace y\in Y^\prime :y<n\rbrace$, shouldn't it be $\lbrace y\in Y:y\leq n\rbrace$ and $\lbrace y\in Y^\prime :y\leq n\rbrace$, if not could you please explain why? – Kareem Taha Aug 29 '20 at 20:35

The following is a supplement to the proof provided by the other poster. The only issue with that proof is that it is assumed that both $$\{y\in Y_{n}: y\notin Y_{n}'\}$$ and $$\{y\in Y_{n}': y\notin Y_{n}\}$$ are assumed non-empty. However, WLOG suppose $$\{y\in Y_{n}': y\notin Y_{n}\} = \emptyset$$. Then we have $$Y_{n}'\subseteq Y_{n}$$. As in the other proof, we let $$y_{0} = \text{min}(\{y\in Y_{n}: y\notin Y_{n}'\})$$ and we obtain $$\{y\in Y\cap Y': y < n\} = \{y\in Y\cap Y': y < y_{0}\} = \{y\in Y: y < y_{0}\}$$ But since $$Y_{n}'\subseteq Y_{n}$$ we have $$\{y\in Y': y < n\} = \{y\in Y\cap Y': y < n\}$$. Therefore, $$n = s(\{y\in Y': y < n\}) = s(\{y\in Y: y < y_{0}\}) = y_{0}$$ a contradiction, since $$y_{0} < n$$ by definition. This concludes the proof.