$\mathcal{W}$ is a set of well orderings $\leq$ on subsets of $X$. We define a partial ordering $\mathfrak{R}$ on $\mathcal{W}$ as follows. If $\leq_a$ and $\leq_b$ are well orderings on $X_a$ and $X_b$, respectively, then $(\leq_a,\leq_b)\in \mathfrak{R}$ iff

  • $X_a\subset X_b$
  • $x\leq_a y$ iff $x\leq_b y$ for all $x,y\in X_a$
  • $x\leq_b y$ for all $x\in X_a$ and $y\in X_b\backslash X_a$

Let's agree to write $\leq_a$ precedes $\leq_b$ instead of $(\leq_a,\leq_b)\in \mathfrak{R}$. I already proved that $\mathfrak{R}$ satisfies properties of a partial ordering.

Let $\mathcal{A}$ be a linearly ordered (by $\mathfrak{R}$) subset of $\mathcal{W}$. I want to prove that $\mathfrak{a}=\bigcup_{\leq\in\mathcal{A}}\leq$ is an upper bound of $\mathcal{A}$. In other words, we have to prove that $\mathfrak{a}\in\mathcal{W}$ and $\leq$ precedes $\mathfrak{a}$ for all $\leq\,\in\mathcal{A}$. For $\mathfrak{a}\in\mathcal{W}$ to be true $\mathfrak{a}$ should be a well ordering on some subset of $X$, to wit $\mathfrak{a}$ should be a linear ordering on some $A\subset X$ and every nonempty subset of $A$ should have a minimal element. I already showed that $\mathfrak{a}$ is a linear ordering on $A=\bigcup_{Y\in S}Y$ where $$S=\{Y: Y \text{ is well ordered by some} \leq\,\in\mathcal{A}\}.$$ It should be noted that $S$ is linearly ordered by $\subset$. Now we have to show that every subset of $A$ has a minimal element, viz., for every set $B\subset A$ there exists $x\in B$ such that if $(y,x)\in\mathfrak{a}$ then $x=y$ for all $y\in B$.

Proof for the case when $B$ is finite.

Since $B\subset A$, for all $x\in B$ there exists $Y\in S$ such that $x\in Y$. Since $B$ is finite, there exists a finite set $T\subset S$ such that for all $x\in B$ there exists $Y\in T$ such that $x\in Y$. Since $S$ is linearly ordered by $\subset$, there exists a maximal element and upper bound $Z$ of $T$. Hence, $Y\subset Z$ for all $Y\in T$; therefore, $B\subset Z$. Since $Z\in S$, $Z$ is well ordered by some $\leq\,\in\mathcal{A}$; therefore, $Z$ is well ordered by $\mathfrak{a}$. Hence, by definition, every subset of $Z$ has a minimal element. Since $B\subset Z$, $B$ has a minimal element. $\blacksquare$

Could anyone help me generalize this proof for the case when $B$ is infinite? I can provide proofs for the statements in the text upon request.


Just to clarify: $\mathcal{W}$ is meant to be all the well-orderings on the subsets of $X$, right? If it is just some set of well orderings, then the claim is not necessarily true (in particular, $\mathfrak{a}$ might not be in $\mathcal{W}$).

Anyway, here's a proof. The basic idea is that you don't need to have $B \subseteq Z$, as in your proof; it is enough to find a $Z$ such that $Z \cap B$ is non-empty.

Let $B \subseteq A = \bigcup_{Y \in S}Y$. Then there exists some $Z$ in $S$ such that $Z \cap B$ is non-empty. By the definition of $S$, this $Z$ also has a well-ordering $\leq_Z \: \in \mathcal{A}$. It follows that $Z \cap B$ has some $\leq_Z$-minimal element $z$. Our aim is to show that $z$ is $\mathfrak{a}$-minimal in $B$, which amounts to showing that for all $y$ in $B$ we have $(z,y) \in \mathfrak{a}$ (this is equivalent to the definition you provided).

So take any $y \in B$. If $y \in Z$, then we are done by the $\leq_Z$-minimality of $z$, so let us assume that this is not the case. Still, there is some $Y$ in $S$, and a corresponding well-ordering $\leq_Y \in \mathcal{A}$ on it, such that $y \in Y$. The fact that $S$ is linearly ordered implies $Z \subset Y$ (or else $y$ would be in $Z$ after all). Then $\leq_Z$ precedes $\leq_Y$, which, by definition, implies that since $z \in Z$ and $y \in Y\setminus Z$, we have $z \leq_Y y$, and consequently, $(z,y) \in \mathfrak{a}$, as intended.

  • $\begingroup$ Yes, $\mathcal{W}$ is a set of all the well orderings on the subsets of $X$. Thank a lot! $\endgroup$ – Yerbolat Jul 3 '16 at 7:00

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.