Distality Rank and Tree Dimension

Building on Pierre Simon's notion of distality, Part I of our thesis introduces distality rank as a property of first-order theories and gives examples for each rank. For NIP theories, we show that distality rank is invariant under base change. We also define a generalization of type orthogonality called m-determinacy and show that theories of distality rank m require certain products to be m-determined. Furthermore, for NIP theories, this behavior characterizes m-distality. If we narrow the scope to stable theories, we observe that m-distality can be characterized by the maximum cycle size found in the forking “geometry,” so it coincides with (m-1)-triviality. On a broader scale, we see that m-distality is a strengthening of Saharon Shelah's notion of m-dependence. We also introduce strong distality rank which applies to global invariant types and formulas, as well as EM-types and theories. When applied to definable sets, this stronger variant provides a means of cell decomposition. If the defining formula is distal, this decomposition is equivalent to the one provided by strong honest definitions. Part II of our thesis introduces tree dimension and its leveled variant in order to measure the complexity of leaf sets for finite-height binary trees. We then provide a tight upper bound for the size of an arbitrary leaf set based on its leveled tree dimension. This, in turn, implies the famous Sauer-Shelah Lemma for Vapnik-Chervonenkis dimension and Bhaskar's version for Littlestone dimension giving clearer insight into why these results place the exact same upper bound on their respective shatter functions. We also fully classify the maximal leaf sets for each tree dimension by isomorphism type. With appropriate modifications, these results extend to higher-arity trees. Finally, we apply our analysis to infinite-height binary trees.