bigger well order of a set of well orders

Question

Let M be a set of well orders. Then there exists an well order $(X,<_X)$ whereas it holds that for all $(Y,<_Y) \in M$, $(Y,<_Y)$ is strict smaller than $(X,<_X)$. (We call $(Y,<_Y)$ strict smaller than $(X,<_X)$ if $(Y,<_Y)$ is isomorphic to an initial segment of $(X,<_X)$ and $(Y,<_Y)$ is not isomorphic to $(X,<_X)$.

I have already shown that M is well ordered up to isomorphisms. But I don't get how I could construct my $(X,<_X)$ from there on. And I should only use ZF to prove it...

Answer 1

As mentioned in the comments above, deviation through the ordinals is a straightforward approach, as long as you've already (seen) proved that every well-ordered set is uniquely isomorphic to a unique ordinal.

Now, let's suppose you haven't had that proved, yet. One option is to actually prove it, and proceed as outlined above. I outline another approach, here.

---

First of all, we may assume without loss of generality that the elements of $\mathcal M$ are disjoint as sets--if not, we may replace all such sets $A$ by $A\times\{A\},$ and adjust the corresponding relations easily to again yield a set of well-ordered sets isomorphic to those of $\mathcal M.$ We may also assume $\mathcal M$ is non-empty, for if not, then we're (vacuously) finished.

Next, we construct a representative for each order type of elements of $\mathcal M.$ Observing that $\cong$ is an equivalence relation on $\mathcal M,$ we have that $\mathcal M$ can be partitioned into $\cong$-equivalence classes. Given any such equivalence class $\mathcal I,$ we have that $\mathcal I$ is a non-empty subset of $\mathcal M,$ that the elements of $\mathcal I$ are isomorphic, and that if an element $\langle B,<_B\rangle$ of $\mathcal M$ is isomorphic to some element of $\mathcal I,$ then $\langle B,<_B\rangle$ is also an element of $\mathcal I.$ Given any $\langle A,<_A\rangle,\langle B,<_B\rangle\in \mathcal I,$ recall/prove that there is a unique order-isomorphism $f_B:A\to B.$ Let $A'$ be the set whose elements are of the form $\{f_B(a):B\in \mathcal I\}$ for each $a\in A,$ and define $<_{A'}$ on $A'$ by $X<_{A'}Y$ if there exist $x\in X,y\in Y,$ and $B\in\mathcal I$ such that $x<_By.$ By disjointness and construction, you should be able to show that $\langle A',<_{A'}\rangle$ is a well-order isomorphic to $\langle A,<_A\rangle.$ Moreover, our choice of $A$ doesn't matter, in the sense that, for any $A,B\in\mathcal I,$ we have $\langle A',<_{A'}\rangle=\langle B',<_{B'}\rangle.$ Consequently, this set is determined by $\mathcal I,$ rather than by choice of any element of $\mathcal I,$ so instead, we denote the set and relation thus constructed by $R(\mathcal I)$ and $<_{R(\mathcal I)}.$

Now, we consider the set $\mathcal N$ whose elements are the well-orderings $\langle R(\mathcal I),<_{R(\mathcal I)}\rangle$ for each $\cong$-equivalence class $\mathcal I$ of $\mathcal M.$ You should be able to show that $\mathcal N$ is well-ordered by "is strictly less than" (in the sense of initial segments), and that its elements are disjoint as sets. If $\mathcal N$ has a greatest element with respect to this relation--say $\langle C,<_C\rangle$--then we're nearly done. We construct a new well-order by adding one more element to $C,$ and specifying that this new element is greater than every element of $C.$ This new well-order is the one we want. If $\mathcal N$ doesn't have a greatest element, we need to work harder.

We define a function $f$ on $\mathcal N$ by transfinite recursion as follows:

• Base Step: We leave the least element of $\mathcal N$ alone--that is, if $\langle X,<_X\rangle$ is the least element of $\mathcal N,$ we define $f\bigl(\langle X,<_X\rangle\bigr)=\langle X,<_X\rangle.$
• Successor Step: Suppose we have defined $f\bigl(\langle X,<_X\rangle\bigr)=\langle Y,<_Y\rangle$ for some $\langle X,<_X\rangle\in\mathcal N,$ and that $\langle X,<_X\rangle\cong\langle Y,<_Y\rangle.$ Take the least $\langle Z,<_Z\rangle\in\mathcal N$ greater than $\langle X,<_X\rangle,$ so that there is a unique order isomorphism $g$ from $Y$ into a proper initial segment of $\langle Z,<_Z\rangle.$ We replace said initial segment with $Y$--that is, we make $Z'=Y\cup\bigl(Z\smallsetminus g[Y]\bigr)$ make $<_{Z'}$ equal to $<_Y$ on $Y,$ equal to $<_Z$ on $Z\smallsetminus g[Y],$ and say that $y<_{Z'}z$ whenever $y\in Y$ and $z\in Z\smallsetminus g[Y].$ Note that $\langle Z,<_Z\rangle\cong\langle Z',<_{Z'}\rangle,$ and that $\langle Y,<_Y\rangle$ is a proper initial segment of $\langle Z',<_{Z'}\rangle,$ rather than simply being isomorphic to one. Define $f\bigl(\langle Z,<_Z\rangle\bigr)=\langle Z',<_{Z'}\rangle.$
• Limit Step: Finally, suppose $\langle L,<_L\rangle$ is an element of $\mathcal N$ with no immediate predecessor, and that $f\bigl(\langle X,<_X\rangle\bigr)$ has been defined for all $\langle X,<_X\rangle\in\mathcal N$ less than $\langle L,<_L\rangle.$ Let $U$ be the union of the first component of $f\bigl(\langle X,<_X\rangle\bigr)$ for all such $\langle X,<_X\rangle\in\mathcal N,$ $<_U$ the union of the second component of $f\bigl(\langle X,<_X\rangle\bigr)$ for all such $\langle X,<_X\rangle\in\mathcal N.$ One can show that $\langle U,<_U\rangle$ is a well-order strictly greater than each $f\bigl(\langle X,<_X\rangle\bigr),$ and less than $\langle L,<_L\rangle.$ If $\langle U,<_U\rangle$ is isomorphic to $\langle L,<_L\rangle,$ let $f\bigl(\langle L,<_L\rangle\bigr)=\langle U,<_U\rangle;$ otherwise, we construct $L'$ and $<_{L'}$ as in the successor step above, and let $f\bigl(\langle L,<_L\rangle\bigr)=\langle L',<_{L'}\rangle.$

Let $\mathcal N'$ be the image of the function $f,$ let $G$ be the union of all first components of elements of $\mathcal N',$ and let $<_G$ be the union of all second components of elements of $\mathcal N'.$ Finally, show that $\langle G,<_G\rangle$ is the well-order we seek.