Background
I am trying to prove a lemma in Terence Tao's Analysis 1 which is used to prove the statement below.
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.
My Understanding
The following definitions are relevant:
- Let $X$ be a partially ordered set with ordering relation $\leq$, and let $Y$ be a subset of X. If $x \in X$, we say that $x$ is an upper bound for $Y$ iff $y \leq x$ for all $y \in Y$. If in addition $x \notin Y$ then we say $x$ is a strict upper bound of $Y$.
Tao assumes to the contrary that the statement above is false. Then every well-ordered subset $Y$ of $X$ which has $x_0$ as its minimal element has at least one strict upper bound. Appealing to the Axiom of Choice we can assign to each such subset $Y$ a strict upper bound $s(Y) \in X$. He then makes the following definition.
A subset $Y$ of $X$ is said to be good set if $Y$ is well-ordered, contains $x_0$ as its minimal element and obeys the property that $x = s(\{y \in Y: y < x\})$ for each $x \in Y$ where $x \neq x_0$.
The lemma set as Exercise 8.5.13 and the one i'm trying to prove is
If $Y$ and $Y'$ are two good subsets of $X$, then every element of $Y'\setminus Y$ is a strict upper bound for $Y$, and every element of $Y \setminus Y'$ is a strict upper bound for $Y'$
I got stuck for some time so I peeked at the hint in the textbook which was roughly show that $s(Y \cap Y ')$ exists and that $Y \cap Y'$ is good. Then show that $s(Y \cap Y') = \min(Y \setminus Y')$ if $Y \setminus Y'$ is non-empty and simlarly when $Y$ and $Y'$ are interchanged.
I have managed to show $s(Y \cap Y ')$ exists and that $Y \cap Y'$ is good but I am terribly stuck with regards to the last part of the hint. If one can point me in the right direction or give me a hint that would be extremely helpful and appreciated.
Note: I have already looked at the following relevant question Exercise 8.5.13 Tao Analysis 1 but the accepted answer uses Zorn's Lemma which unfortunately is not satisfactory since my lemma is used to prove the statment I mentioned at the start of the question. And this statement is used to prove Zorn's Lemma which is Exercise 8.5.14
Best Answer
I think I have managed to solve my problem:
(*)We first note that using the "generalised strong induction principle" (Proposition 8.5.10) that we can show $\{y \in Y: y \leq a \} = \{y \in Y': y \leq a \} = \{y \in Y \cap Y': y \leq a \}$ for each $a \in Y \cap Y'$. Also observe that $Y \cap Y'$ is well-ordered since $Y$ is well-ordered and that $\min(Y \cap Y') = x_0$. This implies that $s(Y \cap Y')$ exists.
Now we claim that if $Y\setminus Y'$ is non-empty then $s(Y \cap Y') = \min(Y \setminus Y')$. By assumption $Y$ is good and $\min(Y \setminus Y') \in Y$ which implies that $\min(Y \setminus Y') = s(\{y \in Y: y < \min(Y \setminus Y')\})$. It thus suffices to show that $\{y \in Y: y < \min(Y \setminus Y')\} = Y \cap Y'$. Clearly $\{y \in Y: y < \min(Y \setminus Y') \subseteq Y \cap Y'$ otherwise we would contradict the minimality of $\min(Y \setminus Y')$. Now let $y'\in Y \cap Y$ since $Y$ is totally ordered we must have $\min(Y \setminus Y') < y$ or $y < \min(Y \setminus Y')$. We need only consider the first case. In this situation we have that $\min(Y \setminus Y') \leq y$, where $y \in Y \cap Y'$. But then using (*) we can conclude that $\min(Y \setminus Y') \in Y \cap Y'$ which is a contradiction. Therefore our claim must be true. The same arguement with $Y$ and $Y'$ interchanged shows that when $Y'\setminus Y$ is non-empty then $s(Y \cap Y') = \min(Y' \setminus Y)$.
Suppose to the contrary that $Y \setminus Y'$ and $Y' \setminus Y$ are non-empty. Then the claim we have just proven yields $\min(Y' \setminus Y) = \min(Y \setminus Y')$ which leads to a contradiction. Therefore at least one of the two sets $Y \setminus Y'$ and $Y' \setminus Y$ is empty.
Without loss of generality suppose that $Y' \setminus Y$ is empty. Then it is vacously true that every element of $Y'\setminus Y$ is a strict upper bound of $Y$. Conversly since $Y' \setminus Y$ is empty it follows that $Y' \subseteq Y$ therefore $Y \cap Y' = Y$. Also we have $s(Y \cap Y') = \min(Y \setminus Y')$ since $Y \setminus Y'$ is not empty. This implies that every element of $Y \setminus Y'$ is a strict upper bound of $Y'$ since otherwise there is an element $y'$ in $Y \setminus Y'$ and an element $y'' \in Y'$ such that $y'' > y$ but $s(Y \cap Y')$ is a strict upper bound of $Y'$. From this we can conclude that $\min(Y \setminus Y') > y'$ a contradiction. Thus it is indeed the case that If $Y$ and $Y'$ are two good subsets of $X$, then every element of $Y'\setminus Y$ is a strict upper bound for $Y$, and every element of $Y \setminus Y'$ is a strict upper bound for $Y'$. As desired.