4
$\begingroup$

These topics are outside of my area of research, so I am not quite sure where in the literature to find the answers.

In what follows, if $X$ is partially ordered and $n$ is a natural number, let $[[X]]^n$ denote the set of $S\subset X$ such that $|S|=n$ and $S$ is linearly ordered. A tree will be a partially ordered set $X$ such that for each $x\in X$, $$X|x:=\{y\in X: y\leqslant x\}$$ is a well-ordered set. The height of the tree $X$ is the supremum of the order types of $X|x$ as $x$ ranges through $X$. We define $d(X)$ to be the tree obtained by removing from $X$ all of its maximal members. We then define $$d^0(X)=X,$$ $$d^{\xi+1}(X)=d(d^\xi(X)),$$ and if $\xi$ is a limit ordinal, $$d^\xi(X)=\bigcap_{\zeta<\xi}d^\zeta(X).$$ We then define the rank of $X$ to be the minimum $\xi$ (assuming one exists) such that $d^\xi(X)=\emptyset$.

For the following questions, I suspect the answers are known, and if so, I would a reference. If the answers are not known, I would like to know what is the best partial result in this direction and some of the most relevant related results in the literature.

Question $1$: Given an ordinal $\xi$ and a tree $X$ with height $\omega^\xi$, is it true that either $(a)$ there exists a linearly ordered subset $B$ of $X$ such that the height of $B$ is $\omega^\xi$, or $(b)$ there exists a collection $(X_i)_{i\in I}$ of incomparable subsets of $X$ such that $\sup_{i\in I}\text{height}(X_i)=\omega^\xi$ EDIT and each $X_i$ is linearly ordered.

Question $2$: For a fixed natural number $n$, for which ordinals $\xi$ is the following true? If $X$ is a tree with height $\xi$ and if $[[X]]^n$ is colored with finitely many colors, there exists a subtree $Y$ of $X$ with height $\xi$ such that $[[Y]]^n$ is monochromatic.

Question $3$: Same as Question $2$, but with height replaced by rank.

$\endgroup$
15
  • $\begingroup$ Let N be the partially ordered set of the positive integers. I get what d(N^op) could be, but what is d(N)? Gerhard "Needs Understanding Of Simple Examples" Paseman, 2019.01.19. $\endgroup$ Commented Jan 19, 2019 at 21:10
  • $\begingroup$ $d(\mathbb{N})=\mathbb{N}$, since it has no maximal members. In the question, we have defined the rank to be the minimum $\xi$ such that $d^\xi(X)$ is empty assuming such a $\xi$ exists. For the natural numbers, there is no such $\xi$. More generally, for a tree $X$, $d^\xi(X)$ is empty for some $\xi$ if and only if $X$ has no subset which is order isomorphic to $\mathbb{N}$ if and only if there does not exist a sequence $(t_n)_{n=1}^\infty \subset X$ such that $t_1<t_2<\ldots$ (which is, under the reverse order $\geq$, the same as saying $\geq$ is a well-founded relation on $X$) $\endgroup$
    – user-1
    Commented Jan 19, 2019 at 22:22
  • $\begingroup$ For question $3$, the natural numbers would be excluded from consideration, since it does not have rank $\xi$ for any $\xi$. One could say that the rank of a tree $X$ is the class of ordinals $\zeta$ for which $d^\zeta(X)$ is non-empty. In this case, with the convention that $\xi=[0, \xi)$, this definition coincides for all well-founded trees, and the rank of $\mathbb{N}$ is the class Ord of all ordinals. The analogue of question $3$ for trees whose rank is Ord is the classical Ramsey theorem for finite colorings of $[\mathbb{N}]^n$. $\endgroup$
    – user-1
    Commented Jan 19, 2019 at 22:26
  • $\begingroup$ To elaborate, let us say a tree $X$ is ill-founded if $d^\xi(X)$ is non-empty for all $\xi$. The analogue of question $3$ in this case would be: If I color the $n$-element, linearly ordered subsets of an ill-founded tree $X$, is there an ill-founded subtree $Y$ all of whose $n$-element, linearly ordered subsets get the same color? This is equivalent to: If I color the $n$-element subsets of $\mathbb{N}$ with finitely many colors, is there an infinite subset $Y$ of $\mathbb{N}$ all of whose $n$-element subsets get the same color? $\endgroup$
    – user-1
    Commented Jan 19, 2019 at 22:32
  • $\begingroup$ To see why these questions are equivalent, a positive answer to the first question implies a positive answer to the second by taking $X=\mathbb{N}$ with its usual order, which is ill-founded. A positive answer to the second question implies a positive answer to the first because any ill-founded tree has a subset $Z$ order isomorphic to $\mathbb{N}$. A coloring on $X$ incudes a coloring on $Z$ and therefore on $\mathbb{N}$. We then find $Y'\subset \mathbb{N}$ infinite and monochromatic, which corresponds to an ill-founded $Y\subset X$. $\endgroup$
    – user-1
    Commented Jan 19, 2019 at 22:34

1 Answer 1

2
$\begingroup$

Question 1 is true for countable $\omega^\xi$ but it is at least consistent that this is false at $\omega_1.$ There might be a ZFC counterexample but the first thing that popped to mind is a Suslin tree. It is consistent with ZFC that there is a Suslin tree but it is also consistent that there aren't any.

To see that a Suslin tree $X$ is a counterexample, recall that a Suslin tree is a tree of height $\omega_1$ where every linearly ordered set is countable and every antichain is countable. Suppose we have a collection $(X_i)_{i \in I}$ of incomparable nonempty linearly ordered subsets of $X$. Let $x_i$ be the minimal element of $X_i$. This set $\{x_i \mid i \in I\}$ is an antichain, which must therefore be countable. Since each $X_i$ is countable, the supremum of the heights of the $X_i$ must be countable as well since $\omega_1$ is a regular cardinal.

Suslin trees generalize to higher levels and provide similar counterexamples higher up. It's harder to get rid of higher Suslin trees than it is to get rid of those with height $\omega_1$ but these are still conditional counterexamples since we can't prove the existence of such trees in ZFC.

For Question 2, if $n \geq 2$, it is necessary that $\xi$ is either $\omega$ or a weakly compact cardinal otherwise the result is false when $X$ is linearly ordered. The result is true for $\xi=\omega$ because of Ramsey's Theorem. There are two cases:

First, the easy case, if $X$ has a branch of height $\omega$ then apply the infinite form of Ramsey's Theorem to that branch.

Otherwise, by Kőnig's Lemma, the tree must have an infinite level. For simplicity, let's chop the base of the tree so that we can assume that the tree (or rather forest) has infinitely many roots. This gives a partition of $X$ into infinitely many rooted trees $(X_i)_{i \in I}$. Since $X$ has height $\omega$, the heights of these trees are unbounded and they are all finite. From a selection of these trees pick branches $Y_1,Y_2,\ldots$ so that the finite form of Ramsey's Theorem ensures that if $[Y_m]^n$ is $k$-colored then there is a homogeneous set $Z_m$ of size $m$ (where $n$ and $k$ are given by your setup). Apply Ramsey's Theorem to each $Y_m$ using your coloring and assemble the subchains $Z_m$ into a homogeneous tree of height $\omega$.

The same trick applies when $\xi$ is weakly compact. The basic idea is that a weakly compact cardinal satisfies the analogue of the infinite form of Ramsey's Theorem and it also has an analogue of Kőnig's Lemma. As a replacement for the finite form of Ramsey's Theorem, one needs to use the Erdős-Rado Theorem along with the observation that weakly compact cardinals are inaccessible.

$\endgroup$
4
  • $\begingroup$ I believe Question 1 should have a positive answer for any ordinal of countable cofinality. Your answer suggests that a definitive answer for all $\xi$ is unlikely. You have taken care of Question 2, although the answer is not nearly as nice as I had hoped. I know the answer for the $n=2$ case of Question 3, which is that $\xi$ has this property if and only if it is multiplicatively indecomposable. I had hoped for a similarly nice answer to Question 2. Do you know of any progress on Question 3? $\endgroup$
    – user-1
    Commented Jan 20, 2019 at 2:12
  • $\begingroup$ Rank is much trickier so I'm still thinking about Question 3. Yes, Question 1 does have a positive answer when $\xi$ has countable cofinality. I think you can stretch a Suslin tree to make a counterexample at ordinals of cofinality $\omega_1$. So, if $V=L$, where Suslin trees abound the only positive cases would be at ordinals of countable cofinality and possibly at ordinals of weakly compact cofinality. $\endgroup$ Commented Jan 20, 2019 at 2:17
  • $\begingroup$ If Question 3 is not already known for $n>2$, would you be interested in a collaboration? I answered the $n=2$ case of Question 3, which has given me some idea how one should proceed for the $n>2$ cases. $\endgroup$
    – user-1
    Commented Jan 20, 2019 at 2:39
  • $\begingroup$ This is definitely the kind of thing I like thinking about. I haven't had any clever ideas yet but you can find my contact info from my website. $\endgroup$ Commented Jan 20, 2019 at 3:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .