On some tree partitions.

Abstract

A large part of combinatorial set theory is concerned with the study of partitions. In 1930, F. P. Ramsey published his paper "On a Problem of Formal Logic." This contained his now famous Ramsey's theorem. Many other partition theorems followed, creating a diverse collection and the discipline of Ramsey theory. This thesis begins with the study of finite partitions of infinite perfect trees (similar to partitions seen in the Halpern-Lauchli theorem). For such partitions, we get perfect homogeneous subtrees. These tree partitions naturally give rise to the study of (a) some ultrafilters on the set of natural numbers, and (b) a new cardinal characteristic of the continuum. These ultrafilters, called hlt-ultrafilters (for "homogeneous level trees"), have a Ramsey-like definition. Hlt-ultrafilters, however, are more general than p-point ultrafilters, which in turn generalize Ramsey ultrafilters. We also define and study hlt, the cardinal characteristic of the continuum mentioned above. In ZFC, we relate hlt to other well-known cardinal characteristics of the continuum, namely r, r$\sb\sigma$, and d. We give a consistency result involving hlt and study hlt$\sp\prime$, another cardinal characteristic, which is a variation of hlt. Finally, the study of the proofs that relate cardinal characteristics of the continuum to one another, such as the ones mentioned above, but also others unrelated to hlt, gives rise to a notion of proof complexity, introduced by Peter Vojtas. He has asked whether the complexity of such proofs can be reduced. We show that the answer "yes" is consistent in some cases (assuming the continuum hypothesis) but, in some other cases, the answer "no" is provable.