Is it possible, in ZFC, to find an $\omega_1$-branching tree $(T,\leq)$ of size and height $\omega_1$ such that whenever $T$ is partitioned into countably many sets $T=\bigcup_{n<\omega} T_n$ one of the sets $T_n$ contains a subset $S$ which is again an $\omega_1$-branching tree of size and height $\omega_1$ (with the tree order on $S$ being just $\leq$ restricted to $S$).

  • 1
    $\begingroup$ Can't you put all the nodes occurring at limit levels into $T_1$ and the rest into $T_2$? $\endgroup$
    – Ashutosh
    Aug 7 '14 at 14:39
  • 1
    $\begingroup$ Then $T_2$ (and, typically, also $T_1$) would be $\omega_1$-branching and have height $\omega_1$. $\endgroup$ Aug 7 '14 at 14:47
  • 2
    $\begingroup$ Do you have an example of such $T$ which cannot be partitioned? Because it seems to me that at least one of these $T_n$'s would have to meet uncountably many levels on an uncountable set. $\endgroup$
    – Asaf Karagila
    Aug 7 '14 at 14:52
  • $\begingroup$ Jonathan, You are right, I understand your question now. Asaf, it may happen that the nodes you describe are all at level one (being incomparable) of $T_n$. Some coherence is required. $\endgroup$
    – Ashutosh
    Aug 7 '14 at 14:58
  • 1
    $\begingroup$ @AsafKaragila: Yes, but the tree could collapse, as the tree structure is just the restriction of $\leq$. For example, I think the following should work: Take a Suslin tree and glue a full $\omega_1$-ary tree of height $\omega$ to every node. Now color the original nodes by $0$ and the added nodes by $1$. Then $T_0$ is just the original Suslin tree (so it isn't $\omega_1$ branching and no subset of it is) while $T_1$ collapses into a tree of height $\omega_1$. $\endgroup$ Aug 7 '14 at 14:59

The existence of such trees is independent of ZFC.

On one hand, if $CH$ holds then $\omega_1^{<\omega_1}$ (and in fact - any $\sigma$-closed $\omega_1$-branching tree) cannot be partitioned into $\aleph_0$ many subsets, each does not contain an $\omega_1$-branching tree.

Proof: Assume otherwise and let $T_n$ be such partition.

Claim: For each $n<\omega$, each $t\in T$ can be extended to a node $s\in T$ such that $s$ has no extension in $T_n$.

Proof: If this failed for some $n$ then $T_n$ would be $\omega_1$-branching of height $\omega_1$. $\blacksquare$

Using the claim we can construct, by recursion on $n$, a strictly increasing sequence of $s_n$'s such that $s_n$ has no extension in $T_n$. Then, by $\sigma$-closedness of $T$, all of them would have a single extension $s_\omega\in T$. However, $s_\omega$ would have no extension in any $T_n$ contradicting the fact that $T=\bigcup T_n$.$\square$

On the other hand, it is consistent (relative to the existence of an inaccessible) that $2^{\aleph_0} = \aleph_2$ and every tree of height and size $\omega_1$ can be partitioned into countably many subsets, each not containing an $\omega_1$-branching subtree.

Definition: Let $T$ be a tree of height $\omega_1$, $|T|=\omega_1$. $T$ is special if there is a function $f:T\to \omega$ such that for every $x,y,z\in T$ if $f(x)=f(y)=f(z)$ and $x\leq y,z$ then $y\leq z$ or $z\leq y$.

If $T$ is special, as witnessed by $f$, then $T_n = f^{-1}(n)$ is the desired partition: for every $x\in T_n$, $x$ doesn't have any two incompatible successors in $T_n$, since if $x\leq y,z$ and $y,z\in T_n$ then $f(y)=f(z)=f(x)=n$ and therefore $y$ and $z$ are comparable.

Theorem (Todorcevic/Baumgartner): The statement "Every tree of size and height $\omega_1$ is special" is equiconsistent with the existence of an inaccessible cardinal.

See "Some Combinatorial Properties of Trees" by Todorcevic, and "Aronszajn trees and the independence of the transfer property" by Mitchell for more details.

  • $\begingroup$ I wasted several past hours thinning $\omega_1^{< \omega_1}$, so thanks for ending my misery. $\endgroup$
    – Ashutosh
    Aug 7 '14 at 20:39
  • $\begingroup$ This is also in Baumgartner's Iterated Forcing (Surveys in set theory, 1–59, LMS Lecture Note Series 87, 1983; MR0823775). If memory serves correctly, there were more details in there. $\endgroup$ Aug 7 '14 at 21:50
  • 1
    $\begingroup$ It's interesting to check whether the consistency strength of the negative answer is indeed inaccessible. "Every tree is special" seems to be a stronger assertion, so it might be the case that it's possible to prove the consistency of the negative answer without any large cardinals. $\endgroup$
    – Yair Hayut
    Aug 8 '14 at 5:42
  • $\begingroup$ @FrançoisG.Dorais thanks for the reference! $\endgroup$ Aug 8 '14 at 9:21
  • $\begingroup$ @YairHayut, well that's what I'll be looking at next :-) Btw. thanks for the quick answer; would you mind if I edit the first part of your answer slightly? $\endgroup$ Aug 8 '14 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.