Proof of Lemma 8.5.14 in Terence Tao Analysis I

Question

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

Answer 1

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<n \}$, and $Y^\prime_n := \{y \in Y^\prime: y<n \}$. 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<y_1$, 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.

Answer 2

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.