0

Let X be a POSET. Show that one can write X as a union of two disjoint sets A and B such that A is well ordered (with respect to the ordering in X) and B has no least element

My approach
Intuitively, we can draw a Hasse diagram. If X has a least element, we can take a path starting from that and upto any element. And we can define a covering relation on that path (wrt to the ordering). Take that as set A, and the rest as B.
But I'm not sure.

Context: Introductory course in relations and set theory. No prior knowledge of topology.

xavitop
  • 41

1 Answers1

2

Edit: In response to the comments a proof using Zorn's lemma is also included in this answer. Notice that if $X$ is either well-ordered or does not have a least element there is nothing more to prove. The two sets are $X$ and $\varnothing$. Suppose that $X$ has a least element $x_{0}$ but $X$ is not well-ordered.

Define $W_{0} = \{ x_{0} \} $. Suppose that $\beta$ is an ordinal and for all ordinals $\alpha < \beta$ the set $W_{\alpha}$ has been defined and is well-ordered. Furthermore if $\alpha_{0} \leq \alpha_{1} < \beta$, then $W_{\alpha_{0}} \subseteq W_{\alpha_{1}}$.

If $\beta$ is a limit ordinal define $W_{\beta} = \cup \{ W_{\alpha} \colon \alpha < \beta \} $.

If $\beta = \alpha + 1$ there are two cases.

Case 1. The set $X \smallsetminus W_{\alpha}$ has a least element, say $x_{\beta}$. In this case define $W_{\beta} = W_{\alpha + 1} \cup \{ x_{\beta} \} $.

Case 2. The set $X \smallsetminus W_{\alpha}$ does not have a least element. In this case stop the construction. Define $A = W_{\alpha}$ and $B = X \smallsetminus W_{\alpha}$.

Since $X$ is a set, eventually you will run out of elements that can be well-ordered as in case 1. This puts you in case 2.

Proof using Zorn's lemma.

As above suppose that $X$ has a least element but $X$ is not well ordered. Define $$\mathcal{B} = \{ B \subseteq X \colon B \text{ does not have a least element} \text{.} \} $$ Since $X$ is not well-ordered, the set $\mathcal{B}$ is not empty. Suppose that $\mathcal{T} \subset \mathcal{B}$ is nonempty and totally ordered by inclusion. Select $t \in \cup \mathcal{T}$. For some $T \in \mathcal{T}$ we have $t \in T$. Since $T \in \mathcal{B}$, there is a $t^{*} \in T$ which satisfies $t^{*} < t$. But then $t$ is not the least element in $T$, which in turn means $t$ is not the least element in $\cup \mathcal{T}$. Thus $\cup \mathcal{T} \in \mathcal{B}$. Using Zorn's lemma, there is a maximal $B^{*} \in \mathcal{B}$.

Suppose that $X \smallsetminus B^{*}$ is not totally ordered. Then there exist $y_{0}, y_{1} \in X \smallsetminus B^{*}$ such that $y_{0} \not \leq y_{1}$ and $y_{1} \not \leq y_{0}$. Notice that $B^{*} \cup \{ y_{0}, y_{1} \}$ does not have a least element. This contradicts the maximality of $B^{*}$.

Suppose that $X \smallsetminus B^{*}$ is not well-ordered. Then there exists a nonempty $E \subseteq X \smallsetminus B^{*}$ which does not have a least element. Notice that $B^{*} \cup E$ does not have a least element. This contradicts the maximality of $B^{*}$.

Thus $X \smallsetminus B^{*}$ and $B^{*}$ are the desired sets.

Jay
  • 3,822
  • My only concern with this proof is that it uses transfinite induction on ordinals, while at the OP's level it might be better to rewrite it to use Zorn's lemma. –  Sep 15 '21 at 13:53
  • @Jay, I appreciate your help. However, I've not encountered cardinal arithmetic yet. So, it's hard for me to understand your solution. If you could explain it further, or reframe it... – xavitop Sep 15 '21 at 14:17
  • If you use a maximal set in $\mathcal{A} = {A \subset X \colon x_{0} \in A \text{ and } A \text{ is well-ordered} } $ it is not clear that a maximal element of $\mathcal{A}$ will be well-ordered. As the sets in totally ordered collection get bigger, they may introduce a descending sequence of elements in $X$ which will violate well-foundedness. – Jay Sep 15 '21 at 17:26
  • 1
    @xavitop, A proof using Zorn's lemma has been added to the answer. – Jay Sep 15 '21 at 19:33