Combinatorial problems on trees: partitions, \(\Delta\)-systems and large free subtrees (Q1108269): Difference between revisions

The theorems on Erdős and Rado on \(\Delta\)-systems and of Fodor and Hajnal on free sets (and other results) are here generalised to a context of trees. The results were needed in previous work of the authors' [e.g. Isr. J. Math. 45, 100-146 (1983; Zbl 0552.03018), J. Symb. Logic 48, 542- 557 (1983; Zbl 0537.03026)]. Here it is set out systematically, in some generality, with some open questions. The general form of these generalisations replaces some underlying set by a tree of height \(\leq \omega\), with a notion of ``large subset'' replaced by a large subtree (one of which is isomorphic to the original). Thus the classical version of the \(\Delta\)-system lemma treats any collection \(\subseteq {\mathcal P}(C)\) and, under suitable conditions, gives a large subcollection which is a \(\Delta\)-system. The tree version treats a function F: \(T\to {\mathcal P}(C)\) (where T is a tree), and gives appropriate notions of \(\Delta\)-system and conditions to ensure that there is a large subtree \(T'\) of T such that \(F\upharpoonright T'\) is such a \(\Delta\)- system. Counterexamples show that the restriction to trees of height \(\leq \omega\) is needed.