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.

  • $\begingroup$ Huh? What are you trying to prove? $\endgroup$ – Asaf Karagila Mar 30 '18 at 12:43
  • $\begingroup$ @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. $\endgroup$ – Alvin Lepik Mar 30 '18 at 12:43
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Mar 30 '18 at 12:51

Your proof is overly complicated, and the reliance on the axiom of choice is itself a bad direction. The construction ultimately leads to Hartogs' theorem which implies the axiom of choice follows from the comparability of any two cardinals. If we had used the axiom of choice to prove Hartogs' theorem, then this would be circular.

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

  • $\begingroup$ Your advice under main post is certainly sensible. It's more akin to struggling to get free from a spider's web. The more you struggle, the tighter the web gets around you. Thanks for the breath of fresh air :D $\endgroup$ – Alvin Lepik Mar 30 '18 at 13:01
  • $\begingroup$ In hindsight, I'd have known not to use choice if I knew the ins and outs of Hartog's theorem. We're just given these things as exercises and mostly they're just routine checks. Sometimes things get weird, though. $\endgroup$ – Alvin Lepik Mar 30 '18 at 13:04
  • 1
    $\begingroup$ Well, hindsight 20/20. I can't even count the number of mistakes that in retrospect I should have never made. :) $\endgroup$ – Asaf Karagila Mar 30 '18 at 13:09
  • $\begingroup$ Good point, I withdraw my statement. $\endgroup$ – Alvin Lepik Mar 30 '18 at 13:11

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.