# Well ordering on the quotient of well ordered sets

Let $X\neq\emptyset$ be some set. Consider $\mathcal A$ to be the set containing all pairs $(Y,\leq)$, where $Y\subseteq X$ and $\leq$ is a well-ordering. Define $(A,\leq)\equiv (B,\leq')$ iff $(A,\leq)$ is order isomorphic to $(B,\leq')$, which is clearly an equivalence relation. Further, define, in $\mathcal A/\equiv\,= :\hat{\mathcal A}$ an ordering $[(A,\leq)]\preceq [(B,\leq')]$ if there exists an initial segment of $B'\subseteq B$ such that $(A,\leq)\equiv (B',\leq')$. The ordering is strict if all $B'\subset B$ are proper initial segments.

I have verified this ordering is well-defined and is a total ordering since for any two well ordered sets there is an order isomorphism from one to an initial segment of the other.

Now, fix $(A,\leq)\in\mathcal A$ and consider the set $$\hat{\mathcal S}_A := \{ [(B,\leq')] : [(B,\leq')]\prec [(A,\leq)]\}$$ The mapping $f: (A,\leq)\to \hat{S}_A, x\mapsto [(A_x,\leq)]$, where $A_x := \{z\in A: z<x\}\subset A$ is a proper initial segment, is an order isomorphism.

From the above, we are to deduce the set $(\hat{A},\preceq)$ is actually well-ordered.

To finish A. Karagila's post. If $B$ is not least in $\mathcal B$, then $B'\in\mathcal B$ and $B'\prec B$, hence $B'$ embeds into an initial segment $A_y\subset A$, but then $y\in A$ to which corresponds $B'\in\mathcal B$ such that $B'\equiv A_y$, consequently $y<x$, which is impossible.

• Huh? What are you trying to prove? – Asaf Karagila Mar 30 '18 at 12:43
• @AsafKaragila that the total ordering $\preceq$ is also a well ordering. An upper bound for a nonempty subset of $\hat{A}$ would be sufficient, as well. I'm sort of stuck, it's probably something stupidly simple. – Alvin Lepik Mar 30 '18 at 12:43
• When you weave a labyrinth around your work, it is easy to get lost. A good exit strategy is to scrap the idea all together, and start fresh. – Asaf Karagila Mar 30 '18 at 12:51

The proof is simpler and tantamount to just verifying by hand. Given a non-empty family $\cal B\subseteq A$, pick some $A$ such that $[(A,\leq)]$ is in $\cal B$. If this is a minimal element, we're done. So let's assume it's not.
Now each $[(B,\leq_B)]\in\cal B$ such that $[(B,\leq_B)]\prec[(A,\leq)]$ embeds into a unique proper initial segment of $A$. So each such $B$ gives us a unique $x$ such that $(B,\leq_B)$ is isomorphic to $A_x=\{a\in A\mid a<x\}$. Moreover, since $A$ is not the minimal element of $\cal B$, the set of $\{x\in A\mid\exists[(B,\leq_B)]\in\mathcal B, B\equiv A_x\}$ is non-empty. Since $\leq$ is a well-ordering of $A$, there is a minimal $x$.
Now show that $B$ which corresponds to this minimal $x$ is the minimal element of $\cal B$.