Exercise (from T.Tao's Analysis 1 textbook):

Let $X$ be a set, and let $\Omega$ be the space of all pairs $(Y,\leq)$, where $Y$ is a subset of $X$ and $\leq$ is a well-ordering of $Y$. If $(Y,\leq)$ and $(Y',\leq ')$ are elements of $\Omega$, we say that $(Y,\leq)$ is an \emph{initial segment} of $(Y',\leq ')$ if there exists an $x\in Y'$ such that $Y=\{y\in Y': y<'x\}$ (so in particular $Y\subset Y'$), and for any $y,y'\in Y$, $y\leq y'$ iff $y\leq ' y'$. Define a relation $\preceq$ on $\Omega$ by defining $(Y,\leq)\preceq (Y',\leq ')$ if either $(Y,\leq)=(Y',\leq ')$, or if $(Y,\leq)$ is an initial segment of $(Y',\leq ')$.

(a) Show that $\preceq$ is a partial ordering of $\Omega$.

(b) There is exactly one minimal element of $\Omega$; what is it?

(c) Show that the maximal elements of $\Omega$ are precisely the well-orderings $(X,\leq)$ of $X$.

(d) Using Zorn's lemma, conclude the well-ordering principle: every set $X$ has at least one well-ordering.

(e) Conversely, use the well-ordering principle to prove the axiom of choice, Axiom 8.1. (Hint: place a well-ordering $\leq$ on $\bigcup_{\alpha\in I}X_{\alpha}$, and then consider the minimal elements of each $X_{\alpha}$.)

I've managed to do (a), (b), (c), (e) but I'm stuck on (d).

I've thought about applying Zorn's lemma in the following way: let $Z$ be a totally ordered subset of $\Omega$ (which is $\neq\emptyset$ since $(\emptyset,\leq_{\emptyset})\in\Omega$) then we define $W:=\{V:(V,\leq)\in Z\ for\ some\ well-ordering\ of\ V \}$ and $U:=\{\leq : (T,\leq)\in Z\ for\ some\ T\in 2^X\}$; then $(S,\leq_{S})$, where $S:=\bigcup W$ and $\forall z,z'\in Z$ we say that $z\leq_S z'$ iff $\exists\leq\in U$ such that $z\leq z'$ could be a candidate upper bound for $Z$, but I'm not sure about this and in fact I haven't been able to prove that it is an upper bound for $Z$.

So I would appreciate any hint about how to show that Zorn's lemma holds for the set $\Omega$.

Best regards,



Suppose that $Z$ is a chain in $\Omega$, show that $Y=\bigcup_{(S,\leq_S)\in Z}S$ is a subset of $X$ and $\leq_Y$ defined by: $$y\leq_Yy'\iff\exists(S,\leq_S)\in Z: y,y'\in S, y\leq_S y'$$ is a well-ordering of $Y$, and that $(Y,\leq_Y)$ is an upper-bound for $Z$.

Then apply Zorn's lemma.

(You might notice that $\leq_Y$ is actually the union of $\leq_S$ from those $(S,\leq_S)\in T$, and you won't be wrong.)

  • $\begingroup$ that's for sure, but my question in fact is: how to show that Zorn's lemma holds? $\endgroup$
    – lorenzo
    Dec 5 '16 at 13:30
  • 1
    $\begingroup$ That's not your question. Read your question. $\endgroup$
    – Asaf Karagila
    Dec 5 '16 at 13:32
  • $\begingroup$ ok, I clarified my question. $\endgroup$
    – lorenzo
    Dec 5 '16 at 14:02

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.