# Intuition behind proof and verification partially ordered sets

Hi everyone in the book that I read I have trouble to understand the argument of the proof at the below proposition. There is a lot of point which are left as exercises, which is great. One of these is the following claim I put all the proposition for the sake of the completeness but not the entire proof.

My questions are: Is the proof of the claim correct (I use the hints which the book give us)? What is the intuition behind the claim? I mean, the entire construction of the "good sets" is rather artificial to me, what would be a possible motivation for them? I don't quite understand all the approach. Any suggestion, advice, whatever would be great thanks in advance. If someone consider opportune I'd put the entire proof or change the title (if there is one better).

Proposition: Let $X$ be a partially ordered set with ordering relation $\le_X$, and let $x_0\in X$. Then there is a well ordered subset $Y$ of $X$ which has $x_0$ as its minimum element, and which has no strict upper bound.

Proof: Suppose for the sake of contradiction that every well-ordered subset $Y$ of $X$ which has $x_0$ as its minimum element contain at least one strict upper bound. Using the axiom of choice we can thus assign a strict upper bound $s(Y)$ to each well-ordered subset $Y$ of $X$ which has $x_0$ as its minimum element.

Let us define a special class of subsets $Y$ of $X$. We say that a subset $Y$ of $X$ is a good set iff is well-ordered, contain $x_0$ as its minimum element and obey the property

$$x=s(\{y\in Y: y<x\})\; \text{for all }\; x\in Y\backslash \{x_0\}$$

The collection $\Omega:=\{ Y: Y\; \text{is a good set}\;\}$ is non-empty since contains the set $\{x_0\}$.

Claim 1: Let $Y, Y' \in \Omega$, i.e., both are good sets. Then each element in $Y'\backslash Y$ is a strict upper bound for $Y$. Similarly each element in $Y\backslash Y'$ is a strict upper bound for $Y'$.

Proof of the Claim 1: Note that $Y\cap Y' \not= \varnothing$ because both contains at least $x_0$. First we'd like to show that for all $x\in Y\cap Y'$ we have the following equality:

$$\{y\in Y: y\le x \}=\{y\in Y': y\le x \}=\{y\in Y\cap Y': y\le x \}$$

We may use strong induction for this purpose (this is possible because everyone of the above sets is well-ordered). Suppose that the assertion hold for each $y\in Y\cap Y'$ such that $y<x$, in other words we have the equality $\{y\in Y: y< x \}=\{y\in Y': y< x \}=\{y\in Y\cap Y': y< x \}$. We shall show that also hold when $y=x$.

We have $x=s(\{y\in Y: y< x \})=s(\{y\in Y': y< x \})$ because both are good sets. Then the equality of the first two sets hold. So, if $y\in Y,\; y=x$ and $y\in Y,\;y= x$ are equal for $x\in Y\cap Y'$. Thus the claim follows for the third set.

(2) Now we wish to show that $Y\cap Y'$ is itself a good set. Note that automatically is a well-ordered set, since every subset of a well-ordered set is well-ordered. And also contain $x_0$ as its minimum element. So, only we have to show that obey the third property. In other words our task is to show

$$x=s(\{y\in Y \cap Y': y<x\})\; \text{for all }\; x\in (Y\cap Y')\backslash \{x_0\}$$

We may assume $(Y\cap Y')\backslash \{x_0\} \not= \varnothing$ since otherwise is a good set and there is nothing to prove. Let $x\in (Y\cap Y')\backslash \{x_0\}$, and we set $\{y\in Y \cap Y': y<x\}$. For the first part of the proof we already known $\{y\in Y \cap Y': y<x\}=\{y\in Y: y< x \}$ for all $x\in (Y\cap Y')\backslash \{x_0\} \subset Y\cap Y'$. Thus $x=s(\{y\in Y: y< x \})=s(\{y\in Y \cap Y': y<x\})$, which shows that the set is a good set.

(3) For the above part of the claim we know that $s(Y\cap Y')$ exists. We shall show that if $Y'\backslash Y\not= \varnothing$, then $s(Y\cap Y')= \text{min}(Y'\backslash Y)$. Similarly with the roles of $Y$ and $Y'$ interchanged.

Suppose the set $Y'\backslash Y$ is non-empty, then contains a minimum element because is a well-ordered set. Let a call it for brevity $x_0$. Thus for all $y<x_0$ we have $\{y\in Y': y<x_0 \} \subset Y$ using the minimality of $x_0$. Also is easy to check that $y\in Y \cap Y'$ iff $y<x_0$.

So $\{y\in Y': y<x_0 \}=\{y\in Y\cap Y': y<x_0 \}$. Then $x_0=s(\{y\in Y\cap Y': y<x_0 \})$ because as we have shown is a good set. In other words $x_0= \text{min} (Y'\backslash Y) =s(\{y\in Y\cap Y': y<x_0 \})$.

It's trivial to show $s(\{y\in Y\cap Y': y<x_0 \}) =s(Y\cap Y')$ this follows immediately for the way in which $x_0$ was specified since $\{y\in Y\cap Y': y<x_0 \}=Y\cap Y'$, one inclusion is obvious and the other follows because if $y\in Y\cap Y' \subset Y$ thus it can't be greater than $x_0$.

Note that exactly the same argument applies only with the roles interchanged of $Y, Y'$ when we assumme $Y\backslash Y'\not= \varnothing$.

(4) If $Y,Y' \in \Omega$ are good sets. Then either $Y\backslash Y'$ is non-empty or $Y'\backslash Y$ is non-empty but not both at the same time.

Suppose for the sake of contradiction that both cases occurs at the same time, i.e., $Y\backslash Y'\not= \varnothing$ and $Y' \backslash Y\not= \varnothing$. Let $x= \text{min} (Y\backslash Y')$ and $x'= \text{min} (Y'\backslash Y)$. We know by (3) that $x= s(Y\cap Y')$ and also $x'=s(Y\cap Y')$, which would imply that $x=x'$ but this means that $x,x'\in Y\cap Y'$ which is a contradiction. Hence, it is not possible that both holds at the same time.

Also we can show that either $Y\subset Y'$ or $Y' \subset Y$, if were not the case, i.e., $Y\not\subset Y'$ and $Y' \not\subset Y$. Then $Y'\backslash Y$ and $Y\backslash Y'$ are both non-empty which as we have shown above leads a contradiction.

(5) To conclude the proof of the claim we shall show that all the elements in $Y'\backslash Y$ are strict upper bounds for $Y$. Note it is not necessary shows that the elements in $Y\backslash Y'$ a strict upper bounds for $Y'$ because exactly the same arguments apply.

Let $Y,Y' \in \Omega$, so both are good sets.Then either $Y'\backslash Y$ is empty or not. If the set is empty is vacuously true that each of its element is a strict upper bound for $Y$. If were not the case, this meant $Y\subset Y'$ and $Y\cap Y'=Y$ for what shown in (4). Then $s(Y\cap Y')= s(Y)= \text{min}(Y'\backslash Y)$. So, the minimum element of $Y'\backslash Y$ is an upper bound for $Y$ and so, each element in $Y'\backslash Y$ is strictly greater than each element in $Y$ by transitivity, i.e., are strict upper bounds for $Y$.

Hence the claim follows as desired.

I think there is an intimate relation of this proposition and the Zorn's lemma. Am I right?

• The entire proof appears in the Tao's Analysis book. If someone consider correct I'd put the entire argument here. Although at this moment my problem is regard this claim. – Jose Antonio Jan 11 '14 at 21:14
• No one could help me, please? – Jose Antonio Jan 12 '14 at 4:50
• I don't know the term "strict upper bound", what does it mean exactly? – Asaf Karagila Jan 12 '14 at 8:55
• Basically the author says: Let $X$ be a partially ordered set with ordering relation $\le_X$ and let $Y\subset X$, then a strict upper bound is any $x\in X$ which is an upper bound for all elements in $Y$ but is not in $Y$. – Jose Antonio Jan 12 '14 at 9:02
• To your last edit, the statement is indeed equivalent to Zorn's lemma. In fact Zorn's lemma can be reduced to the following formulation, if every well-ordered chain has an upper bound then there is a maximal element. This statement shows that there is a well-ordered chain that either has a last element which is maximal, or that there is a chain without an upper bound (not a strict, but generally no upper bound). – Asaf Karagila Jan 12 '14 at 23:17

Jose Antonio, I haven't checked the entire proof above in detail, but it appears clear to me that it is possible to prove the proposition by that method. So I will address only the question of intuition regarding "good sets."

In the considerations below, I will use some facts (about transfinite induction) that are known only after the proofs of the basic properties of well-ordered sets have been carried out. Evidently, at this stage of the book, the author doesn't yet have these facts available, so he must use an indirect approach to prove the proposition. I will use a direct approach to say what these good sets really are, intuitively.

A proper initial segment of a well-ordered set $A$ is a subset of the form $I_x = \{ y \in A \mid y < x \}$. For example, if $A = \mathbf{N}$, then the proper initial segments of $A$ are $I_0 = \varnothing$, $I_1 = \{0\}$, $I_2 = \{0, 1\}$, $I_3 = \{0, 1, 2\}, \ldots$

Now assume temporarily that $A = \mathbf{N}$, and let $B$ be some other set. Say that you would like to define a function $f \colon A \to B$ by induction. What information do you need? To define $f(n)$, you need a rule that tells you how to select a value for $f(n)$ depending on all the values $f(m)$ for $m < n$. In other words, you need a function $F \colon \cup_{I \in S_A} B^I \to B$, where $S_A$ is the set of proper initial segments of $A$, and $B^I$ is the set of functions from $I$ to $B$. Thus whenever $\sigma \colon I \to B$ is a function defined on some proper initial segment $I$ of $A$, we have a well-defined element $F(\sigma)$ of $B$. To define your function $f$, you then declare that for all $n \in A$, we should have $$f(n) = F\left(\left.f\right|_{I_n}\right).$$

It turns out that such definitions by induction are possible even for arbitrary well-ordered sets $A$, not just $\mathbf{N}$. This is definition by transfinite induction. There is also a method of proof by transfinite induction.

Turning now to the example, imagine that there exists some very large well-ordered set $A$, much larger than your set $X$. Define a function $f \colon A \to X \cup \{*\}$, where $\{*\}$ is some point not in $X$, in the following way. Let $f(0) = x_0$, where $0$ is the smallest element of $A$. If $\alpha > 0$, let $f(\alpha) = s(f(I_{\alpha}))$ if $f(I_\alpha)$ is a well-ordered subset of $X$ that has $x_0$ as its least element, and $f(\alpha) = *$ otherwise.

Then it can be checked by (transfinite) induction that $f(I_\alpha)$ is always a well-ordered set with minimum element $x_0$. Thus $f(\alpha) \ne *$ for all $\alpha$. In fact, $f$ realizes an isomorphism of $A$ with some well-ordered subset of $X$. This is a contradiction because we assumed $A$ to be larger than $X$.

If we hadn't made the absurd assumption that every well-ordered subset of $X$ (with least element $x_0$) had a strict upper bound, then this construction would have stopped at some point $\alpha_0$, and then we would have had $f(\alpha) = *$ for all $\alpha \geq \alpha_0$. Then $f$ would have realized an isomorphism of the initial segment $I_{\alpha_0}$ with a well-ordered subset of $X$ without a strict upper bound.

The "good sets" that appear in the proof are precisely the sets $f(I_\alpha) \subseteq X$ in the above construction. Intuitively, start with $x_0$, add an element $x_1 > x_0$, then $x_2 > x_1$, etc. Once you have added all the $x_n$ for $n \in \mathbf{N}$, these elements form a well-ordered set, so add an $x_{\omega}$ that is greater than all the $x_n$. Then keep going like this. The good sets are those sets which, at some point in time, consist of all the elements that have already been added up to that point.

The facts that I've used here will become obvious to you (even on a rigorous level) once you've learned about transfinite induction. Unfortunately, some authors prefer to explain only Zorn's lemma instead of transfinite induction, and then there is much less intuition about what you are doing, even in some practical cases where Zorn's lemma may be sufficient. (Also, occasionally, there are cases when transfinite induction cannot be avoided.) If that is the case in the book you're reading, this material can be found in the first chapter of Introductory Real Analysis By Kolmogorov and Fomin, or for a fuller treatment, in Introduction to Set Theory by Jech and Hrbáček.

Edit: I've corrected an error in notation concerning the domain of the function $F$.

• Thanks for your time, let me read it carefully. After a lot of work I think the intuition behind good-sets is construct under the hypothesis that each well-ordered set contain a strict upper bound a self-defeating object. But, it is great find a meticulous answer as yours. Thanks. If we have some other question I hope might ask you. Indeed the book only give us the Zorn's lemma and a lot of amazing exercises. I got the Kolmogorov's book, but I love the way in which Tao explained things, he has a divine talent to do it, although since my formation is not in mathematics is sometimes difficult. – Jose Antonio Jan 19 '14 at 21:54
• I'm glad this was helpful. – user122171 Jan 19 '14 at 23:11