# Every linearly ordered subset $\mathcal{A}$ of a set $\mathcal{W}$ of well orderings $\leq$ on subsets of some set $X$ has an upper bound.

$\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.

## 1 Answer

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.

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