Combinatorial problems on trees: partitions, \(\Delta\)-systems and large free subtrees
type: Item
instance of: scholarly article
title: Combinatorial problems on trees: partitions, \(\Delta\)-systems and large free subtrees
zbMATH Open document ID: 0654.04002
DOI: 10.1016/0168-0072(87)90075-3
author: Matatyahu Rubin
author: S. Shelah
published in: Annals of Pure and Applied Logic
publication date: 1987-01-01T00:00:00Z
review text: 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.
reviewed by: F.R.Drake
Mathematics Subject Classification ID: 03E05
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 4066889
zbMATH Keywords: large free subtrees
zbMATH Keywords: partition theorems
zbMATH Keywords: \(\Delta\)-systems
MaRDI profile type: Publication
full work available at URL: 0168-0072(87)90075-3
OpenAlex ID: W2095026520
cites work: Intersection Theorems for Systems of Sets (II)
cites work: Q3237252
cites work: Proof of a conjecture of B. Ruziewicz
cites work: Q3852172
cites work: Borel determinacy
cites work: Q5678856
cites work: On the expressibility hierarchy of Magidor-Malitz quantifiers
cites work: Iterated forcing and changing cofinalities
cites work: Proper forcing
cites work: Constructions of many complicated uncountable structures and Boolean algebras
cites work: An ideal game
description: scientific article; zbMATH DE number 4066889