7
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – lioness99a Jul 17 '17 at 11:50
  • 1
    $\begingroup$ Thanks for your comments @lioness99a, when I found the image is not displayed correctly I retyped my question. $\endgroup$ – bin Jul 17 '17 at 12:01
  • $\begingroup$ @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$ $\endgroup$ – bin Jul 17 '17 at 12:09
  • 1
    $\begingroup$ 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. $\endgroup$ – math635 Jul 17 '17 at 12:14
  • $\begingroup$ 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 uniquely determined, am I right ? $\endgroup$ – bin Jul 17 '17 at 13:18
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Karthik Kannan Aug 7 at 19:57
  • $\begingroup$ @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. $\endgroup$ – It'sNotALie. Aug 11 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.