Showing every well-order is a chain

147 Views Asked by At

Exercise Show every well-ordering is a chain.

I have read the other articles on this site and they seem to be immersed more in the context of linear algebra, Banach spaces, or category theory. I seek to prove this in a way that is simple, clean, and order-theoretic.

Proof.

We begin by supposing that $(L, \leq)$ is a well-ordered set. It follows that $(L, \leq)$ is a partial order and for every nonempty subset $M$ of $L$, there exists a first element $m_0 \in M$ defined by

$$\forall m \in M \hspace{0.4cm} m_0 \leq M$$

Equivalently, we may say $m_0 = \min(M)$.


From here, I imagine it would be useful to partition $L$ into a collection of nonempty subsets and use the transitivity and antisymmetry of $\leq$ to generalize this result for any subset of $L$ and show that for $m_1, m_2 \in M$, either $m_1 \leq m_2$ or $m_2 \leq m_1$. Any advice or hints from this point?

1

There are 1 best solutions below

0
On BEST ANSWER

Turning my comment into an answer:

If every subset of $X$ has a $\trianglelefteq$-least element, then $(X,\trianglelefteq)$ must be a chain (= total order, linear order, and probably a few other terms): just apply the subset hypothesis to a given pair $\{x,y\}$. Either $\min\{x,y\}=x$ in which case $x\le y$, or $\min\{x,y\}=y$ in which case $y\le x$.


As a quick coda, note that all we're using here is that every pair has a least element. Indeed, this is equivalent to $(X,\trianglelefteq)$ being a chain (trivially - it's literally part of the definition of a chain). Well-orderedness is a strengthening of this property. The following are good exercises at this point:

  • Show that in a linear order, every finite subset has a least element.

  • Suppose $(X,\trianglelefteq)$ is a linear order in which every finite or countably infinite set has a least element. Show that $(X,\trianglelefteq)$ is in fact a well-ordering.

These exercises basically establish that in fact well-orderedness is the only way to strengthen the chain property along these lines. (Technically the second question uses a small amount of the axiom of choice.)