A linear order with sequences of length $\omega_0$ but without sequences of length $\omega_1$.

121 Views Asked by At

Given a set $S$ of cardinal $|S|\geq \omega_1$, can I give a linear < order on S such that at least one of the following two options A) or B) happen?

Option A): A.1) and A.2) are satisfied.

A.1) There are infinite countable increasing sequences.

A.2) There aren't uncountable increasing sequences.

Option B): B.1) and B.2) are satisfied.

B.1) There are infinite countable decreasing sequences.

B.2) There aren't uncountable decreasing sequences.

1

There are 1 best solutions below

6
On BEST ANSWER

It's not totally clear what you mean by "sequence". In this answer, I assume you're talking about sequences indexed by ordinals. So, e.g., an increasing sequence is $(x_\beta)_{\beta<\alpha}$, where $\alpha$ is an ordinal and $x_\beta < x_\gamma$ for all $\beta<\gamma<\alpha$.

Let $\kappa$ be an uncountable cardinal (viewed as an initial ordinal). The linear order $\omega^{\mathrm{op}}+\kappa$ satisfies your Option B. Indeed, the copy of $\omega^{\mathrm{op}}$ is a countable decreasing sequence. And any decreasing sequence includes only finitely many elements of $\kappa$ (since $\kappa$ is well-ordered), followed by elements of $\omega^{\mathrm{op}}$, so it is at most countable. In fact, an ordinal-indexed decreasing sequence in this order cannot be indexed by any ordinal greater than $\omega$.

The order $\omega^{\mathrm{op}}+\kappa$ has cardinality $\kappa$, so if $S$ is any set of cardinality $\kappa$, we can equip $S$ with a linear order isomorphic to $\omega^{\mathrm{op}}+\kappa$.

Similarly, $\kappa^{\mathrm{op}} + \omega$ satisifes your Option A, and any set of cardinality $\kappa$ can be equipped with a linear order isomorphic to $\kappa^{\mathrm{op}} + \omega$.


A more interesting question is to determine the possible cardinalities of linear orders satisfying both Option A and Option B. That is, linear orders with infinite increasing and descending sequences, but no uncountable increasing or decreasing sequences.

Let me first point out:

Theorem 1: Every infinite linear order has an infinite increasing sequence or an infinite decreasing sequence.

Proof: Let $(L,<)$ be a linear order, and choose a well-order $\lessdot$ on $L$ (which may have nothing to do with $<$). Now for each pair $a\neq b$ in $L$ with $a\lessdot b$, color $\{a,b\}$ blue if $a<b$, and color $\{a,b\}$ red if $b<a$. By Ramsey's theorem, $L$ has an infinite monochromatic subset $L'\subseteq L$. Note that $L$ is well-ordered by $\lessdot$, so we can naturally view it as an infinite ordinal-index sequence. If it is monochromatic blue, it is an increasing sequence, and if it is monochromatic red, it is a decreasing sequence. $\square$

Now suppose $(L,<)$ is an infinite linear order with no uncountable increasing or decreasing sequences. By Theorem 1, $L$ has either an infinite increasing sequence or an infinite decreasing sequence. Define $L' = L+L^{\mathrm{op}}$. Then $|L'| = |L|$, $L'$ has both infinite increasing and infinite decreasing sequences (one in $L$ and one in $L^{\mathrm{op}}$), and $L'$ has no uncountable increasing or decreasing sequences (since the intersection of such a sequence with $L$ or with $L^{\mathrm{op}}$ would again be uncountable).

This shows that the problem reduces to: What are the possible cardinalities of infinite linear orders with no uncountable increasing or decreasing sequences? Let's call such a linear order "short".

It's a classic fact that $\mathbb{R}$ has no uncountable increasing or decreasing sequences (because it has a countable dense set $\mathbb{Q}$). See here, for example. So there is a short linear order of cardinality $2^{\aleph_0}$.

Now for any $\kappa$ with $\aleph_0\leq \kappa\leq 2^{\aleph_0}$, let $L\subseteq \mathbb{R}$ be a subset of cardinality $\kappa$. The induced order on $L$ is short, because any sequence in $L$ is a sequence in $\mathbb{R}$.

Ok, so we can get short linear orders of any infinite cardinality $\kappa\leq 2^{\aleph_0}$. What about $\kappa>2^{\aleph_0}$? The answer is no, by a strengthening of Theorem 1.

Theorem 2: Every linear order $(L,<)$ with $|L|>2^{\aleph_0}$ has an uncountable increasing sequence or an uncountable decreasing sequence.

Proof: Same as Theorem 1, but this time we apply the Erdös-Rado theorem. As a special case of Erdös-Rado, we have $(2^{\aleph_0})^+\rightarrow (\aleph_1)^2_{\aleph_0}$. In English, this says that if $S$ is a set with $|S|>2^{\aleph_0}$ and we color each pair from $S$ by one of a countable number of colors, then we can find a monochromatic subset of cardinality $\aleph_1$. Applying the same coloring as in the proof of Theorem 1, we find an uncountable subset of $L$, well-ordered by $\lessdot$, which is either an increasing sequence or a decreasing sequence in $L$.

This shows that if a linear order is short, then it has cardinality $\leq 2^{\aleph_0}$.