Timeline for Partition Calculus and Ramsey theory question
Current License: CC BY-SA 4.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 20, 2019 at 2:06 | vote | accept | user-1 | ||
| Jan 20, 2019 at 2:02 | comment | added | François G. Dorais | An ordinal that has this partition property must be a cardinal. Suppose instead $\kappa < \xi$ is the cardinal number of $\xi.$ Pick an injection $f:\xi\to\kappa$ and color $[\xi]^2$ by $c(\alpha,\beta) = 0$ if $\alpha < \beta \land f(\alpha) < f(\beta)$ and $c(\alpha,\beta) = 1$ if $\alpha<\beta \land f(\alpha) > f(\beta)$. A homogeneous set of color $0$ has order type at most $\kappa$ and a homogeneous set of color $1$ must be finite since it is well-ordered both ways. | |
| Jan 20, 2019 at 1:37 | answer | added | François G. Dorais | timeline score: 2 | |
| Jan 20, 2019 at 1:08 | comment | added | user-1 | My formulation of Question 1 was incomplete. I have edited it. | |
| Jan 20, 2019 at 1:05 | comment | added | user-1 | As for your second comment, your answer is about cardinals, not ordinals. Is this intentional? | |
| Jan 20, 2019 at 1:01 | history | edited | user-1 | CC BY-SA 4.0 |
added 44 characters in body
|
| Jan 20, 2019 at 0:55 | comment | added | François G. Dorais | For question 2 and $n\geq2$, you need $\xi = \omega$ or $\xi$ is weakly compact. | |
| Jan 20, 2019 at 0:53 | comment | added | François G. Dorais | Thanks, but that leaves me puzzled about Question 1. If $X$ is linearly ordered then (a) works. If $X$ has two incomparable elements, pick $x_0$ such that $X_0=\{x \in X \mid x \geq x_0\}$ and $X_1 = \{x \in X \mid x \ngeq x_0 \land x \nleq x_0\}$ are nonempty. These two sets are incomparable and one of the two must have height $\omega^\xi.$ Is there a missing requirement? | |
| Jan 20, 2019 at 0:21 | comment | added | user-1 | By "incomparable subsets $(P_i)_{i\in I}$," I mean that for distinct $i,j$, no member of $P_i$ is related by $\leqslant $ to any member of $j$. By "subtree," I mean a subset of a tree which is also a tree. But since my definition of tree has the property that any subset of a tree is also a tree, here "subtree" is equivalent to "subset." | |
| Jan 20, 2019 at 0:17 | comment | added | François G. Dorais | Could you clarify what you mean by "incomparable subsets" and "subtree"? There's a few variants of each. | |
| Jan 20, 2019 at 0:07 | history | edited | user-1 | CC BY-SA 4.0 |
edited body
|
| Jan 19, 2019 at 22:51 | comment | added | user-1 | Then the maximal members of $D(\alpha, \beta)$ are the sequences whose last member is exactly $\alpha$. This is more or less the successor step of an induction proof that $d^\xi(D(\alpha, \beta))=D(\alpha+\xi, \beta)$. Since $D(\alpha, \beta)=\varnothing$ if and only if $\alpha \geq \beta$, $d^\xi(D(0, \beta))=D(\xi, \beta)$ is empty iff $\xi\geqslant \beta$, so the rank of $D(0, \beta)$ is $\beta$. | |
| Jan 19, 2019 at 22:48 | comment | added | user-1 | For an intuitive example. for ordinals $\alpha, \beta$, let $D(\alpha, \beta)$ be the set of sequences $(\gamma_i)_{i=1}^n$ such that $\beta>\gamma_1>\ldots >\gamma_n\geq \alpha$. Let $(\gamma_i)_{i=1}^n\leq (\delta_i)_{i=1}^m$ if $n\leq m$ and $\gamma_i=\delta_i$ for all $I\leq n$ (that is, if $(\gamma_i)_{i=1}^n$ is an initial segment of $(\delta_i)_{i=1}^m$). | |
| Jan 19, 2019 at 22:38 | comment | added | user-1 | Of course, it is Ramsey's theorem which tells us the second question has a positive answer. Therefore the analogue of Question 3 for ill-founded trees is already solved. So Question 3, as posed, avoids examples such as $\mathbb{N}$. | |
| Jan 19, 2019 at 22:34 | comment | added | user-1 | 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$. | |
| Jan 19, 2019 at 22:32 | comment | added | user-1 | 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? | |
| Jan 19, 2019 at 22:26 | comment | added | user-1 | 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$. | |
| Jan 19, 2019 at 22:22 | comment | added | user-1 | $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$) | |
| Jan 19, 2019 at 21:10 | comment | added | Gerhard Paseman | 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. | |
| Jan 19, 2019 at 20:15 | history | edited | user-1 | CC BY-SA 4.0 |
I removed undefined notation.
|
| Jan 19, 2019 at 20:05 | review | First posts | |||
| Jan 19, 2019 at 20:46 | |||||
| Jan 19, 2019 at 20:02 | history | asked | user-1 | CC BY-SA 4.0 |