According to the well ordering theorem "Any set can be well ordered". Whenever we have a well ordering on a set, it is not difficult to construct a new well ordering with a largest element.
My question is:

For a given infinite set, can we find a well ordering on it such that there is no largest element?

  • 2
    $\begingroup$ Set of natural numbers. $\endgroup$ – Wuestenfux Jul 2 '17 at 18:54
  • 2
    $\begingroup$ Induce the well-order by a bijection with a cardinal number. $\endgroup$ – Daniel Fischer Jul 2 '17 at 18:55
  • $\begingroup$ Use Choice + transfinite induction to define it one at a time? $\endgroup$ – Chappers Jul 2 '17 at 19:02
  • $\begingroup$ math.stackexchange.com/questions/6501/… $\endgroup$ – Count Iblis Jul 2 '17 at 19:16
  • $\begingroup$ @CountIblis That question is not related to this one at all. $\endgroup$ – Noah Schweber Jul 2 '17 at 20:02

Yes. In fact, there is a canonical way to transform a well-ordering into a well-ordering of the same set with no greatest element.

Suppose I have an infinite well-order $X$. Let $F_X$ be the set of elements of $X$ with finitely many things bigger than them - for instance, the greatest element of $X$ (if such an element exists) is in $F_X$, while (if $X$ is infinite) the least element of $X$ (which always exists, since $X$ is a well-ordering) is not in $F_X$.

It's not hard to show that $F_X$ is finite, since otherwise we could build an infinite descending chain in $X$ (exercise). Now let $I_X=X\setminus F_X$; this is a well-ordered set with no greatest element.

If $X$ is infinite, $I_X$ and $X$ have the same cardinality. If you want an explicit isomorphism, we can "move $F_X$ to the back" - define a new ordering $\prec$ on $X$, given by $a\prec b$ iff

  • $a, b\in I_X$ and $a<b$ in the original sense of $X$; or

  • $a, b\in F_X$ and $a<b$ in the original sense of $X$; or

  • $a\in F_X, b\in I_X$.


If $A$ is infinite then $A$ can be put in bijection with $A \cup \mathbb{N}$. Now from the well ordering of $A$ you can ge a well ordering of $A \cup \mathbb{N}$ without a largest element ( in the obvious way ) and then back, a new well-ordering of $A$ without a largest element.

  • 2
    $\begingroup$ As an interesting aside, note that for the first sentence, we either need a weak form of the axiom of choice or the assumption (which is present here) that $A$ is well-orderable: it is consistent with ZF that there is an infinite set $A$ which is not in bijection with $A\cup\mathbb{N}$ (namely, any infinite Dedekind-finite set). $\endgroup$ – Noah Schweber Jul 2 '17 at 21:48
  • 1
    $\begingroup$ @Noah Schweber: Very interesting.! To do away with the bijection, I guess we could just move $\mathbb{N}$ from the beginning to the end, similarly to the move in your solution. $\endgroup$ – Orest Bucicovschi Jul 2 '17 at 23:44

In the usual development of ZFC, a cardinal is defined to the the least ordinal with a given cardinality. Infinite cardinals are "limit ordinals" --- as ordered sets they have no largest element.


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.