Exercise 8.5.13 Tao Analysis 1

Question

I am trying to understand the proof of Exercise $8.5.13$ in Terence Tao's book Analysis $1$. The problem and its solution are posted here

Proof of Lemma 8.5.14 in Terence Tao Analysis I

In the proof, it is assumed that the sets $\{y\in Y_{n}: y\notin Y'_{n}\}$ and $\{y\in Y'_{n}: y\notin Y_{n}\}$ are both non-empty and therefore have minimal elements. In this way, the user arrives at a contradiction.

Question: What is the justification for this assumption? If this assumption is incorrect, how would one arrive at a contradiction (i.e. by assuming at least one of the above sets is non-empty)?

Answer 1

This is how I would prove 8.5.13.

Let $\le$ be a transitive reflexive binary relation on $X,$ and $x_0\in X.$ As usual $x<x'$ means $x'\ne x\le x'.$ We will also assume that $\forall x,x'\in X\, (x\le x'\le x\implies x=x')$ (Such $\le$ are called strict) for reasons given in my final remark.

Let $W$ be the set of subsets of $X$ that are well-ordered by $<$ and have $x_0$ as their least member. We have $\{x_0\} \in W,$ so $W$ is not empty. We introduce a binary relation $<^*$ on $W$,

where $w<^*w'$ iff $$(i). w\subsetneqq w'$$ $$(ii). \forall x\in w \, \forall x'\in (w'\setminus w)\,(x<x').$$

We show there exists a $<^*$-maximal $Y\in W.$

From that, if $x'\in X$ is a $\le$-upper bound for $Y$ and $x'\not \in Y$ then by the strictness of $\le$ we have $\forall w\in Y\, (w<x').$ But then $Y'=Y\cup \{x'\}\in W$ with $Y<^*Y',$ contradicting the $<^*$-maximality of $Y$. So $Y$ has no strict upper bound.

Finding $Y$ is by the following, which those familiar with set theory will recognize as a common method:

A chain in $W$ is any $C\subset W$ such that $$(iii). \forall c,c'\in C\,(c<^*c'\lor c'<^*c\lor c=c').$$

Claim: If $C$ is a non-empty chain in $W$ then $\cup C\in W$ and $\cup C$ is a $<^*$-upper bound for $C.$

Proof of claim: If $x,x'\in \cup C$ then for some $c,c'\in C$ we have $x\in c$ and $x'\in c'.$ Now $C$ is a $<^*$-chain so $c''=c\cup c'$ is one of $c,c'$ by (i) and (iii), so $\{x,x'\}\subset c''\in C.$ And since $c''$ is well-ordered by $<$, we have $(x'<x\lor x<x'\lor x=x').$

$\bullet \;$ So (since, also, $\le$ is transitive), $\cup C$ is linearly ordered by $<.$

Now suppose $\emptyset \ne S\subset \cup C.$ Take $c_0\in C$ such that $c_0\cap S \ne \emptyset$ and let $$s_0=\min_<(c_0\cap S)$$ which exists because $c_0$ is well-ordered by $<.$

Now for any $s\in S,$ take $c\in C$ such that $s\in c.$

If $c<^*c_0$ or $c=c_0$ then $s\in c\subset c_0$ so $s\in c_0\cap S,$ so by definition of $s_0$ we have $(s_0<s\lor s_0=s).$

Or if $c_0<^*c$ then

$(a).$ If $s\not \in c_0$ then by $(ii)$ we have $\forall w\in c_0 \,(w<s ),$ and in particular $s_0\in c_0,$ so $s_0<s.$

$(b).$ If $s\in c_0$ then $s\in c_0\cap S$ so by definition of $s_0$ we have $(s_0<s \lor s_0=s).$ (Similar to a previous case above.)

$\bullet \bullet \;$ So $\cup C$ is well-ordered by $<,$ so $\cup C \in W.$

Finally if $c\in C$ and $s\in (\cup C) \setminus c,$ take $c'\in C$ with $s\in c'.$ We cannot have $c'=c$ but we cannot have $c'<^* c$ either, else $s\in c'\subset c.$ So $c<^*c'$ and $s\in c'\setminus c,$ so by $(ii)$, we have $\forall w\in c\, (w<s).$ So $c<^*\cup C\lor c=\cup C.$

$\bullet \bullet \bullet \;$ So $\cup C$ is a $<^*$-upper bound for $C.$ QED.

Now by the claim (and since $W$ is not empty) we can apply Zorn's Lemma to $(W,<^*)$ and conclude there exists a $<^*$-maximal $Y\in W.$

Remark. $Y$ need not be $\subset$-maximal nor unique For example if $X=\{x_0,x_2,x_3\}$ with $x_0<x_1<x_2$ then $X$ and $\{x_0,x_3\}$ are $<^*$-incomparable and $<^*$-maximal

Final remark. If the poset is not assumed to be strict we might have $X=\{x_0,x_1\}$ with $x_0\ne x_1$ and $x_0\le x_1\le x_0.$ Then $Y=\{x_0\}$ but $x_1$ is a $\le$-strict upper bound for $Y$.