Uncountable chains in an uncountable partially ordered set

Question

Let $(S,<)$ be a partially ordered set such that $S$ is uncountable and has the property that for all $x\in S$ there exists a $y\in S$ such that $y<x$. Is it always true that $S$ contains an uncountable chain (with or without assuming the axiom of choice)?

My basic approach would be to start with any $x_0\in S$ then pick a $x_1$ guaranteed by the condition such that $x_1<x_0$ and repeat the process indefinitely. However, I don't know if this is valid because this process is sequential and uncountable sets are not. I know that in assuming the axiom of choice, there would also be a well ordering on $S$ but this might not help at all because the poset may not extend to one. Any suggestions or counterexamples?

Answer 1

No, this isn't true: consider uncountably many copies of (say) $\mathbb{Z}$ with the usual ordering, placed "side-by-side."

(Concretely: let $I$ be some uncountable set, and let $\mathbb{P}$ be the partial order with underlying set $I\times\mathbb{Z}$ ordered by $$(i,a)\trianglelefteq(j,b)\quad\iff\quad i=j\mbox{ and }a\le b$$ where $\le$ is the usual ordering on $\mathbb{Z}$.)

---

That said, here are a couple quick comments (in $\mathsf{ZFC}$):

• If we strengthen the requirement to "For every countable chain $X\subseteq S$ there is a $y\in S$ with $y\trianglelefteq x$ for each $x\in X$," then the answer is affirmative: by transfinite recursion we can build a descending sequence of ordertype $\omega_1$.

• Meanwhile, that the counterexample above, while lacking long chains, does have long antichains (e.g. $\{(i,z): z\in\mathbb{Z}\}$ for any fixed $i\in I$). We can ask more subtle questions around both types of set; for example, is there an uncountable Boolean algebra in which every chain and antichain is countable? (See here.) In general, this sort of "uncountable Ramsey theory" takes us deep into combinatorial set theory and independence results.

---

Finally, note that if we drop choice things can get truly bizarre. It is consistent with $\mathsf{ZF}$ that there is an infinite Dedekind-finite set of real numbers with no least element (this occurs in Cohen's original model of $\mathsf{ZF+\neg AC}$); such a set, construed as a linear order in the usual way, is an uncountable linear order which satisfies your condition but doesn't have any infinite ascending or descending sequences! Generally some choice is needed to avoid serious silliness (on the other hand, sometimes we want to be silly ...).

Answer 2

Noah gave a good and complete answer. But let me make a small point about what can happen in $\sf ZF+\lnot AC$.

Noah mentions an uncountable linear order without any ascending or descending sequences. But an uncountable linear order is a chain, so to your question at large, it still has an uncountable chain.

On the other hand, you can have a tree, $T$, which means it is a partial order with a minimum where for every $t\in T$, $\{s\in T\mid s<_Tt\}$ is well-ordered by $<_T$, which is uncountable, does not have maximal elements, and does not have uncountable chains.

"Hang on a minute", you might say, "this has nothing to do with $\sf AC$". And you'd be right, even in $\sf ZFC$ we can find such objects.

1. If you want to be trivial, simply consider all the finite sequences of real numbers ordered by extension. Easily, this tree is uncountable, but we can't have an uncountable chain since the height of the tree is $\omega$.

2. Somewhat less trivial, consider the tree given by all well-ordered sequences of real numbers (well-ordered in the natural well-ordering of the reals, that is) that are indexed by any countable ordinal. That is, we look at all the order embeddings of any countable ordinal into the real numbers. Again, trivially this is uncountable, and every countable ordinal embed into the reals, but there is no uncountable chain in this tree, since that would define an order embedding of $\omega_1$ into $\Bbb R$. We can replace $\Bbb R$ by $\Bbb Q$ and nothing would be lost, by the way.

3. Even more non-trivial, $\sf ZFC$ still proves the existence of Aronszajn trees which are trees of height $\omega_1$, where every level of the tree is countable, but there are no uncountable chains. Indeed, this by itself can be enough to answer your original question. The original construction by Aronszajn was of a tree of ordinal-indexed sequences of rational numbers and it is truly worth seeing.

4. And even more seriously, you may have heard of a strengthening of Aronszajn trees called Suslin (or Souslin) trees, where we also don't have any uncountable antichains. The existence of these is independent of $\sf ZFC$ and they are very interesting combinatorial objects. But let's not go there today.

"But you promised to talk about $\sf ZF+\lnot AC$", I did, didn't I? Let's get back to that. Noah pointed out that if we replace the condition of "there are no maximal element" with "every countable chain is bounded" would suffice. And indeed, in all of these examples this is easily not the case.

So what happens in $\sf ZF+\lnot AC$? Or rather, would could happen in $\sf ZF+\lnot AC$? Well, we can have a tree where every countable chain has an upper bound, but there are no uncountable chains. The assertion that this does not happen, i.e., that such trees always have an uncountable chain, is called $\sf DC_{\omega_1}$, it is a strengthening of the Principle of Dependent Choice.

Another way of thinking about $\sf DC_{\omega_1}$ is that this is Zorn's Lemma with restricted power: If $P$ is a partial order where every countable chain has an upper bound, then $P$ has a maximal element or an uncountable chain.

As far as choice principles go, this one is not so innocent. It implies, among other things, the existence of non-measurable sets of reals; that $\omega_1$ is regular; countable choice; and much more.

But at the same time it is not strong enough to prove things like the existence of free ultrafilters on $\omega$; the idempotence of cardinal addition (i.e., for all infinite set $A$, $|A|=|A\times 2|$); and again, much more.

And finally, unlike its countable sibling, Dependent Choice (which can read as "every partial order has a maximal or an infinite chain"), it does not follow from $\sf AC_{WO}$. Namely, if every well-ordered family of sets has a choice function, then we can prove $\sf DC$. But we can't quite prove $\sf DC_{\omega_1}$.